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

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Thomas Lord <lord <at> emf.net>
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 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

Previous Next

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