Re: Regex: A case where the longest match isn't being found

[Dale R. Worley]

"Dan Bornstein" <danfuzz@murtbo.com> writes:
> I found a case where the regex evaluator doesn't seem to be finding
> the longest possible match for a given expression. The expression
> works as expected on an older version of Bash (3.2.57(1)-release
> (arm64-apple-darwin22)).
>
> Here's the regex: ^(\$\'([^\']|\\\')*\')(.*)$

This would be *much* easier to understand if you'd rewritten it into a
test case where none of the characters that the regex was consuming were
regex metacharacters, e.g. letters.  That would make everything far
easier to read.

> (FWIW, this is meant to capture a string that looks like an ANSI-style
> literal string, plus a "rest" for further processing.)

*If* I read the regex correctly, it must match the entire string, ^...$.
Then it matches in two parenthesized strings.
The second string is .*, as you san "the rest for further processing".
The first string is $, followed by a single ', followed by any number
of:
- one character that is not '
- the character \ followed by '
followed by a single '

Note that this regex does not give the matcher any leeway; it either
matches a string or not, and if it matches, it matches in only one way.
This isn't a question of whether it is choosing "the longest match".

*If* I read the subject string correctly, it is

    $'foo\' x' bar

(with two internal spaces and none at the beginning or end).

So it does seem to say that the first parenthesized string should match

    $'foo\' x'

> For example, run this:
>
> [[ $'$\'foo\\\' x\' bar' =~ ^(\$\'([^\']|\\\')*\')(.*)$ ]] && echo 
> "${BASH_REMATCH[1]}"
>
> On v5.2, this prints: $'foo\'
> On v3.2.57, this prints: $'foo\' x'

Executing this suggests that the subject string is being interpreted as
intended:

$ echo -E $'$\'foo\\\' x\' bar'
$'foo\' x' bar
$

OK, here's the problem.  Compare these executions, which have an
additional \\ inserted in the character class specification [...]:

$ [[ $'$\'foo\\\' x\' bar' =~ ^(\$\'([^\']|\\\')*\')(.*)$ ]] && echo -E 
"${BASH_REMATCH[1]}"
$'foo\'
$ [[ $'$\'foo\\\' x\' bar' =~ ^(\$\'([^\']|\\\')*\')(.*)$ ]] && echo -E 
"${BASH_REMATCH[3]}"
 x' bar
$ [[ $'$\'foo\\\' x\' bar' =~ ^(\$\'([^\\\']|\\\')*\')(.*)$ ]] && echo -E 
"${BASH_REMATCH[1]}"
$'foo\' x'
$ [[ $'$\'foo\\\' x\' bar' =~ ^(\$\'([^\\\']|\\\')*\')(.*)$ ]] && echo -E 
"${BASH_REMATCH[3]}"
 bar
$

What you wrote was [^\'].  The backslash is consumed while the regexp is
being read and is interpreted as causing the succeeding ' to be
non-magic.  Of course, that ' isn't magic in that context.  But it means
that the character class includes all non-newline characters other than
'.  Specifically, that *includes* backslash.  So the regexp matcher sees
the first alternative of the | as matching an isolated backslash.

That means that when the matcher is processing the iterator *, at that
iteration, it will first match the character class, which matches, then
attempt to iterate further (which will fail, exiting the iterator),
match the closing ' (which will succeed), match the (.*) (which will
succeed), match the $ (which will succeed), then return that match.

Now, if the part of the pattern following the iterator failed, the
matcher would backtrack until it attempted the *second* branch of the
alternative in the final iteration, which would *also* match, but would
leave the matcher lookng at " x'...", which would allow it to continue
iterating.

The complication is that if you'd written [^\\\'], the matcher would
have only one way to match any subject string, and the matching process
could be ignored.  But with [^\'], there are multiple ways to match, and
you get the first one the matcher finds.  Specifically, ?, +, and * are
"greedy", they start by matching as many copies of their sub-pattern as
they are allowed, and if backtracked into, reduce the number of
iterations one at a time as far as they're allowed.  Alternations,
though, start by attempting the first alternative, then the second,
etc., and if backtracked into after succeeding with one alternative, try
the next one.  Ugh, that's a rough outline; it's not quite that simple.

I suspect the difference between the versions is how the regexp is
unquoted while it is being read, with version 3 interpreting [^\'] as
"character class excluding newline, backslash, and quote" and version 5
interpreting it as "character class excluding newline and quote".

Dale