Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Stefan Monnier]

>     (unfreeze_pattern, freeze_pattern): New functions.
>     (compile_pattern): Return a regexp_cache pointer instead of the
>     re_pattern_buffer, allowing callers to use `freeze_pattern' if
>     needed.  Do not consider busy patterns as cache hit candidates;
>     error if we run out of non-busy cache entries.

IIRC the main/only reason why you can't use a compiled pattern in
a reentrant way is because the \{N,M\} repetitions use a counter that's
stored directly within the compiled pattern.

But these are fairly rare.

So we could easily change the code to add a boolean stating whether there
is such a repetition-counter in the pattern, and if there isn't then
"freeze" can just do nothing because we can freely use that pattern
multiple times at the same time.


        Stefan

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

>>     (unfreeze_pattern, freeze_pattern): New functions.
>>     (compile_pattern): Return a regexp_cache pointer instead of the
>>     re_pattern_buffer, allowing callers to use `freeze_pattern' if
>>     needed.  Do not consider busy patterns as cache hit candidates;
>>     error if we run out of non-busy cache entries.
>
> IIRC the main/only reason why you can't use a compiled pattern in
> a reentrant way is because the \{N,M\} repetitions use a counter that's
> stored directly within the compiled pattern.
>
> But these are fairly rare.
>
> So we could easily change the code to add a boolean stating whether there
> is such a repetition-counter in the pattern, and if there isn't then
> "freeze" can just do nothing because we can freely use that pattern
> multiple times at the same time.

Good idea. My reading of the "smart jump" stuff in regex.c suggested that
we use the optimization for _all_ greedy Kleene star constructs though,
not just the bounded ones. Am I wrong?

But anyway, I think the regex code needs a major overhaul.  I was actually
thinking about forking and vendoring RE2. Granted, having done that, you'd
need a C++ compiler to build Emacs, but it's probably one of the better
actively-maintained DFA-based regex engines around.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

>>>     (unfreeze_pattern, freeze_pattern): New functions.
>>>     (compile_pattern): Return a regexp_cache pointer instead of the
>>>     re_pattern_buffer, allowing callers to use `freeze_pattern' if
>>>     needed.  Do not consider busy patterns as cache hit candidates;
>>>     error if we run out of non-busy cache entries.
>>
>> IIRC the main/only reason why you can't use a compiled pattern in
>> a reentrant way is because the \{N,M\} repetitions use a counter that's
>> stored directly within the compiled pattern.
>>
>> But these are fairly rare.
>>
>> So we could easily change the code to add a boolean stating whether
>> there
>> is such a repetition-counter in the pattern, and if there isn't then
>> "freeze" can just do nothing because we can freely use that pattern
>> multiple times at the same time.
>
> Good idea. My reading of the "smart jump" stuff in regex.c suggested that
> we use the optimization for _all_ greedy Kleene star constructs though,
> not just the bounded ones. Am I wrong?

Oh, yeah. One more thing. The busy flag isn't *just* to prevent the regex
bytecode engine confusing itself with self-modifying bytecode. It also
serves to protect the cache slot holding the regex pattern from reuse,
which would be disastrous whether or not the bytecode of a particular
pattern happens to be mutable. Under your proposal, we can get cache hits
on busy patterns, but we still have to mark them busy in the first place
so we can prevent this reuse.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Stefan Monnier]

> Oh, yeah. One more thing. The busy flag isn't *just* to prevent the regex
> bytecode engine confusing itself with self-modifying bytecode. It also
> serves to protect the cache slot holding the regex pattern from reuse,
> which would be disastrous whether or not the bytecode of a particular
> pattern happens to be mutable.

It doesn't have to be disastrous *if* we complexify the code such that
removing a pattern from the cache doesn't inevitably free that pattern ;-)
[ But, yes, we'd still need to mark the pattern as "busy" in order to
  know when it can be freed.  ]


        Stefan

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

>> Oh, yeah. One more thing. The busy flag isn't *just* to prevent the
>> regex
>> bytecode engine confusing itself with self-modifying bytecode. It also
>> serves to protect the cache slot holding the regex pattern from reuse,
>> which would be disastrous whether or not the bytecode of a particular
>> pattern happens to be mutable.
>
> It doesn't have to be disastrous *if* we complexify the code such that
> removing a pattern from the cache doesn't inevitably free that pattern ;-)
> [ But, yes, we'd still need to mark the pattern as "busy" in order to
>   know when it can be freed.  ]

Sure. And at that point, we might as well make compiled patterns into
GC-able heap objects. That's probably a good idea, but it's a bigger
project.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Stefan Monnier]

> Good idea. My reading of the "smart jump" stuff in regex.c suggested that
> we use the optimization for _all_ greedy Kleene star constructs though,
> not just the bounded ones. Am I wrong?

Oh, right, I forgot about that lazy optimization.  We'd need to fix this
so the optimization is performed eagerly.

> But anyway, I think the regex code needs a major overhaul.

Yes, but it's a fairly major project.

> I was actually thinking about forking and vendoring RE2.  Granted,
> having done that, you'd need a C++ compiler to build Emacs, but it's
> probably one of the better actively-maintained DFA-based regex
> engines around.

Yes, it's a nice library, but we'd need to add support for
back-references, which doesn't seem straightforward (I think the
easiest would be to fallback on the old regex engine when backrefs are
present, but keeping two completely different regexp engines is a real
PITA).


        Stefan

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Sun, 17 Jun 2018 11:51:33 -0700 "Daniel Colascione"
<dancol@dancol.org> wrote:
> But anyway, I think the regex code needs a major overhaul.  I was
> actually thinking about forking and vendoring RE2. Granted, having
> done that, you'd need a C++ compiler to build Emacs, but it's
> probably one of the better actively-maintained DFA-based regex
> engines around.

I think needing C++ makes this less than the most obvious choice.

I think the right thing would be to use TRE if we could get Ville
Laurikari to let someone else be the maintainer. Sadly right now it
seems unmaintained and has been for years, but it's fast, complete,
and has the ability to handle things like gap buffers.

This would also give Emacs access to an approximate match facility,
which would be a very neat thing. I often would like to do
approximate searches, and there's no way to do that right now. TRE
would let us do it.

But again, that would be contingent on someone else taking over
maintenance and fixing the backlog of issues it has right now.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

> On Sun, 17 Jun 2018 11:51:33 -0700 "Daniel Colascione"
> <dancol@dancol.org> wrote:
>> But anyway, I think the regex code needs a major overhaul.  I was
>> actually thinking about forking and vendoring RE2. Granted, having
>> done that, you'd need a C++ compiler to build Emacs, but it's
>> probably one of the better actively-maintained DFA-based regex
>> engines around.
>
> I think needing C++ makes this less than the most obvious choice.

Why? C++ is everywhere these days. I'm in no hurry to move the Emacs core
to C++, but requiring a C++ compiler for the sake of some dependency
shouldn't be a problem. It's good enough for GDB.

>
> I think the right thing would be to use TRE if we could get Ville
> Laurikari to let someone else be the maintainer. Sadly right now it
> seems unmaintained and has been for years, but it's fast, complete,
> and has the ability to handle things like gap buffers.

Last time I looked, many years ago, there were several bugs (or
differences between TRE and POSIX anyway)

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Mon, 18 Jun 2018 10:49:46 -0700 "Daniel Colascione"
<dancol@dancol.org> wrote:
> > I think the right thing would be to use TRE if we could get Ville
> > Laurikari to let someone else be the maintainer. Sadly right now
> > it seems unmaintained and has been for years, but it's fast,
> > complete, and has the ability to handle things like gap buffers.  
> 
> Last time I looked, many years ago, there were several bugs (or
> differences between TRE and POSIX anyway)

Bugs yes, but the POSIX conformance was pretty strict. As I said, he
seemed to have abandoned the thing, but the bones are pretty good.
Someone could just fork it and implement all the patches people have
been contributing that have been languishing in the github issue
trackers.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 09:40:05 -0400 "Perry E. Metzger"
<perry@piermont.com> wrote:
> On Mon, 18 Jun 2018 10:49:46 -0700 "Daniel Colascione"
> <dancol@dancol.org> wrote:
> > > I think the right thing would be to use TRE if we could get
> > > Ville Laurikari to let someone else be the maintainer. Sadly
> > > right now it seems unmaintained and has been for years, but
> > > it's fast, complete, and has the ability to handle things like
> > > gap buffers.    
> > 
> > Last time I looked, many years ago, there were several bugs (or
> > differences between TRE and POSIX anyway)  
> 
> Bugs yes, but the POSIX conformance was pretty strict. As I said, he
> seemed to have abandoned the thing, but the bones are pretty good.
> Someone could just fork it and implement all the patches people have
> been contributing that have been languishing in the github issue
> trackers.

Oh, and re2 isn't built for POSIX compliance. It has no constructs
that require backtracking etc.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

On 06/19/2018 06:44 AM, Perry E. Metzger wrote:
> On Tue, 19 Jun 2018 09:40:05 -0400 "Perry E. Metzger"
> <perry@piermont.com> wrote:
>> On Mon, 18 Jun 2018 10:49:46 -0700 "Daniel Colascione"
>> <dancol@dancol.org> wrote:
>>>> I think the right thing would be to use TRE if we could get
>>>> Ville Laurikari to let someone else be the maintainer. Sadly
>>>> right now it seems unmaintained and has been for years, but
>>>> it's fast, complete, and has the ability to handle things like
>>>> gap buffers.
>>>
>>> Last time I looked, many years ago, there were several bugs (or
>>> differences between TRE and POSIX anyway)
>>
>> Bugs yes, but the POSIX conformance was pretty strict. As I said, he
>> seemed to have abandoned the thing, but the bones are pretty good.
>> Someone could just fork it and implement all the patches people have
>> been contributing that have been languishing in the github issue
>> trackers.
> 
> Oh, and re2 isn't built for POSIX compliance. It has no constructs
> that require backtracking etc.

No DFA engine can do backtracking.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 06:49:03 -0700 Daniel Colascione
<dancol@dancol.org> wrote:
> On 06/19/2018 06:44 AM, Perry E. Metzger wrote:
> > On Tue, 19 Jun 2018 09:40:05 -0400 "Perry E. Metzger"
> > <perry@piermont.com> wrote:  
> >> On Mon, 18 Jun 2018 10:49:46 -0700 "Daniel Colascione"
> >> <dancol@dancol.org> wrote:  
> >>>> I think the right thing would be to use TRE if we could get
> >>>> Ville Laurikari to let someone else be the maintainer. Sadly
> >>>> right now it seems unmaintained and has been for years, but
> >>>> it's fast, complete, and has the ability to handle things like
> >>>> gap buffers.  
> >>>
> >>> Last time I looked, many years ago, there were several bugs (or
> >>> differences between TRE and POSIX anyway)  
> >>
> >> Bugs yes, but the POSIX conformance was pretty strict. As I
> >> said, he seemed to have abandoned the thing, but the bones are
> >> pretty good. Someone could just fork it and implement all the
> >> patches people have been contributing that have been languishing
> >> in the github issue trackers.  
> > 
> > Oh, and re2 isn't built for POSIX compliance. It has no constructs
> > that require backtracking etc.  
> 
> No DFA engine can do backtracking.

Correct, but there are regexp libraries that will switch between DFA
and non-DFA implementations depending on whether the regexp has
constructs in it that require backtracking.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 10:30:02 -0400 "Perry E. Metzger"
<perry@piermont.com> wrote:
> > > Oh, and re2 isn't built for POSIX compliance. It has no
> > > constructs that require backtracking etc.    
> > 
> > No DFA engine can do backtracking.  
> 
> Correct, but there are regexp libraries that will switch between DFA
> and non-DFA implementations depending on whether the regexp has
> constructs in it that require backtracking.

Just to be explicit: TRE does this, IIRC. It certainly implements
backreferences, which re2 does not. (And, it has provisions in its
API for handling things like gap buffers. The main problem is it is
unmaintained.)

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

On 06/19/2018 07:33 AM, Perry E. Metzger wrote:
> On Tue, 19 Jun 2018 10:30:02 -0400 "Perry E. Metzger"
> <perry@piermont.com> wrote:
>>>> Oh, and re2 isn't built for POSIX compliance. It has no
>>>> constructs that require backtracking etc.
>>>
>>> No DFA engine can do backtracking.
>>
>> Correct, but there are regexp libraries that will switch between DFA
>> and non-DFA implementations depending on whether the regexp has
>> constructs in it that require backtracking.
> 
> Just to be explicit: TRE does this, IIRC. It certainly implements
> backreferences, which re2 does not. (And, it has provisions in its
> API for handling things like gap buffers. The main problem is it is
> unmaintained.)

If we did want to adopt TRE, we'd have to add supports for PCRE-like 
callouts for implementing Emacs-specific assertions. (PCRE itself has 
the opposite problem: explicit support for pluggable callouts, but no 
support for an iterator API.)

I'd also like to better understand the specific remaining differences 
between POSIX regular expression semantics and what TRE implements, 
whether this difference is intentional or not. And I'd also like to 
understand how we can give the engine Emacs-regex semantics instead of 
POSIX ones. (Very few people use the POSIX mode of Emacs regex matching.)

I'm also not sure how copyright assignment would work for abandonware.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 07:48:28 -0700 Daniel Colascione
<dancol@dancol.org> wrote:
> If we did want to adopt TRE, we'd have to add supports for
> PCRE-like callouts for implementing Emacs-specific assertions.
> (PCRE itself has the opposite problem: explicit support for
> pluggable callouts, but no support for an iterator API.)

Probably.

> I'd also like to better understand the specific remaining
> differences between POSIX regular expression semantics and what TRE
> implements, whether this difference is intentional or not.

The documentation is, I think, pretty good on this.

> And I'd also like to understand how we can give the engine
> Emacs-regex semantics instead of POSIX ones. (Very few people use
> the POSIX mode of Emacs regex matching.)
>
> I'm also not sure how copyright assignment would work for
> abandonware.

I don't think we could get a copyright assignment. It would have to be
maintained as a separate package that Emacs depended on.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Paul Eggert]

If we're going to go to that much work, why not use glibc regex? It uses a DFA 
and falls back on backtracking only when needed. Although glibc regex isn't 
maintained that well, it's at least maintained, which TRE is not. And it does 
have some advantages: it has an API that is like Emacs src/regex.c, and it won't 
have any licensing issues. Its main disadvantage (it doesn't support split 
buffers) could be overcome fairly easily, either by adding support for that back 
into the library, or arranging for a single array whenever the regex matcher is 
called.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 09:20:43 -0700 Paul Eggert <eggert@cs.ucla.edu>
wrote:
> If we're going to go to that much work, why not use glibc regex? It
> uses a DFA and falls back on backtracking only when needed.
> Although glibc regex isn't maintained that well, it's at least
> maintained, which TRE is not. And it does have some advantages: it
> has an API that is like Emacs src/regex.c, and it won't have any
> licensing issues. Its main disadvantage (it doesn't support split
> buffers) could be overcome fairly easily, either by adding support
> for that back into the library, or arranging for a single array
> whenever the regex matcher is called.

That's also an option. I really like the idea of being able to do
approximate searches in files, but it's not that big a deal. (Does
the glibc stuff have appropriate unicode support etc?)

Truthfully, my biggest interest is in seeing the default regex syntax
migrate to something much more modern, and that can be done
regardless of which engine we use.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Stefan Monnier]

> Truthfully, my biggest interest is in seeing the default regex syntax
> migrate to something much more modern, and that can be done
> regardless of which engine we use.

Not only that: changing the engine won't help in changing the syntax.


        Stefan

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

>> Truthfully, my biggest interest is in seeing the default regex syntax
>> migrate to something much more modern, and that can be done
>> regardless of which engine we use.
>
> Not only that: changing the engine won't help in changing the syntax.

Right. Anyone is free to experiment with changing read-regexp today. I
think a combination of rx input with paredit* for easier editing might
work pretty well, maybe with a mode key to distinguish input modalities.

(Which gets me into more about how isearch should have multiple orthogonal
modes sharing history, not a hard distinction between the literal and
regexp cases.)

* or whatever structured editing package people use today

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 13:46:20 -0400 Stefan Monnier
<monnier@IRO.UMontreal.CA> wrote:
> > Truthfully, my biggest interest is in seeing the default regex
> > syntax migrate to something much more modern, and that can be done
> > regardless of which engine we use.  
> 
> Not only that: changing the engine won't help in changing the
> syntax.

Precisely. So to some extent I'm less interested in the engine than I
might appear to be.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[John Wiegley]

>>>>> "PE" == Paul Eggert <eggert@cs.ucla.edu> writes:

PE> If we're going to go to that much work, why not use glibc regex? It uses a
PE> DFA and falls back on backtracking only when needed. Although glibc regex
PE> isn't maintained that well, it's at least maintained, which TRE is not.
PE> And it does have some advantages: it has an API that is like Emacs
PE> src/regex.c, and it won't have any licensing issues. Its main disadvantage
PE> (it doesn't support split buffers) could be overcome fairly easily, either
PE> by adding support for that back into the library, or arranging for a
PE> single array whenever the regex matcher is called.

If we do find a problem with it, how long will it take before the fix we need
is propagated everywhere it needs to go?

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 09:54:50 -0700 "John Wiegley" <johnw@gnu.org>
wrote:
> >>>>> "PE" == Paul Eggert <eggert@cs.ucla.edu> writes:  
> 
> PE> If we're going to go to that much work, why not use glibc
> PE> regex? It uses a DFA and falls back on backtracking only when
> PE> needed. Although glibc regex isn't maintained that well, it's
> PE> at least maintained, which TRE is not. And it does have some
> PE> advantages: it has an API that is like Emacs src/regex.c, and
> PE> it won't have any licensing issues. Its main disadvantage (it
> PE> doesn't support split buffers) could be overcome fairly easily,
> PE> either by adding support for that back into the library, or
> PE> arranging for a single array whenever the regex matcher is
> PE> called.  
> 
> If we do find a problem with it, how long will it take before the
> fix we need is propagated everywhere it needs to go?

Which package was the referent for "it"?

-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[John Wiegley]

>>>>> Perry E Metzger <perry@piermont.com> writes:

> Which package was the referent for "it"?

glibc regex

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Paul Eggert]

On 06/19/2018 09:54 AM, John Wiegley wrote:
> If we do find a problem with it, how long will it take before the fix we need
> is propagated everywhere it needs to go?

It shouldn't take much time at all to propagate Emacs-related regex 
changes back to Gnulib, which is commonly used by GNU applications like 
'grep' so that they can assume the same regex API everywhere. It would 
take more time to propagate the changes back into Glibc, but the 
distance between Gnulib regex and Glibc regex is relatively small (it's 
way less than the distance between Emacs regex and Glibc regex) and it's 
feasible to do that propagation (mostly, this means to jump the Glibc 
bureaucratic hurdles).

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

> On 06/19/2018 09:54 AM, John Wiegley wrote:
>> If we do find a problem with it, how long will it take before the fix we
>> need
>> is propagated everywhere it needs to go?
>
> It shouldn't take much time at all to propagate Emacs-related regex
> changes back to Gnulib, which is commonly used by GNU applications like
> 'grep' so that they can assume the same regex API everywhere. It would
> take more time to propagate the changes back into Glibc, but the
> distance between Gnulib regex and Glibc regex is relatively small (it's
> way less than the distance between Emacs regex and Glibc regex) and it's
> feasible to do that propagation (mostly, this means to jump the Glibc
> bureaucratic hurdles).
>

Do you think the glib regex maintainers would be amenable to adding 1)
external iterator support (that we'd use to deal with the gap), and 2)
user-pluggable callouts (which we'd use to implement Emacs-specific
assertions)? I'd rather not have a huge pile of ifdefs the way we do now.
I'd much prefer using maintained extension points.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Paul Eggert]

On 06/19/2018 11:16 AM, Daniel Colascione wrote:
> Do you think the glib regex maintainers would be amenable to adding 1)
> external iterator support (that we'd use to deal with the gap), and 2)
> user-pluggable callouts (which we'd use to implement Emacs-specific
> assertions)? I'd rather not have a huge pile of ifdefs the way we do now.
> I'd much prefer using maintained extension points.

We could add those to Gnulib. I think we could also add them to Glibc 
eventually, though that would require more consensus. The main question 
to my mind is whether we'd want the extension points to be visible to 
Glibc users. If not, most likely we'd need some ifdefs, though I expect 
we wouldn't need a huge pile of them (as glibc code can assume GCC 
optimization).

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Andreas Schwab]

On Jun 19 2018, Paul Eggert <eggert@cs.ucla.edu> wrote:

> If we're going to go to that much work, why not use glibc regex?

It doesn't support a gap either.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Paul Eggert]

On 06/19/2018 11:03 AM, Andreas Schwab wrote:
>> If we're going to go to that much work, why not use glibc regex?
> It doesn't support a gap either.

Yes, and I noted that in my email (I called it "split buffers").

Actually, Gnulib/Glibc regex does support a gap; it's just that it's 
implemented inefficiently, and for Emacs we'd want it to be more 
efficient if we were to use it.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Daniel Colascione]

On 06/19/2018 07:30 AM, Perry E. Metzger wrote:
> On Tue, 19 Jun 2018 06:49:03 -0700 Daniel Colascione
> <dancol@dancol.org> wrote:
>> On 06/19/2018 06:44 AM, Perry E. Metzger wrote:
>>> On Tue, 19 Jun 2018 09:40:05 -0400 "Perry E. Metzger"
>>> <perry@piermont.com> wrote:
>>>> On Mon, 18 Jun 2018 10:49:46 -0700 "Daniel Colascione"
>>>> <dancol@dancol.org> wrote:
>>>>>> I think the right thing would be to use TRE if we could get
>>>>>> Ville Laurikari to let someone else be the maintainer. Sadly
>>>>>> right now it seems unmaintained and has been for years, but
>>>>>> it's fast, complete, and has the ability to handle things like
>>>>>> gap buffers.
>>>>>
>>>>> Last time I looked, many years ago, there were several bugs (or
>>>>> differences between TRE and POSIX anyway)
>>>>
>>>> Bugs yes, but the POSIX conformance was pretty strict. As I
>>>> said, he seemed to have abandoned the thing, but the bones are
>>>> pretty good. Someone could just fork it and implement all the
>>>> patches people have been contributing that have been languishing
>>>> in the github issue trackers.
>>>
>>> Oh, and re2 isn't built for POSIX compliance. It has no constructs
>>> that require backtracking etc.
>>
>> No DFA engine can do backtracking.
> 
> Correct, but there are regexp libraries that will switch between DFA
> and non-DFA implementations depending on whether the regexp has
> constructs in it that require backtracking

Sure, but the DFA and non-DFA engines can vary independently so long as 
they understand the same language, modulo backreference support.

IMHO, back reference support is an old unix mistake. I can't think of a 
time when I've wanted to actually use them, but their theoretical use is 
still a hindrance. One option would be to just deprecate them.

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Andreas Schwab]

On Jun 19 2018, Daniel Colascione <dancol@dancol.org> wrote:

> IMHO, back reference support is an old unix mistake. I can't think of a
> time when I've wanted to actually use them, but their theoretical use is
> still a hindrance. One option would be to just deprecate them.

There are quite a few uses in Emacs.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 16:58:15 +0200 Andreas Schwab <schwab@suse.de>
wrote:
> On Jun 19 2018, Daniel Colascione <dancol@dancol.org> wrote:
> 
> > IMHO, back reference support is an old unix mistake. I can't
> > think of a time when I've wanted to actually use them, but their
> > theoretical use is still a hindrance. One option would be to just
> > deprecate them.  
> 
> There are quite a few uses in Emacs.

I agree that they're a mistake, but we're a bit stuck. The right
thing, I think, is using a library like TRE that uses a fast
algorithm whenever a backreference isn't in use.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

What is TRE?

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Mon, 18 Jun 2018 19:25:04 -0400 Richard Stallman <rms@gnu.org>
wrote:
> What is TRE?

It's a fairly nice regular expression engine, with excellent
performance and the unique feature of doing approximate matching.

https://laurikari.net/tre/about/

code is at

https://github.com/laurikari/tre/

The unfortunate bit is that the author seems to have abandoned it a
few years ago.

Perry
-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > It's a fairly nice regular expression engine, with excellent
  > performance and the unique feature of doing approximate matching.

Sounds interesting.  I am sure we can modify the code to suit our
needs, if we want to do that.  What is its licensing?
-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Perry E. Metzger]

On Tue, 19 Jun 2018 18:54:37 -0400 Richard Stallman <rms@gnu.org>
wrote:
> [[[ To any NSA and FBI agents reading my email: please
> consider    ]]] [[[ whether defending the US Constitution against
> all enemies,     ]]] [[[ foreign or domestic, requires you to
> follow Snowden's example. ]]]
> 
>   > It's a fairly nice regular expression engine, with excellent
>   > performance and the unique feature of doing approximate
>   > matching.  
> 
> Sounds interesting.  I am sure we can modify the code to suit our
> needs, if we want to do that.  What is its licensing?

Two-clause BSD.
https://github.com/laurikari/tre/blob/master/LICENSE

-- 
Perry E. Metzger		perry@piermont.com

Re: [Emacs-diffs] master 938d252 4/4: Make regex matching reentrant; update syntax during match

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > Two-clause BSD.
  > https://github.com/laurikari/tre/blob/master/LICENSE

Not the best choice, but it is not an obstacle to our using it.
If we make large changes we should copyleft the result.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)