>From 17222d03f207fa39467a5d1ea8250b0d77965ad7 Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Tue, 22 Sep 2026 23:39:35 +0000 Subject: [PATCH 03/25] regex: fix O(n) recursion in regcomp use the allocated stack that other ast traversal functions used. regcomp(&re, "aaaa...", 0) can crash on a small stack (e.g. tre_ast_to_tnfa stack frame can be ~40 bytes and then a 4000 long input would overflow a 160k stack) --- src/regex/regcomp.c | 31 ++++++++++--------------------- 1 file changed, 10 insertions(+), 21 deletions(-) diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c index 1152de88..cba8c912 100644 --- a/src/regex/regcomp.c +++ b/src/regex/regcomp.c @@ -1090,13 +1090,6 @@ static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx) from tre-compile.c ***********************************************************************/ - -/* - TODO: - - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive - function calls. -*/ - /* Algorithms to setup tags so that submatch addressing can be done. */ @@ -2641,7 +2634,7 @@ tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2, strings). The TNFA takes O(n^2) space in the worst case, `n' is size of the regexp. */ static reg_errcode_t -tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, +tre_ast_to_tnfa(tre_stack_t *stack, tre_ast_node_t *node, tre_tnfa_transition_t *transitions, int *counts, int *offs) { tre_union_t *uni; @@ -2649,17 +2642,15 @@ tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, tre_iteration_t *iter; reg_errcode_t errcode = REG_OK; - /* XXX - recurse using a stack!. */ - switch (node->type) + STACK_PUSHR(stack, voidptr, 0); + for (; node; node = tre_stack_pop_voidptr(stack)) switch (node->type) { case LITERAL: break; case UNION: uni = (tre_union_t *)node->obj; - errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs); - if (errcode != REG_OK) - return errcode; - errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs); + STACK_PUSHR(stack, voidptr, uni->right); + STACK_PUSHR(stack, voidptr, uni->left); break; case CATENATION: @@ -2670,10 +2661,8 @@ tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, transitions, counts, offs); if (errcode != REG_OK) return errcode; - errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs); - if (errcode != REG_OK) - return errcode; - errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs); + STACK_PUSHR(stack, voidptr, cat->right); + STACK_PUSHR(stack, voidptr, cat->left); break; case ITERATION: @@ -2690,7 +2679,7 @@ tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, if (errcode != REG_OK) return errcode; } - errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs); + STACK_PUSHR(stack, voidptr, iter->arg); break; } return errcode; @@ -2848,7 +2837,7 @@ regcomp(regex_t *restrict preg, const char *restrict regex, int cflags) if (offs == NULL) ERROR_EXIT(REG_ESPACE); - tre_ast_to_tnfa(tree, NULL, counts, NULL); + tre_ast_to_tnfa(stack, tree, NULL, counts, NULL); add = 0; for (i = 0; i < parse_ctx.position; i++) @@ -2865,7 +2854,7 @@ regcomp(regex_t *restrict preg, const char *restrict regex, int cflags) tnfa->transitions = transitions; tnfa->num_transitions = add; - errcode = tre_ast_to_tnfa(tree, transitions, counts, offs); + errcode = tre_ast_to_tnfa(stack, tree, transitions, counts, offs); if (errcode != REG_OK) ERROR_EXIT(errcode); -- 2.52.0