Re: [PATCH 07/10] regex: fix longstanding backref match bug

[Adhemerval Zanella <adhemerval.zanella@linaro.org>]

Hi Paul,

Trying to sync gnulib with glibc code, this patch trigger some regression
on glibc testcases:

FAIL: posix/tst-boost
FAIL: posix/tst-pcre
FAIL: posix/tst-rxspencer
FAIL: posix/tst-rxspencer-no-utf8

$ grep -n "FAIL rm" posix/tst-boost.out
445:FAIL rm[1] 3..-1 != expected 2..3
448:FAIL rm[1] 3..-1 != expected 2..3
451:FAIL rm[1] 3..-1 != expected 2..3
454:FAIL rm[1] 3..-1 != expected 2..3

$ cat posix/tst-pcre.out 
1168: /([a]*)*/ on a unexpectedly failed to match register 1 1..-1
1171: /([a]*)*/ on aaaaa  unexpectedly failed to match register 1 5..-1
1176: /([ab]*)*/ on a unexpectedly failed to match register 1 1..-1
1179: /([ab]*)*/ on b unexpectedly failed to match register 1 1..-1
1182: /([ab]*)*/ on ababab unexpectedly failed to match register 1 6..-1
1185: /([ab]*)*/ on aaaabcde unexpectedly failed to match register 1 5..-1
1188: /([ab]*)*/ on bbbb     unexpectedly failed to match register 1 4..-1
1193: /([^a]*)*/ on b unexpectedly failed to match register 1 1..-1
1196: /([^a]*)*/ on bbbb unexpectedly failed to match register 1 4..-1
1203: /([^ab]*)*/ on cccc unexpectedly failed to match register 1 4..-1

$ cat posix/tst-rxspencer.out  | grep FAIL
FAIL rm[1] unexpectedly did not match
FAIL rm[1] unexpectedly did not match

$ cat posix/tst-rxspencer-no-utf8.out | grep FAIL
FAIL rm[1] unexpectedly did not match
FAIL rm[1] unexpectedly did not match

On 05/02/2021 22:25, Paul Eggert wrote:
> This fixes a longstanding glibc bug concerning backreferences
> <https://sourceware.org/11053> (2009-12-04).
> * lib/regexec.c (proceed_next_node, push_fail_stack)
> (pop_fail_stack): Push and pop the previous registers
> as well as the current ones.  All callers changed.
> (set_regs): Also pop if CUR_NODE has already been checked,
> so that it does not get added as a duplicate set entry.
> (update_regs): Fix comment location.
> * tests/test-regex.c (tests): New constant.
> (bug_regex11): New test function.
> (main): Bump alarm value.  Call new test function.
> ---
>  ChangeLog          |  13 ++++++
>  lib/regexec.c      |  26 +++++++----
>  tests/test-regex.c | 113 ++++++++++++++++++++++++++++++++++++++++++++-
>  3 files changed, 141 insertions(+), 11 deletions(-)
> 
> diff --git a/ChangeLog b/ChangeLog
> index 74304474b..bd7d1fa16 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,5 +1,18 @@
>  2021-02-05  Paul Eggert  <eggert@cs.ucla.edu>
>  
> +	regex: fix longstanding backref match bug
> +	This fixes a longstanding glibc bug concerning backreferences
> +	<https://sourceware.org/11053> (2009-12-04).
> +	* lib/regexec.c (proceed_next_node, push_fail_stack)
> +	(pop_fail_stack): Push and pop the previous registers
> +	as well as the current ones.  All callers changed.
> +	(set_regs): Also pop if CUR_NODE has already been checked,
> +	so that it does not get added as a duplicate set entry.
> +	(update_regs): Fix comment location.
> +	* tests/test-regex.c (tests): New constant.
> +	(bug_regex11): New test function.
> +	(main): Bump alarm value.  Call new test function.
> +
>  	regex: avoid duplicate in espilon closure
>  	* lib/regcomp.c (calc_eclosure_iter): Insert NODE into epsilon
>  	closure first rather than last.  Otherwise, the epsilon closure
> diff --git a/lib/regexec.c b/lib/regexec.c
> index fdd2e373e..424bc8d15 100644
> --- a/lib/regexec.c
> +++ b/lib/regexec.c
> @@ -59,7 +59,7 @@ static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
>  			 Idx cur_idx, Idx nmatch);
>  static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
>  				      Idx str_idx, Idx dest_node, Idx nregs,
> -				      regmatch_t *regs,
> +				      regmatch_t *regs, regmatch_t *prevregs,
>  				      re_node_set *eps_via_nodes);
>  static reg_errcode_t set_regs (const regex_t *preg,
>  			       const re_match_context_t *mctx,
> @@ -1211,6 +1211,7 @@ check_halt_state_context (const re_match_context_t *mctx,
>  
>  static Idx
>  proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
> +		   regmatch_t *prevregs,
>  		   Idx *pidx, Idx node, re_node_set *eps_via_nodes,
>  		   struct re_fail_stack_t *fs)
>  {
> @@ -1243,7 +1244,7 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
>  	      /* Otherwise, push the second epsilon-transition on the fail stack.  */
>  	      else if (fs != NULL
>  		       && push_fail_stack (fs, *pidx, candidate, nregs, regs,
> -					   eps_via_nodes))
> +					   prevregs, eps_via_nodes))
>  		return -2;
>  
>  	      /* We know we are going to exit.  */
> @@ -1316,7 +1317,8 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
>  static reg_errcode_t
>  __attribute_warn_unused_result__
>  push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
> -		 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
> +		 Idx nregs, regmatch_t *regs, regmatch_t *prevregs,
> +		 re_node_set *eps_via_nodes)
>  {
>    reg_errcode_t err;
>    Idx num = fs->num++;
> @@ -1332,23 +1334,26 @@ push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
>      }
>    fs->stack[num].idx = str_idx;
>    fs->stack[num].node = dest_node;
> -  fs->stack[num].regs = re_malloc (regmatch_t, nregs);
> +  fs->stack[num].regs = re_malloc (regmatch_t, 2 * nregs);
>    if (fs->stack[num].regs == NULL)
>      return REG_ESPACE;
>    memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
> +  memcpy (fs->stack[num].regs + nregs, prevregs, sizeof (regmatch_t) * nregs);
>    err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
>    return err;
>  }
>  
>  static Idx
>  pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
> -		regmatch_t *regs, re_node_set *eps_via_nodes)
> +		regmatch_t *regs, regmatch_t *prevregs,
> +		re_node_set *eps_via_nodes)
>  {
>    if (fs == NULL || fs->num == 0)
>      return -1;
>    Idx num = --fs->num;
>    *pidx = fs->stack[num].idx;
>    memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
> +  memcpy (prevregs, fs->stack[num].regs + nregs, sizeof (regmatch_t) * nregs);
>    re_node_set_free (eps_via_nodes);
>    re_free (fs->stack[num].regs);
>    *eps_via_nodes = fs->stack[num].eps_via_nodes;
> @@ -1408,7 +1413,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>      {
>        update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
>  
> -      if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
> +      if ((idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
> +	  || re_node_set_contains (&eps_via_nodes, cur_node))
>  	{
>  	  Idx reg_idx;
>  	  cur_node = -1;
> @@ -1418,7 +1424,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>  		if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
>  		  {
>  		    cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
> -					       &eps_via_nodes);
> +					       prev_idx_match, &eps_via_nodes);
>  		    break;
>  		  }
>  	    }
> @@ -1431,7 +1437,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>  	}
>  
>        /* Proceed to next node.  */
> -      cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
> +      cur_node = proceed_next_node (mctx, nmatch, pmatch, prev_idx_match,
> +				    &idx, cur_node,
>  				    &eps_via_nodes, fs);
>  
>        if (__glibc_unlikely (cur_node < 0))
> @@ -1443,7 +1450,8 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
>  	      free_fail_stack_return (fs);
>  	      return REG_ESPACE;
>  	    }
> -	  cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, &eps_via_nodes);
> +	  cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
> +				     prev_idx_match, &eps_via_nodes);
>  	  if (cur_node < 0)
>  	    {
>  	      re_node_set_free (&eps_via_nodes);
> diff --git a/tests/test-regex.c b/tests/test-regex.c
> index 58f8200f2..a14619805 100644
> --- a/tests/test-regex.c
> +++ b/tests/test-regex.c
> @@ -55,6 +55,111 @@ really_utf8 (void)
>    return strcmp (locale_charset (), "UTF-8") == 0;
>  }
>  
> +/* Tests supposed to match; copied from glibc posix/bug-regex11.c.  */
> +static struct
> +{
> +  const char *pattern;
> +  const char *string;
> +  int flags, nmatch;
> +  regmatch_t rm[5];
> +} const tests[] = {
> +  /* Test for newline handling in regex.  */
> +  { "[^~]*~", "\nx~y", 0, 2, { { 0, 3 }, { -1, -1 } } },
> +  /* Other tests.  */
> +  { "a(.*)b", "a b", REG_EXTENDED, 2, { { 0, 3 }, { 1, 2 } } },
> +  { ".*|\\([KIO]\\)\\([^|]*\\).*|?[KIO]", "10~.~|P|K0|I10|O16|?KSb", 0, 3,
> +    { { 0, 21 }, { 15, 16 }, { 16, 18 } } },
> +  { ".*|\\([KIO]\\)\\([^|]*\\).*|?\\1", "10~.~|P|K0|I10|O16|?KSb", 0, 3,
> +    { { 0, 21 }, { 8, 9 }, { 9, 10 } } },
> +  { "^\\(a*\\)\\1\\{9\\}\\(a\\{0,9\\}\\)\\([0-9]*;.*[^a]\\2\\([0-9]\\)\\)",
> +    "a1;;0a1aa2aaa3aaaa4aaaaa5aaaaaa6aaaaaaa7aaaaaaaa8aaaaaaaaa9aa2aa1a0", 0,
> +    5, { { 0, 67 }, { 0, 0 }, { 0, 1 }, { 1, 67 }, { 66, 67 } } },
> +  /* Test for BRE expression anchoring.  POSIX says just that this may match;
> +     in glibc regex it always matched, so avoid changing it.  */
> +  { "\\(^\\|foo\\)bar", "bar", 0, 2, { { 0, 3 }, { -1, -1 } } },
> +  { "\\(foo\\|^\\)bar", "bar", 0, 2, { { 0, 3 }, { -1, -1 } } },
> +  /* In ERE this must be treated as an anchor.  */
> +  { "(^|foo)bar", "bar", REG_EXTENDED, 2, { { 0, 3 }, { -1, -1 } } },
> +  { "(foo|^)bar", "bar", REG_EXTENDED, 2, { { 0, 3 }, { -1, -1 } } },
> +  /* Here ^ cannot be treated as an anchor according to POSIX.  */
> +  { "(^|foo)bar", "(^|foo)bar", 0, 2, { { 0, 10 }, { -1, -1 } } },
> +  { "(foo|^)bar", "(foo|^)bar", 0, 2, { { 0, 10 }, { -1, -1 } } },
> +  /* More tests on backreferences.  */
> +  { "()\\1", "x", REG_EXTENDED, 2, { { 0, 0 }, { 0, 0 } } },
> +  { "()x\\1", "x", REG_EXTENDED, 2, { { 0, 1 }, { 0, 0 } } },
> +  { "()\\1*\\1*", "", REG_EXTENDED, 2, { { 0, 0 }, { 0, 0 } } },
> +  { "([0-9]).*\\1(a*)", "7;7a6", REG_EXTENDED, 3, { { 0, 4 }, { 0, 1 }, { 3, 4 } } },
> +  { "([0-9]).*\\1(a*)", "7;7a", REG_EXTENDED, 3, { { 0, 4 }, { 0, 1 }, { 3, 4 } } },
> +  { "(b)()c\\1", "bcb", REG_EXTENDED, 3, { { 0, 3 }, { 0, 1 }, { 1, 1 } } },
> +  { "()(b)c\\2", "bcb", REG_EXTENDED, 3, { { 0, 3 }, { 0, 0 }, { 0, 1 } } },
> +  { "a(b)()c\\1", "abcb", REG_EXTENDED, 3, { { 0, 4 }, { 1, 2 }, { 2, 2 } } },
> +  { "a()(b)c\\2", "abcb", REG_EXTENDED, 3, { { 0, 4 }, { 1, 1 }, { 1, 2 } } },
> +  { "()(b)\\1c\\2", "bcb", REG_EXTENDED, 3, { { 0, 3 }, { 0, 0 }, { 0, 1 } } },
> +  { "(b())\\2\\1", "bbbb", REG_EXTENDED, 3, { { 0, 2 }, { 0, 1 }, { 1, 1 } } },
> +  { "a()(b)\\1c\\2", "abcb", REG_EXTENDED, 3, { { 0, 4 }, { 1, 1 }, { 1, 2 } } },
> +  { "a()d(b)\\1c\\2", "adbcb", REG_EXTENDED, 3, { { 0, 5 }, { 1, 1 }, { 2, 3 } } },
> +  { "a(b())\\2\\1", "abbbb", REG_EXTENDED, 3, { { 0, 3 }, { 1, 2 }, { 2, 2 } } },
> +  { "(bb())\\2\\1", "bbbb", REG_EXTENDED, 3, { { 0, 4 }, { 0, 2 }, { 2, 2 } } },
> +  { "^([^,]*),\\1,\\1$", "a,a,a", REG_EXTENDED, 2, { { 0, 5 }, { 0, 1 } } },
> +  { "^([^,]*),\\1,\\1$", "ab,ab,ab", REG_EXTENDED, 2, { { 0, 8 }, { 0, 2 } } },
> +  { "^([^,]*),\\1,\\1,\\1$", "abc,abc,abc,abc", REG_EXTENDED, 2,
> +    { { 0, 15 }, { 0, 3 } } },
> +  { "^(.?)(.?)(.?)(.?)(.?).?\\5\\4\\3\\2\\1$",
> +    "level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
> +  { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
> +    "level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
> +  { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
> +    "abcdedcba", REG_EXTENDED, 1, { { 0, 9 } } },
> +  /* XXX Not used since they fail so far.  */
> +  { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$|^.?$",
> +    "ababababa", REG_EXTENDED, 1, { { 0, 9 } } },
> +  { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$",
> +    "level", REG_NOSUB | REG_EXTENDED, 0, { { -1, -1 } } },
> +  { "^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$",
> +    "ababababa", REG_EXTENDED, 1, { { 0, 9 } } },
> +};
> +
> +static void
> +bug_regex11 (void)
> +{
> +  regex_t re;
> +  regmatch_t rm[5];
> +  size_t i;
> +  int n;
> +
> +  for (i = 0; i < sizeof (tests) / sizeof (tests[0]); ++i)
> +    {
> +      n = regcomp (&re, tests[i].pattern, tests[i].flags);
> +      if (n != 0)
> +	{
> +	  char buf[500];
> +	  regerror (n, &re, buf, sizeof (buf));
> +	  report_error ("%s: regcomp %zd failed: %s", tests[i].pattern, i, buf);
> +	  continue;
> +	}
> +
> +      if (regexec (&re, tests[i].string, tests[i].nmatch, rm, 0))
> +	{
> +	  report_error ("%s: regexec %zd failed", tests[i].pattern, i);
> +	  regfree (&re);
> +	  continue;
> +	}
> +
> +      for (n = 0; n < tests[i].nmatch; ++n)
> +	if (rm[n].rm_so != tests[i].rm[n].rm_so
> +              || rm[n].rm_eo != tests[i].rm[n].rm_eo)
> +	  {
> +	    if (tests[i].rm[n].rm_so == -1 && tests[i].rm[n].rm_eo == -1)
> +	      break;
> +	    report_error ("%s: regexec %zd match failure rm[%d] %d..%d",
> +                          tests[i].pattern, i, n, rm[n].rm_so, rm[n].rm_eo);
> +	    break;
> +	  }
> +
> +      regfree (&re);
> +    }
> +}
> +
>  int
>  main (void)
>  {
> @@ -65,11 +170,15 @@ main (void)
>    struct re_registers regs;
>  
>  #if HAVE_DECL_ALARM
> -  /* Some builds of glibc go into an infinite loop on this test.  */
> -  int alarm_value = 2;
> +  /* In case a bug causes glibc to go into an infinite loop.
> +     The tests should take less than 10 s on a reasonably modern CPU.  */
> +  int alarm_value = 1000;
>    signal (SIGALRM, SIG_DFL);
>    alarm (alarm_value);
>  #endif
> +
> +  bug_regex11 ();
> +
>    if (setlocale (LC_ALL, "en_US.UTF-8"))
>      {
>        {
>