Updated to fedora-glibc-20050208T0948cvs/fedora-glibc-2_3_4-6

14 files changed, 749 insertions, 697 deletions

diff --git a/posix/Makefile b/posix/Makefile
index 149283c65d..3af9e6681d 100644
--- a/posix/Makefile
+++ b/posix/Makefile
@@ -1,4 +1,4 @@
-# Copyright (C) 1991-1999, 2000-2003, 2004 Free Software Foundation, Inc.
+# Copyright (C) 1991-1999, 2000-2003, 2004, 2005 Free Software Foundation, Inc.
 # This file is part of the GNU C Library.
 
 # The GNU C Library is free software; you can redistribute it and/or
@@ -140,16 +140,27 @@ CFLAGS-waitid.c = -fexceptions
 CFLAGS-waitpid.c = -fexceptions -fasynchronous-unwind-tables
 CFLAGS-getopt.c = -fexceptions
 CFLAGS-wordexp.c = -fexceptions
+CFLAGS-wordexp.os = -fomit-frame-pointer
 CFLAGS-sysconf.c = -fexceptions -DGETCONF_DIR='"$(libexecdir)/getconf"'
 CFLAGS-pathconf.c = -fexceptions
 CFLAGS-fpathconf.c = -fexceptions
 CFLAGS-spawn.c = -fexceptions
+CFLAGS-spawn.os = -fomit-frame-pointer
 CFLAGS-spawnp.c = -fexceptions
+CFLAGS-spawnp.os = -fomit-frame-pointer
 CFLAGS-spawni.c = -fexceptions
+CFLAGS-spawni.os = -fomit-frame-pointer
 CFLAGS-pause.c = -fexceptions
 CFLAGS-glob.c = $(uses-callbacks) -fexceptions
 CFLAGS-glob64.c = $(uses-callbacks) -fexceptions
 CFLAGS-getconf.c = -DGETCONF_DIR='"$(libexecdir)/getconf"'
+CFLAGS-execve.os = -fomit-frame-pointer
+CFLAGS-fexecve.os = -fomit-frame-pointer
+CFLAGS-execv.os = -fomit-frame-pointer
+CFLAGS-execle.os = -fomit-frame-pointer
+CFLAGS-execl.os = -fomit-frame-pointer
+CFLAGS-execvp.os = -fomit-frame-pointer
+CFLAGS-execlp.os = -fomit-frame-pointer
 
 tstgetopt-ARGS = -a -b -cfoobar --required foobar --optional=bazbug \
 		--none random --col --color --colour
diff --git a/posix/bug-regex19.c b/posix/bug-regex19.c
index 4000b19b4d..3a173a6ca0 100644
--- a/posix/bug-regex19.c
+++ b/posix/bug-regex19.c
@@ -1,5 +1,5 @@
 /* Regular expression tests.
-   Copyright (C) 2003 Free Software Foundation, Inc.
+   Copyright (C) 2003, 2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Jakub Jelinek <jakub@redhat.com>, 2003.
 
@@ -170,22 +170,22 @@ static struct test_s
   {ERE, "[^k]\\B[^k]", "kBk", 0, -1},
   {ERE, "[^C]\\B[^C]", "CCCABA", 0, 3},
   {ERE, "[^C]\\B[^C]", "CBC", 0, -1},
-  {ERE, ".(\\b|\\B).", "=~AB", 0, 1},
+  {ERE, ".(\\b|\\B).", "=~AB", 0, 0},
   {ERE, ".(\\b|\\B).", "A=C", 0, 0},
   {ERE, ".(\\b|\\B).", "ABC", 0, 0},
-  {ERE, ".(\\b|\\B).", "=~\\!", 0, -1},
-  {ERE, "[^k](\\b|\\B)[^k]", "=~AB", 0, 1},
+  {ERE, ".(\\b|\\B).", "=~\\!", 0, 0},
+  {ERE, "[^k](\\b|\\B)[^k]", "=~AB", 0, 0},
   {ERE, "[^k](\\b|\\B)[^k]", "A=C", 0, 0},
   {ERE, "[^k](\\b|\\B)[^k]", "ABC", 0, 0},
-  {ERE, "[^k](\\b|\\B)[^k]", "=~kBD", 0, 3},
-  {ERE, "[^k](\\b|\\B)[^k]", "=~\\!", 0, -1},
-  {ERE, "[^k](\\b|\\B)[^k]", "=~kB", 0, -1},
-  {ERE, "[^C](\\b|\\B)[^C]", "=~AB", 0, 1},
+  {ERE, "[^k](\\b|\\B)[^k]", "=~kBD", 0, 0},
+  {ERE, "[^k](\\b|\\B)[^k]", "=~\\!", 0, 0},
+  {ERE, "[^k](\\b|\\B)[^k]", "=~kB", 0, 0},
+  {ERE, "[^C](\\b|\\B)[^C]", "=~AB", 0, 0},
   {ERE, "[^C](\\b|\\B)[^C]", "A=C", 0, 0},
   {ERE, "[^C](\\b|\\B)[^C]", "ABC", 0, 0},
-  {ERE, "[^C](\\b|\\B)[^C]", "=~CBD", 0, 3},
-  {ERE, "[^C](\\b|\\B)[^C]", "=~\\!", 0, -1},
-  {ERE, "[^C](\\b|\\B)[^C]", "=~CB", 0, -1},
+  {ERE, "[^C](\\b|\\B)[^C]", "=~CBD", 0, 0},
+  {ERE, "[^C](\\b|\\B)[^C]", "=~\\!", 0, 0},
+  {ERE, "[^C](\\b|\\B)[^C]", "=~CB", 0, 0},
   {ERE, "\\b([A]|[!]|.B)", "A=AC", 0, 0},
   {ERE, "\\b([A]|[!]|.B)", "=AC", 0, 1},
   {ERE, "\\b([A]|[!]|.B)", "!AC", 0, 1},
diff --git a/posix/execl.c b/posix/execl.c
index 62fd45db58..12b59f9de3 100644
--- a/posix/execl.c
+++ b/posix/execl.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,92,94,97,98,99,2002 Free Software Foundation, Inc.
+/* Copyright (C) 1991,92,94,97,98,99,2002,2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -16,10 +16,10 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
-#include <alloca.h>
 #include <unistd.h>
 #include <stdarg.h>
 #include <stddef.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include <stackinfo.h>
@@ -33,46 +33,44 @@
 int
 execl (const char *path, const char *arg, ...)
 {
-  size_t argv_max = 1024;
-  const char **argv = alloca (argv_max * sizeof (const char *));
-  unsigned int i;
+#define INITIAL_ARGV_MAX 1024
+  size_t argv_max = INITIAL_ARGV_MAX;
+  const char *initial_argv[INITIAL_ARGV_MAX];
+  const char **argv = initial_argv;
   va_list args;
 
   argv[0] = arg;
 
   va_start (args, arg);
-  i = 0;
+  unsigned int i = 0;
   while (argv[i++] != NULL)
     {
       if (i == argv_max)
 	{
-	  const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *));
-
-#ifndef _STACK_GROWS_UP
-	  if ((char *) nptr + argv_max == (char *) argv)
+	  argv_max *= 2;
+	  const char **nptr = realloc (argv == initial_argv ? NULL : argv,
+				       argv_max * sizeof (const char *));
+	  if (nptr == NULL)
 	    {
-	      /* Stack grows down.  */
-	      argv = (const char **) memcpy (nptr, argv,
-					     i * sizeof (const char *));
-	      argv_max += i;
+	      if (argv != initial_argv)
+		free (argv);
+	      return -1;
 	    }
-	  else
-#endif
-#ifndef _STACK_GROWS_DOWN
-	    if ((char *) argv + i == (char *) nptr)
-	    /* Stack grows up.  */
-	    argv_max += i;
-	  else
-#endif
-	    /* We have a hole in the stack.  */
-	    argv = (const char **) memcpy (nptr, argv,
-					   i * sizeof (const char *));
+	  if (argv == initial_argv)
+	    /* We have to copy the already filled-in data ourselves.  */
+	    memcpy (nptr, argv, i * sizeof (const char *));
+
+	  argv = nptr;
 	}
 
       argv[i] = va_arg (args, const char *);
     }
   va_end (args);
 
-  return __execve (path, (char *const *) argv, __environ);
+  int ret = __execve (path, (char *const *) argv, __environ);
+  if (argv != initial_argv)
+    free (argv);
+
+  return ret;
 }
 libc_hidden_def (execl)
diff --git a/posix/execle.c b/posix/execle.c
index 2199ebeb74..70522ad2e5 100644
--- a/posix/execle.c
+++ b/posix/execle.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,97,98,99,2002 Free Software Foundation, Inc.
+/* Copyright (C) 1991,97,98,99,2002,2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -16,10 +16,10 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
-#include <alloca.h>
 #include <unistd.h>
 #include <stdarg.h>
 #include <stddef.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include <stackinfo.h>
@@ -29,48 +29,45 @@
 int
 execle (const char *path, const char *arg, ...)
 {
-  size_t argv_max = 1024;
-  const char **argv = alloca (argv_max * sizeof (const char *));
-  const char *const *envp;
-  unsigned int i;
+#define INITIAL_ARGV_MAX 1024
+  size_t argv_max = INITIAL_ARGV_MAX;
+  const char *initial_argv[INITIAL_ARGV_MAX];
+  const char **argv = initial_argv;
   va_list args;
   argv[0] = arg;
 
   va_start (args, arg);
-  i = 0;
+  unsigned int i = 0;
   while (argv[i++] != NULL)
     {
       if (i == argv_max)
 	{
-	  const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *));
-
-#ifndef _STACK_GROWS_UP
-	  if ((char *) nptr + argv_max == (char *) argv)
+	  argv_max *= 2;
+	  const char **nptr = realloc (argv == initial_argv ? NULL : argv,
+				       argv_max * sizeof (const char *));
+	  if (nptr == NULL)
 	    {
-	      /* Stack grows down.  */
-	      argv = (const char **) memcpy (nptr, argv,
-					     i * sizeof (const char *));
-	      argv_max += i;
+	      if (argv != initial_argv)
+		free (argv);
+	      return -1;
 	    }
-	  else
-#endif
-#ifndef _STACK_GROWS_DOWN
-	    if ((char *) argv + i == (char *) nptr)
-	    /* Stack grows up.  */
-	    argv_max += i;
-	  else
-#endif
-	    /* We have a hole in the stack.  */
-	    argv = (const char **) memcpy (nptr, argv,
-					   i * sizeof (const char *));
+	  if (argv == initial_argv)
+	    /* We have to copy the already filled-in data ourselves.  */
+	    memcpy (nptr, argv, i * sizeof (const char *));
+
+	  argv = nptr;
 	}
 
       argv[i] = va_arg (args, const char *);
     }
 
-  envp = va_arg (args, const char *const *);
+  const char *const *envp = va_arg (args, const char *const *);
   va_end (args);
 
-  return __execve (path, (char *const *) argv, (char *const *) envp);
+  int ret = __execve (path, (char *const *) argv, (char *const *) envp);
+  if (argv != initial_argv)
+    free (argv);
+
+  return ret;
 }
 libc_hidden_def (execle)
diff --git a/posix/execlp.c b/posix/execlp.c
index ba8fc74c90..66996a9367 100644
--- a/posix/execlp.c
+++ b/posix/execlp.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,93,96,97,98,99,2002 Free Software Foundation, Inc.
+/* Copyright (C) 1991,93,96,97,98,99,2002,2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -16,10 +16,10 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
-#include <alloca.h>
 #include <unistd.h>
 #include <stdarg.h>
 #include <stddef.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include <stackinfo.h>
@@ -30,46 +30,44 @@
 int
 execlp (const char *file, const char *arg, ...)
 {
-  size_t argv_max = 1024;
-  const char **argv = alloca (argv_max * sizeof (const char *));
-  unsigned int i;
+#define INITIAL_ARGV_MAX 1024
+  size_t argv_max = INITIAL_ARGV_MAX;
+  const char *initial_argv[INITIAL_ARGV_MAX];
+  const char **argv = initial_argv;
   va_list args;
 
   argv[0] = arg;
 
   va_start (args, arg);
-  i = 0;
+  unsigned int i = 0;
   while (argv[i++] != NULL)
     {
       if (i == argv_max)
 	{
-	  const char **nptr = alloca ((argv_max *= 2) * sizeof (const char *));
-
-#ifndef _STACK_GROWS_UP
-	  if ((char *) nptr + argv_max == (char *) argv)
+	  argv_max *= 2;
+	  const char **nptr = realloc (argv == initial_argv ? NULL : argv,
+				       argv_max * sizeof (const char *));
+	  if (nptr == NULL)
 	    {
-	      /* Stack grows down.  */
-	      argv = (const char **) memcpy (nptr, argv,
-					     i * sizeof (const char *));
-	      argv_max += i;
+	      if (argv != initial_argv)
+		free (argv);
+	      return -1;
 	    }
-	  else
-#endif
-#ifndef _STACK_GROWS_DOWN
-	    if ((char *) argv + i == (char *) nptr)
-	    /* Stack grows up.  */
-	    argv_max += i;
-	  else
-#endif
-	    /* We have a hole in the stack.  */
-	    argv = (const char **) memcpy (nptr, argv,
-					   i * sizeof (const char *));
+	  if (argv == initial_argv)
+	    /* We have to copy the already filled-in data ourselves.  */
+	    memcpy (nptr, argv, i * sizeof (const char *));
+
+	  argv = nptr;
 	}
 
       argv[i] = va_arg (args, const char *);
     }
   va_end (args);
 
-  return execvp (file, (char *const *) argv);
+  int ret = execvp (file, (char *const *) argv);
+  if (argv != initial_argv)
+    free (argv);
+
+  return ret;
 }
 libc_hidden_def (execlp)
diff --git a/posix/execvp.c b/posix/execvp.c
index d6f60c02e7..9ccfd7fc22 100644
--- a/posix/execvp.c
+++ b/posix/execvp.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,92,1995-99,2002,2004 Free Software Foundation, Inc.
+/* Copyright (C) 1991,92,1995-99,2002,2004,2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -18,6 +18,7 @@
 
 #include <unistd.h>
 #include <stdarg.h>
+#include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #include <errno.h>
@@ -26,9 +27,9 @@
 
 /* The file is accessible but it is not an executable file.  Invoke
    the shell to interpret it as a script.  */
-static void
+static char **
 internal_function
-script_execute (const char *file, char *const argv[])
+allocate_scripts_argv (const char *file, char *const argv[])
 {
   /* Count the arguments.  */
   int argc = 0;
@@ -36,19 +37,19 @@ script_execute (const char *file, char *const argv[])
     ;
 
   /* Construct an argument list for the shell.  */
-  {
-    char *new_argv[argc + 1];
-    new_argv[0] = (char *) _PATH_BSHELL;
-    new_argv[1] = (char *) file;
-    while (argc > 1)
-      {
-	new_argv[argc] = argv[argc - 1];
-	--argc;
-      }
-
-    /* Execute the shell.  */
-    __execve (new_argv[0], new_argv, __environ);
-  }
+  char **new_argv = (char **) malloc ((argc + 1) * sizeof (char *));
+  if (new_argv != NULL)
+    {
+      new_argv[0] = (char *) _PATH_BSHELL;
+      new_argv[1] = (char *) file;
+      while (argc > 1)
+	{
+	  new_argv[argc] = argv[argc - 1];
+	  --argc;
+	}
+    }
+
+  return new_argv;
 }
 
 
@@ -66,42 +67,58 @@ execvp (file, argv)
       return -1;
     }
 
+  char **script_argv = NULL;
+
   if (strchr (file, '/') != NULL)
     {
       /* Don't search when it contains a slash.  */
       __execve (file, argv, __environ);
 
       if (errno == ENOEXEC)
-	script_execute (file, argv);
+	{
+	  script_argv = allocate_scripts_argv (file, argv);
+	  if (script_argv != NULL)
+	    {
+	      __execve (script_argv[0], script_argv, __environ);
+
+	      free (script_argv);
+	    }
+	}
     }
   else
     {
-      int got_eacces = 0;
-      char *path, *p, *name;
-      size_t len;
-      size_t pathlen;
-
-      path = getenv ("PATH");
+      char *path = getenv ("PATH");
+      bool path_malloc = false;
       if (path == NULL)
 	{
 	  /* There is no `PATH' in the environment.
 	     The default search path is the current directory
 	     followed by the path `confstr' returns for `_CS_PATH'.  */
-	  len = confstr (_CS_PATH, (char *) NULL, 0);
-	  path = (char *) __alloca (1 + len);
+	  size_t len = confstr (_CS_PATH, (char *) NULL, 0);
+	  path = (char *) malloc (1 + len);
+	  if (path == NULL)
+	    return -1;
 	  path[0] = ':';
 	  (void) confstr (_CS_PATH, path + 1, len);
+	  path_malloc = true;
 	}
 
-      len = strlen (file) + 1;
-      pathlen = strlen (path);
-      name = __alloca (pathlen + len + 1);
+      size_t len = strlen (file) + 1;
+      size_t pathlen = strlen (path);
+      char *name = malloc (pathlen + len + 1);
+      if (name == NULL)
+	{
+	  if (path_malloc)
+	    free (path);
+	  return -1;
+	}
       /* Copy the file name at the top.  */
       name = (char *) memcpy (name + pathlen + 1, file, len);
       /* And add the slash.  */
       *--name = '/';
 
-      p = path;
+      bool got_eacces = false;
+      char *p = path;
       do
 	{
 	  char *startp;
@@ -120,7 +137,21 @@ execvp (file, argv)
 	  __execve (startp, argv, __environ);
 
 	  if (errno == ENOEXEC)
-	    script_execute (startp, argv);
+	    {
+	      if (script_argv == NULL)
+		{
+		  script_argv = allocate_scripts_argv (file, argv);
+		  if (script_argv == NULL)
+		    {
+		      /* A possible EACCES error is not as important as
+			 the ENOMEM.  */
+		      got_eacces = false;
+		      break;
+		    }
+		}
+
+	      __execve (script_argv[0], script_argv, __environ);
+	    }
 
 	  switch (errno)
 	    {
@@ -128,7 +159,7 @@ execvp (file, argv)
 	      /* Record the we got a `Permission denied' error.  If we end
 		 up finding no executable we can use, we want to diagnose
 		 that we did find one but were denied access.  */
-	      got_eacces = 1;
+	      got_eacces = true;
 	    case ENOENT:
 	    case ESTALE:
 	    case ENOTDIR:
@@ -156,6 +187,11 @@ execvp (file, argv)
 	/* At least one failure was due to permissions, so report that
            error.  */
 	__set_errno (EACCES);
+
+      free (script_argv);
+      free (name);
+      if (path_malloc)
+	free (path);
     }
 
   /* Return the error from the last attempt (probably ENOENT).  */
diff --git a/posix/getconf.c b/posix/getconf.c
index 4ce4f8e413..0cc0c0d7b5 100644
--- a/posix/getconf.c
+++ b/posix/getconf.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991, 92, 1995-2003, 2004 Free Software Foundation, Inc.
+/* Copyright (C) 1991, 92, 1995-2003, 2004, 2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
    The GNU C Library is free software; you can redistribute it and/or
@@ -964,7 +964,7 @@ main (int argc, char *argv[])
 Copyright (C) %s Free Software Foundation, Inc.\n\
 This is free software; see the source for copying conditions.  There is NO\n\
 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
-"), "2004");
+"), "2005");
       fprintf (stderr, gettext ("Written by %s.\n"), "Roland McGrath");
       return 0;
     }
diff --git a/posix/regcomp.c b/posix/regcomp.c
index 5de5bf725a..1a5f7952c3 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -1,5 +1,5 @@
 /* Extended regular expression matching and search library.
-   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
 
@@ -33,19 +33,21 @@ static reg_errcode_t create_initial_state (re_dfa_t *dfa);
 #ifdef RE_ENABLE_I18N
 static void optimize_utf8 (re_dfa_t *dfa);
 #endif
-struct subexp_optimize
-{
-  re_dfa_t *dfa;
-  re_token_t *nodes;
-  int no_sub, re_nsub;
-};
-static bin_tree_t *optimize_subexps (struct subexp_optimize *so,
-                                     bin_tree_t *node, int sidx, int depth);
-static reg_errcode_t analyze (re_dfa_t *dfa);
-static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);
-static void calc_first (re_dfa_t *dfa, bin_tree_t *node);
-static void calc_next (re_dfa_t *dfa, bin_tree_t *node);
-static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node);
+static reg_errcode_t analyze (regex_t *preg);
+static reg_errcode_t create_initial_state (re_dfa_t *dfa);
+static reg_errcode_t preorder (bin_tree_t *root,
+			       reg_errcode_t (fn (void *, bin_tree_t *)),
+			       void *extra);
+static reg_errcode_t postorder (bin_tree_t *root,
+				reg_errcode_t (fn (void *, bin_tree_t *)),
+				void *extra);
+static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
+static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
+static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
+				 bin_tree_t *node);
+static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
+static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
+static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
 static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
 					     int top_clone_node, int root_node,
 					     unsigned int constraint);
@@ -56,7 +58,7 @@ static int search_duplicated_node (re_dfa_t *dfa, int org_node,
 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
 					 int node, int root);
-static void calc_inveclosure (re_dfa_t *dfa);
+static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
 static int fetch_number (re_string_t *input, re_token_t *token,
 			 reg_syntax_t syntax);
 static void fetch_token (re_token_t *result, re_string_t *input,
@@ -138,14 +140,14 @@ static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
 				       int non_match, reg_errcode_t *err);
 static bin_tree_t *create_tree (re_dfa_t *dfa,
 				bin_tree_t *left, bin_tree_t *right,
-				re_token_type_t type, int index);
-static bin_tree_t *re_dfa_add_tree_node (re_dfa_t *dfa,
-					 bin_tree_t *left, bin_tree_t *right,
-					 const re_token_t *token)
-  __attribute ((noinline));
+				re_token_type_t type);
+static bin_tree_t *create_token_tree (re_dfa_t *dfa,
+				      bin_tree_t *left, bin_tree_t *right,
+				      const re_token_t *token);
 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
-static void mark_opt_subexp (const bin_tree_t *src, re_dfa_t *dfa);
-static void mark_opt_subexp_iter (const bin_tree_t *src, re_dfa_t *dfa, int idx);
+static void free_token (re_token_t *node);
+static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
+static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
 
 /* This table gives an error message for each of the error codes listed
    in regex.h.  Obviously the order here has to be same as there.
@@ -598,16 +600,7 @@ free_dfa_content (re_dfa_t *dfa)
 
   if (dfa->nodes)
     for (i = 0; i < dfa->nodes_len; ++i)
-      {
-	re_token_t *node = dfa->nodes + i;
-#ifdef RE_ENABLE_I18N
-	if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
-	  free_charset (node->opr.mbcset);
-	else
-#endif /* RE_ENABLE_I18N */
-	  if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
-	    re_free (node->opr.sbcset);
-      }
+      free_token (dfa->nodes + i);
   re_free (dfa->nexts);
   for (i = 0; i < dfa->nodes_len; ++i)
     {
@@ -811,29 +804,17 @@ re_compile_internal (preg, pattern, length, syntax)
   if (BE (dfa->str_tree == NULL, 0))
     goto re_compile_internal_free_return;
 
+  /* Analyze the tree and create the nfa.  */
+  err = analyze (preg);
+  if (BE (err != REG_NOERROR, 0))
+    goto re_compile_internal_free_return;
+
 #ifdef RE_ENABLE_I18N
   /* If possible, do searching in single byte encoding to speed things up.  */
   if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)
     optimize_utf8 (dfa);
 #endif
 
-  if (preg->re_nsub > 0)
-    {
-      struct subexp_optimize so;
-
-      so.dfa = dfa;
-      so.nodes = dfa->nodes;
-      so.no_sub = preg->no_sub;
-      so.re_nsub = preg->re_nsub;
-      dfa->str_tree = optimize_subexps (&so, dfa->str_tree, -1, 0);
-    }
-
-  /* Analyze the tree and collect information which is necessary to
-     create the dfa.  */
-  err = analyze (dfa);
-  if (BE (err != REG_NOERROR, 0))
-    goto re_compile_internal_free_return;
-
   /* Then create the initial state of the dfa.  */
   err = create_initial_state (dfa);
 
@@ -894,9 +875,9 @@ init_dfa (dfa, pat_len)
   codeset_name = nl_langinfo (CODESET);
 # else
   codeset_name = getenv ("LC_ALL");
-  if (codeset_name == NULL || codeset[0] == '\0')
+  if (codeset_name == NULL || codeset_name[0] == '\0')
     codeset_name = getenv ("LC_CTYPE");
-  if (codeset_name == NULL || codeset[0] == '\0')
+  if (codeset_name == NULL || codeset_name[0] == '\0')
     codeset_name = getenv ("LANG");
   if (codeset_name == NULL)
     codeset_name = "";
@@ -998,7 +979,7 @@ create_initial_state (dfa)
 
   /* Initial states have the epsilon closure of the node which is
      the first node of the regular expression.  */
-  first = dfa->str_tree->first;
+  first = dfa->str_tree->first->node_idx;
   dfa->init_node = first;
   err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
   if (BE (err != REG_NOERROR, 0))
@@ -1104,10 +1085,11 @@ optimize_utf8 (dfa)
       case OP_ALT:
       case END_OF_RE:
       case OP_DUP_ASTERISK:
-      case OP_DUP_QUESTION:
       case OP_OPEN_SUBEXP:
       case OP_CLOSE_SUBEXP:
 	break;
+      case COMPLEX_BRACKET:
+	return;
       case SIMPLE_BRACKET:
 	/* Just double check.  */
         for (i = 0x80 / UINT_BITS; i < BITSET_UINTS; ++i)
@@ -1115,7 +1097,7 @@ optimize_utf8 (dfa)
 	    return;
 	break;
       default:
-	return;
+	abort ();
       }
 
   if (mb_chars || has_period)
@@ -1135,90 +1117,14 @@ optimize_utf8 (dfa)
 }
 #endif
 
-static bin_tree_t *
-optimize_subexps (so, node, sidx, depth)
-     struct subexp_optimize *so;
-     bin_tree_t *node;
-     int sidx, depth;
-{
-  int idx, new_depth, new_sidx;
-  bin_tree_t *ret;
-  if (node == NULL)
-    return NULL;
-
-  new_depth = 0;
-  new_sidx = sidx;
-  if ((depth & 1) && node->type == CONCAT
-      && node->right && node->right->type == 0
-      && so->nodes[idx = node->right->node_idx].type == OP_CLOSE_SUBEXP)
-    {
-      new_depth = depth + 1;
-      if (new_depth == 2
-          || (so->nodes[idx].opr.idx < 8 * sizeof (so->dfa->used_bkref_map)
-              && so->dfa->used_bkref_map & (1 << so->nodes[idx].opr.idx)))
-        new_sidx = so->nodes[idx].opr.idx;
-    }
-  node->left = optimize_subexps (so, node->left, new_sidx, new_depth);
-  new_depth = (depth & 1) == 0 && node->type == CONCAT
-              && node->left && node->left->type == 0
-              && so->nodes[node->left->node_idx].type == OP_OPEN_SUBEXP
-              ? depth + 1 : 0;
-  node->right = optimize_subexps (so, node->right, sidx, new_depth);
-                                     
-  if (node->type != CONCAT)
-    return node;
-  if ((depth & 1) == 0
-      && node->left
-      && node->left->type == 0
-      && so->nodes[idx = node->left->node_idx].type == OP_OPEN_SUBEXP)
-    ret = node->right;
-  else if ((depth & 1)
-           && node->right
-           && node->right->type == 0
-           && so->nodes[idx = node->right->node_idx].type == OP_CLOSE_SUBEXP)
-    ret = node->left;
-  else
-    return node;
-
-  if (so->nodes[idx].opr.idx < 8 * sizeof (so->dfa->used_bkref_map)
-      && so->dfa->used_bkref_map & (1 << so->nodes[idx].opr.idx))
-    return node;
-
-  if (!so->no_sub)
-    {
-      int i;
-
-      if (depth < 2)
-        return node;
-
-      if (so->dfa->subexp_map == NULL)
-        {
-          so->dfa->subexp_map = re_malloc (int, so->re_nsub);
-          if (so->dfa->subexp_map == NULL)
-            return node;
-
-          for (i = 0; i < so->re_nsub; i++)
-            so->dfa->subexp_map[i] = i;
-        }
-
-      i = so->nodes[idx].opr.idx;
-      assert (sidx < i);
-      so->dfa->subexp_map[i] = sidx;
-    }
-
-  so->nodes[idx].type = OP_DELETED_SUBEXP;
-  ret->parent = node->parent;
-  return ret;
-}
-
 /* Analyze the structure tree, and calculate "first", "next", "edest",
    "eclosure", and "inveclosure".  */
 
 static reg_errcode_t
-analyze (dfa)
-     re_dfa_t *dfa;
+analyze (preg)
+     regex_t *preg;
 {
-  int i;
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
   reg_errcode_t ret;
 
   /* Allocate arrays.  */
@@ -1226,225 +1132,321 @@ analyze (dfa)
   dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
   dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
   dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
-  dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
   if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
-	  || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
+	  || dfa->eclosures == NULL, 0))
     return REG_ESPACE;
-  /* Initialize them.  */
-  for (i = 0; i < dfa->nodes_len; ++i)
+
+  dfa->subexp_map = re_malloc (int, preg->re_nsub);
+  if (dfa->subexp_map != NULL)
     {
-      dfa->nexts[i] = -1;
-      re_node_set_init_empty (dfa->edests + i);
-      re_node_set_init_empty (dfa->eclosures + i);
-      re_node_set_init_empty (dfa->inveclosures + i);
+      int i;
+      for (i = 0; i < preg->re_nsub; i++)
+	dfa->subexp_map[i] = i;
+      preorder (dfa->str_tree, optimize_subexps, dfa);
+      for (i = 0; i < preg->re_nsub; i++)
+	if (dfa->subexp_map[i] != i)
+	  break;
+      if (i == preg->re_nsub)
+	{
+	  free (dfa->subexp_map);
+	  dfa->subexp_map = NULL;
+	}
     }
 
-  ret = analyze_tree (dfa, dfa->str_tree);
-  if (BE (ret == REG_NOERROR, 1))
+  ret = postorder (dfa->str_tree, lower_subexps, preg);
+  if (BE (ret != REG_NOERROR, 0))
+    return ret;
+  ret = postorder (dfa->str_tree, calc_first, dfa);
+  if (BE (ret != REG_NOERROR, 0))
+    return ret;
+  preorder (dfa->str_tree, calc_next, dfa);
+  ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
+  if (BE (ret != REG_NOERROR, 0))
+    return ret;
+  ret = calc_eclosure (dfa);
+  if (BE (ret != REG_NOERROR, 0))
+    return ret;
+
+  /* We only need this during the prune_impossible_nodes pass in regexec.c;
+     skip it if p_i_n will not run, as calc_inveclosure can be quadratic.  */
+  if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
+      || dfa->nbackref)
     {
-      ret = calc_eclosure (dfa);
-      if (ret == REG_NOERROR)
-	calc_inveclosure (dfa);
+      dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
+      if (BE (dfa->inveclosures == NULL, 0))
+        return REG_ESPACE;
+      ret = calc_inveclosure (dfa);
     }
+
   return ret;
 }
 
-/* Helper functions for analyze.
-   This function calculate "first", "next", and "edest" for the subtree
-   whose root is NODE.  */
+/* Our parse trees are very unbalanced, so we cannot use a stack to
+   implement parse tree visits.  Instead, we use parent pointers and
+   some hairy code in these two functions.  */
+static reg_errcode_t
+postorder (root, fn, extra)
+     bin_tree_t *root;
+     reg_errcode_t (fn (void *, bin_tree_t *));
+     void *extra;
+{
+  bin_tree_t *node, *prev;
+
+  for (node = root; ; )
+    {
+      /* Descend down the tree, preferably to the left (or to the right
+	 if that's the only child).  */
+      while (node->left || node->right)
+	if (node->left)
+          node = node->left;
+        else
+          node = node->right;
+
+      do
+	{
+	  reg_errcode_t err = fn (extra, node);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+          if (node->parent == NULL)
+	    return REG_NOERROR;
+	  prev = node;
+	  node = node->parent;
+	}
+      /* Go up while we have a node that is reached from the right.  */
+      while (node->right == prev || node->right == NULL);
+      node = node->right;
+    }
+}
 
 static reg_errcode_t
-analyze_tree (dfa, node)
-     re_dfa_t *dfa;
+preorder (root, fn, extra)
+     bin_tree_t *root;
+     reg_errcode_t (fn (void *, bin_tree_t *));
+     void *extra;
+{
+  bin_tree_t *node;
+
+  for (node = root; ; )
+    {
+      reg_errcode_t err = fn (extra, node);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
+
+      /* Go to the left node, or up and to the right.  */
+      if (node->left)
+	node = node->left;
+      else
+	{
+	  bin_tree_t *prev = NULL;
+	  while (node->right == prev || node->right == NULL)
+	    {
+	      prev = node;
+	      node = node->parent;
+	      if (!node)
+	        return REG_NOERROR;
+	    }
+	  node = node->right;
+	}
+    }
+}
+
+/* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
+   re_search_internal to map the inner one's opr.idx to this one's.  Adjust
+   backreferences as well.  Requires a preorder visit.  */
+static reg_errcode_t
+optimize_subexps (extra, node)
+     void *extra;
      bin_tree_t *node;
 {
-  reg_errcode_t ret;
-  if (node->first == -1)
-    calc_first (dfa, node);
-  if (node->next == -1)
-    calc_next (dfa, node);
-  calc_epsdest (dfa, node);
+  re_dfa_t *dfa = (re_dfa_t *) extra;
 
-  /* Calculate "first" etc. for the left child.  */
-  if (node->left != NULL)
+  if (node->token.type == OP_BACK_REF && dfa->subexp_map)
     {
-      ret = analyze_tree (dfa, node->left);
-      if (BE (ret != REG_NOERROR, 0))
-	return ret;
+      int idx = node->token.opr.idx;
+      node->token.opr.idx = dfa->subexp_map[idx];
+      dfa->used_bkref_map |= 1 << node->token.opr.idx;
     }
-  /* Calculate "first" etc. for the right child.  */
-  if (node->right != NULL)
+
+  else if (node->token.type == SUBEXP
+           && node->left && node->left->token.type == SUBEXP)
     {
-      ret = analyze_tree (dfa, node->right);
-      if (BE (ret != REG_NOERROR, 0))
-	return ret;
+      int other_idx = node->left->token.opr.idx;
+
+      node->left = node->left->left;
+      if (node->left)
+        node->left->parent = node;
+
+      dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
+      if (other_idx < 8 * sizeof (dfa->used_bkref_map))
+	dfa->used_bkref_map &= ~(1 << other_idx);
     }
+
   return REG_NOERROR;
 }
 
-/* Calculate "first" for the node NODE.  */
-static void
-calc_first (dfa, node)
-     re_dfa_t *dfa;
+/* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
+   of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP.  */
+static reg_errcode_t
+lower_subexps (extra, node)
+     void *extra;
      bin_tree_t *node;
 {
-  int idx, type;
-  idx = node->node_idx;
-  type = (node->type == 0) ? dfa->nodes[idx].type : node->type;
+  regex_t *preg = (regex_t *) extra;
+  reg_errcode_t err = REG_NOERROR;
 
-  switch (type)
+  if (node->left && node->left->token.type == SUBEXP)
     {
-#ifdef DEBUG
-    case OP_OPEN_BRACKET:
-    case OP_CLOSE_BRACKET:
-    case OP_OPEN_DUP_NUM:
-    case OP_CLOSE_DUP_NUM:
-    case OP_DUP_PLUS:
-    case OP_NON_MATCH_LIST:
-    case OP_OPEN_COLL_ELEM:
-    case OP_CLOSE_COLL_ELEM:
-    case OP_OPEN_EQUIV_CLASS:
-    case OP_CLOSE_EQUIV_CLASS:
-    case OP_OPEN_CHAR_CLASS:
-    case OP_CLOSE_CHAR_CLASS:
-      /* These must not appear here.  */
-      assert (0);
-#endif
-    case END_OF_RE:
-    case CHARACTER:
-    case OP_PERIOD:
-    case OP_DUP_ASTERISK:
-    case OP_DUP_QUESTION:
-#ifdef RE_ENABLE_I18N
-    case OP_UTF8_PERIOD:
-    case COMPLEX_BRACKET:
-#endif /* RE_ENABLE_I18N */
-    case SIMPLE_BRACKET:
-    case OP_BACK_REF:
-    case ANCHOR:
-    case OP_OPEN_SUBEXP:
-    case OP_CLOSE_SUBEXP:
-      node->first = idx;
-      break;
-    case OP_ALT:
-      node->first = idx;
-      break;
-      /* else fall through */
-    default:
-#ifdef DEBUG
-      assert (node->left != NULL);
-#endif
-      if (node->left->first == -1)
-	calc_first (dfa, node->left);
-      node->first = node->left->first;
-      break;
+      node->left = lower_subexp (&err, preg, node->left);
+      if (node->left)
+	node->left->parent = node;
+    }
+  if (node->right && node->right->token.type == SUBEXP)
+    {
+      node->right = lower_subexp (&err, preg, node->right);
+      if (node->right)
+	node->right->parent = node;
     }
-}
 
-/* Calculate "next" for the node NODE.  */
+  return err;
+}
 
-static void
-calc_next (dfa, node)
-     re_dfa_t *dfa;
+static bin_tree_t *
+lower_subexp (err, preg, node)
+     reg_errcode_t *err;
+     regex_t *preg;
      bin_tree_t *node;
 {
-  int idx, type;
-  bin_tree_t *parent = node->parent;
-  if (parent == NULL)
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+  bin_tree_t *body = node->left;
+  bin_tree_t *op, *cls, *tree1, *tree;
+
+  if (preg->no_sub
+      && (node->token.opr.idx >= 8 * sizeof (dfa->used_bkref_map)
+	  || !(dfa->used_bkref_map & (1 << node->token.opr.idx))))
+    return node->left;
+
+  /* Convert the SUBEXP node to the concatenation of an
+     OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP.  */
+  op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
+  cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
+  tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
+  tree = create_tree (dfa, op, tree1, CONCAT);
+  if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
     {
-      node->next = -1;
-      idx = node->node_idx;
-      if (node->type == 0)
-	dfa->nexts[idx] = node->next;
-      return;
+      *err = REG_ESPACE;
+      return NULL;
     }
 
-  idx = parent->node_idx;
-  type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;
+  op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
+  op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
+  return tree;
+}
 
-  switch (type)
+/* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
+   nodes.  Requires a postorder visit.  */
+static reg_errcode_t
+calc_first (extra, node)
+     void *extra;
+     bin_tree_t *node;
+{
+  re_dfa_t *dfa = (re_dfa_t *) extra;
+  if (node->token.type == CONCAT)
+    {
+      node->first = node->left->first;
+      node->node_idx = node->left->node_idx;
+    }
+  else
+    {
+      node->first = node;
+      node->node_idx = re_dfa_add_node (dfa, node->token);
+      if (BE (node->node_idx == -1, 0))
+        return REG_ESPACE;
+    }
+  return REG_NOERROR;
+}
+
+/* Pass 2: compute NEXT on the tree.  Preorder visit.  */
+static reg_errcode_t
+calc_next (extra, node)
+     void *extra;
+     bin_tree_t *node;
+{
+  switch (node->token.type)
     {
     case OP_DUP_ASTERISK:
-      node->next = idx;
+      node->left->next = node;
       break;
     case CONCAT:
-      if (parent->left == node)
-	{
-	  if (parent->right->first == -1)
-	    calc_first (dfa, parent->right);
-	  node->next = parent->right->first;
-	  break;
-	}
-      /* else fall through */
+      node->left->next = node->right->first;
+      node->right->next = node->next;
+      break;
     default:
-      if (parent->next == -1)
-	calc_next (dfa, parent);
-      node->next = parent->next;
+      if (node->left)
+	node->left->next = node->next;
+      if (node->right)
+        node->right->next = node->next;
       break;
     }
-  idx = node->node_idx;
-  if (node->type == 0)
-    dfa->nexts[idx] = node->next;
+  return REG_NOERROR;
 }
 
-/* Calculate "edest" for the node NODE.  */
-
-static void
-calc_epsdest (dfa, node)
-     re_dfa_t *dfa;
+/* Pass 3: link all DFA nodes to their NEXT node (any order will do).  */
+static reg_errcode_t
+link_nfa_nodes (extra, node)
+     void *extra;
      bin_tree_t *node;
 {
-  int idx;
-  idx = node->node_idx;
-  if (node->type == 0)
+  re_dfa_t *dfa = (re_dfa_t *) extra;
+  int idx = node->node_idx;
+  reg_errcode_t err = REG_NOERROR;
+
+  switch (node->token.type)
     {
-      if (dfa->nodes[idx].type == OP_DUP_ASTERISK
-	  || dfa->nodes[idx].type == OP_DUP_QUESTION)
-	{
-	  if (node->left->first == -1)
-	    calc_first (dfa, node->left);
-	  if (node->next == -1)
-	    calc_next (dfa, node);
-	  re_node_set_init_2 (dfa->edests + idx, node->left->first,
-			      node->next);
-	}
-      else if (dfa->nodes[idx].type == OP_ALT)
-	{
-	  int left, right;
-	  if (node->left != NULL)
-	    {
-	      if (node->left->first == -1)
-		calc_first (dfa, node->left);
-	      left = node->left->first;
-	    }
-	  else
-	    {
-	      if (node->next == -1)
-		calc_next (dfa, node);
-	      left = node->next;
-	    }
-	  if (node->right != NULL)
-	    {
-	      if (node->right->first == -1)
-		calc_first (dfa, node->right);
-	      right = node->right->first;
-	    }
-	  else
-	    {
-	      if (node->next == -1)
-		calc_next (dfa, node);
-	      right = node->next;
-	    }
-	  re_node_set_init_2 (dfa->edests + idx, left, right);
-	}
-      else if (dfa->nodes[idx].type == ANCHOR
-	       || dfa->nodes[idx].type == OP_OPEN_SUBEXP
-	       || dfa->nodes[idx].type == OP_CLOSE_SUBEXP
-	       || dfa->nodes[idx].type == OP_BACK_REF)
-	re_node_set_init_1 (dfa->edests + idx, node->next);
-      else
-        assert (!IS_EPSILON_NODE (dfa->nodes[idx].type));
+    case CONCAT:
+      break;
+
+    case END_OF_RE:
+      assert (node->next == NULL);
+      break;
+
+    case OP_DUP_ASTERISK:
+    case OP_ALT:
+      {
+	int left, right;
+	dfa->has_plural_match = 1;
+	if (node->left != NULL)
+	  left = node->left->first->node_idx;
+	else
+	  left = node->next->node_idx;
+	if (node->right != NULL)
+	  right = node->right->first->node_idx;
+	else
+	  right = node->next->node_idx;
+	assert (left > -1);
+	assert (right > -1);
+	err = re_node_set_init_2 (dfa->edests + idx, left, right);
+      }
+      break;
+
+    case ANCHOR:
+    case OP_OPEN_SUBEXP:
+    case OP_CLOSE_SUBEXP:
+      err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
+      break;
+
+    case OP_BACK_REF:
+      dfa->nexts[idx] = node->next->node_idx;
+      if (node->token.type == OP_BACK_REF)
+	re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
+      break;
+
+    default:
+      assert (!IS_EPSILON_NODE (node->token.type));
+      dfa->nexts[idx] = node->next->node_idx;
+      break;
     }
+
+  return err;
 }
 
 /* Duplicate the epsilon closure of the node ROOT_NODE.
@@ -1520,7 +1522,7 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
       else /* dfa->edests[org_node].nelem == 2 */
 	{
 	  /* In case of the node can epsilon-transit, and it has two
-	     destinations. E.g. '|', '*', '+', '?'.   */
+	     destinations. In the bin_tree_t and DFA, that's '|' and '*'.   */
 	  org_dest = dfa->edests[org_node].elems[0];
 	  re_node_set_empty (dfa->edests + clone_node);
 	  /* Search for a duplicated node which satisfies the constraint.  */
@@ -1591,16 +1593,13 @@ duplicate_node (new_idx, dfa, org_idx, constraint)
      int *new_idx, org_idx;
      unsigned int constraint;
 {
-  int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx], 1);
+  int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
   if (BE (dup_idx == -1, 0))
     return REG_ESPACE;
   dfa->nodes[dup_idx].constraint = constraint;
   if (dfa->nodes[org_idx].type == ANCHOR)
     dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
   dfa->nodes[dup_idx].duplicated = 1;
-  re_node_set_init_empty (dfa->edests + dup_idx);
-  re_node_set_init_empty (dfa->eclosures + dup_idx);
-  re_node_set_init_empty (dfa->inveclosures + dup_idx);
 
   /* Store the index of the original node.  */
   dfa->org_indices[dup_idx] = org_idx;
@@ -1608,21 +1607,26 @@ duplicate_node (new_idx, dfa, org_idx, constraint)
   return REG_NOERROR;
 }
 
-static void
+static reg_errcode_t
 calc_inveclosure (dfa)
      re_dfa_t *dfa;
 {
-  int src, idx, dest;
+  int src, idx, ret;
+  for (idx = 0; idx < dfa->nodes_len; ++idx)
+    re_node_set_init_empty (dfa->inveclosures + idx);
+
   for (src = 0; src < dfa->nodes_len; ++src)
     {
-      if (dfa->nodes[src].type == OP_DELETED_SUBEXP)
-        continue;
+      int *elems = dfa->eclosures[src].elems;
       for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
 	{
-	  dest = dfa->eclosures[src].elems[idx];
-	  re_node_set_insert_last (dfa->inveclosures + dest, src);
+	  ret = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
+	  if (BE (ret == -1, 0))
+	    return REG_ESPACE;
 	}
     }
+
+  return REG_NOERROR;
 }
 
 /* Calculate "eclosure" for all the node in DFA.  */
@@ -1652,8 +1656,6 @@ calc_eclosure (dfa)
 #ifdef DEBUG
       assert (dfa->eclosures[node_idx].nelem != -1);
 #endif
-      if (dfa->nodes[node_idx].type == OP_DELETED_SUBEXP)
-        continue;
 
       /* If we have already calculated, skip it.  */
       if (dfa->eclosures[node_idx].nelem != 0)
@@ -1859,7 +1861,7 @@ peek_token (token, input, syntax)
 	  if (!(syntax & RE_NO_GNU_OPS))
 	    {
 	      token->type = ANCHOR;
-	      token->opr.ctx_type = INSIDE_WORD;
+	      token->opr.ctx_type = NOT_WORD_DELIM;
 	    }
 	  break;
 	case 'w':
@@ -2124,9 +2126,9 @@ parse (regexp, preg, syntax, err)
   tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
   if (BE (*err != REG_NOERROR && tree == NULL, 0))
     return NULL;
-  eor = re_dfa_add_tree_node (dfa, NULL, NULL, &current_token);
+  eor = create_tree (dfa, NULL, NULL, END_OF_RE);
   if (tree != NULL)
-    root = create_tree (dfa, tree, eor, CONCAT, 0);
+    root = create_tree (dfa, tree, eor, CONCAT);
   else
     root = eor;
   if (BE (eor == NULL || root == NULL, 0))
@@ -2163,7 +2165,6 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err)
 
   while (token->type == OP_ALT)
     {
-      re_token_t alt_token = *token;
       fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
       if (token->type != OP_ALT && token->type != END_OF_RE
 	  && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
@@ -2174,13 +2175,12 @@ parse_reg_exp (regexp, preg, token, syntax, nest, err)
 	}
       else
 	branch = NULL;
-      tree = re_dfa_add_tree_node (dfa, tree, branch, &alt_token);
+      tree = create_tree (dfa, tree, branch, OP_ALT);
       if (BE (tree == NULL, 0))
 	{
 	  *err = REG_ESPACE;
 	  return NULL;
 	}
-      dfa->has_plural_match = 1;
     }
   return tree;
 }
@@ -2219,7 +2219,7 @@ parse_branch (regexp, preg, token, syntax, nest, err)
 	}
       if (tree != NULL && exp != NULL)
 	{
-	  tree = create_tree (dfa, tree, exp, CONCAT, 0);
+	  tree = create_tree (dfa, tree, exp, CONCAT);
 	  if (tree == NULL)
 	    {
 	      *err = REG_ESPACE;
@@ -2253,7 +2253,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
   switch (token->type)
     {
     case CHARACTER:
-      tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+      tree = create_token_tree (dfa, NULL, NULL, token);
       if (BE (tree == NULL, 0))
 	{
 	  *err = REG_ESPACE;
@@ -2267,8 +2267,8 @@ parse_expression (regexp, preg, token, syntax, nest, err)
 	    {
 	      bin_tree_t *mbc_remain;
 	      fetch_token (token, regexp, syntax);
-	      mbc_remain = re_dfa_add_tree_node (dfa, NULL, NULL, token);
-	      tree = create_tree (dfa, tree, mbc_remain, CONCAT, 0);
+	      mbc_remain = create_token_tree (dfa, NULL, NULL, token);
+	      tree = create_tree (dfa, tree, mbc_remain, CONCAT);
 	      if (BE (mbc_remain == NULL || tree == NULL, 0))
 		{
 		  *err = REG_ESPACE;
@@ -2295,7 +2295,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
 	  return NULL;
 	}
       dfa->used_bkref_map |= 1 << token->opr.idx;
-      tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+      tree = create_token_tree (dfa, NULL, NULL, token);
       if (BE (tree == NULL, 0))
 	{
 	  *err = REG_ESPACE;
@@ -2340,7 +2340,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
       token->type = CHARACTER;
       /* mb_partial and word_char bits should be initialized already
 	 by peek_token.  */
-      tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+      tree = create_token_tree (dfa, NULL, NULL, token);
       if (BE (tree == NULL, 0))
 	{
 	  *err = REG_ESPACE;
@@ -2349,18 +2349,27 @@ parse_expression (regexp, preg, token, syntax, nest, err)
       break;
     case ANCHOR:
       if ((token->opr.ctx_type
-	   & (WORD_DELIM | INSIDE_WORD | WORD_FIRST | WORD_LAST))
+	   & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
 	  && dfa->word_ops_used == 0)
 	init_word_char (dfa);
-      if (token->opr.ctx_type == WORD_DELIM)
+      if (token->opr.ctx_type == WORD_DELIM
+          || token->opr.ctx_type == NOT_WORD_DELIM)
 	{
 	  bin_tree_t *tree_first, *tree_last;
-	  token->opr.ctx_type = WORD_FIRST;
-	  tree_first = re_dfa_add_tree_node (dfa, NULL, NULL, token);
-	  token->opr.ctx_type = WORD_LAST;
-	  tree_last = re_dfa_add_tree_node (dfa, NULL, NULL, token);
-	  token->type = OP_ALT;
-	  tree = re_dfa_add_tree_node (dfa, tree_first, tree_last, token);
+	  if (token->opr.ctx_type == WORD_DELIM)
+	    {
+	      token->opr.ctx_type = WORD_FIRST;
+	      tree_first = create_token_tree (dfa, NULL, NULL, token);
+	      token->opr.ctx_type = WORD_LAST;
+            }
+          else
+            {
+	      token->opr.ctx_type = INSIDE_WORD;
+	      tree_first = create_token_tree (dfa, NULL, NULL, token);
+	      token->opr.ctx_type = INSIDE_NOTWORD;
+            }
+	  tree_last = create_token_tree (dfa, NULL, NULL, token);
+	  tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
 	  if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
 	    {
 	      *err = REG_ESPACE;
@@ -2369,7 +2378,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
 	}
       else
 	{
-	  tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+	  tree = create_token_tree (dfa, NULL, NULL, token);
 	  if (BE (tree == NULL, 0))
 	    {
 	      *err = REG_ESPACE;
@@ -2383,7 +2392,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
       fetch_token (token, regexp, syntax);
       return tree;
     case OP_PERIOD:
-      tree = re_dfa_add_tree_node (dfa, NULL, NULL, token);
+      tree = create_token_tree (dfa, NULL, NULL, token);
       if (BE (tree == NULL, 0))
 	{
 	  *err = REG_ESPACE;
@@ -2439,7 +2448,6 @@ parse_expression (regexp, preg, token, syntax, nest, err)
 	  *err = REG_BADRPT;
 	  return NULL;
 	}
-      dfa->has_plural_match = 1;
     }
 
   return tree;
@@ -2462,17 +2470,10 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err)
      reg_errcode_t *err;
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
-  bin_tree_t *tree, *left_par, *right_par;
+  bin_tree_t *tree;
   size_t cur_nsub;
   cur_nsub = preg->re_nsub++;
 
-  left_par = re_dfa_add_tree_node (dfa, NULL, NULL, token);
-  if (BE (left_par == NULL, 0))
-    {
-      *err = REG_ESPACE;
-      return NULL;
-    }
-  dfa->nodes[left_par->node_idx].opr.idx = cur_nsub;
   fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
 
   /* The subexpression may be a null string.  */
@@ -2481,26 +2482,20 @@ parse_sub_exp (regexp, preg, token, syntax, nest, err)
   else
     {
       tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
-      if (BE (*err != REG_NOERROR && tree == NULL, 0))
+      if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
+        *err = REG_EPAREN;
+      if (BE (*err != REG_NOERROR, 0))
 	return NULL;
     }
-  if (BE (token->type != OP_CLOSE_SUBEXP, 0))
-    {
-      *err = REG_EPAREN;
-      return NULL;
-    }
-  right_par = re_dfa_add_tree_node (dfa, NULL, NULL, token);
   dfa->completed_bkref_map |= 1 << cur_nsub;
-  tree = ((tree == NULL) ? right_par
-	  : create_tree (dfa, tree, right_par, CONCAT, 0));
-  tree = create_tree (dfa, left_par, tree, CONCAT, 0);
-  if (BE (right_par == NULL || tree == NULL, 0))
+
+  tree = create_tree (dfa, tree, NULL, SUBEXP);
+  if (BE (tree == NULL, 0))
     {
       *err = REG_ESPACE;
       return NULL;
     }
-  dfa->nodes[right_par->node_idx].opr.idx = cur_nsub;
-
+  tree->token.opr.idx = cur_nsub;
   return tree;
 }
 
@@ -2515,7 +2510,6 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err)
      reg_syntax_t syntax;
      reg_errcode_t *err;
 {
-  re_token_t dup_token;
   bin_tree_t *tree = NULL, *old_tree = NULL;
   int i, start, end, start_idx = re_string_cur_idx (regexp);
   re_token_t start_token = *token;
@@ -2578,9 +2572,13 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err)
 
   fetch_token (token, regexp, syntax);
 
-  /* Treat "<re>{0}*" etc. as "<re>{0}".  */
-  if (BE (elem == NULL || (start == 0 && end == 0), 0))
+  if (BE (elem == NULL, 0))
     return NULL;
+  if (BE (start == 0 && end == 0, 0))
+    {
+      postorder (elem, free_tree, NULL);
+      return NULL;
+    }
 
   /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}".  */
   if (BE (start > 0, 0))
@@ -2589,7 +2587,7 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err)
       for (i = 2; i <= start; ++i)
 	{
 	  elem = duplicate_tree (elem, dfa);
-	  tree = create_tree (dfa, tree, elem, CONCAT, 0);
+	  tree = create_tree (dfa, tree, elem, CONCAT);
 	  if (BE (elem == NULL || tree == NULL, 0))
 	    goto parse_dup_op_espace;
 	}
@@ -2604,9 +2602,10 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err)
   else
     old_tree = NULL;
 
-  mark_opt_subexp (elem, dfa);
-  dup_token.type = (end == -1 ? OP_DUP_ASTERISK : OP_DUP_QUESTION);
-  tree = re_dfa_add_tree_node (dfa, elem, NULL, &dup_token);
+  if (elem->token.type == SUBEXP)
+    postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
+
+  tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
   if (BE (tree == NULL, 0))
     goto parse_dup_op_espace;
 
@@ -2616,17 +2615,17 @@ parse_dup_op (elem, regexp, dfa, token, syntax, err)
   for (i = start + 2; i <= end; ++i)
     {
       elem = duplicate_tree (elem, dfa);
-      tree = create_tree (dfa, tree, elem, CONCAT, 0);
+      tree = create_tree (dfa, tree, elem, CONCAT);
       if (BE (elem == NULL || tree == NULL, 0))
         goto parse_dup_op_espace;
 
-      tree = re_dfa_add_tree_node (dfa, tree, NULL, &dup_token);
+      tree = create_tree (dfa, tree, NULL, OP_ALT);
       if (BE (tree == NULL, 0))
         goto parse_dup_op_espace;
     }
 
   if (old_tree)
-    tree = create_tree (dfa, old_tree, tree, CONCAT, 0);
+    tree = create_tree (dfa, old_tree, tree, CONCAT);
 
   return tree;
 
@@ -3282,57 +3281,59 @@ parse_bracket_exp (regexp, dfa, token, syntax, err)
   /* Ensure only single byte characters are set.  */
   if (dfa->mb_cur_max > 1)
     bitset_mask (sbcset, dfa->sb_char);
-#endif /* RE_ENABLE_I18N */
 
-  /* Build a tree for simple bracket.  */
-  br_token.type = SIMPLE_BRACKET;
-  br_token.opr.sbcset = sbcset;
-  work_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
-  if (BE (work_tree == NULL, 0))
-    goto parse_bracket_exp_espace;
-
-#ifdef RE_ENABLE_I18N
   if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
       || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
 						     || mbcset->non_match)))
     {
-      re_token_t alt_token;
       bin_tree_t *mbc_tree;
       int sbc_idx;
       /* Build a tree for complex bracket.  */
       dfa->has_mb_node = 1;
+      br_token.type = COMPLEX_BRACKET;
+      br_token.opr.mbcset = mbcset;
+      mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
+      if (BE (mbc_tree == NULL, 0))
+	goto parse_bracket_exp_espace;
       for (sbc_idx = 0; sbc_idx < BITSET_UINTS; ++sbc_idx)
 	if (sbcset[sbc_idx])
 	  break;
       /* If there are no bits set in sbcset, there is no point
 	 of having both SIMPLE_BRACKET and COMPLEX_BRACKET.  */
-      if (sbc_idx == BITSET_UINTS)
+      if (sbc_idx < BITSET_UINTS)
+	{
+          /* Build a tree for simple bracket.  */
+          br_token.type = SIMPLE_BRACKET;
+          br_token.opr.sbcset = sbcset;
+          work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
+          if (BE (work_tree == NULL, 0))
+            goto parse_bracket_exp_espace;
+
+          /* Then join them by ALT node.  */
+          work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
+          if (BE (work_tree == NULL, 0))
+            goto parse_bracket_exp_espace;
+	}
+      else
 	{
 	  re_free (sbcset);
-	  dfa->nodes[work_tree->node_idx].type = COMPLEX_BRACKET;
-	  dfa->nodes[work_tree->node_idx].opr.mbcset = mbcset;
-	  return work_tree;
+	  work_tree = mbc_tree;
 	}
-      br_token.type = COMPLEX_BRACKET;
-      br_token.opr.mbcset = mbcset;
-      mbc_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
-      if (BE (mbc_tree == NULL, 0))
-	goto parse_bracket_exp_espace;
-      /* Then join them by ALT node.  */
-      alt_token.type = OP_ALT;
-      dfa->has_plural_match = 1;
-      work_tree = re_dfa_add_tree_node (dfa, work_tree, mbc_tree, &alt_token);
-      if (BE (mbc_tree != NULL, 1))
-	return work_tree;
     }
   else
+#endif /* not RE_ENABLE_I18N */
     {
+#ifdef RE_ENABLE_I18N
       free_charset (mbcset);
-      return work_tree;
+#endif
+      /* Build a tree for simple bracket.  */
+      br_token.type = SIMPLE_BRACKET;
+      br_token.opr.sbcset = sbcset;
+      work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
+      if (BE (work_tree == NULL, 0))
+        goto parse_bracket_exp_espace;
     }
-#else /* not RE_ENABLE_I18N */
   return work_tree;
-#endif /* not RE_ENABLE_I18N */
 
  parse_bracket_exp_espace:
   *err = REG_ESPACE;
@@ -3693,26 +3694,23 @@ build_charclass_op (dfa, trans, class_name, extra, non_match, err)
   /* Build a tree for simple bracket.  */
   br_token.type = SIMPLE_BRACKET;
   br_token.opr.sbcset = sbcset;
-  tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
+  tree = create_token_tree (dfa, NULL, NULL, &br_token);
   if (BE (tree == NULL, 0))
     goto build_word_op_espace;
 
 #ifdef RE_ENABLE_I18N
   if (dfa->mb_cur_max > 1)
     {
-      re_token_t alt_token;
       bin_tree_t *mbc_tree;
       /* Build a tree for complex bracket.  */
       br_token.type = COMPLEX_BRACKET;
       br_token.opr.mbcset = mbcset;
       dfa->has_mb_node = 1;
-      mbc_tree = re_dfa_add_tree_node (dfa, NULL, NULL, &br_token);
+      mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
       if (BE (mbc_tree == NULL, 0))
 	goto build_word_op_espace;
       /* Then join them by ALT node.  */
-      alt_token.type = OP_ALT;
-      dfa->has_plural_match = 1;
-      tree = re_dfa_add_tree_node (dfa, tree, mbc_tree, &alt_token);
+      tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
       if (BE (mbc_tree != NULL, 1))
 	return tree;
     }
@@ -3783,12 +3781,23 @@ free_charset (re_charset_t *cset)
 /* Create a tree node.  */
 
 static bin_tree_t *
-create_tree (dfa, left, right, type, index)
+create_tree (dfa, left, right, type)
      re_dfa_t *dfa;
      bin_tree_t *left;
      bin_tree_t *right;
      re_token_type_t type;
-     int index;
+{
+  re_token_t t;
+  t.type = type;
+  return create_token_tree (dfa, left, right, &t);
+}
+
+static bin_tree_t *
+create_token_tree (dfa, left, right, token)
+     re_dfa_t *dfa;
+     bin_tree_t *left;
+     bin_tree_t *right;
+     const re_token_t *token;
 {
   bin_tree_t *tree;
   if (BE (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE, 0))
@@ -3806,11 +3815,12 @@ create_tree (dfa, left, right, type, index)
   tree->parent = NULL;
   tree->left = left;
   tree->right = right;
-  tree->type = type;
-  tree->node_idx = index;
-  tree->first = -1;
-  tree->next = -1;
-  re_node_set_init_empty (&tree->eclosure);
+  tree->token = *token;
+  tree->token.duplicated = 0;
+  tree->token.opt_subexp = 0;
+  tree->first = NULL;
+  tree->next = NULL;
+  tree->node_idx = -1;
 
   if (left != NULL)
     left->parent = tree;
@@ -3819,103 +3829,89 @@ create_tree (dfa, left, right, type, index)
   return tree;
 }
 
-/* Create both a DFA node and a tree for it.  */
+/* Mark the tree SRC as an optional subexpression.
+   To be called from preorder or postorder.  */
 
-static bin_tree_t *
-re_dfa_add_tree_node (dfa, left, right, token)
-     re_dfa_t *dfa;
-     bin_tree_t *left;
-     bin_tree_t *right;
-     const re_token_t *token;
+static reg_errcode_t
+mark_opt_subexp (extra, node)
+     void *extra;
+     bin_tree_t *node;
 {
-  int new_idx = re_dfa_add_node (dfa, *token, 0);
+  int idx = (int) (long) extra;
+  if (node->token.type == SUBEXP && node->token.opr.idx == idx)
+    node->token.opt_subexp = 1;
 
-  if (new_idx == -1)
-    return NULL;
-
-  return create_tree (dfa, left, right, 0, new_idx);
+  return REG_NOERROR;
 }
 
-/* Mark the tree SRC as an optional subexpression.  */
+/* Free the allocated memory inside NODE. */
 
 static void
-mark_opt_subexp (src, dfa)
-     const bin_tree_t *src;
-     re_dfa_t *dfa;
+free_token (re_token_t *node)
 {
-  /* Pass an OPT_SUBEXP_IDX which is != 1 if the duplicated tree is
-     a subexpression.  */
-  if (src->type == CONCAT
-      && src->left->type == NON_TYPE
-      && dfa->nodes[src->left->node_idx].type == OP_OPEN_SUBEXP)
-    mark_opt_subexp_iter (src, dfa, dfa->nodes[src->left->node_idx].opr.idx);
+#ifdef RE_ENABLE_I18N
+  if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
+    free_charset (node->opr.mbcset);
+  else
+#endif /* RE_ENABLE_I18N */
+    if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
+      re_free (node->opr.sbcset);
 }
 
+/* Worker function for tree walking.  Free the allocated memory inside NODE
+   and its children. */
 
-/* Recursive tree walker for mark_opt_subexp.  */
-
-static void
-mark_opt_subexp_iter (src, dfa, idx)
-     const bin_tree_t *src;
-     re_dfa_t *dfa;
-     int idx;
+static reg_errcode_t
+free_tree (void *extra, bin_tree_t *node)
 {
-  int node_idx;
-
-  if (src->type == NON_TYPE)
-    {
-      node_idx = src->node_idx;
-      if ((dfa->nodes[node_idx].type == OP_OPEN_SUBEXP
-	   || dfa->nodes[node_idx].type == OP_CLOSE_SUBEXP)
-	  && dfa->nodes[node_idx].opr.idx == idx)
-	dfa->nodes[node_idx].opt_subexp = 1;
-     }
-
-  if (src->left != NULL)
-    mark_opt_subexp_iter (src->left, dfa, idx);
-
-  if (src->right != NULL)
-    mark_opt_subexp_iter (src->right, dfa, idx);
+  free_token (&node->token);
+  return REG_NOERROR;
 }
 
 
-/* Duplicate the node SRC, and return new node.  */
+/* Duplicate the node SRC, and return new node.  This is a preorder
+   visit similar to the one implemented by the generic visitor, but
+   we need more infrastructure to maintain two parallel trees --- so,
+   it's easier to duplicate.  */
 
 static bin_tree_t *
-duplicate_tree (src, dfa)
-     const bin_tree_t *src;
+duplicate_tree (root, dfa)
+     const bin_tree_t *root;
      re_dfa_t *dfa;
 {
-  bin_tree_t *left = NULL, *right = NULL, *new_tree;
-  int new_node_idx;
-  /* Since node indies must be according to Post-order of the tree,
-     we must duplicate the left at first.  */
-  if (src->left != NULL)
-    {
-      left = duplicate_tree (src->left, dfa);
-      if (left == NULL)
-	return NULL;
-    }
+  const bin_tree_t *node;
+  bin_tree_t *dup_root;
+  bin_tree_t **p_new = &dup_root, *dup_node = root->parent;
 
-  /* Secondaly, duplicate the right.  */
-  if (src->right != NULL)
+  for (node = root; ; )
     {
-      right = duplicate_tree (src->right, dfa);
-      if (right == NULL)
+      /* Create a new tree and link it back to the current parent.  */
+      *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
+      if (*p_new == NULL)
 	return NULL;
-    }
+      (*p_new)->parent = dup_node;
+      (*p_new)->token.duplicated = 1;
+      dup_node = *p_new;
 
-  /* At last, duplicate itself.  */
-  if (src->type == NON_TYPE)
-    {
-      new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0);
-      dfa->nodes[new_node_idx].duplicated = 1;
-      if (BE (new_node_idx == -1, 0))
-	return NULL;
+      /* Go to the left node, or up and to the right.  */
+      if (node->left)
+	{
+	  node = node->left;
+	  p_new = &dup_node->left;
+	}
+      else
+	{
+	  const bin_tree_t *prev = NULL;
+	  while (node->right == prev || node->right == NULL)
+	    {
+	      prev = node;
+	      node = node->parent;
+	      dup_node = dup_node->parent;
+	      if (!node)
+	        return dup_root;
+	    }
+	  node = node->right;
+	  p_new = &dup_node->right;
+	}
     }
-  else
-    new_node_idx = src->type;
-
-  new_tree = create_tree (dfa, left, right, src->type, new_node_idx);
-  return new_tree;
 }
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index f15cb575eb..c3295a851c 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -1330,47 +1330,44 @@ re_node_set_remove_at (set, idx)
    Or return -1, if an error will be occured.  */
 
 static int
-re_dfa_add_node (dfa, token, mode)
+re_dfa_add_node (dfa, token)
      re_dfa_t *dfa;
      re_token_t token;
-     int mode;
 {
+  int type = token.type;
   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
     {
       int new_nodes_alloc = dfa->nodes_alloc * 2;
+      int *new_nexts, *new_indices;
+      re_node_set *new_edests, *new_eclosures;
+
       re_token_t *new_array = re_realloc (dfa->nodes, re_token_t,
 					  new_nodes_alloc);
       if (BE (new_array == NULL, 0))
 	return -1;
       dfa->nodes = new_array;
-      if (mode)
-	{
-	  int *new_nexts, *new_indices;
-	  re_node_set *new_edests, *new_eclosures, *new_inveclosures;
-
-	  new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
-	  new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
-	  new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
-	  new_eclosures = re_realloc (dfa->eclosures, re_node_set,
-				      new_nodes_alloc);
-	  new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
-					 new_nodes_alloc);
-	  if (BE (new_nexts == NULL || new_indices == NULL
-		  || new_edests == NULL || new_eclosures == NULL
-		  || new_inveclosures == NULL, 0))
-	    return -1;
-	  dfa->nexts = new_nexts;
-	  dfa->org_indices = new_indices;
-	  dfa->edests = new_edests;
-	  dfa->eclosures = new_eclosures;
-	  dfa->inveclosures = new_inveclosures;
-	}
+      new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
+      new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
+      new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
+      new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc);
+      if (BE (new_nexts == NULL || new_indices == NULL
+	      || new_edests == NULL || new_eclosures == NULL, 0))
+	return -1;
+      dfa->nexts = new_nexts;
+      dfa->org_indices = new_indices;
+      dfa->edests = new_edests;
+      dfa->eclosures = new_eclosures;
       dfa->nodes_alloc = new_nodes_alloc;
     }
   dfa->nodes[dfa->nodes_len] = token;
-  dfa->nodes[dfa->nodes_len].opt_subexp = 0;
-  dfa->nodes[dfa->nodes_len].duplicated = 0;
   dfa->nodes[dfa->nodes_len].constraint = 0;
+#ifdef RE_ENABLE_I18N
+  dfa->nodes[dfa->nodes_len].accept_mb =
+    (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET;
+#endif
+  dfa->nexts[dfa->nodes_len] = -1;
+  re_node_set_init_empty (dfa->edests + dfa->nodes_len);
+  re_node_set_init_empty (dfa->eclosures + dfa->nodes_len);
   return dfa->nodes_len++;
 }
 
@@ -1551,16 +1548,13 @@ create_ci_newstate (dfa, nodes, hash)
       re_token_type_t type = node->type;
       if (type == CHARACTER && !node->constraint)
 	continue;
+#ifdef RE_ENABLE_I18N
+      newstate->accept_mb |= node->accept_mb;
+#endif /* RE_ENABLE_I18N */
 
       /* If the state has the halt node, the state is a halt state.  */
-      else if (type == END_OF_RE)
+      if (type == END_OF_RE)
 	newstate->halt = 1;
-#ifdef RE_ENABLE_I18N
-      else if (type == COMPLEX_BRACKET
-	       || type == OP_UTF8_PERIOD
-	       || (type == OP_PERIOD && dfa->mb_cur_max > 1))
-	newstate->accept_mb = 1;
-#endif /* RE_ENABLE_I18N */
       else if (type == OP_BACK_REF)
 	newstate->has_backref = 1;
       else if (type == ANCHOR || node->constraint)
@@ -1611,15 +1605,13 @@ create_cd_newstate (dfa, nodes, context, hash)
 
       if (type == CHARACTER && !constraint)
 	continue;
-      /* If the state has the halt node, the state is a halt state.  */
-      else if (type == END_OF_RE)
-	newstate->halt = 1;
 #ifdef RE_ENABLE_I18N
-      else if (type == COMPLEX_BRACKET
-	       || type == OP_UTF8_PERIOD
-	       || (type == OP_PERIOD && dfa->mb_cur_max > 1))
-	newstate->accept_mb = 1;
+      newstate->accept_mb |= node->accept_mb;
 #endif /* RE_ENABLE_I18N */
+
+      /* If the state has the halt node, the state is a halt state.  */
+      if (type == END_OF_RE)
+	newstate->halt = 1;
       else if (type == OP_BACK_REF)
 	newstate->has_backref = 1;
       else if (type == ANCHOR)
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 23765c970e..f065cf449d 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -1,5 +1,5 @@
 /* Extended regular expression matching and search library.
-   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
 
@@ -143,18 +143,21 @@ static inline void bitset_mask (bitset dest, const bitset src);
 #define NEXT_NEWLINE_CONSTRAINT 0x0020
 #define PREV_BEGBUF_CONSTRAINT 0x0040
 #define NEXT_ENDBUF_CONSTRAINT 0x0080
-#define DUMMY_CONSTRAINT 0x0100
+#define WORD_DELIM_CONSTRAINT 0x0100
+#define NOT_WORD_DELIM_CONSTRAINT 0x0200
 
 typedef enum
 {
   INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
   WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
   WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
+  INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
   LINE_FIRST = PREV_NEWLINE_CONSTRAINT,
   LINE_LAST = NEXT_NEWLINE_CONSTRAINT,
   BUF_FIRST = PREV_BEGBUF_CONSTRAINT,
   BUF_LAST = NEXT_ENDBUF_CONSTRAINT,
-  WORD_DELIM = DUMMY_CONSTRAINT
+  WORD_DELIM = WORD_DELIM_CONSTRAINT,
+  NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT
 } re_context_type;
 
 typedef struct
@@ -186,16 +189,16 @@ typedef enum
   OP_CLOSE_SUBEXP = EPSILON_BIT | 1,
   OP_ALT = EPSILON_BIT | 2,
   OP_DUP_ASTERISK = EPSILON_BIT | 3,
-  OP_DUP_PLUS = EPSILON_BIT | 4,
-  OP_DUP_QUESTION = EPSILON_BIT | 5,
-  ANCHOR = EPSILON_BIT | 6,
-  OP_DELETED_SUBEXP = EPSILON_BIT | 7,
+  ANCHOR = EPSILON_BIT | 4,
 
   /* Tree type, these are used only by tree. */
   CONCAT = 16,
+  SUBEXP = 17,
 
   /* Token type, these are used only by token.  */
-  OP_OPEN_BRACKET = 17,
+  OP_DUP_PLUS = 18,
+  OP_DUP_QUESTION,
+  OP_OPEN_BRACKET,
   OP_CLOSE_BRACKET,
   OP_CHARSET_RANGE,
   OP_OPEN_DUP_NUM,
@@ -284,6 +287,7 @@ typedef struct
   unsigned int duplicated : 1;
   unsigned int opt_subexp : 1;
 #ifdef RE_ENABLE_I18N
+  unsigned int accept_mb : 1;
   /* These 2 bits can be moved into the union if needed (e.g. if running out
      of bits; move opr.c to opr.c.c and move the flags to opr.c.flags).  */
   unsigned int mb_partial : 1;
@@ -292,8 +296,6 @@ typedef struct
 } re_token_t;
 
 #define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT)
-#define ACCEPT_MB_NODE(type) \
-  ((type) >= OP_PERIOD && (type) <= OP_UTF8_PERIOD)
 
 struct re_string_t
 {
@@ -429,15 +431,14 @@ struct bin_tree_t
   struct bin_tree_t *parent;
   struct bin_tree_t *left;
   struct bin_tree_t *right;
+  struct bin_tree_t *first;
+  struct bin_tree_t *next;
+
+  re_token_t token;
 
   /* `node_idx' is the index in dfa->nodes, if `type' == 0.
      Otherwise `type' indicate the type of this node.  */
-  re_token_type_t type;
   int node_idx;
-
-  int first;
-  int next;
-  re_node_set eclosure;
 };
 typedef struct bin_tree_t bin_tree_t;
 
@@ -677,7 +678,7 @@ static void re_node_set_remove_at (re_node_set *set, int idx) internal_function;
   (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1))
 #define re_node_set_empty(p) ((p)->nelem = 0)
 #define re_node_set_free(set) re_free ((set)->elems)
-static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token, int mode) internal_function;
+static int re_dfa_add_node (re_dfa_t *dfa, re_token_t token) internal_function;
 static re_dfastate_t *re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa,
 					const re_node_set *nodes) internal_function;
 static re_dfastate_t *re_acquire_state_context (reg_errcode_t *err,
diff --git a/posix/regexec.c b/posix/regexec.c
index 1b21b699e9..636396e6f7 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -605,6 +605,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
   int left_lim, right_lim, incr;
   int fl_longest_match, match_first, match_kind, match_last = -1;
+  int extra_nmatch;
   int sb, ch;
 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
   re_match_context_t mctx = { .dfa = dfa };
@@ -620,6 +621,9 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   mctx.dfa = dfa;
 #endif
 
+  extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
+  nmatch -= extra_nmatch;
+
   /* Check if the DFA haven't been compiled.  */
   if (BE (preg->used == 0 || dfa->init_state == NULL
 	  || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
@@ -882,11 +886,14 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
 	    pmatch[reg_idx].rm_so += match_first;
 	    pmatch[reg_idx].rm_eo += match_first;
 	  }
+      for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
+	{
+	  pmatch[nmatch + reg_idx].rm_so = -1;
+	  pmatch[nmatch + reg_idx].rm_eo = -1;
+	}
 
       if (dfa->subexp_map)
-        for (reg_idx = 0;
-             reg_idx + 1 < nmatch && reg_idx < preg->re_nsub;
-             reg_idx++)
+        for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
           if (dfa->subexp_map[reg_idx] != reg_idx)
             {
               pmatch[reg_idx + 1].rm_so
@@ -1262,7 +1269,7 @@ proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
       re_token_type_t type = dfa->nodes[node].type;
 
 #ifdef RE_ENABLE_I18N
-      if (ACCEPT_MB_NODE (type))
+      if (dfa->nodes[node].accept_mb)
 	naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
       else
 #endif /* RE_ENABLE_I18N */
@@ -1371,7 +1378,7 @@ set_regs (preg, mctx, nmatch, pmatch, fl_backtrack)
      int fl_backtrack;
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
-  int idx, cur_node, real_nmatch;
+  int idx, cur_node;
   re_node_set eps_via_nodes;
   struct re_fail_stack_t *fs;
   struct re_fail_stack_t fs_body = { 0, 2, NULL };
@@ -1392,15 +1399,14 @@ set_regs (preg, mctx, nmatch, pmatch, fl_backtrack)
     fs = NULL;
 
   cur_node = dfa->init_node;
-  real_nmatch = (nmatch <= preg->re_nsub) ? nmatch : preg->re_nsub + 1;
   re_node_set_init_empty (&eps_via_nodes);
 
-  prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * real_nmatch);
-  memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * real_nmatch);
+  prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * nmatch);
+  memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
 
   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
     {
-      update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, real_nmatch);
+      update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
 
       if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
 	{
@@ -1624,15 +1630,13 @@ build_sifted_states (mctx, sctx, str_idx, cur_dest)
       int naccepted = 0;
       int ret;
 
-#if defined DEBUG || defined RE_ENABLE_I18N
-      re_token_type_t type = dfa->nodes[prev_node].type;
-#endif
 #ifdef DEBUG
+      re_token_type_t type = dfa->nodes[prev_node].type;
       assert (!IS_EPSILON_NODE (type));
 #endif
 #ifdef RE_ENABLE_I18N
       /* If the node may accept `multi byte'.  */
-      if (ACCEPT_MB_NODE (type))
+      if (dfa->nodes[prev_node].accept_mb)
 	naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
 					 str_idx, sctx->last_str_idx);
 #endif /* RE_ENABLE_I18N */
@@ -2471,10 +2475,13 @@ transit_state_mb (mctx, pstate)
     {
       re_node_set dest_nodes, *new_nodes;
       int cur_node_idx = pstate->nodes.elems[i];
-      int naccepted = 0, dest_idx;
+      int naccepted, dest_idx;
       unsigned int context;
       re_dfastate_t *dest_state;
 
+      if (!dfa->nodes[cur_node_idx].accept_mb)
+        continue;
+
       if (dfa->nodes[cur_node_idx].constraint)
 	{
 	  context = re_string_context_at (&mctx->input,
@@ -2486,9 +2493,8 @@ transit_state_mb (mctx, pstate)
 	}
 
       /* How many bytes the node can accept?  */
-      if (ACCEPT_MB_NODE (dfa->nodes[cur_node_idx].type))
-	naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
-					     re_string_cur_idx (&mctx->input));
+      naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
+					   re_string_cur_idx (&mctx->input));
       if (naccepted == 0)
 	continue;
 
@@ -2502,9 +2508,7 @@ transit_state_mb (mctx, pstate)
 #ifdef DEBUG
       assert (dfa->nexts[cur_node_idx] != -1);
 #endif
-      /* `cur_node_idx' may point the entity of the OP_CONTEXT_NODE,
-	 then we use pstate->nodes.elems[i] instead.  */
-      new_nodes = dfa->eclosures + dfa->nexts[pstate->nodes.elems[i]];
+      new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
 
       dest_state = mctx->state_log[dest_idx];
       if (dest_state == NULL)
@@ -3020,15 +3024,13 @@ check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes)
     {
       int naccepted = 0;
       int cur_node = cur_nodes->elems[cur_idx];
-#if defined DEBUG || defined RE_ENABLE_I18N
-      re_token_type_t type = dfa->nodes[cur_node].type;
-#endif
 #ifdef DEBUG
+      re_token_type_t type = dfa->nodes[cur_node].type;
       assert (!IS_EPSILON_NODE (type));
 #endif
 #ifdef RE_ENABLE_I18N
       /* If the node may accept `multi byte'.  */
-      if (ACCEPT_MB_NODE (type))
+      if (dfa->nodes[cur_node].accept_mb)
 	{
 	  naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
 					       str_idx);
diff --git a/posix/rxspencer/tests b/posix/rxspencer/tests
index a724252d8c..a8b6e4baa8 100644
--- a/posix/rxspencer/tests
+++ b/posix/rxspencer/tests
@@ -526,3 +526,12 @@ a((b+|((c)*)))+d	-	abcd	abcd	c,c,c,c
 (((\b))){0}	-	x	@x	-,-,-
 a(((.*)))b((\2)){0}c	-	abc	abc	@bc,@bc,@bc,-,-
 a(((.*)))b((\1)){0}c	-	axbc	axbc	x,x,x,-,-
+
+\b	&	SaT	@aT
+\b	&	aT	@aT
+a.*\b	&	abT	ab
+\b	&	STSS
+\B	&	abc	@bc
+\B	&	aSbTc
+\B	&	SaT	@SaT
+\B	&	aSTSb	@TSb
diff --git a/posix/tst-rxspencer.c b/posix/tst-rxspencer.c
index cb40421797..a68bab2de9 100644
--- a/posix/tst-rxspencer.c
+++ b/posix/tst-rxspencer.c
@@ -1,5 +1,5 @@
 /* Regular expression tests.
-   Copyright (C) 2003 Free Software Foundation, Inc.
+   Copyright (C) 2003, 2005 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Jakub Jelinek <jakub@redhat.com>, 2003.
 
@@ -127,14 +127,15 @@ mb_frob_string (const char *str, const char *letters)
 }
 
 /* Like mb_frob_string, but don't replace anything between
-   [: and :], [. and .] or [= and =].  */
+   [: and :], [. and .] or [= and =] or characters escaped
+   with a backslash.  */
 
 static char *
 mb_frob_pattern (const char *str, const char *letters)
 {
   char *ret, *dst;
   const char *src;
-  int in_class = 0;
+  int in_class = 0, escaped = 0;
 
   if (str == NULL)
     return NULL;
@@ -144,7 +145,18 @@ mb_frob_pattern (const char *str, const char *letters)
     return NULL;
 
   for (src = str, dst = ret; *src; ++src)
-    if (!in_class && strchr (letters, *src))
+    if (*src == '\\')
+      {
+	escaped ^= 1;
+	*dst++ = *src;
+      }
+    else if (escaped)
+      {
+	escaped = 0;
+	*dst++ = *src;
+	continue;
+      }
+    else if (!in_class && strchr (letters, *src))
       dst = mb_replace (dst, *src);
     else
       {
diff --git a/posix/unistd.h b/posix/unistd.h
index 06c8ca7c21..744c10c50b 100644
--- a/posix/unistd.h
+++ b/posix/unistd.h
@@ -468,7 +468,7 @@ extern char *getwd (char *__buf)
 extern int dup (int __fd) __THROW __wur;
 
 /* Duplicate FD to FD2, closing FD2 and making it open on the same file.  */
-extern int dup2 (int __fd, int __fd2) __THROW __wur;
+extern int dup2 (int __fd, int __fd2) __THROW;
 
 /* NULL-terminated array of "NAME=VALUE" environment variables.  */
 extern char **__environ;