Updated to fedora-glibc-20041112T1640

6 files changed, 351 insertions, 274 deletions

diff --git a/posix/Makefile b/posix/Makefile
index cd6a52c098..8bc15ad215 100644
--- a/posix/Makefile
+++ b/posix/Makefile
@@ -79,7 +79,8 @@ tests		:= tstgetopt testfnm runtests runptests	     \
 		   bug-regex8 bug-regex9 bug-regex10 bug-regex11 bug-regex12 \
 		   bug-regex13 bug-regex14 bug-regex15 bug-regex16 \
 		   bug-regex17 bug-regex18 bug-regex19 bug-regex20 \
-		   bug-regex21 bug-regex22 bug-regex23 tst-nice tst-nanosleep \
+		   bug-regex21 bug-regex22 bug-regex23 bug-regex24 \
+		   tst-nice tst-nanosleep \
 		   transbug tst-rxspencer tst-pcre tst-boost \
 		   bug-ga1 tst-vfork1 tst-vfork2 tst-waitid \
 		   tst-getaddrinfo2 bug-glob1 bug-glob2
diff --git a/posix/bug-regex24.c b/posix/bug-regex24.c
new file mode 100644
index 0000000000..83ea10bb62
--- /dev/null
+++ b/posix/bug-regex24.c
@@ -0,0 +1,59 @@
+#include <regex.h>
+#include <stdio.h>
+
+#define str "civic"
+
+#define N 10
+static const char *expected[N] =
+  {
+    str, "c", "i", "", "", "", "", "", "", ""
+  };
+
+static int
+do_test (void)
+{
+  regex_t rbuf;
+  static const char pat[] = "\
+^(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?)(.?).?\\9\\8\\7\\6\\5\\4\\3\\2\\1$";
+
+  int err = regcomp (&rbuf, pat, REG_EXTENDED);
+  if (err != 0)
+    {
+      char errstr[300];
+      regerror (err, &rbuf, errstr, sizeof (errstr));
+      puts (errstr);
+      return err;
+    }
+
+  regmatch_t m[N];
+  err = regexec (&rbuf, str, N, m, 0);
+  if (err != 0)
+    {
+      puts ("regexec failed");
+      return 1;
+    }
+
+  int result = 0;
+  for (int i = 0; i < N; ++i)
+    if (m[i].rm_so == -1)
+      {
+	printf ("m[%d] unused\n", i);
+	result = 1;
+      }
+    else
+      {
+	int len = m[i].rm_eo - m[i].rm_so;
+
+	printf ("m[%d] = \"%.*s\"\n", i, len, str + m[i].rm_so);
+
+	if (strlen (expected[i]) != len
+	    || memcmp (expected[i], str + m[i].rm_so, len) != 0)
+	  result = 1;
+      }
+
+  return result;
+}
+
+#define TIMEOUT 30
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index 609719f79c..bb1d73d9a0 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -576,7 +576,7 @@ re_string_reconstruct (pstr, idx, eflags)
      int idx, eflags;
 {
   int offset = idx - pstr->raw_mbs_idx;
-  if (offset < 0)
+  if (BE (offset < 0, 0))
     {
       /* Reset buffer.  */
 #ifdef RE_ENABLE_I18N
@@ -596,10 +596,10 @@ re_string_reconstruct (pstr, idx, eflags)
       offset = idx;
     }
 
-  if (offset != 0)
+  if (BE (offset != 0, 1))
     {
       /* Are the characters which are already checked remain?  */
-      if (offset < pstr->valid_raw_len
+      if (BE (offset < pstr->valid_raw_len, 1)
 #ifdef RE_ENABLE_I18N
 	  /* Handling this would enlarge the code too much.
 	     Accept a slowdown in that case.  */
@@ -614,7 +614,7 @@ re_string_reconstruct (pstr, idx, eflags)
 	    memmove (pstr->wcs, pstr->wcs + offset,
 		     (pstr->valid_len - offset) * sizeof (wint_t));
 #endif /* RE_ENABLE_I18N */
-	  if (pstr->mbs_allocated)
+	  if (BE (pstr->mbs_allocated, 0))
 	    memmove (pstr->mbs, pstr->mbs + offset,
 		     pstr->valid_len - offset);
 	  pstr->valid_len -= offset;
@@ -711,7 +711,7 @@ re_string_reconstruct (pstr, idx, eflags)
 				      ? CONTEXT_NEWLINE : 0));
 	    }
 	}
-      if (!pstr->mbs_allocated)
+      if (!BE (pstr->mbs_allocated, 0))
 	pstr->mbs += offset;
     }
   pstr->raw_mbs_idx = idx;
@@ -733,16 +733,17 @@ re_string_reconstruct (pstr, idx, eflags)
     }
   else
 #endif /* RE_ENABLE_I18N */
+  if (BE (pstr->mbs_allocated, 0))
     {
       if (pstr->icase)
 	build_upper_buffer (pstr);
       else if (pstr->trans != NULL)
 	re_string_translate_buffer (pstr);
-      else
-	pstr->valid_len = pstr->len;
     }
-  pstr->cur_idx = 0;
+  else
+    pstr->valid_len = pstr->len;
 
+  pstr->cur_idx = 0;
   return REG_NOERROR;
 }
 
@@ -840,16 +841,13 @@ re_string_context_at (input, idx, eflags)
      int idx, eflags;
 {
   int c;
-  if (idx < 0 || idx == input->len)
-    {
-      if (idx < 0)
-	/* In this case, we use the value stored in input->tip_context,
-	   since we can't know the character in input->mbs[-1] here.  */
-	return input->tip_context;
-      else /* (idx == input->len) */
-	return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
-		: CONTEXT_NEWLINE | CONTEXT_ENDBUF);
-    }
+  if (BE (idx < 0, 0))
+    /* In this case, we use the value stored in input->tip_context,
+       since we can't know the character in input->mbs[-1] here.  */
+    return input->tip_context;
+  if (BE (idx == input->len, 0))
+    return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
+	    : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
 #ifdef RE_ENABLE_I18N
   if (input->mb_cur_max > 1)
     {
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 023056c028..14d95a5b84 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -548,9 +548,9 @@ struct re_backref_cache_entry
   int str_idx;
   int subexp_from;
   int subexp_to;
-  /* We need only one byte from the following field.  If other small
-     fields are added the type could be changed to 'char'.  */
-  int more;
+  char more;
+  char unused;
+  unsigned short int eps_reachable_subexps_map;
 };
 
 typedef struct
diff --git a/posix/regexec.c b/posix/regexec.c
index 72ae70b916..a03df2636a 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -22,8 +22,6 @@ static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
 				     int n) internal_function;
 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
 static void match_ctx_free (re_match_context_t *cache) internal_function;
-static void match_ctx_free_subtops (re_match_context_t *mctx)
-     internal_function;
 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
 					  int str_idx, int from, int to)
      internal_function;
@@ -606,15 +604,16 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   reg_errcode_t err;
   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
   int left_lim, right_lim, incr;
-  int fl_longest_match, match_first, match_last = -1;
-  int fast_translate, sb;
+  int fl_longest_match, match_first, match_kind, match_last = -1;
+  int sb, ch;
 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
   re_match_context_t mctx = { .dfa = dfa };
 #else
   re_match_context_t mctx;
 #endif
-  char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
-		    && range && !preg->can_be_null) ? preg->fastmap : NULL);
+  char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
+		   && range && !preg->can_be_null) ? preg->fastmap : NULL;
+  unsigned RE_TRANSLATE_TYPE t = (unsigned RE_TRANSLATE_TYPE) preg->translate;
 
 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
   memset (&mctx, '\0', sizeof (re_match_context_t));
@@ -685,88 +684,100 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   left_lim = (range < 0) ? start + range : start;
   right_lim = (range < 0) ? start : start + range;
   sb = dfa->mb_cur_max == 1;
-  fast_translate = sb || !(preg->syntax & RE_ICASE || preg->translate);
-
-  for (;;)
+  match_kind =
+    (fastmap
+     ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
+	| (range >= 0 ? 2 : 0)
+	| (t != NULL ? 1 : 0))
+     : 8);
+
+  for (;; match_first += incr)
     {
-      /* At first get the current byte from input string.  */
-      if (fastmap)
+      err = REG_NOMATCH;
+      if (match_first < left_lim || right_lim < match_first)
+	goto free_return;
+
+      /* Advance as rapidly as possible through the string, until we
+	 find a plausible place to start matching.  This may be done
+	 with varying efficiency, so there are various possibilities:
+	 only the most common of them are specialized, in order to
+	 save on code size.  We use a switch statement for speed.  */
+      switch (match_kind)
 	{
-	  if (BE (fast_translate, 1))
+	case 8:
+	  /* No fastmap.  */
+	  break;
+
+	case 7:
+	  /* Fastmap with single-byte translation, match forward.  */
+	  while (BE (match_first < right_lim, 1)
+		 && !fastmap[t[(unsigned char) string[match_first]]])
+	    ++match_first;
+	  goto forward_match_found_start_or_reached_end;
+
+	case 6:
+	  /* Fastmap without translation, match forward.  */
+	  while (BE (match_first < right_lim, 1)
+		 && !fastmap[(unsigned char) string[match_first]])
+	    ++match_first;
+
+	forward_match_found_start_or_reached_end:
+	  if (BE (match_first == right_lim, 0))
 	    {
-	      unsigned RE_TRANSLATE_TYPE t
-		= (unsigned RE_TRANSLATE_TYPE) preg->translate;
-	      if (BE (range >= 0, 1))
-		{
-		  if (BE (t != NULL, 0))
-		    {
-		      while (BE (match_first < right_lim, 1)
-			     && !fastmap[t[(unsigned char) string[match_first]]])
-			++match_first;
-		    }
-		  else
-		    {
-		      while (BE (match_first < right_lim, 1)
-			     && !fastmap[(unsigned char) string[match_first]])
-			++match_first;
-		    }
-		  if (BE (match_first == right_lim, 0))
-		    {
-		      int ch = match_first >= length
-			       ? 0 : (unsigned char) string[match_first];
-		      if (!fastmap[t ? t[ch] : ch])
-			break;
-		    }
-		}
-	      else
-		{
-		  while (match_first >= left_lim)
-		    {
-		      int ch = match_first >= length
-			       ? 0 : (unsigned char) string[match_first];
-		      if (fastmap[t ? t[ch] : ch])
-			break;
-		      --match_first;
-		    }
-		  if (match_first < left_lim)
-		    break;
-		}
+	      ch = match_first >= length
+		       ? 0 : (unsigned char) string[match_first];
+	      if (!fastmap[t ? t[ch] : ch])
+		goto free_return;
 	    }
-	  else
+	  break;
+
+	case 4:
+	case 5:
+	  /* Fastmap without multi-byte translation, match backwards.  */
+	  while (match_first >= left_lim)
 	    {
-	      int ch;
+	      ch = match_first >= length
+		       ? 0 : (unsigned char) string[match_first];
+	      if (fastmap[t ? t[ch] : ch])
+		break;
+	      --match_first;
+	    }
+	  if (match_first < left_lim)
+	    goto free_return;
+	  break;
 
-	      do
+	default:
+	  /* In this case, we can't determine easily the current byte,
+	     since it might be a component byte of a multibyte
+	     character.  Then we use the constructed buffer instead.  */
+	  for (;;)
+	    {
+	      /* If MATCH_FIRST is out of the valid range, reconstruct the
+		 buffers.  */
+	      unsigned int offset = match_first - mctx.input.raw_mbs_idx;
+	      if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
 		{
-		  /* In this case, we can't determine easily the current byte,
-		     since it might be a component byte of a multibyte
-		     character.  Then we use the constructed buffer
-		     instead.  */
-		  /* If MATCH_FIRST is out of the valid range, reconstruct the
-		     buffers.  */
-		  if (mctx.input.raw_mbs_idx + mctx.input.valid_raw_len
-		      <= match_first
-		      || match_first < mctx.input.raw_mbs_idx)
-		    {
-		      err = re_string_reconstruct (&mctx.input, match_first,
-						   eflags);
-		      if (BE (err != REG_NOERROR, 0))
-			goto free_return;
-		    }
-		  /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
-		     Note that MATCH_FIRST must not be smaller than 0.  */
-		  ch = ((match_first >= length) ? 0
-		       : re_string_byte_at (&mctx.input,
-					    match_first
-					    - mctx.input.raw_mbs_idx));
-		  if (fastmap[ch])
-		    break;
-		  match_first += incr;
+		  err = re_string_reconstruct (&mctx.input, match_first,
+					       eflags);
+		  if (BE (err != REG_NOERROR, 0))
+		    goto free_return;
+
+		  offset = match_first - mctx.input.raw_mbs_idx;
 		}
-	      while (match_first >= left_lim && match_first <= right_lim);
-	      if (! fastmap[ch])
+	      /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
+		 Note that MATCH_FIRST must not be smaller than 0.  */
+	      ch = (match_first >= length
+		    ? 0 : re_string_byte_at (&mctx.input, offset));
+	      if (fastmap[ch])
 		break;
+	      match_first += incr;
+	      if (match_first < left_lim || match_first > right_lim)
+	        {
+	          err = REG_NOMATCH;
+	          goto free_return;
+	        }
 	    }
+	  break;
 	}
 
       /* Reconstruct the buffers so that the matcher can assume that
@@ -774,57 +785,60 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
       err = re_string_reconstruct (&mctx.input, match_first, eflags);
       if (BE (err != REG_NOERROR, 0))
 	goto free_return;
+
 #ifdef RE_ENABLE_I18N
-     /* Eliminate it when it is a component of a multibyte character
-	 and isn't the head of a multibyte character.  */
-      if (sb || re_string_first_byte (&mctx.input, 0))
+     /* Don't consider this char as a possible match start if it part,
+	yet isn't the head, of a multibyte character.  */
+      if (!sb && !re_string_first_byte (&mctx.input, 0))
+	continue;
 #endif
+
+      /* It seems to be appropriate one, then use the matcher.  */
+      /* We assume that the matching starts from 0.  */
+      mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
+      match_last = check_matching (&mctx, fl_longest_match,
+				   range >= 0 ? &match_first : NULL);
+      if (match_last != -1)
 	{
-	  /* It seems to be appropriate one, then use the matcher.  */
-	  /* We assume that the matching starts from 0.  */
-	  mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
-	  match_last = check_matching (&mctx, fl_longest_match,
-				       range >= 0 ? &match_first : NULL);
-	  if (match_last != -1)
+	  if (BE (match_last == -2, 0))
 	    {
-	      if (BE (match_last == -2, 0))
+	      err = REG_ESPACE;
+	      goto free_return;
+	    }
+	  else
+	    {
+	      mctx.match_last = match_last;
+	      if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
 		{
-		  err = REG_ESPACE;
-		  goto free_return;
+		  re_dfastate_t *pstate = mctx.state_log[match_last];
+		  mctx.last_node = check_halt_state_context (&mctx, pstate,
+							     match_last);
 		}
-	      else
+	      if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
+		  || dfa->nbackref)
 		{
-		  mctx.match_last = match_last;
-		  if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
-		    {
-		      re_dfastate_t *pstate = mctx.state_log[match_last];
-		      mctx.last_node = check_halt_state_context (&mctx, pstate,
-								 match_last);
-		    }
-		  if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
-		      || dfa->nbackref)
-		    {
-		      err = prune_impossible_nodes (&mctx);
-		      if (err == REG_NOERROR)
-			break;
-		      if (BE (err != REG_NOMATCH, 0))
-			goto free_return;
-		      match_last = -1;
-		    }
-		  else
-		    break; /* We found a match.  */
+		  err = prune_impossible_nodes (&mctx);
+		  if (err == REG_NOERROR)
+		    break;
+		  if (BE (err != REG_NOMATCH, 0))
+		    goto free_return;
+		  match_last = -1;
 		}
+	      else
+		break; /* We found a match.  */
 	    }
-	  match_ctx_clean (&mctx);
 	}
-      /* Update counter.  */
-      match_first += incr;
-      if (match_first < left_lim || right_lim < match_first)
-	break;
+
+      match_ctx_clean (&mctx);
     }
 
+#ifdef DEBUG
+  assert (match_last != -1);
+  assert (err == REG_NOERROR);
+#endif
+
   /* Set pmatch[] if we need.  */
-  if (match_last != -1 && nmatch > 0)
+  if (nmatch > 0)
     {
       int reg_idx;
 
@@ -869,7 +883,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
 	    pmatch[reg_idx].rm_eo += match_first;
 	  }
     }
-  err = (match_last == -1) ? REG_NOMATCH : REG_NOERROR;
+
  free_return:
   re_free (mctx.state_log);
   if (dfa->nbackref)
@@ -1072,6 +1086,20 @@ check_matching (mctx, fl_longest_match, p_match_first)
   while (!re_string_eoi (&mctx->input))
     {
       re_dfastate_t *old_state = cur_state;
+      int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
+
+      if (BE (next_char_idx >= mctx->input.bufs_len, 0)
+          || (BE (next_char_idx >= mctx->input.valid_len, 0)
+              && mctx->input.valid_len < mctx->input.len))
+        {
+          err = extend_buffers (mctx);
+          if (BE (err != REG_NOERROR, 0))
+	    {
+	      assert (err == REG_ESPACE);
+	      return -2;
+	    }
+        }
+
       cur_state = transit_state (&err, mctx, cur_state);
       if (mctx->state_log != NULL)
 	cur_state = merge_state_with_log (&err, mctx, cur_state);
@@ -1090,10 +1118,10 @@ check_matching (mctx, fl_longest_match, p_match_first)
 	    break;
 	}
 
-      if (at_init_state)
+      if (BE (at_init_state, 0))
 	{
 	  if (old_state == cur_state)
-	    next_start_idx = re_string_cur_idx (&mctx->input);
+	    next_start_idx = next_char_idx;
 	  else
 	    at_init_state = 0;
 	}
@@ -1109,13 +1137,16 @@ check_matching (mctx, fl_longest_match, p_match_first)
 	      /* We found an appropriate halt state.  */
 	      match_last = re_string_cur_idx (&mctx->input);
 	      match = 1;
+
+	      /* We found a match, do not modify match_first below.  */
+	      p_match_first = NULL;
 	      if (!fl_longest_match)
 		break;
 	    }
 	}
-   }
+    }
 
-  if (match_last == -1 && p_match_first)
+  if (p_match_first)
     *p_match_first += next_start_idx;
 
   return match_last;
@@ -1854,7 +1885,12 @@ check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
 	      {
 		int dst, cpos;
 
-		if (ent->node != node || ent->subexp_from != ent->subexp_to)
+		if (ent->node != node)
+		  continue;
+
+		if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map)
+		    && (ent->eps_reachable_subexps_map
+			& (1 << (subexp_idx - 1))) == 0)
 		  continue;
 
 		/* Recurse trying to reach the OP_OPEN_SUBEXP and
@@ -1875,11 +1911,13 @@ check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
 		cpos = check_dst_limits_calc_pos_1 (mctx, boundaries,
 						    subexp_idx, dst, bkref_idx);
 
-		if (cpos == -1 && (boundaries & 1))
+		if (cpos == -1 /* && (boundaries & 1) */)
 		  return -1;
 
-		if (cpos == 0 /* && (boundaries & 2) */)
+		if (cpos == 0 && (boundaries & 2))
 		  return 0;
+
+		ent->eps_reachable_subexps_map &= ~(1 << (subexp_idx - 1));
 	      }
 	    while (ent++->more);
 	    break;
@@ -2167,23 +2205,14 @@ transit_state (err, mctx, state)
   re_dfastate_t **trtable;
   unsigned char ch;
 
-  if (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.bufs_len
-      || (re_string_cur_idx (&mctx->input) + 1 >= mctx->input.valid_len
-	  && mctx->input.valid_len < mctx->input.len))
+#ifdef RE_ENABLE_I18N
+  /* If the current state can accept multibyte.  */
+  if (BE (state->accept_mb, 0))
     {
-      *err = extend_buffers (mctx);
+      *err = transit_state_mb (mctx, state);
       if (BE (*err != REG_NOERROR, 0))
 	return NULL;
     }
-
-#ifdef RE_ENABLE_I18N
-      /* If the current state can accept multibyte.  */
-      if (state->accept_mb)
-	{
-	  *err = transit_state_mb (mctx, state);
-	  if (BE (*err != REG_NOERROR, 0))
-	    return NULL;
-	}
 #endif /* RE_ENABLE_I18N */
 
   /* Then decide the next state with the single byte.  */
@@ -4078,28 +4107,6 @@ static void
 match_ctx_clean (mctx)
     re_match_context_t *mctx;
 {
-  match_ctx_free_subtops (mctx);
-  mctx->nsub_tops = 0;
-  mctx->nbkref_ents = 0;
-}
-
-/* Free all the memory associated with MCTX.  */
-
-static void
-match_ctx_free (mctx)
-    re_match_context_t *mctx;
-{
-  match_ctx_free_subtops (mctx);
-  re_free (mctx->sub_tops);
-  re_free (mctx->bkref_ents);
-}
-
-/* Free all the memory associated with MCTX->SUB_TOPS.  */
-
-static void
-match_ctx_free_subtops (mctx)
-     re_match_context_t *mctx;
-{
   int st_idx;
   for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
     {
@@ -4119,6 +4126,21 @@ match_ctx_free_subtops (mctx)
 	}
       free (top);
     }
+
+  mctx->nsub_tops = 0;
+  mctx->nbkref_ents = 0;
+}
+
+/* Free all the memory associated with MCTX.  */
+
+static void
+match_ctx_free (mctx)
+    re_match_context_t *mctx;
+{
+  /* First, free all the memory associated with MCTX->SUB_TOPS.  */
+  match_ctx_clean (mctx);
+  re_free (mctx->sub_tops);
+  re_free (mctx->bkref_ents);
 }
 
 /* Add a new backreference entry to MCTX.
@@ -4154,6 +4176,18 @@ match_ctx_add_entry (mctx, node, str_idx, from, to)
   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
+
+  /* This is a cache that saves negative results of check_dst_limits_calc_pos.
+     If bit N is clear, means that this entry won't epsilon-transition to
+     an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression.  If
+     it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
+     such node.
+
+     A backreference does not epsilon-transition unless it is empty, so set
+     to all zeros if FROM != TO.  */
+  mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
+    = (from == to ? ~0 : 0);
+
   mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
   if (mctx->max_mb_elem_len < to - from)
     mctx->max_mb_elem_len = to - from;
diff --git a/posix/tst-waitid.c b/posix/tst-waitid.c
index 642d529a9a..d810922f04 100644
--- a/posix/tst-waitid.c
+++ b/posix/tst-waitid.c
@@ -18,7 +18,7 @@
    02111-1307 USA.  */
 
 #include <errno.h>
-#include <error.h>
+#include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
 #include <sys/wait.h>
@@ -56,16 +56,15 @@ sigchld (int signo, siginfo_t *info, void *ctx)
 {
   if (signo != SIGCHLD)
     {
-      error (0, 0, "SIGCHLD handler got signal %d instead!", signo);
+      printf ("SIGCHLD handler got signal %d instead!\n", signo);
       _exit (EXIT_FAILURE);
     }
 
   if (! expecting_sigchld)
     {
       spurious_sigchld = 1;
-      error (0, 0,
-	     "spurious SIGCHLD: signo %d code %d status %d pid %d\n",
-	     info->si_signo, info->si_code, info->si_status, info->si_pid);
+      printf ("spurious SIGCHLD: signo %d code %d status %d pid %d\n",
+	      info->si_signo, info->si_code, info->si_status, info->si_pid);
     }
   else
     {
@@ -79,7 +78,7 @@ check_sigchld (const char *phase, int *ok, int code, int status, pid_t pid)
 {
   if (expecting_sigchld)
     {
-      error (0, 0, "missing SIGCHLD on %s", phase);
+      printf ("missing SIGCHLD on %s\n", phase);
       *ok = EXIT_FAILURE;
       expecting_sigchld = 0;
       return;
@@ -87,22 +86,22 @@ check_sigchld (const char *phase, int *ok, int code, int status, pid_t pid)
 
   if (sigchld_info.si_signo != SIGCHLD)
     {
-      error (0, 0, "SIGCHLD for %s signal %d", phase, sigchld_info.si_signo);
+      printf ("SIGCHLD for %s signal %d\n", phase, sigchld_info.si_signo);
       *ok = EXIT_FAILURE;
     }
   if (sigchld_info.si_code != code)
     {
-      error (0, 0, "SIGCHLD for %s code %d", phase, sigchld_info.si_code);
+      printf ("SIGCHLD for %s code %d\n", phase, sigchld_info.si_code);
       *ok = EXIT_FAILURE;
     }
   if (sigchld_info.si_status != status)
     {
-      error (0, 0, "SIGCHLD for %s status %d", phase, sigchld_info.si_status);
+      printf ("SIGCHLD for %s status %d\n", phase, sigchld_info.si_status);
       *ok = EXIT_FAILURE;
     }
   if (sigchld_info.si_pid != pid)
     {
-      error (0, 0, "SIGCHLD for %s pid %d", phase, sigchld_info.si_pid);
+      printf ("SIGCHLD for %s pid %d\n", phase, sigchld_info.si_pid);
       *ok = EXIT_FAILURE;
     }
 }
@@ -121,7 +120,7 @@ do_test (int argc, char *argv[])
   sa.sa_sigaction = &sigchld;
   if (sigemptyset (&sa.sa_mask) < 0 || sigaction (SIGCHLD, &sa, NULL) < 0)
     {
-      error (0, errno, "setting SIGCHLD handler");
+      printf ("setting SIGCHLD handler: %m\n");
       return EXIT_FAILURE;
     }
 #endif
@@ -131,7 +130,7 @@ do_test (int argc, char *argv[])
   pid_t pid = fork ();
   if (pid < 0)
     {
-      error (0, errno, "fork");
+      printf ("fork: %m\n");
       return EXIT_FAILURE;
     }
   else if (pid == 0)
@@ -156,18 +155,18 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid returned bogus value %d\n", fail);
+      printf ("waitid returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WNOHANG on stopped");
+      printf ("waitid WNOHANG on stopped: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo == 0)
 	break;
       if (info.si_signo == SIGCHLD)
-	error (0, 0, "waitid WNOHANG on stopped status %d\n", info.si_status);
+	printf ("waitid WNOHANG on stopped status %d\n", info.si_status);
       else
-	error (0, 0, "waitid WNOHANG on stopped signal %d\n", info.si_signo);
+	printf ("waitid WNOHANG on stopped signal %d\n", info.si_signo);
       RETURN (EXIT_FAILURE);
     }
 
@@ -179,34 +178,34 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid WSTOPPED|WNOHANG returned bogus value %d\n", fail);
+      printf ("waitid WSTOPPED|WNOHANG returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WSTOPPED|WNOHANG on stopped");
+      printf ("waitid WSTOPPED|WNOHANG on stopped: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo != SIGCHLD)
 	{
-	  error (0, 0, "waitid WSTOPPED|WNOHANG on stopped signal %d\n",
-		 info.si_signo);
+	  printf ("waitid WSTOPPED|WNOHANG on stopped signal %d\n",
+		  info.si_signo);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_code != CLD_STOPPED)
 	{
-	  error (0, 0, "waitid WSTOPPED|WNOHANG on stopped code %d\n",
-		 info.si_code);
+	  printf ("waitid WSTOPPED|WNOHANG on stopped code %d\n",
+		  info.si_code);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_status != SIGSTOP)
 	{
-	  error (0, 0, "waitid WSTOPPED|WNOHANG on stopped status %d\n",
-		 info.si_status);
+	  printf ("waitid WSTOPPED|WNOHANG on stopped status %d\n",
+		  info.si_status);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_pid != pid)
 	{
-	  error (0, 0, "waitid WSTOPPED|WNOHANG on stopped pid %d != %d\n",
-		 info.si_pid, pid);
+	  printf ("waitid WSTOPPED|WNOHANG on stopped pid %d != %d\n",
+		  info.si_pid, pid);
 	  RETURN (EXIT_FAILURE);
 	}
     }
@@ -215,7 +214,7 @@ do_test (int argc, char *argv[])
 
   if (kill (pid, SIGCONT) != 0)
     {
-      error (0, errno, "kill (%d, SIGCONT)", pid);
+      printf ("kill (%d, SIGCONT): %m\n", pid);
       RETURN (EXIT_FAILURE);
     }
 
@@ -225,7 +224,7 @@ do_test (int argc, char *argv[])
 #if WCONTINUED != 0
   if (expecting_sigchld)
     {
-      error (0, 0, "no SIGCHLD seen for SIGCONT (optional)");
+      printf ("no SIGCHLD seen for SIGCONT (optional)\n");
       expecting_sigchld = 0;
     }
   else
@@ -238,35 +237,34 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0,
-	     "waitid WCONTINUED|WNOWAIT returned bogus value %d\n", fail);
+      printf ("waitid WCONTINUED|WNOWAIT returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WCONTINUED|WNOWAIT on continued");
+      printf ("waitid WCONTINUED|WNOWAIT on continued: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo != SIGCHLD)
 	{
-	  error (0, 0, "waitid WCONTINUED|WNOWAIT on continued signal %d\n",
-		 info.si_signo);
+	  printf ("waitid WCONTINUED|WNOWAIT on continued signal %d\n",
+		  info.si_signo);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_code != CLD_CONTINUED)
 	{
-	  error (0, 0, "waitid WCONTINUED|WNOWAIT on continued code %d\n",
-		 info.si_code);
+	  printf ("waitid WCONTINUED|WNOWAIT on continued code %d\n",
+		  info.si_code);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_status != SIGCONT)
 	{
-	  error (0, 0, "waitid WCONTINUED|WNOWAIT on continued status %d\n",
-		 info.si_status);
+	  printf ("waitid WCONTINUED|WNOWAIT on continued status %d\n",
+		  info.si_status);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_pid != pid)
 	{
-	  error (0, 0, "waitid WCONTINUED|WNOWAIT on continued pid %d != %d\n",
-		 info.si_pid, pid);
+	  printf ("waitid WCONTINUED|WNOWAIT on continued pid %d != %d\n",
+		  info.si_pid, pid);
 	  RETURN (EXIT_FAILURE);
 	}
     }
@@ -279,34 +277,32 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid WCONTINUED returned bogus value %d\n", fail);
+      printf ("waitid WCONTINUED returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WCONTINUED on continued");
+      printf ("waitid WCONTINUED on continued: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo != SIGCHLD)
 	{
-	  error (0, 0, "waitid WCONTINUED on continued signal %d\n",
-		 info.si_signo);
+	  printf ("waitid WCONTINUED on continued signal %d\n", info.si_signo);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_code != CLD_CONTINUED)
 	{
-	  error (0, 0, "waitid WCONTINUED on continued code %d\n",
-		 info.si_code);
+	  printf ("waitid WCONTINUED on continued code %d\n", info.si_code);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_status != SIGCONT)
 	{
-	  error (0, 0, "waitid WCONTINUED on continued status %d\n",
-		 info.si_status);
+	  printf ("waitid WCONTINUED on continued status %d\n",
+		  info.si_status);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_pid != pid)
 	{
-	  error (0, 0, "waitid WCONTINUED on continued pid %d != %d\n",
-		 info.si_pid, pid);
+	  printf ("waitid WCONTINUED on continued pid %d != %d\n",
+		  info.si_pid, pid);
 	  RETURN (EXIT_FAILURE);
 	}
     }
@@ -317,22 +313,20 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid returned bogus value %d\n", fail);
+      printf ("waitid returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WCONTINUED|WNOHANG on waited continued");
+      printf ("waitid WCONTINUED|WNOHANG on waited continued: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo == 0)
 	break;
       if (info.si_signo == SIGCHLD)
-	error (0, 0,
-	       "waitid WCONTINUED|WNOHANG on waited continued status %d\n",
-	       info.si_status);
+	printf ("waitid WCONTINUED|WNOHANG on waited continued status %d\n",
+		info.si_status);
       else
-	error (0, 0,
-	       "waitid WCONTINUED|WNOHANG on waited continued signal %d\n",
-	       info.si_signo);
+	printf ("waitid WCONTINUED|WNOHANG on waited continued signal %d\n",
+		info.si_signo);
       RETURN (EXIT_FAILURE);
     }
 
@@ -340,26 +334,25 @@ do_test (int argc, char *argv[])
   expecting_sigchld = 1;
   if (kill (pid, SIGSTOP) != 0)
     {
-      error (0, errno, "kill (%d, SIGSTOP)", pid);
+      printf ("kill (%d, SIGSTOP): %m\n", pid);
       RETURN (EXIT_FAILURE);
     }
   pid_t wpid = waitpid (pid, &fail, WUNTRACED);
   if (wpid < 0)
     {
-      error (0, errno, "waitpid WUNTRACED on stopped");
+      printf ("waitpid WUNTRACED on stopped: %m\n");
       RETURN (EXIT_FAILURE);
     }
   else if (wpid != pid)
     {
-      error (0, 0,
-	     "waitpid WUNTRACED on stopped returned %d != %d (status %x)",
-	     wpid, pid, fail);
+      printf ("waitpid WUNTRACED on stopped returned %d != %d (status %x)\n",
+	      wpid, pid, fail);
       RETURN (EXIT_FAILURE);
     }
   else if (!WIFSTOPPED (fail) || WIFSIGNALED (fail) || WIFEXITED (fail)
 	   || WIFCONTINUED (fail) || WSTOPSIG (fail) != SIGSTOP)
     {
-      error (0, 0, "waitpid WUNTRACED on stopped: status %x", fail);
+      printf ("waitpid WUNTRACED on stopped: status %x\n", fail);
       RETURN (EXIT_FAILURE);
     }
   CHECK_SIGCHLD ("stopped", CLD_STOPPED, SIGSTOP);
@@ -367,7 +360,7 @@ do_test (int argc, char *argv[])
   expecting_sigchld = 1;
   if (kill (pid, SIGCONT) != 0)
     {
-      error (0, errno, "kill (%d, SIGCONT)", pid);
+      printf ("kill (%d, SIGCONT): %m\n", pid);
       RETURN (EXIT_FAILURE);
     }
 
@@ -376,7 +369,7 @@ do_test (int argc, char *argv[])
 
   if (expecting_sigchld)
     {
-      error (0, 0, "no SIGCHLD seen for SIGCONT (optional)");
+      printf ("no SIGCHLD seen for SIGCONT (optional)\n");
       expecting_sigchld = 0;
     }
   else
@@ -386,24 +379,24 @@ do_test (int argc, char *argv[])
   if (wpid < 0)
     {
       if (errno == EINVAL)
-	error (0, 0, "waitpid does not support WCONTINUED");
+	printf ("waitpid does not support WCONTINUED\n");
       else
 	{
-	  error (0, errno, "waitpid WCONTINUED on continued");
+	  printf ("waitpid WCONTINUED on continued: %m\n");
 	  RETURN (EXIT_FAILURE);
 	}
     }
   else if (wpid != pid)
     {
-      error (0, 0,
-	     "waitpid WCONTINUED on continued returned %d != %d (status %x)",
+      printf ("\
+waitpid WCONTINUED on continued returned %d != %d (status %x)\n",
 	     wpid, pid, fail);
       RETURN (EXIT_FAILURE);
     }
   else if (WIFSTOPPED (fail) || WIFSIGNALED (fail) || WIFEXITED (fail)
 	   || !WIFCONTINUED (fail))
     {
-      error (0, 0, "waitpid WCONTINUED on continued: status %x", fail);
+      printf ("waitpid WCONTINUED on continued: status %x\n", fail);
       RETURN (EXIT_FAILURE);
     }
 #endif
@@ -413,7 +406,7 @@ do_test (int argc, char *argv[])
   /* Die, child, die!  */
   if (kill (pid, SIGKILL) != 0)
     {
-      error (0, errno, "kill (%d, SIGKILL)", pid);
+      printf ("kill (%d, SIGKILL): %m\n", pid);
       RETURN (EXIT_FAILURE);
     }
 
@@ -425,34 +418,30 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid WNOWAIT returned bogus value %d\n", fail);
+      printf ("waitid WNOWAIT returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WNOWAIT on killed");
+      printf ("waitid WNOWAIT on killed: %m\n");
       RETURN (errno == ENOTSUP ? EXIT_SUCCESS : EXIT_FAILURE);
     case 0:
       if (info.si_signo != SIGCHLD)
 	{
-	  error (0, 0, "waitid WNOWAIT on killed signal %d\n",
-		 info.si_signo);
+	  printf ("waitid WNOWAIT on killed signal %d\n", info.si_signo);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_code != CLD_KILLED)
 	{
-	  error (0, 0, "waitid WNOWAIT on killed code %d\n",
-		 info.si_code);
+	  printf ("waitid WNOWAIT on killed code %d\n", info.si_code);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_status != SIGKILL)
 	{
-	  error (0, 0, "waitid WNOWAIT on killed status %d\n",
-		 info.si_status);
+	  printf ("waitid WNOWAIT on killed status %d\n", info.si_status);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_pid != pid)
 	{
-	  error (0, 0, "waitid WNOWAIT on killed pid %d != %d\n",
-		 info.si_pid, pid);
+	  printf ("waitid WNOWAIT on killed pid %d != %d\n", info.si_pid, pid);
 	  RETURN (EXIT_FAILURE);
 	}
     }
@@ -470,34 +459,30 @@ do_test (int argc, char *argv[])
   switch (fail)
     {
     default:
-      error (0, 0, "waitid WNOHANG returned bogus value %d\n", fail);
+      printf ("waitid WNOHANG returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     case -1:
-      error (0, errno, "waitid WNOHANG on killed");
+      printf ("waitid WNOHANG on killed: %m\n");
       RETURN (EXIT_FAILURE);
     case 0:
       if (info.si_signo != SIGCHLD)
 	{
-	  error (0, 0, "waitid WNOHANG on killed signal %d\n",
-		 info.si_signo);
+	  printf ("waitid WNOHANG on killed signal %d\n", info.si_signo);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_code != CLD_KILLED)
 	{
-	  error (0, 0, "waitid WNOHANG on killed code %d\n",
-		 info.si_code);
+	  printf ("waitid WNOHANG on killed code %d\n", info.si_code);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_status != SIGKILL)
 	{
-	  error (0, 0, "waitid WNOHANG on killed status %d\n",
-		 info.si_status);
+	  printf ("waitid WNOHANG on killed status %d\n", info.si_status);
 	  RETURN (EXIT_FAILURE);
 	}
       if (info.si_pid != pid)
 	{
-	  error (0, 0, "waitid WNOHANG on killed pid %d != %d\n",
-		 info.si_pid, pid);
+	  printf ("waitid WNOHANG on killed pid %d != %d\n", info.si_pid, pid);
 	  RETURN (EXIT_FAILURE);
 	}
     }
@@ -507,13 +492,13 @@ do_test (int argc, char *argv[])
     {
       if (errno != ECHILD)
 	{
-	  error (0, errno, "waitid WEXITED on killed");
+	  printf ("waitid WEXITED on killed: %m\n");
 	  RETURN (EXIT_FAILURE);
 	}
     }
   else
     {
-      error (0, 0, "waitid WEXITED returned bogus value %d\n", fail);
+      printf ("waitid WEXITED returned bogus value %d\n", fail);
       RETURN (EXIT_FAILURE);
     }