What regex can match arbitrary-length quoted string?

jimav has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: What regex can match arbitrary-length quoted string? by dave_the_m (Monsignor) on Sep 28, 2017 at 22:47 UTC
The regex engine doesn't recurse these days, but the error message hasn't changed. It does still have to store a backtracking state for each iteration, and there's still a hard limit of 32768-ish backtrack states hard-coded in for this op type, which aught to be changed at some point. Dave.	[reply]
Re: What regex can match arbitrary-length quoted string? by AnomalousMonk (Archbishop) on Sep 29, 2017 at 02:51 UTC
Here's an example based on the pre-5.10 `(?>pattern)` atomic grouping. It should be fairly easily convertable to use the `+` possessive quantifier modifier. (I'm using `'x'` in place of `'"'` because Windose command line and my REPL don't like double-quotes, but you get the idea.) c:\@Work\Perl\monks>perl -wMstrict -le "print 'perl version: ', $]; print '------------'; ;; my $non_x_or_escaped = qr{ (?> [^x\\]{0,32766}) (?> (?> \\.){0,32766} (?> [^x\\]{0,32766})) }xms; ;; my $s = 'zx' . ('\x' x 1_000_000) . 'xz'; print 'length of test string: ', length $s; print substr($s, 0, 20), ' ... ', substr($s, -20); ;; print 'MATCHED' if $s =~ m{ (x (?> $non_x_or_escaped)* x) }xms; my $captured = $1; print 'length captured: ', length $captured; print substr($captured, 0, 20), ' ... ', substr($captured, -20); print '------------'; ;; $s = 'zx' . ('p' x 1_000_000) . '\x' . ('q' x 1_000_000) . 'xz'; print 'length of test string: ', length $s; print substr($s, 0, 20), ' ... ', substr($s, -20); ;; print 'MATCHED' if $s =~ m{ (x (?> $non_x_or_escaped)* x) }xms; $captured = $1; print 'length captured: ', length $captured; print substr($captured, 0, 20), ' ... ', substr($captured, -20); " perl version: 5.008009 ------------ length of test string: 2000004 zx\x\x\x\x\x\x\x\x\x ... \x\x\x\x\x\x\x\x\xxz MATCHED length captured: 2000002 x\x\x\x\x\x\x\x\x\x\ ... x\x\x\x\x\x\x\x\x\xx ------------ length of test string: 2000006 zxpppppppppppppppppp ... qqqqqqqqqqqqqqqqqqxz MATCHED length captured: 2000004 xppppppppppppppppppp ... qqqqqqqqqqqqqqqqqqqx [download] Give a man a fish: `<%-{-{-{-<`	[reply] [d/l] [select]
Re: What regex can match arbitrary-length quoted string? by Anonymous Monk on Sep 28, 2017 at 22:48 UTC
Perl regex engine tries to avoid (endless) backtracking and/or recursion as much as possible. It also has implementation limits or kludges (depending on how you see it). The repeat count(er) seems to be a 16-bit value. Indeed, if you specify a `{1,77777}` qualifier, you'd see an error `Quantifier in {,} bigger than 32766 in regex;` ... The warning message ("recursion limit exceeded") itself is misleading. There is no recursion involved in your regex, only iteration. The message is the same in either case. To work around the limitation, you could double the repeat qualifiers, `(?: (?: ... )+ )*+` or similar. Explicit bound `{1,32000}` is probably better as it gets rid of the warning, as well.	[reply] [d/l] [select]
Re: What regex can match arbitrary-length quoted string? by QM (Parson) on Sep 29, 2017 at 09:48 UTC
It seems the `\\.`, which captures the `\"` in the target, is not possessive, and is causing the error. The following works in the given case. Are there cases where it fails? `print "NOT MATCHED!\n" unless /^ " (?: [^"\\]++ \| (?: \\. )++ )+ " /x ;` [download] Update:* Playing around more, it seems that the possessives are not needed on the internals, but only that the `\\.` should have a quantifier: `print "NOT MATCHED!\n" unless /^ " (?: [^"\\]+ \| (?: \\. )+ )*+ " /x ;` [download] This works on a string of length 100 million, in <2s on my machine. (I didn't try any longer strings.) -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l] [select]
Re^2: What regex can match arbitrary-length quoted string? by QM (Parson) on Sep 29, 2017 at 13:26 UTC
Assuming this is correct... Is this a simple omission or transcription error in perlre? Besides the entry in perlre, where else is the original solution given? Should it be updated or annotated? -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l]
Re^2: What regex can match arbitrary-length quoted string? by Anonymous Monk on Sep 29, 2017 at 13:51 UTC
Your update doesn't solve the problem. `$_ = '"' . ('x\"' x 100000) . '"'; print "NOT MATCHED!\n" unless /^ " (?: [^"\\]+ \| (?: \\. )+ )*+ " /x; __END__ Complex regular subexpression recursion limit (32766) exceeded at foo +line 4. NOT MATCHED!` [download]	[reply] [d/l]
Re^3: What regex can match arbitrary-length quoted string? by QM (Parson) on Oct 03, 2017 at 10:46 UTC
Hmmm...I get "NOT MATCHED!", but no error message. But there are other inconsistencies. Putting several into a single script: #!/usr/bin/perl use strict; use warnings; our $quotes = '"' . ('\"' x 10000000) . '"'; print "Length of string is ", length($quotes), "\n"; our @qr; push @qr, qr/^ " (?: [^"\\]++ \| \\. )+ " /x ; push @qr, qr/^ " (?: [^"\\]++ \| (?: \\. )++ )+ " /x ; push @qr, qr/^ " (?: [^"\\]+ \| (?: \\. )+ )+ " /x ; for my $i (0..$#qr) { print "$i) $qr[$i] ==> "; print "NOT " unless $quotes =~ $qr[$i]; print "MATCHED!\n"; } __END__ Length of string is 20000002 Complex regular subexpression recursion limit (32766) exceeded at ./pm +1200316.pl line 16. 0) (?^x:^ " (?: [^"\\]++ \| \\. )+ " ) ==> NOT MATCHED! 1) (?^x:^ " (?: [^"\\]++ \| (?: \\. )++ )+ " ) ==> MATCHED! 2) (?^x:^ " (?: [^"\\]+ \| (?: \\. )+ )+ " ) ==> MATCHED! [download] `perl -v This is perl 5, version 22, subversion 1 (v5.22.1) built for x86_64-li +nux-gnu-thread-multi (with 58 registered patches, see perl -V for more detail) Copyright 1987-2015, Larry Wall` [download] -QM -- Quantum Mechanics: The dreams stuff is made of	[reply] [d/l] [select]
Re^3: What regex can match arbitrary-length quoted string? by jimav (Sexton) on Aug 26, 2023 at 00:29 UTC
Typo there: `$_ = '"' . ('x\"' x 100000) . '"';` presumably should be `$_ = '"' . ('\\"' x 100000) . '"';` (Yes, it sometimes takes me a long time to read my email...)	[reply] [d/l] [select]


Clear questions and runnable code get the best and fastest answer
	PerlMonks