Is this a /^*/ bug?

[Tom Christiansen]

I realize this is nonsense, but I wonder if it is not a bug. Shouldn't the
overall pattern still fail, not succeed?

% perl -WE 'say "foo.bar" =~ /^.*.bar$/ || "FAIL"'
1

% perl -WE 'say "foo.bar" =~ /^*.bar$/ || "FAIL"'
^* matches null string many times in regex; marked by <-- HERE in m/^* <-- HERE .bar$/ at -e line 1.
1

% perl -WE 'say "foo.bar" =~ /(^*).bar$/ || "FAIL"'
^* matches null string many times in regex; marked by <-- HERE in m/(^* <-- HERE ).bar$/ at -e line 1.
1

% perl -WE 'say "foo.bar" =~ /^.bar$/ || "FAIL"'
FAIL

Tested with v5.8.8, v5.14.0, v5.16.0, and v5.17.0-352-g3630f57.

--tom

[Zefram]

Tom Christiansen wrote:
>I realize this is nonsense, but I wonder if it is not a bug. Shouldn't the
>overall pattern still fail, not succeed?

No, the behaviour looks correct to me. /^*/ will match beginning-of-line
zero or more times. In your example, the pattern matches completely
when this repetition count is zero: it's not matching beginning-of-line,
but you didn't require it to.

-zefram

[demerphq]

There might be a case to change this from a warning to a fatal error.

But its a warning, and as such no, I dont think the pattern should fail:

$ perl -WE 'say "foo.bar" =~ /^*.bar$/ || "FAIL"' 2>&1 | splain

^* matches null string many times in regex; marked by <-- HERE in m/^* <-- HERE

.bar$/ at -e line 1 (#1)
(W regexp) The pattern you've specified would be an infinite loop if the
regular expression engine didn't specifically check for that. The <-- HERE
shows in the regular expression about where the problem was discovered.
See perlre.

1

Consider that ^* means "match at the start of the string 0 or more
times". So the pattern succeeds because it matches 0 times.

It warns because it could match at the same spot an infinite number of times.

All of this is as I expect.

Yves




--
perl -Mre=debug -e "/just|another|perl|hacker/"

[Brad Gilbert]

$ perl -WE'say "foo.bar" =~ /^+.bar/ || "FAIL"'
^+ matches null string many times in regex; marked by <-- HERE in
m/^+ <-- HERE .bar/ at -e line 1.
FAIL

$ perl -WE'say "foo.bar" =~ /^?.bar/ || "FAIL"'
1

`"foo.bar" =~ /^*.bar/` doesn't fail because it allows `^` to not
match anything
thus allowing it to start to match later in the string.

$ perl -WE '"foo.bar" =~ /^*.bar$/; say $&'

^* matches null string many times in regex; marked by <-- HERE in
m/^* <-- HERE .bar$/ at -e line 1.

.bar

Imagine if the `^` were replaced with `\b`, another zero width assertion

$ perl -WE '"foo.bar" =~ /\b*.bar$/; say $&'
\b* matches null string many times in regex; marked by <-- HERE in
m/\b* <-- HERE .bar$/ at -e line 1.
.bar

[Tom Christiansen]

I read is as saying

1 Match the beginning of the string 0 or more times.
2 Match any one non-newline character.
3 Match the constant string "bar"
4 Match the end of the string, with optional newline slop

I think somehow the pointer tracking the position in the string to matched
got bumped up inappropriately because of the constant-string-at-the-end
optimization. It fails to account for the "foo" bar, which is why I
believe it is in error.

But you are saying that it is ok *not* to match the beginning of the
string, since 0 or more includes 0, and here we did not match the
beginning of the string at all.

That's pretty darned ugly, is all I can say.

--tom

[demerphq]

No arguments here.

> I think somehow the pointer tracking the position in the string to matched
> got bumped up inappropriately because of the constant-string-at-the-end
> optimization. It fails to account for the "foo" bar, which is why I
> believe it is in error.

Well I can see why there might be confusion here. But consider, do you
think that

perl -Mre=debug -WE 'say "foo.bar" =~ /.bar$/

should fail?

Because to me the two patterns are functionally identical. ^* or ^?
are to me no-ops, so you can just remove them from the pattern when
you analyze what it does.

> But you are saying that it is ok *not* to match the beginning of the
> string, since 0 or more includes 0, and here we did not match the
> beginning of the string at all.
>
> That's pretty darned ugly, is all I can say.

Maybe the helps: (# comments added by me):

$ perl -Mre=debug -WE 'say "foo.bar" =~ /^*.bar$/ || "FAIL"'
Compiling REx "^*.bar$"

^* matches null string many times in regex; marked by <-- HERE in m/^*
<-- HERE .bar$/ at -e line 1.

Final program:
1: CURLYX[0] {0,32767} (5)
3: BOL (4)
4: WHILEM[1/1] (0)
5: NOTHING (6)
6: REG_ANY (7)
7: EXACT <bar> (9)
9: EOL (10)
10: END (0)
floating "bar"$ at 1..1 (checking floating) minlen 4

# so this says that it must find a "bar" at the end of the string


Guessing start of match in sv for REx "^*.bar$" against "foo.bar"
Found floating substr "bar"$ at offset 4...
Starting position does not contradict /^/m...
Guessed: match at offset 3

# So it found "bar" at offset 4, and then decremented the start pos by
1 (because it needs 4 chars to match)

Matching REx "^*.bar$" against ".bar"
3 <foo> <.bar> | 1:CURLYX[0] {0,32767}(5)
3 <foo> <.bar> | 4: WHILEM[1/1](0)
whilem: matched 0 out of 0..32767
3 <foo> <.bar> | 3: BOL(4)
failed...
whilem: failed, trying continuation...
3 <foo> <.bar> | 5: NOTHING(6)
3 <foo> <.bar> | 6: REG_ANY(7)
4 <foo.> <bar> | 7: EXACT <bar>(9)
7 <foo.bar> <> | 9: EOL(10)
7 <foo.bar> <> | 10: END(0)
Match successful!
1
Freeing REx: "^*.bar$"

# And matched successfully at that position.

[Zefram]

Tom Christiansen wrote:
>I think somehow the pointer tracking the position in the string to matched
>got bumped up inappropriately because of the constant-string-at-the-end
>optimization.

Seems perfectly appropriate, if such optimisation was applied.

>But you are saying that it is ok *not* to match the beginning of the
>string, since 0 or more includes 0, and here we did not match the
>beginning of the string at all.

Yes. It matched beginning-of-line zero times, which is within the range
that is compatible with an overall match.

>That's pretty darned ugly, is all I can say.

What's the alternative? If the "*" is interpreted as a quantifier
(which is how you read it), the only thing it can be quantifying is /^/.
The observed behaviour is the perfectly regular result of applying the
quantifier to the anchor. A match failure would require some irregular
rule, which would be uglier.

The actual alternative comes from very old regexp semantics. In BREs,
"^" isn't a regular (hence quantifiable) regexp node. Instead, it's
a flag that's only recognised at the very beginning of the regexp, and
has the effect of anchoring the regexp as a whole. (Similarly "$" at
the end.) If "^" appears anywhere other than the very beginning then,
as with any other misplaced metachar, it's treated as literal. Which is
also how "*" is treated when it's at the beginning of the pattern with
nothing to quantify. So in this system /^*/ matches a literal "*"
at beginning-of-line.

-zefram

[A. Pagaltzis]

* Zefram <zef...@fysh.org> [2013-03-25 17:40]:

> What's the alternative? If the "*" is interpreted as a quantifier
> (which is how you read it), the only thing it can be quantifying is
> /^/. The observed behaviour is the perfectly regular result of
> applying the quantifier to the anchor. A match failure would require
> some irregular rule, which would be uglier.

Should zero-width assertions in general be quantifiable at all? What
would be the fallout of making that a compile-time error? If too bad,
what of optimising them away with a specially worded warning?

[h...@crypt.org]

"A. Pagaltzis" <paga...@gmx.de> wrote:
:* Zefram <zef...@fysh.org> [2013-03-25 17:40]:

:> What's the alternative? If the "*" is interpreted as a quantifier
:> (which is how you read it), the only thing it can be quantifying is
:> /^/. The observed behaviour is the perfectly regular result of
:> applying the quantifier to the anchor. A match failure would require
:> some irregular rule, which would be uglier.
:
:Should zero-width assertions in general be quantifiable at all?

I believe so. The canonical example is optional lookahead with capture
/(?=x(y)z)?/ - the side-effect of capture makes it a not necessarily
useless thing to do.

:What would be the fallout of making that a compile-time error?

A bunch of stuff would fall over at runtime; in a small number of cases
that would highlight a bug that might not otherwise have been found, or
found as quickly; in most cases it will already have been doing what
was wanted, and people will either change the pattern to something
equivalent-but-legal (if a fixed pattern), or put in extra (probably buggy)
logic to detect and change to equivalent-but-legal for a constructed pattern.

I say "probably buggy", because detecting this in the general case is quite
hard: I think you can't do it with anything short of a full regexp parser.

:If too bad, what of optimising them away with a specially worded warning?

That's exactly what we do now. The specially worded warning is "matches null
string many times in regex", and you can see the optimization under debug:

% perl -Mre=debug -wle '"foo" =~ /^+f/' 2>&1 | grep 'while'
whilem: matched 0 out of 1..32767
whilem: matched 1 out of 1..32767
whilem: empty match detected, trying continuation...
%

Without optimization, it would match 32767 of them before continuing.

Hugo

[Eric Brine]

On Mon, Mar 25, 2013 at 10:14 PM, A. Pagaltzis <paga...@gmx.de> wrote:

Should zero-width assertions in general be quantifiable at all? What
would be the fallout of making that a compile-time error? If too bad,
what of optimising them away with a specially worded warning?

/...(?=.*(foo))?.../ might make sense, but could be automatically rewritten as /...(?=(?:.*(foo))?).../

[Zefram]

h...@crypt.org wrote:
>That's exactly what we do now. The specially worded warning is "matches null
>string many times in regex",

There's no warning for /^?/.

-zefram

[demerphq]

I dont think there should be

?

is syntactic sugar for

(?:X|)

so

^?

means:

(?:^|)

and IMO at that point it is perfectly reasonable. Anything could be in
the second half of that alternation.

[Tom Christiansen]

demerphq <deme...@gmail.com> wrote on Tue, 26 Mar 2013 11:11:57 BST:

>On 26 March 2013 11:01, Zefram <zef...@fysh.org> wrote:
>> h...@crypt.org wrote:
>>>That's exactly what we do now. The specially worded warning is "matches null
>>>string many times in regex",
>>
>> There's no warning for /^?/.

> I dont think there should be

> ?

> is syntactic sugar for

> (?:X|)

> so

> ^?

> means:

> (?:^|)

> and IMO at that point it is perfectly reasonable. Anything could be in
> the second half of that alternation.

That's exactly what I eventually arrived at thinking, too.

--tom

[Aristotle Pagaltzis]

* h...@crypt.org <h...@crypt.org> [2013-03-26 10:30]:

> "A. Pagaltzis" <paga...@gmx.de> wrote:
> > Should zero-width assertions in general be quantifiable at all?
>
> I believe so. The canonical example is optional lookahead with capture
> /(?=x(y)z)?/ - the side-effect of capture makes it a not necessarily
> useless thing to do.

Is there a similar case to make for `*` instead of `?`?

> > What would be the fallout of making that a compile-time error?
>
> A bunch of stuff would fall over at runtime; in a small number of
> cases that would highlight a bug that might not otherwise have been
> found, or found as quickly; in most cases it will already have been
> doing what was wanted, and people will either change the pattern to
> something equivalent-but-legal (if a fixed pattern), or put in extra
> (probably buggy) logic to detect and change to equivalent-but-legal
> for a constructed pattern.

The case with captures within zero-width assertions essentially makes it
unappealing.

One could debate the utility of still disallowing quantifiers after
non-generic zero-width assertions like `^`, `$`, `\A`, `\b` etc., which
inherently cannot enclose captures within (nor (?{}) constructs, for
that matter).

But then we get a conditional rule with an ad-hoc inclusion list, rather
than a general principle, which is exactly what Zefram argued against
with good reason.

Oh well.

> I say "probably buggy", because detecting this in the general case is
> quite hard: I think you can't do it with anything short of a full
> regexp parser.

I did mean for the pattern compiler to detect this during REx program
construction, when it creates a node for a quantifier, and finds its
previous node to be some zero-width assertion construction. I did not
mean doing it by way of some clumsy string matching against the pattern.

> > If too bad, what of optimising them away with a specially worded
> > warning?
>
> That's exactly what we do now. The specially worded warning is "matches null
> string many times in regex", and you can see the optimization under debug:
>
> % perl -Mre=debug -wle '"foo" =~ /^+f/' 2>&1 | grep 'while'
> whilem: matched 0 out of 1..32767
> whilem: matched 1 out of 1..32767
> whilem: empty match detected, trying continuation...
> %
>
> Without optimization, it would match 32767 of them before continuing.

I thought it was a runtime warning. Mea culpa.


* demerphq <deme...@gmail.com> [2013-03-26 11:15]:

> On 26 March 2013 11:01, Zefram <zef...@fysh.org> wrote:
> > h...@crypt.org wrote:
> > There's no warning for /^?/.
>
> I dont think there should be
>
> ?
>
> is syntactic sugar for
>
> (?:X|)
>
> so
>
> ^?
>
> means:
>
> (?:^|)
>
> and IMO at that point it is perfectly reasonable. Anything could be in
> the second half of that alternation.

No it couldn’t. If you write the long form with the alternation, then
sure. And there are lots of times I have written `(?:^|/)` in URL
rewrite rules, say. But I have never literally written `(?:^|)` (with
nothing on the right side). Because, err, what would be the point? But
since we’re not trying to solve the halting problem, a literal `(?:^|)`
is reasonable to not warn on.

However there is no way to write `^?` and then add something to it such
that it equates to `(?:^|$whatever)`. So I don’t see how a literal `^?`
would ever make sense to show up in a pattern. (Well – I suppose it *is*
a cute way of golfing `(?:)`…) And so in the name of assisting the user
it would be reasonable to warn or even error on that construct.

But the inconsistency required between simple and compound zero-width
assertions makes me disinclined toward the idea anyhow. So consider my
tentative suggestion retracted.

Regards,
--
Aristotle Pagaltzis // <http://plasmasturm.org/>

[h...@crypt.org]

Aristotle Pagaltzis <paga...@gmx.de> wrote:
:> A bunch of stuff would fall over at runtime; in a small number of

:> cases that would highlight a bug that might not otherwise have been
:> found, or found as quickly; in most cases it will already have been
:> doing what was wanted, and people will either change the pattern to
:> something equivalent-but-legal (if a fixed pattern), or put in extra
:> (probably buggy) logic to detect and change to equivalent-but-legal
:> for a constructed pattern.

[...]
:> I say "probably buggy", because detecting this in the general case is

:> quite hard: I think you can't do it with anything short of a full
:> regexp parser.
:
:I did mean for the pattern compiler to detect this during REx program
:construction, when it creates a node for a quantifier, and finds its
:previous node to be some zero-width assertion construction. I did not
:mean doing it by way of some clumsy string matching against the pattern.

My "probably buggy" was referring to the workaround Joe Perl puts in when
his regexp construction code (which was working fine, but which he no longer
fully understands) starts dying after a perl upgrade. He *will* do that by

clumsy string matching against the pattern.

Hugo