From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Thomas Lord Newsgroups: gmane.emacs.devel Subject: Re: regexp does not work as documented Date: Sun, 11 May 2008 13:03:00 -0700 Message-ID: <482750F4.2050102@emf.net> References: <87k5i8ukq8.fsf@stupidchicken.com> <200805061335.11379.bruno@clisp.org> <48204B3D.6000500@gmx.at> <4826A303.3030002@gmx.at> <87abiwoqzd.fsf@stupidchicken.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="------------070006010001000508030704" X-Trace: ger.gmane.org 1210533622 25933 80.91.229.12 (11 May 2008 19:20:22 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 11 May 2008 19:20:22 +0000 (UTC) Cc: Chong Yidong , 192@emacsbugs.donarmstrong.com, emacs-devel@gnu.org, martin rudalics , David Koppelman , Bruno Haible To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun May 11 21:20:58 2008 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1JvH6M-0005ft-Uq for ged-emacs-devel@m.gmane.org; Sun, 11 May 2008 21:20:55 +0200 Original-Received: from localhost ([127.0.0.1]:33056 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1JvH5e-0000B2-4I for ged-emacs-devel@m.gmane.org; Sun, 11 May 2008 15:20:10 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1JvH5Z-000098-7O for emacs-devel@gnu.org; Sun, 11 May 2008 15:20:05 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1JvH5Y-00008S-JC for emacs-devel@gnu.org; Sun, 11 May 2008 15:20:04 -0400 Original-Received: from [199.232.76.173] (port=48932 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1JvH5Y-00008J-Eh for emacs-devel@gnu.org; Sun, 11 May 2008 15:20:04 -0400 Original-Received: from mail.42inc.com ([205.149.0.25]:35107) by monty-python.gnu.org with esmtps (SSL 3.0:RSA_3DES_EDE_CBC_SHA1:24) (Exim 4.60) (envelope-from ) id 1JvH5Y-00039o-07 for emacs-devel@gnu.org; Sun, 11 May 2008 15:20:04 -0400 X-TFF-CGPSA-Version: 1.5 X-TFF-CGPSA-Filter-42inc: Scanned X-42-Virus-Scanned: by 42 Antivirus -- Found to be clean. Original-Received: from [69.236.114.9] (account lord@emf.net HELO [192.168.1.64]) by mail.42inc.com (CommuniGate Pro SMTP 5.0.13) with ESMTPA id 30292298; Sun, 11 May 2008 12:19:49 -0700 User-Agent: Thunderbird 1.5.0.5 (X11/20060808) In-Reply-To: X-detected-kernel: by monty-python.gnu.org: Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:96979 Archived-At: This is a multi-part message in MIME format. --------------070006010001000508030704 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit >> 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 --------------070006010001000508030704 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 
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


--------------070006010001000508030704--