[Support] Fix alternation support in backreferences (PR60073)
authorNikita Popov <npopov@redhat.com>
Mon, 16 Jan 2023 14:03:35 +0000 (15:03 +0100)
committerNikita Popov <npopov@redhat.com>
Tue, 17 Jan 2023 08:58:10 +0000 (09:58 +0100)
commitbb5e26dad9512e5d60a0462edf0d07044d21e22e
tree900be7074ce5ae32c049e79edcb531ed4b2b1df7
parent951cf656b2faaf6fc0baa867293c0cb0ab131951
[Support] Fix alternation support in backreferences (PR60073)

backref() always performs a full match on the remaining string,
and as such also needs to be matched against the whole remaining
strip. For alternations, the match was performed against just the
sub-strip for one alternative, which would of course fail to match
the whole string.

This can be done by skipping the part of the strip between OOR1
and O_CH, so that only the first alternative in the strip is
matched, and the remaining ones are skipped. Indeed, the necessary
OOR1 skipping code was already implemented in the easy-path of
backref(), so this is clearly how it was supposed to work.

However, there were two bugs: First, under this scheme we should
be passing the stop point of the original strip, not just the
alternative sub-strip. Second, while skipping for OOR1 was
implemented, handling for O_CH was missing. This would occur when
the last alternative matches, as O_CH is preceded by an implicit
OOR1 only.

Fixes https://github.com/llvm/llvm-project/issues/60073.
llvm/lib/Support/regengine.inc
llvm/unittests/Support/RegexTest.cpp