How are regexen implemented in Emacs?

How are regexen implemented in Emacs?

[Marcin Borkowski]

Hi all,

some time ago I read (well, skimmed) this article:
https://swtch.com/~rsc/regexp/regexp1.html

I looked at
https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
and started to wonder if the hints there mean that Emacs has a "naive",
backtracking regex engine or a FA-based one?

Before I get yelled at, let me make it clear: I'm not accusing Emacs
devs of sloppy programming.  In fact, my confusion might result from me
not understanding something.  But the warnings in the manual about some
regexen being slow worry me a tiny little bit.

Best,

-- 
Marcin Borkowski
http://mbork.pl

Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor]

> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
> and started to wonder if the hints there mean that Emacs has a "naive",
> backtracking regex engine or a FA-based one?

Naive!


        Stefan

Re: How are regexen implemented in Emacs?

[Marcin Borkowski]

On 2022-12-12, at 19:16, Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org> wrote:

>> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
>> and started to wonder if the hints there mean that Emacs has a "naive",
>> backtracking regex engine or a FA-based one?
>
> Naive!

And what are the reasons?  Out of curiosity: would implementing
a FA-based one be a very big undertaking?  (And no, I won't do it, if
only because I don't know C.)

Best,

-- 
Marcin Borkowski
http://mbork.pl

Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor]

>>> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
>>> and started to wonder if the hints there mean that Emacs has a "naive",
>>> backtracking regex engine or a FA-based one?
>> Naive!
> And what are the reasons?

Largely historical, but changing it is a lot of work with uncertain
outcome:
- Reproducing the exact behavior of the naive match with a non-naive
  match can be tricky.
- The naive approach sucks when the match fails in many
  different ways, but it's quite efficient when the match succeeds
  without any backtracking.
Ideally, we'd like to replace the regexp engine with a "standard one",
but it's not easy to find one that satisfies all the requirements
(e.g. ability to add Emacs-specific elements like \_<, \s, and \c,
ability to operate on "two-part strings" (i.e. with a gap in the
middle), ...).


        Stefan

Re: How are regexen implemented in Emacs?

[Marcin Borkowski]

On 2022-12-12, at 20:17, Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org> wrote:

>>>> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
>>>> and started to wonder if the hints there mean that Emacs has a "naive",
>>>> backtracking regex engine or a FA-based one?
>>> Naive!
>> And what are the reasons?
>
> Largely historical, but changing it is a lot of work with uncertain
> outcome:
> - Reproducing the exact behavior of the naive match with a non-naive
>   match can be tricky.
> - The naive approach sucks when the match fails in many
>   different ways, but it's quite efficient when the match succeeds
>   without any backtracking.
> Ideally, we'd like to replace the regexp engine with a "standard one",
> but it's not easy to find one that satisfies all the requirements
> (e.g. ability to add Emacs-specific elements like \_<, \s, and \c,
> ability to operate on "two-part strings" (i.e. with a gap in the
> middle), ...).

Thanks, that's pretty interesting.

The linked article sounded a bit like "only idiots implement regexen
in the naive way", and I was pretty sure Emacs devs are not idiots - but
now I understand the reasons better.

Best,

-- 
Marcin Borkowski
http://mbork.pl

Re: How are regexen implemented in Emacs?

[Stefan Monnier]

> The linked article sounded a bit like "only idiots implement regexen
> in the naive way", and I was pretty sure Emacs devs are not idiots - but
> now I understand the reasons better.

I fully agree that it doesn't make sense to *start* with
a backtracking implementation, yes.
But once you've invested in one, it's harder to move to
something better.

This said, it *would* be better.  Not only in terms of eliminating the
pathological blow ups, but it also offers opportunity to get new
functionality, such as the ability to capture the state of a regexp
match at a specific buffer position (so you can perform a multiline
regexp match one line at a time).  It could also make it much more
reasonable to add the possibility to run ELisp code from within the
regexp match engine (e.g. add a \p(NAME) entry which calls the NAME
ELisp function).


        Stefan

Re: How are regexen implemented in Emacs?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1576 bytes --]

On Mon, Dec 12, 2022 at 04:19:19PM -0500, Stefan Monnier wrote:
> > The linked article sounded a bit like "only idiots implement regexen
> > in the naive way", and I was pretty sure Emacs devs are not idiots - but
> > now I understand the reasons better.

There comes my favourite motto: "all generalizations suck" (Michael
Heerdegen enjoyed it a couple of threads back).

Whoever uses a library these days uses PCRE, and this is, AFAIK, a
DFA-with-backtracking thingy. Note that I haven't read the code,
so I might well be wrong.

> I fully agree that it doesn't make sense to *start* with
> a backtracking implementation, yes.
> But once you've invested in one, it's harder to move to
> something better.
> 
> This said, it *would* be better.  Not only in terms of eliminating the
> pathological blow ups, but it also offers opportunity to get new
> functionality, such as the ability to capture the state of a regexp
> match at a specific buffer position (so you can perform a multiline
> regexp match one line at a time).  It could also make it much more
> reasonable to add the possibility to run ELisp code from within the
> regexp match engine (e.g. add a \p(NAME) entry which calls the NAME
> ELisp function).

Perl does the latter. That has saved my bacon from time to time.
So that seems possible with a backtracker, too. Don't ask me how,
though :-)

Saving state at any point would be cool -- you could easily invert
control (feeding the regexp machine a spoonful at a time). Think
network or an abstract buffer.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor]

> Perl does the latter. That has saved my bacon from time to time.
> So that seems possible with a backtracker, too.  Don't ask me how,
> though :-)

Indeed, it's not more difficulty to allow to run ELisp/Perl
code in the middle of the backtracking match than a non-backtracking
one, but the difference is in the number of times the ELisp/Perl code
may need to be run, which changes the performance profile (and hence
the potential use-cases) significantly.


        Stefan


PS: Regarding non-backtracking matchers are backreferences, most of the
uses of backreferences I'm familiar with *can* be implemented without
backtracking because the subgroup to which the backref points has only
one possible way to match.  It won't handle cases like
`diff-merge-strings`, but it's still an important subset of cases.

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

tomas wrote:

> Whoever uses a library these days uses PCRE

PCRE = Perl Compatible Regular Expressions

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[Akib Azmain Turja]

[-- Attachment #1: Type: text/plain, Size: 479 bytes --]

Emanuel Berg <incal@dataswamp.org> writes:

> tomas wrote:
>
>> Whoever uses a library these days uses PCRE
>
> PCRE = Perl Compatible Regular Expressions

Then what's the name of the Emacs one?  I guess its...

EPGRES = Emacs's Pretty Good Regular Expression Syntax  ;-)

-- 
Akib Azmain Turja, GPG key: 70018CE5819F17A3BBA666AFE74F0EFA922AE7F5
Fediverse: akib@hostux.social
Codeberg: akib
emailselfdefense.fsf.org | "Nothing can be secure without encryption."

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

Akib Azmain Turja wrote:

>>> Whoever uses a library these days uses PCRE
>>
>> PCRE = Perl Compatible Regular Expressions
>
> Then what's the name of the Emacs one?  I guess its...
>
> EPGRES = Emacs's Pretty Good Regular Expression Syntax  ;-)

Makes sense, since I think the syntax is pretty good actually!

Check out line 313 in this file

  https://dataswamp.org/~incal/FILM

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[Jean Louis]

* Emanuel Berg <incal@dataswamp.org> [2022-12-17 12:57]:
> Check out line 313 in this file
> 
>   https://dataswamp.org/~incal/FILM

Nice way to provide the count. Just that it needs to be opened by one
of Emacs text browsers to evaluate `how-many' funtion, so that it
works. 

It would be good to have MIME type that is related to Emacs, so that
browsers recognize it and open Emacs with it. I have recommended that
EWW automatically open Org files by recognizing the MIME type. Then
you could place FILM.org or simply FILM, but which has Org MIME type,
and any other browser would open the file FILM and display it in Emacs
when configured so.

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

Jean Louis wrote:

>> Check out line 313 in this file
>> 
>>   https://dataswamp.org/~incal/FILM
>
> Nice way to provide the count. Just that it needs to be
> opened by one of Emacs text browsers to evaluate `how-many'
> funtion, so that it works.
>
> It would be good to have MIME type that is related to Emacs,
> so that browsers recognize it and open Emacs with it.

But actually it works in Emacs-w3m.

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 901 bytes --]

On Mon, Dec 12, 2022 at 08:09:42PM +0100, Marcin Borkowski wrote:
> 
> On 2022-12-12, at 19:16, Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org> wrote:
> 
> >> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
> >> and started to wonder if the hints there mean that Emacs has a "naive",
> >> backtracking regex engine or a FA-based one?
> >
> > Naive!
> 
> And what are the reasons?  Out of curiosity: would implementing
> a FA-based one be a very big undertaking?  (And no, I won't do it, if
> only because I don't know C.)

Nitpick: The Emacs regexp engine is a FA based one, but a DFA,
not a NFA (the famous Thompson NFA).

NFAs seem to be quite the beast, judging by how few implementations
are out there. I don't even know how easy it is to implement, e.g.
capture or (gasp!) back references,

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: How are regexen implemented in Emacs?

[Marcin Borkowski]

On 2022-12-12, at 21:01, tomas@tuxteam.de wrote:

> On Mon, Dec 12, 2022 at 08:09:42PM +0100, Marcin Borkowski wrote:
>>
>> On 2022-12-12, at 19:16, Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org> wrote:
>>
>> >> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
>> >> and started to wonder if the hints there mean that Emacs has a "naive",
>> >> backtracking regex engine or a FA-based one?
>> >
>> > Naive!
>>
>> And what are the reasons?  Out of curiosity: would implementing
>> a FA-based one be a very big undertaking?  (And no, I won't do it, if
>> only because I don't know C.)
>
> Nitpick: The Emacs regexp engine is a FA based one, but a DFA,
> not a NFA (the famous Thompson NFA).
>
> NFAs seem to be quite the beast, judging by how few implementations
> are out there. I don't even know how easy it is to implement, e.g.
> capture or (gasp!) back references,

Very interesting.  Re: back references, are even "regexen" with back
references still real regular expressions?

Best,

-- 
Marcin Borkowski
http://mbork.pl

Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor]

> Very interesting.  Re: back references, are even "regexen" with back
> references still real regular expressions?

No, back references aren't part of the "regular language" family.
They can't easily be accommodated by the usual DFA/NFA
non-backtracking matchers (and IIRC they are fundamentally
exponential-complexity in the worst case), tho some do handle them
(by falling back to a backtracking algorithm, AFAIK).


        Stefan

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

tomas wrote:

> Nitpick: The Emacs regexp engine is a FA based one, but
> a DFA, not a NFA (the famous Thompson NFA).

DFA = Deterministic finite automaton
NFA = Nondeterministic finite automaton

Finite - it's a state machine, finite means the number of
states are not infinite.

A set of rules crunches the input and determines transitions
from one state to another, I can imagine deterministic such
rules - but nondeterministic, what does that mean?

Maybe that from one state S and input I there are not one but
several ways to go, one can go to S' but also S'' and both
"moves" are legal?

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 813 bytes --]

On Thu, Dec 15, 2022 at 06:18:36AM +0100, Emanuel Berg wrote:

[...]

> A set of rules crunches the input and determines transitions
> from one state to another, I can imagine deterministic such
> rules - but nondeterministic, what does that mean?
> 
> Maybe that from one state S and input I there are not one but
> several ways to go, one can go to S' but also S'' and both
> "moves" are legal?

Exactly. The naive implementation of which involves keeping
a queue of possible states (breadth-first search).

Thompson's trick is converting the NFA into a DFA by considering
"sets of (possible) states" as your new states. But now you've
got 2^n states; the clever part is how to reduce that to some
manageable state space.

I think the Wikipedia has good articles on that.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor]

> Nitpick: The Emacs regexp engine is a FA based one, but a DFA,
> not a NFA (the famous Thompson NFA).

No, it's definitely not DFA because it uses a stack to implement
the backtracking.

It's usually considered to be an NFA that's processed via backtracking
rather than via "parallel execution" as "Thompson's NFA" does.
[ For Haskeller's out there, it's a bit like the difference between the
  Cont monad and the List monad with the added twist that "Thompson's
  NFA" replaces the List monad with a "Set monad", which is what changes
  its complexity.  ]

> NFAs seem to be quite the beast, judging by how few implementations
> are out there. I don't even know how easy it is to implement, e.g.
> capture or (gasp!) back references,

It's not hard to implement, no.
At least not until you consider things like *? and backreferences.


        Stefan

Re: How are regexen implemented in Emacs?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1267 bytes --]

On Thu, Dec 15, 2022 at 11:46:13AM -0500, Stefan Monnier via Users list for the GNU Emacs text editor wrote:
> > Nitpick: The Emacs regexp engine is a FA based one, but a DFA,
> > not a NFA (the famous Thompson NFA).
> 
> No, it's definitely not DFA because it uses a stack to implement
> the backtracking.
> 
> It's usually considered to be an NFA that's processed via backtracking
> rather than via "parallel execution" as "Thompson's NFA" does.

I stand corrected. Thanks.

> [ For Haskeller's out there, it's a bit like the difference between the
>   Cont monad and the List monad with the added twist that "Thompson's
>   NFA" replaces the List monad with a "Set monad", which is what changes
>   its complexity.  ]

Shudder :-)

> > NFAs seem to be quite the beast, judging by how few implementations
> > are out there. I don't even know how easy it is to implement, e.g.
> > capture or (gasp!) back references,
> 
> It's not hard to implement, no.
> At least not until you consider things like *? and backreferences.

Interestingly, Tcl seems to "do" Thompson (the article mentioned
upthread has Tcl as one of the examples, AFAIR), and they do back
references and non-greedy repetitions. There seems to be a way.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

tomas wrote:

> Interestingly, Tcl seems to "do" Thompson

Tcl 1988 ("tickle") interpreted, compact programming language

https://en.wikipedia.org/wiki/Tcl

https://dataswamp.org/~incal/COMP-HIST 223 entries

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

Marcin Borkowski wrote:

>> Naive!
>
> And what are the reasons? Out of curiosity: would
> implementing a FA-based one be a very big undertaking? (And
> no, I won't do it, if only because I don't know C.)

C is not so difficult, but probably someone else did it
already so it would be a matter of integrating and reusing
that rather than writing it all over from scratch interesting
as that may sound ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: How are regexen implemented in Emacs?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1035 bytes --]

On Thu, Dec 15, 2022 at 04:45:05AM +0100, Emanuel Berg wrote:
> Marcin Borkowski wrote:
> 
> >> Naive!
> >
> > And what are the reasons? Out of curiosity: would
> > implementing a FA-based one be a very big undertaking? (And
> > no, I won't do it, if only because I don't know C.)
> 
> C is not so difficult, but probably someone else did it
> already so it would be a matter of integrating and reusing
> that rather than writing it all over from scratch interesting
> as that may sound ...

The devil is in the details: each long-living RE implementation
develops its own useful warts, and they are all different. Stefan
already hinted at it, but you can't underestimate the weight of
(a) Emacs's existing corpus of code hidden away in REs and (b)
the one hidden away in its diverse user base's brains and
muscle memories.

So you better come up with some fully backward compatible thing,
whatever the implementation. I think the easiest would be to
substitute one little piece at a time :-)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: How are regexen implemented in Emacs?

[Emanuel Berg]

Marcin Borkowski wrote:

> I looked at [...] and started to wonder if the hints there
> mean that Emacs has a "naive", backtracking regex engine or
> a FA-based one?

FA = Finite Automaton, buzzword from Computer Science
Automata theory ...

https://en.wikipedia.org/wiki/Automata_theory

-- 
underground experts united
https://dataswamp.org/~incal