[<prev] [day] [month] [year] [list]
Message-ID: <20261015103821.GF3542221@port70.net>
Date: Thu, 15 Oct 2026 12:38:21 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: [PATCH 00/25] regex fixes
i reviewed the tre regcomp code, collected various fixes
when a small change could improve things.
there are design issues as well as implementation issues
in tre so it is not worth doing too many changes (better
to rewrite with modern design), but non-intrusive fixes
can still be useful. (not all patches are equally worthy
of inclusion).
i was mainly testing against a subset of
https://github.com/att/ast/tree/master/src/cmd/re
overall .text size change and final value on x86_64:
-761 19501 regcomp.lo
+433 9087 regexec.lo
correctness:
- tnfa cannot do posix * e.g. (a|ab|abc|bcd|cde|de|e)*
matches abcde as (a)(bcd)(e), (ab)(cde) or (abc)(de)
posix wants the latter, the tnfa engine in regexec can
easily select longest or shortest last match, but (de)
is neither so more complex logic would be needed (this
is about selecting the "right" match and setting the
captured submatch offsets based on that: if there are
multiple leftmost longest matches then the "right" one
is where subpatterns are longest from left to right.
this is expensive to implement with fast worst-case).
- tre gets (x|y) wrong when x,y are patterns that match
empty: tre only considers x and ignores y so e.g.
(a*$|b*)c and (a*$)?c fail to match "c". (can be fixed
by tracking a list of empty matches with assertions
instead of just one, but this would be a big change)
- did not look at multibyte or locale issues (but .* does
not match invalid utf8 except in the C locale and there
is no collation support in brackets).
- fixed easier regcomp and backtrack bugs (beyond these
fixes and the list above i don't know any conformance
issues.)
[5/25] (a){0} vs "" wrong submatch
[7/25] a|($) vs "a" wrong submatch
[9/25] (a(x*)|b)* vs "ab" wrong submatch
[10/25] BRE \(..*.\)\1 vs "ababa" failed
[11/25] BRE \(\(a\)\|b\)\2 vs "b" wrong match
[12/25] BRE \(\(a*\)\2\)b vs "aab" failed
[13/25] BRE \(a*\)\{2\}\1 vs "aaa" wrong match
- fixed safety issues
[1/25] int oflow, held back, being reviewed off-list
[3/25] stack overflow
efficiency:
- tre is slow in the common case and uses a lot of memory
(both at regcomp and regexec time). regcomp memory use
is often dominated by tag lists kept in firstpos/lastpos
during the nfl pass and in the final tnfa (both can be
O(n^3) for n ast nodes), if nfl and tnfa creation was
integrated into one ast traversal then a big portion of
the nfl memory could be released and reused maybe with
a custom allocator. and tag lists are often repeated so
sharing them in tnfa can reduce its size. the ast could
be optimized (before expanding {n,k}) via analysis so
the final tnfa is even smaller for faster regexec.
regexec engine has linear scans that could be sped up
for large tnfa. but these are big projects and still
bounded by tre design choices so redesing maybe better.
- regcomp memory and speed fixes (mainly some bad edge
case behaviour fixes but some common case fixes too.
i had to hold back on a lot of tiny cleanups to keep
this managable, these are lower prio and less clear
cut changes than the correctness ones)
[4/25] memory of ((((..))))
[14/25] speed of . with REG_NEWLINE
[15/25] memory of [aaaaa..]
[16/25] minor speed of deep ast
[17/25] general ~20% memory saving
[20/25] memory of (a*){0,n}
[21/25] memory of ((a|)(b|)(c|)..)*
[22/25] bit of speed and memory
[23/25] speed of ()()()()..
[25/25] memory of x{n,m}
- [25/25] saves memory on x{n,m} expansion, but it
changes user visible behaviour so not ideal. kept
for the record.
Szabolcs Nagy (25):
regex: avoid int overflow in regcomp
regex: remove bracket limit
regex: fix O(n) recursion in regcomp
regex: fix an O(n^2) allocation for nested sub expr
regex: fix a{0} support in regcomp
regex: avoid unnecessary tags on some union nodes
regex: fix a|() recording an unselected empty match
regex: remove unused code from tre_add_tags
regex: fix (a(x*)|b)* incorrect submatch offsets
regex: fix BRE with backref to repetition
regex: fix BRE with backref to no match
regex: fix BRE with backref within a submatch
regex: fix BRE with backref to empty match
regex: optimize . in REG_NEWLINE
regex: fix large tnfa size for brackets
regex: use amortized O(1) stack resize in regcomp
regex: struct changes for memory saving
regex: fix a bad int type choice in regcomp
regex: refactor tag list merging
regex: avoid tag dups
regex: use sorted tags in regcomp
regex: optimize tre_set_union
regex: change regset handling in tre_add_tags
regex: support {,n} as {0,n}
regex: change {n,m} expand in regcomp
src/regex/regcomp.c | 474 ++++++++++++++++++++++----------------------
src/regex/regexec.c | 86 +++++---
src/regex/tre.h | 15 +-
3 files changed, 295 insertions(+), 280 deletions(-)
--
2.52.0
View attachment "0002-regex-remove-bracket-limit.patch" of type "text/x-diff" (759 bytes)
View attachment "0003-regex-fix-O-n-recursion-in-regcomp.patch" of type "text/x-diff" (3718 bytes)
View attachment "0004-regex-fix-an-O-n-2-allocation-for-nested-sub-expr.patch" of type "text/x-diff" (6180 bytes)
View attachment "0005-regex-fix-a-0-support-in-regcomp.patch" of type "text/x-diff" (2272 bytes)
View attachment "0006-regex-avoid-unnecessary-tags-on-some-union-nodes.patch" of type "text/x-diff" (3348 bytes)
View attachment "0007-regex-fix-a-recording-an-unselected-empty-match.patch" of type "text/x-diff" (2168 bytes)
View attachment "0008-regex-remove-unused-code-from-tre_add_tags.patch" of type "text/x-diff" (1922 bytes)
View attachment "0009-regex-fix-a-x-b-incorrect-submatch-offsets.patch" of type "text/x-diff" (6091 bytes)
View attachment "0010-regex-fix-BRE-with-backref-to-repetition.patch" of type "text/x-diff" (1105 bytes)
View attachment "0011-regex-fix-BRE-with-backref-to-no-match.patch" of type "text/x-diff" (975 bytes)
View attachment "0012-regex-fix-BRE-with-backref-within-a-submatch.patch" of type "text/x-diff" (3793 bytes)
View attachment "0013-regex-fix-BRE-with-backref-to-empty-match.patch" of type "text/x-diff" (2168 bytes)
View attachment "0014-regex-optimize-.-in-REG_NEWLINE.patch" of type "text/x-diff" (1357 bytes)
View attachment "0015-regex-fix-large-tnfa-size-for-brackets.patch" of type "text/x-diff" (2527 bytes)
View attachment "0016-regex-use-amortized-O-1-stack-resize-in-regcomp.patch" of type "text/x-diff" (2157 bytes)
View attachment "0017-regex-struct-changes-for-memory-saving.patch" of type "text/x-diff" (2749 bytes)
View attachment "0018-regex-fix-a-bad-int-type-choice-in-regcomp.patch" of type "text/x-diff" (901 bytes)
View attachment "0019-regex-refactor-tag-list-merging.patch" of type "text/x-diff" (2197 bytes)
View attachment "0020-regex-avoid-tag-dups.patch" of type "text/x-diff" (1504 bytes)
View attachment "0021-regex-use-sorted-tags-in-regcomp.patch" of type "text/x-diff" (2510 bytes)
View attachment "0022-regex-optimize-tre_set_union.patch" of type "text/x-diff" (3204 bytes)
View attachment "0023-regex-change-regset-handling-in-tre_add_tags.patch" of type "text/x-diff" (9816 bytes)
View attachment "0024-regex-support-n-as-0-n.patch" of type "text/x-diff" (771 bytes)
View attachment "0025-regex-change-n-m-expand-in-regcomp.patch" of type "text/x-diff" (1869 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
