Ancient Regex Regression

[p5pRT]

Migrated from rt.perl.org#133352 (status was 'open')

Searchable as RT133352$

[p5pRT]

From @deven

Created by @deven

I discovered a bug in Perl's regular expression engine a few
months ago. I showed it to many people at The Perl Conference
in Salt Lake City a couple weeks ago, and everyone agreed that
this was a bug in the regex engine in Perl itself, including
Abigail, Tom Christiansen, Karl Williamson and Larry Wall.

I even ended up doing a lightning talk about the bug​:

  https://www.youtube.com/watch?v=U-JhPIECkPY

This was my test case, which works with or without anchors​:

  "afoobar" =~ /((.)foo|bar)*/
  "afoobar" =~ /^((.)foo|bar)*$/

Or, as a standalone command​:

  perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

This prints "b", even though "bfoo" never appears in "afoobar"!

I understand why this is happening -- the inner group does match
against "b" in "bar" on the second iteration, but this branch of
the alternation fails. The capture is still being used, despite
the fact that it came from a failed branch of the alternation.

The correct answer seems to be "a", since that's the last match
of the inner group and the overall match is successful. Perl 1.0
can't handle this regex (Larry said it was the regex engine from
Gosling Emacs), but Perl 2.0 through Perl 5.0 alpha 9 all print
"a" for the command above. Other regex implementations, such as
PCRE, RE2, GNU and others, also return "a" for the inner group.

Perl 5.000 (from 1994) is the first commit in the git repository
(commit a0d0e21) which exhibits
the bug, printing "b" instead of "a". I just built blead again
today and confirmed that the bug is still there, despite passing
the full test suite. (Tom Christiansen pointed out that this bug
is technically a regression, since it used to work correctly.)

Even though I have never worked on the Perl core, and I've been
warned that the regex engine is particularly difficult, I would
still like to attempt to develop a patch for this bug myself.

I've already managed to create a working patch that fixes this
bug without breaking any of the regular expression tests in the
test suite, so I think I'm on the right track, but I think there
may be a few edge cases to consider, so I'm not ready to submit
the patch just yet.

Yves, SawyerX thought you might be willing to mentor me on this?
If so, that would be great!

My solution involves saving the captures with regcppush() on
BRANCH and TRIE nodes and restoring them with regcp_restore() at
BRANCH_next_fail and TRIE_next_fail. Does that sound like the
right approach, give or take?

Perl Info

Flags:
    category=core
    severity=low

Site configuration information for perl 5.29.1:

Configured by deven at Sat Jul  7 22:07:54 EDT 2018.

Summary of my perl5 (revision 5 version 29 subversion 1) configuration:
  Commit id: 71525f77826ad33944c007b06b68a1f14a085e7a
  Platform:
    osname=linux
    osvers=3.19.8-100.fc20.x86_64
    archname=x86_64-linux-thread-multi
    uname='linux twist.ties.org 3.19.8-100.fc20.x86_64 #1 smp tue may 12
17:08:50 utc 2015 x86_64 x86_64 x86_64 gnulinux '
    config_args=''
    hint=previous
    useposix=true
    d_sigaction=define
    useithreads=define
    usemultiplicity=define
    use64bitint=define
    use64bitall=define
    uselongdouble=undef
    usemymalloc=n
    default_inc_excludes_dot=define
    bincompat5005=undef
  Compiler:
    cc='gcc'
    ccflags ='-DDEBUGGING -D_REENTRANT -D_GNU_SOURCE -fwrapv
-fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include
-D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64'
    optimize='-g'
    cppflags='-DDEBUGGING -D_REENTRANT -D_GNU_SOURCE -fwrapv
-fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
    ccversion=''
    gccversion='4.8.3 20140911 (Red Hat 4.8.3-7)'
    gccosandvers=''
    intsize=4
    longsize=8
    ptrsize=8
    doublesize=8
    byteorder=12345678
    doublekind=3
    d_longlong=define
    longlongsize=8
    d_longdbl=define
    longdblsize=16
    longdblkind=3
    ivtype='long'
    ivsize=8
    nvtype='double'
    nvsize=8
    Off_t='off_t'
    lseeksize=8
    alignbytes=8
    prototype=define
  Linker and Libraries:
    ld='gcc'
    ldflags =' -fstack-protector-strong -L/usr/local/lib'
    libpth=/usr/local/lib /usr/lib /lib/../lib64 /usr/lib/../lib64 /lib
/lib64 /usr/lib64 /usr/local/lib64 /usr/local/lib /usr/lib
    libs=-lpthread -lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc
-lgdbm_compat
    perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
    libc=libc-2.18.so
    so=so
    useshrplib=false
    libperl=libperl.a
    gnulibc_version='2.18'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs
    dlext=so
    d_dlsymun=undef
    ccdlflags='-Wl,-E'
    cccdlflags='-fPIC'
    lddlflags='-shared -g -L/usr/local/lib -fstack-protector-strong'



@INC for perl 5.29.1:
    lib
    /usr/local/lib/perl5/site_perl/5.29.1/x86_64-linux-thread-multi
    /usr/local/lib/perl5/site_perl/5.29.1
    /usr/local/lib/perl5/5.29.1/x86_64-linux-thread-multi
    /usr/local/lib/perl5/5.29.1


Environment for perl 5.29.1:
    HOME=/home/deven
    LANG=en_US.UTF-8
    LANGUAGE (unset)
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)

PATH=/home/deven/bin:/home/deven/scripts:/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:/etc:/sbin:/home/deven/bin
    PERL_BADLANG (unset)
    SHELL=/bin/bash

[p5pRT]

From @jkeenan

On Mon, 09 Jul 2018 04​:04​:32 GMT, dcorzine wrote​:

This is a bug report for perl from deven@​ties.org,
generated with the help of perlbug 1.41 running under perl 5.29.1.

-----------------------------------------------------------------
[Please describe your issue here]

I discovered a bug in Perl's regular expression engine a few
months ago. I showed it to many people at The Perl Conference
in Salt Lake City a couple weeks ago, and everyone agreed that
this was a bug in the regex engine in Perl itself, including
Abigail, Tom Christiansen, Karl Williamson and Larry Wall.

I even ended up doing a lightning talk about the bug​:

https://www.youtube.com/watch?v=U-JhPIECkPY

This was my test case, which works with or without anchors​:

"afoobar" =~ /((.)foo|bar)*/
"afoobar" =~ /^((.)foo|bar)*$/

Or, as a standalone command​:

perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

This prints "b", even though "bfoo" never appears in "afoobar"!

I understand why this is happening -- the inner group does match
against "b" in "bar" on the second iteration, but this branch of
the alternation fails. The capture is still being used, despite
the fact that it came from a failed branch of the alternation.

The correct answer seems to be "a", since that's the last match
of the inner group and the overall match is successful. Perl 1.0
can't handle this regex (Larry said it was the regex engine from
Gosling Emacs), but Perl 2.0 through Perl 5.0 alpha 9 all print
"a" for the command above. Other regex implementations, such as
PCRE, RE2, GNU and others, also return "a" for the inner group.

Perl 5.000 (from 1994) is the first commit in the git repository
(commit a0d0e21) which exhibits
the bug, printing "b" instead of "a". I just built blead again
today and confirmed that the bug is still there, despite passing
the full test suite. (Tom Christiansen pointed out that this bug
is technically a regression, since it used to work correctly.)

Even though I have never worked on the Perl core, and I've been
warned that the regex engine is particularly difficult, I would
still like to attempt to develop a patch for this bug myself.

I've already managed to create a working patch that fixes this
bug without breaking any of the regular expression tests in the
test suite, so I think I'm on the right track, but I think there
may be a few edge cases to consider, so I'm not ready to submit
the patch just yet.

Please submit the patch as an attachment. Even if it's not complete, it gives us something to run through the test suite and a starting point for discussion.

Yves, SawyerX thought you might be willing to mentor me on this?
If so, that would be great!

My solution involves saving the captures with regcppush() on
BRANCH and TRIE nodes and restoring them with regcp_restore() at
BRANCH_next_fail and TRIE_next_fail. Does that sound like the
right approach, give or take?

Thank you very much.

--
James E Keenan (jkeenan@​cpan.org)

[p5pRT]

The RT System itself - Status changed from 'new' to 'open'

[p5pRT]

From @deven

On Tue, Jul 10, 2018 at 1​:09 PM, James E Keenan via RT <
perlbug-followup@​perl.org> wrote​:

On Mon, 09 Jul 2018 04​:04​:32 GMT, dcorzine wrote​:

This is a bug report for perl from deven@​ties.org,
generated with the help of perlbug 1.41 running under perl 5.29.1.

[...]

Please submit the patch as an attachment. Even if it's not complete, it
gives us something to run through the test suite and a starting point for
discussion.

Fair enough. I'll do that now.

Deven

[p5pRT]

From @deven

On Tue, Jul 10, 2018 at 1​:09 PM, James E Keenan via RT <
perlbug-followup@​perl.org> wrote​:

On Mon, 09 Jul 2018 04​:04​:32 GMT, dcorzine wrote​:

This is a bug report for perl from deven@​ties.org,
generated with the help of perlbug 1.41 running under perl 5.29.1.

[...]

Please submit the patch as an attachment. Even if it's not complete, it
gives us something to run through the test suite and a starting point for
discussion.

Fair enough. I'll do that now.

Deven

[p5pRT]

From @hvds

On Sun, 08 Jul 2018 21​:04​:32 -0700, dcorzine wrote​:

This was my test case, which works with or without anchors​:

"afoobar" =~ /((.)foo|bar)*/
"afoobar" =~ /^((.)foo|bar)*$/

Or, as a standalone command​:

perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

This prints "b", even though "bfoo" never appears in "afoobar"!
[...]
The correct answer seems to be "a", since that's the last match
of the inner group and the overall match is successful.

It's by no means clear to me that that must be the correct answer; the other candidate worth considering is that, since in /(...)*/ we return the match for the last iteration of the group, you'd expect further captures embedded within there also to deliver the version from the last iteration of the group.

Under that interpretation, the correct answer would be undef, and the earlier releases that returned 'a' were merely more subtly wrong than the current release.

The fact that other examples don't match such an interpretation argues against it​:
% perl -wle 'use Data​::Dumper; print Dumper([ "foobar" =~ /((foo)|(bar))*/ ])'
$VAR1 = [
  'bar',
  'foo',
  'bar'
  ];
%
.. but I don't recall seeing docs to justify such results. I'll have to have another wade through them.

Hugo

[p5pRT]

From @deven

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994​:

  perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons​:

* I haven't finished analyzing the code to check for edge cases that
  I may have overlooked with this patch. Since TRIE_next_fail included
  a test for ST.jump which would call UNWIND_PAREN(), I want to better
  understand how that was working and determine whether ST.jump being
  set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
  the patch to fix it, and I know that both BRANCH and TRIE variations
  need to be tested.

* This patch is currently saving ALL captures, including captures that
  can't possibly change inside the alternation. This is an easier fix,
  but I believe the performance impact should be mitigated, since this
  would impact many everyday regular expressions which aren't affected
  by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
  mitigate most (but not all) of the performance impact of this fix,
  but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
  for alternations containing capture groups, maybe only for ones which
  also have a quantifier applied, since I believe both are required to
  trigger this bug. (This might have to be treated as an optimization
  in regcomp.c to use the old logic for alternations that can't trigger
  the bug, but it might be hard to tell if a quantifier is applied for
  qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
  regular expression engine (maybe Yves?) about this patch and whether
  the approach I've taken is on the right track.

---

regexec.c | 28 ++++++++++++++++------------
regexp.h | 3 +++
2 files changed, 19 insertions(+), 12 deletions(-)

[p5pRT]

From @deven

perl-133136-test1.patch

From 1a53f4dc4ab5032ea9cd0bf254adc0902695daa4 Mon Sep 17 00:00:00 2001
From: "Deven T. Corzine" <deven@ties.org>
Date: Sat, 23 Jun 2018 23:17:03 -0400
Subject: [PATCH] Save and restore captures for BRANCH/TRIE failures

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994:

     perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons:

* I haven't finished analyzing the code to check for edge cases that
  I may have overlooked with this patch.  Since TRIE_next_fail included
  a test for ST.jump which would call UNWIND_PAREN(), I want to better
  understand how that was working and determine whether ST.jump being
  set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
  the patch to fix it, and I know that both BRANCH and TRIE variations
  need to be tested.

* This patch is currently saving ALL captures, including captures that
  can't possibly change inside the alternation.  This is an easier fix,
  but I believe the performance impact should be mitigated, since this
  would impact many everyday regular expressions which aren't affected
  by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
  mitigate most (but not all) of the performance impact of this fix,
  but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
  for alternations containing capture groups, maybe only for ones which
  also have a quantifier applied, since I believe both are required to
  trigger this bug.  (This might have to be treated as an optimization
  in regcomp.c to use the old logic for alternations that can't trigger
  the bug, but it might be hard to tell if a quantifier is applied for
  qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
  regular expression engine (maybe Yves?) about this patch and whether
  the approach I've taken is on the right track.
---
 regexec.c | 28 ++++++++++++++++------------
 regexp.h  |  3 +++
 2 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/regexec.c b/regexec.c
index ba52ae9..1d42b0d 100644
--- a/regexec.c
+++ b/regexec.c
@@ -5920,6 +5920,10 @@ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
 		HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
                 U32 state = trie->startstate;
 
+		/* save state of captures at branch start */
+		ST.cp = regcppush(rex, 0, maxopenparen);
+		REGCP_SET(ST.lastcp);
+
                 if (scan->flags == EXACTL || scan->flags == EXACTFLU8) {
                     _CHECK_AND_WARN_PROBLEMATIC_LOCALE;
                     if (utf8_target
@@ -6067,15 +6071,10 @@ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
 	case TRIE_next_fail: /* we failed - try next alternative */
         {
             U8 *uc;
-            if ( ST.jump ) {
-                /* undo any captures done in the tail part of a branch,
-                 * e.g.
-                 *    /(?:X(.)(.)|Y(.)).../
-                 * where the trie just matches X then calls out to do the
-                 * rest of the branch */
-                REGCP_UNWIND(ST.cp);
-                UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
-	    }
+
+	    /* restore state of captures from branch start */
+	    regcp_restore(rex, ST.lastcp, &maxopenparen);
+
 	    if (!--ST.accepted) {
 	        DEBUG_EXECUTE_r({
                     Perl_re_exec_indentf( aTHX_  "%sTRIE failed...%s\n",
@@ -8043,7 +8042,10 @@ NULL
 	    ST.lastparen = rex->lastparen;
 	    ST.lastcloseparen = rex->lastcloseparen;
 	    ST.next_branch = next;
-	    REGCP_SET(ST.cp);
+
+	    /* save state of captures at branch start */
+	    ST.cp = regcppush(rex, 0, maxopenparen);
+	    REGCP_SET(ST.lastcp);
 
 	    /* Now go into the branch */
 	    if (has_cutgroup) {
@@ -8077,8 +8079,10 @@ NULL
 	        do_cutgroup = 0;
 	        no_final = 0;
 	    }
-	    REGCP_UNWIND(ST.cp);
-            UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
+
+	    /* restore state of captures from branch start */
+	    regcp_restore(rex, ST.lastcp, &maxopenparen);
+
 	    scan = ST.next_branch;
 	    /* no more branches? */
 	    if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
diff --git a/regexp.h b/regexp.h
index 44409f0..aa61c97 100644
--- a/regexp.h
+++ b/regexp.h
@@ -754,6 +754,7 @@ typedef struct regmatch_state {
 	    U32 lastparen;
 	    U32 lastcloseparen;
 	    CHECKPOINT cp;
+	    CHECKPOINT lastcp;
 	    
         } branchlike;
         	    
@@ -763,6 +764,7 @@ typedef struct regmatch_state {
 	    U32 lastparen;
 	    U32 lastcloseparen;
 	    CHECKPOINT cp;
+	    CHECKPOINT lastcp;
 	    
 	    regnode *next_branch; /* next branch node */
 	} branch;
@@ -773,6 +775,7 @@ typedef struct regmatch_state {
 	    U32 lastparen;
 	    U32 lastcloseparen;
 	    CHECKPOINT cp;
+	    CHECKPOINT lastcp;
 
 	    U32		accepted; /* how many accepting states left */
 	    bool	longfold;/* saw a fold with a 1->n char mapping */
-- 
2.7.4

[p5pRT]

From @deven

On Tue, 10 Jul 2018 12​:19​:30 -0700, hv wrote​:

On Sun, 08 Jul 2018 21​:04​:32 -0700, dcorzine wrote​:

This was my test case, which works with or without anchors​:

"afoobar" =~ /((.)foo|bar)*/
"afoobar" =~ /^((.)foo|bar)*$/

Or, as a standalone command​:

perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

This prints "b", even though "bfoo" never appears in "afoobar"!
[...]
The correct answer seems to be "a", since that's the last match
of the inner group and the overall match is successful.

It's by no means clear to me that that must be the correct answer; the
other candidate worth considering is that, since in /(...)*/ we return
the match for the last iteration of the group, you'd expect further
captures embedded within there also to deliver the version from the
last iteration of the group.

Under that interpretation, the correct answer would be undef, and the
earlier releases that returned 'a' were merely more subtly wrong than
the current release.

Yeah, that's why I said the correct "seems" to be "a". There's a decent argument for returning undef, and it's certainly counter-intuitive to some degree to have $1="bar" from the second iteration and $2="a" from the first iteration, but the inner group does successfully match during the first iteration only, so "a" is indeed the last successful match.

I see two different viewpoints here, and both are quite reasonable. One viewpoint is that these are nested groups and both should be returning results from the same iteration, and therefore $2 should be undef because the nested match doesn't match anything on that iteration. Intuitively, this feels right. The other viewpoint is that each group can match multiple times and we only get to keep one capture per group, so $2 should be "a" since that's the last successful match for that group, despite the confusion of matching $1 and $2 from different iterations.

Personally, the $2="a" viewpoint seems like a stronger argument to me, but I could be in the minority in thinking that. I like the $2=undef viewpoint too, but we can't have both. In terms of how regular expressions are defined and documented, I'm having trouble rationalizing $2=undef even though it sounds good.

Is there anything definitive in the documentation that would resolve the question without ambiguity? I haven't found it yet, if there is.

For what it's worth, other regular expression engines like PCRE, RE2, GNU and others all return "a", which seems to suggest there may be some sort of consensus that "a" is the correct answer, but maybe it's just a gray area with no definite right answer?

The fact that other examples don't match such an interpretation argues
against it​:
% perl -wle 'use Data​::Dumper; print Dumper([ "foobar" =~
/((foo)|(bar))*/ ])'
$VAR1 = [
'bar',
'foo',
'bar'
];
%
.. but I don't recall seeing docs to justify such results. I'll have
to have another wade through them.

Hugo

That example is certainly returning $2 and $3 from different loop iterations, and it's less clear in this case that returning $2=undef would somehow be preferable or more intuitive for this example. Is that what you were getting at?

Deven

[p5pRT]

From @deven

[I originally entered this via RT, but I didn't see it come though
p5p, so I'm resending directly, hopefully it's not a duplicate!]

On Tue, 10 Jul 2018 12​:19​:30 -0700, hv wrote​:

On Sun, 08 Jul 2018 21​:04​:32 -0700, dcorzine wrote​:

This was my test case, which works with or without anchors​:

"afoobar" =~ /((.)foo|bar)*/
"afoobar" =~ /^((.)foo|bar)*$/

Or, as a standalone command​:

perl -e 'print "$2\n" if "afoobar" =~ /^((.)foo|bar)*$/;'

This prints "b", even though "bfoo" never appears in "afoobar"!
[...]
The correct answer seems to be "a", since that's the last match
of the inner group and the overall match is successful.

It's by no means clear to me that that must be the correct answer; the
other candidate worth considering is that, since in /(...)*/ we return
the match for the last iteration of the group, you'd expect further
captures embedded within there also to deliver the version from the
last iteration of the group.

Under that interpretation, the correct answer would be undef, and the
earlier releases that returned 'a' were merely more subtly wrong than
the current release.

Yeah, that's why I said the correct "seems" to be "a". There's a
decent argument for returning undef, and it's certainly
counter-intuitive to some degree to have $1="bar" from the second
iteration and $2="a" from the first iteration, but the inner group
does successfully match during the first iteration only, so "a" is
indeed the last successful match.

I see two different viewpoints here, and both are quite reasonable.
One viewpoint is that these are nested groups and both should be
returning results from the same iteration, and therefore $2 should be
undef because the nested match doesn't match anything on that
iteration. Intuitively, this feels right. The other viewpoint is
that each group can match multiple times and we only get to keep one
capture per group, so $2 should be "a" since that's the last
successful match for that group, despite the confusion of matching $1
and $2 from different iterations.

Personally, the $2="a" viewpoint seems like a stronger argument to me,
but I could be in the minority in thinking that. I like the $2=undef
viewpoint too, but we can't have both. In terms of how regular
expressions are defined and documented, I'm having trouble
rationalizing $2=undef even though it sounds good.

Is there anything definitive in the documentation that would resolve
the question without ambiguity? I haven't found it yet, if there is.

For what it's worth, other regular expression engines like PCRE, RE2,
GNU and others all return "a", which seems to suggest there may be
some sort of consensus that "a" is the correct answer, but maybe it's
just a gray area with no definite right answer?

The fact that other examples don't match such an interpretation argues
against it​:
% perl -wle 'use Data​::Dumper; print Dumper([ "foobar" =~
/((foo)|(bar))*/ ])'
$VAR1 = [
'bar',
'foo',
'bar'
];
%
.. but I don't recall seeing docs to justify such results. I'll have
to have another wade through them.

Hugo

That example is certainly returning $2 and $3 from different loop
iterations, and it's less clear in this case that returning $2=undef
would somehow be preferable or more intuitive for this example. Is
that what you were getting at?

Deven

[p5pRT]

From @deven

Has anyone taken a look at this patch yet? I'd like to hear what
others think so far, thanks!

Deven

On Tue, Jul 10, 2018 at 3​:19 PM, Deven T. Corzine via RT
<perlbug-followup@​perl.org> wrote​:

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994​:

 perl \-e 'print "$2\\n" if "afoobar" =~ /^\(\(\.\)foo|bar\)\*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons​:

* I haven't finished analyzing the code to check for edge cases that
I may have overlooked with this patch. Since TRIE_next_fail included
a test for ST.jump which would call UNWIND_PAREN(), I want to better
understand how that was working and determine whether ST.jump being
set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
the patch to fix it, and I know that both BRANCH and TRIE variations
need to be tested.

* This patch is currently saving ALL captures, including captures that
can't possibly change inside the alternation. This is an easier fix,
but I believe the performance impact should be mitigated, since this
would impact many everyday regular expressions which aren't affected
by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
mitigate most (but not all) of the performance impact of this fix,
but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
for alternations containing capture groups, maybe only for ones which
also have a quantifier applied, since I believe both are required to
trigger this bug. (This might have to be treated as an optimization
in regcomp.c to use the old logic for alternations that can't trigger
the bug, but it might be hard to tell if a quantifier is applied for
qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
regular expression engine (maybe Yves?) about this patch and whether
the approach I've taken is on the right track.
---
regexec.c | 28 ++++++++++++++++------------
regexp.h | 3 +++
2 files changed, 19 insertions(+), 12 deletions(-)

---
via perlbug​: queue​: perl5 status​: open
https://rt-archive.perl.org/perl5/Ticket/Display.html?id=133352

From 1a53f4dc4ab5032ea9cd0bf254adc0902695daa4 Mon Sep 17 00​:00​:00 2001
From​: "Deven T. Corzine" <deven@​ties.org>
Date​: Sat, 23 Jun 2018 23​:17​:03 -0400
Subject​: [PATCH] Save and restore captures for BRANCH/TRIE failures

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994​:

 perl \-e 'print "$2\\n" if "afoobar" =~ /^\(\(\.\)foo|bar\)\*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons​:

* I haven't finished analyzing the code to check for edge cases that
I may have overlooked with this patch. Since TRIE_next_fail included
a test for ST.jump which would call UNWIND_PAREN(), I want to better
understand how that was working and determine whether ST.jump being
set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
the patch to fix it, and I know that both BRANCH and TRIE variations
need to be tested.

* This patch is currently saving ALL captures, including captures that
can't possibly change inside the alternation. This is an easier fix,
but I believe the performance impact should be mitigated, since this
would impact many everyday regular expressions which aren't affected
by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
mitigate most (but not all) of the performance impact of this fix,
but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
for alternations containing capture groups, maybe only for ones which
also have a quantifier applied, since I believe both are required to
trigger this bug. (This might have to be treated as an optimization
in regcomp.c to use the old logic for alternations that can't trigger
the bug, but it might be hard to tell if a quantifier is applied for
qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
regular expression engine (maybe Yves?) about this patch and whether
the approach I've taken is on the right track.
---
regexec.c | 28 ++++++++++++++++------------
regexp.h | 3 +++
2 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/regexec.c b/regexec.c
index ba52ae9..1d42b0d 100644
--- a/regexec.c
+++ b/regexec.c
@​@​ -5920,6 +5920,10 @​@​ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
U32 state = trie->startstate;

+ /* save state of captures at branch start */
+ ST.cp = regcppush(rex, 0, maxopenparen);
+ REGCP_SET(ST.lastcp);
+
if (scan->flags == EXACTL || scan->flags == EXACTFLU8) {
_CHECK_AND_WARN_PROBLEMATIC_LOCALE;
if (utf8_target
@​@​ -6067,15 +6071,10 @​@​ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
case TRIE_next_fail​: /* we failed - try next alternative */
{
U8 *uc;
- if ( ST.jump ) {
- /* undo any captures done in the tail part of a branch,
- * e.g.
- * /(?​:X(.)(.)|Y(.)).../
- * where the trie just matches X then calls out to do the
- * rest of the branch */
- REGCP_UNWIND(ST.cp);
- UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
- }
+
+ /* restore state of captures from branch start */
+ regcp_restore(rex, ST.lastcp, &maxopenparen);
+
if (!--ST.accepted) {
DEBUG_EXECUTE_r({
Perl_re_exec_indentf( aTHX_ "%sTRIE failed...%s\n",
@​@​ -8043,7 +8042,10 @​@​ NULL
ST.lastparen = rex->lastparen;
ST.lastcloseparen = rex->lastcloseparen;
ST.next_branch = next;
- REGCP_SET(ST.cp);
+
+ /* save state of captures at branch start */
+ ST.cp = regcppush(rex, 0, maxopenparen);
+ REGCP_SET(ST.lastcp);

        /\* Now go into the branch \*/
        if \(has\_cutgroup\) \{

@​@​ -8077,8 +8079,10 @​@​ NULL
do_cutgroup = 0;
no_final = 0;
}
- REGCP_UNWIND(ST.cp);
- UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
+
+ /* restore state of captures from branch start */
+ regcp_restore(rex, ST.lastcp, &maxopenparen);
+
scan = ST.next_branch;
/* no more branches? */
if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
diff --git a/regexp.h b/regexp.h
index 44409f0..aa61c97 100644
--- a/regexp.h
+++ b/regexp.h
@​@​ -754,6 +754,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

     \} branchlike;

@​@​ -763,6 +764,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

        regnode \*next\_branch; /\* next branch node \*/
    \} branch;

@​@​ -773,6 +775,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

        U32         accepted; /\* how many accepting states left \*/
        bool        longfold;/\* saw a fold with a 1\->n char mapping \*/

--
2.7.4

[p5pRT]

From @deven

Has anyone taken a look at this patch yet? I'd like to hear what
others think so far, thanks!

Deven

On Tue, Jul 10, 2018 at 3​:19 PM, Deven T. Corzine via RT
<perlbug-followup@​perl.org> wrote​:

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994​:

 perl \-e 'print "$2\\n" if "afoobar" =~ /^\(\(\.\)foo|bar\)\*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons​:

* I haven't finished analyzing the code to check for edge cases that
I may have overlooked with this patch. Since TRIE_next_fail included
a test for ST.jump which would call UNWIND_PAREN(), I want to better
understand how that was working and determine whether ST.jump being
set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
the patch to fix it, and I know that both BRANCH and TRIE variations
need to be tested.

* This patch is currently saving ALL captures, including captures that
can't possibly change inside the alternation. This is an easier fix,
but I believe the performance impact should be mitigated, since this
would impact many everyday regular expressions which aren't affected
by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
mitigate most (but not all) of the performance impact of this fix,
but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
for alternations containing capture groups, maybe only for ones which
also have a quantifier applied, since I believe both are required to
trigger this bug. (This might have to be treated as an optimization
in regcomp.c to use the old logic for alternations that can't trigger
the bug, but it might be hard to tell if a quantifier is applied for
qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
regular expression engine (maybe Yves?) about this patch and whether
the approach I've taken is on the right track.
---
regexec.c | 28 ++++++++++++++++------------
regexp.h | 3 +++
2 files changed, 19 insertions(+), 12 deletions(-)

---
via perlbug​: queue​: perl5 status​: open
https://rt-archive.perl.org/perl5/Ticket/Display.html?id=133352

From 1a53f4dc4ab5032ea9cd0bf254adc0902695daa4 Mon Sep 17 00​:00​:00 2001
From​: "Deven T. Corzine" <deven@​ties.org>
Date​: Sat, 23 Jun 2018 23​:17​:03 -0400
Subject​: [PATCH] Save and restore captures for BRANCH/TRIE failures

This is a first pass at a patch to fix RT #133352, to save and restore
all captures during alternations (BRANCH and TRIE) to avoid incorrectly
returning a capture from a failed branch, as happens with the following
test case, which has been broken ever since Perl 5.000 in 1994​:

 perl \-e 'print "$2\\n" if "afoobar" =~ /^\(\(\.\)foo|bar\)\*$/;'

Perl 2.0 through Perl 5.0 alpha 9 all print "a" for this command, while
Perl 5.000 through today's blead all incorrectly print "b" instead.

This patch appears to work (making the test case above print "a" again),
and I am submitting it as a preliminary patch for discussion purposes;
I don't consider it ready to apply yet, for a number of reasons​:

* I haven't finished analyzing the code to check for edge cases that
I may have overlooked with this patch. Since TRIE_next_fail included
a test for ST.jump which would call UNWIND_PAREN(), I want to better
understand how that was working and determine whether ST.jump being
set might have any implications for this patch.

* I haven't developed any new regression tests to exercise this bug and
the patch to fix it, and I know that both BRANCH and TRIE variations
need to be tested.

* This patch is currently saving ALL captures, including captures that
can't possibly change inside the alternation. This is an easier fix,
but I believe the performance impact should be mitigated, since this
would impact many everyday regular expressions which aren't affected
by this bug in the first place.

* I believe that setting a paren floor (which CURLYX does) would likely
mitigate most (but not all) of the performance impact of this fix,
but I haven't yet found a clean way to implement this.

* Another possibility might be to create new regnode types to use only
for alternations containing capture groups, maybe only for ones which
also have a quantifier applied, since I believe both are required to
trigger this bug. (This might have to be treated as an optimization
in regcomp.c to use the old logic for alternations that can't trigger
the bug, but it might be hard to tell if a quantifier is applied for
qr// cases.)

* Regardless, I would like feedback from an expert on this part of the
regular expression engine (maybe Yves?) about this patch and whether
the approach I've taken is on the right track.
---
regexec.c | 28 ++++++++++++++++------------
regexp.h | 3 +++
2 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/regexec.c b/regexec.c
index ba52ae9..1d42b0d 100644
--- a/regexec.c
+++ b/regexec.c
@​@​ -5920,6 +5920,10 @​@​ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
U32 state = trie->startstate;

+ /* save state of captures at branch start */
+ ST.cp = regcppush(rex, 0, maxopenparen);
+ REGCP_SET(ST.lastcp);
+
if (scan->flags == EXACTL || scan->flags == EXACTFLU8) {
_CHECK_AND_WARN_PROBLEMATIC_LOCALE;
if (utf8_target
@​@​ -6067,15 +6071,10 @​@​ S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
case TRIE_next_fail​: /* we failed - try next alternative */
{
U8 *uc;
- if ( ST.jump ) {
- /* undo any captures done in the tail part of a branch,
- * e.g.
- * /(?​:X(.)(.)|Y(.)).../
- * where the trie just matches X then calls out to do the
- * rest of the branch */
- REGCP_UNWIND(ST.cp);
- UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
- }
+
+ /* restore state of captures from branch start */
+ regcp_restore(rex, ST.lastcp, &maxopenparen);
+
if (!--ST.accepted) {
DEBUG_EXECUTE_r({
Perl_re_exec_indentf( aTHX_ "%sTRIE failed...%s\n",
@​@​ -8043,7 +8042,10 @​@​ NULL
ST.lastparen = rex->lastparen;
ST.lastcloseparen = rex->lastcloseparen;
ST.next_branch = next;
- REGCP_SET(ST.cp);
+
+ /* save state of captures at branch start */
+ ST.cp = regcppush(rex, 0, maxopenparen);
+ REGCP_SET(ST.lastcp);

        /\* Now go into the branch \*/
        if \(has\_cutgroup\) \{

@​@​ -8077,8 +8079,10 @​@​ NULL
do_cutgroup = 0;
no_final = 0;
}
- REGCP_UNWIND(ST.cp);
- UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
+
+ /* restore state of captures from branch start */
+ regcp_restore(rex, ST.lastcp, &maxopenparen);
+
scan = ST.next_branch;
/* no more branches? */
if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
diff --git a/regexp.h b/regexp.h
index 44409f0..aa61c97 100644
--- a/regexp.h
+++ b/regexp.h
@​@​ -754,6 +754,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

     \} branchlike;

@​@​ -763,6 +764,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

        regnode \*next\_branch; /\* next branch node \*/
    \} branch;

@​@​ -773,6 +775,7 @​@​ typedef struct regmatch_state {
U32 lastparen;
U32 lastcloseparen;
CHECKPOINT cp;
+ CHECKPOINT lastcp;

        U32         accepted; /\* how many accepting states left \*/
        bool        longfold;/\* saw a fold with a 1\->n char mapping \*/

--
2.7.4

[p5pRT]

From @iabyn

On Sun, Jul 15, 2018 at 03​:52​:30PM -0400, Deven T. Corzine wrote​:

Has anyone taken a look at this patch yet? I'd like to hear what
others think so far, thanks!

I plan to look at it at some point, but I hate and fear the capture
save and restore code in regmatch(), which has kept me away from looking
at your patch yet. Maybe in a few days.

--
Art is anything that has a label (especially if the label is "untitled 1")

[p5pRT]

From @iabyn

On Sun, Jul 15, 2018 at 03​:52​:30PM -0400, Deven T. Corzine wrote​:

Has anyone taken a look at this patch yet? I'd like to hear what
others think so far, thanks!

I plan to look at it at some point, but I hate and fear the capture
save and restore code in regmatch(), which has kept me away from looking
at your patch yet. Maybe in a few days.

--
Art is anything that has a label (especially if the label is "untitled 1")

[p5pRT]

From @deven

On Mon, Jul 16, 2018 at 4​:13 AM, Dave Mitchell <davem@​iabyn.com> wrote​:

I plan to look at it at some point, but I hate and fear the capture
save and restore code in regmatch(), which has kept me away from looking
at your patch yet. Maybe in a few days.

I look forward to hearing your feedback, thanks Dave! That's
definitely complex code! It took quite a few hours of study to
understand it well enough to make that patch, though it's only a few
lines long.

The patch still needs work -- right now it's saving and restoring ALL
the captures, which is overkill. There's no need to save and restore
captures that are outside the alternation, and that could affect the
performance of many regexes which aren't affected by this bug in the
first place.

My initial inclination was try setting a paren floor (which CURLYX
does), but I haven't figured out a clean way to do that yet.

When a regmatch_state is allocated, is the memory cleared or uninitialized?

Deven