>From 68b71d7ef7655c014763a1e8cb36892cbef8b4bb Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Fri, 18 Sep 2026 13:14:27 +0000 Subject: [PATCH 06/25] regex: avoid unnecessary tags on some union nodes A union with submatch needs extra tags so leftmost is selected if there are otherwise equal matches. The num_submatches > 0 condition was meant to check for the subs, but that includes the sub of the union itself so true for (a|b), not just for a|(b). (a|a)(a|a)(a|a)(a|a) used 12 tags before now 4 this affected top level [ab] too (implicit sub). the extra tags were processed during regexec (but not doing anything useful). Fixed by using n->num_submatches - (n->submatch_id >= 0) > 0, and made the stack use conditional. --- src/regex/regcomp.c | 24 +++++++++++++++--------- 1 file changed, 15 insertions(+), 9 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index 9b4b8f16..04de3a3e 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1430,6 +1430,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, tre_ast_node_t *right = uni->right; int left_tag; int right_tag; + int added_tags = regset[0] >= 0; + int child_subs = node->num_submatches - (node->submatch_id>=0); if (regset[0] >= 0) { @@ -1443,10 +1445,15 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, } /* After processing right child. */ - STACK_PUSHX(stack, int, right_tag); - STACK_PUSHX(stack, int, left_tag); + if (child_subs) + { + /* Add tags to children with sub expr. */ + STACK_PUSHX(stack, int, right_tag); + STACK_PUSHX(stack, int, left_tag); + added_tags += 2; + } STACK_PUSHX(stack, voidptr, regset); - STACK_PUSHX(stack, int, regset[0] >= 0); + STACK_PUSHX(stack, int, added_tags); STACK_PUSHX(stack, voidptr, node); STACK_PUSHX(stack, voidptr, right); STACK_PUSHX(stack, voidptr, left); @@ -1489,7 +1496,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, next_tag++; } - if (node->num_submatches > 0) + if (child_subs) { /* The next two tags are reserved for markers. */ next_tag++; @@ -1568,12 +1575,9 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, if (first_pass) { node->num_tags = ((tre_union_t *)node->obj)->left->num_tags - + ((tre_union_t *)node->obj)->right->num_tags + added_tags - + ((node->num_submatches > 0) ? 2 : 0); + + ((tre_union_t *)node->obj)->right->num_tags + added_tags; } regset = tre_stack_pop_voidptr(stack); - tag_left = tre_stack_pop_int(stack); - tag_right = tre_stack_pop_int(stack); /* Add tags after both children, the left child gets a smaller tag than the right child. This guarantees that we prefer @@ -1584,8 +1588,10 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, is used. If so, use tre_add_tag_left (putting the tag before the child as opposed after the child) and throw away tre_add_tag_right. */ - if (node->num_submatches > 0) + if (added_tags >= 2) { + tag_left = tre_stack_pop_int(stack); + tag_right = tre_stack_pop_int(stack); if (!first_pass) { status = tre_add_tag_right(mem, left, tag_left); -- 2.52.0