From 9ff01e711b062ddafa6b157eb1bd88b255d10f68 Mon Sep 17 00:00:00 2001
From: Stefan Monnier <monnier@iro.umontreal.ca>
Date: Wed, 8 Mar 2000 23:25:41 +0000
Subject: [PATCH] This is a big redesign of failure-stack and register
 handling, prompted by bugs revealed when trying to add shy-groups.  Overall,
 what happened is that loops are now structured a little differently, groups
 can be shy and the code is a little simpler.

(enum re_opcode_t): Remove jump_past_alt, maybe_pop_jump,
push_dummy_failure and dumy_failure_jump.
Add on_failure_jump_(exclusive, loop and smart).
Also fix the comment for (start|stop)_memory since they now only take
one argument (the second has becomes unnecessary).
(print_partial_compiled_pattern): Adjust for changes in re_opcode_t.
(print_compiled_pattern): Use %ld to printf long ints and flush to make
debugging a little easier.
(union fail_stack_elt): Make the integer unsigned.
(struct fail_stack_type): Add a `frame' element.
(INIT_FAIL_STACK): Init `frame' as well.
(POP_PATTERN_OP): New macro for re_compile_fastmap.
(DEBUG_PUSH, DEBUG_POP): Remove.
(NUM_REG_ITEMS): Remove.
(NUM_NONREG_ITEMS): Adjust.
(FAILURE_PAT, FAILURE_STR, NEXT_FAILURE_HANDLE, TOP_FAILURE_HANDLE):
New macros for the cycle detection.
(ENSURE_FAIL_STACK): New macro for PUSH_FAILURE_(REG|POINT).
(PUSH_FAILURE_REG, POP_FAILURE_REG, CHECK_INFINITE_LOOP): New macros.
(PUSH_FAILURE_POINT): Don't push registers any more.
The pattern address pushed is not the destination of the jump
but the source of it instead.
(NUM_FAILURE_ITEMS): Remove.
(POP_FAILURE_POINT): Adapt to the new stack structure (i.e. pop
registers before the actual failure point).
Don't hardcode any meaning for str==NULL anymore.
(union register_info_type, REG_MATCH_NULL_STRING_P, IS_ACTIVE)
(MATCHED_SOMETHING, EVER_MATCHED_SOMETHING, SET_REGS_MATCHED): Remove.
(REG_UNSET_VALUE): Use NULL (why not?).
(compile_range): Remove declaration since it doesn't exist.
(struct compile_stack_elt_t): Remove inner_group_offset.
(old_reg(start|end), reg_info, reg_dummy, reg_info_dummy): Remove.
(regex_grow_registers): Remove dead code.
(FIXUP_ALT_JUMP): New macro.
(regex_compile): Add shy-groups
Change loops to use	on_failure_jump_smart&jump instead of
on_failure_jump&maybe_pop_jump.
Change + loops to eliminate the initial (dummy_failure_)jump.
Remove c1_base (looks like unused variable to me).
Use `jump' instead of `jump_past_alt' and don't bother with
push_dummy_failure in alternatives since it is now unnecessary.
Use FIXUP_ALT_JUMP.
Eliminate a useless `#ifdef emacs' for (re)allocating the stack.
(re_compile_fastmap): Remove dead variables i and num_regs.
Exit from loop when bufp->can_be_null rather than jumping to `done'.
Avoid jumping backwards so as to ensure termination.
Use PATTERN_STACK_EMPTY and POP_PATTERN_OP.
Improved handling of backreferences.
Remove dead code in handling of `anychar'.
(skip_noops, mutually_exclusive_p): New functions taken from the
handling of `maybe_pop_jump' in re_match_2_internal.
Slightly improve mutually_exclusive_p to handle ".+\n".
((lowest|highest)_active_reg, NO_(LOWEST|HIGHEST)_ACTIVE_REG)
Remove.
(re_match_2_internal): Use %p instead of 0x%x when printf'ing ptrs.
Don't SET_REGS_MATCHED anymore.  Remove many dead variables.
Push register (in `start_memory') on the stack rather than storing it
in old_reg(start|end).
Remove the cycle detection from `stop_memory', replaced by the use
of on_failure_jump_loop for greedy loops.
Add code for the new on_failure_jump_<foo>.
Remove ad-hoc code in `on_failure_jump' to push more registers
in the case of a loop.
Take out code from `maybe_pop_jump' into separate functions and
adapt it to the semantics of `on_failure_jump_smart'.
Remove jump_past_alt, dummy_failure_jump and push_dummy_failure.
Remove dummy_failure handling and handling of `failures to jump
to on_failure_jump' (this last one was already dead code, it seems).
((group|alt|common_op)_match_null_string_p): Remove.
---
 regex.c | 1842 +++++++++++++++++++++------------------------------------------
 1 file changed, 623 insertions(+), 1219 deletions(-)

diff --git a/regex.c b/regex.c
index 09f56a1df..809a7d242 100644
--- a/regex.c
+++ b/regex.c
@@ -2,7 +2,7 @@
    0.12.  (Implements POSIX draft P10003.2/D11.2, except for
    internationalization features.)
 
-   Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999 Free Software Foundation, Inc.
+   Copyright (C) 1993,94,95,96,97,98,2000 Free Software Foundation, Inc.
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -19,6 +19,14 @@
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    USA.	 */
 
+/* TODO:
+   - detect nasty infinite loops like "\\(\\)+?ab" when matching "ac".
+   - use `keep_string' more often than just .*\n.
+   - structure the opcode space into opcode+flag.
+   - merge with glic's regex.[ch]
+
+   That's it for now    -sm */
+
 /* AIX requires this to be the first thing in the file. */
 #if defined (_AIX) && !defined (REGEX_MALLOC)
   #pragma alloca
@@ -473,19 +481,13 @@ typedef enum
 	/* Start remembering the text that is matched, for storing in a
 	   register.  Followed by one byte with the register number, in
 	   the range 0 to one less than the pattern buffer's re_nsub
-	   field.  Then followed by one byte with the number of groups
-	   inner to this one.  (This last has to be part of the
-	   start_memory only because we need it in the on_failure_jump
-	   of re_match_2.)  */
+	   field.  */
   start_memory,
 
 	/* Stop remembering the text that is matched and store it in a
 	   memory register.  Followed by one byte with the register
 	   number, in the range 0 to one less than `re_nsub' in the
-	   pattern buffer, and one byte with the number of inner groups,
-	   just like `start_memory'.  (We need the number of inner
-	   groups here because we don't have any easy way of finding the
-	   corresponding start_memory when we're at a stop_memory.)  */
+	   pattern buffer.  */
   stop_memory,
 
 	/* Match a duplicate of something remembered. Followed by one
@@ -508,9 +510,6 @@ typedef enum
 	/* Followed by two byte relative address to which to jump.  */
   jump,
 
-	/* Same as jump, but marks the end of an alternative.  */
-  jump_past_alt,
-
 	/* Followed by two-byte relative address of place to resume at
 	   in case of failure.	*/
   on_failure_jump,
@@ -519,29 +518,24 @@ typedef enum
 	   current string position when executed.  */
   on_failure_keep_string_jump,
 
-	/* Throw away latest failure point and then jump to following
-	   two-byte relative address.  */
-  pop_failure_jump,
-
-	/* Change to pop_failure_jump if know won't have to backtrack to
-	   match; otherwise change to jump.  This is used to jump
-	   back to the beginning of a repeat.  If what follows this jump
-	   clearly won't match what the repeat does, such that we can be
-	   sure that there is no use backtracking out of repetitions
-	   already matched, then we change it to a pop_failure_jump.
-	   Followed by two-byte address.  */
-  maybe_pop_jump,
-
-	/* Jump to following two-byte address, and push a dummy failure
-	   point. This failure point will be thrown away if an attempt
-	   is made to use it for a failure.  A `+' construct makes this
-	   before the first repeat.  Also used as an intermediary kind
-	   of jump when compiling an alternative.  */
-  dummy_failure_jump,
-
-	/* Push a dummy failure point and continue.  Used at the end of
-	   alternatives.  */
-  push_dummy_failure,
+	/* Like `on_failure_jump', except that it assumes that the
+	   pattern following it is mutually exclusive with the pattern
+	   at the destination of the jump:  if one matches something,
+	   the other won't match at all.
+	   Always used via `on_failure_jump_smart'.  */
+  on_failure_jump_exclusive,
+
+	/* Just like `on_failure_jump', except that it checks that we
+	   don't get stuck in an infinite loop (matching an empty string
+	   indefinitely).  */
+  on_failure_jump_loop,
+
+        /* A smart `on_failure_jump' used for greedy * and + operators.
+	   It analyses the loop before which it is put and if the
+	   loop does not require backtracking, it changes itself to
+	   `on_failure_jump_exclusive', else it just defaults to
+	   changing itself into `on_failure_jump_loop'.  */
+  on_failure_jump_smart,
 
 	/* Followed by two-byte relative address and two-byte number n.
 	   After matching N times, jump to the address upon failure.  */
@@ -855,13 +849,11 @@ print_partial_compiled_pattern (start, end)
 	  break;
 
 	case start_memory:
-	  mcnt = *p++;
-	  printf ("/start_memory/%d/%d", mcnt, *p++);
+	  printf ("/start_memory/%d", *p++);
 	  break;
 
 	case stop_memory:
-	  mcnt = *p++;
-	  printf ("/stop_memory/%d/%d", mcnt, *p++);
+	  printf ("/stop_memory/%d", *p++);
 	  break;
 
 	case duplicate:
@@ -944,28 +936,19 @@ print_partial_compiled_pattern (start, end)
 	  printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
 	  break;
 
-	case dummy_failure_jump:
-	  extract_number_and_incr (&mcnt, &p);
-	  printf ("/dummy_failure_jump to %d", p + mcnt - start);
-	  break;
-
-	case push_dummy_failure:
-	  printf ("/push_dummy_failure");
-	  break;
-
-	case maybe_pop_jump:
+	case on_failure_jump_exclusive:
 	  extract_number_and_incr (&mcnt, &p);
-	  printf ("/maybe_pop_jump to %d", p + mcnt - start);
+	  printf ("/on_failure_jump_exclusive to %d", p + mcnt - start);
 	  break;
 
-	case pop_failure_jump:
+	case on_failure_jump_loop:
 	  extract_number_and_incr (&mcnt, &p);
-	  printf ("/pop_failure_jump to %d", p + mcnt - start);
+	  printf ("/on_failure_jump_loop to %d", p + mcnt - start);
 	  break;
 
-	case jump_past_alt:
+	case on_failure_jump_smart:
 	  extract_number_and_incr (&mcnt, &p);
-	  printf ("/jump_past_alt to %d", p + mcnt - start);
+	  printf ("/on_failure_jump_smart to %d", p + mcnt - start);
 	  break;
 
 	case jump:
@@ -1066,7 +1049,7 @@ print_compiled_pattern (bufp)
   unsigned char *buffer = bufp->buffer;
 
   print_partial_compiled_pattern (buffer, buffer + bufp->used);
-  printf ("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated);
+  printf ("%ld bytes used/%ld bytes allocated.\n", bufp->used, bufp->allocated);
 
   if (bufp->fastmap_accurate && bufp->fastmap)
     {
@@ -1082,6 +1065,7 @@ print_compiled_pattern (bufp)
   printf ("not_bol: %d\t", bufp->not_bol);
   printf ("not_eol: %d\t", bufp->not_eol);
   printf ("syntax: %d\n", bufp->syntax);
+  fflush (stdout);
   /* Perhaps we should print the translate table?  */
 }
 
@@ -1246,7 +1230,7 @@ int re_max_failures = 4000;
 union fail_stack_elt
 {
   unsigned char *pointer;
-  int integer;
+  unsigned int integer;
 };
 
 typedef union fail_stack_elt fail_stack_elt_t;
@@ -1255,11 +1239,12 @@ typedef struct
 {
   fail_stack_elt_t *stack;
   unsigned size;
-  unsigned avail;			/* Offset of next open position.  */
+  unsigned avail;		/* Offset of next open position.  */
+  unsigned frame;		/* Offset of the cur constructed frame.  */
 } fail_stack_type;
 
-#define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
-#define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
+#define PATTERN_STACK_EMPTY()     (fail_stack.avail == 0)
+#define FAIL_STACK_EMPTY()     (fail_stack.frame == 0)
 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
 
 
@@ -1278,6 +1263,7 @@ typedef struct
 									\
     fail_stack.size = INIT_FAILURE_ALLOC;				\
     fail_stack.avail = 0;						\
+    fail_stack.frame = 0;						\
   } while (0)
 
 #define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
@@ -1285,6 +1271,7 @@ typedef struct
 #define INIT_FAIL_STACK()						\
   do {									\
     fail_stack.avail = 0;						\
+    fail_stack.frame = 0;						\
   } while (0)
 
 #define RESET_FAIL_STACK()
@@ -1337,6 +1324,7 @@ typedef struct
    ? 0									\
    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,	\
       1))
+#define POP_PATTERN_OP() POP_FAILURE_POINTER ()
 
 /* Push a pointer value onto the failure stack.
    Assumes the variable `fail_stack'.  Probably should only
@@ -1362,110 +1350,105 @@ typedef struct
 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
 
-/* Used to omit pushing failure point id's when we're not debugging.  */
-#ifdef DEBUG
-#define DEBUG_PUSH PUSH_FAILURE_INT
-#define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
-#else
-#define DEBUG_PUSH(item)
-#define DEBUG_POP(item_addr)
-#endif
+/* Individual items aside from the registers.  */
+#define NUM_NONREG_ITEMS 3
+
+/* Used to examine the stack (to detect infinite loops).  */
+#define FAILURE_PAT(h) fail_stack.stack[(h) - 1].pointer
+#define FAILURE_STR(h) ((char*)fail_stack.stack[(h) - 2].pointer)
+#define NEXT_FAILURE_HANDLE(h) fail_stack.stack[(h) - 3].integer
+#define TOP_FAILURE_HANDLE() fail_stack.frame
 
 
+#define ENSURE_FAIL_STACK(space)					\
+while (REMAINING_AVAIL_SLOTS <= space) {				\
+  if (!GROW_FAIL_STACK (fail_stack))					\
+    return -2;								\
+  DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n", (fail_stack).size);\
+  DEBUG_PRINT2 ("	 slots available: %d\n", REMAINING_AVAIL_SLOTS);\
+}
+
+/* Push register NUM onto the stack.  */
+#define PUSH_FAILURE_REG(num)						\
+do {									\
+  char *destination;							\
+  ENSURE_FAIL_STACK(3);							\
+  DEBUG_PRINT4 ("    Push reg %d (spanning %p -> %p)\n",		\
+		num, regstart[num], regend[num]);			\
+  PUSH_FAILURE_POINTER (regstart[num]);					\
+  PUSH_FAILURE_POINTER (regend[num]);					\
+  PUSH_FAILURE_INT (num);						\
+} while (0)
+
+/* Pop a saved register off the stack.  */
+#define POP_FAILURE_REG()						\
+do {									\
+  int reg = POP_FAILURE_INT ();						\
+  regend[reg] = POP_FAILURE_POINTER ();					\
+  regstart[reg] = POP_FAILURE_POINTER ();				\
+  DEBUG_PRINT4 ("     Pop reg %d (spanning %p -> %p)\n",		\
+		reg, regstart[reg], regend[reg]);			\
+} while (0)
+
+/* Check that we are not stuck in an infinite loop.  */
+#define CHECK_INFINITE_LOOP(pat_cur, string_place)			\
+do {									\
+  int failure = TOP_FAILURE_HANDLE();					\
+  /* Check for infinite matching loops */				\
+  while (failure > 0 &&							\
+	 (FAILURE_STR (failure) == string_place				\
+	  || FAILURE_STR (failure) == NULL))				\
+    {									\
+      assert (FAILURE_PAT (failure) >= bufp->buffer			\
+	      && FAILURE_PAT (failure) <= bufp->buffer + bufp->used);\
+      if (FAILURE_PAT (failure) == pat_cur)				\
+	goto fail;							\
+      DEBUG_PRINT2 ("  Other pattern: %p\n", FAILURE_PAT (failure));\
+      failure = NEXT_FAILURE_HANDLE(failure);				\
+    }									\
+  DEBUG_PRINT2 ("  Other string: %p\n", FAILURE_STR (failure));		\
+} while (0)
+    
 /* Push the information about the state we will need
    if we ever fail back to it.
 
-   Requires variables fail_stack, regstart, regend, reg_info, and
+   Requires variables fail_stack, regstart, regend and
    num_regs be declared.  GROW_FAIL_STACK requires `destination' be
    declared.
 
    Does `return FAILURE_CODE' if runs out of memory.  */
 
-#define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)	\
-  do {									\
-    char *destination;							\
-    /* Must be int, so when we don't save any registers, the arithmetic	\
-       of 0 + -1 isn't done as unsigned.  */				\
-    int this_reg;							\
-									\
-    DEBUG_STATEMENT (failure_id++);					\
-    DEBUG_STATEMENT (nfailure_points_pushed++);				\
-    DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);		\
-    DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
-    DEBUG_PRINT2 ("			size: %d\n", (fail_stack).size);\
-									\
-    DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);		\
-    DEBUG_PRINT2 ("	available: %d\n", REMAINING_AVAIL_SLOTS);	\
-									\
-    /* Ensure we have enough space allocated for what we will push.  */	\
-    while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)			\
-      {									\
-	if (!GROW_FAIL_STACK (fail_stack))				\
-	  return failure_code;						\
-									\
-	DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",		\
-		       (fail_stack).size);				\
-	DEBUG_PRINT2 ("	 slots available: %d\n", REMAINING_AVAIL_SLOTS);\
-      }									\
-									\
-    /* Push the info, starting with the registers.  */			\
-    DEBUG_PRINT1 ("\n");						\
-									\
-    if (1)								\
-      for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
-	   this_reg++)							\
-	{								\
-	  DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);		\
-	  DEBUG_STATEMENT (num_regs_pushed++);				\
-									\
-	  DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);	\
-	  PUSH_FAILURE_POINTER (regstart[this_reg]);			\
-									\
-	  DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);		\
-	  PUSH_FAILURE_POINTER (regend[this_reg]);			\
-									\
-	  DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);	\
-	  DEBUG_PRINT2 (" match_null=%d",				\
-			REG_MATCH_NULL_STRING_P (reg_info[this_reg]));	\
-	  DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));	\
-	  DEBUG_PRINT2 (" matched_something=%d",			\
-			MATCHED_SOMETHING (reg_info[this_reg]));	\
-	  DEBUG_PRINT2 (" ever_matched=%d",				\
-			EVER_MATCHED_SOMETHING (reg_info[this_reg]));	\
-	  DEBUG_PRINT1 ("\n");						\
-	  PUSH_FAILURE_ELT (reg_info[this_reg].word);			\
-	}								\
-									\
-    DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
-    PUSH_FAILURE_INT (lowest_active_reg);				\
-									\
-    DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
-    PUSH_FAILURE_INT (highest_active_reg);				\
-									\
-    DEBUG_PRINT2 ("  Pushing pattern 0x%x: ", pattern_place);		\
-    DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);		\
-    PUSH_FAILURE_POINTER (pattern_place);				\
-									\
-    DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);		\
-    DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,	\
-				 size2);				\
-    DEBUG_PRINT1 ("'\n");						\
-    PUSH_FAILURE_POINTER (string_place);				\
-									\
-    DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);		\
-    DEBUG_PUSH (failure_id);						\
-  } while (0)
-
-/* This is the number of items that are pushed and popped on the stack
-   for each register.  */
-#define NUM_REG_ITEMS  3
-
-/* Individual items aside from the registers.  */
-#ifdef DEBUG
-#define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
-#else
-#define NUM_NONREG_ITEMS 4
-#endif
+#define PUSH_FAILURE_POINT(pattern, string_place)			\
+do {									\
+  char *destination;							\
+  /* Must be int, so when we don't save any registers, the arithmetic	\
+     of 0 + -1 isn't done as unsigned.  */				\
+  									\
+  DEBUG_STATEMENT (failure_id++);					\
+  DEBUG_STATEMENT (nfailure_points_pushed++);				\
+  DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);		\
+  DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);	\
+  DEBUG_PRINT2 ("			size: %d\n", (fail_stack).size);\
+  									\
+  ENSURE_FAIL_STACK (NUM_NONREG_ITEMS);					\
+  									\
+  DEBUG_PRINT1 ("\n");							\
+  									\
+  DEBUG_PRINT2 ("  Push frame index: %d\n", fail_stack.frame);		\
+  PUSH_FAILURE_INT (fail_stack.frame);					\
+  									\
+  DEBUG_PRINT2 ("  Push string %p: `", string_place);			\
+  DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, size2);\
+  DEBUG_PRINT1 ("'\n");							\
+  PUSH_FAILURE_POINTER (string_place);					\
+  									\
+  DEBUG_PRINT2 ("  Push pattern %p: ", pattern);			\
+  DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern, pend);			\
+  PUSH_FAILURE_POINTER (pattern);					\
+  									\
+  /* Close the frame by moving the frame pointer past it.  */		\
+  fail_stack.frame = fail_stack.avail;					\
+} while (0)
 
 /* Estimate the size of data pushed by a typical failure stack entry.
    An estimate is all we need, because all we use this for
@@ -1473,14 +1456,6 @@ typedef struct
 
 #define TYPICAL_FAILURE_SIZE 20
 
-/* This is how many items we actually use for a failure point.
-   It depends on the regexp.  */
-#define NUM_FAILURE_ITEMS				\
-  (((0							\
-     ? 0 : highest_active_reg - lowest_active_reg + 1)	\
-    * NUM_REG_ITEMS)					\
-   + NUM_NONREG_ITEMS)
-
 /* How many items can still be added to the stack without overflowing it.  */
 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
 
@@ -1490,19 +1465,13 @@ typedef struct
    We restore into the parameters, all of which should be lvalues:
      STR -- the saved data position.
      PAT -- the saved pattern position.
-     LOW_REG, HIGH_REG -- the highest and lowest active registers.
      REGSTART, REGEND -- arrays of string positions.
-     REG_INFO -- array of information about each subexpression.
 
    Also assumes the variables `fail_stack' and (if debugging), `bufp',
    `pend', `string1', `size1', `string2', and `size2'.	*/
 
-#define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
-{									\
-  DEBUG_STATEMENT (fail_stack_elt_t failure_id;)			\
-  int this_reg;								\
-  const unsigned char *string_temp;					\
-									\
+#define POP_FAILURE_POINT(str, pat)                                     \
+do {									\
   assert (!FAIL_STACK_EMPTY ());					\
 									\
   /* Remove failure points and point to how many regs pushed.  */	\
@@ -1510,119 +1479,35 @@ typedef struct
   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);	\
   DEBUG_PRINT2 ("		     size: %d\n", fail_stack.size);	\
 									\
-  assert (fail_stack.avail >= NUM_NONREG_ITEMS);			\
+  /* Pop the saved registers.  */					\
+  while (fail_stack.frame < fail_stack.avail)				\
+    POP_FAILURE_REG ();							\
 									\
-  DEBUG_POP (&failure_id.integer);					\
-  DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id.integer);	\
+  pat = (unsigned char *) POP_FAILURE_POINTER ();			\
+  DEBUG_PRINT2 ("  Popping pattern %p: ", pat);				\
+  DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);			\
 									\
   /* If the saved string location is NULL, it came from an		\
      on_failure_keep_string_jump opcode, and we want to throw away the	\
      saved NULL, thus retaining our current position in the string.  */	\
-  string_temp = POP_FAILURE_POINTER ();					\
-  if (string_temp != NULL)						\
-    str = (const char *) string_temp;					\
-									\
-  DEBUG_PRINT2 ("  Popping string 0x%x: `", str);			\
+  str = (char *) POP_FAILURE_POINTER ();				\
+  DEBUG_PRINT2 ("  Popping string %p: `", str);				\
   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);	\
   DEBUG_PRINT1 ("'\n");							\
 									\
-  pat = (unsigned char *) POP_FAILURE_POINTER ();			\
-  DEBUG_PRINT2 ("  Popping pattern 0x%x: ", pat);			\
-  DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);			\
-									\
-  /* Restore register info.  */						\
-  high_reg = (unsigned) POP_FAILURE_INT ();				\
-  DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);		\
-									\
-  low_reg = (unsigned) POP_FAILURE_INT ();				\
-  DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);		\
-									\
-  if (1)								\
-    for (this_reg = high_reg; this_reg >= low_reg; this_reg--)		\
-      {									\
-	DEBUG_PRINT2 ("	   Popping reg: %d\n", this_reg);		\
-									\
-	reg_info[this_reg].word = POP_FAILURE_ELT ();			\
-	DEBUG_PRINT2 ("	     info: 0x%x\n", reg_info[this_reg]);	\
-									\
-	regend[this_reg] = (const char *) POP_FAILURE_POINTER ();	\
-	DEBUG_PRINT2 ("	     end: 0x%x\n", regend[this_reg]);		\
+  fail_stack.frame = POP_FAILURE_INT ();				\
+  DEBUG_PRINT2 ("  Popping  frame index: %d\n", fail_stack.frame);	\
 									\
-	regstart[this_reg] = (const char *) POP_FAILURE_POINTER ();	\
-	DEBUG_PRINT2 ("	     start: 0x%x\n", regstart[this_reg]);	\
-      }									\
-  else									\
-    {									\
-      for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
-	{								\
-	  reg_info[this_reg].word.integer = 0;				\
-	  regend[this_reg] = 0;						\
-	  regstart[this_reg] = 0;					\
-	}								\
-      highest_active_reg = high_reg;					\
-    }									\
+  assert (fail_stack.avail >= 0);					\
+  assert (fail_stack.frame <= fail_stack.avail);			\
 									\
-  set_regs_matched_done = 0;						\
   DEBUG_STATEMENT (nfailure_points_popped++);				\
-} /* POP_FAILURE_POINT */
+} while (0) /* POP_FAILURE_POINT */
 
 
 
-/* Structure for per-register (a.k.a. per-group) information.
-   Other register information, such as the
-   starting and ending positions (which are addresses), and the list of
-   inner groups (which is a bits list) are maintained in separate
-   variables.
-
-   We are making a (strictly speaking) nonportable assumption here: that
-   the compiler will pack our bit fields into something that fits into
-   the type of `word', i.e., is something that fits into one item on the
-   failure stack.  */
-
-typedef union
-{
-  fail_stack_elt_t word;
-  struct
-  {
-      /* This field is one if this group can match the empty string,
-	 zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
-#define MATCH_NULL_UNSET_VALUE 3
-    unsigned match_null_string_p : 2;
-    unsigned is_active : 1;
-    unsigned matched_something : 1;
-    unsigned ever_matched_something : 1;
-  } bits;
-} register_info_type;
-
-#define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
-#define IS_ACTIVE(R)  ((R).bits.is_active)
-#define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
-#define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
-
-
-/* Call this when have matched a real character; it sets `matched' flags
-   for the subexpressions which we are currently inside.  Also records
-   that those subexprs have matched.  */
-#define SET_REGS_MATCHED()						\
-  do									\
-    {									\
-      if (!set_regs_matched_done)					\
-	{								\
-	  unsigned r;							\
-	  set_regs_matched_done = 1;					\
-	  for (r = lowest_active_reg; r <= highest_active_reg; r++)	\
-	    {								\
-	      MATCHED_SOMETHING (reg_info[r])				\
-		= EVER_MATCHED_SOMETHING (reg_info[r])			\
-		= 1;							\
-	    }								\
-	}								\
-    }									\
-  while (0)
-
 /* Registers are set to a sentinel when they haven't yet matched.  */
-static char reg_unset_dummy;
-#define REG_UNSET_VALUE (&reg_unset_dummy)
+#define REG_UNSET_VALUE NULL
 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
 
 /* Subroutine declarations and macros for regex_compile.  */
@@ -1631,7 +1516,6 @@ static void store_op1 (), store_op2 ();
 static void insert_op1 (), insert_op2 ();
 static boolean at_begline_loc_p (), at_endline_loc_p ();
 static boolean group_in_compile_stack ();
-static reg_errcode_t compile_range ();
 
 /* Fetch the next character in the uncompiled pattern---translating it
    if necessary.  Also cast from a signed character in the constant
@@ -1778,7 +1662,6 @@ typedef struct
 {
   pattern_offset_t begalt_offset;
   pattern_offset_t fixup_alt_jump;
-  pattern_offset_t inner_group_offset;
   pattern_offset_t laststart_offset;
   regnum_t regnum;
 } compile_stack_elt_t;
@@ -1920,11 +1803,7 @@ static fail_stack_type fail_stack;
 static int regs_allocated_size;
 
 static const char **	 regstart, **	  regend;
-static const char ** old_regstart, ** old_regend;
 static const char **best_regstart, **best_regend;
-static register_info_type *reg_info;
-static const char **reg_dummy;
-static register_info_type *reg_info_dummy;
 
 /* Make the register vectors big enough for NUM_REGS registers,
    but don't make them smaller.	 */
@@ -1937,13 +1816,8 @@ regex_grow_registers (num_regs)
     {
       RETALLOC_IF (regstart,	 num_regs, const char *);
       RETALLOC_IF (regend,	 num_regs, const char *);
-      RETALLOC_IF (old_regstart, num_regs, const char *);
-      RETALLOC_IF (old_regend,	 num_regs, const char *);
       RETALLOC_IF (best_regstart, num_regs, const char *);
       RETALLOC_IF (best_regend,	 num_regs, const char *);
-      RETALLOC_IF (reg_info,	 num_regs, register_info_type);
-      RETALLOC_IF (reg_dummy,	 num_regs, const char *);
-      RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
 
       regs_allocated_size = num_regs;
     }
@@ -1969,6 +1843,15 @@ regex_grow_registers (num_regs)
    The `fastmap' and `newline_anchor' fields are neither
    examined nor set.  */
 
+/* Insert the `jump' from the end of last alternative to "here".
+   The space for the jump has already been allocated. */
+#define FIXUP_ALT_JUMP()						\
+do {									\
+  if (fixup_alt_jump)							\
+    STORE_JUMP (jump, fixup_alt_jump, b);				\
+} while (0)
+
+
 /* Return, freeing storage we allocated.  */
 #define FREE_STACK_RETURN(value)		\
   do {							\
@@ -2042,6 +1925,7 @@ regex_compile (pattern, size, syntax, bufp)
   struct range_table_work_area range_table_work;
 
 #ifdef DEBUG
+  /* debug = 1; */
   DEBUG_PRINT1 ("\nCompiling pattern: ");
   if (debug)
     {
@@ -2258,9 +2142,8 @@ regex_compile (pattern, size, syntax, bufp)
 		    keep_string_p = true;
 		  }
 		else
-		  /* Anything else.  */
-		  STORE_JUMP (maybe_pop_jump, b, laststart - 3);
-
+		  STORE_JUMP (jump, b, laststart - 3);
+		
 		/* We've added more stuff to the buffer.  */
 		b += 3;
 	      }
@@ -2268,31 +2151,29 @@ regex_compile (pattern, size, syntax, bufp)
 	    /* On failure, jump from laststart to b + 3, which will be the
 	       end of the buffer after this jump is inserted.  */
 	    GET_BUFFER_SPACE (3);
-	    INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
-				       : on_failure_jump,
-			 laststart, b + 3);
-	    pending_exact = 0;
-	    b += 3;
-
 	    if (!zero_times_ok)
 	      {
-		/* At least one repetition is required, so insert a
-		   `dummy_failure_jump' before the initial
-		   `on_failure_jump' instruction of the loop. This
-		   effects a skip over that instruction the first time
-		   we hit that loop.  */
-		GET_BUFFER_SPACE (3);
-		INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
+		assert (many_times_ok);
+		INSERT_JUMP (on_failure_jump_smart, b - 3, b + 3);
+		pending_exact = 0;
+		b += 3;
+	      }
+	    else
+	      {
+		INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
+			     : !many_times_ok ?
+			     on_failure_jump : on_failure_jump_smart,
+			     laststart, b + 3);
+		pending_exact = 0;
 		b += 3;
 	      }
-
 	      }
 	    else		/* not greedy */
 	      { /* I wish the greedy and non-greedy cases could be merged. */
 
 		if (many_times_ok)
 		  {
-		    /* The greedy multiple match looks like a repeat..until:
+		    /* The non-greedy multiple match looks like a repeat..until:
 		       we only need a conditional jump at the end of the loop */
 		    GET_BUFFER_SPACE (3);
 		    STORE_JUMP (on_failure_jump, b, laststart);
@@ -2556,7 +2437,9 @@ regex_compile (pattern, size, syntax, bufp)
 			   Split that into two ranges,,
 			   the low one ending at 0237, and the high one
 			   starting at ...040.  */
-			int c1_base = (c1 & ~0177) | 040;
+			/*   Unless I'm missing something,
+			     this line is useless.  -sm
+			   int c1_base = (c1 & ~0177) | 040; */
 			SET_RANGE_TABLE_WORK_AREA (range_table_work, c, c1);
 			c1 = 0237;
 		      }
@@ -2678,8 +2561,31 @@ regex_compile (pattern, size, syntax, bufp)
 		goto normal_backslash;
 
 	    handle_open:
-	      bufp->re_nsub++;
-	      regnum++;
+	      {
+		int shy = 0;
+		if (p+1 < pend)
+		  {
+		    /* Look for a special (?...) construct */
+		    PATFETCH (c);
+		    if ((syntax & RE_SHY_GROUPS) && c == '?')
+		      {
+			PATFETCH (c);
+			switch (c)
+			  {
+			  case ':': shy = 1; break;
+			  default:
+			    /* Only (?:...) is supported right now. */
+			    FREE_STACK_RETURN (REG_BADPAT);
+			  }
+		      }
+		    else PATUNFETCH;
+		  }
+
+		if (!shy)
+		  {
+		    bufp->re_nsub++;
+		    regnum++;
+		  }
 
 	      if (COMPILE_STACK_FULL)
 		{
@@ -2698,17 +2604,13 @@ regex_compile (pattern, size, syntax, bufp)
 	      COMPILE_STACK_TOP.fixup_alt_jump
 		= fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
 	      COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
-	      COMPILE_STACK_TOP.regnum = regnum;
+	      COMPILE_STACK_TOP.regnum = shy ? -regnum : regnum;
 
-	      /* We will eventually replace the 0 with the number of
-		 groups inner to this one.  But do not push a
+	      /* Do not push a
 		 start_memory for groups beyond the last one we can
 		 represent in the compiled pattern.  */
-	      if (regnum <= MAX_REGNUM)
-		{
-		  COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
-		  BUF_PUSH_3 (start_memory, regnum, 0);
-		}
+	      if (regnum <= MAX_REGNUM && !shy)
+		BUF_PUSH_2 (start_memory, regnum);
 
 	      compile_stack.avail++;
 
@@ -2720,36 +2622,30 @@ regex_compile (pattern, size, syntax, bufp)
 		 clear pending_exact explicitly.  */
 	      pending_exact = 0;
 	      break;
-
+	      }
 
 	    case ')':
 	      if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
 
 	      if (COMPILE_STACK_EMPTY)
-		if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
-		  goto normal_backslash;
-		else
-		  FREE_STACK_RETURN (REG_ERPAREN);
+		{
+		  if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
+		    goto normal_backslash;
+		  else
+		    FREE_STACK_RETURN (REG_ERPAREN);
+		}
 
 	    handle_close:
-	      if (fixup_alt_jump)
-		{ /* Push a dummy failure point at the end of the
-		     alternative for a possible future
-		     `pop_failure_jump' to pop.	 See comments at
-		     `push_dummy_failure' in `re_match_2'.  */
-		  BUF_PUSH (push_dummy_failure);
-
-		  /* We allocated space for this jump when we assigned
-		     to `fixup_alt_jump', in the `handle_alt' case below.  */
-		  STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
-		}
+	      FIXUP_ALT_JUMP ();
 
 	      /* See similar code for backslashed left paren above.  */
 	      if (COMPILE_STACK_EMPTY)
-		if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
-		  goto normal_char;
-		else
-		  FREE_STACK_RETURN (REG_ERPAREN);
+		{
+		  if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
+		    goto normal_char;
+		  else
+		    FREE_STACK_RETURN (REG_ERPAREN);
+		}
 
 	      /* Since we just checked for an empty stack above, this
 		 ``can't happen''.  */
@@ -2775,15 +2671,8 @@ regex_compile (pattern, size, syntax, bufp)
 
 		/* We're at the end of the group, so now we know how many
 		   groups were inside this one.	 */
-		if (this_group_regnum <= MAX_REGNUM)
-		  {
-		    unsigned char *inner_group_loc
-		      = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
-
-		    *inner_group_loc = regnum - this_group_regnum;
-		    BUF_PUSH_3 (stop_memory, this_group_regnum,
-				regnum - this_group_regnum);
-		  }
+		if (this_group_regnum <= MAX_REGNUM && this_group_regnum > 0)
+		  BUF_PUSH_2 (stop_memory, this_group_regnum);
 	      }
 	      break;
 
@@ -2818,8 +2707,7 @@ regex_compile (pattern, size, syntax, bufp)
 		 fixup_alt_jump to right after `b', and leave behind three
 		 bytes which we'll fill in when we get to after `c'.  */
 
-	      if (fixup_alt_jump)
-		STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
+	      FIXUP_ALT_JUMP ();
 
 	      /* Mark and leave space for a jump after this alternative,
 		 to be filled in later either by next alternative or
@@ -3173,8 +3061,7 @@ regex_compile (pattern, size, syntax, bufp)
 
   /* Through the pattern now.  */
 
-  if (fixup_alt_jump)
-    STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
+  FIXUP_ALT_JUMP ();
 
   if (!COMPILE_STACK_EMPTY)
     FREE_STACK_RETURN (REG_EPAREN);
@@ -3192,8 +3079,10 @@ regex_compile (pattern, size, syntax, bufp)
 #ifdef DEBUG
   if (debug)
     {
+      re_compile_fastmap (bufp);
       DEBUG_PRINT1 ("\nCompiled pattern: \n");
       print_compiled_pattern (bufp);
+      /* debug = 0; */
     }
 #endif /* DEBUG */
 
@@ -3208,17 +3097,6 @@ regex_compile (pattern, size, syntax, bufp)
       {
 	fail_stack.size = re_max_failures * TYPICAL_FAILURE_SIZE;
 
-#ifdef emacs
-	if (! fail_stack.stack)
-	  fail_stack.stack
-	    = (fail_stack_elt_t *) xmalloc (fail_stack.size
-					    * sizeof (fail_stack_elt_t));
-	else
-	  fail_stack.stack
-	    = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
-					     (fail_stack.size
-					      * sizeof (fail_stack_elt_t)));
-#else /* not emacs */
 	if (! fail_stack.stack)
 	  fail_stack.stack
 	    = (fail_stack_elt_t *) malloc (fail_stack.size
@@ -3228,7 +3106,6 @@ regex_compile (pattern, size, syntax, bufp)
 	    = (fail_stack_elt_t *) realloc (fail_stack.stack,
 					    (fail_stack.size
 					     * sizeof (fail_stack_elt_t)));
-#endif /* not emacs */
       }
 
     regex_grow_registers (num_regs);
@@ -3388,15 +3265,13 @@ int
 re_compile_fastmap (bufp)
      struct re_pattern_buffer *bufp;
 {
-  int i, j, k;
+  int j, k;
 #ifdef MATCH_MAY_ALLOCATE
   fail_stack_type fail_stack;
 #endif
 #ifndef REGEX_MALLOC
   char *destination;
 #endif
-  /* We don't push any register information onto the failure stack.  */
-  unsigned num_regs = 0;
 
   register char *fastmap = bufp->fastmap;
   unsigned char *pattern = bufp->buffer;
@@ -3431,19 +3306,45 @@ re_compile_fastmap (bufp)
   bufp->fastmap_accurate = 1;	    /* It will be when we're done.  */
   bufp->can_be_null = 0;
 
-  while (1)
+  /* The loop below works as follows:
+     - It has a working-list kept in the PATTERN_STACK and which basically
+       starts by only containing a pointer to the first operation.
+     - If the opcode we're looking at is a match against some set of
+       chars, then we add those chars to the fastmap and go on to the
+       next work element from the worklist (done via `break').
+     - If the opcode is a control operator on the other hand, we either
+       ignore it (if it's meaningless at this point, such as `start_memory')
+       or execute it (if it's a jump).  If the jump has several destinations
+       (i.e. `on_failure_jump'), then we push the other destination onto the
+       worklist.
+     We guarantee termination by ignoring backward jumps (more or less),
+     so that `p' is monotonically increasing.  More to the point, we
+     never set `p' (or push) anything `<= p1'.  */
+
+  /* If can_be_null is set, then the fastmap will not be used anyway.  */
+  while (!bufp->can_be_null)
     {
+      /* `p1' is used as a marker of how far back a `on_failure_jump'
+	 can go without being ignored.  It is normally equal to `p'
+	 (which prevents any backward `on_failure_jump') except right
+	 after a plain `jump', to allow patterns such as:
+	    0: jump 10
+	    3..9: <body>
+	    10: on_failure_jump 3
+	 as used for the *? operator.  */
+      unsigned char *p1 = p;
+
       if (p == pend || *p == succeed)
 	{
 	  /* We have reached the (effective) end of pattern.  */
-	  if (!FAIL_STACK_EMPTY ())
+	  if (!PATTERN_STACK_EMPTY ())
 	    {
 	      bufp->can_be_null |= path_can_be_null;
 
 	      /* Reset for next path.  */
 	      path_can_be_null = true;
 
-	      p = fail_stack.stack[--fail_stack.avail].pointer;
+	      p = POP_PATTERN_OP ();
 
 	      continue;
 	    }
@@ -3457,14 +3358,13 @@ re_compile_fastmap (bufp)
       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
 	{
 
-	/* I guess the idea here is to simply not bother with a fastmap
-	   if a backreference is used, since it's too hard to figure out
-	   the fastmap for the corresponding group.  Setting
-	   `can_be_null' stops `re_search_2' from using the fastmap, so
-	   that is all we do.  */
 	case duplicate:
-	  bufp->can_be_null = 1;
-	  goto done;
+	  /* If the first character has to match a backreference, that means
+	     that the group was empty (since it already matched).  Since this
+	     is the only case that interests us here, we can assume that the
+	     backreference must match the empty string.  */
+	  p++;
+	  continue;
 
 
       /* Following are the cases which match a character.  These end
@@ -3534,9 +3434,8 @@ re_compile_fastmap (bufp)
 		 multibyte character in the range table. */
 	      int c, count;
 
-	      /* Make P points the range table.  `+ 2' is to skip flag
-                 bits for a character class.  */
-	      p += CHARSET_BITMAP_SIZE (&p[-2]) + 2;
+	      /* Make P points the range table. */
+	      p += CHARSET_BITMAP_SIZE (&p[-2]);
 
 	      /* Extract the number of ranges in range table into COUNT.  */
 	      EXTRACT_NUMBER_AND_INCR (count, p);
@@ -3630,11 +3529,6 @@ re_compile_fastmap (bufp)
 	    if (!(bufp->syntax & RE_DOT_NEWLINE))
 	      fastmap['\n'] = fastmap_newline;
 
-	    /* Return if we have already set `can_be_null'; if we have,
-	       then the fastmap is irrelevant.	Something's wrong here.	 */
-	    else if (bufp->can_be_null)
-	      goto done;
-
 	    /* Otherwise, have to check alternative paths.  */
 	    break;
 	  }
@@ -3649,7 +3543,7 @@ re_compile_fastmap (bufp)
 	  /* This match depends on text properties.  These end with
 	     aborting optimizations.  */
 	  bufp->can_be_null = 1;
-	  goto done;
+	  continue;
 #if 0
 	  k = *p++;
 	  simple_char_max = bufp->multibyte ? 0x80 : (1 << BYTEWIDTH);
@@ -3727,44 +3621,38 @@ re_compile_fastmap (bufp)
 	case wordbeg:
 	case wordend:
 #endif
-	case push_dummy_failure:
 	  continue;
 
 
 	case jump_n:
-	case pop_failure_jump:
-	case maybe_pop_jump:
 	case jump:
-	case jump_past_alt:
-	case dummy_failure_jump:
-	  EXTRACT_NUMBER_AND_INCR (j, p);
-	  p += j;
-	  if (j > 0)
-	    continue;
-
-	  /* Jump backward implies we just went through the body of a
-	     loop and matched nothing.	Opcode jumped to should be
-	     `on_failure_jump' or `succeed_n'.	Just treat it like an
-	     ordinary jump.  For a * loop, it has pushed its failure
-	     point already; if so, discard that as redundant.  */
-	  if ((re_opcode_t) *p != on_failure_jump
-	      && (re_opcode_t) *p != succeed_n)
-	    continue;
-
-	  p++;
 	  EXTRACT_NUMBER_AND_INCR (j, p);
+	  if (j < 0)
+	    /* Backward jumps can only go back to code that we've already
+	       visited.  `re_compile' should make sure this is true.  */
+	    break;
 	  p += j;
-
-	  /* If what's on the stack is where we are now, pop it.  */
-	  if (!FAIL_STACK_EMPTY ()
-	      && fail_stack.stack[fail_stack.avail - 1].pointer == p)
-	    fail_stack.avail--;
-
-	  continue;
-
+	  switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
+	    {
+	    case on_failure_jump:
+	    case on_failure_keep_string_jump:
+	    case on_failure_jump_exclusive:
+	    case on_failure_jump_loop:
+	    case on_failure_jump_smart:
+	      p++;
+	      break;
+	    default:
+	      continue;
+	    };
+	  /* Keep `p1' to allow the `on_failure_jump' we are jumping to
+	     to jump back to "just after here".  */
+	  /* Fallthrough */
 
 	case on_failure_jump:
 	case on_failure_keep_string_jump:
+	case on_failure_jump_exclusive:
+	case on_failure_jump_loop:
+	case on_failure_jump_smart:
 	handle_on_failure_jump:
 	  EXTRACT_NUMBER_AND_INCR (j, p);
 
@@ -3775,7 +3663,10 @@ re_compile_fastmap (bufp)
 	     to push such a point since we obviously won't find any more
 	     fastmap entries beyond `pend'.  Such a pattern can match
 	     the null string, though.  */
-	  if (p + j < pend)
+	  if (p + j <= p1)
+	    /* Backward jump to be ignored.  */
+	    ;
+	  else if (p + j < pend)
 	    {
 	      if (!PUSH_PATTERN_OP (p + j, fail_stack))
 		{
@@ -3817,7 +3708,7 @@ re_compile_fastmap (bufp)
 
 	case start_memory:
 	case stop_memory:
-	  p += 2;
+	  p += 1;
 	  continue;
 
 
@@ -3838,8 +3729,6 @@ re_compile_fastmap (bufp)
   /* Set `can_be_null' for the last path (also the first path, if the
      pattern is empty).	 */
   bufp->can_be_null |= path_can_be_null;
-
- done:
   RESET_FAIL_STACK ();
   return 0;
 } /* re_compile_fastmap */
@@ -4167,9 +4056,6 @@ re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
 /* Declarations and macros for re_match_2.  */
 
 static int bcmp_translate ();
-static boolean alt_match_null_string_p (),
-	       common_op_match_null_string_p (),
-	       group_match_null_string_p ();
 
 /* This converts PTR, a pointer into one of the search strings `string1'
    and `string2' into an offset from the beginning of that string.  */
@@ -4237,27 +4123,208 @@ static boolean alt_match_null_string_p (),
     REGEX_FREE_STACK (fail_stack.stack);				\
     FREE_VAR (regstart);						\
     FREE_VAR (regend);							\
-    FREE_VAR (old_regstart);						\
-    FREE_VAR (old_regend);						\
     FREE_VAR (best_regstart);						\
     FREE_VAR (best_regend);						\
-    FREE_VAR (reg_info);						\
-    FREE_VAR (reg_dummy);						\
-    FREE_VAR (reg_info_dummy);						\
   } while (0)
 #else
 #define FREE_VARIABLES() ((void)0) /* Do nothing!  But inhibit gcc warning.  */
 #endif /* not MATCH_MAY_ALLOCATE */
 
-/* These values must meet several constraints.	They must not be valid
-   register values; since we have a limit of 255 registers (because
-   we use only one byte in the pattern for the register number), we can
-   use numbers larger than 255.	 They must differ by 1, because of
-   NUM_FAILURE_ITEMS above.  And the value for the lowest register must
-   be larger than the value for the highest register, so we do not try
-   to actually save any registers when none are active.	 */
-#define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
-#define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
+
+/* Optimization routines.  */
+
+/* Jump over non-matching operations.  */
+static unsigned char *
+skip_noops (p, pend, memory)
+     unsigned char *p, *pend;
+     int memory;
+{
+  int mcnt;
+  while (p < pend)
+    {
+      switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
+	{
+	case start_memory:
+	  if (!memory)
+	    return p;
+	case stop_memory:
+	  p += 2; break;
+	case no_op:
+	  p += 1; break;
+	case jump:
+	  p += 1;
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  p += mcnt;
+	  break;
+	default:
+	  return p;
+	}
+    }
+  assert (p == pend);
+  return p;
+}
+
+/* Non-zero if "p1 matches something" implies "p2 fails".  */
+static int
+mutually_exclusive_p (bufp, p1, p2)
+     struct re_pattern_buffer *bufp;
+     unsigned char *p1, *p2;
+{
+  int multibyte = bufp->multibyte;
+  unsigned char *pend = bufp->buffer + bufp->used;
+
+  assert (p1 >= bufp->buffer && p1 <= pend
+	  && p2 >= bufp->buffer && p2 <= pend);
+
+  /* Skip over open/close-group commands.
+     If what follows this loop is a ...+ construct,
+     look at what begins its body, since we will have to
+     match at least one of that.  */
+  p2 = skip_noops (p2, pend, 1);
+  /* The same skip can be done for p1, except that skipping over
+     start_memory is not a good idea (if there's a group inside
+     the loop delimited by on_failure_jump_exclusive, then it
+     can't optimize the push away (it still works properly, but
+     slightly slower rather than faster)).  */
+  p1 = skip_noops (p1, pend, 0);
+
+  /* If we're at the end of the pattern, we can change.  */
+  if (p2 == pend)
+    {
+      switch (SWITCH_ENUM_CAST ((re_opcode_t) *p1))
+	{
+	case anychar:
+	case charset_not:
+	case charset:
+	case exactn:
+	  DEBUG_PRINT1 ("  End of pattern: fast loop.\n");
+	  return 1;
+	default:
+	  return 0;
+	}
+    }
+
+  else if ((re_opcode_t) *p2 == exactn
+	   || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
+    {
+      register unsigned int c
+	= *p2 == (unsigned char) endline ? '\n' : p2[2];
+
+      if ((re_opcode_t) *p1 == exactn)
+	{
+	  if (!(multibyte /* && (c != '\n') */
+		&& BASE_LEADING_CODE_P (c))
+	      ? c != p1[2]
+	      : (STRING_CHAR (&p2[2], pend - &p2[2])
+		 != STRING_CHAR (&p1[2], pend - &p1[2])))
+	    {
+	      DEBUG_PRINT3 ("  '%c' != '%c' => fast loop.\n", c, p1[2]);
+	      return 1;
+	    }
+	}
+
+      else if ((re_opcode_t) *p1 == charset
+	       || (re_opcode_t) *p1 == charset_not)
+	{
+	  int not = (re_opcode_t) *p1 == charset_not;
+
+	  if (multibyte /* && (c != '\n') */
+	      && BASE_LEADING_CODE_P (c))
+	    c = STRING_CHAR (&p2[2], pend - &p2[2]);
+
+	  /* Test if C is listed in charset (or charset_not)
+	     at `p1'.  */
+	  if (SINGLE_BYTE_CHAR_P (c))
+	    {
+	      if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
+		  && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
+		not = !not;
+	    }
+	  else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
+	    CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
+
+	  /* `not' is equal to 1 if c would match, which means
+	     that we can't change to pop_failure_jump.  */
+	  if (!not)
+	    {
+	      DEBUG_PRINT1 ("	 No match => fast loop.\n");
+	      return 1;
+	    }
+	}
+      else if ((re_opcode_t) *p1 == anychar
+	       && c == '\n')
+	{
+	  DEBUG_PRINT1 ("   . != \\n => fast loop.\n");
+	  return 1;
+	}
+    }
+  else if ((re_opcode_t) *p2 == charset
+	   || (re_opcode_t) *p2 == charset_not)
+    {
+      if ((re_opcode_t) *p1 == exactn)
+	/* Reuse the code above.  */
+	return mutually_exclusive_p (bufp, p2, p1);
+
+
+      /* It is hard to list up all the character in charset
+	 P2 if it includes multibyte character.  Give up in
+	 such case.  */
+      else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2))
+	{
+	  /* Now, we are sure that P2 has no range table.
+	     So, for the size of bitmap in P2, `p2[1]' is
+	     enough.	But P1 may have range table, so the
+	     size of bitmap table of P1 is extracted by
+	     using macro `CHARSET_BITMAP_SIZE'.
+
+	     Since we know that all the character listed in
+	     P2 is ASCII, it is enough to test only bitmap
+	     table of P1.  */
+
+	  if (*p1 == *p2)
+	    {
+	      int idx;
+	      /* We win if the charset inside the loop
+		 has no overlap with the one after the loop.  */
+	      for (idx = 0;
+		   (idx < (int) p2[1]
+		    && idx < CHARSET_BITMAP_SIZE (p1));
+		   idx++)
+		if ((p2[2 + idx] & p1[2 + idx]) != 0)
+		  break;
+
+	      if (idx == p2[1]
+		  || idx == CHARSET_BITMAP_SIZE (p1))
+		{
+		  DEBUG_PRINT1 ("	 No match => fast loop.\n");
+		  return 1;
+		}
+	    }
+	  else if ((re_opcode_t) *p1 == charset
+		   || (re_opcode_t) *p1 == charset_not)
+	    {
+	      int idx;
+	      /* We win if the charset_not inside the loop lists
+		 every character listed in the charset after.	 */
+	      for (idx = 0; idx < (int) p2[1]; idx++)
+		if (! (p2[2 + idx] == 0
+		       || (idx < CHARSET_BITMAP_SIZE (p1)
+			   && ((p2[2 + idx] & ~ p1[2 + idx]) == 0))))
+		  break;
+
+	      if (idx == p2[1])
+		{
+		  DEBUG_PRINT1 ("	 No match => fast loop.\n");
+		  return 1;
+		}
+	    }
+	}
+    }
+
+  /* Safe default.  */
+  return 0;
+}
+
 
 /* Matching routines.  */
 
@@ -4351,10 +4418,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
   unsigned char *p = bufp->buffer;
   register unsigned char *pend = p + bufp->used;
 
-  /* Mark the opcode just after a start_memory, so we can test for an
-     empty subpattern when we get to the stop_memory.  */
-  unsigned char *just_past_start_mem = 0;
-
   /* We use this to map every character in the string.	*/
   RE_TRANSLATE_TYPE translate = bufp->translate;
 
@@ -4363,13 +4426,11 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 
   /* Failure point stack.  Each place that can handle a failure further
      down the line pushes a failure point on this stack.  It consists of
-     restart, regend, and reg_info for all registers corresponding to
+     regstart, and regend for all registers corresponding to
      the subexpressions we're currently inside, plus the number of such
      registers, and, finally, two char *'s.  The first char * is where
      to resume scanning the pattern; the second one is where to resume
-     scanning the strings.  If the latter is zero, the failure point is
-     a ``dummy''; if a failure happens and the failure point is a dummy,
-     it gets discarded and the next next one is tried.	*/
+     scanning the strings.	*/
 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.	 */
   fail_stack_type fail_stack;
 #endif
@@ -4387,10 +4448,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
      an element for register zero.  */
   unsigned num_regs = bufp->re_nsub + 1;
 
-  /* The currently active registers.  */
-  unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG;
-  unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG;
-
   /* Information on the contents of registers. These are pointers into
      the input strings; they record just what was matched (on this
      attempt) by a subexpression part of the pattern, that is, the
@@ -4402,25 +4459,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
   const char **regstart, **regend;
 #endif
 
-  /* If a group that's operated upon by a repetition operator fails to
-     match anything, then the register for its start will need to be
-     restored because it will have been set to wherever in the string we
-     are when we last see its open-group operator.  Similarly for a
-     register's end.  */
-#ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
-  const char **old_regstart, **old_regend;
-#endif
-
-  /* The is_active field of reg_info helps us keep track of which (possibly
-     nested) subexpressions we are currently in. The matched_something
-     field of reg_info[reg_num] helps us tell whether or not we have
-     matched any of the pattern so far this time through the reg_num-th
-     subexpression.  These two fields get reset each time through any
-     loop their register is in.	 */
-#ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.	 */
-  register_info_type *reg_info;
-#endif
-
   /* The following record the register info as found in the above
      variables when we find a match better than any we've seen before.
      This happens as we backtrack through the failure points, which in
@@ -4440,15 +4478,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
      and need to test it, it's not garbage.  */
   const char *match_end = NULL;
 
-  /* This helps SET_REGS_MATCHED avoid doing redundant work.  */
-  int set_regs_matched_done = 0;
-
-  /* Used when we pop values we don't care about.  */
-#ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
-  const char **reg_dummy;
-  register_info_type *reg_info_dummy;
-#endif
-
 #ifdef DEBUG
   /* Counts the total number of registers pushed.  */
   unsigned num_regs_pushed = 0;
@@ -4468,16 +4497,10 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
     {
       regstart = REGEX_TALLOC (num_regs, const char *);
       regend = REGEX_TALLOC (num_regs, const char *);
-      old_regstart = REGEX_TALLOC (num_regs, const char *);
-      old_regend = REGEX_TALLOC (num_regs, const char *);
       best_regstart = REGEX_TALLOC (num_regs, const char *);
       best_regend = REGEX_TALLOC (num_regs, const char *);
-      reg_info = REGEX_TALLOC (num_regs, register_info_type);
-      reg_dummy = REGEX_TALLOC (num_regs, const char *);
-      reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
 
-      if (!(regstart && regend && old_regstart && old_regend && reg_info
-	    && best_regstart && best_regend && reg_dummy && reg_info_dummy))
+      if (!(regstart && regend && best_regstart && best_regend))
 	{
 	  FREE_VARIABLES ();
 	  return -2;
@@ -4487,9 +4510,7 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
     {
       /* We must initialize all our variables to NULL, so that
 	 `FREE_VARIABLES' doesn't try to free them.  */
-      regstart = regend = old_regstart = old_regend = best_regstart
-	= best_regend = reg_dummy = NULL;
-      reg_info = reg_info_dummy = (register_info_type *) NULL;
+      regstart = regend = best_regstart = best_regend = NULL;
     }
 #endif /* MATCH_MAY_ALLOCATE */
 
@@ -4505,13 +4526,7 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
      register information struct.  */
   for (mcnt = 1; mcnt < num_regs; mcnt++)
     {
-      regstart[mcnt] = regend[mcnt]
-	= old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
-
-      REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
-      IS_ACTIVE (reg_info[mcnt]) = 0;
-      MATCHED_SOMETHING (reg_info[mcnt]) = 0;
-      EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
+      regstart[mcnt] = regend[mcnt] = REG_UNSET_VALUE;
     }
 
   /* We move `string1' into `string2' if the latter's empty -- but not if
@@ -4566,7 +4581,7 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
      fails at this starting point in the input data.  */
   for (;;)
     {
-      DEBUG_PRINT2 ("\n0x%x: ", p);
+      DEBUG_PRINT2 ("\n%p: ", p);
 
       if (p == pend)
 	{ /* End of pattern means we might have succeeded.  */
@@ -4796,7 +4811,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 		}
 	      while (--mcnt);
 	    }
-	  SET_REGS_MATCHED ();
 	  break;
 
 
@@ -4828,7 +4842,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 		    && buf_ch == '\000'))
 	      goto fail;
 
-	    SET_REGS_MATCHED ();
 	    DEBUG_PRINT2 ("  Matched `%d'.\n", *d);
 	    d += buf_charlen;
 	  }
@@ -4913,195 +4926,55 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 
 	    if (!not) goto fail;
 
-	    SET_REGS_MATCHED ();
 	    d += len;
 	    break;
 	  }
 
 
 	/* The beginning of a group is represented by start_memory.
-	   The arguments are the register number in the next byte, and the
-	   number of groups inner to this one in the next.  The text
+	   The argument is the register number.  The text
 	   matched within the group is recorded (in the internal
 	   registers data structure) under the register number.	 */
 	case start_memory:
-	  DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]);
-
-	  /* Find out if this group can match the empty string.	 */
-	  p1 = p;		/* To send to group_match_null_string_p.  */
-
-	  if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
-	    REG_MATCH_NULL_STRING_P (reg_info[*p])
-	      = group_match_null_string_p (&p1, pend, reg_info);
-
-	  /* Save the position in the string where we were the last time
-	     we were at this open-group operator in case the group is
-	     operated upon by a repetition operator, e.g., with `(a*)*b'
-	     against `ab'; then we want to ignore where we are now in
-	     the string in case this attempt to match fails.  */
-	  old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
-			     ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
-			     : regstart[*p];
-	  DEBUG_PRINT2 ("  old_regstart: %d\n",
-			 POINTER_TO_OFFSET (old_regstart[*p]));
+	  DEBUG_PRINT2 ("EXECUTING start_memory %d:\n", *p);
+
+	  /* In case we need to undo this operation (via backtracking).  */
+	  PUSH_FAILURE_REG ((unsigned int)*p);
 
 	  regstart[*p] = d;
+	  regend[*p] = REG_UNSET_VALUE;	/* probably unnecessary.  -sm  */
 	  DEBUG_PRINT2 ("  regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
 
-	  IS_ACTIVE (reg_info[*p]) = 1;
-	  MATCHED_SOMETHING (reg_info[*p]) = 0;
-
-	  /* Clear this whenever we change the register activity status.  */
-	  set_regs_matched_done = 0;
-
-	  /* This is the new highest active register.  */
-	  highest_active_reg = *p;
-
-	  /* If nothing was active before, this is the new lowest active
-	     register.	*/
-	  if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
-	    lowest_active_reg = *p;
-
 	  /* Move past the register number and inner group count.  */
-	  p += 2;
-	  just_past_start_mem = p;
-
+	  p += 1;
 	  break;
 
 
 	/* The stop_memory opcode represents the end of a group.  Its
-	   arguments are the same as start_memory's: the register
-	   number, and the number of inner groups.  */
+	   argument is the same as start_memory's: the register number.  */
 	case stop_memory:
-	  DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
-
-	  /* We need to save the string position the last time we were at
-	     this close-group operator in case the group is operated
-	     upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
-	     against `aba'; then we want to ignore where we are now in
-	     the string in case this attempt to match fails.  */
-	  old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
-			   ? REG_UNSET (regend[*p]) ? d : regend[*p]
-			   : regend[*p];
-	  DEBUG_PRINT2 ("      old_regend: %d\n",
-			 POINTER_TO_OFFSET (old_regend[*p]));
+	  DEBUG_PRINT2 ("EXECUTING stop_memory %d:\n", *p);
+
+	  assert (!REG_UNSET (regstart[*p]));
+	  /* Strictly speaking, there should be code such as:
+	     
+	        assert (REG_UNSET (regend[*p]));
+		PUSH_FAILURE_REGSTOP ((unsigned int)*p);
+
+	     But the only info to be pushed is regend[*p] and it is known to
+	     be UNSET, so there really isn't anything to push.
+	     Not pushing anything, on the other hand deprives us from the
+	     guarantee that regend[*p] is UNSET since undoing this operation
+	     will not reset its value properly.  This is not important since
+	     the value will only be read on the next start_memory or at
+	     the very end and both events can only happen if this stop_memory
+	     is *not* undone.  */
 
 	  regend[*p] = d;
 	  DEBUG_PRINT2 ("      regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
 
-	  /* This register isn't active anymore.  */
-	  IS_ACTIVE (reg_info[*p]) = 0;
-
-	  /* Clear this whenever we change the register activity status.  */
-	  set_regs_matched_done = 0;
-
-	  /* If this was the only register active, nothing is active
-	     anymore.  */
-	  if (lowest_active_reg == highest_active_reg)
-	    {
-	      lowest_active_reg = NO_LOWEST_ACTIVE_REG;
-	      highest_active_reg = NO_HIGHEST_ACTIVE_REG;
-	    }
-	  else
-	    { /* We must scan for the new highest active register, since
-		 it isn't necessarily one less than now: consider
-		 (a(b)c(d(e)f)g).  When group 3 ends, after the f), the
-		 new highest active register is 1.  */
-	      unsigned char r = *p - 1;
-	      while (r > 0 && !IS_ACTIVE (reg_info[r]))
-		r--;
-
-	      /* If we end up at register zero, that means that we saved
-		 the registers as the result of an `on_failure_jump', not
-		 a `start_memory', and we jumped to past the innermost
-		 `stop_memory'.	 For example, in ((.)*) we save
-		 registers 1 and 2 as a result of the *, but when we pop
-		 back to the second ), we are at the stop_memory 1.
-		 Thus, nothing is active.  */
-	      if (r == 0)
-		{
-		  lowest_active_reg = NO_LOWEST_ACTIVE_REG;
-		  highest_active_reg = NO_HIGHEST_ACTIVE_REG;
-		}
-	      else
-		highest_active_reg = r;
-	    }
-
-	  /* If just failed to match something this time around with a
-	     group that's operated on by a repetition operator, try to
-	     force exit from the ``loop'', and restore the register
-	     information for this group that we had before trying this
-	     last match.  */
-	  if ((!MATCHED_SOMETHING (reg_info[*p])
-	       || just_past_start_mem == p - 1)
-	      && (p + 2) < pend)
-	    {
-	      boolean is_a_jump_n = false;
-
-	      p1 = p + 2;
-	      mcnt = 0;
-	      switch ((re_opcode_t) *p1++)
-		{
-		  case jump_n:
-		    is_a_jump_n = true;
-		  case pop_failure_jump:
-		  case maybe_pop_jump:
-		  case jump:
-		  case dummy_failure_jump:
-		    EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-		    if (is_a_jump_n)
-		      p1 += 2;
-		    break;
-
-		  default:
-		    /* do nothing */ ;
-		}
-	      p1 += mcnt;
-
-	      /* If the next operation is a jump backwards in the pattern
-		 to an on_failure_jump right before the start_memory
-		 corresponding to this stop_memory, exit from the loop
-		 by forcing a failure after pushing on the stack the
-		 on_failure_jump's jump in the pattern, and d.	*/
-	      if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
-		  && (re_opcode_t) p1[3] == start_memory && p1[4] == *p)
-		{
-		  /* If this group ever matched anything, then restore
-		     what its registers were before trying this last
-		     failed match, e.g., with `(a*)*b' against `ab' for
-		     regstart[1], and, e.g., with `((a*)*(b*)*)*'
-		     against `aba' for regend[3].
-
-		     Also restore the registers for inner groups for,
-		     e.g., `((a*)(b*))*' against `aba' (register 3 would
-		     otherwise get trashed).  */
-
-		  if (EVER_MATCHED_SOMETHING (reg_info[*p]))
-		    {
-		      unsigned r;
-
-		      EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
-
-		      /* Restore this and inner groups' (if any) registers.  */
-		      for (r = *p; r < *p + *(p + 1); r++)
-			{
-			  regstart[r] = old_regstart[r];
-
-			  /* xx why this test?	*/
-			  if (old_regend[r] >= regstart[r])
-			    regend[r] = old_regend[r];
-			}
-		    }
-		  p1++;
-		  EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-		  PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
-
-		  goto fail;
-		}
-	    }
-
 	  /* Move past the register number and the inner group count.  */
-	  p += 2;
+	  p += 1;
 	  break;
 
 
@@ -5162,9 +5035,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 		    : bcmp (d, d2, mcnt))
 		  goto fail;
 		d += mcnt, d2 += mcnt;
-
-		/* Do this because we've match some characters.	 */
-		SET_REGS_MATCHED ();
 	      }
 	  }
 	  break;
@@ -5224,7 +5094,7 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 
 	/* on_failure_keep_string_jump is used to optimize `.*\n'.  It
 	   pushes NULL as the value for the string on the stack.  Then
-	   `pop_failure_point' will keep the current value for the
+	   `POP_FAILURE_POINT' will keep the current value for the
 	   string, instead of restoring it.  To see why, consider
 	   matching `foo\nbar' against `.*\n'.	The .* matches the foo;
 	   then the . fails against the \n.  But the next thing we want
@@ -5239,12 +5109,47 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	   `anychar's code to do something besides goto fail in this
 	   case; that seems worse than this.  */
 	case on_failure_keep_string_jump:
-	  DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  DEBUG_PRINT3 ("EXECUTING on_failure_keep_string_jump %d (to %p):\n",
+			mcnt, p + mcnt);
+
+	  PUSH_FAILURE_POINT (p - 3, NULL);
+	  break;
 
+	case on_failure_jump_exclusive:
 	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
-	  DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
+	  DEBUG_PRINT3 ("EXECUTING on_failure_jump_exclusive %d (to %p):\n",
+			mcnt, p + mcnt);
 
-	  PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
+	  if (! FAIL_STACK_EMPTY ()
+	      && FAILURE_PAT (TOP_FAILURE_HANDLE ()) == (p - 3)
+	      && fail_stack.avail == fail_stack.frame)
+	    {
+	      /* We are trying to push failure F2 onto the stack but there
+		 is already a failure F1 pushed from the same instruction.
+		 Between F1 and now, something has matched (else this is an
+		 improper use of on_failure_jump_exclusive), so that we know
+		 that the fail-destination of F1 cannot match, hence we can
+		 pop F1 before pushing F2.  Instead of doing this pop/push,
+		 we manually turn F1 into F2.
+		 `fail_stack.avail == fail_stack.frame' makes sure
+		 that popping F1 doesn't involve registers, else
+		 this optimization cannot be done so trivially.  */
+	      assert (FAILURE_STR (TOP_FAILURE_HANDLE ()) != d);
+	      FAILURE_STR (TOP_FAILURE_HANDLE ()) = d;
+	    }
+	  else
+	    PUSH_FAILURE_POINT (p - 3, d);
+	  break;
+
+	case on_failure_jump_loop:
+	on_failure:
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  DEBUG_PRINT3 ("EXECUTING on_failure_jump_loop %d (to %p):\n",
+			mcnt, p + mcnt);
+
+	  CHECK_INFINITE_LOOP (p - 3, d);
+	  PUSH_FAILURE_POINT (p - 3, d);
 	  break;
 
 
@@ -5261,272 +5166,55 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	   the repetition text and either the following jump or
 	   pop_failure_jump back to this on_failure_jump.  */
 	case on_failure_jump:
-	on_failure:
-	  DEBUG_PRINT1 ("EXECUTING on_failure_jump");
 
 #if defined (WINDOWSNT) && defined (emacs)
 	  QUIT;
 #endif
 
 	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
-	  DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
-
-	  /* If this on_failure_jump comes right before a group (i.e.,
-	     the original * applied to a group), save the information
-	     for that group and all inner ones, so that if we fail back
-	     to this point, the group's information will be correct.
-	     For example, in \(a*\)*\1, we need the preceding group,
-	     and in \(zz\(a*\)b*\)\2, we need the inner group.	*/
-
-	  /* We can't use `p' to check ahead because we push
-	     a failure point to `p + mcnt' after we do this.  */
-	  p1 = p;
-
-	  /* We need to skip no_op's before we look for the
-	     start_memory in case this on_failure_jump is happening as
-	     the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
-	     against aba.  */
-	  while (p1 < pend && (re_opcode_t) *p1 == no_op)
-	    p1++;
-
-	  if (p1 < pend && (re_opcode_t) *p1 == start_memory)
-	    {
-	      /* We have a new highest active register now.  This will
-		 get reset at the start_memory we are about to get to,
-		 but we will have saved all the registers relevant to
-		 this repetition op, as described above.  */
-	      highest_active_reg = *(p1 + 1) + *(p1 + 2);
-	      if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
-		lowest_active_reg = *(p1 + 1);
-	    }
+	  DEBUG_PRINT3 ("EXECUTING on_failure_jump %d (to %p):\n",
+			mcnt, p + mcnt);
 
-	  DEBUG_PRINT1 (":\n");
-	  PUSH_FAILURE_POINT (p + mcnt, d, -2);
+	  PUSH_FAILURE_POINT (p -3, d);
 	  break;
 
-
-	/* A smart repeat ends with `maybe_pop_jump'.
-	   We change it to either `pop_failure_jump' or `jump'.	 */
-	case maybe_pop_jump:
+	/* This operation is used for greedy * and +.
+	   Compare the beginning of the repeat with what in the
+	   pattern follows its end. If we can establish that there
+	   is nothing that they would both match, i.e., that we
+	   would have to backtrack because of (as in, e.g., `a*a')
+	   then we can use a non-backtracking loop based on
+	   on_failure_jump_exclusive instead of on_failure_jump_loop.  */
+	case on_failure_jump_smart:
 #if defined (WINDOWSNT) && defined (emacs)
 	  QUIT;
 #endif
 	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
-	  DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
+	  DEBUG_PRINT3 ("EXECUTING on_failure_jump_smart %d (to %p).\n",
+			mcnt, p + mcnt);
 	  {
-	    register unsigned char *p2 = p;
-
-	    /* Compare the beginning of the repeat with what in the
-	       pattern follows its end. If we can establish that there
-	       is nothing that they would both match, i.e., that we
-	       would have to backtrack because of (as in, e.g., `a*a')
-	       then we can change to pop_failure_jump, because we'll
-	       never have to backtrack.
-
-	       This is not true in the case of alternatives: in
-	       `(a|ab)*' we do need to backtrack to the `ab' alternative
-	       (e.g., if the string was `ab').	But instead of trying to
-	       detect that here, the alternative has put on a dummy
-	       failure point which is what we will end up popping.  */
-
-	    /* Skip over open/close-group commands.
-	       If what follows this loop is a ...+ construct,
-	       look at what begins its body, since we will have to
-	       match at least one of that.  */
-	    while (1)
-	      {
-		if (p2 + 2 < pend
-		    && ((re_opcode_t) *p2 == stop_memory
-			|| (re_opcode_t) *p2 == start_memory))
-		  p2 += 3;
-		else if (p2 + 6 < pend
-			 && (re_opcode_t) *p2 == dummy_failure_jump)
-		  p2 += 6;
-		else
-		  break;
-	      }
+	    unsigned char *p1 = p; /* Next operation.  */
+	    unsigned char *p2 = p + mcnt; /* Destination of the jump.  */
 
-	    p1 = p + mcnt;
-	    /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
-	       to the `maybe_finalize_jump' of this case.  Examine what
-	       follows.	 */
+	    p -= 3;		/* Reset so that we will re-execute the
+				   instruction once it's been changed. */
 
-	    /* If we're at the end of the pattern, we can change.  */
-	    if (p2 == pend)
+	    /* DEBUG_STATEMENT (debug = 1); */
+	    if (mutually_exclusive_p (bufp, p1, p2))
 	      {
-		/* Consider what happens when matching ":\(.*\)"
-		   against ":/".  I don't really understand this code
-		   yet.	 */
-		p[-3] = (unsigned char) pop_failure_jump;
-		DEBUG_PRINT1
-		  ("  End of pattern: change to `pop_failure_jump'.\n");
+		/* Use a fast `on_failure_keep_string_jump' loop.  */
+		*p = (unsigned char) on_failure_jump_exclusive;
+		/* STORE_NUMBER (p2 - 2, mcnt + 3); */
 	      }
-
-	    else if ((re_opcode_t) *p2 == exactn
-		     || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
+	    else
 	      {
-		register unsigned int c
-		  = *p2 == (unsigned char) endline ? '\n' : p2[2];
-
-		if ((re_opcode_t) p1[3] == exactn)
-		  {
-		    if (!(multibyte /* && (c != '\n') */
-			  && BASE_LEADING_CODE_P (c))
-			? c != p1[5]
-			: (STRING_CHAR (&p2[2], pend - &p2[2])
-			   != STRING_CHAR (&p1[5], pend - &p1[5])))
-		  {
-		    p[-3] = (unsigned char) pop_failure_jump;
-		    DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
-				  c, p1[5]);
-		  }
-		  }
-
-		else if ((re_opcode_t) p1[3] == charset
-			 || (re_opcode_t) p1[3] == charset_not)
-		  {
-		    int not = (re_opcode_t) p1[3] == charset_not;
-
-		    if (multibyte /* && (c != '\n') */
-			&& BASE_LEADING_CODE_P (c))
-		      c = STRING_CHAR (&p2[2], pend - &p2[2]);
-
-		    /* Test if C is listed in charset (or charset_not)
-		       at `&p1[3]'.  */
-		    if (SINGLE_BYTE_CHAR_P (c))
-		      {
-			if (c < CHARSET_BITMAP_SIZE (&p1[3]) * BYTEWIDTH
-			&& p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
-		      not = !not;
-		      }
-		    else if (CHARSET_RANGE_TABLE_EXISTS_P (&p1[3]))
-		      CHARSET_LOOKUP_RANGE_TABLE (not, c, &p1[3]);
-
-		    /* `not' is equal to 1 if c would match, which means
-			that we can't change to pop_failure_jump.  */
-		    if (!not)
-		      {
-			p[-3] = (unsigned char) pop_failure_jump;
-			DEBUG_PRINT1 ("	 No match => pop_failure_jump.\n");
-		      }
-		  }
-	      }
-	    else if ((re_opcode_t) *p2 == charset)
-	      {
-		if ((re_opcode_t) p1[3] == exactn)
-		  {
-		    register unsigned int c = p1[5];
-		    int not = 0;
-
-		    if (multibyte && BASE_LEADING_CODE_P (c))
-		      c = STRING_CHAR (&p1[5], pend - &p1[5]);
-
-		    /* Test if C is listed in charset at `p2'.	*/
-		    if (SINGLE_BYTE_CHAR_P (c))
-		      {
-			if (c < CHARSET_BITMAP_SIZE (p2) * BYTEWIDTH
-			    && (p2[2 + c / BYTEWIDTH]
-				& (1 << (c % BYTEWIDTH))))
-			  not = !not;
-		      }
-		    else if (CHARSET_RANGE_TABLE_EXISTS_P (p2))
-		      CHARSET_LOOKUP_RANGE_TABLE (not, c, p2);
-
-		    if (!not)
-		  {
-		    p[-3] = (unsigned char) pop_failure_jump;
-			DEBUG_PRINT1 ("	 No match => pop_failure_jump.\n");
-		      }
-		  }
-
-		/* It is hard to list up all the character in charset
-		   P2 if it includes multibyte character.  Give up in
-		   such case.  */
-		else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2))
-		  {
-		    /* Now, we are sure that P2 has no range table.
-		       So, for the size of bitmap in P2, `p2[1]' is
-		       enough.	But P1 may have range table, so the
-		       size of bitmap table of P1 is extracted by
-		       using macro `CHARSET_BITMAP_SIZE'.
-
-		       Since we know that all the character listed in
-		       P2 is ASCII, it is enough to test only bitmap
-		       table of P1.  */
-
-		    if ((re_opcode_t) p1[3] == charset_not)
-		  {
-		    int idx;
-			/* We win if the charset_not inside the loop lists
-			   every character listed in the charset after.	 */
-		    for (idx = 0; idx < (int) p2[1]; idx++)
-		      if (! (p2[2 + idx] == 0
-				 || (idx < CHARSET_BITMAP_SIZE (&p1[3])
-				 && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
-			break;
-
-		    if (idx == p2[1])
-		      {
-			p[-3] = (unsigned char) pop_failure_jump;
-			DEBUG_PRINT1 ("	 No match => pop_failure_jump.\n");
-		      }
-		  }
-		else if ((re_opcode_t) p1[3] == charset)
-		  {
-		    int idx;
-		    /* We win if the charset inside the loop
-		       has no overlap with the one after the loop.  */
-		    for (idx = 0;
-			     (idx < (int) p2[1]
-			      && idx < CHARSET_BITMAP_SIZE (&p1[3]));
-			 idx++)
-		      if ((p2[2 + idx] & p1[5 + idx]) != 0)
-			break;
-
-			if (idx == p2[1]
-			    || idx == CHARSET_BITMAP_SIZE (&p1[3]))
-		      {
-			p[-3] = (unsigned char) pop_failure_jump;
-			DEBUG_PRINT1 ("	 No match => pop_failure_jump.\n");
-		      }
-		  }
+		/* Default to a safe `on_failure_jump' loop.  */
+		DEBUG_PRINT1 ("  smart default => slow loop.\n");
+		*p = (unsigned char) on_failure_jump_loop;
 	      }
+	    /* DEBUG_STATEMENT (debug = 0); */
 	  }
-	  }
-	  p -= 2;		/* Point at relative address again.  */
-	  if ((re_opcode_t) p[-1] != pop_failure_jump)
-	    {
-	      p[-1] = (unsigned char) jump;
-	      DEBUG_PRINT1 ("  Match => jump.\n");
-	      goto unconditional_jump;
-	    }
-	/* Note fall through.  */
-
-
-	/* The end of a simple repeat has a pop_failure_jump back to
-	   its matching on_failure_jump, where the latter will push a
-	   failure point.  The pop_failure_jump takes off failure
-	   points put on by this pop_failure_jump's matching
-	   on_failure_jump; we got through the pattern to here from the
-	   matching on_failure_jump, so didn't fail.  */
-	case pop_failure_jump:
-	  {
-	    /* We need to pass separate storage for the lowest and
-	       highest registers, even though we don't care about the
-	       actual values.  Otherwise, we will restore only one
-	       register from the stack, since lowest will == highest in
-	       `pop_failure_point'.  */
-	    unsigned dummy_low_reg, dummy_high_reg;
-	    unsigned char *pdummy;
-	    const char *sdummy;
-
-	    DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
-	    POP_FAILURE_POINT (sdummy, pdummy,
-			       dummy_low_reg, dummy_high_reg,
-			       reg_dummy, reg_dummy, reg_info_dummy);
-	  }
-	  /* Note fall through.	 */
-
+	  break;
 
 	/* Unconditionally jump (without popping any failure points).  */
 	case jump:
@@ -5537,42 +5225,10 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	  EXTRACT_NUMBER_AND_INCR (mcnt, p);	/* Get the amount to jump.  */
 	  DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
 	  p += mcnt;				/* Do the jump.	 */
-	  DEBUG_PRINT2 ("(to 0x%x).\n", p);
+	  DEBUG_PRINT2 ("(to %p).\n", p);
 	  break;
 
 
-	/* We need this opcode so we can detect where alternatives end
-	   in `group_match_null_string_p' et al.  */
-	case jump_past_alt:
-	  DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
-	  goto unconditional_jump;
-
-
-	/* Normally, the on_failure_jump pushes a failure point, which
-	   then gets popped at pop_failure_jump.  We will end up at
-	   pop_failure_jump, also, and with a pattern of, say, `a+', we
-	   are skipping over the on_failure_jump, so we have to push
-	   something meaningless for pop_failure_jump to pop.  */
-	case dummy_failure_jump:
-	  DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
-	  /* It doesn't matter what we push for the string here.  What
-	     the code at `fail' tests is the value for the pattern.  */
-	  PUSH_FAILURE_POINT (0, 0, -2);
-	  goto unconditional_jump;
-
-
-	/* At the end of an alternative, we need to push a dummy failure
-	   point in case we are followed by a `pop_failure_jump', because
-	   we don't want the failure point for the alternative to be
-	   popped.  For example, matching `(a|ab)*' against `aab'
-	   requires that we match the `ab' alternative.	 */
-	case push_dummy_failure:
-	  DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
-	  /* See comments just above at `dummy_failure_jump' about the
-	     two zeroes.  */
-	  PUSH_FAILURE_POINT (0, 0, -2);
-	  break;
-
 	/* Have to succeed matching what follows at least n times.
 	   After that, handle like `on_failure_jump'.  */
 	case succeed_n:
@@ -5586,11 +5242,11 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	       mcnt--;
 	       p += 2;
 	       STORE_NUMBER_AND_INCR (p, mcnt);
-	       DEBUG_PRINT3 ("	Setting 0x%x to %d.\n", p, mcnt);
+	       DEBUG_PRINT3 ("	Setting %p to %d.\n", p, mcnt);
 	    }
 	  else if (mcnt == 0)
 	    {
-	      DEBUG_PRINT2 ("  Setting two bytes from 0x%x to no_op.\n", p+2);
+	      DEBUG_PRINT2 ("  Setting two bytes from %p to no_op.\n", p+2);
 	      p[2] = (unsigned char) no_op;
 	      p[3] = (unsigned char) no_op;
 	      goto on_failure;
@@ -5620,7 +5276,7 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	    EXTRACT_NUMBER_AND_INCR (mcnt, p);
 	    p1 = p + mcnt;
 	    EXTRACT_NUMBER_AND_INCR (mcnt, p);
-	    DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p1, mcnt);
+	    DEBUG_PRINT3 ("  Setting %p to %d.\n", p1, mcnt);
 	    STORE_NUMBER (p1, mcnt);
 	    break;
 	  }
@@ -5837,7 +5493,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	    goto fail;
 	    d += len;
 	  }
-	  SET_REGS_MATCHED ();
 	  break;
 
 	case notsyntaxspec:
@@ -5868,7 +5523,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	    goto fail;
 	    d += len;
 	  }
-	  SET_REGS_MATCHED ();
 	  break;
 
 	case categoryspec:
@@ -5887,7 +5541,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	      goto fail;
 	    d += len;
 	  }
-	  SET_REGS_MATCHED ();
 	  break;
 
 	case notcategoryspec:
@@ -5906,7 +5559,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	      goto fail;
 	    d += len;
 	  }
-	  SET_REGS_MATCHED ();
           break;
 
 #else /* not emacs */
@@ -5915,7 +5567,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	  PREFETCH ();
           if (!WORDCHAR_P (d))
             goto fail;
-	  SET_REGS_MATCHED ();
           d++;
 	  break;
 
@@ -5924,7 +5575,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 	  PREFETCH ();
 	  if (WORDCHAR_P (d))
             goto fail;
-          SET_REGS_MATCHED ();
           d++;
 	  break;
 #endif /* not emacs */
@@ -5941,44 +5591,40 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
       QUIT;
 #endif
       if (!FAIL_STACK_EMPTY ())
-	{ /* A restart point is known.  Restore to that state.  */
+	{
+	  char *str;
+	  unsigned char *pat;
+	  /* A restart point is known.  Restore to that state.  */
           DEBUG_PRINT1 ("\nFAIL:\n");
-          POP_FAILURE_POINT (d, p,
-                             lowest_active_reg, highest_active_reg,
-                             regstart, regend, reg_info);
+          POP_FAILURE_POINT (str, pat);
+	  switch (SWITCH_ENUM_CAST ((re_opcode_t) *pat++))
+	    {
+	    case on_failure_keep_string_jump:
+	      assert (str == NULL);
+	      goto continue_failure_jump;
+
+	    case on_failure_jump_exclusive:
+	      /* If something has matched, the alternative will not match,
+		 so we might as well keep popping right away.  */
+	      if (0 /* d != str && d != string2 */) /* Don't bother.  -sm */
+		/* (d == string2 && str == end1) => (d =~ str) */
+		goto fail;
+	      /* Fallthrough */
+
+	    case on_failure_jump_loop:
+	    case on_failure_jump:
+	    case succeed_n:
+	      d = str;
+	    continue_failure_jump:
+	      EXTRACT_NUMBER_AND_INCR (mcnt, pat);
+	      p = pat + mcnt;
+	      break;
 
-          /* If this failure point is a dummy, try the next one.  */
-          if (!p)
-	    goto fail;
+	    default:
+	      abort();
+	    }
 
-          /* If we failed to the end of the pattern, don't examine *p.  */
-	  assert (p <= pend);
-          if (p < pend)
-            {
-              boolean is_a_jump_n = false;
-
-              /* If failed to a backwards jump that's part of a repetition
-                 loop, need to pop this failure point and use the next one.  */
-              switch ((re_opcode_t) *p)
-                {
-                case jump_n:
-                  is_a_jump_n = true;
-                case maybe_pop_jump:
-                case pop_failure_jump:
-                case jump:
-                  p1 = p + 1;
-                  EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-                  p1 += mcnt;
-
-                  if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
-                      || (!is_a_jump_n
-                          && (re_opcode_t) *p1 == on_failure_jump))
-                    goto fail;
-                  break;
-                default:
-                  /* do nothing */ ;
-                }
-            }
+	  assert (p >= bufp->buffer && p <= pend);
 
           if (d >= string1 && d <= end1)
 	    dend = end_match_1;
@@ -5997,248 +5643,6 @@ re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
 
 /* Subroutine definitions for re_match_2.  */
 
-
-/* We are passed P pointing to a register number after a start_memory.
-
-   Return true if the pattern up to the corresponding stop_memory can
-   match the empty string, and false otherwise.
-
-   If we find the matching stop_memory, sets P to point to one past its number.
-   Otherwise, sets P to an undefined byte less than or equal to END.
-
-   We don't handle duplicates properly (yet).  */
-
-static boolean
-group_match_null_string_p (p, end, reg_info)
-    unsigned char **p, *end;
-    register_info_type *reg_info;
-{
-  int mcnt;
-  /* Point to after the args to the start_memory.  */
-  unsigned char *p1 = *p + 2;
-
-  while (p1 < end)
-    {
-      /* Skip over opcodes that can match nothing, and return true or
-	 false, as appropriate, when we get to one that can't, or to the
-         matching stop_memory.  */
-
-      switch ((re_opcode_t) *p1)
-        {
-        /* Could be either a loop or a series of alternatives.  */
-        case on_failure_jump:
-          p1++;
-          EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-
-          /* If the next operation is not a jump backwards in the
-	     pattern.  */
-
-	  if (mcnt >= 0)
-	    {
-              /* Go through the on_failure_jumps of the alternatives,
-                 seeing if any of the alternatives cannot match nothing.
-                 The last alternative starts with only a jump,
-                 whereas the rest start with on_failure_jump and end
-                 with a jump, e.g., here is the pattern for `a|b|c':
-
-                 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
-                 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
-                 /exactn/1/c
-
-                 So, we have to first go through the first (n-1)
-                 alternatives and then deal with the last one separately.  */
-
-
-              /* Deal with the first (n-1) alternatives, which start
-                 with an on_failure_jump (see above) that jumps to right
-                 past a jump_past_alt.  */
-
-              while ((re_opcode_t) p1[mcnt-3] == jump_past_alt)
-                {
-                  /* `mcnt' holds how many bytes long the alternative
-                     is, including the ending `jump_past_alt' and
-                     its number.  */
-
-                  if (!alt_match_null_string_p (p1, p1 + mcnt - 3,
-				                      reg_info))
-                    return false;
-
-                  /* Move to right after this alternative, including the
-		     jump_past_alt.  */
-                  p1 += mcnt;
-
-                  /* Break if it's the beginning of an n-th alternative
-                     that doesn't begin with an on_failure_jump.  */
-                  if ((re_opcode_t) *p1 != on_failure_jump)
-                    break;
-
-		  /* Still have to check that it's not an n-th
-		     alternative that starts with an on_failure_jump.  */
-		  p1++;
-                  EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-                  if ((re_opcode_t) p1[mcnt-3] != jump_past_alt)
-                    {
-		      /* Get to the beginning of the n-th alternative.  */
-                      p1 -= 3;
-                      break;
-                    }
-                }
-
-              /* Deal with the last alternative: go back and get number
-                 of the `jump_past_alt' just before it.  `mcnt' contains
-                 the length of the alternative.  */
-              EXTRACT_NUMBER (mcnt, p1 - 2);
-
-              if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info))
-                return false;
-
-              p1 += mcnt;	/* Get past the n-th alternative.  */
-            } /* if mcnt > 0 */
-          break;
-
-
-        case stop_memory:
-	  assert (p1[1] == **p);
-          *p = p1 + 2;
-          return true;
-
-
-        default:
-          if (!common_op_match_null_string_p (&p1, end, reg_info))
-            return false;
-        }
-    } /* while p1 < end */
-
-  return false;
-} /* group_match_null_string_p */
-
-
-/* Similar to group_match_null_string_p, but doesn't deal with alternatives:
-   It expects P to be the first byte of a single alternative and END one
-   byte past the last. The alternative can contain groups.  */
-
-static boolean
-alt_match_null_string_p (p, end, reg_info)
-    unsigned char *p, *end;
-    register_info_type *reg_info;
-{
-  int mcnt;
-  unsigned char *p1 = p;
-
-  while (p1 < end)
-    {
-      /* Skip over opcodes that can match nothing, and break when we get
-         to one that can't.  */
-
-      switch ((re_opcode_t) *p1)
-        {
-	/* It's a loop.  */
-        case on_failure_jump:
-          p1++;
-          EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-          p1 += mcnt;
-          break;
-
-	default:
-          if (!common_op_match_null_string_p (&p1, end, reg_info))
-            return false;
-        }
-    }  /* while p1 < end */
-
-  return true;
-} /* alt_match_null_string_p */
-
-
-/* Deals with the ops common to group_match_null_string_p and
-   alt_match_null_string_p.
-
-   Sets P to one after the op and its arguments, if any.  */
-
-static boolean
-common_op_match_null_string_p (p, end, reg_info)
-    unsigned char **p, *end;
-    register_info_type *reg_info;
-{
-  int mcnt;
-  boolean ret;
-  int reg_no;
-  unsigned char *p1 = *p;
-
-  switch ((re_opcode_t) *p1++)
-    {
-    case no_op:
-    case begline:
-    case endline:
-    case begbuf:
-    case endbuf:
-    case wordbeg:
-    case wordend:
-    case wordbound:
-    case notwordbound:
-#ifdef emacs
-    case before_dot:
-    case at_dot:
-    case after_dot:
-#endif
-      break;
-
-    case start_memory:
-      reg_no = *p1;
-      assert (reg_no > 0 && reg_no <= MAX_REGNUM);
-      ret = group_match_null_string_p (&p1, end, reg_info);
-
-      /* Have to set this here in case we're checking a group which
-         contains a group and a back reference to it.  */
-
-      if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
-        REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
-
-      if (!ret)
-        return false;
-      break;
-
-    /* If this is an optimized succeed_n for zero times, make the jump.  */
-    case jump:
-      EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-      if (mcnt >= 0)
-        p1 += mcnt;
-      else
-        return false;
-      break;
-
-    case succeed_n:
-      /* Get to the number of times to succeed.  */
-      p1 += 2;
-      EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-
-      if (mcnt == 0)
-        {
-          p1 -= 4;
-          EXTRACT_NUMBER_AND_INCR (mcnt, p1);
-          p1 += mcnt;
-        }
-      else
-        return false;
-      break;
-
-    case duplicate:
-      if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
-        return false;
-      break;
-
-    case set_number_at:
-      p1 += 4;
-
-    default:
-      /* All other opcodes mean we cannot match the empty string.  */
-      return false;
-  }
-
-  *p = p1;
-  return true;
-} /* common_op_match_null_string_p */
-
-
 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
    bytes; nonzero otherwise.  */
 
-- 
2.11.0