Latest from Jeffrey Ollie.

Infinite failure stack, some bugs fixed (fastmap, star_jump, register bug).

2 files changed, 1680 insertions, 1473 deletions

diff --git a/Modules/regexpr.c b/Modules/regexpr.c
index 1eebdb8..c74ece3 100644
--- a/Modules/regexpr.c
+++ b/Modules/regexpr.c
@@ -1,34 +1,43 @@
-/*
-
-regexpr.c
-
-Author: Tatu Ylonen <ylo@ngs.fi>
-
-Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
-
-Permission to use, copy, modify, distribute, and sell this software
-and its documentation for any purpose is hereby granted without fee,
-provided that the above copyright notice appear in all copies.  This
-software is provided "as is" without express or implied warranty.
-
-Created: Thu Sep 26 17:14:05 1991 ylo
-Last modified: Mon Nov  4 17:06:48 1991 ylo
-Ported to Think C: 19 Jan 1992 guido@cwi.nl
-
-This code draws many ideas from the regular expression packages by
-Henry Spencer of the University of Toronto and Richard Stallman of the
-Free Software Foundation.
-
-Emacs-specific code and syntax table code is almost directly borrowed
-from GNU regexp.
-
-*/
+/* regexpr.c
+ *
+ * Author: Tatu Ylonen <ylo@ngs.fi>
+ *
+ * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies.
+ * This software is provided "as is" without express or implied
+ * warranty.
+ *
+ * Created: Thu Sep 26 17:14:05 1991 ylo
+ * Last modified: Mon Nov  4 17:06:48 1991 ylo
+ * Ported to Think C: 19 Jan 1992 guido@cwi.nl
+ *
+ * This code draws many ideas from the regular expression packages by
+ * Henry Spencer of the University of Toronto and Richard Stallman of
+ * the Free Software Foundation.
+ *
+ * Emacs-specific code and syntax table code is almost directly borrowed
+ * from GNU regexp.
+ *
+ * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
+ * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
+ * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
+ * probably one or two others that I'm forgetting.
+ *
+ * $Id$ */
 
 #include "config.h" /* For Win* specific redefinition of printf c.s. */
 
-#include "myproto.h" /* For Py_PROTO macro --Guido */
+#include "myproto.h" /* For PROTO macro --Guido */
 
 #include <stdio.h>
+
+#ifndef NDEBUG
+#define NDEBUG 1
+#endif
+
 #include <assert.h>
 #include "regexpr.h"
 
@@ -48,8 +57,316 @@ char *realloc();
 #endif /* __STDC__ */
 #endif /* THINK_C */
 
-#define MACRO_BEGIN do {
-#define MACRO_END } while (0)
+/* The stack implementation is taken from an idea by Andrew Kuchling.
+ * It's a doubly linked list of arrays. The advantages of this over a
+ * simple linked list are that the number of mallocs required are
+ * reduced. It also makes it possible to statically allocate enough
+ * space so that small patterns don't ever need to call malloc.
+ *
+ * The advantages over a single array is that is periodically
+ * realloced when more space is needed is that we avoid ever copying
+ * the stack. */
+
+/* item_t is the basic stack element.  Defined as a union of
+ * structures so that both registers, failure points, and counters can
+ * be pushed/popped from the stack.  There's nothing built into the
+ * item to keep track of whether a certain stack item is a register, a
+ * failure point, or a counter. */
+
+typedef union item_t
+{
+      struct
+      {
+	    int num;
+	    int level;
+	    char *start;
+	    char *end;
+      } reg;
+      struct
+      {
+	    int count;
+	    int level;
+	    int phantom;
+	    char *code;
+	    char *text;
+      } fail;
+      struct
+      {
+	    int num;
+	    int level;
+	    int count;
+      } cntr;
+} item_t;
+
+#define STACK_PAGE_SIZE 256
+#define NUM_REGISTERS 256
+
+/* A 'page' of stack items. */
+
+typedef struct item_page_t
+{
+      item_t items[STACK_PAGE_SIZE];
+      struct item_page_t *prev;
+      struct item_page_t *next;
+} item_page_t;
+
+
+typedef struct match_state
+{
+      /* Structure to encapsulate the stack. */
+      struct
+      {
+	    /* index into the curent page.  If index == 0 and you need
+	     * to pop and item, move to the previous page and set
+	     * index = STACK_PAGE_SIZE - 1.  Otherwise decrement index
+	     * to push a page. If index == STACK_PAGE_SIZE and you
+	     * need to push a page move to the next page and set index
+	     * = 0. If there is no new next page, allocate a new page
+	     * and link it in. Otherwise, increment index to push a
+	     * page. */
+	    int index;
+	    item_page_t *current; /* Pointer to the current page. */
+	    item_page_t first; /* First page is statically allocated. */
+      } stack;
+      char *start[NUM_REGISTERS];
+      char *end[NUM_REGISTERS];
+
+      int changed[NUM_REGISTERS];
+      /* The number of registers that have been pushed onto the stack
+       * since the last failure point. */
+      int count;
+      /* Used to control when registers need to be pushed onto the
+       * stack. */
+      int level;
+      /* The number of failure points on the stack. */
+      int point;
+} match_state;
+
+/* Discard the top 'count' stack items. */
+
+#define STACK_DISCARD(stack, count, on_error) \
+stack.index -= count; \
+while (stack.index < 0) \
+{ \
+   if (stack.current->prev == NULL) \
+      on_error; \
+   stack.current = stack.current->prev; \
+   stack.index += STACK_PAGE_SIZE; \
+}
+
+/* Store a pointer to the previous item on the stack. Used to pop an
+ * item off of the stack. */
+
+#define STACK_PREV(stack, top, on_error) \
+if (stack.index == 0) \
+{ \
+   if (stack.current->prev == NULL) \
+      on_error; \
+   stack.current = stack.current->prev; \
+   stack.index = STACK_PAGE_SIZE - 1; \
+} \
+else \
+   stack.index--; \
+top = &(stack.current->items[stack.index])
+
+/* Store a pointer to the next item on the stack. Used to push an item
+ * on to the stack. */
+
+#define STACK_NEXT(stack, top, on_error) \
+if (stack.index == STACK_PAGE_SIZE) \
+{ \
+   if (stack.current->next == NULL) \
+   { \
+      stack.current->next = malloc(sizeof(item_page_t)); \
+      if (stack.current->next == NULL) \
+         on_error; \
+      stack.current->next->prev = stack.current; \
+      stack.current->next->next = NULL; \
+   } \
+   stack.current = stack.current->next; \
+   stack.index = 0; \
+} \
+top = &(stack.current->items[stack.index++])
+
+/* Store a pointer to the item that is 'count' items back in the
+ * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
+ * STACK_TOP(stack, top, on_error).  */
+
+#define STACK_BACK(stack, top, count, on_error) \
+{ \
+   int index; \
+   item_page_t *current; \
+   current = stack.current; \
+   index = stack.index - (count); \
+   while (index < 0) \
+   { \
+      if (current->prev == NULL) \
+	 on_error; \
+      current = current->prev; \
+      index += STACK_PAGE_SIZE; \
+   } \
+   top = &(current->items[index]); \
+}
+
+/* Store a pointer to the top item on the stack. Execute the
+ * 'on_error' code if there are no items on the stack. */
+
+#define STACK_TOP(stack, top, on_error) \
+if (stack.index == 0) \
+{ \
+   if (stack.current->prev == NULL) \
+      on_error; \
+   top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
+} \
+else \
+   top = &(stack.current->items[stack.index - 1])
+
+/* Test to see if the stack is empty */
+
+#define STACK_EMPTY(stack) ((stack.index == 0) && \
+			    (stack.current->prev == NULL))
+
+
+/* Initialize a state object */
+
+#define NEW_STATE(state) \
+memset(&state, 0, sizeof(match_state)); \
+state.stack.current = &state.stack.first; \
+state.level = 1
+
+/* Free any memory that might have been malloc'd */
+
+#define FREE_STATE(state) \
+while(state.stack.first.next != NULL) \
+{ \
+   state.stack.current = state.stack.first.next; \
+   state.stack.first.next = state.stack.current->next; \
+   free(state.stack.current); \
+}
+
+/* Return the start of register 'reg' */
+
+#define GET_REG_START(state, reg) (state.start[reg])
+
+/* Return the end of register 'reg' */
+
+#define GET_REG_END(state, reg) (state.end[reg])
+
+/* Set the start of register 'reg'. If the state of the register needs
+ * saving, push it on the stack. */
+
+#define SET_REG_START(state, reg, text, on_error) \
+if(state.changed[reg] < state.level) \
+{ \
+   item_t *item; \
+   STACK_NEXT(state.stack, item, on_error); \
+   item->reg.num = reg; \
+   item->reg.start = state.start[reg]; \
+   item->reg.end = state.end[reg]; \
+   item->reg.level = state.changed[reg]; \
+   state.changed[reg] = state.level; \
+   state.count++; \
+} \
+state.start[reg] = text
+
+/* Set the end of register 'reg'. If the state of the register needs
+ * saving, push it on the stack. */
+
+#define SET_REG_END(state, reg, text, on_error) \
+if(state.changed[reg] < state.level) \
+{ \
+   item_t *item; \
+   STACK_NEXT(state.stack, item, on_error); \
+   item->reg.num = reg; \
+   item->reg.start = state.start[reg]; \
+   item->reg.end = state.end[reg]; \
+   item->reg.level = state.changed[reg]; \
+   state.changed[reg] = state.level; \
+   state.count++; \
+} \
+state.end[reg] = text
+
+#define PUSH_FAILURE(state, xcode, xtext, on_error) \
+{ \
+   item_t *item; \
+   STACK_NEXT(state.stack, item, on_error); \
+   item->fail.code = xcode; \
+   item->fail.text = xtext; \
+   item->fail.count = state.count; \
+   item->fail.level = state.level; \
+   item->fail.phantom = 0; \
+   state.count = 0; \
+   state.level++; \
+   state.point++; \
+}
+
+/* Update the last failure point with a new position in the text. */
+
+/* #define UPDATE_FAILURE(state, xtext, on_error) \ */
+/* { \ */
+/*    item_t *item; \ */
+/*    STACK_DISCARD(state.stack, state.count, on_error); \ */
+/*    STACK_TOP(state.stack, item, on_error); \ */
+/*    item->fail.text = xtext; \ */
+/*    state.count = 0; \ */
+/* } */
+
+/* #define UPDATE_FAILURE(state, xtext, on_error) \ */
+/* { \ */
+/*    item_t *item; \ */
+/*    STACK_BACK(state.stack, item, state.count + 1, on_error); \ */
+/*    item->fail.text = xtext; \ */
+/* } */
+
+#define UPDATE_FAILURE(state, xtext, on_error) \
+{ \
+   item_t *item; \
+   STACK_BACK(state.stack, item, state.count + 1, on_error); \
+   if (!item->fail.phantom) \
+   { \
+      item_t *item2; \
+      STACK_NEXT(state.stack, item2, on_error); \
+      item2->fail.code = item->fail.code; \
+      item2->fail.text = xtext; \
+      item2->fail.count = state.count; \
+      item2->fail.level = state.level; \
+      item2->fail.phantom = 1; \
+      state.count = 0; \
+      state.level++; \
+      state.point++; \
+   } \
+   else \
+   { \
+      STACK_DISCARD(state.stack, state.count, on_error); \
+      STACK_TOP(state.stack, item, on_error); \
+      item->fail.text = xtext; \
+      state.count = 0; \
+      state.level++; \
+   } \
+}
+
+#define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
+{ \
+   item_t *item; \
+   do \
+   { \
+      while(state.count > 0) \
+      { \
+         STACK_PREV(state.stack, item, on_error); \
+         state.start[item->reg.num] = item->reg.start; \
+         state.end[item->reg.num] = item->reg.end; \
+         state.changed[item->reg.num] = item->reg.level; \
+         state.count--; \
+      } \
+      STACK_PREV(state.stack, item, on_empty); \
+      xcode = item->fail.code; \
+      xtext = item->fail.text; \
+      state.count = item->fail.count; \
+      state.level = item->fail.level; \
+      state.point--; \
+   } \
+   while (item->fail.text == NULL); \
+}
 
 enum regexp_compiled_ops /* opcodes for compiled regexp */
 {
@@ -73,9 +390,6 @@ enum regexp_compiled_ops /* opcodes for compiled regexp */
   Cwordend,		/* match at end of word */
   Cwordbound,		/* match if at word boundary */
   Cnotwordbound,	/* match if not at word boundary */
-#ifdef emacs
-  Cemacs_at_dot,	/* emacs only: matches at dot */
-#endif /* emacs */
   Csyntaxspec,		/* matches syntax code (1 byte follows) */
   Cnotsyntaxspec	/* matches if syntax code does not match (1 byte foll)*/
 };
@@ -106,11 +420,6 @@ enum regexp_syntax_op	/* syntax codes for plain and quoted characters */
   Rwordend,		/* end of word */
   Rwordbound,		/* word bound */
   Rnotwordbound,	/* not word bound */
-#ifdef emacs
-  Remacs_at_dot,	/* emacs: at dot */
-  Remacs_syntaxspec,	/* syntaxspec */
-  Remacs_notsyntaxspec,	/* notsyntaxspec */
-#endif /* emacs */
   Rnum_ops
 };
 
@@ -126,99 +435,70 @@ static int regexp_ansi_sequences;
 #define NUM_LEVELS  5    /* number of precedence levels in use */
 #define MAX_NESTING 100  /* max nesting level of operators */
 
-#ifdef emacs
-
-/* This code is for emacs compatibility only. */
-
-#include "config.h"
-#include "lisp.h"
-#include "buffer.h"
-#include "syntax.h"
-
-/* emacs defines NULL in some strange way? */
-#undef NULL
-#define NULL 0
-
-#else /* emacs */
-
 #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
 #define Sword 1
 
-#ifdef SYNTAX_TABLE
-char *re_syntax_table;
-#else
 static char re_syntax_table[256];
-#endif /* SYNTAX_TABLE */
 
-#endif /* emacs */
-
-static void re_compile_initialize Py_PROTO((void));
-static void re_compile_initialize()
+static void re_compile_initialize(void)
 {
-  int a;
-  
-#if !defined(emacs) && !defined(SYNTAX_TABLE)
-  static int syntax_table_inited = 0;
+   int a;
   
-  if (!syntax_table_inited)
-    {
+   static int syntax_table_inited = 0;
+   
+   if (!syntax_table_inited)
+   {
       syntax_table_inited = 1;
       memset(re_syntax_table, 0, 256);
       for (a = 'a'; a <= 'z'; a++)
-	re_syntax_table[a] = Sword;
+	 re_syntax_table[a] = Sword;
       for (a = 'A'; a <= 'Z'; a++)
-	re_syntax_table[a] = Sword;
+	 re_syntax_table[a] = Sword;
       for (a = '0'; a <= '9'; a++)
-	re_syntax_table[a] = Sword;
-    }
-#endif /* !emacs && !SYNTAX_TABLE */
-  re_compile_initialized = 1;
-  for (a = 0; a < 256; a++)
-    {
+	 re_syntax_table[a] = Sword;
+   }
+   re_compile_initialized = 1;
+   for (a = 0; a < 256; a++)
+   {
       regexp_plain_ops[a] = Rnormal;
       regexp_quoted_ops[a] = Rnormal;
-    }
-  for (a = '0'; a <= '9'; a++)
-    regexp_quoted_ops[a] = Rmemory;
-  regexp_plain_ops['\134'] = Rquote;
-  if (regexp_syntax & RE_NO_BK_PARENS)
-    {
+   }
+   for (a = '0'; a <= '9'; a++)
+      regexp_quoted_ops[a] = Rmemory;
+   regexp_plain_ops['\134'] = Rquote;
+   if (regexp_syntax & RE_NO_BK_PARENS)
+   {
       regexp_plain_ops['('] = Ropenpar;
       regexp_plain_ops[')'] = Rclosepar;
-    }
-  else
-    {
+   }
+   else
+   {
       regexp_quoted_ops['('] = Ropenpar;
       regexp_quoted_ops[')'] = Rclosepar;
-    }
-  if (regexp_syntax & RE_NO_BK_VBAR)
-    regexp_plain_ops['\174'] = Ror;
-  else
-    regexp_quoted_ops['\174'] = Ror;
-  regexp_plain_ops['*'] = Rstar;
-  if (regexp_syntax & RE_BK_PLUS_QM)
-    {
+   }
+   if (regexp_syntax & RE_NO_BK_VBAR)
+      regexp_plain_ops['\174'] = Ror;
+   else
+      regexp_quoted_ops['\174'] = Ror;
+   regexp_plain_ops['*'] = Rstar;
+   if (regexp_syntax & RE_BK_PLUS_QM)
+   {
       regexp_quoted_ops['+'] = Rplus;
       regexp_quoted_ops['?'] = Roptional;
-    }
-  else
-    {
+   }
+   else
+   {
       regexp_plain_ops['+'] = Rplus;
       regexp_plain_ops['?'] = Roptional;
-    }
-  if (regexp_syntax & RE_NEWLINE_OR)
-    regexp_plain_ops['\n'] = Ror;
-  regexp_plain_ops['\133'] = Ropenset;
-  regexp_plain_ops['\136'] = Rbol;
-  regexp_plain_ops['$'] = Reol;
-  regexp_plain_ops['.'] = Ranychar;
-  if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
-    {
-#ifdef emacs
-      regexp_quoted_ops['='] = Remacs_at_dot;
-      regexp_quoted_ops['s'] = Remacs_syntaxspec;
-      regexp_quoted_ops['S'] = Remacs_notsyntaxspec;
-#endif /* emacs */
+   }
+   if (regexp_syntax & RE_NEWLINE_OR)
+      regexp_plain_ops['\n'] = Ror;
+   regexp_plain_ops['\133'] = Ropenset;
+   regexp_plain_ops['\136'] = Rbol;
+   regexp_plain_ops['$'] = Reol;
+   regexp_plain_ops['.'] = Ranychar;
+   if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
+   {
       regexp_quoted_ops['w'] = Rwordchar;
       regexp_quoted_ops['W'] = Rnotwordchar;
       regexp_quoted_ops['<'] = Rwordbeg;
@@ -227,86 +507,469 @@ static void re_compile_initialize()
       regexp_quoted_ops['B'] = Rnotwordbound;
       regexp_quoted_ops['`'] = Rbegbuf;
       regexp_quoted_ops['\''] = Rendbuf;
-    }
-  if (regexp_syntax & RE_ANSI_HEX)
-    regexp_quoted_ops['v'] = Rextended_memory;
-  for (a = 0; a < Rnum_ops; a++)
-    regexp_precedences[a] = 4;
-  if (regexp_syntax & RE_TIGHT_VBAR)
-    {
+   }
+   if (regexp_syntax & RE_ANSI_HEX)
+      regexp_quoted_ops['v'] = Rextended_memory;
+   for (a = 0; a < Rnum_ops; a++)
+      regexp_precedences[a] = 4;
+   if (regexp_syntax & RE_TIGHT_VBAR)
+   {
       regexp_precedences[Ror] = 3;
       regexp_precedences[Rbol] = 2;
       regexp_precedences[Reol] = 2;
-    }
-  else
-    {
+   }
+   else
+   {
       regexp_precedences[Ror] = 2;
       regexp_precedences[Rbol] = 3;
       regexp_precedences[Reol] = 3;
-    }
-  regexp_precedences[Rclosepar] = 1;
-  regexp_precedences[Rend] = 0;
-  regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
-  regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
+   }
+   regexp_precedences[Rclosepar] = 1;
+   regexp_precedences[Rend] = 0;
+   regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
+   regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
 }
 
-int re_set_syntax(syntax)
-int syntax;
+int re_set_syntax(int syntax)
 {
-  int ret;
+   int ret;
+   
+   ret = regexp_syntax;
+   regexp_syntax = syntax;
+   re_syntax = syntax; /* Exported copy */
+   re_compile_initialize();
+   return ret;
+}
+
+static int hex_char_to_decimal(int ch)
+{
+   if (ch >= '0' && ch <= '9')
+      return ch - '0';
+   if (ch >= 'a' && ch <= 'f')
+      return ch - 'a' + 10;
+   if (ch >= 'A' && ch <= 'F')
+      return ch - 'A' + 10;
+   return 16;
+}
 
-  ret = regexp_syntax;
-  regexp_syntax = syntax;
-  re_syntax = syntax; /* Exported copy */
-  re_compile_initialize();
-  return ret;
+static void re_compile_fastmap_aux(char *code,
+				   int pos,
+				   char *visited,
+				   char *can_be_null,
+				   char *fastmap)
+{
+   int a;
+   int b;
+   int syntaxcode;
+   
+   if (visited[pos])
+      return;  /* we have already been here */
+   visited[pos] = 1;
+   for (;;)
+      switch (code[pos++])
+      {
+	 case Cend:
+	 {
+	    *can_be_null = 1;
+	    return;
+	 }
+	 case Cbol:
+	 case Cbegbuf:
+	 case Cendbuf:
+	 case Cwordbeg:
+	 case Cwordend:
+	 case Cwordbound:
+	 case Cnotwordbound:
+	 {
+	    break;
+	 }
+	 case Csyntaxspec:
+	 {
+	    syntaxcode = code[pos++];
+	    for (a = 0; a < 256; a++)
+	       if (SYNTAX(a) == syntaxcode)
+		  fastmap[a] = 1;
+	    return;
+	 }
+	 case Cnotsyntaxspec:
+	 {
+	    syntaxcode = code[pos++];
+	    for (a = 0; a < 256; a++)
+	       if (SYNTAX(a) != syntaxcode)
+		  fastmap[a] = 1;
+	    return;
+	 }
+	 case Ceol:
+	 {
+	    fastmap['\n'] = 1;
+	    if (*can_be_null == 0)
+	       *can_be_null = 2; /* can match null, but only at end of buffer*/
+	    return;
+	 }
+	 case Cset:
+	 {
+	    for (a = 0; a < 256/8; a++)
+	       if (code[pos + a] != 0)
+		  for (b = 0; b < 8; b++)
+		     if (code[pos + a] & (1 << b))
+			fastmap[(a << 3) + b] = 1;
+	    pos += 256/8;
+	    return;
+	 }
+	 case Cexact:
+	 {
+	    fastmap[(unsigned char)code[pos]] = 1;
+	    return;
+	 }
+	 case Canychar:
+	 {
+	    for (a = 0; a < 256; a++)
+	       if (a != '\n')
+		  fastmap[a] = 1;
+	    return;
+	 }
+	 case Cstart_memory:
+	 case Cend_memory:
+	 {
+	    pos++;
+	    break;
+	 }
+	 case Cmatch_memory:
+	 {
+	    for (a = 0; a < 256; a++)
+	       fastmap[a] = 1;
+	    *can_be_null = 1;
+	    return;
+	 }
+	 case Cjump:
+	 case Cdummy_failure_jump:
+	 case Cupdate_failure_jump:
+	 case Cstar_jump:
+	 {
+	    a = (unsigned char)code[pos++];
+	    a |= (unsigned char)code[pos++] << 8;
+	    pos += (int)(short)a;
+	    if (visited[pos])
+	    {
+	       /* argh... the regexp contains empty loops.  This is not
+		  good, as this may cause a failure stack overflow when
+		  matching.  Oh well. */
+	       /* this path leads nowhere; pursue other paths. */
+	       return;
+	    }
+	    visited[pos] = 1;
+	    break;
+	 }
+	 case Cfailure_jump:
+	 {
+	    a = (unsigned char)code[pos++];
+	    a |= (unsigned char)code[pos++] << 8;
+	    a = pos + (int)(short)a;
+	    re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
+	    break;
+	 }
+	 default:
+	 {
+	    abort();  /* probably some opcode is missing from this switch */
+	    /*NOTREACHED*/
+	 }
+      }
 }
 
-static int hex_char_to_decimal Py_PROTO((int));
-static int hex_char_to_decimal(ch)
-int ch;
+static int re_do_compile_fastmap(char *buffer,
+				 int used,
+				 int pos,
+				 char *can_be_null,
+				 char *fastmap)
 {
-  if (ch >= '0' && ch <= '9')
-    return ch - '0';
-  if (ch >= 'a' && ch <= 'f')
-    return ch - 'a' + 10;
-  if (ch >= 'A' && ch <= 'F')
-    return ch - 'A' + 10;
-  return 16;
+   char small_visited[512], *visited;
+   
+   if (used <= sizeof(small_visited))
+      visited = small_visited;
+   else
+   {
+      visited = malloc(used);
+      if (!visited)
+	 return 0;
+   }
+   *can_be_null = 0;
+   memset(fastmap, 0, 256);
+   memset(visited, 0, used);
+   re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
+   if (visited != small_visited)
+      free(visited);
+   return 1;
 }
 
-char *re_compile_pattern(regex, size, bufp)
-char *regex;
-int size;
-regexp_t bufp;
+void re_compile_fastmap(regexp_t bufp)
 {
-  int a, pos, op, current_level, level, opcode;
-  int pattern_offset = 0, alloc;
-  int starts[NUM_LEVELS * MAX_NESTING], starts_base;
-  int future_jumps[MAX_NESTING], num_jumps;
-  unsigned char ch = '\0';
-  char *pattern, *translate;
-  int next_register, paren_depth, num_open_registers, open_registers[RE_NREGS];
-  int beginning_context;
-
-#define NEXTCHAR(var)			\
-  MACRO_BEGIN				\
-    if (pos >= size)			\
-      goto ends_prematurely;		\
-    (var) = regex[pos];			\
-    pos++;				\
-  MACRO_END
-
-#define ALLOC(amount)				\
-  MACRO_BEGIN					\
-    if (pattern_offset+(amount) > alloc)	\
-      {						\
-	alloc += 256 + (amount);		\
-	pattern = realloc(pattern, alloc);	\
-	if (!pattern)				\
-	  goto out_of_memory;			\
-      }						\
-  MACRO_END
+   if (!bufp->fastmap || bufp->fastmap_accurate)
+      return;
+   assert(bufp->used > 0);
+   if (!re_do_compile_fastmap(bufp->buffer,
+			      bufp->used,
+			      0,
+			      &bufp->can_be_null,
+			      bufp->fastmap))
+      return;
+   if (bufp->buffer[0] == Cbol)
+      bufp->anchor = 1;   /* begline */
+   else
+      if (bufp->buffer[0] == Cbegbuf)
+	 bufp->anchor = 2; /* begbuf */
+      else
+	 bufp->anchor = 0; /* none */
+   bufp->fastmap_accurate = 1;
+}
+
+/* 
+ * star is coded as:
+ * 1: failure_jump 2
+ *    ... code for operand of star
+ *    star_jump 1
+ * 2: ... code after star
+ *
+ * We change the star_jump to update_failure_jump if we can determine
+ * that it is safe to do so; otherwise we change it to an ordinary
+ * jump.
+ *
+ * plus is coded as
+ *
+ *    jump 2
+ * 1: failure_jump 3
+ * 2: ... code for operand of plus
+ *    star_jump 1
+ * 3: ... code after plus
+ *
+ * For star_jump considerations this is processed identically to star.
+ *
+ */
+
+static int re_optimize_star_jump(regexp_t bufp, char *code)
+{
+   char map[256];
+   char can_be_null;
+   char *p1;
+   char *p2;
+   char ch;
+   int a;
+   int b;
+
+   a = (unsigned char)*code++;
+   a |= (unsigned char)*code++ << 8;
+   a = (int)(short)a;
+
+   p1 = code + a + 3; /* skip the failure_jump */
+   assert(p1[-3] == Cfailure_jump);
+   p2 = code;
+   /* p1 points inside loop, p2 points to after loop */
+   if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
+			      p2 - bufp->buffer, &can_be_null, map))
+      goto make_normal_jump;
+   
+   /* If we might introduce a new update point inside the
+    * loop, we can't optimize because then update_jump would
+    * update a wrong failure point.  Thus we have to be
+    * quite careful here.
+    */
+      
+   /* loop until we find something that consumes a character */
+  loop_p1:
+   switch (*p1++)
+   {
+      case Cbol:
+      case Ceol:
+      case Cbegbuf:
+      case Cendbuf:
+      case Cwordbeg:
+      case Cwordend:
+      case Cwordbound:
+      case Cnotwordbound:
+      {
+	 goto loop_p1;
+      }
+      case Cstart_memory:
+      case Cend_memory:
+      {
+	 p1++;
+	 goto loop_p1;
+      }
+      case Cexact:
+      {
+	 ch = (unsigned char)*p1++;
+	 if (map[ch])
+	    goto make_normal_jump;
+	 break;
+      }
+      case Canychar:
+      {
+	 for (b = 0; b < 256; b++)
+	    if (b != '\n' && map[b])
+	       goto make_normal_jump;
+	 break;
+      }
+      case Cset:
+      {
+	 for (b = 0; b < 256; b++)
+	    if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
+	       goto make_normal_jump;
+	 p1 += 256/8;
+	 break;
+      }
+      default:
+      {
+	 goto make_normal_jump;
+      }
+   }
+   /* now we know that we can't backtrack. */
+   while (p1 != p2 - 3)
+   {
+      switch (*p1++)
+      {
+	 case Cend:
+	 {
+	    return 0;
+	 }
+	 case Cbol:
+	 case Ceol:
+	 case Canychar:
+	 case Cbegbuf:
+	 case Cendbuf:
+	 case Cwordbeg:
+	 case Cwordend:
+	 case Cwordbound:
+	 case Cnotwordbound:
+	 {
+	    break;
+	 }
+	 case Cset:
+	 {
+	    p1 += 256/8;
+	    break;
+	 }
+	 case Cexact:
+	 case Cstart_memory:
+	 case Cend_memory:
+	 case Cmatch_memory:
+	 case Csyntaxspec:
+	 case Cnotsyntaxspec:
+	 {
+	    p1++;
+	    break;
+	 }
+	 case Cjump:
+	 case Cstar_jump:
+	 case Cfailure_jump:
+	 case Cupdate_failure_jump:
+	 case Cdummy_failure_jump:
+	 {
+	    goto make_normal_jump;
+	 }
+	 default:
+	 {
+	    return 0;
+	    break;
+	 }
+      }
+   }
+
+  make_update_jump:
+   code -= 3;
+   a += 3;  /* jump to after the Cfailure_jump */
+   code[0] = Cupdate_failure_jump;
+   code[1] = a & 0xff;
+   code[2] = a >> 8;
+   return 1;
+
+  make_normal_jump:
+   code -= 3;
+   *code = Cjump;
+   return 1;
+}
+
+static int re_optimize(regexp_t bufp)
+{
+   char *code;
+
+   code = bufp->buffer;
+
+   while(1)
+   {
+      switch (*code++)
+      {
+	 case Cend:
+	 {
+	    return 1;
+	 }
+	 case Canychar:
+	 case Cbol:
+	 case Ceol:
+	 case Cbegbuf:
+	 case Cendbuf:
+	 case Cwordbeg:
+	 case Cwordend:
+	 case Cwordbound:
+	 case Cnotwordbound:
+	 {
+	    break;
+	 }
+	 case Cset:
+	 {
+	    code += 256/8;
+	    break;
+	 }
+	 case Cexact:
+	 case Cstart_memory:
+	 case Cend_memory:
+	 case Cmatch_memory:
+	 case Csyntaxspec:
+	 case Cnotsyntaxspec:
+	 {
+	    code++;
+	    break;
+	 }
+	 case Cstar_jump:
+	 {
+	    if (!re_optimize_star_jump(bufp, code))
+	    {
+	       return 0;
+	    }
+	    /* fall through */
+	 }
+	 case Cupdate_failure_jump:
+	 case Cjump:
+	 case Cdummy_failure_jump:
+	 case Cfailure_jump:
+	 {
+	    code += 2;
+	    break;
+	 }
+	 default:
+	 {
+	    return 0;
+	 }
+      }
+   }
+}
+
+#define NEXTCHAR(var) \
+{ \
+   if (pos >= size) \
+      goto ends_prematurely; \
+   (var) = regex[pos]; \
+   pos++; \
+}
+
+#define ALLOC(amount) \
+{ \
+   if (pattern_offset+(amount) > alloc) \
+   { \
+      alloc += 256 + (amount); \
+      pattern = realloc(pattern, alloc); \
+      if (!pattern) \
+	 goto out_of_memory; \
+   } \
+}
 
 #define STORE(ch) pattern[pattern_offset++] = (ch)
 
@@ -314,450 +977,522 @@ regexp_t bufp;
 
 #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
 
-#define PUSH_LEVEL_STARTS if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
-		            starts_base += NUM_LEVELS;			\
-                          else						\
-			    goto too_complex
+#define PUSH_LEVEL_STARTS \
+   if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
+      starts_base += NUM_LEVELS; \
+   else \
+      goto too_complex
 
 #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
 
-#define PUT_ADDR(offset,addr)				\
-  MACRO_BEGIN						\
-    int disp = (addr) - (offset) - 2;			\
-    pattern[(offset)] = disp & 0xff;			\
-    pattern[(offset)+1] = (disp>>8) & 0xff;		\
-  MACRO_END
-
-#define INSERT_JUMP(pos,type,addr)			\
-  MACRO_BEGIN						\
-    int a, p = (pos), t = (type), ad = (addr);		\
-    for (a = pattern_offset - 1; a >= p; a--)		\
-      pattern[a + 3] = pattern[a];			\
-    pattern[p] = t;					\
-    PUT_ADDR(p+1,ad);					\
-    pattern_offset += 3;				\
-  MACRO_END
+#define PUT_ADDR(offset,addr) \
+{ \
+   int disp = (addr) - (offset) - 2; \
+   pattern[(offset)] = disp & 0xff; \
+   pattern[(offset)+1] = (disp>>8) & 0xff; \
+}
 
+#define INSERT_JUMP(pos,type,addr) \
+{ \
+   int a, p = (pos), t = (type), ad = (addr); \
+   for (a = pattern_offset - 1; a >= p; a--) \
+      pattern[a + 3] = pattern[a]; \
+   pattern[p] = t; \
+   PUT_ADDR(p+1,ad); \
+   pattern_offset += 3; \
+}
 #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
 
-#define SET_FIELDS				\
-  MACRO_BEGIN					\
-    bufp->allocated = alloc;			\
-    bufp->buffer = pattern;			\
-    bufp->used = pattern_offset;		\
-  MACRO_END
+#define SET_FIELDS \
+{ \
+   bufp->allocated = alloc; \
+   bufp->buffer = pattern; \
+   bufp->used = pattern_offset; \
+}
     
-#define GETHEX(var)						\
-  MACRO_BEGIN							\
-    char gethex_ch, gethex_value;				\
-    NEXTCHAR(gethex_ch);					\
-    gethex_value = hex_char_to_decimal(gethex_ch);		\
-    if (gethex_value == 16)					\
-      goto hex_error;						\
-    NEXTCHAR(gethex_ch);					\
-    gethex_ch = hex_char_to_decimal(gethex_ch);			\
-    if (gethex_ch == 16)					\
-      goto hex_error;						\
-    (var) = gethex_value * 16 + gethex_ch;			\
-  MACRO_END
-
-#define ANSI_TRANSLATE(ch)				\
-  MACRO_BEGIN						\
-    switch (ch)						\
-      {							\
-      case 'a':						\
-      case 'A':						\
-	ch = 7; /* audible bell */			\
-	break;						\
-      case 'b':						\
-      case 'B':						\
-	ch = 8; /* backspace */				\
-	break;						\
-      case 'f':						\
-      case 'F':						\
-	ch = 12; /* form feed */			\
-	break;						\
-      case 'n':						\
-      case 'N':						\
-	ch = 10; /* line feed */			\
-	break;						\
-      case 'r':						\
-      case 'R':						\
-	ch = 13; /* carriage return */			\
-	break;						\
-      case 't':						\
-      case 'T':						\
-	ch = 9; /* tab */				\
-	break;						\
-      case 'v':						\
-      case 'V':						\
-	ch = 11; /* vertical tab */			\
-	break;						\
-      case 'x': /* hex code */				\
-      case 'X':						\
-	GETHEX(ch);					\
-	break;						\
-      default:						\
-	/* other characters passed through */		\
-	if (translate)					\
-	  ch = translate[(unsigned char)ch];		\
-	break;						\
-      }							\
-  MACRO_END
-
-  if (!re_compile_initialized)
-    re_compile_initialize();
-  bufp->used = 0;
-  bufp->fastmap_accurate = 0;
-  bufp->uses_registers = 0;
-  translate = bufp->translate;
-  pattern = bufp->buffer;
-  alloc = bufp->allocated;
-  if (alloc == 0 || pattern == NULL)
-    {
+#define GETHEX(var) \
+{ \
+   char gethex_ch, gethex_value; \
+   NEXTCHAR(gethex_ch); \
+   gethex_value = hex_char_to_decimal(gethex_ch); \
+   if (gethex_value == 16) \
+      goto hex_error; \
+   NEXTCHAR(gethex_ch); \
+   gethex_ch = hex_char_to_decimal(gethex_ch); \
+   if (gethex_ch == 16) \
+      goto hex_error; \
+   (var) = gethex_value * 16 + gethex_ch; \
+}
+
+#define ANSI_TRANSLATE(ch)  \
+{ \
+   switch (ch) \
+   { \
+      case 'a': \
+      case 'A': \
+      { \
+	 ch = 7; /* audible bell */ \
+	 break; \
+      } \
+      case 'b': \
+      case 'B': \
+      { \
+	 ch = 8; /* backspace */ \
+	 break; \
+      } \
+      case 'f': \
+      case 'F': \
+      { \
+	 ch = 12; /* form feed */ \
+	 break; \
+      } \
+      case 'n': \
+      case 'N': \
+      { \
+	 ch = 10; /* line feed */ \
+	 break; \
+      } \
+      case 'r': \
+      case 'R': \
+      { \
+	 ch = 13; /* carriage return */ \
+	 break; \
+      } \
+      case 't': \
+      case 'T': \
+      { \
+	 ch = 9; /* tab */ \
+	 break; \
+      } \
+      case 'v': \
+      case 'V': \
+      { \
+	 ch = 11; /* vertical tab */ \
+	 break; \
+      } \
+      case 'x': /* hex code */ \
+      case 'X': \
+      { \
+	 GETHEX(ch); \
+	 break; \
+      } \
+      default: \
+      { \
+	 /* other characters passed through */ \
+	 if (translate) \
+	    ch = translate[(unsigned char)ch]; \
+	 break; \
+      } \
+   } \
+}
+
+char *re_compile_pattern(char *regex, int size, regexp_t bufp)
+{
+   int a;
+   int pos;
+   int op;
+   int current_level;
+   int level;
+   int opcode;
+   int pattern_offset, alloc;
+   int starts[NUM_LEVELS * MAX_NESTING];
+   int starts_base;
+   int future_jumps[MAX_NESTING];
+   int num_jumps;
+   unsigned char ch;
+   char *pattern;
+   char *translate;
+   int next_register;
+   int paren_depth;
+   int num_open_registers;
+   int open_registers[RE_NREGS];
+   int beginning_context;
+
+   if (!re_compile_initialized)
+      re_compile_initialize();
+   bufp->used = 0;
+   bufp->fastmap_accurate = 0;
+   bufp->uses_registers = 0;
+   translate = bufp->translate;
+   pattern = bufp->buffer;
+   alloc = bufp->allocated;
+   if (alloc == 0 || pattern == NULL)
+   {
       alloc = 256;
       pattern = malloc(alloc);
       if (!pattern)
-	goto out_of_memory;
-    }
-  pattern_offset = 0;
-  starts_base = 0;
-  num_jumps = 0;
-  current_level = 0;
-  SET_LEVEL_START;
-  num_open_registers = 0;
-  next_register = 1;
-  paren_depth = 0;
-  beginning_context = 1;
-  op = -1;
-  /* we use Rend dummy to ensure that pending jumps are updated (due to
-     low priority of Rend) before exiting the loop. */
-  pos = 0;
-  while (op != Rend)
-    {
+	 goto out_of_memory;
+   }
+   pattern_offset = 0;
+   starts_base = 0;
+   num_jumps = 0;
+   current_level = 0;
+   SET_LEVEL_START;
+   num_open_registers = 0;
+   next_register = 1;
+   paren_depth = 0;
+   beginning_context = 1;
+   op = -1;
+   /* we use Rend dummy to ensure that pending jumps are updated (due to
+      low priority of Rend) before exiting the loop. */
+   pos = 0;
+   while (op != Rend)
+   {
       if (pos >= size)
-	op = Rend;
+	 op = Rend;
       else
-	{
-	  NEXTCHAR(ch);
-	  if (translate)
+      {
+	 NEXTCHAR(ch);
+	 if (translate)
 	    ch = translate[(unsigned char)ch];
-	  op = regexp_plain_ops[(unsigned char)ch];
-	  if (op == Rquote)
-	    {
-	      NEXTCHAR(ch);
-	      op = regexp_quoted_ops[(unsigned char)ch];
-	      if (op == Rnormal && regexp_ansi_sequences)
-		ANSI_TRANSLATE(ch);
-	    }
-	}
+	 op = regexp_plain_ops[(unsigned char)ch];
+	 if (op == Rquote)
+	 {
+	    NEXTCHAR(ch);
+	    op = regexp_quoted_ops[(unsigned char)ch];
+	    if (op == Rnormal && regexp_ansi_sequences)
+	       ANSI_TRANSLATE(ch);
+	 }
+      }
       level = regexp_precedences[op];
       /* printf("ch='%c' op=%d level=%d current_level=%d curlevstart=%d\n",
-	     ch, op, level, current_level, CURRENT_LEVEL_START); */
+	 ch, op, level, current_level, CURRENT_LEVEL_START); */
       if (level > current_level)
-	{
-	  for (current_level++; current_level < level; current_level++)
+      {
+	 for (current_level++; current_level < level; current_level++)
 	    SET_LEVEL_START;
-	  SET_LEVEL_START;
-	}
+	 SET_LEVEL_START;
+      }
       else
-	if (level < current_level)
-	  {
+	 if (level < current_level)
+	 {
 	    current_level = level;
 	    for (;num_jumps > 0 &&
-		 future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
+		    future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
 		 num_jumps--)
-	      PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
-	  }
+	       PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
+	 }
       switch (op)
-	{
-	case Rend:
-	  break;
-	case Rnormal:
-	normal_char:
-	  opcode = Cexact;
-	store_opcode_and_arg: /* opcode & ch must be set */
-	  SET_LEVEL_START;
-	  ALLOC(2);
-	  STORE(opcode);
-	  STORE(ch);
-	  break;
-	case Ranychar:
-	  opcode = Canychar;
-	store_opcode:
-	  SET_LEVEL_START;
-	  ALLOC(1);
-	  STORE(opcode);
-	  break;
-	case Rquote:
-	  abort();
-	  /*NOTREACHED*/
-	case Rbol:
-	  if (!beginning_context)
-	    if (regexp_context_indep_ops)
-	      goto op_error;
-	    else
-	      goto normal_char;
-	  opcode = Cbol;
-	  goto store_opcode;
-	case Reol:
-	  if (!((pos >= size) ||
-		((regexp_syntax & RE_NO_BK_VBAR) ?
-		 (regex[pos] == '\174') :
-		 (pos+1 < size && regex[pos] == '\134' &&
-		  regex[pos+1] == '\174')) ||
-		((regexp_syntax & RE_NO_BK_PARENS)?
-		 (regex[pos] == ')'):
-		 (pos+1 < size && regex[pos] == '\134' &&
-		  regex[pos+1] == ')'))))
-	    if (regexp_context_indep_ops)
-	      goto op_error;
-	    else
-	      goto normal_char;
-	  opcode = Ceol;
-	  goto store_opcode;
-	  /* NOTREACHED */
-	  break;
-	case Roptional:
-	  if (beginning_context)
-	    if (regexp_context_indep_ops)
-	      goto op_error;
-	    else
-	      goto normal_char;
-	  if (CURRENT_LEVEL_START == pattern_offset)
-	    break; /* ignore empty patterns for ? */
-	  ALLOC(3);
-	  INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
-		      pattern_offset + 3);
-	  break;
-	case Rstar:
-	case Rplus:
-	  if (beginning_context)
-	    if (regexp_context_indep_ops)
-	      goto op_error;
-	    else
-	      goto normal_char;
-	  if (CURRENT_LEVEL_START == pattern_offset)
-	    break; /* ignore empty patterns for + and * */
-	  ALLOC(9);
-	  INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
-		      pattern_offset + 6);
-	  INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
-	  if (op == Rplus)  /* jump over initial failure_jump */
-	    INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
-			CURRENT_LEVEL_START + 6);
-	  break;
-	case Ror:
-	  ALLOC(6);
-	  INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
-		      pattern_offset + 6);
-	  if (num_jumps >= MAX_NESTING)
-	    goto too_complex;
-	  STORE(Cjump);
-	  future_jumps[num_jumps++] = pattern_offset;
-	  STORE(0);
-	  STORE(0);
-	  SET_LEVEL_START;
-	  break;
-	case Ropenpar:
-	  SET_LEVEL_START;
-	  if (next_register < RE_NREGS)
+      {
+	 case Rend:
+	 {
+	    break;
+	 }
+	 case Rnormal:
+	 {
+	   normal_char:
+	    opcode = Cexact;
+	   store_opcode_and_arg: /* opcode & ch must be set */
+	    SET_LEVEL_START;
+	    ALLOC(2);
+	    STORE(opcode);
+	    STORE(ch);
+	    break;
+	 }
+	 case Ranychar:
+	 {
+	    opcode = Canychar;
+	   store_opcode:
+	    SET_LEVEL_START;
+	    ALLOC(1);
+	    STORE(opcode);
+	    break;
+	 }
+	 case Rquote:
+	 {
+	    abort();
+	    /*NOTREACHED*/
+	 }
+	 case Rbol:
+	 {
+	    if (!beginning_context)
+	       if (regexp_context_indep_ops)
+		  goto op_error;
+	       else
+		  goto normal_char;
+	    opcode = Cbol;
+	    goto store_opcode;
+	 }
+	 case Reol:
+	 {
+	    if (!((pos >= size) ||
+		  ((regexp_syntax & RE_NO_BK_VBAR) ?
+		   (regex[pos] == '\174') :
+		   (pos+1 < size && regex[pos] == '\134' &&
+		    regex[pos+1] == '\174')) ||
+		  ((regexp_syntax & RE_NO_BK_PARENS)?
+		   (regex[pos] == ')'):
+		   (pos+1 < size && regex[pos] == '\134' &&
+		    regex[pos+1] == ')'))))
+	       if (regexp_context_indep_ops)
+		  goto op_error;
+	       else
+		  goto normal_char;
+	    opcode = Ceol;
+	    goto store_opcode;
+	    /* NOTREACHED */
+	    break;
+	 }
+	 case Roptional:
+	 {
+	    if (beginning_context)
+	       if (regexp_context_indep_ops)
+		  goto op_error;
+	       else
+		  goto normal_char;
+	    if (CURRENT_LEVEL_START == pattern_offset)
+	       break; /* ignore empty patterns for ? */
+	    ALLOC(3);
+	    INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
+			pattern_offset + 3);
+	    break;
+	 }
+	 case Rstar:
+	 case Rplus:
+	 {
+	    if (beginning_context)
+	       if (regexp_context_indep_ops)
+		  goto op_error;
+	       else
+		  goto normal_char;
+	    if (CURRENT_LEVEL_START == pattern_offset)
+	       break; /* ignore empty patterns for + and * */
+	    ALLOC(9);
+	    INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
+			pattern_offset + 6);
+	    INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
+	    if (op == Rplus)  /* jump over initial failure_jump */
+	       INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
+			   CURRENT_LEVEL_START + 6);
+	    break;
+	 }
+	 case Ror:
+	 {
+	    ALLOC(6);
+	    INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
+			pattern_offset + 6);
+	    if (num_jumps >= MAX_NESTING)
+	       goto too_complex;
+	    STORE(Cjump);
+	    future_jumps[num_jumps++] = pattern_offset;
+	    STORE(0);
+	    STORE(0);
+	    SET_LEVEL_START;
+	    break;
+	 }
+	 case Ropenpar:
+	 {
+	    SET_LEVEL_START;
+	    if (next_register < RE_NREGS)
 	    {
-	      bufp->uses_registers = 1;
-	      ALLOC(2);
-	      STORE(Cstart_memory);
-	      STORE(next_register);
-	      open_registers[num_open_registers++] = next_register;
-	      next_register++;
+	       bufp->uses_registers = 1;
+	       ALLOC(2);
+	       STORE(Cstart_memory);
+	       STORE(next_register);
+	       open_registers[num_open_registers++] = next_register;
+	       next_register++;
 	    }
-	  paren_depth++;
-	  PUSH_LEVEL_STARTS;
-	  current_level = 0;
-	  SET_LEVEL_START;
-	  break;
-	case Rclosepar:
-	  if (paren_depth <= 0)
-	    goto parenthesis_error;
-	  POP_LEVEL_STARTS;
-	  current_level = regexp_precedences[Ropenpar];
-	  paren_depth--;
-	  if (paren_depth < num_open_registers)
+	    paren_depth++;
+	    PUSH_LEVEL_STARTS;
+	    current_level = 0;
+	    SET_LEVEL_START;
+	    break;
+	 }
+	 case Rclosepar:
+	 {
+	    if (paren_depth <= 0)
+	       goto parenthesis_error;
+	    POP_LEVEL_STARTS;
+	    current_level = regexp_precedences[Ropenpar];
+	    paren_depth--;
+	    if (paren_depth < num_open_registers)
 	    {
-	      bufp->uses_registers = 1;
-	      ALLOC(2);
-	      STORE(Cend_memory);
-	      num_open_registers--;
-	      STORE(open_registers[num_open_registers]);
+	       bufp->uses_registers = 1;
+	       ALLOC(2);
+	       STORE(Cend_memory);
+	       num_open_registers--;
+	       STORE(open_registers[num_open_registers]);
 	    }
-	  break;
-	case Rmemory:
-	  if (ch == '0')
-	    goto bad_match_register;
-	  assert(ch >= '0' && ch <= '9');
-	  bufp->uses_registers = 1;
-	  opcode = Cmatch_memory;
-	  ch -= '0';
-	  goto store_opcode_and_arg;
-	case Rextended_memory:
-	  NEXTCHAR(ch);
-	  if (ch < '0' || ch > '9')
-	    goto bad_match_register;
-	  NEXTCHAR(a);
-	  if (a < '0' || a > '9')
-	    goto bad_match_register;
-	  ch = 10 * (a - '0') + ch - '0';
-	  if (ch <= 0 || ch >= RE_NREGS)
-	    goto bad_match_register;
-	  bufp->uses_registers = 1;
-	  opcode = Cmatch_memory;
-	  goto store_opcode_and_arg;
-	case Ropenset:
-	  {
-	    int complement,prev,offset,range,firstchar;
+	    break;
+	 }
+	 case Rmemory:
+	 {
+	    if (ch == '0')
+	       goto bad_match_register;
+	    assert(ch >= '0' && ch <= '9');
+	    bufp->uses_registers = 1;
+	    opcode = Cmatch_memory;
+	    ch -= '0';
+	    goto store_opcode_and_arg;
+	 }
+	 case Rextended_memory:
+	 {
+	    NEXTCHAR(ch);
+	    if (ch < '0' || ch > '9')
+	       goto bad_match_register;
+	    NEXTCHAR(a);
+	    if (a < '0' || a > '9')
+	       goto bad_match_register;
+	    ch = 10 * (a - '0') + ch - '0';
+	    if (ch <= 0 || ch >= RE_NREGS)
+	       goto bad_match_register;
+	    bufp->uses_registers = 1;
+	    opcode = Cmatch_memory;
+	    goto store_opcode_and_arg;
+	 }
+	 case Ropenset:
+	 {
+	    int complement;
+	    int prev;
+	    int offset;
+	    int range;
+	    int firstchar;
 	    
 	    SET_LEVEL_START;
 	    ALLOC(1+256/8);
 	    STORE(Cset);
 	    offset = pattern_offset;
 	    for (a = 0; a < 256/8; a++)
-	      STORE(0);
+	       STORE(0);
 	    NEXTCHAR(ch);
 	    if (translate)
-	      ch = translate[(unsigned char)ch];
+	       ch = translate[(unsigned char)ch];
 	    if (ch == '\136')
-	      {
-		complement = 1;
-		NEXTCHAR(ch);
-		if (translate)
+	    {
+	       complement = 1;
+	       NEXTCHAR(ch);
+	       if (translate)
 		  ch = translate[(unsigned char)ch];
-	      }
+	    }
 	    else
-	      complement = 0;
+	       complement = 0;
 	    prev = -1;
 	    range = 0;
 	    firstchar = 1;
 	    while (ch != '\135' || firstchar)
-	      {
-		firstchar = 0;
-		if (regexp_ansi_sequences && ch == '\134')
-		  {
-		    NEXTCHAR(ch);
-		    ANSI_TRANSLATE(ch);
-		  }
-		if (range)
-		  {
-		    for (a = prev; a <= (int)ch; a++)
-		      SETBIT(pattern, offset, a);
-		    prev = -1;
-		    range = 0;
-		  }
-		else
+	    {
+	       firstchar = 0;
+	       if (regexp_ansi_sequences && ch == '\134')
+	       {
+		  NEXTCHAR(ch);
+		  ANSI_TRANSLATE(ch);
+	       }
+	       if (range)
+	       {
+		  for (a = prev; a <= (int)ch; a++)
+		     SETBIT(pattern, offset, a);
+		  prev = -1;
+		  range = 0;
+	       }
+	       else
 		  if (prev != -1 && ch == '-')
-		    range = 1;
+		     range = 1;
 		  else
-		    {
-		      SETBIT(pattern, offset, ch);
-		      prev = ch;
-		    }
-		NEXTCHAR(ch);
-		if (translate)
+		  {
+		     SETBIT(pattern, offset, ch);
+		     prev = ch;
+		  }
+	       NEXTCHAR(ch);
+	       if (translate)
 		  ch = translate[(unsigned char)ch];
-	      }
+	    }
 	    if (range)
-	      SETBIT(pattern, offset, '-');
+	       SETBIT(pattern, offset, '-');
 	    if (complement)
-	      {
-		for (a = 0; a < 256/8; a++)
+	    {
+	       for (a = 0; a < 256/8; a++)
 		  pattern[offset+a] ^= 0xff;
-	      }
+	    }
 	    break;
-	  }
-	case Rbegbuf:
-	  opcode = Cbegbuf;
-	  goto store_opcode;
-	case Rendbuf:
-	  opcode = Cendbuf;
-	  goto store_opcode;
-	case Rwordchar:
-	  opcode = Csyntaxspec;
-	  ch = Sword;
-	  goto store_opcode_and_arg;
-	case Rnotwordchar:
-	  opcode = Cnotsyntaxspec;
-	  ch = Sword;
-	  goto store_opcode_and_arg;
-	case Rwordbeg:
-	  opcode = Cwordbeg;
-	  goto store_opcode;
-	case Rwordend:
-	  opcode = Cwordend;
-	  goto store_opcode;
-	case Rwordbound:
-	  opcode = Cwordbound;
-	  goto store_opcode;
-	case Rnotwordbound:
-	  opcode = Cnotwordbound;
-	  goto store_opcode;
-#ifdef emacs
-	case Remacs_at_dot:
-	  opcode = Cemacs_at_dot;
-	  goto store_opcode;
-	case Remacs_syntaxspec:
-	  NEXTCHAR(ch);
-	  if (translate)
-	    ch = translate[(unsigned char)ch];
-	  opcode = Csyntaxspec;
-	  ch = syntax_spec_code[(unsigned char)ch];
-	  goto store_opcode_and_arg;
-	case Remacs_notsyntaxspec:
-	  NEXTCHAR(ch);
-	  if (translate)
-	    ch = translate[(unsigned char)ch];
-	  opcode = Cnotsyntaxspec;
-	  ch = syntax_spec_code[(unsigned char)ch];
-	  goto store_opcode_and_arg;
-#endif /* emacs */
-	default:
-	  abort();
-	}
+	 }
+	 case Rbegbuf:
+	 {
+	    opcode = Cbegbuf;
+	    goto store_opcode;
+	 }
+	 case Rendbuf:
+	 {
+	    opcode = Cendbuf;
+	    goto store_opcode;
+	 }
+	 case Rwordchar:
+	 {
+	    opcode = Csyntaxspec;
+	    ch = Sword;
+	    goto store_opcode_and_arg;
+	 }
+	 case Rnotwordchar:
+	 {
+	    opcode = Cnotsyntaxspec;
+	    ch = Sword;
+	    goto store_opcode_and_arg;
+	 }
+	 case Rwordbeg:
+	 {
+	    opcode = Cwordbeg;
+	    goto store_opcode;
+	 }
+	 case Rwordend:
+	 {
+	    opcode = Cwordend;
+	    goto store_opcode;
+	 }
+	 case Rwordbound:
+	 {
+	    opcode = Cwordbound;
+	    goto store_opcode;
+	 }
+	 case Rnotwordbound:
+	 {
+	    opcode = Cnotwordbound;
+	    goto store_opcode;
+	 }
+	 default:
+	 {
+	    abort();
+	 }
+      }
       beginning_context = (op == Ropenpar || op == Ror);
-    }
-  if (starts_base != 0)
-    goto parenthesis_error;
-  assert(num_jumps == 0);
-  ALLOC(1);
-  STORE(Cend);
-  SET_FIELDS;
-  return NULL;
-
- op_error:
-  SET_FIELDS;
-  return "Badly placed special character";
-
- bad_match_register:
-  SET_FIELDS;
-  return "Bad match register number";
-
- hex_error:
-  SET_FIELDS;
-  return "Bad hexadecimal number";
-
- parenthesis_error:
-  SET_FIELDS;
-  return "Badly placed parenthesis";
-
- out_of_memory:
-  SET_FIELDS;
-  return "Out of memory";
-
- ends_prematurely:
-  SET_FIELDS;
-  return "Regular expression ends prematurely";
-
- too_complex:
-  SET_FIELDS;
-  return "Regular expression too complex";
+   }
+   if (starts_base != 0)
+      goto parenthesis_error;
+   assert(num_jumps == 0);
+   ALLOC(1);
+   STORE(Cend);
+   SET_FIELDS;
+   if(!re_optimize(bufp))
+      return "Optimization error";
+   return NULL;
+
+  op_error:
+   SET_FIELDS;
+   return "Badly placed special character";
+
+  bad_match_register:
+   SET_FIELDS;
+   return "Bad match register number";
+   
+  hex_error:
+   SET_FIELDS;
+   return "Bad hexadecimal number";
+   
+  parenthesis_error:
+   SET_FIELDS;
+   return "Badly placed parenthesis";
+   
+  out_of_memory:
+   SET_FIELDS;
+   return "Out of memory";
+   
+  ends_prematurely:
+   SET_FIELDS;
+   return "Regular expression ends prematurely";
+
+  too_complex:
+   SET_FIELDS;
+   return "Regular expression too complex";
 }
+
 #undef CHARAT
 #undef NEXTCHAR
 #undef GETHEX
@@ -772,933 +1507,423 @@ regexp_t bufp;
 #undef SETBIT
 #undef SET_FIELDS
 
-static void re_compile_fastmap_aux
-	Py_PROTO((char *, int, char *, char *, char *));
-static void re_compile_fastmap_aux(code, pos, visited, can_be_null, fastmap)
-char *code, *visited, *can_be_null, *fastmap;
-int pos;
-{
-  int a, b, syntaxcode;
+#define PREFETCH if (text == textend) goto fail
 
-  if (visited[pos])
-    return;  /* we have already been here */
-  visited[pos] = 1;
-  for (;;)
-    switch (code[pos++])
-      {
-      case Cend:
-	*can_be_null = 1;
-	return;
-      case Cbol:
-      case Cbegbuf:
-      case Cendbuf:
-      case Cwordbeg:
-      case Cwordend:
-      case Cwordbound:
-      case Cnotwordbound:
-#ifdef emacs
-      case Cemacs_at_dot:
-#endif /* emacs */
-	break;
-      case Csyntaxspec:
-	syntaxcode = code[pos++];
-	for (a = 0; a < 256; a++)
-	  if (SYNTAX(a) == syntaxcode)
-	    fastmap[a] = 1;
-	return;
-      case Cnotsyntaxspec:
-	syntaxcode = code[pos++];
-	for (a = 0; a < 256; a++)
-	  if (SYNTAX(a) != syntaxcode)
-	    fastmap[a] = 1;
-	return;
-      case Ceol:
-	fastmap['\n'] = 1;
-	if (*can_be_null == 0)
-	  *can_be_null = 2;  /* can match null, but only at end of buffer*/
-	return;
-      case Cset:
-	for (a = 0; a < 256/8; a++)
-	  if (code[pos + a] != 0)
-	    for (b = 0; b < 8; b++)
-	      if (code[pos + a] & (1 << b))
-		fastmap[(a << 3) + b] = 1;
-	pos += 256/8;
-	return;
-      case Cexact:
-	fastmap[(unsigned char)code[pos]] = 1;
-	return;
-      case Canychar:
-	for (a = 0; a < 256; a++)
-	  if (a != '\n')
-	    fastmap[a] = 1;
-	return;
-      case Cstart_memory:
-      case Cend_memory:
-	pos++;
-	break;
-      case Cmatch_memory:
-	/* should this ever happen for sensible patterns??? */
-	*can_be_null = 1;
-	return;
-      case Cjump:
-      case Cdummy_failure_jump:
-      case Cupdate_failure_jump:
-      case Cstar_jump:
-	a = (unsigned char)code[pos++];
-	a |= (unsigned char)code[pos++] << 8;
-	pos += (int)(short)a;
-	if (visited[pos])
-	  {
-	    /* argh... the regexp contains empty loops.  This is not
-	       good, as this may cause a failure stack overflow when
-	       matching.  Oh well. */
-	    /* this path leads nowhere; pursue other paths. */
-	    return;
-	  }
-	visited[pos] = 1;
-	break;
-      case Cfailure_jump:
-	a = (unsigned char)code[pos++];
-	a |= (unsigned char)code[pos++] << 8;
-	a = pos + (int)(short)a;
-	re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
-	break;
-      default:
-	abort();  /* probably some opcode is missing from this switch */
-	/*NOTREACHED*/
-      }
-}
+#define NEXTCHAR(var) \
+PREFETCH; \
+var = (unsigned char)*text++; \
+if (translate) \
+   var = translate[var]
 
-static int re_do_compile_fastmap Py_PROTO((char *, int, int, char *, char *));
-static int re_do_compile_fastmap(buffer, used, pos, can_be_null, fastmap)
-char *buffer, *fastmap, *can_be_null;
-int used, pos;
+int re_match(regexp_t bufp,
+	     char *string,
+	     int size,
+	     int pos,
+	     regexp_registers_t old_regs)
 {
-  char small_visited[512], *visited;
-
-  if (used <= sizeof(small_visited))
-    visited = small_visited;
-  else
-    {
-      visited = malloc(used);
-      if (!visited)
-	return 0;
-    }
-  *can_be_null = 0;
-  memset(fastmap, 0, 256);
-  memset(visited, 0, used);
-  re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
-  if (visited != small_visited)
-    free(visited);
-  return 1;
-}
-
-void re_compile_fastmap(bufp)
-regexp_t bufp;
-{
-  if (!bufp->fastmap || bufp->fastmap_accurate)
-    return;
-  assert(bufp->used > 0);
-  if (!re_do_compile_fastmap(bufp->buffer, bufp->used, 0, &bufp->can_be_null,
-			     bufp->fastmap))
-    return;
-  if (bufp->buffer[0] == Cbol)
-    bufp->anchor = 1;   /* begline */
-  else
-    if (bufp->buffer[0] == Cbegbuf)
-      bufp->anchor = 2; /* begbuf */
-    else
-      bufp->anchor = 0; /* none */
-  bufp->fastmap_accurate = 1;
-}
-
-#define INITIAL_FAILURES  128  /* initial # failure points to allocate */
-#define MAX_FAILURES     4100L /* max # of failure points before failing */
-
-int re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop)
-regexp_t bufp;
-char *string1, *string2;
-int size1, size2, pos, mstop;
-regexp_registers_t regs;
-{
-  struct failure_point { char *text, *partend, *code; }
-    *failure_stack_start, *failure_sp, *failure_stack_end,
-    initial_failure_stack[INITIAL_FAILURES];
-  char *code, *translate, *text, *textend, *partend, *part_2_end;
-  char *regstart_text[RE_NREGS], *regstart_partend[RE_NREGS];
-  char *regend_text[RE_NREGS], *regend_partend[RE_NREGS];
-  int a, b, ch, reg, regch, match_end;
-  char *regtext, *regpartend, *regtextend;
-
-#define PREFETCH					\
-  MACRO_BEGIN						\
-    if (text == partend)				\
-      {							\
-	if (text == textend)				\
-	  goto fail;					\
-	text = string2;					\
-	partend = part_2_end;				\
-      }							\
-  MACRO_END
-
-#define NEXTCHAR(var)				\
-  MACRO_BEGIN					\
-    PREFETCH;					\
-    (var) = (unsigned char)*text++;		\
-    if (translate)				\
-      (var) = (unsigned char)translate[(var)];	\
-  MACRO_END
-
-  assert(pos >= 0 && size1 >= 0 && size2 >= 0 && mstop >= 0);
-  assert(mstop <= size1 + size2);
-  assert(pos <= mstop);
-
-  if (pos <= size1)
-    {
-      text = string1 + pos;
-      if (mstop <= size1)
-	{
-	  partend = string1 + mstop;
-	  textend = partend;
-	}
-      else
-	{
-	  partend = string1 + size1;
-	  textend = string2 + mstop - size1;
-	}
-      part_2_end = string2 + mstop - size1;
-    }
-  else
-    {
-      text = string2 + pos - size1;
-      partend = string2 + mstop - size1;
-      textend = partend;
-      part_2_end = partend;
-    }
-
-  if (bufp->uses_registers && regs != NULL)
-    for (a = 0; a < RE_NREGS; a++)
-      regend_text[a] = NULL;
-
+  char *code;
+  char *translate;
+  char *text;
+  char *textstart;
+  char *textend;
+  int a;
+  int b;
+  int ch;
+  int reg;
+  int match_end;
+  char *regstart;
+  char *regend;
+  int regsize;
+  match_state state;
+  
+  assert(pos >= 0 && size >= 0);
+  assert(pos <= size);
+  
+  text = string + pos;
+  textstart = string;
+  textend = string + size;
+  
   code = bufp->buffer;
+  
   translate = bufp->translate;
-  failure_stack_start = failure_sp = initial_failure_stack;
-  failure_stack_end = initial_failure_stack + INITIAL_FAILURES;
-
-#if 0
-  /* re_search_2 has already done this, and otherwise we get little benefit
-     from this.  So I'll leave this out. */
-  if (bufp->fastmap_accurate && !bufp->can_be_null &&
-      text != textend &&
-      !bufp->fastmap[translate ?
-		     (unsigned char)translate[(unsigned char)*text] :
-		     (unsigned char)*text])
-    return -1;  /* it can't possibly match */
-#endif
-
- continue_matching:
-  for (;;)
-    {
-      switch (*code++)
+/*   translated = NULL; */
+/*   if (bufp->translate) */
+/*   { */
+/*      char *t1; */
+/*      char *t2; */
+     
+/*      translated = malloc(size); */
+/*      if (translated == NULL) */
+/* 	goto error; */
+
+/*      t1 = string; */
+/*      t2 = translated; */
+/*      while(t1 < textend) */
+/* 	*t2++ = bufp->translate[*t1++]; */
+     
+/*      text = translated + pos; */
+/*      textstart = translated; */
+/*      textend = translated + size; */
+/*   } */
+  
+  NEW_STATE(state);
+  
+  continue_matching:
+  switch (*code++)
+  {
+     case Cend:
+     {
+	match_end = text - textstart;
+	if (old_regs)
 	{
-	case Cend:
-	  if (partend != part_2_end)
-	    match_end = text - string1;
-	  else
-	    match_end = text - string2 + size1;
-	  if (regs)
-	    {
-	      regs->start[0] = pos;
-	      regs->end[0] = match_end;
-	      if (!bufp->uses_registers)
-		{
-		  for (a = 1; a < RE_NREGS; a++)
-		    {
-		      regs->start[a] = -1;
-		      regs->end[a] = -1;
-		    }
-		}
-	      else
-		{
-		  for (a = 1; a < RE_NREGS; a++)
-		    {
-		      if (regend_text[a] == NULL)
-			{
-			  regs->start[a] = -1;
-			  regs->end[a] = -1;
-			  continue;
-			}
-		      if (regstart_partend[a] != part_2_end)
-			regs->start[a] = regstart_text[a] - string1;
-		      else
-			regs->start[a] = regstart_text[a] - string2 + size1;
-		      if (regend_partend[a] != part_2_end)
-			regs->end[a] = regend_text[a] - string1;
-		      else
-			regs->end[a] = regend_text[a] - string2 + size1;
-		    }
-		}
-	    }
-	  if (failure_stack_start != initial_failure_stack)
-	    free((char *)failure_stack_start);
-	  return match_end - pos;
-	case Cbol:
-	  if (text == string1 || text[-1] == '\n') /* text[-1] always valid */
-	    break;
-	  goto fail;
-	case Ceol:
-	  if (text == string2 + size2 ||
-	      (text == string1 + size1 ?
-	       (size2 == 0 || *string2 == '\n') :
-	       *text == '\n'))
-	    break;
-	  goto fail;
-	case Cset:
-	  NEXTCHAR(ch);
-	  if (code[ch/8] & (1<<(ch & 7)))
-	    {
-	      code += 256/8;
-	      break;
-	    }
-	  goto fail;
-	case Cexact:
-	  NEXTCHAR(ch);
-	  if (ch != (unsigned char)*code++)
-	    goto fail;
-	  break;
-	case Canychar:
-	  NEXTCHAR(ch);
-	  if (ch == '\n')
-	    goto fail;
-	  break;
-	case Cstart_memory:
-	  reg = *code++;
-	  regstart_text[reg] = text;
-	  regstart_partend[reg] = partend;
-	  break;
-	case Cend_memory:
-	  reg = *code++;
-	  regend_text[reg] = text;
-	  regend_partend[reg] = partend;
-	  break;
-	case Cmatch_memory:
-	  reg = *code++;
-	  if (regend_text[reg] == NULL)
-	    goto fail;  /* or should we just match nothing? */
-	  regtext = regstart_text[reg];
-	  regtextend = regend_text[reg];
-	  if (regstart_partend[reg] == regend_partend[reg])
-	    regpartend = regtextend;
-	  else
-	    regpartend = string1 + size1;
-	  
-	  for (;regtext != regtextend;)
-	    {
-	      NEXTCHAR(ch);
-	      if (regtext == regpartend)
-		regtext = string2;
-	      regch = (unsigned char)*regtext++;
-	      if (translate)
-		regch = (unsigned char)translate[regch];
-	      if (regch != ch)
-		goto fail;
-	    }
-	  break;
-	case Cstar_jump:
-	  /* star is coded as:
-	       1: failure_jump 2
-	          ... code for operand of star
-		  star_jump 1
-	       2: ... code after star
-	     We change the star_jump to update_failure_jump if we can determine
-	     that it is safe to do so; otherwise we change it to an ordinary
-	     jump.
-	     plus is coded as
-	          jump 2
-	       1: failure_jump 3
-	       2: ... code for operand of plus
-	          star_jump 1
-	       3: ... code after plus
-	     For star_jump considerations this is processed identically
-	     to star. */
-	  a = (unsigned char)*code++;
-	  a |= (unsigned char)*code++ << 8;
-	  a = (int)(short)a;
-	  {
-	    char map[256], can_be_null;
-	    char *p1, *p2;
-
-	    p1 = code + a + 3; /* skip the failure_jump */
-	    assert(p1[-3] == Cfailure_jump);
-	    p2 = code;
-	    /* p1 points inside loop, p2 points to after loop */
-	    if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
-				       p2 - bufp->buffer, &can_be_null, map))
-	      goto make_normal_jump;
-	    /* If we might introduce a new update point inside the loop,
-	       we can't optimize because then update_jump would update a
-	       wrong failure point.  Thus we have to be quite careful here. */
-	  loop_p1:
-	    /* loop until we find something that consumes a character */
-	    switch (*p1++)
+	   old_regs->start[0] = pos;
+	   old_regs->end[0] = match_end;
+	   if (!bufp->uses_registers)
+	   {
+	      for (a = 1; a < RE_NREGS; a++)
 	      {
-              case Cbol:
-              case Ceol:
-              case Cbegbuf:
-              case Cendbuf:
-              case Cwordbeg:
-              case Cwordend:
-              case Cwordbound:
-              case Cnotwordbound:
-#ifdef emacs
-              case Cemacs_at_dot:
-#endif /* emacs */
-                goto loop_p1;
-              case Cstart_memory:
-              case Cend_memory:
-                p1++;
-                goto loop_p1;
-	      case Cexact:
-		ch = (unsigned char)*p1++;
-		if (map[ch])
-		  goto make_normal_jump;
-		break;
-	      case Canychar:
-		for (b = 0; b < 256; b++)
-		  if (b != '\n' && map[b])
-		    goto make_normal_jump;
-		break;
-	      case Cset:
-		for (b = 0; b < 256; b++)
-		  if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
-		    goto make_normal_jump;
-		p1 += 256/8;
-		break;
-	      default:
-		goto make_normal_jump;
+		 old_regs->start[a] = -1;
+		 old_regs->end[a] = -1;
 	      }
-	    /* now we know that we can't backtrack. */
-	    while (p1 != p2 - 3)
+	   }
+	   else
+	   {
+	      for (a = 1; a < RE_NREGS; a++)
 	      {
-		switch (*p1++)
-		  {
-		  case Cend:
-		    abort();  /* we certainly shouldn't get this inside loop */
-		    /*NOTREACHED*/
-		  case Cbol:
-		  case Ceol:
-		  case Canychar:
-		  case Cbegbuf:
-		  case Cendbuf:
-		  case Cwordbeg:
-		  case Cwordend:
-		  case Cwordbound:
-		  case Cnotwordbound:
-#ifdef emacs
-		  case Cemacs_at_dot:
-#endif /* emacs */
-		    break;
-		  case Cset:
-		    p1 += 256/8;
-		    break;
-		  case Cexact:
-		  case Cstart_memory:
-		  case Cend_memory:
-		  case Cmatch_memory:
-		  case Csyntaxspec:
-		  case Cnotsyntaxspec:
-		    p1++;
-		    break;
-		  case Cjump:
-		  case Cstar_jump:
-		  case Cfailure_jump:
-		  case Cupdate_failure_jump:
-		  case Cdummy_failure_jump:
-		    goto make_normal_jump;
-		  default:
-		    printf("regexpr.c: processing star_jump: unknown op %d\n", p1[-1]);
-		    break;
-		  }
+		 if ((GET_REG_START(state, a) == NULL) ||
+		     (GET_REG_END(state, a) == NULL))
+		 {
+		    old_regs->start[a] = -1;
+		    old_regs->end[a] = -1;
+		    continue;
+		 }
+		 old_regs->start[a] = GET_REG_START(state, a) - textstart;
+		 old_regs->end[a] = GET_REG_END(state, a) - textstart;
 	      }
-	    goto make_update_jump;
-	  }
-	make_normal_jump:
-	  /* printf("changing to normal jump\n"); */
-	  code -= 3;
-	  *code = Cjump;
-	  break;
-	make_update_jump:
-	  /* printf("changing to update jump\n"); */
-	  code -= 2;
-	  a += 3;  /* jump to after the Cfailure_jump */
-	  code[-1] = Cupdate_failure_jump;
-	  code[0] = a & 0xff;
-	  code[1] = a >> 8;
-	  /* fall to next case */
-	case Cupdate_failure_jump:
-	  failure_sp[-1].text = text;
-	  failure_sp[-1].partend = partend;
-	  /* fall to next case */
-	case Cjump:
-	  a = (unsigned char)*code++;
-	  a |= (unsigned char)*code++ << 8;
-	  code += (int)(short)a;
-	  break;
-	case Cdummy_failure_jump:
-	case Cfailure_jump:
-	  if (failure_sp == failure_stack_end)
-	    {
-	      if (failure_stack_start != initial_failure_stack)
-		goto error;
-	      failure_stack_start = (struct failure_point *)
-		malloc(MAX_FAILURES * sizeof(*failure_stack_start));
-	      if (failure_stack_start == NULL)
-	        {
-		  failure_stack_start = initial_failure_stack;
-		  goto error;
-		}
-	      failure_stack_end = failure_stack_start + MAX_FAILURES;
-	      memcpy((char *)failure_stack_start, (char *)initial_failure_stack,
-		     INITIAL_FAILURES * sizeof(*failure_stack_start));
-	      failure_sp = failure_stack_start + INITIAL_FAILURES;
-	    }
-	  a = (unsigned char)*code++;
-	  a |= (unsigned char)*code++ << 8;
-	  a = (int)(short)a;
-	  if (code[-3] == Cdummy_failure_jump)
-	    { /* this is only used in plus */
-	      assert(*code == Cfailure_jump);
-	      b = (unsigned char)code[1];
-	      b |= (unsigned char)code[2] << 8;
-	      failure_sp->code = code + (int)(short)b + 3;
-	      failure_sp->text = NULL;
-	      code += a;
-	    }
-	  else
-	    {
-	      failure_sp->code = code + a;
-	      failure_sp->text = text;
-	      failure_sp->partend = partend;
-	    }
-	  failure_sp++;
-	  break;
-	case Cbegbuf:
-	  if (text == string1)
-	    break;
-	  goto fail;
-	case Cendbuf:
-	  if (size2 == 0 ? text == string1 + size1 : text == string2 + size2)
-	    break;
-	  goto fail;
-	case Cwordbeg:
-	  if (text == string2 + size2)
-	    goto fail;
-	  if (size2 == 0 && text == string1 + size1)
-	    goto fail;
-	  if (SYNTAX(text == string1 + size1 ? *string1 : *text) != Sword)
-	    goto fail;
-	  if (text == string1)
-	    break;
-	  if (SYNTAX(text[-1]) != Sword)
-	    break;
-	  goto fail;
-	case Cwordend:
-	  if (text == string1)
-	    goto fail;
-	  if (SYNTAX(text[-1]) != Sword)
-	    goto fail;
-	  if (text == string2 + size2)
-	    break;
-	  if (size2 == 0 && text == string1 + size1)
-	    break;
-	  if (SYNTAX(*text) == Sword)
-	    goto fail;
-	  break;
-	case Cwordbound:
-	  /* Note: as in gnu regexp, this also matches at the beginning
-	     and end of buffer. */
-	  if (text == string1 || text == string2 + size2 ||
-	      (size2 == 0 && text == string1 + size1))
-	    break;
-	  if ((SYNTAX(text[-1]) == Sword) ^
-	      (SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword))
-	    break;
-	  goto fail;
-	case Cnotwordbound:
-	  /* Note: as in gnu regexp, this never matches at the beginning
-	     and end of buffer. */
-	  if (text == string1 || text == string2 + size2 ||
-	      (size2 == 0 && text == string1 + size1))
-	    goto fail;
-	  if (!((SYNTAX(text[-1]) == Sword) ^
-		(SYNTAX(text == string1 + size1 ? *string2 : *text) == Sword)))
-	    goto fail;
-	  break;
-	case Csyntaxspec:
-	  NEXTCHAR(ch);
-	  if (SYNTAX(ch) != (unsigned char)*code++)
-	    goto fail;
-	  break;
-	case Cnotsyntaxspec:
-	  NEXTCHAR(ch);
-	  if (SYNTAX(ch) != (unsigned char)*code++)
-	    break;
-	  goto fail;
-#ifdef emacs
-	case Cemacs_at_dot:
-	  if (PTR_CHAR_POS((unsigned char *)text) + 1 != point)
-	    goto fail;
-	  break;
-#endif /* emacs */
-	default:
-	  abort();
-	  /*NOTREACHED*/
+	   }
 	}
-    }
+/* 	if(translated) */
+/* 	   free(translated); */
+	FREE_STATE(state);
+	return match_end - pos;
+     }
+     case Cbol:
+     {
+	if (text == textstart || text[-1] == '\n')
+	   goto continue_matching;
+	goto fail;
+     }
+     case Ceol:
+     {
+	if (text == textend || *text == '\n')
+	   goto continue_matching;
+	goto fail;
+     }
+     case Cset:
+     {
+	NEXTCHAR(ch);
+	if (code[ch/8] & (1<<(ch & 7)))
+	{
+	   code += 256/8;
+	   goto continue_matching;
+	}
+	goto fail;
+     }
+     case Cexact:
+     {
+	NEXTCHAR(ch);
+	if (ch != (unsigned char)*code++)
+	   goto fail;
+/* 	{ */
+/* 	   char *p1 = code - 2; */
+/* 	   ch = *(code - 1); */
+/* 	   POP_FAILURE(state, code, text, goto done_matching, goto error); */
+/* 	   while ((code == p1) && (*text != ch)) */
+/* 	      POP_FAILURE(state, code, text, goto done_matching, goto error); */
+/* 	   if ((code == p1) && (*text == ch)) */
+/* 	   { */
+/* 	      code += 2; */
+/* 	      text++; */
+/* 	   } */
+/* 	} */
+	goto continue_matching;
+     }
+     case Canychar:
+     {
+	NEXTCHAR(ch);
+	if (ch == '\n')
+	   goto fail;
+	goto continue_matching;
+     }
+     case Cstart_memory:
+     {
+	reg = *code++;
+	SET_REG_START(state, reg, text, goto error);
+	goto continue_matching;
+     }
+     case Cend_memory:
+     {
+	reg = *code++;
+	SET_REG_END(state, reg, text, goto error);
+	goto continue_matching;
+     }
+     case Cmatch_memory:
+     {
+	reg = *code++;
+	regstart = GET_REG_START(state, reg);
+	regend = GET_REG_END(state, reg);
+	if ((regstart == NULL) || (regend == NULL))
+	   goto fail;  /* or should we just match nothing? */
+	regsize = regend - regstart;
+
+	if (regsize > (textend - text))
+	   goto fail;
+	if(translate)
+	{
+	   for (; regstart < regend; regstart++, text++)
+	      if (translate[*regstart] != translate[*text])
+		 goto fail;
+	}
+	else
+	   for (; regstart < regend; regstart++, text++)
+	      if (*regstart != *text)
+		 goto fail;
+/*	if (memcmp(text, regstart, regsize) != 0)
+	   goto fail;
+	text += regsize; */
+	goto continue_matching;
+     }
+     case Cupdate_failure_jump:
+     {
+	UPDATE_FAILURE(state, text, goto error);
+	/* fall to next case */
+     }
+     /* treat Cstar_jump just like Cjump if it hasn't been optimized */
+     case Cstar_jump:
+     case Cjump:
+     {
+	a = (unsigned char)*code++;
+	a |= (unsigned char)*code++ << 8;
+	code += (int)(short)a;
+	goto continue_matching;
+     }
+     case Cdummy_failure_jump:
+     {
+	a = (unsigned char)*code++;
+	a |= (unsigned char)*code++ << 8;
+	a = (int)(short)a;
+	assert(*code == Cfailure_jump);
+	b = (unsigned char)code[1];
+	b |= (unsigned char)code[2] << 8;
+	PUSH_FAILURE(state, code + (int)(short)b + 3, NULL, goto error);
+	code += a;
+	goto continue_matching;
+     }
+     case Cfailure_jump:
+     {
+	a = (unsigned char)*code++;
+	a |= (unsigned char)*code++ << 8;
+	a = (int)(short)a;
+	PUSH_FAILURE(state, code + a, text, goto error);
+	goto continue_matching;
+     }
+     case Cbegbuf:
+     {
+	if (text == textstart)
+	   goto continue_matching;
+	goto fail;
+     }
+     case Cendbuf:
+     {
+	if (text == textend)
+	   goto continue_matching;
+	goto fail;
+     }
+     case Cwordbeg:
+     {
+	if (text == textend)
+	   goto fail;
+	if (SYNTAX(*text) != Sword)
+	   goto fail;
+	if (text == textstart)
+	   goto continue_matching;
+	if (SYNTAX(text[-1]) != Sword)
+	   goto continue_matching;
+	goto fail;
+     }
+     case Cwordend:
+     {
+	if (text == textstart)
+	   goto fail;
+	if (SYNTAX(text[-1]) != Sword)
+	   goto fail;
+	if (text == textend)
+	   goto continue_matching;
+	if (SYNTAX(*text) == Sword)
+	   goto fail;
+	goto continue_matching;
+     }
+     case Cwordbound:
+     {
+	/* Note: as in gnu regexp, this also matches at the beginning
+	 * and end of buffer.  */
+
+	if (text == textstart || text == textend)
+	   goto continue_matching;
+	if ((SYNTAX(text[-1]) == Sword) ^ (SYNTAX(*text) == Sword))
+	   goto continue_matching;
+	goto fail;
+     }
+     case Cnotwordbound:
+     {
+	/* Note: as in gnu regexp, this never matches at the beginning
+	 * and end of buffer.  */
+	if (text == textstart || text == textend)
+	   goto fail;
+	if (!((SYNTAX(text[-1]) == Sword) ^ (SYNTAX(*text) == Sword)))
+	   goto fail;
+	goto continue_matching;
+     }
+     case Csyntaxspec:
+     {
+	NEXTCHAR(ch);
+	if (SYNTAX(ch) != (unsigned char)*code++)
+	   goto fail;
+	   goto continue_matching;
+     }
+     case Cnotsyntaxspec:
+     {
+	NEXTCHAR(ch);
+	if (SYNTAX(ch) != (unsigned char)*code++)
+	   break;
+	goto continue_matching;
+     }
+     default:
+     {
+	abort();
+	/*NOTREACHED*/
+     }
+  }
+
 #if 0 /* This line is never reached --Guido */
   abort();
 #endif
-  /*NOTREACHED*/
-
- fail:
-  if (failure_sp != failure_stack_start)
-    {
-      failure_sp--;
-      text = failure_sp->text;
-      if (text == NULL)
-	goto fail;
-      partend = failure_sp->partend;
-      code = failure_sp->code;
-      goto continue_matching;
-    }
-  if (failure_stack_start != initial_failure_stack)
-    free((char *)failure_stack_start);
+  /*
+   *NOTREACHED
+   */
+  
+  fail:
+  POP_FAILURE(state, code, text, goto done_matching, goto error);
+  goto continue_matching;
+  
+  done_matching:
+/*   if(translated != NULL) */
+/*      free(translated); */
+  FREE_STATE(state);
   return -1;
 
- error:
-  if (failure_stack_start != initial_failure_stack)
-    free((char *)failure_stack_start);
+  error:
+/*   if (translated != NULL) */
+/*      free(translated); */
+  FREE_STATE(state);
   return -2;
 }
 
 #undef PREFETCH
 #undef NEXTCHAR
-#undef PUSH_FAILURE
 
-int re_match(bufp, string, size, pos, regs)
-regexp_t bufp;
-char *string;
-int size, pos;
-regexp_registers_t regs;
+int re_search(regexp_t bufp,
+	      char *string,
+	      int size,
+	      int pos,
+	      int range,
+	      regexp_registers_t regs)
 {
-  return re_match_2(bufp, string, size, (char *)NULL, 0, pos, regs, size);
-}
-
-int re_search_2(bufp, string1, size1, string2, size2, pos, range, regs,
-		mstop)
-regexp_t bufp;
-char *string1, *string2;
-int size1, size2, pos, range, mstop;
-regexp_registers_t regs;
-{
-  char *fastmap, *translate, *text, *partstart, *partend;
-  int dir, ret;
+  char *fastmap;
+  char *translate;
+  char *text;
+  char *partstart;
+  char *partend;
+  int dir;
+  int ret;
   char anchor;
   
-  assert(size1 >= 0 && size2 >= 0 && pos >= 0 && mstop >= 0);
-  assert(pos + range >= 0 && pos + range <= size1 + size2); /* Bugfix by ylo */
-  assert(pos <= mstop);
+  assert(size >= 0 && pos >= 0);
+  assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
   
   fastmap = bufp->fastmap;
   translate = bufp->translate;
   if (fastmap && !bufp->fastmap_accurate)
-    re_compile_fastmap(bufp);
+     re_compile_fastmap(bufp);
   anchor = bufp->anchor;
   if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
-    fastmap = NULL;
+     fastmap = NULL;
+
   if (range < 0)
-    {
-      dir = -1;
-      range = -range;
-    }
+  {
+     dir = -1;
+     range = -range;
+  }
   else
-    dir = 1;
+     dir = 1;
+
   if (anchor == 2)
-    if (pos != 0)
-      return -1;
-    else
-      range = 0;
+     if (pos != 0)
+	return -1;
+     else
+	range = 0;
+
   for (; range >= 0; range--, pos += dir)
-    {
-      if (fastmap)
-	{
-	  if (dir == 1)
-	    { /* searching forwards */
-	      if (pos < size1)
-		{
-		  text = string1 + pos;
-		  if (pos + range > size1)
-		    partend = string1 + size1;
-		  else
-		    partend = string1 + pos + range;
-		}
-	      else
-		{
-		  text = string2 + pos - size1;
-		  partend = string2 + pos + range - size1;
-		}
-	      partstart = text;
-	      if (translate)
-		while (text != partend &&
-		       !fastmap[(unsigned char)
-				translate[(unsigned char)*text]])
-		  text++;
-	      else
-		while (text != partend && !fastmap[(unsigned char)*text])
-		  text++;
-	      pos += text - partstart;
-	      range -= text - partstart;
-	      if (pos == size1 + size2 && bufp->can_be_null == 0)
-		return -1;
-	    }
-	  else
-	    { /* searching backwards */
-	      if (pos <= size1)
-		{
-		  text = string1 + pos;
-		  partstart = string1 + pos - range;
-		}
-	      else
-		{
-		  text = string2 + pos - size1;
-		  if (range < pos - size1)
-		    partstart = string2 + pos - size1 - range;
-		  else
-		    partstart = string2;
-		}
-	      partend = text;
-	      if (translate)
-		while (text != partstart &&
-		       !fastmap[(unsigned char)
-				translate[(unsigned char)*text]])
-		  text--;
-	      else
-		while (text != partstart &&
-		       !fastmap[(unsigned char)*text])
-		  text--;
-	      pos -= partend - text;
-	      range -= partend - text;
-	    }
+  {
+     if (fastmap)
+     {
+	if (dir == 1)
+	{ /* searching forwards */
+
+	   text = string + pos;
+	   partend = string + size;
+	   partstart = text;
+	   if (translate)
+	      while (text != partend &&
+		     !fastmap[(unsigned char) translate[(unsigned char)*text]])
+		 text++;
+	   else
+	      while (text != partend && !fastmap[(unsigned char)*text])
+		 text++;
+	   pos += text - partstart;
+	   range -= text - partstart;
+	   if (pos == size && bufp->can_be_null == 0)
+	      return -1;
 	}
-      if (anchor == 1)
-	{ /* anchored to begline */
-	  if (pos > 0 &&
-	      (pos <= size1 ? string1[pos - 1] :
-	       string2[pos - size1 - 1]) != '\n')
-	    continue;
+	else
+	{ /* searching backwards */
+	   text = string + pos;
+	   partstart = string + pos - range;
+	   partend = text;
+	   if (translate)
+	      while (text != partstart &&
+		     !fastmap[(unsigned char)
+			     translate[(unsigned char)*text]])
+		 text--;
+	   else
+	      while (text != partstart &&
+		     !fastmap[(unsigned char)*text])
+		 text--;
+	   pos -= partend - text;
+	   range -= partend - text;
 	}
-      assert(pos >= 0 && pos <= size1 + size2);
-      ret = re_match_2(bufp, string1, size1, string2, size2, pos, regs, mstop);
-      if (ret >= 0)
+     }
+     if (anchor == 1)
+     { /* anchored to begline */
+	if (pos > 0 && string[pos - 1])
+	   continue;
+     }
+     assert(pos >= 0 && pos <= size);
+     ret = re_match(bufp, string, size, pos, regs);
+     if (ret >= 0)
 	return pos;
-      if (ret == -2)
+     if (ret == -2)
 	return -2;
-    }
+  }
   return -1;
 }
-
-int re_search(bufp, string, size, startpos, range, regs)
-regexp_t bufp;
-char *string;
-int size, startpos, range;
-regexp_registers_t regs;
-{
-  return re_search_2(bufp, string, size, (char *)NULL, 0,
-		     startpos, range, regs, size);
-}
-
-#ifdef UNUSED
-
-static struct re_pattern_buffer re_comp_buf;
-
-char *re_comp(s)
-char *s;
-{
-  if (s == NULL)
-    {
-      if (!re_comp_buf.buffer)
-	return "Out of memory";
-      return NULL;
-    }
-  if (!re_comp_buf.buffer)
-    {
-      /* the buffer will be allocated automatically */
-      re_comp_buf.fastmap = malloc(256);
-      re_comp_buf.translate = NULL;
-      if (re_comp_buf.fastmap == NULL)
-	return "Out of memory";
-    }
-  return re_compile_pattern(s, strlen(s), &re_comp_buf);
-}
-
-int re_exec(s)
-char *s;
-{
-  int len = strlen(s);
-  
-  return re_search(&re_comp_buf, s, len, 0, len, (regexp_registers_t)NULL) >= 0;
-}
-
-#endif
-
-#ifdef TEST_REGEXP
-
-int main()
-{
-  char buf[500];
-  char *cp;
-  struct re_pattern_buffer exp;
-  struct re_registers regs;
-  int a,pos;
-  char fastmap[256];
-
-  exp.allocated = 0;
-  exp.buffer = 0;
-  exp.translate = NULL;
-  exp.fastmap = fastmap;
-
-  /* re_set_syntax(RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_ANSI_HEX); */
-
-  while (1)
-    {
-      printf("Enter regexp:\n");
-      gets(buf);
-      cp=re_compile_pattern(buf, strlen(buf), &exp);
-      if (cp)
-	{
-	  printf("Error: %s\n", cp);
-	  continue;
-	}
-      re_compile_fastmap(&exp);
-      printf("dump:\n");
-      for (pos = 0; pos < exp.used;)
-	{
-	  printf("%d: ", pos);
-	  switch (exp.buffer[pos++])
-	    {
-	    case Cend:
-	      strcpy(buf, "end");
-	      break;
-	    case Cbol:
-	      strcpy(buf, "bol");
-	      break;
-	    case Ceol:
-	      strcpy(buf, "eol");
-	      break;
-	    case Cset:
-	      strcpy(buf, "set ");
-	      for (a = 0; a < 256/8; a++)
-		sprintf(buf+strlen(buf)," %02x",
-			(unsigned char)exp.buffer[pos++]);
-	      break;
-	    case Cexact:
-	      sprintf(buf, "exact '%c' 0x%x", exp.buffer[pos],
-		      (unsigned char)exp.buffer[pos]);
-	      pos++;
-	      break;
-	    case Canychar:
-	      strcpy(buf, "anychar");
-	      break;
-	    case Cstart_memory:
-	      sprintf(buf, "start_memory %d", exp.buffer[pos++]);
-	      break;
-	    case Cend_memory:
-	      sprintf(buf, "end_memory %d", exp.buffer[pos++]);
-	      break;
-	    case Cmatch_memory:
-	      sprintf(buf, "match_memory %d", exp.buffer[pos++]);
-	      break;
-	    case Cjump:
-	    case Cdummy_failure_jump:
-	    case Cstar_jump:
-	    case Cfailure_jump:
-	    case Cupdate_failure_jump:
-	      a = (unsigned char)exp.buffer[pos++];
-	      a += (unsigned char)exp.buffer[pos++] << 8;
-	      a = (int)(short)a;
-	      switch (exp.buffer[pos-3])
-		{
-		case Cjump:
-		  cp = "jump";
-		  break;
-		case Cstar_jump:
-		  cp = "star_jump";
-		  break;
-		case Cfailure_jump:
-		  cp = "failure_jump";
-		  break;
-		case Cupdate_failure_jump:
-		  cp = "update_failure_jump";
-		  break;
-		case Cdummy_failure_jump:
-		  cp = "dummy_failure_jump";
-		  break;
-		default:
-		  cp = "unknown jump";
-		  break;
-		}
-	      sprintf(buf, "%s %d", cp, a + pos);
-	      break;
-	    case Cbegbuf:
-	      strcpy(buf,"begbuf");
-	      break;
-	    case Cendbuf:
-	      strcpy(buf,"endbuf");
-	      break;
-	    case Cwordbeg:
-	      strcpy(buf,"wordbeg");
-	      break;
-	    case Cwordend:
-	      strcpy(buf,"wordend");
-	      break;
-	    case Cwordbound:
-	      strcpy(buf,"wordbound");
-	      break;
-	    case Cnotwordbound:
-	      strcpy(buf,"notwordbound");
-	      break;
-	    default:
-	      sprintf(buf, "unknown code %d",
-		      (unsigned char)exp.buffer[pos - 1]);
-	      break;
-	    }
-	  printf("%s\n", buf);
-	}
-      printf("can_be_null = %d uses_registers = %d anchor = %d\n",
-	     exp.can_be_null, exp.uses_registers, exp.anchor);
-      
-      printf("fastmap:");
-      for (a = 0; a < 256; a++)
-	if (exp.fastmap[a])
-	  printf(" %d", a);
-      printf("\n");
-      printf("Enter strings.  An empty line terminates.\n");
-      while (fgets(buf, sizeof(buf), stdin))
-	{
-	  if (buf[0] == '\n')
-	    break;
-	  a = re_search(&exp, buf, strlen(buf), 0, strlen(buf), &regs);
-	  printf("search returns %d\n", a);
-	  if (a != -1)
-	    {
-	      for (a = 0; a < RE_NREGS; a++)
-		{
-		  printf("buf %d: %d to %d\n", a, regs.start[a], regs.end[a]);
-		}
-	    }
-	}
-    }
-}
-
-#endif /* TEST_REGEXP */
diff --git a/Modules/regexpr.h b/Modules/regexpr.h
index 0ddb3a1..e623362 100644
--- a/Modules/regexpr.h
+++ b/Modules/regexpr.h
@@ -69,9 +69,7 @@ typedef struct re_registers
 #define re_set_syntax _Py_re_set_syntax
 #define re_compile_pattern _Py_re_compile_pattern
 #define re_match _Py_re_match
-#define re_match_2 _Py_re_match_2
 #define re_search _Py_re_search
-#define re_search_2 _Py_re_search_2
 #define re_compile_fastmap _Py_re_compile_fastmap
 #define re_comp _Py_re_comp
 #define re_exec _Py_re_exec
@@ -96,20 +94,12 @@ char *re_compile_pattern(char *regex, int regex_size, regexp_t compiled);
    translation table, or NULL if it is not used. */
 
 int re_match(regexp_t compiled, char *string, int size, int pos,
-	     regexp_registers_t regs);
+	     regexp_registers_t old_regs);
 /* This tries to match the regexp against the string.  This returns the
    length of the matched portion, or -1 if the pattern could not be
    matched and -2 if an error (such as failure stack overflow) is
    encountered. */
 
-int re_match_2(regexp_t compiled, char *string1, int size1,
-	      char *string2, int size2, int pos, regexp_registers_t regs,
-	       int mstop);
-/* This tries to match the regexp to the concatenation of string1 and
-   string2.  This returns the length of the matched portion, or -1 if the
-   pattern could not be matched and -2 if an error (such as failure stack
-   overflow) is encountered. */
-
 int re_search(regexp_t compiled, char *string, int size, int startpos,
 	      int range, regexp_registers_t regs);
 /* This rearches for a substring matching the regexp.  This returns the first
@@ -119,12 +109,6 @@ int re_search(regexp_t compiled, char *string, int size, int startpos,
    which a match must not go.  This returns -1 if no match is found, and
    -2 if an error (such as failure stack overflow) is encountered. */
 
-int re_search_2(regexp_t compiled, char *string1, int size1,
-		char *string2, int size2, int startpos, int range,
-		regexp_registers_t regs, int mstop);
-/* This is like re_search, but search from the concatenation of string1 and
-   string2.  */
-
 void re_compile_fastmap(regexp_t compiled);
 /* This computes the fastmap for the regexp.  For this to have any effect,
    the calling program must have initialized the fastmap field to point
@@ -146,9 +130,7 @@ extern int re_syntax;
 int re_set_syntax();
 char *re_compile_pattern();
 int re_match();
-int re_match_2();
 int re_search();
-int re_search_2();
 void re_compile_fastmap();
 char *re_comp();
 int re_exec();