>From a7e8a0236c45bba7085459d0ccc45988e0ffa2a0 Mon Sep 17 00:00:00 2001
From: Szabolcs Nagy <nsz@port70.net>
Date: Wed, 14 Oct 2026 20:27:58 +0000
Subject: [PATCH 12/25] regex: fix BRE with backref within a submatch

the backtracking matcher queried sub match offsets for backrefs
half-way through the input, but within a submatch that sub is
unfinished and all subs under it get reported as no match so the
backref always failed to match. (before the previous no match fix
this could lead to match with non-sense offsets).

  \(\(a*\)\2\)b vs "aab" was no match now (0,3)(0,2)(0,1)

the fix is a bit of a hack to avoid too many changes (records the
parent sub of the bref and sets parent sub eo to the current offset).
---
 src/regex/regcomp.c |  3 +++
 src/regex/regexec.c | 28 +++++++++++++++++++---------
 src/regex/tre.h     |  1 +
 3 files changed, 23 insertions(+), 9 deletions(-)

diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
index bf2b457d..9aa5e23b 100644
--- a/src/regex/regcomp.c
+++ b/src/regex/regcomp.c
@@ -1296,6 +1296,9 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
 		if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
 		  {
 		    int i;
+		    if (IS_BACKREF(lit))
+		      /* Record the containing submatch. */
+		      tnfa->backref_parent[lit->code_max] = parent;
 		    if (regset[0] >= 0)
 		      {
 			/* Regset is not empty, so add a tag before the
diff --git a/src/regex/regexec.c b/src/regex/regexec.c
index 980abe56..52513647 100644
--- a/src/regex/regexec.c
+++ b/src/regex/regexec.c
@@ -776,7 +776,7 @@ tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
 
 	  /* Get the substring we need to match against.  Remember to
 	     turn off REG_NOSUB temporarily. */
-	  tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB,
+	  tre_fill_pmatch(bt + 1, pmatch, ~REG_NOSUB,
 			  tnfa, tags, pos);
 	  so = pmatch[bt].rm_so;
 	  eo = pmatch[bt].rm_eo;
@@ -936,6 +936,13 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
   tre_submatch_data_t *submatch_data;
   unsigned int i, parent;
 
+  i = 0;
+  while (i < nmatch)
+    {
+      pmatch[i].rm_so = -1;
+      pmatch[i].rm_eo = -1;
+      i++;
+    }
   i = 0;
   if (match_eo >= 0 && !(cflags & REG_NOSUB))
     {
@@ -953,6 +960,15 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
 	  else
 	    tags[right] = -1;
 	}
+      /* Use ~REG_NOSUB to mean a backtracking backref match
+       * where parent subs of the backref are unfinished. */
+      if (cflags == ~REG_NOSUB)
+	{
+	  int bref = nmatch - 1;
+	  int i = tnfa->backref_parent[bref];
+	  for (; i; i = tnfa->submatch_data[i].parent)
+	    pmatch[i].rm_eo = match_eo;
+	}
       /* Construct submatch offsets from the tags. */
       submatch_data = tnfa->submatch_data;
       while (i < tnfa->num_submatches && i < nmatch)
@@ -968,7 +984,8 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
 	    pmatch[i].rm_eo = match_eo;
 	  else if (submatch_data[i].eo_tag == -1)
 	    pmatch[i].rm_eo = -1;
-	  else
+	  else if (tags[submatch_data[i].eo_tag] >= 0)
+	    /* Only update eo with set tags, so backref init above works. */
 	    pmatch[i].rm_eo = tags[submatch_data[i].eo_tag];
 
 	  /* If either of the endpoints were not used, this submatch
@@ -988,13 +1005,6 @@ tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
 	  i++;
 	}
     }
-
-  while (i < nmatch)
-    {
-      pmatch[i].rm_so = -1;
-      pmatch[i].rm_eo = -1;
-      i++;
-    }
 }
 
 
diff --git a/src/regex/tre.h b/src/regex/tre.h
index bd685c95..55b17257 100644
--- a/src/regex/tre.h
+++ b/src/regex/tre.h
@@ -169,6 +169,7 @@ struct tnfa {
   int cflags;
   int have_backrefs;
   int have_approx;
+  int backref_parent[10];
 };
 
 /* from tre-mem.h: */
-- 
2.52.0