>From 4a3f0206efd1105d93d30610403b740bab100232 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Fri, 2 Oct 2026 18:00:35 +0000 Subject: [PATCH 23/25] regex: change regset handling in tre_add_tags change the representation of regset to avoid an O(n^2) edge case that can dominate regcomp runtime e.g. with input ()()()()... this also reduced code size and common case runtime a bit and the worst case stack use is reduced from 12n+eps to 8n+eps for an n long input. regset manages lists of (subid,flag) encoded as v>=0 with ops: init setup an empty list by *regset = -1 isempty test if list is empty by *regset < 0 add add v to the list purge process the list and start an empty one save save the list (to a stack) and start an empty one restore restore a saved list (only valid after a purge) before: regset pointed to the start of a -1 terminated array add for(p=regset;*p>=0;p++); p[0]=v; p[1]=-1 purge for(p=regset;*p>=0;p++); proc(p); *regset=-1 save push(regset); while(*regset>=0)regset++ restore regset = pop() after: regset points to the last item of an array starting with -1 add *++regset = v purge while(*regset>=0)proc(regset--) save push(*regset); *regset = -1 restore *regset = pop() so adding n values to regset is now O(n) instead of O(n^2). save could bump regset instead of pushing the last value, but then we don't know how to size the regset array: the number of saves is not known upfront. one complication is that tre_add_tags is called twice: in the first pass purge does not have to process values, but isempty has to work. both before and after this is solved by using *regset=-1 instead of purge in the first pass, but now we ensure regset stays in place. --- src/regex/regcomp.c | 102 +++++++++++++++++++++++--------------------- 1 file changed, 54 insertions(+), 48 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index 40850456..5f6d5c28 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1168,12 +1168,12 @@ typedef enum { /* Go through `regset' and set submatch data for submatches that are using this tag. */ -static void +static int * tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag) { int i; - for (i = 0; regset[i] >= 0; i++) + for (i = 0; regset[i] >= 0; i--) { int id = regset[i] / 2; int start = !(regset[i] % 2); @@ -1182,7 +1182,7 @@ tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag) else tnfa->submatch_data[id].eo_tag = tag; } - regset[0] = -1; + return regset + i; } @@ -1198,7 +1198,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, int bottom = tre_stack_num_objects(stack); /* True for first pass (counting number of needed tags) */ int first_pass = (mem == NULL || tnfa == NULL); - int *regset, *orig_regset; + int regset_first_pass[1]; + int *regset = regset_first_pass; int num_tags = 0; /* Total number of tags. */ int num_minimals = 0; /* Number of special minimal tags. */ int tag = 0; /* The tag that is to be added next. */ @@ -1223,13 +1224,15 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, tnfa->end_tag = 0; tnfa->minimal_tags[0] = -1; - } - regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2)); - if (regset == NULL) - return REG_ESPACE; + regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2)); + if (!regset) + { + xfree(union_stack); + return REG_ESPACE; + } + } regset[0] = -1; - orig_regset = regset; STACK_PUSH(stack, voidptr, node); STACK_PUSH(stack, int, ADDTAGS_RECURSE); @@ -1245,17 +1248,19 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, case ADDTAGS_SET_SUBMATCH_END: { - int id = tre_stack_pop_int(stack); - int i; + int val = 0; + if (!first_pass) + { + int id = tre_stack_pop_int(stack); - /* Add end of this submatch to regset. */ - for (i = 0; regset[i] >= 0; i++); - regset[i] = id * 2 + 1; - regset[i + 1] = -1; + /* Add end of this submatch to regset. */ + val = id * 2 + 1; + regset++; - /* Get the containing submatch from the parent list. */ - if (!first_pass) - parent = tnfa->submatch_data[id].parent; + /* Get the containing submatch from the parent list. */ + parent = tnfa->submatch_data[id].parent; + } + regset[0] = val; break; } @@ -1264,24 +1269,23 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, if (node->submatch_id >= 0) { - int id = node->submatch_id; - int i; - - - /* Add start of this submatch to regset. */ - for (i = 0; regset[i] >= 0; i++); - regset[i] = id * 2; - regset[i + 1] = -1; - + int val = 0; if (!first_pass) { + int id = node->submatch_id; + + /* Add start of this submatch to regset. */ + val = id * 2; + regset++; + tnfa->submatch_data[id].parent = parent; parent = id; + STACK_PUSHX(stack, int, id); } + regset[0] = val; /* Add end of this submatch to regset after processing this node. */ - STACK_PUSHX(stack, int, node->submatch_id); STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END); } @@ -1314,7 +1318,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, minimal_tag = -1; num_minimals++; } - tre_purge_regset(regset, tnfa, tag); + regset = tre_purge_regset(regset, tnfa, tag); } else { @@ -1405,7 +1409,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, minimal_tag = -1; num_minimals++; } - tre_purge_regset(regset, tnfa, tag); + regset = tre_purge_regset(regset, tnfa, tag); } regset[0] = -1; @@ -1450,18 +1454,12 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, STACK_PUSHX(stack, int, left_tag); added_tags += 2; } - STACK_PUSHX(stack, voidptr, regset); STACK_PUSHX(stack, int, added_tags); STACK_PUSHX(stack, voidptr, node); - STACK_PUSHX(stack, voidptr, right); STACK_PUSHX(stack, voidptr, left); - STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT); - - /* Process right child. */ - STACK_PUSHX(stack, voidptr, right); - STACK_PUSHX(stack, int, ADDTAGS_RECURSE); /* After processing left child. */ + STACK_PUSHX(stack, voidptr, right); STACK_PUSHX(stack, int, child_subs && !first_pass); STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT); @@ -1486,7 +1484,7 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, minimal_tag = -1; num_minimals++; } - tre_purge_regset(regset, tnfa, tag); + regset = tre_purge_regset(regset, tnfa, tag); } regset[0] = -1; @@ -1560,17 +1558,24 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, 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 + invisible. The original bottom will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */ - while (*regset >= 0) - regset++; + void *right = tre_stack_pop_voidptr(stack); + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, regset[0]); + regset[0] = -1; + STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT); + /* Process right child. */ + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); break; case ADDTAGS_AFTER_UNION_RIGHT: { int added_tags, tag_left, tag_right; - tre_ast_node_t *left = tre_stack_pop_voidptr(stack); + int regset_bottom_value = tre_stack_pop_int(stack); tre_ast_node_t *right = tre_stack_pop_voidptr(stack); + tre_ast_node_t *left = tre_stack_pop_voidptr(stack); node = tre_stack_pop_voidptr(stack); added_tags = tre_stack_pop_int(stack); if (first_pass) @@ -1578,8 +1583,6 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, node->num_tags = ((tre_union_t *)node->obj)->left->num_tags + ((tre_union_t *)node->obj)->right->num_tags + added_tags; } - int *regset_right = regset; - regset = tre_stack_pop_voidptr(stack); /* Add tags after both children, the left child gets a smaller tag than the right child. This guarantees that we prefer @@ -1602,8 +1605,9 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, status = tre_add_tag_right(mem, right, tag_right); tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE; /* use the child end tags for submatches */ - tre_purge_regset(regset_right, tnfa, tag_right); - tre_purge_regset(regset, tnfa, tag_left); + regset = tre_purge_regset(regset, tnfa, tag_right); + regset[0] = regset_bottom_value; + regset = 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; @@ -1625,7 +1629,10 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, } /* end while(tre_stack_num_objects(stack) > bottom) */ if (!first_pass) - tre_purge_regset(regset, tnfa, tag); + { + regset = tre_purge_regset(regset, tnfa, tag); + xfree(regset); + } if (!first_pass) xfree(union_stack); @@ -1645,7 +1652,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; tnfa->num_unions = num_unions; - xfree(orig_regset); return status; } -- 2.52.0