Document a bug in Perl in 5.18.*

[petdance]

This should match, but doesn't.

$ echo 'x"firstname":"peter"' | ack '"firstname":"[^"]*"'

Take away the leading x and it succeeds

$ echo '"firstname":"peter"' | ack '"firstname":"[^"]*"'
"firstname":"peter"

Change the * to + and it succeeds.

$ echo 'x"firstname":"peter"' | ack '"firstname":"[^"]+"'
x"firstname":"peter"

Change firstname to z and it succeeds.

$ echo 'x"z":"peter"' | ack '"z":"[^"]*"'
x"z":"peter"

This happens in ack 2 as well. This is the simplest failing case I've been able to make so far.

I'm wondering if the ^ in the class negation is somehow getting translated into a ^ that anchors at the beginning of the string.

[petdance]

Whittled further

$ echo 'x"first":"p"' | ack '"first":"[^"]*"'
$ echo 'x"firs":"p"' | ack '"firs":"[^"]*"'
x"firs":"p"

But this is only on my Mac, not on Linux.

[n1vux]

also fails for me with same Perl 5.18.2 that Andy reported was on his Mac.

[n1vux]

i do remember seeing some examples of *, *?, + behaving oddly in the wild too )
further cases using . instead of [^"]

$ echo 'x"first":"p"' | ack2 '"first":".*?"'
$ echo 'x"first":"p"' | ack2 '"first":".+"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 '"first":".+?"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 '"first":"..*?"'
x"first":"p"

[n1vux]

I attempted to get perl to abuse the RE same as ack does (cribbing processing of $opt_regex from ack3) to provoke the bad behavior with perl 5.18 but no luck.

$ echo 'x"firs":"p"' \
   | PAT='"firs":"[^"]*"'  perl -nle'use 5.01001; $str=$ENV{PAT}; my $re = eval { qr/$str/m }; /$re/o; print while $_ =~ /$re/og;'
x"firs":"p"

[n1vux]

Even replacing wild card with p* fails ...

$ echo 'x"first":"p"' | ack2 '"first":"p*"'
$ echo 'x"first":"p"' | ack2 '"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 ':"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 '":"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 't":"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 'st":"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 'rst":"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 'irst":"p*"'
x"first":"p"
$ echo 'x"first":"p"' | ack2 'first":"p*"'

Bing! no understanding of why that ... but consistent with firs vs first above

[petdance]

It's something with /i.

$ echo 'x"first":"p"' | perl -E'say <> =~ /(?i)"first":"p*"/'

$ echo 'x"first":"p"' | perl -E'say <> =~ /(?i)"first":"p+"/'
1
$ echo 'x"first":"p"' | perl -E'say <> =~ /"first":"p*"/'
1

Dropping the (?i) makes it work.

[petdance]

@n1vux has it narrowed down to a bug in Perl:

perlbrew exec perl -le'$x=q(x"first":"p"); $str=q(first":"p*"); my $re = eval { qr/$str/im }; /$re/og; if ( $x  =~ /$re/og) {print qq(ok $]) ; } else { print qq(FAIL $] testing "$x" =~ $re"); };'

Using that tester, we find that it fails in Perl 5.18.0 and 5.18.2.

Do we want to warn people about it?

[petdance]

Simpler by one character:

perlbrew exec \
perl -le'$x=q("first":"p"); $str=q(first":"p*"); my $re = eval { qr/$str/im }; /$re/og; if ( $x  =~ /$re/og) {print qq(ok $]) ; } else { print qq(FAIL $] testing "$x" =~ $re"); };'

[n1vux]

With my perlbrew collection, 5.18.x is only* perl for which Andy's t/gh95.t fails, and the following concurs

$ perlbrew exec perl -le'$x=q(x"first":"p"); $str=q(first":"p*"); my $re = eval { qr/$str/im }; \
  /$re/og; if ( $x  =~ /$re/og) {print qq(ok $]) ; }  \
  else { print qq(FAIL $] testing "$x" =~ $re"); };'

• and 5.6.1 doesn't do -E of course !

I infer some fix listed in perldelta5180 causes this and that some fix possibly listed in 5.20.0 cleared it, but both lists are selective.

E.g., 5.18.0 says

Some failed regular expression matches such as 'f' =~ /../g" were not resetting pos . Also, "match-once" patterns(m?...?g)` failed to reset it, too, when invoked a second time [perl #23180].

My intuition is it's a failed optimization in Perl's RE engine that is botching the quantifiers, but maybe something else..

Checking cross-product of /i, /m modifiers and various quantifiers, ? * *? + +? {1} {0,1} {0,3}, test below, we can conclude

• The //i modifier (ack -i --smart-case) is required to fail.
• The //m modifier is irrelevant.
• The p is quantified as optional enables fail; somehow p? is treated as p{0} not as p{0}|p{1}.
• bug introduced in Perl, not Ack; after perl-5.16.x, no later than dev release perl-5.17.11, fixed no later than perl-5.20.0-RC1

The Perl RE engine should deduce that the optional p is required to get from 3rd " to matching the final 4th ". If "p{0,1}" doesn't match with 'p' x 0 , then it must try 'p' x 1`

Example below works uniformly on all perl >= 5.10.1 except 5.17/18; 5.20.0-RC1 is good first good again. So we can conclude it is 5.18.x only.

for $ii ("(?i)", "", "(?im)", "(?m)" ){ 
    for $cc ( "?", "*",  "*?", "+",  "+?",  "{1}", "{0,1}", "{0,3}", "{0,}", "{1,}" ){ 
        $str=q{first":"}."p$cc".q{"}; my $re = eval { qr/$ii$str/ };  
        if (scalar( q(x"first":"p") =~ /$re/)){ print qq(ok    $] $cc $ii)}
        else{print qq(fail! $] $cc $ii $re)};
     }}' 2>/dev/null | ack 'fail(?!.*im)'

fail! 5.017011 ? (?i) (?^:(?i)first":"p?")
fail! 5.017011 * (?i) (?^:(?i)first":"p*")
fail! 5.017011 *? (?i) (?^:(?i)first":"p*?")
fail! 5.017011 {0,1} (?i) (?^:(?i)first":"p{0,1}")
fail! 5.017011 {0,3} (?i) (?^:(?i)first":"p{0,3}")
fail! 5.017011 {0,} (?i) (?^:(?i)first":"p{0,}")

fail! 5.018002 ? (?i) (?^:(?i)first":"p?")
fail! 5.018002 * (?i) (?^:(?i)first":"p*")
fail! 5.018002 *? (?i) (?^:(?i)first":"p*?")
fail! 5.018002 {0,1} (?i) (?^:(?i)first":"p{0,1}")
fail! 5.018002 {0,3} (?i) (?^:(?i)first":"p{0,3}")
fail! 5.018002 {0,} (?i) (?^:(?i)first":"p{0,}")

fail! 5.018004 * (?i) (?^:(?i)first":"p*")
fail! 5.018004 *? (?i) (?^:(?i)first":"p*?")
fail! 5.018004 {0,1} (?i) (?^:(?i)first":"p{0,1}")
fail! 5.018004 {0,3} (?i) (?^:(?i)first":"p{0,3}")
fail! 5.018004 {0,} (?i) (?^:(?i)first":"p{0,}")

All of these fail as if {0,} was {0}.

Andy noted earlier, removing the unmatched prefix from the target string so that the pattern RE matches the first char is sufficient to mask this. Prefixing pattern with .* to allow it to match from first is also sufficient. So there is subtle interplay between case insensitive, quantifier backtracking, and stepping the beginning back-tracking. Since there were pos bugs mentioned, this could be splatter from those bugs ?

List of perls tested -

perl-5.10.1 perl-5.12.5 perl-5.14.4  perl-5.16.2 perl-5.16.3(forced) perl-5.17.11(forced) perl-5.17.11 perl-5.18.0 (5.18.2) perl-5.18.4(forced) perl-5.18.4  perl-5.20.0-RC1 perl-5.22 perl-5.20.3 perl-5.22.0  perl-5.22.4 perl-5.24.2 perl-5.25.0 perl-5.26.0 perl-5.27.2=perl-blead 

(forced = perl install forced due to failing tests, but behaves predictably for above tests.)

[n1vux]

= How do we communicate?

In the Known Issues section (normally in MAN template, do we have one? add one?)

There was known bug in (officially obsolete) perl 5.18.*'s RegEx internals (pos and backtracking), which was long since fixed in 5.20.0 (2017) and later, that has failing edgecases visible in ack2 and ack3 search.

== Necessary Conditions

Bug seems to appear if

• ack executed under perl 5.18.x, and
• -i (including --smart-case ), and
• if pattern is not anchored to beginning, and
• a quantifier that doesn't end the pattern allows for 0 repetitions (.* .{0,} .? etc)

== Uknowns

• a data sensitivity, as above are necessary for known edgecase, but demonstrated not sufficient.
• whethe -i or equivalent (?i) is absolutely necessary, or if other paths to the bug may exist.
• if old ack1 suffers from this also, but may be presumed.

== Workarounds

For those using ack with perl 5.18:

• upgrade perl to 5.20 or later;
• or use perlbrew to get a local perl and insert that in ack-standalone #! line;
• or do not use -i or --smart-case with perl 5.18 (including remove from ackrc files);
• or specify -I whenever using * or ? or similar 0+ quantifier not at end of pattern (this is fallible so not recommended);
• or use ^.*?\K prefix to anchor pattern at start but ignore from there to first real match
• or insert a \K at start of pattern (or anywhere before quantified term); highlight will start at that point. Hypothesis is this works because it forces a pos sync !

=Optional Enforcement

We could insert in both Ack2 (github and next patch if any) and Ack3 a check for $] =~ /^5[.]01[78]/ and print the above as a fatal error unless a --p518-silent-assent is added to ackrc, ENV, or the shell cmd; and report fatally that --p518-silent-assent is incompatible with -i or --smart-case (use `-I') if violated.

(I suggest that is overkill for this but if reliability is paramount, this would prevent wrong answers. But we don't know )