Adding upstream version 1:0.1.9998svn3589+dfsg.upstream/1%0.1.9998svn3589+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 4372 insertions, 0 deletions

diff --git a/src/grep/lib/dfa.c b/src/grep/lib/dfa.c
new file mode 100644
index 0000000..3f85e75
--- /dev/null
+++ b/src/grep/lib/dfa.c
@@ -0,0 +1,4372 @@
+/* dfa.c - deterministic extended regexp routines for GNU
+   Copyright (C) 1988, 1998, 2000, 2002, 2004-2005, 2007-2021 Free Software
+   Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc.,
+   51 Franklin Street - Fifth Floor, Boston, MA  02110-1301, USA */
+
+/* Written June, 1988 by Mike Haertel
+   Modified July, 1988 by Arthur David Olson to assist BMG speedups  */
+
+#include <config.h>
+
+#include "dfa.h"
+
+#include "flexmember.h"
+#include "idx.h"
+#include "verify.h"
+
+#include <assert.h>
+#include <ctype.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+
+/* Pacify gcc -Wanalyzer-null-dereference in areas where GCC
+   understandably cannot deduce that the input comes from a
+   well-formed regular expression.  There's little point to the
+   runtime overhead of 'assert' instead of 'assume_nonnull' when the
+   MMU will check anyway.  */
+#define assume_nonnull(x) assume ((x) != NULL)
+
+static bool
+streq (char const *a, char const *b)
+{
+  return strcmp (a, b) == 0;
+}
+
+static bool
+isasciidigit (char c)
+{
+  return '0' <= c && c <= '9';
+}
+
+#include "gettext.h"
+#define _(str) gettext (str)
+
+#include <wchar.h>
+
+#include "xalloc.h"
+#include "localeinfo.h"
+
+#ifndef FALLTHROUGH
+# if 201710L < __STDC_VERSION__
+#  define FALLTHROUGH [[__fallthrough__]]
+# elif (__GNUC__ >= 7) || (__clang_major__ >= 10)
+#  define FALLTHROUGH __attribute__ ((__fallthrough__))
+# else
+#  define FALLTHROUGH ((void) 0)
+# endif
+#endif
+
+#ifndef MIN
+# define MIN(a,b) ((a) < (b) ? (a) : (b))
+#endif
+
+/* HPUX defines these as macros in sys/param.h.  */
+#ifdef setbit
+# undef setbit
+#endif
+#ifdef clrbit
+# undef clrbit
+#endif
+
+/* For code that does not use Gnulib’s isblank module.  */
+#if !defined isblank && !defined HAVE_ISBLANK && !defined GNULIB_ISBLANK
+# define isblank dfa_isblank
+static int
+isblank (int c)
+{
+  return c == ' ' || c == '\t';
+}
+#endif
+
+/* First integer value that is greater than any character code.  */
+enum { NOTCHAR = 1 << CHAR_BIT };
+
+#ifdef UINT_LEAST64_MAX
+
+/* Number of bits used in a charclass word.  */
+enum { CHARCLASS_WORD_BITS = 64 };
+
+/* This represents part of a character class.  It must be unsigned and
+   at least CHARCLASS_WORD_BITS wide.  Any excess bits are zero.  */
+typedef uint_least64_t charclass_word;
+
+/* Part of a charclass initializer that represents 64 bits' worth of a
+   charclass, where LO and HI are the low and high-order 32 bits of
+   the 64-bit quantity.  */
+# define CHARCLASS_PAIR(lo, hi) (((charclass_word) (hi) << 32) + (lo))
+
+#else
+/* Fallbacks for pre-C99 hosts that lack 64-bit integers.  */
+enum { CHARCLASS_WORD_BITS = 32 };
+typedef unsigned long charclass_word;
+# define CHARCLASS_PAIR(lo, hi) lo, hi
+#endif
+
+/* An initializer for a charclass whose 32-bit words are A through H.  */
+#define CHARCLASS_INIT(a, b, c, d, e, f, g, h)		\
+   {{							\
+      CHARCLASS_PAIR (a, b), CHARCLASS_PAIR (c, d),	\
+      CHARCLASS_PAIR (e, f), CHARCLASS_PAIR (g, h)	\
+   }}
+
+/* The maximum useful value of a charclass_word; all used bits are 1.  */
+static charclass_word const CHARCLASS_WORD_MASK
+  = ((charclass_word) 1 << (CHARCLASS_WORD_BITS - 1) << 1) - 1;
+
+/* Number of words required to hold a bit for every character.  */
+enum
+{
+  CHARCLASS_WORDS = (NOTCHAR + CHARCLASS_WORD_BITS - 1) / CHARCLASS_WORD_BITS
+};
+
+/* Sets of unsigned characters are stored as bit vectors in arrays of ints.  */
+typedef struct { charclass_word w[CHARCLASS_WORDS]; } charclass;
+
+/* Convert a possibly-signed character to an unsigned character.  This is
+   a bit safer than casting to unsigned char, since it catches some type
+   errors that the cast doesn't.  */
+static unsigned char
+to_uchar (char ch)
+{
+  return ch;
+}
+
+/* Contexts tell us whether a character is a newline or a word constituent.
+   Word-constituent characters are those that satisfy iswalnum, plus '_'.
+   Each character has a single CTX_* value; bitmasks of CTX_* values denote
+   a particular character class.
+
+   A state also stores a context value, which is a bitmask of CTX_* values.
+   A state's context represents a set of characters that the state's
+   predecessors must match.  For example, a state whose context does not
+   include CTX_LETTER will never have transitions where the previous
+   character is a word constituent.  A state whose context is CTX_ANY
+   might have transitions from any character.  */
+
+enum
+  {
+    CTX_NONE = 1,
+    CTX_LETTER = 2,
+    CTX_NEWLINE = 4,
+    CTX_ANY = 7
+  };
+
+/* Sometimes characters can only be matched depending on the surrounding
+   context.  Such context decisions depend on what the previous character
+   was, and the value of the current (lookahead) character.  Context
+   dependent constraints are encoded as 9-bit integers.  Each bit that
+   is set indicates that the constraint succeeds in the corresponding
+   context.
+
+   bit 6-8  - valid contexts when next character is CTX_NEWLINE
+   bit 3-5  - valid contexts when next character is CTX_LETTER
+   bit 0-2  - valid contexts when next character is CTX_NONE
+
+   succeeds_in_context determines whether a given constraint
+   succeeds in a particular context.  Prev is a bitmask of possible
+   context values for the previous character, curr is the (single-bit)
+   context value for the lookahead character.  */
+static int
+newline_constraint (int constraint)
+{
+  return (constraint >> 6) & 7;
+}
+static int
+letter_constraint (int constraint)
+{
+  return (constraint >> 3) & 7;
+}
+static int
+other_constraint (int constraint)
+{
+  return constraint & 7;
+}
+
+static bool
+succeeds_in_context (int constraint, int prev, int curr)
+{
+  return !! (((curr & CTX_NONE      ? other_constraint (constraint) : 0) \
+              | (curr & CTX_LETTER  ? letter_constraint (constraint) : 0) \
+              | (curr & CTX_NEWLINE ? newline_constraint (constraint) : 0)) \
+             & prev);
+}
+
+/* The following describe what a constraint depends on.  */
+static bool
+prev_newline_dependent (int constraint)
+{
+  return ((constraint ^ constraint >> 2) & 0111) != 0;
+}
+static bool
+prev_letter_dependent (int constraint)
+{
+  return ((constraint ^ constraint >> 1) & 0111) != 0;
+}
+
+/* Tokens that match the empty string subject to some constraint actually
+   work by applying that constraint to determine what may follow them,
+   taking into account what has gone before.  The following values are
+   the constraints corresponding to the special tokens previously defined.  */
+enum
+  {
+    NO_CONSTRAINT = 0777,
+    BEGLINE_CONSTRAINT = 0444,
+    ENDLINE_CONSTRAINT = 0700,
+    BEGWORD_CONSTRAINT = 0050,
+    ENDWORD_CONSTRAINT = 0202,
+    LIMWORD_CONSTRAINT = 0252,
+    NOTLIMWORD_CONSTRAINT = 0525
+  };
+
+/* The regexp is parsed into an array of tokens in postfix form.  Some tokens
+   are operators and others are terminal symbols.  Most (but not all) of these
+   codes are returned by the lexical analyzer.  */
+
+typedef ptrdiff_t token;
+static token const TOKEN_MAX = PTRDIFF_MAX;
+
+/* States are indexed by state_num values.  These are normally
+   nonnegative but -1 is used as a special value.  */
+typedef ptrdiff_t state_num;
+
+/* Predefined token values.  */
+enum
+{
+  END = -1,                     /* END is a terminal symbol that matches the
+                                   end of input; any value of END or less in
+                                   the parse tree is such a symbol.  Accepting
+                                   states of the DFA are those that would have
+                                   a transition on END.  This is -1, not some
+                                   more-negative value, to tweak the speed of
+                                   comparisons to END.  */
+
+  /* Ordinary character values are terminal symbols that match themselves.  */
+
+  /* CSET must come last in the following list of special tokens.  Otherwise,
+     the list order matters only for performance.  Related special tokens
+     should have nearby values so that code like (t == ANYCHAR || t == MBCSET
+     || CSET <= t) can be done with a single machine-level comparison.  */
+
+  EMPTY = NOTCHAR,              /* EMPTY is a terminal symbol that matches
+                                   the empty string.  */
+
+  QMARK,                        /* QMARK is an operator of one argument that
+                                   matches zero or one occurrences of its
+                                   argument.  */
+
+  STAR,                         /* STAR is an operator of one argument that
+                                   matches the Kleene closure (zero or more
+                                   occurrences) of its argument.  */
+
+  PLUS,                         /* PLUS is an operator of one argument that
+                                   matches the positive closure (one or more
+                                   occurrences) of its argument.  */
+
+  REPMN,                        /* REPMN is a lexical token corresponding
+                                   to the {m,n} construct.  REPMN never
+                                   appears in the compiled token vector.  */
+
+  CAT,                          /* CAT is an operator of two arguments that
+                                   matches the concatenation of its
+                                   arguments.  CAT is never returned by the
+                                   lexical analyzer.  */
+
+  OR,                           /* OR is an operator of two arguments that
+                                   matches either of its arguments.  */
+
+  LPAREN,                       /* LPAREN never appears in the parse tree,
+                                   it is only a lexeme.  */
+
+  RPAREN,                       /* RPAREN never appears in the parse tree.  */
+
+#if defined(KMK_GREP) && defined(KBUILD_OS_WINDOWS)
+# define WCHAR DFA_WCHAR
+#endif
+  WCHAR,                        /* Only returned by lex.  wctok contains
+                                   the wide character representation.  */
+
+  ANYCHAR,                      /* ANYCHAR is a terminal symbol that matches
+                                   a valid multibyte (or single byte) character.
+                                   It is used only if MB_CUR_MAX > 1.  */
+
+  BEG,                          /* BEG is an initial symbol that matches the
+                                   beginning of input.  */
+
+  BEGLINE,                      /* BEGLINE is a terminal symbol that matches
+                                   the empty string at the beginning of a
+                                   line.  */
+
+  ENDLINE,                      /* ENDLINE is a terminal symbol that matches
+                                   the empty string at the end of a line.  */
+
+  BEGWORD,                      /* BEGWORD is a terminal symbol that matches
+                                   the empty string at the beginning of a
+                                   word.  */
+
+  ENDWORD,                      /* ENDWORD is a terminal symbol that matches
+                                   the empty string at the end of a word.  */
+
+  LIMWORD,                      /* LIMWORD is a terminal symbol that matches
+                                   the empty string at the beginning or the
+                                   end of a word.  */
+
+  NOTLIMWORD,                   /* NOTLIMWORD is a terminal symbol that
+                                   matches the empty string not at
+                                   the beginning or end of a word.  */
+
+  BACKREF,                      /* BACKREF is generated by \<digit>
+                                   or by any other construct that
+                                   is not completely handled.  If the scanner
+                                   detects a transition on backref, it returns
+                                   a kind of "semi-success" indicating that
+                                   the match will have to be verified with
+                                   a backtracking matcher.  */
+
+  MBCSET,                       /* MBCSET is similar to CSET, but for
+                                   multibyte characters.  */
+
+  CSET                          /* CSET and (and any value greater) is a
+                                   terminal symbol that matches any of a
+                                   class of characters.  */
+};
+
+
+/* States of the recognizer correspond to sets of positions in the parse
+   tree, together with the constraints under which they may be matched.
+   So a position is encoded as an index into the parse tree together with
+   a constraint.  */
+typedef struct
+{
+  idx_t index;			/* Index into the parse array.  */
+  unsigned int constraint;      /* Constraint for matching this position.  */
+} position;
+
+/* Sets of positions are stored as arrays.  */
+typedef struct
+{
+  position *elems;              /* Elements of this position set.  */
+  idx_t nelem;			/* Number of elements in this set.  */
+  idx_t alloc;			/* Number of elements allocated in ELEMS.  */
+} position_set;
+
+/* A state of the dfa consists of a set of positions, some flags,
+   and the token value of the lowest-numbered position of the state that
+   contains an END token.  */
+typedef struct
+{
+  size_t hash;                  /* Hash of the positions of this state.  */
+  position_set elems;           /* Positions this state could match.  */
+  unsigned char context;        /* Context from previous state.  */
+  unsigned short constraint;    /* Constraint for this state to accept.  */
+  position_set mbps;            /* Positions which can match multibyte
+                                   characters or the follows, e.g., period.
+                                   Used only if MB_CUR_MAX > 1.  */
+  state_num mb_trindex;         /* Index of this state in MB_TRANS, or
+                                   negative if the state does not have
+                                   ANYCHAR.  */
+} dfa_state;
+
+/* Maximum for any transition table count.  This should be at least 3,
+   for the initial state setup.  */
+enum { MAX_TRCOUNT = 1024 };
+
+/* A bracket operator.
+   e.g., [a-c], [[:alpha:]], etc.  */
+struct mb_char_classes
+{
+  ptrdiff_t cset;
+  bool invert;
+  wchar_t *chars;               /* Normal characters.  */
+  idx_t nchars;
+  idx_t nchars_alloc;
+};
+
+struct regex_syntax
+{
+  /* Syntax bits controlling the behavior of the lexical analyzer.  */
+  reg_syntax_t syntax_bits;
+  bool syntax_bits_set;
+
+  /* Flag for case-folding letters into sets.  */
+  bool case_fold;
+
+  /* True if ^ and $ match only the start and end of data, and do not match
+     end-of-line within data.  */
+  bool anchor;
+
+  /* End-of-line byte in data.  */
+  unsigned char eolbyte;
+
+  /* Cache of char-context values.  */
+  char sbit[NOTCHAR];
+
+  /* If never_trail[B], the byte B cannot be a non-initial byte in a
+     multibyte character.  */
+  bool never_trail[NOTCHAR];
+
+  /* Set of characters considered letters.  */
+  charclass letters;
+
+  /* Set of characters that are newline.  */
+  charclass newline;
+};
+
+/* Lexical analyzer.  All the dross that deals with the obnoxious
+   GNU Regex syntax bits is located here.  The poor, suffering
+   reader is referred to the GNU Regex documentation for the
+   meaning of the @#%!@#%^!@ syntax bits.  */
+struct lexer_state
+{
+  char const *ptr;	/* Pointer to next input character.  */
+  idx_t left;		/* Number of characters remaining.  */
+  token lasttok;	/* Previous token returned; initially END.  */
+  idx_t parens;		/* Count of outstanding left parens.  */
+  int minrep, maxrep;	/* Repeat counts for {m,n}.  */
+
+  /* Wide character representation of the current multibyte character,
+     or WEOF if there was an encoding error.  Used only if
+     MB_CUR_MAX > 1.  */
+  wint_t wctok;
+
+  /* The most recently analyzed multibyte bracket expression.  */
+  struct mb_char_classes brack;
+
+  /* We're separated from beginning or (, | only by zero-width characters.  */
+  bool laststart;
+};
+
+/* Recursive descent parser for regular expressions.  */
+
+struct parser_state
+{
+  token tok;               /* Lookahead token.  */
+  idx_t depth;		   /* Current depth of a hypothetical stack
+                              holding deferred productions.  This is
+                              used to determine the depth that will be
+                              required of the real stack later on in
+                              dfaanalyze.  */
+};
+
+/* A compiled regular expression.  */
+struct dfa
+{
+  /* Fields filled by the scanner.  */
+  charclass *charclasses;       /* Array of character sets for CSET tokens.  */
+  idx_t cindex;			/* Index for adding new charclasses.  */
+  idx_t calloc;			/* Number of charclasses allocated.  */
+  ptrdiff_t canychar;           /* Index of anychar class, or -1.  */
+
+  /* Scanner state */
+  struct lexer_state lex;
+
+  /* Parser state */
+  struct parser_state parse;
+
+  /* Fields filled by the parser.  */
+  token *tokens;                /* Postfix parse array.  */
+  idx_t tindex;			/* Index for adding new tokens.  */
+  idx_t talloc;			/* Number of tokens currently allocated.  */
+  idx_t depth;			/* Depth required of an evaluation stack
+                                   used for depth-first traversal of the
+                                   parse tree.  */
+  idx_t nleaves;		/* Number of non-EMPTY leaves
+                                   in the parse tree.  */
+  idx_t nregexps;		/* Count of parallel regexps being built
+                                   with dfaparse.  */
+  bool fast;			/* The DFA is fast.  */
+  bool epsilon;			/* Does a token match only the empty string?  */
+  token utf8_anychar_classes[9]; /* To lower ANYCHAR in UTF-8 locales.  */
+  mbstate_t mbs;		/* Multibyte conversion state.  */
+
+  /* The following are valid only if MB_CUR_MAX > 1.  */
+
+  /* The value of multibyte_prop[i] is defined by following rule.
+     if tokens[i] < NOTCHAR
+     bit 0 : tokens[i] is the first byte of a character, including
+     single-byte characters.
+     bit 1 : tokens[i] is the last byte of a character, including
+     single-byte characters.
+
+     e.g.
+     tokens
+     = 'single_byte_a', 'multi_byte_A', single_byte_b'
+     = 'sb_a', 'mb_A(1st byte)', 'mb_A(2nd byte)', 'mb_A(3rd byte)', 'sb_b'
+     multibyte_prop
+     = 3     , 1               ,  0              ,  2              , 3
+   */
+  char *multibyte_prop;
+
+  /* Fields filled by the superset.  */
+  struct dfa *superset;             /* Hint of the dfa.  */
+
+  /* Fields filled by the state builder.  */
+  dfa_state *states;            /* States of the dfa.  */
+  state_num sindex;             /* Index for adding new states.  */
+  idx_t salloc;			/* Number of states currently allocated.  */
+
+  /* Fields filled by the parse tree->NFA conversion.  */
+  position_set *follows;        /* Array of follow sets, indexed by position
+                                   index.  The follow of a position is the set
+                                   of positions containing characters that
+                                   could conceivably follow a character
+                                   matching the given position in a string
+                                   matching the regexp.  Allocated to the
+                                   maximum possible position index.  */
+  bool searchflag;		/* We are supposed to build a searching
+                                   as opposed to an exact matcher.  A searching
+                                   matcher finds the first and shortest string
+                                   matching a regexp anywhere in the buffer,
+                                   whereas an exact matcher finds the longest
+                                   string matching, but anchored to the
+                                   beginning of the buffer.  */
+
+  /* Fields filled by dfaanalyze.  */
+  int *constraints;             /* Array of union of accepting constraints
+                                   in the follow of a position.  */
+  int *separates;               /* Array of contexts on follow of a
+                                   position.  */
+
+  /* Fields filled by dfaexec.  */
+  state_num tralloc;            /* Number of transition tables that have
+                                   slots so far, not counting trans[-1] and
+                                   trans[-2].  */
+  int trcount;                  /* Number of transition tables that have
+                                   been built, other than for initial
+                                   states.  */
+  int min_trcount;              /* Number of initial states.  Equivalently,
+                                   the minimum state number for which trcount
+                                   counts transitions.  */
+  state_num **trans;            /* Transition tables for states that can
+                                   never accept.  If the transitions for a
+                                   state have not yet been computed, or the
+                                   state could possibly accept, its entry in
+                                   this table is NULL.  This points to two
+                                   past the start of the allocated array,
+                                   and trans[-1] and trans[-2] are always
+                                   NULL.  */
+  state_num **fails;            /* Transition tables after failing to accept
+                                   on a state that potentially could do so.
+                                   If trans[i] is non-null, fails[i] must
+                                   be null.  */
+  char *success;                /* Table of acceptance conditions used in
+                                   dfaexec and computed in build_state.  */
+  state_num *newlines;          /* Transitions on newlines.  The entry for a
+                                   newline in any transition table is always
+                                   -1 so we can count lines without wasting
+                                   too many cycles.  The transition for a
+                                   newline is stored separately and handled
+                                   as a special case.  Newline is also used
+                                   as a sentinel at the end of the buffer.  */
+  state_num initstate_notbol;   /* Initial state for CTX_LETTER and CTX_NONE
+                                   context in multibyte locales, in which we
+                                   do not distinguish between their contexts,
+                                   as not supported word.  */
+  position_set mb_follows;      /* Follow set added by ANYCHAR on demand.  */
+  state_num **mb_trans;         /* Transition tables for states with
+                                   ANYCHAR.  */
+  state_num mb_trcount;         /* Number of transition tables for states with
+                                   ANYCHAR that have actually been built.  */
+
+  /* Syntax configuration.  This is near the end so that dfacopysyntax
+     can memset up to here.  */
+  struct regex_syntax syntax;
+
+  /* Information derived from the locale.  This is at the end so that
+     a quick memset need not clear it specially.  */
+
+  /* dfaexec implementation.  */
+  char *(*dfaexec) (struct dfa *, char const *, char *,
+                    bool, ptrdiff_t *, bool *);
+
+  /* Other cached information derived from the locale.  */
+  struct localeinfo localeinfo;
+};
+
+/* User access to dfa internals.  */
+
+/* S could possibly be an accepting state of R.  */
+static bool
+accepting (state_num s, struct dfa const *r)
+{
+  return r->states[s].constraint != 0;
+}
+
+/* STATE accepts in the specified context.  */
+static bool
+accepts_in_context (int prev, int curr, state_num state, struct dfa const *dfa)
+{
+  return succeeds_in_context (dfa->states[state].constraint, prev, curr);
+}
+
+static void regexp (struct dfa *dfa);
+
+/* Store into *PWC the result of converting the leading bytes of the
+   multibyte buffer S of length N bytes, using D->localeinfo.sbctowc
+   and updating the conversion state in *D.  On conversion error,
+   convert just a single byte, to WEOF.  Return the number of bytes
+   converted.
+
+   This differs from mbrtowc (PWC, S, N, &D->mbs) as follows:
+
+   * PWC points to wint_t, not to wchar_t.
+   * The last arg is a dfa *D instead of merely a multibyte conversion
+     state D->mbs.
+   * N is idx_t not size_t, and must be at least 1.
+   * S[N - 1] must be a sentinel byte.
+   * Shift encodings are not supported.
+   * The return value is always in the range 1..N.
+   * D->mbs is always valid afterwards.
+   * *PWC is always set to something.  */
+static int
+mbs_to_wchar (wint_t *pwc, char const *s, idx_t n, struct dfa *d)
+{
+  unsigned char uc = s[0];
+  wint_t wc = d->localeinfo.sbctowc[uc];
+
+  if (wc == WEOF)
+    {
+      wchar_t wch;
+      size_t nbytes = mbrtowc (&wch, s, n, &d->mbs);
+      if (0 < nbytes && nbytes < (size_t) -2)
+        {
+          *pwc = wch;
+          return nbytes;
+        }
+      memset (&d->mbs, 0, sizeof d->mbs);
+    }
+
+  *pwc = wc;
+  return 1;
+}
+
+#ifdef DEBUG
+
+static void
+prtok (token t)
+{
+  if (t <= END)
+    fprintf (stderr, "END");
+  else if (0 <= t && t < NOTCHAR)
+    {
+      unsigned int ch = t;
+      fprintf (stderr, "0x%02x", ch);
+    }
+  else
+    {
+      char const *s;
+      switch (t)
+        {
+        case BEG:
+          s = "BEG";
+          break;
+        case EMPTY:
+          s = "EMPTY";
+          break;
+        case BACKREF:
+          s = "BACKREF";
+          break;
+        case BEGLINE:
+          s = "BEGLINE";
+          break;
+        case ENDLINE:
+          s = "ENDLINE";
+          break;
+        case BEGWORD:
+          s = "BEGWORD";
+          break;
+        case ENDWORD:
+          s = "ENDWORD";
+          break;
+        case LIMWORD:
+          s = "LIMWORD";
+          break;
+        case NOTLIMWORD:
+          s = "NOTLIMWORD";
+          break;
+        case QMARK:
+          s = "QMARK";
+          break;
+        case STAR:
+          s = "STAR";
+          break;
+        case PLUS:
+          s = "PLUS";
+          break;
+        case CAT:
+          s = "CAT";
+          break;
+        case OR:
+          s = "OR";
+          break;
+        case LPAREN:
+          s = "LPAREN";
+          break;
+        case RPAREN:
+          s = "RPAREN";
+          break;
+        case ANYCHAR:
+          s = "ANYCHAR";
+          break;
+        case MBCSET:
+          s = "MBCSET";
+          break;
+        default:
+          s = "CSET";
+          break;
+        }
+      fprintf (stderr, "%s", s);
+    }
+}
+#endif /* DEBUG */
+
+/* Stuff pertaining to charclasses.  */
+
+static bool
+tstbit (unsigned int b, charclass const *c)
+{
+  return c->w[b / CHARCLASS_WORD_BITS] >> b % CHARCLASS_WORD_BITS & 1;
+}
+
+static void
+setbit (unsigned int b, charclass *c)
+{
+  charclass_word one = 1;
+  c->w[b / CHARCLASS_WORD_BITS] |= one << b % CHARCLASS_WORD_BITS;
+}
+
+static void
+clrbit (unsigned int b, charclass *c)
+{
+  charclass_word one = 1;
+  c->w[b / CHARCLASS_WORD_BITS] &= ~(one << b % CHARCLASS_WORD_BITS);
+}
+
+static void
+zeroset (charclass *s)
+{
+  memset (s, 0, sizeof *s);
+}
+
+static void
+fillset (charclass *s)
+{
+  for (int i = 0; i < CHARCLASS_WORDS; i++)
+    s->w[i] = CHARCLASS_WORD_MASK;
+}
+
+static void
+notset (charclass *s)
+{
+  for (int i = 0; i < CHARCLASS_WORDS; ++i)
+    s->w[i] = CHARCLASS_WORD_MASK & ~s->w[i];
+}
+
+static bool
+equal (charclass const *s1, charclass const *s2)
+{
+  charclass_word w = 0;
+  for (int i = 0; i < CHARCLASS_WORDS; i++)
+    w |= s1->w[i] ^ s2->w[i];
+  return w == 0;
+}
+
+static bool
+emptyset (charclass const *s)
+{
+  charclass_word w = 0;
+  for (int i = 0; i < CHARCLASS_WORDS; i++)
+    w |= s->w[i];
+  return w == 0;
+}
+
+/* Ensure that the array addressed by PA holds at least I + 1 items.
+   Either return PA, or reallocate the array and return its new address.
+   Although PA may be null, the returned value is never null.
+
+   The array holds *NITEMS items, where 0 <= I <= *NITEMS; *NITEMS
+   is updated on reallocation.  If PA is null, *NITEMS must be zero.
+   Do not allocate more than NITEMS_MAX items total; -1 means no limit.
+   ITEM_SIZE is the size of one item; it must be positive.
+   Avoid O(N**2) behavior on arrays growing linearly.  */
+static void *
+maybe_realloc (void *pa, idx_t i, idx_t *nitems,
+               ptrdiff_t nitems_max, idx_t item_size)
+{
+  if (i < *nitems)
+    return pa;
+  return xpalloc (pa, nitems, 1, nitems_max, item_size);
+}
+
+/* In DFA D, find the index of charclass S, or allocate a new one.  */
+static idx_t
+charclass_index (struct dfa *d, charclass const *s)
+{
+  idx_t i;
+
+  for (i = 0; i < d->cindex; ++i)
+    if (equal (s, &d->charclasses[i]))
+      return i;
+  d->charclasses = maybe_realloc (d->charclasses, d->cindex, &d->calloc,
+                                  TOKEN_MAX - CSET, sizeof *d->charclasses);
+  ++d->cindex;
+  d->charclasses[i] = *s;
+  return i;
+}
+
+static bool
+unibyte_word_constituent (struct dfa const *dfa, unsigned char c)
+{
+  return dfa->localeinfo.sbctowc[c] != WEOF && (isalnum (c) || (c) == '_');
+}
+
+static int
+char_context (struct dfa const *dfa, unsigned char c)
+{
+  if (c == dfa->syntax.eolbyte && !dfa->syntax.anchor)
+    return CTX_NEWLINE;
+  if (unibyte_word_constituent (dfa, c))
+    return CTX_LETTER;
+  return CTX_NONE;
+}
+
+/* Set a bit in the charclass for the given wchar_t.  Do nothing if WC
+   is represented by a multi-byte sequence.  Even for MB_CUR_MAX == 1,
+   this may happen when folding case in weird Turkish locales where
+   dotless i/dotted I are not included in the chosen character set.
+   Return whether a bit was set in the charclass.  */
+static bool
+setbit_wc (wint_t wc, charclass *c)
+{
+  int b = wctob (wc);
+  if (b < 0)
+    return false;
+
+  setbit (b, c);
+  return true;
+}
+
+/* Set a bit for B and its case variants in the charclass C.
+   MB_CUR_MAX must be 1.  */
+static void
+setbit_case_fold_c (int b, charclass *c)
+{
+  int ub = toupper (b);
+  for (int i = 0; i < NOTCHAR; i++)
+    if (toupper (i) == ub)
+      setbit (i, c);
+}
+
+/* Fetch the next lexical input character from the pattern.  There
+   must at least one byte of pattern input.  Set DFA->lex.wctok to the
+   value of the character or to WEOF depending on whether the input is
+   a valid multibyte character (possibly of length 1).  Then return
+   the next input byte value, except return EOF if the input is a
+   multibyte character of length greater than 1.  */
+static int
+fetch_wc (struct dfa *dfa)
+{
+  int nbytes = mbs_to_wchar (&dfa->lex.wctok, dfa->lex.ptr, dfa->lex.left,
+                             dfa);
+  int c = nbytes == 1 ? to_uchar (dfa->lex.ptr[0]) : EOF;
+  dfa->lex.ptr += nbytes;
+  dfa->lex.left -= nbytes;
+  return c;
+}
+
+/* If there is no more input, report an error about unbalanced brackets.
+   Otherwise, behave as with fetch_wc (DFA).  */
+static int
+bracket_fetch_wc (struct dfa *dfa)
+{
+  if (! dfa->lex.left)
+    dfaerror (_("unbalanced ["));
+  return fetch_wc (dfa);
+}
+
+typedef int predicate (int);
+
+/* The following list maps the names of the Posix named character classes
+   to predicate functions that determine whether a given character is in
+   the class.  The leading [ has already been eaten by the lexical
+   analyzer.  */
+struct dfa_ctype
+{
+  const char *name;
+  predicate *func;
+  bool single_byte_only;
+};
+
+static const struct dfa_ctype prednames[] = {
+  {"alpha", isalpha, false},
+  {"upper", isupper, false},
+  {"lower", islower, false},
+  {"digit", isdigit, true},
+  {"xdigit", isxdigit, false},
+  {"space", isspace, false},
+  {"punct", ispunct, false},
+  {"alnum", isalnum, false},
+  {"print", isprint, false},
+  {"graph", isgraph, false},
+  {"cntrl", iscntrl, false},
+  {"blank", isblank, false},
+  {NULL, NULL, false}
+};
+
+static const struct dfa_ctype *_GL_ATTRIBUTE_PURE
+find_pred (const char *str)
+{
+  for (int i = 0; prednames[i].name; i++)
+    if (streq (str, prednames[i].name))
+      return &prednames[i];
+  return NULL;
+}
+
+/* Parse a bracket expression, which possibly includes multibyte
+   characters.  */
+static token
+parse_bracket_exp (struct dfa *dfa)
+{
+  /* This is a bracket expression that dfaexec is known to
+     process correctly.  */
+  bool known_bracket_exp = true;
+
+  /* Used to warn about [:space:].
+     Bit 0 = first character is a colon.
+     Bit 1 = last character is a colon.
+     Bit 2 = includes any other character but a colon.
+     Bit 3 = includes ranges, char/equiv classes or collation elements.  */
+  int colon_warning_state;
+
+  dfa->lex.brack.nchars = 0;
+  charclass ccl;
+  zeroset (&ccl);
+  int c = bracket_fetch_wc (dfa);
+  bool invert = c == '^';
+  if (invert)
+    {
+      c = bracket_fetch_wc (dfa);
+      known_bracket_exp = dfa->localeinfo.simple;
+    }
+  wint_t wc = dfa->lex.wctok;
+  int c1;
+  wint_t wc1;
+  colon_warning_state = (c == ':');
+  do
+    {
+      c1 = NOTCHAR;	/* Mark c1 as not initialized.  */
+      colon_warning_state &= ~2;
+
+      /* Note that if we're looking at some other [:...:] construct,
+         we just treat it as a bunch of ordinary characters.  We can do
+         this because we assume regex has checked for syntax errors before
+         dfa is ever called.  */
+      if (c == '[')
+        {
+          c1 = bracket_fetch_wc (dfa);
+          wc1 = dfa->lex.wctok;
+
+          if ((c1 == ':' && (dfa->syntax.syntax_bits & RE_CHAR_CLASSES))
+              || c1 == '.' || c1 == '=')
+            {
+              enum { MAX_BRACKET_STRING_LEN = 32 };
+              char str[MAX_BRACKET_STRING_LEN + 1];
+              int len = 0;
+              for (;;)
+                {
+                  c = bracket_fetch_wc (dfa);
+                  if (dfa->lex.left == 0
+                      || (c == c1 && dfa->lex.ptr[0] == ']'))
+                    break;
+                  if (len < MAX_BRACKET_STRING_LEN)
+                    str[len++] = c;
+                  else
+                    /* This is in any case an invalid class name.  */
+                    str[0] = '\0';
+                }
+              str[len] = '\0';
+
+              /* Fetch bracket.  */
+              c = bracket_fetch_wc (dfa);
+              wc = dfa->lex.wctok;
+              if (c1 == ':')
+                /* Build character class.  POSIX allows character
+                   classes to match multicharacter collating elements,
+                   but the regex code does not support that, so do not
+                   worry about that possibility.  */
+                {
+                  char const *class
+                    = (dfa->syntax.case_fold && (streq (str, "upper")
+                                                 || streq (str, "lower"))
+                       ? "alpha" : str);
+                  const struct dfa_ctype *pred = find_pred (class);
+                  if (!pred)
+                    dfaerror (_("invalid character class"));
+
+                  if (dfa->localeinfo.multibyte && !pred->single_byte_only)
+                    known_bracket_exp = false;
+                  else
+                    for (int c2 = 0; c2 < NOTCHAR; ++c2)
+                      if (pred->func (c2))
+                        setbit (c2, &ccl);
+                }
+              else
+                known_bracket_exp = false;
+
+              colon_warning_state |= 8;
+
+              /* Fetch new lookahead character.  */
+              c1 = bracket_fetch_wc (dfa);
+              wc1 = dfa->lex.wctok;
+              continue;
+            }
+
+          /* We treat '[' as a normal character here.  c/c1/wc/wc1
+             are already set up.  */
+        }
+
+      if (c == '\\'
+          && (dfa->syntax.syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS))
+        {
+          c = bracket_fetch_wc (dfa);
+          wc = dfa->lex.wctok;
+        }
+
+      if (c1 == NOTCHAR)
+        {
+          c1 = bracket_fetch_wc (dfa);
+          wc1 = dfa->lex.wctok;
+        }
+
+      if (c1 == '-')
+        /* build range characters.  */
+        {
+          int c2 = bracket_fetch_wc (dfa);
+          wint_t wc2 = dfa->lex.wctok;
+
+          /* A bracket expression like [a-[.aa.]] matches an unknown set.
+             Treat it like [-a[.aa.]] while parsing it, and
+             remember that the set is unknown.  */
+          if (c2 == '[' && dfa->lex.ptr[0] == '.')
+            {
+              known_bracket_exp = false;
+              c2 = ']';
+            }
+
+          if (c2 == ']')
+            {
+              /* In the case [x-], the - is an ordinary hyphen,
+                 which is left in c1, the lookahead character.  */
+              dfa->lex.ptr--;
+              dfa->lex.left++;
+            }
+          else
+            {
+              if (c2 == '\\' && (dfa->syntax.syntax_bits
+                                 & RE_BACKSLASH_ESCAPE_IN_LISTS))
+                {
+                  c2 = bracket_fetch_wc (dfa);
+                  wc2 = dfa->lex.wctok;
+                }
+
+              colon_warning_state |= 8;
+              c1 = bracket_fetch_wc (dfa);
+              wc1 = dfa->lex.wctok;
+
+              /* Treat [x-y] as a range if x != y.  */
+              if (wc != wc2 || wc == WEOF)
+                {
+                  if (dfa->localeinfo.simple
+                      || (isasciidigit (c) & isasciidigit (c2)))
+                    {
+                      for (int ci = c; ci <= c2; ci++)
+                        if (dfa->syntax.case_fold && isalpha (ci))
+                          setbit_case_fold_c (ci, &ccl);
+                        else
+                          setbit (ci, &ccl);
+                    }
+                  else
+                    known_bracket_exp = false;
+
+                  continue;
+                }
+            }
+        }
+
+      colon_warning_state |= (c == ':') ? 2 : 4;
+
+      if (!dfa->localeinfo.multibyte)
+        {
+          if (dfa->syntax.case_fold && isalpha (c))
+            setbit_case_fold_c (c, &ccl);
+          else
+            setbit (c, &ccl);
+          continue;
+        }
+
+      if (wc == WEOF)
+        known_bracket_exp = false;
+      else
+        {
+          wchar_t folded[CASE_FOLDED_BUFSIZE + 1];
+          int n = (dfa->syntax.case_fold
+                   ? case_folded_counterparts (wc, folded + 1) + 1
+                   : 1);
+          folded[0] = wc;
+          for (int i = 0; i < n; i++)
+            if (!setbit_wc (folded[i], &ccl))
+              {
+                dfa->lex.brack.chars
+                  = maybe_realloc (dfa->lex.brack.chars, dfa->lex.brack.nchars,
+                                   &dfa->lex.brack.nchars_alloc, -1,
+                                   sizeof *dfa->lex.brack.chars);
+                dfa->lex.brack.chars[dfa->lex.brack.nchars++] = folded[i];
+              }
+        }
+    }
+  while ((wc = wc1, (c = c1) != ']'));
+
+  if (colon_warning_state == 7)
+    dfawarn (_("character class syntax is [[:space:]], not [:space:]"));
+
+  if (! known_bracket_exp)
+    return BACKREF;
+
+  if (dfa->localeinfo.multibyte && (invert || dfa->lex.brack.nchars != 0))
+    {
+      dfa->lex.brack.invert = invert;
+      dfa->lex.brack.cset = emptyset (&ccl) ? -1 : charclass_index (dfa, &ccl);
+      return MBCSET;
+    }
+
+  if (invert)
+    {
+      notset (&ccl);
+      if (dfa->syntax.syntax_bits & RE_HAT_LISTS_NOT_NEWLINE)
+        clrbit ('\n', &ccl);
+    }
+
+  return CSET + charclass_index (dfa, &ccl);
+}
+
+struct lexptr
+{
+  char const *ptr;
+  idx_t left;
+};
+
+static void
+push_lex_state (struct dfa *dfa, struct lexptr *ls, char const *s)
+{
+  ls->ptr = dfa->lex.ptr;
+  ls->left = dfa->lex.left;
+  dfa->lex.ptr = s;
+  dfa->lex.left = strlen (s);
+}
+
+static void
+pop_lex_state (struct dfa *dfa, struct lexptr const *ls)
+{
+  dfa->lex.ptr = ls->ptr;
+  dfa->lex.left = ls->left;
+}
+
+static token
+lex (struct dfa *dfa)
+{
+  bool backslash = false;
+
+  /* Basic plan: We fetch a character.  If it's a backslash,
+     we set the backslash flag and go through the loop again.
+     On the plus side, this avoids having a duplicate of the
+     main switch inside the backslash case.  On the minus side,
+     it means that just about every case begins with
+     "if (backslash) ...".  */
+  for (int i = 0; i < 2; ++i)
+    {
+      if (! dfa->lex.left)
+        return dfa->lex.lasttok = END;
+      int c = fetch_wc (dfa);
+
+      switch (c)
+        {
+        case '\\':
+          if (backslash)
+            goto normal_char;
+          if (dfa->lex.left == 0)
+            dfaerror (_("unfinished \\ escape"));
+          backslash = true;
+          break;
+
+        case '^':
+          if (backslash)
+            goto normal_char;
+          if (dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_ANCHORS
+              || dfa->lex.lasttok == END || dfa->lex.lasttok == LPAREN
+              || dfa->lex.lasttok == OR)
+            return dfa->lex.lasttok = BEGLINE;
+          goto normal_char;
+
+        case '$':
+          if (backslash)
+            goto normal_char;
+          if (dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_ANCHORS
+              || dfa->lex.left == 0
+              || ((dfa->lex.left
+                   > !(dfa->syntax.syntax_bits & RE_NO_BK_PARENS))
+                  && (dfa->lex.ptr[!(dfa->syntax.syntax_bits & RE_NO_BK_PARENS)
+                                   & (dfa->lex.ptr[0] == '\\')]
+                      == ')'))
+              || ((dfa->lex.left
+                   > !(dfa->syntax.syntax_bits & RE_NO_BK_VBAR))
+                  && (dfa->lex.ptr[!(dfa->syntax.syntax_bits & RE_NO_BK_VBAR)
+                                   & (dfa->lex.ptr[0] == '\\')]
+                      == '|'))
+              || ((dfa->syntax.syntax_bits & RE_NEWLINE_ALT)
+                  && dfa->lex.left > 0 && dfa->lex.ptr[0] == '\n'))
+            return dfa->lex.lasttok = ENDLINE;
+          goto normal_char;
+
+        case '1':
+        case '2':
+        case '3':
+        case '4':
+        case '5':
+        case '6':
+        case '7':
+        case '8':
+        case '9':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_BK_REFS))
+            {
+              dfa->lex.laststart = false;
+              return dfa->lex.lasttok = BACKREF;
+            }
+          goto normal_char;
+
+        case '`':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            {
+              /* FIXME: should be beginning of string */
+              return dfa->lex.lasttok = BEGLINE;
+            }
+          goto normal_char;
+
+        case '\'':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            {
+              /* FIXME: should be end of string */
+              return dfa->lex.lasttok = ENDLINE;
+            }
+          goto normal_char;
+
+        case '<':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            return dfa->lex.lasttok = BEGWORD;
+          goto normal_char;
+
+        case '>':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            return dfa->lex.lasttok = ENDWORD;
+          goto normal_char;
+
+        case 'b':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            return dfa->lex.lasttok = LIMWORD;
+          goto normal_char;
+
+        case 'B':
+          if (backslash && !(dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            return dfa->lex.lasttok = NOTLIMWORD;
+          goto normal_char;
+
+        case '?':
+          if (dfa->syntax.syntax_bits & RE_LIMITED_OPS)
+            goto normal_char;
+          if (backslash != ((dfa->syntax.syntax_bits & RE_BK_PLUS_QM) != 0))
+            goto normal_char;
+          if (!(dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_OPS)
+              && dfa->lex.laststart)
+            goto normal_char;
+          return dfa->lex.lasttok = QMARK;
+
+        case '*':
+          if (backslash)
+            goto normal_char;
+          if (!(dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_OPS)
+              && dfa->lex.laststart)
+            goto normal_char;
+          return dfa->lex.lasttok = STAR;
+
+        case '+':
+          if (dfa->syntax.syntax_bits & RE_LIMITED_OPS)
+            goto normal_char;
+          if (backslash != ((dfa->syntax.syntax_bits & RE_BK_PLUS_QM) != 0))
+            goto normal_char;
+          if (!(dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_OPS)
+              && dfa->lex.laststart)
+            goto normal_char;
+          return dfa->lex.lasttok = PLUS;
+
+        case '{':
+          if (!(dfa->syntax.syntax_bits & RE_INTERVALS))
+            goto normal_char;
+          if (backslash != ((dfa->syntax.syntax_bits & RE_NO_BK_BRACES) == 0))
+            goto normal_char;
+          if (!(dfa->syntax.syntax_bits & RE_CONTEXT_INDEP_OPS)
+              && dfa->lex.laststart)
+            goto normal_char;
+
+          /* Cases:
+             {M} - exact count
+             {M,} - minimum count, maximum is infinity
+             {,N} - 0 through N
+             {,} - 0 to infinity (same as '*')
+             {M,N} - M through N */
+          {
+            char const *p = dfa->lex.ptr;
+            char const *lim = p + dfa->lex.left;
+            dfa->lex.minrep = dfa->lex.maxrep = -1;
+            for (; p != lim && isasciidigit (*p); p++)
+              dfa->lex.minrep = (dfa->lex.minrep < 0
+                                 ? *p - '0'
+                                 : MIN (RE_DUP_MAX + 1,
+                                        dfa->lex.minrep * 10 + *p - '0'));
+            if (p != lim)
+              {
+                if (*p != ',')
+                  dfa->lex.maxrep = dfa->lex.minrep;
+                else
+                  {
+                    if (dfa->lex.minrep < 0)
+                      dfa->lex.minrep = 0;
+                    while (++p != lim && isasciidigit (*p))
+                      dfa->lex.maxrep
+                        = (dfa->lex.maxrep < 0
+                           ? *p - '0'
+                           : MIN (RE_DUP_MAX + 1,
+                                  dfa->lex.maxrep * 10 + *p - '0'));
+                  }
+              }
+            if (! ((! backslash || (p != lim && *p++ == '\\'))
+                   && p != lim && *p++ == '}'
+                   && 0 <= dfa->lex.minrep
+                   && (dfa->lex.maxrep < 0
+                       || dfa->lex.minrep <= dfa->lex.maxrep)))
+              {
+                if (dfa->syntax.syntax_bits & RE_INVALID_INTERVAL_ORD)
+                  goto normal_char;
+                dfaerror (_("invalid content of \\{\\}"));
+              }
+            if (RE_DUP_MAX < dfa->lex.maxrep)
+              dfaerror (_("regular expression too big"));
+            dfa->lex.ptr = p;
+            dfa->lex.left = lim - p;
+          }
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok = REPMN;
+
+        case '|':
+          if (dfa->syntax.syntax_bits & RE_LIMITED_OPS)
+            goto normal_char;
+          if (backslash != ((dfa->syntax.syntax_bits & RE_NO_BK_VBAR) == 0))
+            goto normal_char;
+          dfa->lex.laststart = true;
+          return dfa->lex.lasttok = OR;
+
+        case '\n':
+          if (dfa->syntax.syntax_bits & RE_LIMITED_OPS
+              || backslash || !(dfa->syntax.syntax_bits & RE_NEWLINE_ALT))
+            goto normal_char;
+          dfa->lex.laststart = true;
+          return dfa->lex.lasttok = OR;
+
+        case '(':
+          if (backslash != ((dfa->syntax.syntax_bits & RE_NO_BK_PARENS) == 0))
+            goto normal_char;
+          dfa->lex.parens++;
+          dfa->lex.laststart = true;
+          return dfa->lex.lasttok = LPAREN;
+
+        case ')':
+          if (backslash != ((dfa->syntax.syntax_bits & RE_NO_BK_PARENS) == 0))
+            goto normal_char;
+          if (dfa->lex.parens == 0
+              && dfa->syntax.syntax_bits & RE_UNMATCHED_RIGHT_PAREN_ORD)
+            goto normal_char;
+          dfa->lex.parens--;
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok = RPAREN;
+
+        case '.':
+          if (backslash)
+            goto normal_char;
+          if (dfa->canychar < 0)
+            {
+              charclass ccl;
+              fillset (&ccl);
+              if (!(dfa->syntax.syntax_bits & RE_DOT_NEWLINE))
+                clrbit ('\n', &ccl);
+              if (dfa->syntax.syntax_bits & RE_DOT_NOT_NULL)
+                clrbit ('\0', &ccl);
+              if (dfa->localeinfo.multibyte)
+                for (int c2 = 0; c2 < NOTCHAR; c2++)
+                  if (dfa->localeinfo.sbctowc[c2] == WEOF)
+                    clrbit (c2, &ccl);
+              dfa->canychar = charclass_index (dfa, &ccl);
+            }
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok = (dfa->localeinfo.multibyte
+                                     ? ANYCHAR
+                                     : CSET + dfa->canychar);
+
+        case 's':
+        case 'S':
+          if (!backslash || (dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            goto normal_char;
+          if (!dfa->localeinfo.multibyte)
+            {
+              charclass ccl;
+              zeroset (&ccl);
+              for (int c2 = 0; c2 < NOTCHAR; ++c2)
+                if (isspace (c2))
+                  setbit (c2, &ccl);
+              if (c == 'S')
+                notset (&ccl);
+              dfa->lex.laststart = false;
+              return dfa->lex.lasttok = CSET + charclass_index (dfa, &ccl);
+            }
+
+          /* FIXME: see if optimizing this, as is done with ANYCHAR and
+             add_utf8_anychar, makes sense.  */
+
+          /* \s and \S are documented to be equivalent to [[:space:]] and
+             [^[:space:]] respectively, so tell the lexer to process those
+             strings, each minus its "already processed" '['.  */
+          {
+            struct lexptr ls;
+            push_lex_state (dfa, &ls, &"^[:space:]]"[c == 's']);
+            dfa->lex.lasttok = parse_bracket_exp (dfa);
+            pop_lex_state (dfa, &ls);
+          }
+
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok;
+
+        case 'w':
+        case 'W':
+          if (!backslash || (dfa->syntax.syntax_bits & RE_NO_GNU_OPS))
+            goto normal_char;
+
+          if (!dfa->localeinfo.multibyte)
+            {
+              charclass ccl;
+              zeroset (&ccl);
+              for (int c2 = 0; c2 < NOTCHAR; ++c2)
+                if (dfa->syntax.sbit[c2] == CTX_LETTER)
+                  setbit (c2, &ccl);
+              if (c == 'W')
+                notset (&ccl);
+              dfa->lex.laststart = false;
+              return dfa->lex.lasttok = CSET + charclass_index (dfa, &ccl);
+            }
+
+          /* FIXME: see if optimizing this, as is done with ANYCHAR and
+             add_utf8_anychar, makes sense.  */
+
+          /* \w and \W are documented to be equivalent to [_[:alnum:]] and
+             [^_[:alnum:]] respectively, so tell the lexer to process those
+             strings, each minus its "already processed" '['.  */
+          {
+            struct lexptr ls;
+            push_lex_state (dfa, &ls, &"^_[:alnum:]]"[c == 'w']);
+            dfa->lex.lasttok = parse_bracket_exp (dfa);
+            pop_lex_state (dfa, &ls);
+          }
+
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok;
+
+        case '[':
+          if (backslash)
+            goto normal_char;
+          dfa->lex.laststart = false;
+          return dfa->lex.lasttok = parse_bracket_exp (dfa);
+
+        default:
+        normal_char:
+          dfa->lex.laststart = false;
+          /* For multibyte character sets, folding is done in atom.  Always
+             return WCHAR.  */
+          if (dfa->localeinfo.multibyte)
+            return dfa->lex.lasttok = WCHAR;
+
+          if (dfa->syntax.case_fold && isalpha (c))
+            {
+              charclass ccl;
+              zeroset (&ccl);
+              setbit_case_fold_c (c, &ccl);
+              return dfa->lex.lasttok = CSET + charclass_index (dfa, &ccl);
+            }
+
+          return dfa->lex.lasttok = c;
+        }
+    }
+
+  /* The above loop should consume at most a backslash
+     and some other character.  */
+  abort ();
+  return END;                   /* keeps pedantic compilers happy.  */
+}
+
+static void
+addtok_mb (struct dfa *dfa, token t, char mbprop)
+{
+  if (dfa->talloc == dfa->tindex)
+    {
+      dfa->tokens = xpalloc (dfa->tokens, &dfa->talloc, 1, -1,
+                             sizeof *dfa->tokens);
+      if (dfa->localeinfo.multibyte)
+        dfa->multibyte_prop = xreallocarray (dfa->multibyte_prop, dfa->talloc,
+                                             sizeof *dfa->multibyte_prop);
+    }
+  if (dfa->localeinfo.multibyte)
+    dfa->multibyte_prop[dfa->tindex] = mbprop;
+  dfa->tokens[dfa->tindex++] = t;
+
+  switch (t)
+    {
+    case QMARK:
+    case STAR:
+    case PLUS:
+      break;
+
+    case CAT:
+    case OR:
+      dfa->parse.depth--;
+      break;
+
+    case EMPTY:
+      dfa->epsilon = true;
+      goto increment_depth;
+
+    case BACKREF:
+      dfa->fast = false;
+      goto increment_nleaves;
+
+    case BEGLINE:
+    case ENDLINE:
+    case BEGWORD:
+    case ENDWORD:
+    case LIMWORD:
+    case NOTLIMWORD:
+      dfa->epsilon = true;
+      FALLTHROUGH;
+    default:
+    increment_nleaves:
+      dfa->nleaves++;
+    increment_depth:
+      dfa->parse.depth++;
+      if (dfa->depth < dfa->parse.depth)
+        dfa->depth = dfa->parse.depth;
+      break;
+    }
+}
+
+static void addtok_wc (struct dfa *dfa, wint_t wc);
+
+/* Add the given token to the parse tree, maintaining the depth count and
+   updating the maximum depth if necessary.  */
+static void
+addtok (struct dfa *dfa, token t)
+{
+  if (dfa->localeinfo.multibyte && t == MBCSET)
+    {
+      bool need_or = false;
+
+      /* Extract wide characters into alternations for better performance.
+         This does not require UTF-8.  */
+      for (idx_t i = 0; i < dfa->lex.brack.nchars; i++)
+        {
+          addtok_wc (dfa, dfa->lex.brack.chars[i]);
+          if (need_or)
+            addtok (dfa, OR);
+          need_or = true;
+        }
+      dfa->lex.brack.nchars = 0;
+
+      /* Wide characters have been handled above, so it is possible
+         that the set is empty now.  Do nothing in that case.  */
+      if (dfa->lex.brack.cset != -1)
+        {
+          addtok (dfa, CSET + dfa->lex.brack.cset);
+          if (need_or)
+            addtok (dfa, OR);
+        }
+    }
+  else
+    {
+      addtok_mb (dfa, t, 3);
+    }
+}
+
+/* We treat a multibyte character as a single atom, so that DFA
+   can treat a multibyte character as a single expression.
+
+   e.g., we construct the following tree from "<mb1><mb2>".
+   <mb1(1st-byte)><mb1(2nd-byte)><CAT><mb1(3rd-byte)><CAT>
+   <mb2(1st-byte)><mb2(2nd-byte)><CAT><mb2(3rd-byte)><CAT><CAT> */
+static void
+addtok_wc (struct dfa *dfa, wint_t wc)
+{
+  unsigned char buf[MB_LEN_MAX];
+  mbstate_t s = { 0 };
+  size_t stored_bytes = wcrtomb ((char *) buf, wc, &s);
+  int buflen;
+
+  if (stored_bytes != (size_t) -1)
+    buflen = stored_bytes;
+  else
+    {
+      /* This is merely stop-gap.  buf[0] is undefined, yet skipping
+         the addtok_mb call altogether can corrupt the heap.  */
+      buflen = 1;
+      buf[0] = 0;
+    }
+
+  addtok_mb (dfa, buf[0], buflen == 1 ? 3 : 1);
+  for (int i = 1; i < buflen; i++)
+    {
+      addtok_mb (dfa, buf[i], i == buflen - 1 ? 2 : 0);
+      addtok (dfa, CAT);
+    }
+}
+
+static void
+add_utf8_anychar (struct dfa *dfa)
+{
+  /* Since the Unicode Standard Version 4.0.0 (2003), a well-formed
+     UTF-8 byte sequence has been defined as follows:
+
+     ([\x00-\x7f]
+     |[\xc2-\xdf][\x80-\xbf]
+     |[\xe0][\xa0-\xbf][\x80-\xbf]
+     |[\xe1-\xec\xee-\xef][\x80-\xbf][\x80-\xbf]
+     |[\xed][\x80-\x9f][\x80-\xbf]
+     |[\xf0][\x90-\xbf][\x80-\xbf][\x80-\xbf])
+     |[\xf1-\xf3][\x80-\xbf][\x80-\xbf][\x80-\xbf]
+     |[\xf4][\x80-\x8f][\x80-\xbf][\x80-\xbf])
+
+     which I'll write more concisely "A|BC|DEC|FCC|GHC|IJCC|KCCC|LMCC",
+     where A = [\x00-\x7f], B = [\xc2-\xdf], C = [\x80-\xbf],
+     D = [\xe0], E = [\xa0-\xbf], F = [\xe1-\xec\xee-\xef], G = [\xed],
+     H = [\x80-\x9f], I = [\xf0],
+     J = [\x90-\xbf], K = [\xf1-\xf3], L = [\xf4], M = [\x80-\x8f].
+
+     This can be refactored to "A|(B|DE|GH|(F|IJ|LM|KC)C)C".  */
+
+  /* Mnemonics for classes containing two or more bytes.  */
+  enum { A, B, C, E, F, H, J, K, M };
+
+  /* Mnemonics for single-byte tokens.  */
+  enum { D_token = 0xe0, G_token = 0xed, I_token = 0xf0, L_token = 0xf4 };
+
+  static charclass const utf8_classes[] = {
+    /* A. 00-7f: 1-byte sequence.  */
+    CHARCLASS_INIT (0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0, 0, 0, 0),
+
+    /* B. c2-df: 1st byte of a 2-byte sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0, 0, 0xfffffffc, 0),
+
+    /* C. 80-bf: non-leading bytes.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0xffffffff, 0xffffffff, 0, 0),
+
+    /* D. e0 (just a token).  */
+
+    /* E. a0-bf: 2nd byte of a "DEC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0, 0xffffffff, 0, 0),
+
+    /* F. e1-ec + ee-ef: 1st byte of an "FCC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0, 0, 0, 0xdffe),
+
+    /* G. ed (just a token).  */
+
+    /* H. 80-9f: 2nd byte of a "GHC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0xffff, 0, 0, 0),
+
+    /* I. f0 (just a token).  */
+
+    /* J. 90-bf: 2nd byte of an "IJCC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0xffff0000, 0xffffffff, 0, 0),
+
+    /* K. f1-f3: 1st byte of a "KCCC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0, 0, 0, 0xe0000),
+
+    /* L. f4 (just a token).  */
+
+    /* M. 80-8f: 2nd byte of a "LMCC" sequence.  */
+    CHARCLASS_INIT (0, 0, 0, 0, 0xff, 0, 0, 0),
+  };
+
+  /* Define the character classes that are needed below.  */
+  if (dfa->utf8_anychar_classes[0] == 0)
+    {
+      charclass c = utf8_classes[0];
+      if (! (dfa->syntax.syntax_bits & RE_DOT_NEWLINE))
+        clrbit ('\n', &c);
+      if (dfa->syntax.syntax_bits & RE_DOT_NOT_NULL)
+        clrbit ('\0', &c);
+      dfa->utf8_anychar_classes[0] = CSET + charclass_index (dfa, &c);
+
+      for (int i = 1; i < sizeof utf8_classes / sizeof *utf8_classes; i++)
+        dfa->utf8_anychar_classes[i]
+          = CSET + charclass_index (dfa, &utf8_classes[i]);
+    }
+
+  /* Implement the "A|(B|DE|GH|(F|IJ|LM|KC)C)C" pattern mentioned above.
+     The token buffer is in reverse Polish order, so we get
+     "A B D E CAT OR G H CAT OR F I J CAT OR L M CAT OR K
+      C CAT OR C CAT OR C CAT OR".  */
+  addtok (dfa, dfa->utf8_anychar_classes[A]);
+  addtok (dfa, dfa->utf8_anychar_classes[B]);
+  addtok (dfa, D_token);
+  addtok (dfa, dfa->utf8_anychar_classes[E]);
+  addtok (dfa, CAT);
+  addtok (dfa, OR);
+  addtok (dfa, G_token);
+  addtok (dfa, dfa->utf8_anychar_classes[H]);
+  addtok (dfa, CAT);
+  addtok (dfa, OR);
+  addtok (dfa, dfa->utf8_anychar_classes[F]);
+  addtok (dfa, I_token);
+  addtok (dfa, dfa->utf8_anychar_classes[J]);
+  addtok (dfa, CAT);
+  addtok (dfa, OR);
+  addtok (dfa, L_token);
+  addtok (dfa, dfa->utf8_anychar_classes[M]);
+  addtok (dfa, CAT);
+  addtok (dfa, OR);
+  addtok (dfa, dfa->utf8_anychar_classes[K]);
+  for (int i = 0; i < 3; i++)
+    {
+      addtok (dfa, dfa->utf8_anychar_classes[C]);
+      addtok (dfa, CAT);
+      addtok (dfa, OR);
+    }
+}
+
+/* The grammar understood by the parser is as follows.
+
+   regexp:
+     regexp OR branch
+     branch
+
+   branch:
+     branch closure
+     closure
+
+   closure:
+     closure QMARK
+     closure STAR
+     closure PLUS
+     closure REPMN
+     atom
+
+   atom:
+     <normal character>
+     <multibyte character>
+     ANYCHAR
+     MBCSET
+     CSET
+     BACKREF
+     BEGLINE
+     ENDLINE
+     BEGWORD
+     ENDWORD
+     LIMWORD
+     NOTLIMWORD
+     LPAREN regexp RPAREN
+     <empty>
+
+   The parser builds a parse tree in postfix form in an array of tokens.  */
+
+static void
+atom (struct dfa *dfa)
+{
+  if ((0 <= dfa->parse.tok && dfa->parse.tok < NOTCHAR)
+      || dfa->parse.tok >= CSET
+      || dfa->parse.tok == BEG || dfa->parse.tok == BACKREF
+      || dfa->parse.tok == BEGLINE || dfa->parse.tok == ENDLINE
+      || dfa->parse.tok == BEGWORD || dfa->parse.tok == ENDWORD
+      || dfa->parse.tok == LIMWORD || dfa->parse.tok == NOTLIMWORD
+      || dfa->parse.tok == ANYCHAR || dfa->parse.tok == MBCSET)
+    {
+      if (dfa->parse.tok == ANYCHAR && dfa->localeinfo.using_utf8)
+        {
+          /* For UTF-8 expand the period to a series of CSETs that define a
+             valid UTF-8 character.  This avoids using the slow multibyte
+             path.  I'm pretty sure it would be both profitable and correct to
+             do it for any encoding; however, the optimization must be done
+             manually as it is done above in add_utf8_anychar.  So, let's
+             start with UTF-8: it is the most used, and the structure of the
+             encoding makes the correctness more obvious.  */
+          add_utf8_anychar (dfa);
+        }
+      else
+        addtok (dfa, dfa->parse.tok);
+      dfa->parse.tok = lex (dfa);
+    }
+  else if (dfa->parse.tok == WCHAR)
+    {
+      if (dfa->lex.wctok == WEOF)
+        addtok (dfa, BACKREF);
+      else
+        {
+          addtok_wc (dfa, dfa->lex.wctok);
+
+          if (dfa->syntax.case_fold)
+            {
+              wchar_t folded[CASE_FOLDED_BUFSIZE];
+              int n = case_folded_counterparts (dfa->lex.wctok, folded);
+              for (int i = 0; i < n; i++)
+                {
+                  addtok_wc (dfa, folded[i]);
+                  addtok (dfa, OR);
+                }
+            }
+        }
+
+      dfa->parse.tok = lex (dfa);
+    }
+  else if (dfa->parse.tok == LPAREN)
+    {
+      dfa->parse.tok = lex (dfa);
+      regexp (dfa);
+      if (dfa->parse.tok != RPAREN)
+        dfaerror (_("unbalanced ("));
+      dfa->parse.tok = lex (dfa);
+    }
+  else
+    addtok (dfa, EMPTY);
+}
+
+/* Return the number of tokens in the given subexpression.  */
+static idx_t _GL_ATTRIBUTE_PURE
+nsubtoks (struct dfa const *dfa, idx_t tindex)
+{
+  switch (dfa->tokens[tindex - 1])
+    {
+    default:
+      return 1;
+    case QMARK:
+    case STAR:
+    case PLUS:
+      return 1 + nsubtoks (dfa, tindex - 1);
+    case CAT:
+    case OR:
+      {
+        idx_t ntoks1 = nsubtoks (dfa, tindex - 1);
+        return 1 + ntoks1 + nsubtoks (dfa, tindex - 1 - ntoks1);
+      }
+    }
+}
+
+/* Copy the given subexpression to the top of the tree.  */
+static void
+copytoks (struct dfa *dfa, idx_t tindex, idx_t ntokens)
+{
+  if (dfa->localeinfo.multibyte)
+    for (idx_t i = 0; i < ntokens; i++)
+      addtok_mb (dfa, dfa->tokens[tindex + i],
+                 dfa->multibyte_prop[tindex + i]);
+  else
+    for (idx_t i = 0; i < ntokens; i++)
+      addtok_mb (dfa, dfa->tokens[tindex + i], 3);
+}
+
+static void
+closure (struct dfa *dfa)
+{
+  atom (dfa);
+  while (dfa->parse.tok == QMARK || dfa->parse.tok == STAR
+         || dfa->parse.tok == PLUS || dfa->parse.tok == REPMN)
+    if (dfa->parse.tok == REPMN && (dfa->lex.minrep || dfa->lex.maxrep))
+      {
+        idx_t ntokens = nsubtoks (dfa, dfa->tindex);
+        idx_t tindex = dfa->tindex - ntokens;
+        if (dfa->lex.maxrep < 0)
+          addtok (dfa, PLUS);
+        if (dfa->lex.minrep == 0)
+          addtok (dfa, QMARK);
+        int i;
+        for (i = 1; i < dfa->lex.minrep; i++)
+          {
+            copytoks (dfa, tindex, ntokens);
+            addtok (dfa, CAT);
+          }
+        for (; i < dfa->lex.maxrep; i++)
+          {
+            copytoks (dfa, tindex, ntokens);
+            addtok (dfa, QMARK);
+            addtok (dfa, CAT);
+          }
+        dfa->parse.tok = lex (dfa);
+      }
+    else if (dfa->parse.tok == REPMN)
+      {
+        dfa->tindex -= nsubtoks (dfa, dfa->tindex);
+        dfa->parse.tok = lex (dfa);
+        closure (dfa);
+      }
+    else
+      {
+        addtok (dfa, dfa->parse.tok);
+        dfa->parse.tok = lex (dfa);
+      }
+}
+
+static void
+branch (struct dfa* dfa)
+{
+  closure (dfa);
+  while (dfa->parse.tok != RPAREN && dfa->parse.tok != OR
+         && dfa->parse.tok >= 0)
+    {
+      closure (dfa);
+      addtok (dfa, CAT);
+    }
+}
+
+static void
+regexp (struct dfa *dfa)
+{
+  branch (dfa);
+  while (dfa->parse.tok == OR)
+    {
+      dfa->parse.tok = lex (dfa);
+      branch (dfa);
+      addtok (dfa, OR);
+    }
+}
+
+/* Parse a string S of length LEN into D.  S can include NUL characters.
+   This is the main entry point for the parser.  */
+void
+dfaparse (char const *s, idx_t len, struct dfa *d)
+{
+  d->lex.ptr = s;
+  d->lex.left = len;
+  d->lex.lasttok = END;
+  d->lex.laststart = true;
+
+  if (!d->syntax.syntax_bits_set)
+    dfaerror (_("no syntax specified"));
+
+  if (!d->nregexps)
+    addtok (d, BEG);
+
+  d->parse.tok = lex (d);
+  d->parse.depth = d->depth;
+
+  regexp (d);
+
+  if (d->parse.tok != END)
+    dfaerror (_("unbalanced )"));
+
+  addtok (d, END - d->nregexps);
+  addtok (d, CAT);
+
+  if (d->nregexps)
+    addtok (d, OR);
+
+  ++d->nregexps;
+}
+
+/* Some primitives for operating on sets of positions.  */
+
+/* Copy one set to another.  */
+static void
+copy (position_set const *src, position_set *dst)
+{
+  if (dst->alloc < src->nelem)
+    {
+      free (dst->elems);
+      dst->elems = xpalloc (NULL, &dst->alloc, src->nelem - dst->alloc, -1,
+                            sizeof *dst->elems);
+    }
+  dst->nelem = src->nelem;
+  if (src->nelem != 0)
+    memcpy (dst->elems, src->elems, src->nelem * sizeof *dst->elems);
+}
+
+static void
+alloc_position_set (position_set *s, idx_t size)
+{
+  s->elems = xnmalloc (size, sizeof *s->elems);
+  s->alloc = size;
+  s->nelem = 0;
+}
+
+/* Insert position P in set S.  S is maintained in sorted order on
+   decreasing index.  If there is already an entry in S with P.index
+   then merge (logically-OR) P's constraints into the one in S.
+   S->elems must point to an array large enough to hold the resulting set.  */
+static void
+insert (position p, position_set *s)
+{
+  idx_t count = s->nelem;
+  idx_t lo = 0, hi = count;
+  while (lo < hi)
+    {
+      idx_t mid = (lo + hi) >> 1;
+      if (s->elems[mid].index < p.index)
+        lo = mid + 1;
+      else if (s->elems[mid].index == p.index)
+        {
+          s->elems[mid].constraint |= p.constraint;
+          return;
+        }
+      else
+        hi = mid;
+    }
+
+  s->elems = maybe_realloc (s->elems, count, &s->alloc, -1, sizeof *s->elems);
+  for (idx_t i = count; i > lo; i--)
+    s->elems[i] = s->elems[i - 1];
+  s->elems[lo] = p;
+  ++s->nelem;
+}
+
+static void
+append (position p, position_set *s)
+{
+  idx_t count = s->nelem;
+  s->elems = maybe_realloc (s->elems, count, &s->alloc, -1, sizeof *s->elems);
+  s->elems[s->nelem++] = p;
+}
+
+/* Merge S1 and S2 (with the additional constraint C2) into M.  The
+   result is as if the positions of S1, and of S2 with the additional
+   constraint C2, were inserted into an initially empty set.  */
+static void
+merge_constrained (position_set const *s1, position_set const *s2,
+                   unsigned int c2, position_set *m)
+{
+  idx_t i = 0, j = 0;
+
+  if (m->alloc - s1->nelem < s2->nelem)
+    {
+      free (m->elems);
+      m->alloc = s1->nelem;
+      m->elems = xpalloc (NULL, &m->alloc, s2->nelem, -1, sizeof *m->elems);
+    }
+  m->nelem = 0;
+  while (i < s1->nelem || j < s2->nelem)
+    if (! (j < s2->nelem)
+        || (i < s1->nelem && s1->elems[i].index <= s2->elems[j].index))
+      {
+        unsigned int c = ((i < s1->nelem && j < s2->nelem
+                           && s1->elems[i].index == s2->elems[j].index)
+                          ? s2->elems[j++].constraint & c2
+                          : 0);
+        m->elems[m->nelem].index = s1->elems[i].index;
+        m->elems[m->nelem++].constraint = s1->elems[i++].constraint | c;
+      }
+    else
+      {
+        if (s2->elems[j].constraint & c2)
+          {
+            m->elems[m->nelem].index = s2->elems[j].index;
+            m->elems[m->nelem++].constraint = s2->elems[j].constraint & c2;
+          }
+        j++;
+      }
+}
+
+/* Merge two sets of positions into a third.  The result is exactly as if
+   the positions of both sets were inserted into an initially empty set.  */
+static void
+merge (position_set const *s1, position_set const *s2, position_set *m)
+{
+  merge_constrained (s1, s2, -1, m);
+}
+
+/* Merge into DST all the elements of SRC, possibly destroying
+   the contents of the temporary M.  */
+static void
+merge2 (position_set *dst, position_set const *src, position_set *m)
+{
+  if (src->nelem < 4)
+    {
+      for (idx_t i = 0; i < src->nelem; i++)
+        insert (src->elems[i], dst);
+    }
+   else
+    {
+      merge (src, dst, m);
+      copy (m, dst);
+    }
+}
+
+/* Delete a position from a set.  Return the nonzero constraint of the
+   deleted position, or zero if there was no such position.  */
+static unsigned int
+delete (idx_t del, position_set *s)
+{
+  idx_t count = s->nelem;
+  idx_t lo = 0, hi = count;
+  while (lo < hi)
+    {
+      idx_t mid = (lo + hi) >> 1;
+      if (s->elems[mid].index < del)
+        lo = mid + 1;
+      else if (s->elems[mid].index == del)
+        {
+          unsigned int c = s->elems[mid].constraint;
+          idx_t i;
+          for (i = mid; i + 1 < count; i++)
+            s->elems[i] = s->elems[i + 1];
+          s->nelem = i;
+          return c;
+        }
+      else
+        hi = mid;
+    }
+  return 0;
+}
+
+/* Replace a position with the followed set.  */
+static void
+replace (position_set *dst, idx_t del, position_set *add,
+         unsigned int constraint, position_set *tmp)
+{
+  unsigned int c = delete (del, dst) & constraint;
+
+  if (c)
+    {
+      copy (dst, tmp);
+      merge_constrained (tmp, add, c, dst);
+    }
+}
+
+/* Find the index of the state corresponding to the given position set with
+   the given preceding context, or create a new state if there is no such
+   state.  Context tells whether we got here on a newline or letter.  */
+static state_num
+state_index (struct dfa *d, position_set const *s, int context)
+{
+  size_t hash = 0;
+  int constraint = 0;
+  state_num i;
+
+  for (i = 0; i < s->nelem; ++i)
+    {
+      idx_t ind = s->elems[i].index;
+      hash ^= ind + s->elems[i].constraint;
+    }
+
+  /* Try to find a state that exactly matches the proposed one.  */
+  for (i = 0; i < d->sindex; ++i)
+    {
+      if (hash != d->states[i].hash || s->nelem != d->states[i].elems.nelem
+          || context != d->states[i].context)
+        continue;
+      state_num j;
+      for (j = 0; j < s->nelem; ++j)
+        if (s->elems[j].constraint != d->states[i].elems.elems[j].constraint
+            || s->elems[j].index != d->states[i].elems.elems[j].index)
+          break;
+      if (j == s->nelem)
+        return i;
+    }
+
+#ifdef DEBUG
+  fprintf (stderr, "new state %td\n nextpos:", i);
+  for (state_num j = 0; j < s->nelem; j++)
+    {
+      fprintf (stderr, " %td:", s->elems[j].index);
+      prtok (d->tokens[s->elems[j].index]);
+    }
+  fprintf (stderr, "\n context:");
+  if (context ^ CTX_ANY)
+    {
+      if (context & CTX_NONE)
+        fprintf (stderr, " CTX_NONE");
+      if (context & CTX_LETTER)
+        fprintf (stderr, " CTX_LETTER");
+      if (context & CTX_NEWLINE)
+        fprintf (stderr, " CTX_NEWLINE");
+    }
+  else
+    fprintf (stderr, " CTX_ANY");
+  fprintf (stderr, "\n");
+#endif
+
+  for (state_num j = 0; j < s->nelem; j++)
+    {
+      int c = d->constraints[s->elems[j].index];
+
+      if (c != 0)
+        {
+          if (succeeds_in_context (c, context, CTX_ANY))
+            constraint |= c;
+        }
+      else if (d->tokens[s->elems[j].index] == BACKREF)
+        constraint = NO_CONSTRAINT;
+    }
+
+
+  /* Create a new state.  */
+  d->states = maybe_realloc (d->states, d->sindex, &d->salloc, -1,
+                             sizeof *d->states);
+  d->states[i].hash = hash;
+  alloc_position_set (&d->states[i].elems, s->nelem);
+  copy (s, &d->states[i].elems);
+  d->states[i].context = context;
+  d->states[i].constraint = constraint;
+  d->states[i].mbps.nelem = 0;
+  d->states[i].mbps.elems = NULL;
+  d->states[i].mb_trindex = -1;
+
+  ++d->sindex;
+
+  return i;
+}
+
+/* Find the epsilon closure of D's set of positions.  If any position of the set
+   contains a symbol that matches the empty string in some context, replace
+   that position with the elements of its follow labeled with an appropriate
+   constraint.  Repeat exhaustively until no funny positions are left.
+   S->elems must be large enough to hold the result.  BACKWARD is D's
+   backward set; use and update it too.  */
+static void
+epsclosure (struct dfa const *d, position_set *backward)
+{
+  position_set tmp;
+  alloc_position_set (&tmp, d->nleaves);
+  for (idx_t i = 0; i < d->tindex; i++)
+    if (0 < d->follows[i].nelem)
+      {
+        unsigned int constraint;
+        switch (d->tokens[i])
+          {
+          default:
+            continue;
+
+          case BEGLINE:
+            constraint = BEGLINE_CONSTRAINT;
+            break;
+          case ENDLINE:
+            constraint = ENDLINE_CONSTRAINT;
+            break;
+          case BEGWORD:
+            constraint = BEGWORD_CONSTRAINT;
+            break;
+          case ENDWORD:
+            constraint = ENDWORD_CONSTRAINT;
+            break;
+          case LIMWORD:
+            constraint = LIMWORD_CONSTRAINT;
+            break;
+          case NOTLIMWORD:
+            constraint = NOTLIMWORD_CONSTRAINT;
+            break;
+          case EMPTY:
+            constraint = NO_CONSTRAINT;
+            break;
+          }
+
+        delete (i, &d->follows[i]);
+
+        for (idx_t j = 0; j < backward[i].nelem; j++)
+          replace (&d->follows[backward[i].elems[j].index], i, &d->follows[i],
+                   constraint, &tmp);
+        for (idx_t j = 0; j < d->follows[i].nelem; j++)
+          replace (&backward[d->follows[i].elems[j].index], i, &backward[i],
+                   NO_CONSTRAINT, &tmp);
+      }
+  free (tmp.elems);
+}
+
+/* Returns the set of contexts for which there is at least one
+   character included in C.  */
+
+static int
+charclass_context (struct dfa const *dfa, charclass const *c)
+{
+  int context = 0;
+
+  for (int j = 0; j < CHARCLASS_WORDS; j++)
+    {
+      if (c->w[j] & dfa->syntax.newline.w[j])
+        context |= CTX_NEWLINE;
+      if (c->w[j] & dfa->syntax.letters.w[j])
+        context |= CTX_LETTER;
+      if (c->w[j] & ~(dfa->syntax.letters.w[j] | dfa->syntax.newline.w[j]))
+        context |= CTX_NONE;
+    }
+
+  return context;
+}
+
+/* Returns the contexts on which the position set S depends.  Each context
+   in the set of returned contexts (let's call it SC) may have a different
+   follow set than other contexts in SC, and also different from the
+   follow set of the complement set (sc ^ CTX_ANY).  However, all contexts
+   in the complement set will have the same follow set.  */
+
+static int _GL_ATTRIBUTE_PURE
+state_separate_contexts (struct dfa *d, position_set const *s)
+{
+  int separate_contexts = 0;
+
+  for (idx_t j = 0; j < s->nelem; j++)
+    separate_contexts |= d->separates[s->elems[j].index];
+
+  return separate_contexts;
+}
+
+enum
+{
+  /* Single token is repeated.  It is distinguished from non-repeated.  */
+  OPT_REPEAT = (1 << 0),
+
+  /* Multiple tokens are repeated.  This flag is on at head of tokens.  The
+     node is not merged.  */
+  OPT_LPAREN = (1 << 1),
+
+  /* Multiple branches are joined.  The node is not merged.  */
+  OPT_RPAREN = (1 << 2),
+
+  /* The node is walked.  If the node is found in walking again, OPT_RPAREN
+     flag is turned on. */
+  OPT_WALKED = (1 << 3),
+
+  /* The node is queued.  The node is not queued again.  */
+  OPT_QUEUED = (1 << 4)
+};
+
+static void
+merge_nfa_state (struct dfa *d, idx_t tindex, char *flags,
+                 position_set *merged)
+{
+  position_set *follows = d->follows;
+  idx_t nelem = 0;
+
+  for (idx_t i = 0; i < follows[tindex].nelem; i++)
+    {
+      idx_t sindex = follows[tindex].elems[i].index;
+
+      /* Skip the node as pruned in future.  */
+      unsigned int iconstraint = follows[tindex].elems[i].constraint;
+      if (iconstraint == 0)
+        continue;
+
+      if (d->tokens[follows[tindex].elems[i].index] <= END)
+        {
+          d->constraints[tindex] |= follows[tindex].elems[i].constraint;
+          continue;
+        }
+
+      if (sindex != tindex && !(flags[sindex] & (OPT_LPAREN | OPT_RPAREN)))
+        {
+          idx_t j;
+
+          for (j = 0; j < nelem; j++)
+            {
+              idx_t dindex = follows[tindex].elems[j].index;
+
+              if (dindex == tindex)
+                continue;
+
+              if (follows[tindex].elems[j].constraint != iconstraint)
+                continue;
+
+              if (flags[dindex] & (OPT_LPAREN | OPT_RPAREN))
+                continue;
+
+              if (d->tokens[sindex] != d->tokens[dindex])
+                continue;
+
+              if ((flags[sindex] ^ flags[dindex]) & OPT_REPEAT)
+                continue;
+
+              if (flags[sindex] & OPT_REPEAT)
+                delete (sindex, &follows[sindex]);
+
+              merge2 (&follows[dindex], &follows[sindex], merged);
+
+              break;
+            }
+
+          if (j < nelem)
+            continue;
+        }
+
+      follows[tindex].elems[nelem++] = follows[tindex].elems[i];
+      flags[sindex] |= OPT_QUEUED;
+    }
+
+  follows[tindex].nelem = nelem;
+}
+
+static int
+compare (const void *a, const void *b)
+{
+  position const *p = a, *q = b;
+  return (p->index > q->index) - (p->index < q->index);
+}
+
+static void
+reorder_tokens (struct dfa *d)
+{
+  idx_t nleaves = 0;
+  ptrdiff_t *map = xnmalloc (d->tindex, sizeof *map);
+  map[0] = nleaves++;
+  for (idx_t i = 1; i < d->tindex; i++)
+    map[i] = -1;
+
+  token *tokens = xnmalloc (d->nleaves, sizeof *tokens);
+  position_set *follows = xnmalloc (d->nleaves, sizeof *follows);
+  int *constraints = xnmalloc (d->nleaves, sizeof *constraints);
+  char *multibyte_prop = (d->localeinfo.multibyte
+                          ? xnmalloc (d->nleaves, sizeof *multibyte_prop)
+                          : NULL);
+
+  for (idx_t i = 0; i < d->tindex; i++)
+    {
+      if (map[i] < 0)
+        {
+          free (d->follows[i].elems);
+          d->follows[i].elems = NULL;
+          d->follows[i].nelem = 0;
+          continue;
+        }
+
+      tokens[map[i]] = d->tokens[i];
+      follows[map[i]] = d->follows[i];
+      constraints[map[i]] = d->constraints[i];
+
+      if (multibyte_prop != NULL)
+        multibyte_prop[map[i]] = d->multibyte_prop[i];
+
+      for (idx_t j = 0; j < d->follows[i].nelem; j++)
+        {
+          if (map[d->follows[i].elems[j].index] == -1)
+            map[d->follows[i].elems[j].index] = nleaves++;
+
+          d->follows[i].elems[j].index = map[d->follows[i].elems[j].index];
+        }
+
+      qsort (d->follows[i].elems, d->follows[i].nelem,
+             sizeof *d->follows[i].elems, compare);
+    }
+
+  for (idx_t i = 0; i < nleaves; i++)
+    {
+      d->tokens[i] = tokens[i];
+      d->follows[i] = follows[i];
+      d->constraints[i] = constraints[i];
+
+      if (multibyte_prop != NULL)
+        d->multibyte_prop[i] = multibyte_prop[i];
+    }
+
+  d->tindex = d->nleaves = nleaves;
+
+  free (tokens);
+  free (follows);
+  free (constraints);
+  free (multibyte_prop);
+  free (map);
+}
+
+static void
+dfaoptimize (struct dfa *d)
+{
+  char *flags = xizalloc (d->tindex);
+
+  for (idx_t i = 0; i < d->tindex; i++)
+    {
+      for (idx_t j = 0; j < d->follows[i].nelem; j++)
+        {
+          if (d->follows[i].elems[j].index == i)
+            flags[d->follows[i].elems[j].index] |= OPT_REPEAT;
+          else if (d->follows[i].elems[j].index < i)
+            flags[d->follows[i].elems[j].index] |= OPT_LPAREN;
+          else if (flags[d->follows[i].elems[j].index] &= OPT_WALKED)
+            flags[d->follows[i].elems[j].index] |= OPT_RPAREN;
+          else
+            flags[d->follows[i].elems[j].index] |= OPT_WALKED;
+        }
+    }
+
+  flags[0] |= OPT_QUEUED;
+
+  position_set merged0;
+  position_set *merged = &merged0;
+  alloc_position_set (merged, d->nleaves);
+
+  d->constraints = xicalloc (d->tindex, sizeof *d->constraints);
+
+  for (idx_t i = 0; i < d->tindex; i++)
+    if (flags[i] & OPT_QUEUED)
+      merge_nfa_state (d, i, flags, merged);
+
+  reorder_tokens (d);
+
+  free (merged->elems);
+  free (flags);
+}
+
+/* Perform bottom-up analysis on the parse tree, computing various functions.
+   Note that at this point, we're pretending constructs like \< are real
+   characters rather than constraints on what can follow them.
+
+   Nullable:  A node is nullable if it is at the root of a regexp that can
+   match the empty string.
+   *  EMPTY leaves are nullable.
+   * No other leaf is nullable.
+   * A QMARK or STAR node is nullable.
+   * A PLUS node is nullable if its argument is nullable.
+   * A CAT node is nullable if both its arguments are nullable.
+   * An OR node is nullable if either argument is nullable.
+
+   Firstpos:  The firstpos of a node is the set of positions (nonempty leaves)
+   that could correspond to the first character of a string matching the
+   regexp rooted at the given node.
+   * EMPTY leaves have empty firstpos.
+   * The firstpos of a nonempty leaf is that leaf itself.
+   * The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its
+     argument.
+   * The firstpos of a CAT node is the firstpos of the left argument, union
+     the firstpos of the right if the left argument is nullable.
+   * The firstpos of an OR node is the union of firstpos of each argument.
+
+   Lastpos:  The lastpos of a node is the set of positions that could
+   correspond to the last character of a string matching the regexp at
+   the given node.
+   * EMPTY leaves have empty lastpos.
+   * The lastpos of a nonempty leaf is that leaf itself.
+   * The lastpos of a QMARK, STAR, or PLUS node is the lastpos of its
+     argument.
+   * The lastpos of a CAT node is the lastpos of its right argument, union
+     the lastpos of the left if the right argument is nullable.
+   * The lastpos of an OR node is the union of the lastpos of each argument.
+
+   Follow:  The follow of a position is the set of positions that could
+   correspond to the character following a character matching the node in
+   a string matching the regexp.  At this point we consider special symbols
+   that match the empty string in some context to be just normal characters.
+   Later, if we find that a special symbol is in a follow set, we will
+   replace it with the elements of its follow, labeled with an appropriate
+   constraint.
+   * Every node in the firstpos of the argument of a STAR or PLUS node is in
+     the follow of every node in the lastpos.
+   * Every node in the firstpos of the second argument of a CAT node is in
+     the follow of every node in the lastpos of the first argument.
+
+   Because of the postfix representation of the parse tree, the depth-first
+   analysis is conveniently done by a linear scan with the aid of a stack.
+   Sets are stored as arrays of the elements, obeying a stack-like allocation
+   scheme; the number of elements in each set deeper in the stack can be
+   used to determine the address of a particular set's array.  */
+static void
+dfaanalyze (struct dfa *d, bool searchflag)
+{
+  /* Array allocated to hold position sets.  */
+  position *posalloc = xnmalloc (d->nleaves, 2 * sizeof *posalloc);
+  /* Firstpos and lastpos elements.  */
+  position *firstpos = posalloc;
+  position *lastpos = firstpos + d->nleaves;
+  position pos;
+  position_set tmp;
+
+  /* Stack for element counts and nullable flags.  */
+  struct
+  {
+    /* Whether the entry is nullable.  */
+    bool nullable;
+
+    /* Counts of firstpos and lastpos sets.  */
+    idx_t nfirstpos;
+    idx_t nlastpos;
+  } *stkalloc = xnmalloc (d->depth, sizeof *stkalloc), *stk = stkalloc;
+
+  position_set merged;          /* Result of merging sets.  */
+
+  addtok (d, CAT);
+  idx_t tindex = d->tindex;
+
+#ifdef DEBUG
+  fprintf (stderr, "dfaanalyze:\n");
+  for (idx_t i = 0; i < tindex; i++)
+    {
+      fprintf (stderr, " %td:", i);
+      prtok (d->tokens[i]);
+    }
+  putc ('\n', stderr);
+#endif
+
+  d->searchflag = searchflag;
+  alloc_position_set (&merged, d->nleaves);
+  d->follows = xicalloc (tindex, sizeof *d->follows);
+  position_set *backward
+    = d->epsilon ? xicalloc (tindex, sizeof *backward) : NULL;
+
+  for (idx_t i = 0; i < tindex; i++)
+    {
+      switch (d->tokens[i])
+        {
+        case EMPTY:
+          /* The empty set is nullable.  */
+          stk->nullable = true;
+
+          /* The firstpos and lastpos of the empty leaf are both empty.  */
+          stk->nfirstpos = stk->nlastpos = 0;
+          stk++;
+          break;
+
+        case STAR:
+        case PLUS:
+          /* Every element in the lastpos of the argument is in the backward
+             set of every element in the firstpos.  */
+          if (d->epsilon)
+            {
+              tmp.elems = lastpos - stk[-1].nlastpos;
+              tmp.nelem = stk[-1].nlastpos;
+              for (position *p = firstpos - stk[-1].nfirstpos;
+                   p < firstpos; p++)
+                merge2 (&backward[p->index], &tmp, &merged);
+            }
+
+          /* Every element in the firstpos of the argument is in the follow
+             of every element in the lastpos.  */
+          {
+            tmp.elems = firstpos - stk[-1].nfirstpos;
+            tmp.nelem = stk[-1].nfirstpos;
+            for (position *p = lastpos - stk[-1].nlastpos; p < lastpos; p++)
+              merge2 (&d->follows[p->index], &tmp, &merged);
+          }
+          FALLTHROUGH;
+        case QMARK:
+          /* A QMARK or STAR node is automatically nullable.  */
+          if (d->tokens[i] != PLUS)
+            stk[-1].nullable = true;
+          break;
+
+        case CAT:
+          /* Every element in the lastpos of the first argument is in
+             the backward set of every element in the firstpos of the
+             second argument.  */
+          if (backward)
+            {
+              tmp.nelem = stk[-2].nlastpos;
+              tmp.elems = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
+              for (position *p = firstpos - stk[-1].nfirstpos;
+                   p < firstpos; p++)
+                merge2 (&backward[p->index], &tmp, &merged);
+            }
+
+          /* Every element in the firstpos of the second argument is in the
+             follow of every element in the lastpos of the first argument.  */
+          {
+            tmp.nelem = stk[-1].nfirstpos;
+            tmp.elems = firstpos - stk[-1].nfirstpos;
+            for (position *plim = lastpos - stk[-1].nlastpos,
+                   *p = plim - stk[-2].nlastpos;
+                 p < plim; p++)
+              merge2 (&d->follows[p->index], &tmp, &merged);
+          }
+
+          /* The firstpos of a CAT node is the firstpos of the first argument,
+             union that of the second argument if the first is nullable.  */
+          if (stk[-2].nullable)
+            stk[-2].nfirstpos += stk[-1].nfirstpos;
+          else
+            firstpos -= stk[-1].nfirstpos;
+
+          /* The lastpos of a CAT node is the lastpos of the second argument,
+             union that of the first argument if the second is nullable.  */
+          if (stk[-1].nullable)
+            stk[-2].nlastpos += stk[-1].nlastpos;
+          else
+            {
+              position *p = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
+              for (idx_t j = 0; j < stk[-1].nlastpos; j++)
+                p[j] = p[j + stk[-2].nlastpos];
+              lastpos -= stk[-2].nlastpos;
+              stk[-2].nlastpos = stk[-1].nlastpos;
+            }
+
+          /* A CAT node is nullable if both arguments are nullable.  */
+          stk[-2].nullable &= stk[-1].nullable;
+          stk--;
+          break;
+
+        case OR:
+          /* The firstpos is the union of the firstpos of each argument.  */
+          stk[-2].nfirstpos += stk[-1].nfirstpos;
+
+          /* The lastpos is the union of the lastpos of each argument.  */
+          stk[-2].nlastpos += stk[-1].nlastpos;
+
+          /* An OR node is nullable if either argument is nullable.  */
+          stk[-2].nullable |= stk[-1].nullable;
+          stk--;
+          break;
+
+        default:
+          /* Anything else is a nonempty position.  (Note that special
+             constructs like \< are treated as nonempty strings here;
+             an "epsilon closure" effectively makes them nullable later.
+             Backreferences have to get a real position so we can detect
+             transitions on them later.  But they are nullable.  */
+          stk->nullable = d->tokens[i] == BACKREF;
+
+          /* This position is in its own firstpos and lastpos.  */
+          stk->nfirstpos = stk->nlastpos = 1;
+          stk++;
+
+          firstpos->index = lastpos->index = i;
+          firstpos->constraint = lastpos->constraint = NO_CONSTRAINT;
+          firstpos++, lastpos++;
+
+          break;
+        }
+#ifdef DEBUG
+      /* ... balance the above nonsyntactic #ifdef goo...  */
+      fprintf (stderr, "node %td:", i);
+      prtok (d->tokens[i]);
+      putc ('\n', stderr);
+      fprintf (stderr,
+               stk[-1].nullable ? " nullable: yes\n" : " nullable: no\n");
+      fprintf (stderr, " firstpos:");
+      for (idx_t j = 0; j < stk[-1].nfirstpos; j++)
+        {
+          fprintf (stderr, " %td:", firstpos[j - stk[-1].nfirstpos].index);
+          prtok (d->tokens[firstpos[j - stk[-1].nfirstpos].index]);
+        }
+      fprintf (stderr, "\n lastpos:");
+      for (idx_t j = 0; j < stk[-1].nlastpos; j++)
+        {
+          fprintf (stderr, " %td:", lastpos[j - stk[-1].nlastpos].index);
+          prtok (d->tokens[lastpos[j - stk[-1].nlastpos].index]);
+        }
+      putc ('\n', stderr);
+#endif
+    }
+
+  if (backward)
+    {
+      /* For each follow set that is the follow set of a real position,
+         replace it with its epsilon closure.  */
+      epsclosure (d, backward);
+
+      for (idx_t i = 0; i < tindex; i++)
+        free (backward[i].elems);
+      free (backward);
+    }
+
+  dfaoptimize (d);
+
+#ifdef DEBUG
+  for (idx_t i = 0; i < tindex; i++)
+    if (d->tokens[i] == BEG || d->tokens[i] < NOTCHAR
+        || d->tokens[i] == BACKREF || d->tokens[i] == ANYCHAR
+        || d->tokens[i] == MBCSET || d->tokens[i] >= CSET)
+      {
+        fprintf (stderr, "follows(%td:", i);
+        prtok (d->tokens[i]);
+        fprintf (stderr, "):");
+        for (idx_t j = 0; j < d->follows[i].nelem; j++)
+          {
+            fprintf (stderr, " %td:", d->follows[i].elems[j].index);
+            prtok (d->tokens[d->follows[i].elems[j].index]);
+          }
+        putc ('\n', stderr);
+      }
+#endif
+
+  pos.index = 0;
+  pos.constraint = NO_CONSTRAINT;
+
+  alloc_position_set (&tmp, 1);
+
+  append (pos, &tmp);
+
+  d->separates = xicalloc (tindex, sizeof *d->separates);
+
+  for (idx_t i = 0; i < tindex; i++)
+    {
+      if (prev_newline_dependent (d->constraints[i]))
+        d->separates[i] |= CTX_NEWLINE;
+      if (prev_letter_dependent (d->constraints[i]))
+        d->separates[i] |= CTX_LETTER;
+
+      for (idx_t j = 0; j < d->follows[i].nelem; j++)
+        {
+          if (prev_newline_dependent (d->follows[i].elems[j].constraint))
+            d->separates[i] |= CTX_NEWLINE;
+          if (prev_letter_dependent (d->follows[i].elems[j].constraint))
+            d->separates[i] |= CTX_LETTER;
+        }
+    }
+
+  /* Context wanted by some position.  */
+  int separate_contexts = state_separate_contexts (d, &tmp);
+
+  /* Build the initial state.  */
+  if (separate_contexts & CTX_NEWLINE)
+    state_index (d, &tmp, CTX_NEWLINE);
+  d->initstate_notbol = d->min_trcount
+    = state_index (d, &tmp, separate_contexts ^ CTX_ANY);
+  if (separate_contexts & CTX_LETTER)
+    d->min_trcount = state_index (d, &tmp, CTX_LETTER);
+  d->min_trcount++;
+  d->trcount = 0;
+
+  free (posalloc);
+  free (stkalloc);
+  free (merged.elems);
+  free (tmp.elems);
+}
+
+/* Make sure D's state arrays are large enough to hold NEW_STATE.  */
+static void
+realloc_trans_if_necessary (struct dfa *d)
+{
+  state_num oldalloc = d->tralloc;
+  if (oldalloc < d->sindex)
+    {
+      state_num **realtrans = d->trans ? d->trans - 2 : NULL;
+      idx_t newalloc1 = realtrans ? d->tralloc + 2 : 0;
+      realtrans = xpalloc (realtrans, &newalloc1, d->sindex - oldalloc,
+                           -1, sizeof *realtrans);
+      realtrans[0] = realtrans[1] = NULL;
+      d->trans = realtrans + 2;
+      idx_t newalloc = d->tralloc = newalloc1 - 2;
+      d->fails = xreallocarray (d->fails, newalloc, sizeof *d->fails);
+      d->success = xreallocarray (d->success, newalloc, sizeof *d->success);
+      d->newlines = xreallocarray (d->newlines, newalloc, sizeof *d->newlines);
+      if (d->localeinfo.multibyte)
+        {
+          realtrans = d->mb_trans ? d->mb_trans - 2 : NULL;
+          realtrans = xreallocarray (realtrans, newalloc1, sizeof *realtrans);
+          if (oldalloc == 0)
+            realtrans[0] = realtrans[1] = NULL;
+          d->mb_trans = realtrans + 2;
+        }
+      for (; oldalloc < newalloc; oldalloc++)
+        {
+          d->trans[oldalloc] = NULL;
+          d->fails[oldalloc] = NULL;
+          if (d->localeinfo.multibyte)
+            d->mb_trans[oldalloc] = NULL;
+        }
+    }
+}
+
+/*
+   Calculate the transition table for a new state derived from state s
+   for a compiled dfa d after input character uc, and return the new
+   state number.
+
+   Do not worry about all possible input characters; calculate just the group
+   of positions that match uc.  Label it with the set of characters that
+   every position in the group matches (taking into account, if necessary,
+   preceding context information of s).  Then find the union
+   of these positions' follows, i.e., the set of positions of the
+   new state.  For each character in the group's label, set the transition
+   on this character to be to a state corresponding to the set's positions,
+   and its associated backward context information, if necessary.
+
+   When building a searching matcher, include the positions of state
+   0 in every state.
+
+   The group is constructed by building an equivalence-class
+   partition of the positions of s.
+
+   For each position, find the set of characters C that it matches.  Eliminate
+   any characters from C that fail on grounds of backward context.
+
+   Check whether the group's label L has nonempty
+   intersection with C.  If L - C is nonempty, create a new group labeled
+   L - C and having the same positions as the current group, and set L to
+   the intersection of L and C.  Insert the position in the group, set
+   C = C - L, and resume scanning.
+
+   If after comparing with every group there are characters remaining in C,
+   create a new group labeled with the characters of C and insert this
+   position in that group.  */
+
+static state_num
+build_state (state_num s, struct dfa *d, unsigned char uc)
+{
+  position_set follows;         /* Union of the follows for each
+                                   position of the current state.  */
+  position_set group;           /* Positions that match the input char.  */
+  position_set tmp;             /* Temporary space for merging sets.  */
+  state_num state;              /* New state.  */
+  state_num state_newline;      /* New state on a newline transition.  */
+  state_num state_letter;       /* New state on a letter transition.  */
+
+#ifdef DEBUG
+  fprintf (stderr, "build state %td\n", s);
+#endif
+
+  /* A pointer to the new transition table, and the table itself.  */
+  state_num **ptrans = (accepting (s, d) ? d->fails : d->trans) + s;
+  state_num *trans = *ptrans;
+
+  if (!trans)
+    {
+      /* MAX_TRCOUNT is an arbitrary upper limit on the number of
+         transition tables that can exist at once, other than for
+         initial states.  Often-used transition tables are quickly
+         rebuilt, whereas rarely-used ones are cleared away.  */
+      if (MAX_TRCOUNT <= d->trcount)
+        {
+          for (state_num i = d->min_trcount; i < d->tralloc; i++)
+            {
+              free (d->trans[i]);
+              free (d->fails[i]);
+              d->trans[i] = d->fails[i] = NULL;
+            }
+          d->trcount = 0;
+        }
+
+      d->trcount++;
+      *ptrans = trans = xmalloc (NOTCHAR * sizeof *trans);
+
+      /* Fill transition table with a default value which means that the
+         transited state has not been calculated yet.  */
+      for (int i = 0; i < NOTCHAR; i++)
+        trans[i] = -2;
+    }
+
+  /* Set up the success bits for this state.  */
+  d->success[s] = 0;
+  if (accepts_in_context (d->states[s].context, CTX_NEWLINE, s, d))
+    d->success[s] |= CTX_NEWLINE;
+  if (accepts_in_context (d->states[s].context, CTX_LETTER, s, d))
+    d->success[s] |= CTX_LETTER;
+  if (accepts_in_context (d->states[s].context, CTX_NONE, s, d))
+    d->success[s] |= CTX_NONE;
+
+  alloc_position_set (&follows, d->nleaves);
+
+  /* Find the union of the follows of the positions of the group.
+     This is a hideously inefficient loop.  Fix it someday.  */
+  for (idx_t j = 0; j < d->states[s].elems.nelem; j++)
+    for (idx_t k = 0;
+         k < d->follows[d->states[s].elems.elems[j].index].nelem; ++k)
+      insert (d->follows[d->states[s].elems.elems[j].index].elems[k],
+              &follows);
+
+  /* Positions that match the input char.  */
+  alloc_position_set (&group, d->nleaves);
+
+  /* The group's label.  */
+  charclass label;
+  fillset (&label);
+
+  for (idx_t i = 0; i < follows.nelem; i++)
+    {
+      charclass matches;            /* Set of matching characters.  */
+      position pos = follows.elems[i];
+      bool matched = false;
+      if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR)
+        {
+          zeroset (&matches);
+          setbit (d->tokens[pos.index], &matches);
+          if (d->tokens[pos.index] == uc)
+            matched = true;
+        }
+      else if (d->tokens[pos.index] >= CSET)
+        {
+          matches = d->charclasses[d->tokens[pos.index] - CSET];
+          if (tstbit (uc, &matches))
+            matched = true;
+        }
+      else if (d->tokens[pos.index] == ANYCHAR)
+        {
+          matches = d->charclasses[d->canychar];
+          if (tstbit (uc, &matches))
+            matched = true;
+
+          /* ANYCHAR must match with a single character, so we must put
+             it to D->states[s].mbps which contains the positions which
+             can match with a single character not a byte.  If all
+             positions which has ANYCHAR does not depend on context of
+             next character, we put the follows instead of it to
+             D->states[s].mbps to optimize.  */
+          if (succeeds_in_context (pos.constraint, d->states[s].context,
+                                   CTX_NONE))
+            {
+              if (d->states[s].mbps.nelem == 0)
+                alloc_position_set (&d->states[s].mbps, 1);
+              insert (pos, &d->states[s].mbps);
+            }
+        }
+      else
+        continue;
+
+      /* Some characters may need to be eliminated from matches because
+         they fail in the current context.  */
+      if (pos.constraint != NO_CONSTRAINT)
+        {
+          if (!succeeds_in_context (pos.constraint,
+                                    d->states[s].context, CTX_NEWLINE))
+            for (int j = 0; j < CHARCLASS_WORDS; j++)
+              matches.w[j] &= ~d->syntax.newline.w[j];
+          if (!succeeds_in_context (pos.constraint,
+                                    d->states[s].context, CTX_LETTER))
+            for (int j = 0; j < CHARCLASS_WORDS; ++j)
+              matches.w[j] &= ~d->syntax.letters.w[j];
+          if (!succeeds_in_context (pos.constraint,
+                                    d->states[s].context, CTX_NONE))
+            for (int j = 0; j < CHARCLASS_WORDS; ++j)
+              matches.w[j] &= d->syntax.letters.w[j] | d->syntax.newline.w[j];
+
+          /* If there are no characters left, there's no point in going on.  */
+          if (emptyset (&matches))
+            continue;
+
+          /* If we have reset the bit that made us declare "matched", reset
+             that indicator, too.  This is required to avoid an infinite loop
+             with this command: echo cx | LC_ALL=C grep -E 'c\b[x ]'  */
+          if (!tstbit (uc, &matches))
+            matched = false;
+        }
+
+#ifdef DEBUG
+      fprintf (stderr, " nextpos %td:", pos.index);
+      prtok (d->tokens[pos.index]);
+      fprintf (stderr, " of");
+      for (unsigned j = 0; j < NOTCHAR; j++)
+        if (tstbit (j, &matches))
+          fprintf (stderr, " 0x%02x", j);
+      fprintf (stderr, "\n");
+#endif
+
+      if (matched)
+        {
+          for (int k = 0; k < CHARCLASS_WORDS; ++k)
+            label.w[k] &= matches.w[k];
+          append (pos, &group);
+        }
+      else
+        {
+          for (int k = 0; k < CHARCLASS_WORDS; ++k)
+            label.w[k] &= ~matches.w[k];
+        }
+    }
+
+  alloc_position_set (&tmp, d->nleaves);
+
+  if (group.nelem > 0)
+    {
+      /* If we are building a searching matcher, throw in the positions
+         of state 0 as well, if possible.  */
+      if (d->searchflag)
+        {
+          /* If a token in follows.elems is not 1st byte of a multibyte
+             character, or the states of follows must accept the bytes
+             which are not 1st byte of the multibyte character.
+             Then, if a state of follows encounters a byte, it must not be
+             a 1st byte of a multibyte character nor a single byte character.
+             In this case, do not add state[0].follows to next state, because
+             state[0] must accept 1st-byte.
+
+             For example, suppose <sb a> is a certain single byte character,
+             <mb A> is a certain multibyte character, and the codepoint of
+             <sb a> equals the 2nd byte of the codepoint of <mb A>.  When
+             state[0] accepts <sb a>, state[i] transits to state[i+1] by
+             accepting the 1st byte of <mb A>, and state[i+1] accepts the
+             2nd byte of <mb A>, if state[i+1] encounters the codepoint of
+             <sb a>, it must not be <sb a> but the 2nd byte of <mb A>, so do
+             not add state[0].  */
+
+          bool mergeit = !d->localeinfo.multibyte;
+          if (!mergeit)
+            {
+              mergeit = true;
+              for (idx_t j = 0; mergeit && j < group.nelem; j++)
+                mergeit &= d->multibyte_prop[group.elems[j].index];
+            }
+          if (mergeit)
+            merge2 (&group, &d->states[0].elems, &tmp);
+        }
+
+      /* Find out if the new state will want any context information,
+         by calculating possible contexts that the group can match,
+         and separate contexts that the new state wants to know.  */
+      int possible_contexts = charclass_context (d, &label);
+      int separate_contexts = state_separate_contexts (d, &group);
+
+      /* Find the state(s) corresponding to the union of the follows.  */
+      if (possible_contexts & ~separate_contexts)
+        state = state_index (d, &group, separate_contexts ^ CTX_ANY);
+      else
+        state = -1;
+      if (separate_contexts & possible_contexts & CTX_NEWLINE)
+        state_newline = state_index (d, &group, CTX_NEWLINE);
+      else
+        state_newline = state;
+      if (separate_contexts & possible_contexts & CTX_LETTER)
+        state_letter = state_index (d, &group, CTX_LETTER);
+      else
+        state_letter = state;
+
+      /* Reallocate now, to reallocate any newline transition properly.  */
+      realloc_trans_if_necessary (d);
+    }
+
+  /* If we are a searching matcher, the default transition is to a state
+     containing the positions of state 0, otherwise the default transition
+     is to fail miserably.  */
+  else if (d->searchflag)
+    {
+      state_newline = 0;
+      state_letter = d->min_trcount - 1;
+      state = d->initstate_notbol;
+    }
+  else
+    {
+      state_newline = -1;
+      state_letter = -1;
+      state = -1;
+    }
+
+  /* Set the transitions for each character in the label.  */
+  for (int i = 0; i < NOTCHAR; i++)
+    if (tstbit (i, &label))
+      switch (d->syntax.sbit[i])
+        {
+        case CTX_NEWLINE:
+          trans[i] = state_newline;
+          break;
+        case CTX_LETTER:
+          trans[i] = state_letter;
+          break;
+        default:
+          trans[i] = state;
+          break;
+        }
+
+#ifdef DEBUG
+  fprintf (stderr, "trans table %td", s);
+  for (int i = 0; i < NOTCHAR; ++i)
+    {
+      if (!(i & 0xf))
+        fprintf (stderr, "\n");
+      fprintf (stderr, " %2td", trans[i]);
+    }
+  fprintf (stderr, "\n");
+#endif
+
+  free (group.elems);
+  free (follows.elems);
+  free (tmp.elems);
+
+  /* Keep the newline transition in a special place so we can use it as
+     a sentinel.  */
+  if (tstbit (d->syntax.eolbyte, &label))
+    {
+      d->newlines[s] = trans[d->syntax.eolbyte];
+      trans[d->syntax.eolbyte] = -1;
+    }
+
+  return trans[uc];
+}
+
+/* Multibyte character handling sub-routines for dfaexec.  */
+
+/* Consume a single byte and transit state from 's' to '*next_state'.
+   This function is almost same as the state transition routin in dfaexec.
+   But state transition is done just once, otherwise matching succeed or
+   reach the end of the buffer.  */
+static state_num
+transit_state_singlebyte (struct dfa *d, state_num s, unsigned char const **pp)
+{
+  state_num *t;
+
+  if (d->trans[s])
+    t = d->trans[s];
+  else if (d->fails[s])
+    t = d->fails[s];
+  else
+    {
+      build_state (s, d, **pp);
+      if (d->trans[s])
+        t = d->trans[s];
+      else
+        {
+          t = d->fails[s];
+          assert (t);
+        }
+    }
+
+  if (t[**pp] == -2)
+    build_state (s, d, **pp);
+
+  return t[*(*pp)++];
+}
+
+/* Transit state from s, then return new state and update the pointer of
+   the buffer.  This function is for a period operator which can match a
+   multi-byte character.  */
+static state_num
+transit_state (struct dfa *d, state_num s, unsigned char const **pp,
+               unsigned char const *end)
+{
+  wint_t wc;
+
+  int mbclen = mbs_to_wchar (&wc, (char const *) *pp, end - *pp, d);
+
+  /* This state has some operators which can match a multibyte character.  */
+  d->mb_follows.nelem = 0;
+
+  /* Calculate the state which can be reached from the state 's' by
+     consuming 'mbclen' single bytes from the buffer.  */
+  state_num s1 = s;
+  int mbci;
+  for (mbci = 0; mbci < mbclen && (mbci == 0 || d->min_trcount <= s); mbci++)
+    s = transit_state_singlebyte (d, s, pp);
+  *pp += mbclen - mbci;
+
+  if (wc == WEOF)
+    {
+      /* It is an invalid character, so ANYCHAR is not accepted.  */
+      return s;
+    }
+
+  /* If all positions which have ANYCHAR do not depend on the context
+     of the next character, calculate the next state with
+     pre-calculated follows and cache the result.  */
+  if (d->states[s1].mb_trindex < 0)
+    {
+      if (MAX_TRCOUNT <= d->mb_trcount)
+        {
+          state_num s3;
+          for (s3 = -1; s3 < d->tralloc; s3++)
+            {
+              free (d->mb_trans[s3]);
+              d->mb_trans[s3] = NULL;
+            }
+
+          for (state_num i = 0; i < d->sindex; i++)
+            d->states[i].mb_trindex = -1;
+          d->mb_trcount = 0;
+        }
+      d->states[s1].mb_trindex = d->mb_trcount++;
+    }
+
+  if (! d->mb_trans[s])
+    {
+      enum { TRANSPTR_SIZE = sizeof *d->mb_trans[s] };
+      enum { TRANSALLOC_SIZE = MAX_TRCOUNT * TRANSPTR_SIZE };
+      d->mb_trans[s] = xmalloc (TRANSALLOC_SIZE);
+      for (int i = 0; i < MAX_TRCOUNT; i++)
+        d->mb_trans[s][i] = -1;
+    }
+  else if (d->mb_trans[s][d->states[s1].mb_trindex] >= 0)
+    return d->mb_trans[s][d->states[s1].mb_trindex];
+
+  if (s == -1)
+    copy (&d->states[s1].mbps, &d->mb_follows);
+  else
+    merge (&d->states[s1].mbps, &d->states[s].elems, &d->mb_follows);
+
+  int separate_contexts = state_separate_contexts (d, &d->mb_follows);
+  state_num s2 = state_index (d, &d->mb_follows, separate_contexts ^ CTX_ANY);
+  realloc_trans_if_necessary (d);
+
+  d->mb_trans[s][d->states[s1].mb_trindex] = s2;
+
+  return s2;
+}
+
+/* The initial state may encounter a byte which is not a single byte character
+   nor the first byte of a multibyte character.  But it is incorrect for the
+   initial state to accept such a byte.  For example, in Shift JIS the regular
+   expression "\\" accepts the codepoint 0x5c, but should not accept the second
+   byte of the codepoint 0x815c.  Then the initial state must skip the bytes
+   that are not a single byte character nor the first byte of a multibyte
+   character.
+
+   Given DFA state d, use mbs_to_wchar to advance MBP until it reaches
+   or exceeds P, and return the advanced MBP.  If WCP is non-NULL and
+   the result is greater than P, set *WCP to the final wide character
+   processed, or to WEOF if no wide character is processed.  Otherwise,
+   if WCP is non-NULL, *WCP may or may not be updated.
+
+   Both P and MBP must be no larger than END.  */
+static unsigned char const *
+skip_remains_mb (struct dfa *d, unsigned char const *p,
+                 unsigned char const *mbp, char const *end)
+{
+  if (d->syntax.never_trail[*p])
+    return p;
+  while (mbp < p)
+    {
+      wint_t wc;
+      mbp += mbs_to_wchar (&wc, (char const *) mbp,
+                           end - (char const *) mbp, d);
+    }
+  return mbp;
+}
+
+/* Search through a buffer looking for a match to the struct dfa *D.
+   Find the first occurrence of a string matching the regexp in the
+   buffer, and the shortest possible version thereof.  Return a pointer to
+   the first character after the match, or NULL if none is found.  BEGIN
+   points to the beginning of the buffer, and END points to the first byte
+   after its end.  Note however that we store a sentinel byte (usually
+   newline) in *END, so the actual buffer must be one byte longer.
+   When ALLOW_NL, newlines may appear in the matching string.
+   If COUNT is non-NULL, increment *COUNT once for each newline processed.
+   If MULTIBYTE, the input consists of multibyte characters and/or
+   encoding-error bytes.  Otherwise, it consists of single-byte characters.
+   Here is the list of features that make this DFA matcher punt:
+    - [M-N] range in non-simple locale: regex is up to 25% faster on [a-z]
+    - [^...] in non-simple locale
+    - [[=foo=]] or [[.foo.]]
+    - [[:alpha:]] etc. in multibyte locale (except [[:digit:]] works OK)
+    - back-reference: (.)\1
+    - word-delimiter in multibyte locale: \<, \>, \b, \B
+   See struct localeinfo.simple for the definition of "simple locale".  */
+
+static inline char *
+dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl,
+              ptrdiff_t *count, bool multibyte)
+{
+  if (MAX_TRCOUNT <= d->sindex)
+    {
+      for (state_num s = d->min_trcount; s < d->sindex; s++)
+        {
+          free (d->states[s].elems.elems);
+          free (d->states[s].mbps.elems);
+        }
+      d->sindex = d->min_trcount;
+
+      if (d->trans)
+        {
+          for (state_num s = 0; s < d->tralloc; s++)
+            {
+              free (d->trans[s]);
+              free (d->fails[s]);
+              d->trans[s] = d->fails[s] = NULL;
+            }
+          d->trcount = 0;
+        }
+
+      if (d->localeinfo.multibyte && d->mb_trans)
+        {
+          for (state_num s = -1; s < d->tralloc; s++)
+            {
+              free (d->mb_trans[s]);
+              d->mb_trans[s] = NULL;
+            }
+          for (state_num s = 0; s < d->min_trcount; s++)
+            d->states[s].mb_trindex = -1;
+          d->mb_trcount = 0;
+        }
+    }
+
+  if (!d->tralloc)
+    realloc_trans_if_necessary (d);
+
+  /* Current state.  */
+  state_num s = 0, s1 = 0;
+
+  /* Current input character.  */
+  unsigned char const *p = (unsigned char const *) begin;
+  unsigned char const *mbp = p;
+
+  /* Copy of d->trans so it can be optimized into a register.  */
+  state_num **trans = d->trans;
+  unsigned char eol = d->syntax.eolbyte;  /* Likewise for eolbyte.  */
+  unsigned char saved_end = *(unsigned char *) end;
+  *end = eol;
+
+  if (multibyte)
+    {
+      memset (&d->mbs, 0, sizeof d->mbs);
+      if (d->mb_follows.alloc == 0)
+        alloc_position_set (&d->mb_follows, d->nleaves);
+    }
+
+  idx_t nlcount = 0;
+  for (;;)
+    {
+      state_num *t;
+      while ((t = trans[s]) != NULL)
+        {
+          if (s < d->min_trcount)
+            {
+              if (!multibyte || d->states[s].mbps.nelem == 0)
+                {
+                  while (t[*p] == s)
+                    p++;
+                }
+              if (multibyte)
+                p = mbp = skip_remains_mb (d, p, mbp, end);
+            }
+
+          if (multibyte)
+            {
+              s1 = s;
+
+              if (d->states[s].mbps.nelem == 0
+                  || d->localeinfo.sbctowc[*p] != WEOF || (char *) p >= end)
+                {
+                  /* If an input character does not match ANYCHAR, do it
+                     like a single-byte character.  */
+                  s = t[*p++];
+                }
+              else
+                {
+                  s = transit_state (d, s, &p, (unsigned char *) end);
+                  mbp = p;
+                  trans = d->trans;
+                }
+            }
+          else
+            {
+              s1 = t[*p++];
+              t = trans[s1];
+              if (! t)
+                {
+                  state_num tmp = s;
+                  s = s1;
+                  s1 = tmp;     /* swap */
+                  break;
+                }
+              if (s < d->min_trcount)
+                {
+                  while (t[*p] == s1)
+                    p++;
+                }
+              s = t[*p++];
+            }
+        }
+
+      if (s < 0)
+        {
+          if (s == -2)
+            {
+              s = build_state (s1, d, p[-1]);
+              trans = d->trans;
+            }
+          else if ((char *) p <= end && p[-1] == eol && 0 <= d->newlines[s1])
+            {
+              /* The previous character was a newline.  Count it, and skip
+                 checking of multibyte character boundary until here.  */
+              nlcount++;
+              mbp = p;
+
+              s = (allow_nl ? d->newlines[s1]
+                   : d->syntax.sbit[eol] == CTX_NEWLINE ? 0
+                   : d->syntax.sbit[eol] == CTX_LETTER ? d->min_trcount - 1
+                   : d->initstate_notbol);
+            }
+          else
+            {
+              p = NULL;
+              goto done;
+            }
+        }
+      else if (d->fails[s])
+        {
+          if ((d->success[s] & d->syntax.sbit[*p])
+              || ((char *) p == end
+                  && accepts_in_context (d->states[s].context, CTX_NEWLINE, s,
+                                         d)))
+            goto done;
+
+          if (multibyte && s < d->min_trcount)
+            p = mbp = skip_remains_mb (d, p, mbp, end);
+
+          s1 = s;
+          if (!multibyte || d->states[s].mbps.nelem == 0
+              || d->localeinfo.sbctowc[*p] != WEOF || (char *) p >= end)
+            {
+              /* If a input character does not match ANYCHAR, do it
+                 like a single-byte character.  */
+              s = d->fails[s][*p++];
+            }
+          else
+            {
+              s = transit_state (d, s, &p, (unsigned char *) end);
+              mbp = p;
+              trans = d->trans;
+            }
+        }
+      else
+        {
+          build_state (s, d, p[0]);
+          trans = d->trans;
+        }
+    }
+
+ done:
+  if (count)
+    *count += nlcount;
+  *end = saved_end;
+  return (char *) p;
+}
+
+/* Specialized versions of dfaexec for multibyte and single-byte cases.
+   This is for performance, as dfaexec_main is an inline function.  */
+
+static char *
+dfaexec_mb (struct dfa *d, char const *begin, char *end,
+            bool allow_nl, ptrdiff_t *count, bool *backref)
+{
+  return dfaexec_main (d, begin, end, allow_nl, count, true);
+}
+
+static char *
+dfaexec_sb (struct dfa *d, char const *begin, char *end,
+            bool allow_nl, ptrdiff_t *count, bool *backref)
+{
+  return dfaexec_main (d, begin, end, allow_nl, count, false);
+}
+
+/* Always set *BACKREF and return BEGIN.  Use this wrapper for
+   any regexp that uses a construct not supported by this code.  */
+static char *
+dfaexec_noop (struct dfa *d, char const *begin, char *end,
+              bool allow_nl, ptrdiff_t *count, bool *backref)
+{
+  *backref = true;
+  return (char *) begin;
+}
+
+/* Like dfaexec_main (D, BEGIN, END, ALLOW_NL, COUNT, D->localeinfo.multibyte),
+   but faster and set *BACKREF if the DFA code does not support this
+   regexp usage.  */
+
+char *
+dfaexec (struct dfa *d, char const *begin, char *end,
+         bool allow_nl, ptrdiff_t *count, bool *backref)
+{
+  return d->dfaexec (d, begin, end, allow_nl, count, backref);
+}
+
+struct dfa *
+dfasuperset (struct dfa const *d)
+{
+  return d->superset;
+}
+
+bool
+dfaisfast (struct dfa const *d)
+{
+  return d->fast;
+}
+
+static void
+free_mbdata (struct dfa *d)
+{
+  free (d->multibyte_prop);
+  free (d->lex.brack.chars);
+  free (d->mb_follows.elems);
+
+  if (d->mb_trans)
+    {
+      state_num s;
+      for (s = -1; s < d->tralloc; s++)
+        free (d->mb_trans[s]);
+      free (d->mb_trans - 2);
+    }
+}
+
+/* Return true if every construct in D is supported by this DFA matcher.  */
+bool
+dfasupported (struct dfa const *d)
+{
+  for (idx_t i = 0; i < d->tindex; i++)
+    {
+      switch (d->tokens[i])
+        {
+        case BEGWORD:
+        case ENDWORD:
+        case LIMWORD:
+        case NOTLIMWORD:
+          if (!d->localeinfo.multibyte)
+            continue;
+          FALLTHROUGH;
+        case BACKREF:
+        case MBCSET:
+          return false;
+        }
+    }
+  return true;
+}
+
+/* Disable use of the superset DFA if it is not likely to help
+   performance.  */
+static void
+maybe_disable_superset_dfa (struct dfa *d)
+{
+  if (!d->localeinfo.using_utf8)
+    return;
+
+  bool have_backref = false;
+  for (idx_t i = 0; i < d->tindex; i++)
+    {
+      switch (d->tokens[i])
+        {
+        case ANYCHAR:
+          /* Lowered.  */
+          abort ();
+        case BACKREF:
+          have_backref = true;
+          break;
+        case MBCSET:
+          /* Requires multi-byte algorithm.  */
+          return;
+        default:
+          break;
+        }
+    }
+
+  if (!have_backref && d->superset)
+    {
+      /* The superset DFA is not likely to be much faster, so remove it.  */
+      dfafree (d->superset);
+      free (d->superset);
+      d->superset = NULL;
+    }
+
+  free_mbdata (d);
+  d->localeinfo.multibyte = false;
+  d->dfaexec = dfaexec_sb;
+  d->fast = true;
+}
+
+static void
+dfassbuild (struct dfa *d)
+{
+  struct dfa *sup = dfaalloc ();
+
+  *sup = *d;
+  sup->localeinfo.multibyte = false;
+  sup->dfaexec = dfaexec_sb;
+  sup->multibyte_prop = NULL;
+  sup->superset = NULL;
+  sup->states = NULL;
+  sup->sindex = 0;
+  sup->constraints = NULL;
+  sup->separates = NULL;
+  sup->follows = NULL;
+  sup->tralloc = 0;
+  sup->trans = NULL;
+  sup->fails = NULL;
+  sup->success = NULL;
+  sup->newlines = NULL;
+
+  sup->charclasses = xnmalloc (sup->calloc, sizeof *sup->charclasses);
+  if (d->cindex)
+    {
+      memcpy (sup->charclasses, d->charclasses,
+              d->cindex * sizeof *sup->charclasses);
+    }
+
+  sup->tokens = xnmalloc (d->tindex, 2 * sizeof *sup->tokens);
+  sup->talloc = d->tindex * 2;
+
+  bool have_achar = false;
+  bool have_nchar = false;
+  idx_t j;
+  for (idx_t i = j = 0; i < d->tindex; i++)
+    {
+      switch (d->tokens[i])
+        {
+        case ANYCHAR:
+        case MBCSET:
+        case BACKREF:
+          {
+            charclass ccl;
+            fillset (&ccl);
+            sup->tokens[j++] = CSET + charclass_index (sup, &ccl);
+            sup->tokens[j++] = STAR;
+            if (d->tokens[i + 1] == QMARK || d->tokens[i + 1] == STAR
+                || d->tokens[i + 1] == PLUS)
+              i++;
+            have_achar = true;
+          }
+          break;
+        case BEGWORD:
+        case ENDWORD:
+        case LIMWORD:
+        case NOTLIMWORD:
+          if (d->localeinfo.multibyte)
+            {
+              /* These constraints aren't supported in a multibyte locale.
+                 Ignore them in the superset DFA.  */
+              sup->tokens[j++] = EMPTY;
+              break;
+            }
+          FALLTHROUGH;
+        default:
+          sup->tokens[j++] = d->tokens[i];
+          if ((0 <= d->tokens[i] && d->tokens[i] < NOTCHAR)
+              || d->tokens[i] >= CSET)
+            have_nchar = true;
+          break;
+        }
+    }
+  sup->tindex = j;
+
+  if (have_nchar && (have_achar || d->localeinfo.multibyte))
+    d->superset = sup;
+  else
+    {
+      dfafree (sup);
+      free (sup);
+    }
+}
+
+/* Parse a string S of length LEN into D (but skip this step if S is null).
+   Then analyze D and build a matcher for it.
+   SEARCHFLAG says whether to build a searching or an exact matcher.  */
+void
+dfacomp (char const *s, idx_t len, struct dfa *d, bool searchflag)
+{
+  if (s != NULL)
+    dfaparse (s, len, d);
+
+  dfassbuild (d);
+
+  if (dfasupported (d))
+    {
+      maybe_disable_superset_dfa (d);
+      dfaanalyze (d, searchflag);
+    }
+  else
+    {
+      d->dfaexec = dfaexec_noop;
+    }
+
+  if (d->superset)
+    {
+      d->fast = true;
+      dfaanalyze (d->superset, searchflag);
+    }
+}
+
+/* Free the storage held by the components of a dfa.  */
+void
+dfafree (struct dfa *d)
+{
+  free (d->charclasses);
+  free (d->tokens);
+
+  if (d->localeinfo.multibyte)
+    free_mbdata (d);
+
+  free (d->constraints);
+  free (d->separates);
+
+  for (idx_t i = 0; i < d->sindex; i++)
+    {
+      free (d->states[i].elems.elems);
+      free (d->states[i].mbps.elems);
+    }
+  free (d->states);
+
+  if (d->follows)
+    {
+      for (idx_t i = 0; i < d->tindex; i++)
+        free (d->follows[i].elems);
+      free (d->follows);
+    }
+
+  if (d->trans)
+    {
+      for (idx_t i = 0; i < d->tralloc; i++)
+        {
+          free (d->trans[i]);
+          free (d->fails[i]);
+        }
+
+      free (d->trans - 2);
+      free (d->fails);
+      free (d->newlines);
+      free (d->success);
+    }
+
+  if (d->superset)
+    {
+      dfafree (d->superset);
+      free (d->superset);
+    }
+}
+
+/* Having found the postfix representation of the regular expression,
+   try to find a long sequence of characters that must appear in any line
+   containing the r.e.
+   Finding a "longest" sequence is beyond the scope here;
+   we take an easy way out and hope for the best.
+   (Take "(ab|a)b"--please.)
+
+   We do a bottom-up calculation of sequences of characters that must appear
+   in matches of r.e.'s represented by trees rooted at the nodes of the postfix
+   representation:
+        sequences that must appear at the left of the match ("left")
+        sequences that must appear at the right of the match ("right")
+        lists of sequences that must appear somewhere in the match ("in")
+        sequences that must constitute the match ("is")
+
+   When we get to the root of the tree, we use one of the longest of its
+   calculated "in" sequences as our answer.
+
+   The sequences calculated for the various types of node (in pseudo ANSI c)
+   are shown below.  "p" is the operand of unary operators (and the left-hand
+   operand of binary operators); "q" is the right-hand operand of binary
+   operators.
+
+   "ZERO" means "a zero-length sequence" below.
+
+        Type	left		right		is		in
+        ----	----		-----		--		--
+        char c	# c		# c		# c		# c
+
+        ANYCHAR	ZERO		ZERO		ZERO		ZERO
+
+        MBCSET	ZERO		ZERO		ZERO		ZERO
+
+        CSET	ZERO		ZERO		ZERO		ZERO
+
+        STAR	ZERO		ZERO		ZERO		ZERO
+
+        QMARK	ZERO		ZERO		ZERO		ZERO
+
+        PLUS	p->left		p->right	ZERO		p->in
+
+        CAT	(p->is==ZERO)?	(q->is==ZERO)?	(p->is!=ZERO &&	p->in plus
+                p->left :	q->right :	q->is!=ZERO) ?	q->in plus
+                p->is##q->left	p->right##q->is	p->is##q->is : p->right##q->left
+                                                ZERO
+
+        OR	longest common	longest common	(do p->is and substrings common
+                leading		trailing	to q->is have same p->in and
+                (sub)sequence	(sub)sequence	q->in length and content) ?
+                of p->left	of p->right
+                and q->left	and q->right	p->is : NULL
+
+   If there's anything else we recognize in the tree, all four sequences get set
+   to zero-length sequences.  If there's something we don't recognize in the
+   tree, we just return a zero-length sequence.
+
+   Break ties in favor of infrequent letters (choosing 'zzz' in preference to
+   'aaa')?
+
+   And ... is it here or someplace that we might ponder "optimizations" such as
+        egrep 'psi|epsilon'	->	egrep 'psi'
+        egrep 'pepsi|epsilon'	->	egrep 'epsi'
+                                        (Yes, we now find "epsi" as a "string
+                                        that must occur", but we might also
+                                        simplify the *entire* r.e. being sought)
+        grep '[c]'		->	grep 'c'
+        grep '(ab|a)b'		->	grep 'ab'
+        grep 'ab*'		->	grep 'a'
+        grep 'a*b'		->	grep 'b'
+
+   There are several issues:
+
+   Is optimization easy (enough)?
+
+   Does optimization actually accomplish anything,
+   or is the automaton you get from "psi|epsilon" (for example)
+   the same as the one you get from "psi" (for example)?
+
+   Are optimizable r.e.'s likely to be used in real-life situations
+   (something like 'ab*' is probably unlikely; something like is
+   'psi|epsilon' is likelier)?  */
+
+static char *
+icatalloc (char *old, char const *new)
+{
+  idx_t newsize = strlen (new);
+  if (newsize == 0)
+    return old;
+  idx_t oldsize = strlen (old);
+  char *result = xirealloc (old, oldsize + newsize + 1);
+  memcpy (result + oldsize, new, newsize + 1);
+  return result;
+}
+
+static void
+freelist (char **cpp)
+{
+  while (*cpp)
+    free (*cpp++);
+}
+
+static char **
+enlistnew (char **cpp, char *new)
+{
+  /* Is there already something in the list that's new (or longer)?  */
+  idx_t i;
+  for (i = 0; cpp[i] != NULL; i++)
+    if (strstr (cpp[i], new) != NULL)
+      {
+        free (new);
+        return cpp;
+      }
+  /* Eliminate any obsoleted strings.  */
+  for (idx_t j = 0; cpp[j] != NULL; )
+    if (strstr (new, cpp[j]) == NULL)
+      ++j;
+    else
+      {
+        free (cpp[j]);
+        if (--i == j)
+          break;
+        cpp[j] = cpp[i];
+        cpp[i] = NULL;
+      }
+  /* Add the new string.  */
+  cpp = xreallocarray (cpp, i + 2, sizeof *cpp);
+  cpp[i] = new;
+  cpp[i + 1] = NULL;
+  return cpp;
+}
+
+static char **
+enlist (char **cpp, char const *str, idx_t len)
+{
+  return enlistnew (cpp, ximemdup0 (str, len));
+}
+
+/* Given pointers to two strings, return a pointer to an allocated
+   list of their distinct common substrings.  */
+static char **
+comsubs (char *left, char const *right)
+{
+  char **cpp = xzalloc (sizeof *cpp);
+
+  for (char *lcp = left; *lcp != '\0'; lcp++)
+    {
+      idx_t len = 0;
+      char *rcp = strchr (right, *lcp);
+      while (rcp != NULL)
+        {
+          idx_t i;
+          for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i)
+            continue;
+          if (i > len)
+            len = i;
+          rcp = strchr (rcp + 1, *lcp);
+        }
+      if (len != 0)
+        cpp = enlist (cpp, lcp, len);
+    }
+  return cpp;
+}
+
+static char **
+addlists (char **old, char **new)
+{
+  for (; *new; new++)
+    old = enlistnew (old, xstrdup (*new));
+  return old;
+}
+
+/* Given two lists of substrings, return a new list giving substrings
+   common to both.  */
+static char **
+inboth (char **left, char **right)
+{
+  char **both = xzalloc (sizeof *both);
+
+  for (idx_t lnum = 0; left[lnum] != NULL; lnum++)
+    {
+      for (idx_t rnum = 0; right[rnum] != NULL; rnum++)
+        {
+          char **temp = comsubs (left[lnum], right[rnum]);
+          both = addlists (both, temp);
+          freelist (temp);
+          free (temp);
+        }
+    }
+  return both;
+}
+
+typedef struct must must;
+
+struct must
+{
+  char **in;
+  char *left;
+  char *right;
+  char *is;
+  bool begline;
+  bool endline;
+  must *prev;
+};
+
+static must *
+allocmust (must *mp, idx_t size)
+{
+  must *new_mp = xmalloc (sizeof *new_mp);
+  new_mp->in = xzalloc (sizeof *new_mp->in);
+  new_mp->left = xizalloc (size);
+  new_mp->right = xizalloc (size);
+  new_mp->is = xizalloc (size);
+  new_mp->begline = false;
+  new_mp->endline = false;
+  new_mp->prev = mp;
+  return new_mp;
+}
+
+static void
+resetmust (must *mp)
+{
+  freelist (mp->in);
+  mp->in[0] = NULL;
+  mp->left[0] = mp->right[0] = mp->is[0] = '\0';
+  mp->begline = false;
+  mp->endline = false;
+}
+
+static void
+freemust (must *mp)
+{
+  freelist (mp->in);
+  free (mp->in);
+  free (mp->left);
+  free (mp->right);
+  free (mp->is);
+  free (mp);
+}
+
+struct dfamust *
+dfamust (struct dfa const *d)
+{
+  must *mp = NULL;
+  char const *result = "";
+  bool exact = false;
+  bool begline = false;
+  bool endline = false;
+  bool need_begline = false;
+  bool need_endline = false;
+  bool case_fold_unibyte = d->syntax.case_fold & !d->localeinfo.multibyte;
+
+  for (idx_t ri = 1; ri + 1 < d->tindex; ri++)
+    {
+      token t = d->tokens[ri];
+      switch (t)
+        {
+        case BEGLINE:
+          mp = allocmust (mp, 2);
+          mp->begline = true;
+          need_begline = true;
+          break;
+        case ENDLINE:
+          mp = allocmust (mp, 2);
+          mp->endline = true;
+          need_endline = true;
+          break;
+        case LPAREN:
+        case RPAREN:
+          assert (!"neither LPAREN nor RPAREN may appear here");
+
+        case EMPTY:
+        case BEGWORD:
+        case ENDWORD:
+        case LIMWORD:
+        case NOTLIMWORD:
+        case BACKREF:
+        case ANYCHAR:
+        case MBCSET:
+          mp = allocmust (mp, 2);
+          break;
+
+        case STAR:
+        case QMARK:
+          assume_nonnull (mp);
+          resetmust (mp);
+          break;
+
+        case OR:
+          {
+            char **new;
+            must *rmp = mp;
+            assume_nonnull (rmp);
+            must *lmp = mp = mp->prev;
+            assume_nonnull (lmp);
+            idx_t j, ln, rn, n;
+
+            /* Guaranteed to be.  Unlikely, but ...  */
+            if (streq (lmp->is, rmp->is))
+              {
+                lmp->begline &= rmp->begline;
+                lmp->endline &= rmp->endline;
+              }
+            else
+              {
+                lmp->is[0] = '\0';
+                lmp->begline = false;
+                lmp->endline = false;
+              }
+            /* Left side--easy */
+            idx_t i = 0;
+            while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
+              ++i;
+            lmp->left[i] = '\0';
+            /* Right side */
+            ln = strlen (lmp->right);
+            rn = strlen (rmp->right);
+            n = ln;
+            if (n > rn)
+              n = rn;
+            for (i = 0; i < n; ++i)
+              if (lmp->right[ln - i - 1] != rmp->right[rn - i - 1])
+                break;
+            for (j = 0; j < i; ++j)
+              lmp->right[j] = lmp->right[(ln - i) + j];
+            lmp->right[j] = '\0';
+            new = inboth (lmp->in, rmp->in);
+            freelist (lmp->in);
+            free (lmp->in);
+            lmp->in = new;
+            freemust (rmp);
+          }
+          break;
+
+        case PLUS:
+          assume_nonnull (mp);
+          mp->is[0] = '\0';
+          break;
+
+        case END:
+          assume_nonnull (mp);
+          assert (!mp->prev);
+          for (idx_t i = 0; mp->in[i] != NULL; i++)
+            if (strlen (mp->in[i]) > strlen (result))
+              result = mp->in[i];
+          if (streq (result, mp->is))
+            {
+              if ((!need_begline || mp->begline) && (!need_endline
+                                                     || mp->endline))
+                exact = true;
+              begline = mp->begline;
+              endline = mp->endline;
+            }
+          goto done;
+
+        case CAT:
+          {
+            must *rmp = mp;
+            assume_nonnull (rmp);
+            must *lmp = mp = mp->prev;
+            assume_nonnull (lmp);
+
+            /* In.  Everything in left, plus everything in
+               right, plus concatenation of
+               left's right and right's left.  */
+            lmp->in = addlists (lmp->in, rmp->in);
+            if (lmp->right[0] != '\0' && rmp->left[0] != '\0')
+              {
+                idx_t lrlen = strlen (lmp->right);
+                idx_t rllen = strlen (rmp->left);
+                char *tp = ximalloc (lrlen + rllen + 1);
+                memcpy (tp + lrlen, rmp->left, rllen + 1);
+                memcpy (tp, lmp->right, lrlen);
+                lmp->in = enlistnew (lmp->in, tp);
+              }
+            /* Left-hand */
+            if (lmp->is[0] != '\0')
+              lmp->left = icatalloc (lmp->left, rmp->left);
+            /* Right-hand */
+            if (rmp->is[0] == '\0')
+              lmp->right[0] = '\0';
+            lmp->right = icatalloc (lmp->right, rmp->right);
+            /* Guaranteed to be */
+            if ((lmp->is[0] != '\0' || lmp->begline)
+                && (rmp->is[0] != '\0' || rmp->endline))
+              {
+                lmp->is = icatalloc (lmp->is, rmp->is);
+                lmp->endline = rmp->endline;
+              }
+            else
+              {
+                lmp->is[0] = '\0';
+                lmp->begline = false;
+                lmp->endline = false;
+              }
+            freemust (rmp);
+          }
+          break;
+
+        case '\0':
+          /* Not on *my* shift.  */
+          goto done;
+
+        default:
+          if (CSET <= t)
+            {
+              /* If T is a singleton, or if case-folding in a unibyte
+                 locale and T's members all case-fold to the same char,
+                 convert T to one of its members.  Otherwise, do
+                 nothing further with T.  */
+              charclass *ccl = &d->charclasses[t - CSET];
+              int j;
+              for (j = 0; j < NOTCHAR; j++)
+                if (tstbit (j, ccl))
+                  break;
+              if (! (j < NOTCHAR))
+                {
+                  mp = allocmust (mp, 2);
+                  break;
+                }
+              t = j;
+              while (++j < NOTCHAR)
+                if (tstbit (j, ccl)
+                    && ! (case_fold_unibyte
+                          && toupper (j) == toupper (t)))
+                  break;
+              if (j < NOTCHAR)
+                {
+                  mp = allocmust (mp, 2);
+                  break;
+                }
+            }
+
+          idx_t rj = ri + 2;
+          if (d->tokens[ri + 1] == CAT)
+            {
+              for (; rj < d->tindex - 1; rj += 2)
+                {
+                  if ((rj != ri && (d->tokens[rj] <= 0
+                                    || NOTCHAR <= d->tokens[rj]))
+                      || d->tokens[rj + 1] != CAT)
+                    break;
+                }
+            }
+          mp = allocmust (mp, ((rj - ri) >> 1) + 1);
+          mp->is[0] = mp->left[0] = mp->right[0]
+            = case_fold_unibyte ? toupper (t) : t;
+
+          idx_t i;
+          for (i = 1; ri + 2 < rj; i++)
+            {
+              ri += 2;
+              t = d->tokens[ri];
+              mp->is[i] = mp->left[i] = mp->right[i]
+                = case_fold_unibyte ? toupper (t) : t;
+            }
+          mp->is[i] = mp->left[i] = mp->right[i] = '\0';
+          mp->in = enlist (mp->in, mp->is, i);
+          break;
+        }
+    }
+ done:;
+
+  struct dfamust *dm = NULL;
+  if (*result)
+    {
+      dm = xmalloc (FLEXSIZEOF (struct dfamust, must, strlen (result) + 1));
+      dm->exact = exact;
+      dm->begline = begline;
+      dm->endline = endline;
+      strcpy (dm->must, result);
+    }
+
+  while (mp)
+    {
+      must *prev = mp->prev;
+      freemust (mp);
+      mp = prev;
+    }
+
+  return dm;
+}
+
+void
+dfamustfree (struct dfamust *dm)
+{
+  free (dm);
+}
+
+struct dfa *
+dfaalloc (void)
+{
+  return xmalloc (sizeof (struct dfa));
+}
+
+/* Initialize DFA.  */
+void
+dfasyntax (struct dfa *dfa, struct localeinfo const *linfo,
+           reg_syntax_t bits, int dfaopts)
+{
+  memset (dfa, 0, offsetof (struct dfa, dfaexec));
+  dfa->dfaexec = linfo->multibyte ? dfaexec_mb : dfaexec_sb;
+  dfa->localeinfo = *linfo;
+
+  dfa->fast = !dfa->localeinfo.multibyte;
+
+  dfa->canychar = -1;
+  dfa->syntax.syntax_bits_set = true;
+  dfa->syntax.case_fold = (bits & RE_ICASE) != 0;
+  dfa->syntax.anchor = (dfaopts & DFA_ANCHOR) != 0;
+  dfa->syntax.eolbyte = dfaopts & DFA_EOL_NUL ? '\0' : '\n';
+  dfa->syntax.syntax_bits = bits;
+
+  for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
+    {
+      unsigned char uc = i;
+
+      dfa->syntax.sbit[uc] = char_context (dfa, uc);
+      switch (dfa->syntax.sbit[uc])
+        {
+        case CTX_LETTER:
+          setbit (uc, &dfa->syntax.letters);
+          break;
+        case CTX_NEWLINE:
+          setbit (uc, &dfa->syntax.newline);
+          break;
+        }
+
+      /* POSIX requires that the five bytes in "\n\r./" (including the
+         terminating NUL) cannot occur inside a multibyte character.  */
+      dfa->syntax.never_trail[uc] = (dfa->localeinfo.using_utf8
+                                     ? (uc & 0xc0) != 0x80
+                                     : strchr ("\n\r./", uc) != NULL);
+    }
+}
+
+/* Initialize TO by copying FROM's syntax settings.  */
+void
+dfacopysyntax (struct dfa *to, struct dfa const *from)
+{
+  memset (to, 0, offsetof (struct dfa, syntax));
+  to->canychar = -1;
+  to->fast = from->fast;
+  to->syntax = from->syntax;
+  to->dfaexec = from->dfaexec;
+  to->localeinfo = from->localeinfo;
+}
+
+/* vim:set shiftwidth=2: */