Subject: bug#192: regexp does not work as documented

From: Stefan Monnier <[email-masked]>
Date: Sun, 11 May 2008 21:43:47 -0400

> 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.

That's a very good point.  I'm not sure it's worth the trouble to store
it at various buffer positions and check if it's EQ to stop the rescan,
but at least we could match multiline expression one-line at a time.

In any case, it's indeed a non-trivial amount of work because it
probably requires rewriting not just font-lock but all the
foo-mode-font-lock-keywords as well (font-lock-keywords are order
dependent so you can't apply the rule nb 3 after rule nb 4).

> 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.

I have most of the DFA construction code written, but I may take you up
on that anyway.  BTW, regarding the "very expensive in the worst case",
how common is this worst case in real life?

        Stefan