>From 88cc3ea8ac7d59e63a757656d14283189eecb5ad Mon Sep 17 00:00:00 2001 From: Szabolcs Nagy Date: Tue, 13 Oct 2026 21:34:14 +0000 Subject: [PATCH 13/25] regex: fix BRE with backref to empty match backref to empty pattern could select the wrong match because the backtracking algorithm stopped trying too early (the infinite loop detection only considered one empty match per bref transition): \(a*\)\{2\}\1 vs "aaa" was (0,3)(1,2) now (0,3)(3,3) so it was (a)(a)(a) now (aaa)()() where the second () is captured and the third is the bref to it. longest first match is preferred. Note: this may not be a complete fix, but it strictly allows more cases to continue the search (whenever input pos makes progress) without risking getting into a loop. --- src/regex/regexec.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/src/regex/regexec.c b/src/regex/regexec.c index 52513647..150fbf9d 100644 --- a/src/regex/regexec.c +++ b/src/regex/regexec.c @@ -622,7 +622,7 @@ tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, regoff_t *tags = NULL; /* Current TNFA state. */ tre_tnfa_transition_t *state; - int *states_seen = NULL; + regoff_t *states_seen = NULL; /* Memory allocator to for allocating the backtracking stack. */ tre_mem_t mem = tre_bt_mem_new(); @@ -687,7 +687,7 @@ tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, match_tags[i] = -1; } for (i = 0; i < tnfa->num_states; i++) - states_seen[i] = 0; + states_seen[i] = -1; } state = NULL; @@ -793,12 +793,12 @@ tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, /* Back reference matched. Check for infinite loop. */ if (bt_len == 0) empty_br_match = 1; - if (empty_br_match && states_seen[trans_i->state_id]) + if (empty_br_match && pos <= states_seen[trans_i->state_id]) { goto backtrack; } - states_seen[trans_i->state_id] = empty_br_match; + states_seen[trans_i->state_id] = empty_br_match ? pos : -1; /* Advance in input string and resync `prev_c', `next_c' and pos. */ -- 2.52.0