Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

backtracking in LTM alternation in ratchet mode fails #3704

Open
p6rt opened this issue Feb 25, 2015 · 5 comments
Open

backtracking in LTM alternation in ratchet mode fails #3704

p6rt opened this issue Feb 25, 2015 · 5 comments
Labels
regex Regular expressions, pattern matching, user-defined grammars, tokens and rules

Comments

@p6rt
Copy link

p6rt commented Feb 25, 2015

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

Searchable as RT123934$

@p6rt
Copy link
Author

p6rt commented Feb 25, 2015

From beasley@web.de

say "asdfEnd" ~~ /​:ratchet [ xyz | .+! ] End /;
=> Nil

I would expect this to match.

I also tested (and work as I'd expect)​:
say "asdfEnd" ~~ / [ xyz | .+ ] End /;
=>「asdfEnd」
say "asdfEnd" ~~ /​:ratchet [ xyz || .+! ] End /;
=> 「asdfEnd」

@p6rt
Copy link
Author

p6rt commented Apr 20, 2016

From beasley@web.de

As expressed by perlpilot++ and some others, having

say "asdfEnd" ~~ /​:ratchet [ xyz | .+! ] End /;
say "asdfEnd" ~~ /​:ratchet [ xyz || .+! ] End /;
say "asdfEnd" ~~ /​:ratchet [ .+! ] End /;

all fail might also be a way to harmonize the behavior.

@p6rt
Copy link
Author

p6rt commented May 21, 2016

From beasley@web.de

(I tried adding this comment about a month ago, but failed hard. Thus another
try.)

As expressed by perlpilot++ and some others, having

say "asdfEnd" ~~ /​:ratchet [ xyz | .+! ] End /;
say "asdfEnd" ~~ /​:ratchet [ xyz || .+! ] End /;
say "asdfEnd" ~~ /​:ratchet [ .+! ] End /;

all fail might also be a way to harmonize the behavior.

@p6rt
Copy link
Author

p6rt commented May 21, 2016

From @smls

The way I understand it, following S02 strictly should mean the first two should fail, but the third one should match.

Think of the regex as an expression made up of nested operations.

1) In the case of /​:r [ xyz | .+! ] End/, the last operation before the "End" is an alternation. The :ratchet is supposed to¹ prevent backtracking into alternations, thus this should fail.

2) In the case of /​:r [ xyz || .+! ] End/, the same reasoning applies - except if the phrasing¹ in S05 is imprecise and it actually only meant for `|` alternations to be affected by :ratchet but not `||` alternations.

3) In the case of /​:r [ .+! ] End /, the last operation before the "End" is the + quantifier. (The brackets are not an operator - they only disambiguate precedence, like parens do in normal Perl 6 code.)
But this + operation is un-ratcheted by the ! modifier, so it can be backtracked into if the "End" does not match. So this regex should match.

If this interpretation is correct, it would mean that the actual bug is not that the `|` version fails to backtrack, but that the `||` version does backtrack when it shouldn't.


¹⁾ See this paragraph <http://design.perl6.org/S05.html#line_621> in S05 which explicitly mentions alternations.

@p6rt
Copy link
Author

p6rt commented May 21, 2016

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

@p6rt p6rt added the regex Regular expressions, pattern matching, user-defined grammars, tokens and rules label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
regex Regular expressions, pattern matching, user-defined grammars, tokens and rules
Projects
None yet
Development

No branches or pull requests

1 participant