Bug #125105 for Regexp-Grammars: Segmentation fault at 2 GB of memeory

> Queue: Regexp-Grammars > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=125105 > > > Hi Alex, > > I agree that it would certainly be better if non-backtracking repetitions > could be > applied to subrule calls. It would indeed reduce the parser's memory > footprint > in some cases. > > Unfortunately, I am not aware of any way to make something like <subrule>*+ > work correctly. > > There is a long-standing issue with how in-regex variable localizations are > implemented > which means that they do not unwind correctly when a call to an independent > subpattern is part of a non-backtracking repetition. And because R::G uses > localized variables to implement its parse-tree stack, this issue makes it > impossible to implement <subrule>*+ properly. > > I raised this issue with P5P several years ago but have been unable to > convince > them to change the current behaviour in such a way as to ensure that > repeated > localizations unwind correctly.

> Queue: Regexp-Grammars > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=125105 > > > Yves, > > Here is the simplest test suite I could devise that demonstrates > the problem. In my testing, it fails identically under every release > from 5.10 to 5.26

> > -----cut----------cut----------cut----------cut----------cut----------cut----------cut----- > > > #! /usr/bin/env perl > use warnings; > > # > # The pattern matching code in each pair of subtests is identical, > # except that the second subtest replaces a backtracking quantifier > # with its non-backtracking equivalent. > # > # In each case, the non-backtracking version should pass, but it fails > # > > use Test::More; > plan tests => 12; > > our $count; > > ################ > > subtest 'Backtracking *' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A)* # This quantifier is backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking *+' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A)*+ # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################ > > subtest 'Backtracking (?:*)' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?: (?&A)* ) # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking (?>*)' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?> (?&A)* ) # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################ > > subtest 'Backtracking +' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A)+ # This quantifier is backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking ++' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A)++ # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################ > > subtest 'Backtracking {3}' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A){3} # This quantifier is backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking {3}+' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A){3}+ # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################ > > subtest 'Backtracking {1,3}' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A){1,3} # This quantifier is backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking {1,3}+' => sub { > $count = 0; > ok "aaa" =~ m{ > \A > (?&A){1,3}+ # This quantifier is non-backtracking > \z > (?{ is $count, 3 => "Found 3 a's" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################ > > subtest 'Backtracking ?' => sub { > $count = 0; > ok "a" =~ m{ > \A > (?&A)? # This quantifier is backtracking > \z > (?{ is $count, 1 => "Found 1 a" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > subtest 'Non-backtracking ?+' => sub { > $count = 0; > ok "a" =~ m{ > \A > (?&A)?+ # This quantifier is non-backtracking > \z > (?{ is $count, 1 => "Found 1 a" }) > > (?(DEFINE) (?<A> a (?{ local $count = $count + 1 }) > ) ) > }x => 'Regex matched'; > }; > > ################

> > No problem at all. Thanks for your interest in the problem! > > > > Very well. Hope you are likewise. :-) > > Damian

> Hi Alex, > > > That's the huge mystery here. I simply don't know. > > You reported falling over at 2GB, which strongly implies > a serious memory leak, not a huge object tree. > > Each node object is likely to be less that 1kB, so that would > imply a tree of well over a million nodes, which is absurd. > > Optimizing the tree would, of course, reduce the memory usage, > but I doubt it will solve the problem, because I doubt a big tree > is causing the problem in the first place. > > If you can send me a self-contained example of the grammar > and the data that causing this issue, I'll take a look at it > myself and see if I can see anything obviously amiss. > > But it's more likely, I fear, that we're tripping some internal > issue that's resulting in a huge memory leak. So I can't promise > I'll be able to solve this for you. > > Damian