>From 37551520a6ecaf91e131aeb091c62cdc0d4a6f34 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Fri, 18 Sep 2026 20:16:22 +0000 Subject: [PATCH 25/25] regex: change {n,m} expand in regcomp expand x{0,3} as (x(x(x)?)?)? instead of (|x(|x(|x))), the former is 2n-1 ast nodes, the latter is 3n-1. so this saves memory. this changes behaviour in case of x that matches an empty string since |(a?) matches "" with (0,0)(-1,-1) offsets, but (a?)? with (0,0)(0,0), in | the left side is preferred, in ? empty is preferred to no match. (a?){0,2} against "" was (0,0)(-1,-1) now (0,0)(0,0) good for posix (a?){1,2} against "a" was (0,1)(0,1) now (0,1)(1,1) bad for posix so it's not a clear win, but posix conform repetition is expensive to implement. the idea is from upstream https://github.com/laurikari/tre/commit/4c045e442b88c2802133c158e3a5cc7f33f7d45f --- src/regex/regcomp.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index a6ae7877..60879260 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1960,7 +1960,7 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, { for (j = iter->min; j < iter->max; j++) { - tre_ast_node_t *tmp, *copy; + tre_ast_node_t *copy; pos_add_save = pos_add; status = tre_copy_ast(mem, stack, iter->arg, 0, &pos_add, NULL, ©, &max_pos); @@ -1972,10 +1972,7 @@ tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, seq2 = copy; if (seq2 == NULL) return REG_ESPACE; - tmp = tre_ast_new_literal(mem, EMPTY, -1, -1); - if (tmp == NULL) - return REG_ESPACE; - seq2 = tre_ast_new_union(mem, tmp, seq2); + seq2 = tre_ast_new_iter(mem, seq2, 0, 1, 0); if (seq2 == NULL) return REG_ESPACE; } -- 2.52.0