>From 44db04556d88e0f6aa2f61ea27f22a2596dccbc5 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Mon, 28 Sep 2026 18:18:55 +0000 Subject: [PATCH 09/25] regex: fix (a(x*)|b)* incorrect submatch offsets a repeated pattern may match many times, but only the match offsets for the last rep should be reported. an empty submatch of the last-1 rep was sometimes wrongly reported: (a(x*)|b)* vs "ab" was (0,2)(1,2)(1,1) now (0,2)(1,2)(-1,-1) this was supposed to be handled by the "submatch is within parent" check, but that does not work for a 0 length match on the edge. the fix collects the tree of union end tags as a (parent,left,right) list and only keeps at most one sibling (one with larger offset or the left) and unsets children recursively if a parent is unset to ensure only one branch of a union have tag offsets set. the fix is a bit heavy and relies on regex: fix a|() recording an unselected empty match so submatches in a union branch use the union end tags (or an earlier end tag within the branch) and not a followup tag after the union. the "submatch is within parent" checks are still needed, without them (b|(c*)a)* vs "ab" is not covered (the submatch is not using a union end tag) nor (a(b)?)* vs "aba" (not a union repetition issue). --- src/regex/regcomp.c | 29 +++++++++++++++++++++++++++++ src/regex/regexec.c | 14 ++++++++++++++ src/regex/tre.h | 2 ++ 3 files changed, 45 insertions(+) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index 01084eb1..bf2b457d 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1207,10 +1207,22 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, int next_tag = 1; /* Next tag to use after this one. */ int parent = 0; /* Current node is within this submatch. */ int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */ + int *union_tags; /* List of parent,left,right tags, union child tags only. */ + int *union_stack; /* Union parent tag stack for preparing union_tags. */ + int num_unions = 0; tre_tag_direction_t direction = TRE_TAG_MINIMIZE; if (!first_pass) { + union_tags = xmalloc(sizeof(*union_tags) * 3*tnfa->num_unions); + if (!union_tags) + return REG_ESPACE; + tnfa->union_tags = union_tags; + union_stack = xmalloc(sizeof(*union_stack) * (2*tnfa->num_unions + 1)); + if (!union_stack) + return REG_ESPACE; + union_stack[0] = -1; + tnfa->end_tag = 0; tnfa->minimal_tags[0] = -1; } @@ -1428,6 +1440,11 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, if (child_subs) { /* Add tags to children with sub expr. */ + if (!first_pass) + { + *++union_stack = right_tag; + *++union_stack = left_tag; + } STACK_PUSHX(stack, int, right_tag); STACK_PUSHX(stack, int, left_tag); added_tags += 2; @@ -1444,6 +1461,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, STACK_PUSHX(stack, int, ADDTAGS_RECURSE); /* After processing left child. */ + STACK_PUSHX(stack, int, child_subs && !first_pass); STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT); /* Process left child. */ @@ -1537,6 +1555,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, break; case ADDTAGS_AFTER_UNION_LEFT: + if (tre_stack_pop_int(stack)) + union_stack--; /* Lift the bottom of the `regset' array so that when processing the right operand the items currently in the array are invisible. The original bottom was saved at ADDTAGS_UNION and @@ -1583,7 +1603,12 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, /* use the child end tags for submatches */ tre_purge_regset(regset_right, tnfa, tag_right); tre_purge_regset(regset, tnfa, tag_left); + union_stack--; + union_tags[3*num_unions] = union_stack[0]; + union_tags[3*num_unions+1] = tag_left; + union_tags[3*num_unions+2] = tag_right; } + num_unions++; num_tags += 2; regset[0] = -1; } @@ -1600,6 +1625,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, if (!first_pass) tre_purge_regset(regset, tnfa, tag); + if (!first_pass) + xfree(union_stack); if (!first_pass && minimal_tag >= 0) { @@ -1616,6 +1643,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, tnfa->end_tag = num_tags; tnfa->num_tags = num_tags; tnfa->num_minimals = num_minimals; + tnfa->num_unions = num_unions; xfree(orig_regset); return status; } @@ -2925,5 +2953,6 @@ regfree(regex_t *preg) xfree(tnfa->firstpos_chars); if (tnfa->minimal_tags) xfree(tnfa->minimal_tags); + xfree(tnfa->union_tags); xfree(tnfa); } diff --git a/src/regex/regexec.c b/src/regex/regexec.c index beaf5d8f..bbf02895 100644 --- a/src/regex/regexec.c +++ b/src/regex/regexec.c @@ -936,6 +936,20 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, i = 0; if (match_eo >= 0 && !(cflags & REG_NOSUB)) { + /* Ensure only one branch is selected from an union. */ + int j, *union_tags = tnfa->union_tags; + for (j = 3*tnfa->num_unions; j; j -= 3) + { + int parent = union_tags[j-3]; + int left = union_tags[j-2]; + int right = union_tags[j-1]; + if (parent >= 0 && tags[parent] < 0) + tags[left] = tags[right] = -1; + if (tags[left] < tags[right]) + tags[left] = -1; + else + tags[right] = -1; + } /* Construct submatch offsets from the tags. */ submatch_data = tnfa->submatch_data; while (i < tnfa->num_submatches && i < nmatch) diff --git a/src/regex/tre.h b/src/regex/tre.h index f5315e66..bd685c95 100644 --- a/src/regex/tre.h +++ b/src/regex/tre.h @@ -159,9 +159,11 @@ struct tnfa { int first_char; unsigned int num_submatches; tre_tag_direction_t *tag_directions; + int *union_tags; int *minimal_tags; int num_tags; int num_minimals; + int num_unions; int end_tag; int num_states; int cflags; -- 2.52.0