[PATCH v2] posix: fix false regex match with backrefs and $ anchor

[Collin Funk]

This fixes the $ anchor being ignored in the following grep command:

    $ grep -E '^(.?)(.?).?\2\1$' <<< ab
    ab

However, the regular expression should only match palindromes.

This patch is mostly copied from a commit in Gnulib from Jim Meyering
[1], and a followup commit by Paul Eggert [2]. It was found by Ed Morton
in GNU sed [3].

[1] https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=8c22765403cc34e87ad953cb3f6901e723c937f5
[2] https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=8b627431703c7e7d762f9e3174336d66b558314a
[3] https://bugs.gnu.org/68725
---
 posix/Makefile      |  1 +
 posix/bug-regex39.c | 35 +++++++++++++++++++++++++++++++++++
 posix/regexec.c     | 14 ++++++++++----
 3 files changed, 46 insertions(+), 4 deletions(-)
 create mode 100644 posix/bug-regex39.c

diff --git a/posix/Makefile b/posix/Makefile
index a5e5162c61..0fa532396f 100644
--- a/posix/Makefile
+++ b/posix/Makefile
@@ -242,6 +242,7 @@ tests := \
   bug-regex36 \
   bug-regex37 \
   bug-regex38 \
+  bug-regex39 \
   regexbug1 \
   runptests \
   runtests \
diff --git a/posix/bug-regex39.c b/posix/bug-regex39.c
new file mode 100644
index 0000000000..393fd5491e
--- /dev/null
+++ b/posix/bug-regex39.c
@@ -0,0 +1,35 @@
+/* Test for GNU sed bug 68725.
+   Copyright (C) 2026 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <regex.h>
+
+#include <support/check.h>
+
+static int
+do_test (void)
+{
+  char const pattern[] = "^(.?)(.?).?\\2\\1$";
+  regex_t re;
+  TEST_VERIFY_EXIT (regcomp (&re, pattern, REG_EXTENDED) == 0);
+  regmatch_t match;
+  TEST_VERIFY (regexec (&re, "ab", 1, &match, 0) == REG_NOMATCH);
+  regfree (&re);
+  return 0;
+}
+
+#include <support/test-driver.c>
diff --git a/posix/regexec.c b/posix/regexec.c
index 193d8bd650..9ac5565295 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -946,7 +946,7 @@ prune_impossible_nodes (re_match_context_t *mctx)
 	      goto free_return;
 	  if (sifted_states[0] != NULL || lim_states[0] != NULL)
 	    break;
-	  do
+	  for (;;)
 	    {
 	      --match_last;
 	      if (match_last < 0)
@@ -954,11 +954,17 @@ prune_impossible_nodes (re_match_context_t *mctx)
 		  ret = REG_NOMATCH;
 		  goto free_return;
 		}
-	    } while (mctx->state_log[match_last] == NULL
-		     || !mctx->state_log[match_last]->halt);
-	  halt_node = check_halt_state_context (mctx,
+	      if (mctx->state_log[match_last] != NULL
+		  && mctx->state_log[match_last]->halt)
+		{
+		  halt_node
+		    = check_halt_state_context (mctx,
 						mctx->state_log[match_last],
 						match_last);
+		  if (halt_node)
+		    break;
+		}
+	    }
 	}
       ret = merge_state_array (dfa, sifted_states, lim_states,
 			       match_last + 1);
-- 
2.53.0