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

Capturing separator (like /something % (.+?)/ ) spews out backtracking #4279

Closed
p6rt opened this issue May 30, 2015 · 6 comments
Closed

Capturing separator (like /something % (.+?)/ ) spews out backtracking #4279

p6rt opened this issue May 30, 2015 · 6 comments

Comments

@p6rt
Copy link

p6rt commented May 30, 2015

Migrated from rt.perl.org#125285 (status was 'resolved')

Searchable as RT125285$

@p6rt
Copy link
Author

p6rt commented May 30, 2015

From @AlexDaniel

This command​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %% (.+?)
$/"

Outputs this​:
「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 」
1 => 「 f」
1 => 「 fo」
1 => 「 foo」
1 => 「 foo 」
0 => 「rule2」
1 => 「 」
1 => 「 b」
1 => 「 ba」
1 => 「 bar」

I can't see any reason why these partial matches should appear in the match
object. I expected this​:

「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 foo 」
0 => 「rule2」
1 => 「 bar」

@p6rt
Copy link
Author

p6rt commented Jun 6, 2015

From @AlexDaniel

I works this way though​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %%
$<baz>=[.+?] $/"

「rule1 foo rule2 bar」
0 => 「rule1」
baz => 「 foo 」
0 => 「rule2」
baz => 「 bar」

Change [] to () and it will break the same way.

On Sat, May 30, 2015 at 3​:05 AM, perl6 via RT <perl6-bugs-followup@​perl.org>
wrote​:

Greetings,

This message has been automatically generated in response to the
creation of a trouble ticket regarding​:
"Capturing separator (like /something % (.+?)/ ) spews out
backtracking",
a summary of which appears below.

There is no need to reply to this message right now. Your ticket has been
assigned an ID of [perl #​125285].

Please include the string​:

     \[perl #&#8203;125285\]

in the subject line of all future correspondence about this issue. To do
so,
you may reply to this message.

                    Thank you,
                    perl6\-bugs\-followup@&#8203;perl\.org

-------------------------------------------------------------------------
This command​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %% (.+?)
$/"

Outputs this​:
「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 」
1 => 「 f」
1 => 「 fo」
1 => 「 foo」
1 => 「 foo 」
0 => 「rule2」
1 => 「 」
1 => 「 b」
1 => 「 ba」
1 => 「 bar」

I can't see any reason why these partial matches should appear in the match
object. I expected this​:

「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 foo 」
0 => 「rule2」
1 => 「 bar」

@p6rt
Copy link
Author

p6rt commented Jun 7, 2015

From @labster

[7​:31pm] AlexDaniel​: m​: grammar MyGrammar { regex TOP { ^ [ <foo> <bar> ]+ $ }; regex foo { 'ZZZ' }; regex bar { .*? }; }; my $data = 'ZZZ 123 ZZZ 456'; say MyGrammar.parse($data);
[7​:31pm] camelia​: rakudo-moar c2a57e​: OUTPUT«「ZZZ 123 ZZZ 456」␤ foo => 「ZZZ」␤ bar => 「」␤ bar => 「 」␤ bar => 「 1」␤ bar => 「 12」␤ bar => 「 123」␤ bar => 「 123 」␤ foo => 「ZZZ」␤ bar => 「」␤ bar => 「 」␤ bar => 「 4」␤ bar => 「 45」␤ …»
[7​:31pm] AlexDaniel​: now this is a problem
...
[7​:58pm] AlexDaniel​: m​: grammar MyGrammar { regex TOP { ^ [ <foo> $<bar>=.*? ]+ $ }; regex foo { 'ZZZ' }; }; my $data = 'ZZZ 123 ZZZ 456'; say MyGrammar.parse($data);
[7​:59pm] camelia​: rakudo-moar c2a57e​: OUTPUT«「ZZZ 123 ZZZ 456」␤ foo => 「ZZZ」␤ bar => 「 123 」␤ foo => 「ZZZ」␤ bar => 「 456」␤»

So if you define <bar> inline, you get a single result, but if it's a regex you get multiple, backtracking(?) results.

On Sat Jun 06 14​:54​:18 2015, alex.jakimenko@​gmail.com wrote​:

I works this way though​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %%
$&lt;baz&gt;=[.+?] $/"

「rule1 foo rule2 bar」
0 => 「rule1」
baz => 「 foo 」
0 => 「rule2」
baz => 「 bar」

Change [] to () and it will break the same way.

On Sat, May 30, 2015 at 3​:05 AM, perl6 via RT <perl6-bugs-
followup@​perl.org>
wrote​:

Greetings,

This message has been automatically generated in response to the
creation of a trouble ticket regarding​:
"Capturing separator (like /something % (.+?)/ ) spews out
backtracking",
a summary of which appears below.

There is no need to reply to this message right now. Your ticket has
been
assigned an ID of [perl #​125285].

Please include the string​:

[perl #​125285]

in the subject line of all future correspondence about this issue. To
do
so,
you may reply to this message.

Thank you,
perl6-bugs-followup@​perl.org

-------------------------------------------------------------------------
This command​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %%
(.+?)
$/"

Outputs this​:
「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 」
1 => 「 f」
1 => 「 fo」
1 => 「 foo」
1 => 「 foo 」
0 => 「rule2」
1 => 「 」
1 => 「 b」
1 => 「 ba」
1 => 「 bar」

I can't see any reason why these partial matches should appear in the
match
object. I expected this​:

「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 foo 」
0 => 「rule2」
1 => 「 bar」

@p6rt
Copy link
Author

p6rt commented Nov 11, 2015

From @jnthn

On Fri May 29 17​:05​:32 2015, alex.jakimenko@​gmail.com wrote​:

This command​:
perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %% (.+?)
$/"

Outputs this​:
「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 」
1 => 「 f」
1 => 「 fo」
1 => 「 foo」
1 => 「 foo 」
0 => 「rule2」
1 => 「 」
1 => 「 b」
1 => 「 ba」
1 => 「 bar」

I can't see any reason why these partial matches should appear in the match
object. I expected this​:

「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 foo 」
0 => 「rule2」
1 => 「 bar」

This one took some figuring out... Anyway, fixed now​:

$ perl6 -e "say 'rule1 foo rule2 bar' ~~ /^ ( 'rule1' || 'rule2' )* %% (.+?) $/"
「rule1 foo rule2 bar」
0 => 「rule1」
1 => 「 foo 」
0 => 「rule2」
1 => 「 bar」

Tests in S05-match/capturing-contexts.t.

/jnthn

@p6rt
Copy link
Author

p6rt commented Nov 11, 2015

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

@p6rt
Copy link
Author

p6rt commented Nov 11, 2015

@jnthn - Status changed from 'open' to 'resolved'

@p6rt p6rt closed this as completed Nov 11, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant