>From b8f6e5b53410fa7a4e38f36b74548ec737b2c611 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Thu, 17 Sep 2026 01:59:49 +0000 Subject: [PATCH 04/25] regex: fix an O(n^2) allocation for nested sub expr regexec checked that the final match offsets are correctly nested intervals by keeping a list for every submatch of all the other submatches it should be inside of, then checking them all. e.g. regcomp(&re, "(((...)))", REG_EXTENDED) allocated n*(n+1)/2 ints for n parens. this affects deeply nested sub expressions. nesting is transitive so only check the direct parent. --- src/regex/regcomp.c | 54 ++++++--------------------------------------- src/regex/regexec.c | 27 +++++++---------------- src/regex/tre.h | 4 ++-- 3 files changed, 17 insertions(+), 68 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index cba8c912..358b032c 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1211,8 +1211,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, int num_minimals = 0; /* Number of special minimal tags. */ int tag = 0; /* The tag that is to be added next. */ int next_tag = 1; /* Next tag to use after this one. */ - int *parents; /* Stack of submatches the current submatch is - contained in. */ + int parent = 0; /* Current node is within this submatch. */ int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */ tre_tag_states_t *saved_states; @@ -1229,19 +1228,10 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, regset[0] = -1; orig_regset = regset; - parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1)); - if (parents == NULL) - { - xfree(regset); - return REG_ESPACE; - } - parents[0] = -1; - saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1)); if (saved_states == NULL) { xfree(regset); - xfree(parents); return REG_ESPACE; } else @@ -1273,9 +1263,9 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, regset[i] = id * 2 + 1; regset[i + 1] = -1; - /* Pop this submatch from the parents stack. */ - for (i = 0; parents[i] >= 0; i++); - parents[i - 1] = -1; + /* Get the containing submatch from the parent list. */ + if (!first_pass) + parent = tnfa->submatch_data[id].parent; break; } @@ -1295,22 +1285,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, if (!first_pass) { - for (i = 0; parents[i] >= 0; i++); - tnfa->submatch_data[id].parents = NULL; - if (i > 0) - { - int *p = xmalloc(sizeof(*p) * (i + 1)); - if (p == NULL) - { - status = REG_ESPACE; - break; - } - assert(tnfa->submatch_data[id].parents == NULL); - tnfa->submatch_data[id].parents = p; - for (i = 0; parents[i] >= 0; i++) - p[i] = parents[i]; - p[i] = -1; - } + tnfa->submatch_data[id].parent = parent; + parent = id; } /* Add end of this submatch to regset after processing this @@ -1524,16 +1500,6 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, break; } } - - if (node->submatch_id >= 0) - { - int i; - /* Push this submatch on the parents stack. */ - for (i = 0; parents[i] >= 0; i++); - parents[i] = node->submatch_id; - parents[i + 1] = -1; - } - break; /* end case: ADDTAGS_RECURSE */ case ADDTAGS_AFTER_ITERATION: @@ -1660,7 +1626,6 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, tnfa->num_tags = num_tags; tnfa->num_minimals = num_minimals; xfree(orig_regset); - xfree(parents); xfree(saved_states); return status; } @@ -2958,12 +2923,7 @@ regfree(regex_t *preg) } if (tnfa->submatch_data) - { - for (i = 0; i < tnfa->num_submatches; i++) - if (tnfa->submatch_data[i].parents) - xfree(tnfa->submatch_data[i].parents); - xfree(tnfa->submatch_data); - } + xfree(tnfa->submatch_data); if (tnfa->tag_directions) xfree(tnfa->tag_directions); diff --git a/src/regex/regexec.c b/src/regex/regexec.c index 253b0e14..38d5c845 100644 --- a/src/regex/regexec.c +++ b/src/regex/regexec.c @@ -931,8 +931,7 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo) { tre_submatch_data_t *submatch_data; - unsigned int i, j; - int *parents; + unsigned int i, parent; i = 0; if (match_eo >= 0 && !(cflags & REG_NOSUB)) @@ -956,25 +955,15 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1) pmatch[i].rm_so = pmatch[i].rm_eo = -1; - i++; - } - /* Reset all submatches that are not within all of their parent - submatches. */ - i = 0; - while (i < tnfa->num_submatches && i < nmatch) - { - if (pmatch[i].rm_eo == -1) - assert(pmatch[i].rm_so == -1); assert(pmatch[i].rm_so <= pmatch[i].rm_eo); - parents = submatch_data[i].parents; - if (parents != NULL) - for (j = 0; parents[j] >= 0; j++) - { - if (pmatch[i].rm_so < pmatch[parents[j]].rm_so - || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo) - pmatch[i].rm_so = pmatch[i].rm_eo = -1; - } + /* Reset all submatches that are not within all of their parent + submatches. */ + parent = submatch_data[i].parent; + if (pmatch[i].rm_so < pmatch[parent].rm_so + || pmatch[i].rm_eo > pmatch[parent].rm_eo) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + i++; } } diff --git a/src/regex/tre.h b/src/regex/tre.h index 9aae851f..f5315e66 100644 --- a/src/regex/tre.h +++ b/src/regex/tre.h @@ -139,8 +139,8 @@ struct tre_submatch_data { int so_tag; /* Tag that gives the value for rm_eo (submatch end offset). */ int eo_tag; - /* List of submatches this submatch is contained in. */ - int *parents; + /* Submatch containing this one or 0 for the 0 submatch. */ + int parent; }; typedef struct tre_submatch_data tre_submatch_data_t; -- 2.52.0