Open p5pRT opened 5 years ago
p5pRT
commented
5 years ago Please see the following example:
$ perl -e 'if (abcd =~ /\A(?:.(*COMMIT))*c/) { print "yes >$&\<\n"; } else { print "no \n"; }' yes >abc\<
Why does that pattern match? The repeated group should swallow all of "abcd"\, then fail to match "c" and so backtrack onto (*COMMIT)\, which should fail the whole match\, shouldn't it?
Philip
p5pRT
commented
5 years ago On Tue\, 2 Jul 2019 at 11:17\, Philip Hazel (via RT) \perlbug\-followup@​perl\.org wrote:
# New Ticket Created by Philip Hazel # Please include the string: [perl #134254] # in the subject line of all future correspondence about this issue. # \<URL: https://rt-archive.perl.org/perl5/Ticket/Display.html?id=134254 >
To: perlbug@perl.org Reply-To: ph10@cam.ac.uk Subject: (*COMMIT) behaviour when inside a repeated group From: ph10@cam.ac.uk Cc: builduser Message-Id: \5\.30\.0\_5771\_1562058560@​quercite
This is a bug report for perl from ph10@cam.ac.uk\, generated with the help of perlbug 1.41 running under perl 5.30.0.
----------------------------------------------------------------- [Please describe your issue here]
Please see the following example:
$ perl -e 'if (abcd =~ /\A(?:.(*COMMIT))*c/) { print "yes >$&\<\n"; } else { print "no \n"; }' yes >abc\<
Why does that pattern match? The repeated group should swallow all of "abcd"\, then fail to match "c" and so backtrack onto (*COMMIT)\, which should fail the whole match\, shouldn't it?
Well I have to admit its a bit murky\, but I think the match should succeed. (*COMMIT) relates to how perl moves the start point on failure. This is an anchored match\, so it effectively has a (*COMMIT) at the very start anyway\, and the match does not fail at the given start point\, it succeeds. I think you are confusing atomic matches and (*COMMIT). Change that to /\A(?:.(*COMMIT))*+c/ and it behaves as you say.
From the docs: It's a zero-width pattern similar to "(*SKIP)"\, except that when backtracked into on failure it causes the match to fail outright. No further attempts to find a valid match by advancing the start pointer will occur again.
In this case technically we never backtracked into the COMMIT\, and we certainly did not attempt to advance the start pointer. So I don't think the commit should have fired. But I admit the other interpretation is not unreasonable. We have never really specified how quantifiers and verbs should interact\, and I could go along with an interpretation that says we are doing it wrong. Might need Larry to rule on it tho\, this was copied from Perl6.
Yves
p5pRT
commented
5 years ago The RT System itself - Status changed from 'new' to 'open'
p5pRT
commented
5 years ago On Tue\, 2 Jul 2019\, yves orton via RT wrote:
Well I have to admit its a bit murky\, but I think the match should succeed. (*COMMIT) relates to how perl moves the start point on failure. This is an anchored match\, so it effectively has a (*COMMIT) at the very start anyway\, and the match does not fail at the given start point\, it succeeds.
Hmm. I can now see that there is an alternative interpretation of (*COMMIT)\, which is "If (*COMMIT) is passed during a match attempt\, carry on as normal\, but if the overall match fails\, do not advance the start pointer." However\, under that interpretation\, this match should succeed:
$ perl -e 'if (abcd =~ /.*(*COMMIT)c/) { print "yes >$&\<\n"; } else { print "no \n"; }' no
Incidentally\, the \A at the start of my previous example is not relevant. Leaving it out makes no difference. So the question is why are these two different?
/.*(*COMMIT)c/ does not match "abcd" /(?:.(*COMMIT))*c/ does match "abcd" (matches "abc")
Under your interpretation\, shouldn't the first one match? After all\, it can find a match without advancing the starting point.
From the docs: It's a zero-width pattern similar to "(*SKIP)"\, except that when backtracked into on failure it causes the match to fail outright. No further attempts to find a valid match by advancing the start pointer will occur again.
In this case technically we never backtracked into the COMMIT\,
As an outsider looking at Perl\, I don't understand that. I thought that passing (*COMMIT) always established a backtrack point\, so (unless it was inside an atomic group) a subsequent failure must then backtrack onto it. How has this not happened?
We have never really specified how quantifiers and verbs should interact\, and I could go along with an interpretation that says we are doing it wrong. Might need Larry to rule on it tho\, this was copied from Perl6.
I await the ruling!
Regards\, Philip
-- Philip Hazel
p5pRT
commented
5 years ago On Tue\, 2 Jul 2019 at 16:44\, \ph10@​hermes\.cam\.ac\.uk wrote:
On Tue\, 2 Jul 2019\, yves orton via RT wrote:
Well I have to admit its a bit murky\, but I think the match should succeed. (*COMMIT) relates to how perl moves the start point on failure. This is an anchored match\, so it effectively has a (*COMMIT) at the very start anyway\, and the match does not fail at the given start point\, it succeeds.
Hmm. I can now see that there is an alternative interpretation of (*COMMIT)\, which is "If (*COMMIT) is passed during a match attempt\, carry on as normal\, but if the overall match fails\, do not advance the start pointer." However\, under that interpretation\, this match should succeed:
$ perl -e 'if (abcd =~ /.*(*COMMIT)c/) { print "yes >$&\<\n"; } else { print "no \n"; }' no
No\, because this one definitely DOES backtrack into into the COMMIT op. Right after it fails to match 'c'.
Incidentally\, the \A at the start of my previous example is not relevant. Leaving it out makes no difference. So the question is why are these two different?
/.*(*COMMIT)c/ does not match "abcd" /(?:.(*COMMIT))*c/ does match "abcd" (matches "abc")
Because the * is on a group\, the group is rolled back as a group\, so we never backtrack into the COMMIT in a technical sense\, instead we unroll the attempt to match the group as a whole. I am talking purely implementation here. Try add -Mre=debug and you will see what I mean in the two cases.
Under your interpretation\, shouldn't the first one match? After all\, it can find a match without advancing the starting point.
Again no\, because it backtracks into the (*COMMIT). I am not saying this is *right* by the way\, just that it is what is happening.
From the docs: It's a zero-width pattern similar to "(*SKIP)"\, except that when backtracked into on failure it causes the match to fail outright. No further attempts to find a valid match by advancing the start pointer will occur again.
In this case technically we never backtracked into the COMMIT\,
As an outsider looking at Perl\, I don't understand that. I thought that passing (*COMMIT) always established a backtrack point\, so (unless it was inside an atomic group) a subsequent failure must then backtrack onto it. How has this not happened?
Because (?:...)* is compiled into a construct called CURLYM which does the work of unrolling the group\, and we never actually enter the COMMIT regop via backtracking. You could argue it is an optimisation gone wrong. You could also argue that a commit in a quantifier doesnt make sense.
The problem I think is that there is a clash between the purist DFA interpretation of a star quantifier\, and the backtracking that we actually use.
Lets just take a simple case:
"aaab"=~/a*x/
The rules dont really specify if we ever actually "fail to match" with a star quantifier.
You can say that "a*" matches the first three a's and then fails on the b and backtracks by one then allowing the x to match. And if you did you likely would match what actually happens in the regex engine. Roughly speaking this would be backtracking interpretation.
BUT
There is another equally valid interpretation that a* matches ONLY the first three a's and never even tries to match 'a' to 'x'. This would not match how the engine actually works in perl\, but is perfectly consistent with a purist DFA for the regex.
IOW\, we would have a state machine like this:
/ Input state | a | x | anything-else 1 | 1 | 2 | 3 2 | ACCEPT 3 | FAIL
This machine would never backtrack on "aaab"=~/a*x/;
So at a certain level it doesn't surprise me that we show both behaviors\, they both are reasonable in themselves. Its just they aren't consistent with each other....
Yves
p5pRT
commented
5 years ago On Tue\, 2 Jul 2019\, yves orton via RT wrote:
$ perl -e 'if (abcd =~ /.*(*COMMIT)c/) { print "yes >$&\<\n"; } else { print "no \n"; }' no
No\, because this one definitely DOES backtrack into into the COMMIT op. Right after it fails to match 'c'.
Yves\,
Thanks for taking the time to explain all this to me. So if /.*(*COMMIT)c/ backtracks onto the (*COMMIT)\, presumably /(.*(*COMMIT))c/ would also backtrack onto (*COMMIT) (it does). Seems surprising that /(.(*COMMIT))*c/ doesn't\, but hey\, what do I know? (This all actually arose from a PCRE user's question\, incidentally. I'm not devious enough to think of putting (*COMMIT) inside a quantifier. :-)
Because the * is on a group\, the group is rolled back as a group\, so we never backtrack into the COMMIT in a technical sense\, instead we unroll the attempt to match the group as a whole.
But surely there can be backtracks into other things in a group? How about something like "aaaab" ~ /(a+)+a/ which\, as I understand it\, will swallow all the a's in the first match of the group\, fail to match a second attempt at the group so go on to try the final "a"\, then fail again\, and so must backtrack into the group in order to match. But of course this is all implementation dependent\, and subject to optimizations as well.
I am talking purely implementation here. Try add -Mre=debug and you will see what I mean in the two cases.
I've tried to avoid learning anything about Perl internals :-) but thanks for that. I may have to...
Again no\, because it backtracks into the (*COMMIT). I am not saying this is *right* by the way\, just that it is what is happening.
Understood.
Because (?:...)* is compiled into a construct called CURLYM which does the work of unrolling the group\, and we never actually enter the COMMIT regop via backtracking. You could argue it is an optimisation gone wrong. You could also argue that a commit in a quantifier doesnt make sense.
Indeed! These are are very pathological examples.
So at a certain level it doesn't surprise me that we show both behaviors\, they both are reasonable in themselves. Its just they aren't consistent with each other....
Indeed again.
Regards\, Philip
-- Philip Hazel
Migrated from rt.perl.org#134254 (status was 'open')
Searchable as RT134254$