GNU bug report logs - #192
regexp does not work as documented

Previous Next

Full log

View this message in rfc822 format

From: Thomas Lord <lord <at> emf.net>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Chong Yidong <cyd <at> stupidchicken.com>, martin rudalics <rudalics <at> gmx.at>,
        David Koppelman <koppel <at> ece.lsu.edu>, 192 <at> debbugs.gnu.org,
        Bruno Haible <bruno <at> clisp.org>, emacs-devel <at> gnu.org
Subject: bug#192: regexp does not work as documented
Date: Sun, 11 May 2008 13:03:00 -0700

[Message part 1 (text/plain, inline)]

>> As for making hi-lock-mode detect whether or not a regexp is multi-line,
>> isn't that a computationally non-trivial problem?
>>     
>
> Well, you can turn the regexp into a DFA, then take the ".*\n.+" regexp,
> turn it into another DFA, take the intersection of the two DFAs, and if
> it's empty you know your regexp can never match a multiline element.
>   

If you are going to go that that trouble, perhaps there is a better 
solution:

The Rx pattern matcher found in distributions of GNU Arch has these
relevant capabilities (relevant at least so far as I understand the 
problem you
are trying to solve):

1. It does on-the-fly regexp->DFA conversion, degrading gracefully into
   mixed NFA/DFA mode or pure NFA mode if the DFA would be too
   large.   The calling program gets to say what "too large" is.

2. Although it is a C library, you can capture what is (in essence) the
   continuation of an on-going match.   That is, you can suspend a
   match (or scan) part-way through, then later resume from that point,
   perhaps multiple times.   (This does not involve abusing the C stack.)

3. It does have some Unicode support in there and, though these capabilities
   are under-tested and some features are missing, it is quite flexible 
about
   encoding forms.

4. The DFA construction is "caching" and, for a given regexp, all uses
   will share the DFA construction.   E.g., multiple, suspended regexp
   continuations can be space efficient because they will share state.

5. Because of the caching and structure sharing, you can tell if two 
continuations
   from a single regexp have arrived at the same state with a C EQ test 
("==").

How can this help?

Well, instead of using heuristics to decide where to re-scan from and 
too, you
can cache a record of where the DFA scan arrived at for periodic 
positions in the
buffer.   Then begin scanning from just before any modification for as 
far as it
takes to arrive at a DFA state that is the same as last time, updating 
any highlighting
in the region between those two points.

I don't mean to imply that this is a trivial thing to implement in Emacs but
if you start getting up to building DFAs (very expensive in the worst 
case) and
taking intersections (very expensive in the worst case) -- both also not 
all that
simple to implement (nor obviously possible for Emacs' extended regexp 
language) --
then the effort may be comparable and (re-)visiting the option to adapt 
Rx to Emacs
should be worth considering.

As a point of amusement and credit where due, I think it was Jim Blandy 
who first noticed this
possibility in the early 1990s when I was explaining to him the 
capabilities I
was then just beginning to add to Rx.

This is a very old problem, long recognized, with some work already done on
a (purportedly) Right Thing solution.

-t

[Message part 2 (text/html, inline)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.