>From 652ad652648e57e742e6c181a6be857ebfe0e1ad Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Sat, 10 Oct 2026 23:19:33 +0000 Subject: [PATCH 15/25] regex: fix large tnfa size for brackets n literals in a bracket share "position" so in the tnfa they can be a single state with m incoming transitions instead of n states and n*m transitions. this is a reasonable optimization e.g. in tre [aaaaaa]* (a|a|a|a|a|a)* the former requires 2(n+1) transitions, while the latter (n+1)^2 (for n "a"). however the implementation was half-hearted and allocated similarly large table for both. (and expand [..]{k} introduced state gaps, firstpos grew n long instead of 1 and initial transitions had repeat entries). this is a minimal fix that tries to get most of the benefits of the existing position sharing design. before -> after state and transition counts (allocation size): states trans states trans [aaa..]* 2, ~n^2 -> 2, ~2n [aaa..]{k} ~k*n, ~k*n*n -> ~k*n, ~2*k*n (ideal: k, k*n) [aaa..][bbb..] 3, ~n*m -> 3, ~n+m --- src/regex/regcomp.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index 87662cfe..f9830a44 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -2054,6 +2054,11 @@ tre_set_one(tre_mem_t mem, int position, int code_min, int code_max, return new_set; } +static int shared_pos(tre_pos_and_tags_t *s1, tre_pos_and_tags_t *s2) +{ + return s1[0].position == s2[0].position && s1[0].position >= 0; +} + static tre_pos_and_tags_t * tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2, int *tags, int assertions) @@ -2347,7 +2352,13 @@ tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree) { tre_union_t *uni = (tre_union_t *)node->obj; node->nullable = uni->left->nullable || uni->right->nullable; - node->firstpos = tre_set_union(mem, uni->left->firstpos, + if (shared_pos(uni->left->firstpos, uni->right->firstpos)) + /* brackets are unions of literals with the same position, + * positions differ otherwise. in a bracket all nodes can + * use the same firstpos, literal details don't matter. */ + node->firstpos = uni->left->firstpos; + else + node->firstpos = tre_set_union(mem, uni->left->firstpos, uni->right->firstpos, NULL, 0); if (!node->firstpos) return REG_ESPACE; -- 2.52.0