[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: regexp does not work as documented

From: Thomas Lord
Subject: Re: regexp does not work as documented
Date: Sun, 11 May 2008 13:03:00 -0700
User-agent: Thunderbird (X11/20060808)

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]