slre: drop wrong "anchored" optimization
authorRasmus Villemoes <ravi@prevas.dk>
Tue, 13 May 2025 08:40:26 +0000 (10:40 +0200)
committerTom Rini <trini@konsulko.com>
Thu, 29 May 2025 14:25:18 +0000 (08:25 -0600)
commit19b3e24083eb0b1b5299e689d0bc5f1a6c4ebdcd
tree2625148ba823179a0ef72fb545cfce8e6f9c83d5
parentced883d92c0568cdb15b5b67106c29a4623b19d8
slre: drop wrong "anchored" optimization

The regex '^a|b' means "does the string start with a, or does it have
a b anywhere", not "does the string start with a or b" (the latter
should be spelled '^[ab]' or '^(a|b)'). It should match exactly the
same strings as 'b|^a'. But the current implementation hard-codes an
assumption that when the regex starts with a ^, the whole regex must
match from the beginning, i.e. it only attempts at offset 0.

It really should be completely symmetrical to 'b|c$' ("does it have a
b anywhere or end with c?"), which is treated correctly.

Another quirk is that currently the regex 'x*$', which should match
all strings (because it just means "does the string end
with 0 or more x'es"), does not, because in the unanchored case we
never attempt to match at ofs==len. In the anchored case, '^x*$', this
works correctly and matches exactly strings (including the empty
string) consisting entirely of x'es.

Fix both of these issues by dropping all use of the slre->anchored
member and always test at all possible offsets. If the regex does have
a ^ somewhere (including after a | branch character), that is
correctly handled by the match engine by only matching when *ofs is 0.

Reviewed-by: Simon Glass <sjg@chromium.org>
Signed-off-by: Rasmus Villemoes <ravi@prevas.dk>
include/slre.h
lib/slre.c