From: Thomas Lord <lord@emf.net>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Chong Yidong <cyd@stupidchicken.com>,
192@emacsbugs.donarmstrong.com, emacs-devel@gnu.org,
martin rudalics <rudalics@gmx.at>,
David Koppelman <koppel@ece.lsu.edu>,
Bruno Haible <bruno@clisp.org>
Subject: Re: regexp does not work as documented
Date: Sun, 11 May 2008 13:03:00 -0700 [thread overview]
Message-ID: <482750F4.2050102@emf.net> (raw)
In-Reply-To: <jwv8wygrbss.fsf-monnier+emacsbugreports@gnu.org>
[-- Attachment #1: Type: text/plain, Size: 2842 bytes --]
>> 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
[-- Attachment #2: Type: text/html, Size: 3655 bytes --]
next prev parent reply other threads:[~2008-05-11 20:03 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-05-06 4:20 regexp does not work as documented Chong Yidong
2008-05-06 11:35 ` Bruno Haible
2008-05-06 12:12 ` martin rudalics
2008-05-10 19:18 ` bug#192: " David Koppelman
2008-05-10 19:18 ` David Koppelman
2008-05-10 20:13 ` David Koppelman
2008-05-11 7:40 ` bug#192: " martin rudalics
2008-05-11 7:40 ` martin rudalics
2008-05-11 14:27 ` Chong Yidong
2008-05-11 15:36 ` bug#192: " David Koppelman
2008-05-11 15:36 ` David Koppelman
2008-05-11 18:44 ` Stefan Monnier
2008-05-11 19:09 ` David Koppelman
2008-05-12 1:28 ` bug#192: " Stefan Monnier
2008-05-12 1:28 ` Stefan Monnier
2008-05-12 15:03 ` David Koppelman
2008-05-12 16:29 ` bug#192: " Stefan Monnier
2008-05-12 16:29 ` Stefan Monnier
2008-05-12 17:04 ` David Koppelman
2008-05-12 17:04 ` bug#192: " David Koppelman
2008-05-12 15:03 ` David Koppelman
2008-05-11 19:09 ` David Koppelman
2008-05-11 18:44 ` Stefan Monnier
2008-05-11 18:44 ` Stefan Monnier
2008-05-11 20:03 ` Thomas Lord [this message]
2008-05-12 1:43 ` bug#192: " Stefan Monnier
2008-05-12 1:43 ` Stefan Monnier
2008-05-12 3:30 ` bug#192: " Thomas Lord
2008-05-12 3:30 ` Thomas Lord
2008-05-12 13:43 ` bug#192: " Stefan Monnier
2008-05-12 13:43 ` Stefan Monnier
2008-05-12 15:55 ` bug#192: " Thomas Lord
2008-05-12 15:55 ` Thomas Lord
2008-05-12 16:18 ` bug#192: " tomas
2008-05-12 16:18 ` tomas
2008-05-11 20:03 ` bug#192: " Thomas Lord
2008-05-11 18:44 ` Stefan Monnier
2008-05-11 14:27 ` Chong Yidong
2008-05-10 20:13 ` David Koppelman
2008-05-06 15:35 ` Stefan Monnier
2008-05-06 21:29 ` Bruno Haible
2008-05-10 20:04 ` Bruno Haible
2008-05-10 20:04 ` bug#192: " Bruno Haible
2008-05-06 15:00 ` David Koppelman
2008-05-06 21:35 ` Bruno Haible
2008-05-07 1:04 ` Stefan Monnier
2008-05-07 1:08 ` Auto-discovery of multi-line font-lock regexps Stefan Monnier
2008-05-07 3:46 ` Chong Yidong
2008-05-07 4:21 ` Stefan Monnier
-- strict thread matches above, loose matches on Subject: below --
2008-05-06 1:30 regexp does not work as documented Bruno Haible
2008-05-06 14:15 ` Johan Bockgård
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=482750F4.2050102@emf.net \
--to=lord@emf.net \
--cc=192@emacsbugs.donarmstrong.com \
--cc=bruno@clisp.org \
--cc=cyd@stupidchicken.com \
--cc=emacs-devel@gnu.org \
--cc=koppel@ece.lsu.edu \
--cc=monnier@iro.umontreal.ca \
--cc=rudalics@gmx.at \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.