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

[Adhemerval Zanella Netto]

On 13/04/26 18:18, Collin Funk wrote:
> 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

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> ---
>  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);