[BZ #605, BZ #611]

Update.
2004-12-13  Paolo Bonzini  <bonzini@gnu.org>

	Separate parsing and creation of the NFA.  Avoided recursion on
	the (very unbalanced) parse tree.
	[BZ #611]
	* posix/regcomp.c (struct subexp_optimize, analyze_tree, calc_epsdest,
	re_dfa_add_tree_node, mark_opt_subexp_iter): Removed.
	(optimize_subexps, duplicate_tree, calc_first, calc_next,
	mark_opt_subexp): Rewritten.
	(preorder, postorder, lower_subexps, lower_subexp, link_nfa_nodes,
	create_token_tree, free_tree, free_token): New.
	(analyze): Accept a regex_t *.  Invoke the passes via the preorder and
	postorder generic visitors.  Do not initialize the fields in the
	re_dfa_t that represent the transitions.
	(free_dfa_content): Use free_token.
	(re_compile_internal): Analyze before UTF-8 optimizations.  Do not
	include optimization of subexpressions.
	(create_initial_state): Fetch the DFA node index from the first node's
	bin_tree_t *.
	(optimize_utf8): Abort on unexpected nodes, including OP_DUP_QUESTION.
	Return on COMPLEX_BRACKET.
	(duplicate_node_closure): Fix comment.
	(duplicate_node): Do not initialize the fields in the
	re_dfa_t that represent the transitions.
	(calc_eclosure, calc_inveclosure): Do not handle OP_DELETED_SUBEXP.
	(create_tree): Remove final argument.  All callers adjusted.  Rewritten
	to use create_token_tree.
	(parse_reg_exp, parse_branch, parse_expression, parse_bracket_exp,
	build_charclass_op): Use create_tree or create_token_tree instead
	of re_dfa_add_tree_node.
	(parse_dup_op): Likewise.  Also free the tree using free_tree for
	"<re>{0}", and lower OP_DUP_QUESTION to OP_ALT: "a?" is equivalent
	to "a|".  Adjust invocation of mark_opt_subexp.
	(parse_sub_exp): Create a single SUBEXP node.
	* posix/regex_internal.c (re_dfa_add_node): Remove last parameter,
	always perform as if it was 1.  Do not initialize OPT_SUBEXP and
	DUPLICATED, and initialize the DFA fields representing the transitions.
	* posix/regex_internal.h (re_dfa_add_node): Adjust prototype.
	(re_token_type_t): Move OP_DUP_PLUS and OP_DUP_QUESTION to the tokens
	section.  Add a tree-only code SUBEXP.  Remove OP_DELETED_SUBEXP.
	(bin_tree_t): Include a full re_token_t for TOKEN.  Turn FIRST and
	NEXT into pointers to trees.  Remove ECLOSURE.

2004-12-28  Paolo Bonzini  <bonzini@gnu.org >

	[BZ #605]
	* posix/regcomp.c (parse_bracket_exp): Do not modify DFA nodes
	that were already created.
	* posix/regex_internal.c (re_dfa_add_node): Set accept_mb field
	in the token if needed.
	(create_ci_newstate, create_cd_newstate): Set accept_mb field
	from the tokens' field.
	* posix/regex_internal.h (re_token_t): Add accept_mb field.
	(ACCEPT_MB_NODE): Removed.
	* posix/regexec.c (proceed_next_node, transit_states_mb,
	build_sifted_states, check_arrival_add_next_nodes): Use
	accept_mb instead of ACCEPT_MB_NODE.

5 files changed, 554 insertions, 537 deletions

diff --git a/ChangeLog b/ChangeLog
index aa2e8f3962..f9a34f7f6b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,61 @@
+2004-12-13  Paolo Bonzini  <bonzini@gnu.org>
+
+	Separate parsing and creation of the NFA.  Avoided recursion on
+	the (very unbalanced) parse tree.
+	[BZ #611]
+	* posix/regcomp.c (struct subexp_optimize, analyze_tree, calc_epsdest,
+	re_dfa_add_tree_node, mark_opt_subexp_iter): Removed.
+	(optimize_subexps, duplicate_tree, calc_first, calc_next,
+	mark_opt_subexp): Rewritten.
+	(preorder, postorder, lower_subexps, lower_subexp, link_nfa_nodes,
+	create_token_tree, free_tree, free_token): New.
+	(analyze): Accept a regex_t *.  Invoke the passes via the preorder and
+	postorder generic visitors.  Do not initialize the fields in the
+	re_dfa_t that represent the transitions.
+	(free_dfa_content): Use free_token.
+	(re_compile_internal): Analyze before UTF-8 optimizations.  Do not
+	include optimization of subexpressions.
+	(create_initial_state): Fetch the DFA node index from the first node's
+	bin_tree_t *.
+	(optimize_utf8): Abort on unexpected nodes, including OP_DUP_QUESTION.
+	Return on COMPLEX_BRACKET.
+	(duplicate_node_closure): Fix comment.
+	(duplicate_node): Do not initialize the fields in the
+	re_dfa_t that represent the transitions.
+	(calc_eclosure, calc_inveclosure): Do not handle OP_DELETED_SUBEXP.
+	(create_tree): Remove final argument.  All callers adjusted.  Rewritten
+	to use create_token_tree.
+	(parse_reg_exp, parse_branch, parse_expression, parse_bracket_exp,
+	build_charclass_op): Use create_tree or create_token_tree instead
+	of re_dfa_add_tree_node.
+	(parse_dup_op): Likewise.  Also free the tree using free_tree for
+	"<re>{0}", and lower OP_DUP_QUESTION to OP_ALT: "a?" is equivalent
+	to "a|".  Adjust invocation of mark_opt_subexp.
+	(parse_sub_exp): Create a single SUBEXP node.
+	* posix/regex_internal.c (re_dfa_add_node): Remove last parameter,
+	always perform as if it was 1.  Do not initialize OPT_SUBEXP and
+	DUPLICATED, and initialize the DFA fields representing the transitions.
+	* posix/regex_internal.h (re_dfa_add_node): Adjust prototype.
+	(re_token_type_t): Move OP_DUP_PLUS and OP_DUP_QUESTION to the tokens
+	section.  Add a tree-only code SUBEXP.  Remove OP_DELETED_SUBEXP.
+	(bin_tree_t): Include a full re_token_t for TOKEN.  Turn FIRST and
+	NEXT into pointers to trees.  Remove ECLOSURE.
+
+2004-12-28  Paolo Bonzini  <bonzini@gnu.org >
+
+	[BZ #605]
+	* posix/regcomp.c (parse_bracket_exp): Do not modify DFA nodes
+	that were already created.
+	* posix/regex_internal.c (re_dfa_add_node): Set accept_mb field
+	in the token if needed.
+	(create_ci_newstate, create_cd_newstate): Set accept_mb field
+	from the tokens' field.
+	* posix/regex_internal.h (re_token_t): Add accept_mb field.
+	(ACCEPT_MB_NODE): Removed.
+	* posix/regexec.c (proceed_next_node, transit_states_mb,
+	build_sifted_states, check_arrival_add_next_nodes): Use
+	accept_mb instead of ACCEPT_MB_NODE.
+
 2005-01-26  Ulrich Drepper  <drepper@redhat.com>
 
 	* debug/chk_fail.c (__chk_fail): Print program name in final message.
diff --git a/posix/regcomp.c b/posix/regcomp.c
index 2ac9953d1f..cf759690cf 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -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);
@@ -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);
 
@@ -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.  */
@@ -1230,221 +1136,307 @@ analyze (dfa)
   if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
 	  || dfa->eclosures == NULL || dfa->inveclosures == 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;
+  calc_inveclosure (dfa);
+  return ret;
+}
+
+/* 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; ; )
     {
-      ret = calc_eclosure (dfa);
-      if (ret == REG_NOERROR)
-	calc_inveclosure (dfa);
+      /* 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;
     }
-  return ret;
 }
 
-/* Helper functions for analyze.
-   This function calculate "first", "next", and "edest" for the subtree
-   whose root is NODE.  */
+static reg_errcode_t
+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
-analyze_tree (dfa, node)
-     re_dfa_t *dfa;
+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_E