]> git.saurik.com Git - wxWidgets.git/blobdiff - src/regex/regexec.c
added wsock32.lib (patch 880683)
[wxWidgets.git] / src / regex / regexec.c
index dcb11b285c0cf99c3817394cb1d52199047ec085..dbae952f71298c43bf8a78cb6a7d11d03764aa7b 100644 (file)
 /*
- * the outer shell of regexec()
+ * re_*exec and friends - match REs
  *
- * This file includes engine.c *twice*, after muchos fiddling with the
- * macros that code uses.  This lets the same code operate on two different
- * representations for state sets.
- */
-#include <sys/types.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <limits.h>
-#include <ctype.h>
-#include <regex.h>
-
-#include "utils.h"
-#include "regex2.h"
-
-static int nope = 0;           /* for use in asserts; shuts lint up */
-
-/* macros for manipulating states, small version */
-#define        states  unsigned
-#define        states1 unsigned        /* for later use in regexec() decision */
-#define        CLEAR(v)        ((v) = 0)
-#define        SET0(v, n)      ((v) &= ~((unsigned)1 << (n)))
-#define        SET1(v, n)      ((v) |= (unsigned)1 << (n))
-#define        ISSET(v, n)     ((v) & ((unsigned)1 << (n)))
-#define        ASSIGN(d, s)    ((d) = (s))
-#define        EQ(a, b)        ((a) == (b))
-#define        STATEVARS       int dummy       /* dummy version */
-#define        STATESETUP(m, n)        /* nothing */
-#define        STATETEARDOWN(m)        /* nothing */
-#define        SETUP(v)        ((v) = 0)
-#define        onestate        unsigned
-#define        INIT(o, n)      ((o) = (unsigned)1 << (n))
-#define        INC(o)  ((o) <<= 1)
-#define        ISSTATEIN(v, o) ((v) & (o))
-/* some abbreviations; note that some of these know variable names! */
-/* do "if I'm here, I can also be there" etc without branches */
-#define        FWD(dst, src, n)        ((dst) |= ((unsigned)(src)&(here)) << (n))
-#define        BACK(dst, src, n)       ((dst) |= ((unsigned)(src)&(here)) >> (n))
-#define        ISSETBACK(v, n) ((v) & ((unsigned)here >> (n)))
-/* function names */
-#define SNAMES                 /* engine.c looks after details */
-
-#include "engine.c"
-
-/* now undo things */
-#undef states
-#undef CLEAR
-#undef SET0
-#undef SET1
-#undef ISSET
-#undef ASSIGN
-#undef EQ
-#undef STATEVARS
-#undef STATESETUP
-#undef STATETEARDOWN
-#undef SETUP
-#undef onestate
-#undef INIT
-#undef INC
-#undef ISSTATEIN
-#undef FWD
-#undef BACK
-#undef ISSETBACK
-#undef SNAMES
-
-/* macros for manipulating states, large version */
-#define        states  char *
-#define        CLEAR(v)        memset(v, 0, m->g->nstates)
-#define        SET0(v, n)      ((v)[n] = 0)
-#define        SET1(v, n)      ((v)[n] = 1)
-#define        ISSET(v, n)     ((v)[n])
-#define        ASSIGN(d, s)    memcpy(d, s, m->g->nstates)
-#define        EQ(a, b)        (memcmp(a, b, m->g->nstates) == 0)
-#define        STATEVARS       int vn; char *space
-#define        STATESETUP(m, nv)       { (m)->space = malloc((nv)*(m)->g->nstates); \
-                               if ((m)->space == NULL) return(REG_ESPACE); \
-                               (m)->vn = 0; }
-#define        STATETEARDOWN(m)        { free((m)->space); }
-#define        SETUP(v)        ((v) = &m->space[m->vn++ * m->g->nstates])
-#define        onestate        int
-#define        INIT(o, n)      ((o) = (n))
-#define        INC(o)  ((o)++)
-#define        ISSTATEIN(v, o) ((v)[o])
-/* some abbreviations; note that some of these know variable names! */
-/* do "if I'm here, I can also be there" etc without branches */
-#define        FWD(dst, src, n)        ((dst)[here+(n)] |= (src)[here])
-#define        BACK(dst, src, n)       ((dst)[here-(n)] |= (src)[here])
-#define        ISSETBACK(v, n) ((v)[here - (n)])
-/* function names */
-#define        LNAMES                  /* flag */
-
-#include "engine.c"
-
-/*
- - regexec - interface for matching
- = extern int regexec(const regex_t *, const char *, size_t, \
- =                                     regmatch_t [], int);
- = #define     REG_NOTBOL      00001
- = #define     REG_NOTEOL      00002
- = #define     REG_STARTEND    00004
- = #define     REG_TRACE       00400   // tracing of execution
- = #define     REG_LARGE       01000   // force large representation
- = #define     REG_BACKR       02000   // force use of backref code
+ * Copyright (c) 1998, 1999 Henry Spencer.     All rights reserved.
  *
- * We put this here so we can exploit knowledge of the state representation
- * when choosing which matcher to call.  Also, by this point the matchers
- * have been prototyped.
- */
-int                            /* 0 success, REG_NOMATCH failure */
-regexec(preg, string, nmatch, pmatch, eflags)
-const regex_t *preg;
-const char *string;
-size_t nmatch;
-regmatch_t pmatch[];
-int eflags;
-{
-       register struct re_guts *g = preg->re_g;
-#ifdef REDEBUG
-#      define  GOODFLAGS(f)    (f)
-#else
-#      define  GOODFLAGS(f)    ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
-#endif
-
-       if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
-               return(REG_BADPAT);
-       assert(!(g->iflags&BAD));
-       if (g->iflags&BAD)              /* backstop for no-debug case */
-               return(REG_BADPAT);
-       eflags = GOODFLAGS(eflags);
-
-       if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags&REG_LARGE))
-               return(smatcher(g, (char *)string, nmatch, pmatch, eflags));
+ * Development of this software was funded, in part, by Cray Research Inc.,
+ * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
+ * Corporation, none of whom are responsible for the results.  The author
+ * thanks all of them.
+ *
+ * Redistribution and use in source and binary forms -- with or without
+ * modification -- are permitted for any purpose, provided that
+ * redistributions in source form retain this entire copyright notice and
+ * indicate the origin and nature of any modifications.
+ *
+ * I'd appreciate being given credit for this package in the documentation
+ * of software which uses it, but that is not a requirement.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
+ * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+ * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * $Header: /projects/cvsroot/pgsql-server/src/backend/regex/regexec.c,v 1.23 2003/08/08 21:41:56 momjian Exp $
+ *
+ */
+
+#include "regguts.h"
+
+
+
+/* lazy-DFA representation */
+struct arcp
+{                                                              /* "pointer" to an outarc */
+       struct sset *ss;
+       color           co;
+};
+
+struct sset
+{                                                              /* state set */
+       unsigned   *states;                     /* pointer to bitvector */
+       unsigned        hash;                   /* hash of bitvector */
+#define  HASH(bv, nw)   (((nw) == 1) ? *(bv) : hash(bv, nw))
+#define  HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
+               memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
+       int                     flags;
+#define  STARTER        01                     /* the initial state set */
+#define  POSTSTATE      02                     /* includes the goal state */
+#define  LOCKED                 04                     /* locked in cache */
+#define  NOPROGRESS  010               /* zero-progress state set */
+       struct arcp ins;                        /* chain of inarcs pointing here */
+       chr                *lastseen;           /* last entered on arrival here */
+       struct sset **outs;                     /* outarc vector indexed by color */
+       struct arcp *inchain;           /* chain-pointer vector for outarcs */
+};
+
+struct dfa
+{
+       int                     nssets;                 /* size of cache */
+       int                     nssused;                /* how many entries occupied yet */
+       int                     nstates;                /* number of states */
+       int                     ncolors;                /* length of outarc and inchain vectors */
+       int                     wordsper;               /* length of state-set bitvectors */
+       struct sset *ssets;                     /* state-set cache */
+       unsigned   *statesarea;         /* bitvector storage */
+       unsigned   *work;                       /* pointer to work area within statesarea */
+       struct sset **outsarea;         /* outarc-vector storage */
+       struct arcp *incarea;           /* inchain storage */
+       struct cnfa *cnfa;
+       struct colormap *cm;
+       chr                *lastpost;           /* location of last cache-flushed success */
+       chr                *lastnopr;           /* location of last cache-flushed
+                                                                * NOPROGRESS */
+       struct sset *search;            /* replacement-search-pointer memory */
+       int                     cptsmalloced;   /* were the areas individually malloced? */
+       char       *mallocarea;         /* self, or master malloced area, or NULL */
+};
+
+#define WORK   1                               /* number of work bitvectors needed */
+
+/* setup for non-malloc allocation for small cases */
+#define FEWSTATES      20                      /* must be less than UBITS */
+#define FEWCOLORS      15
+struct smalldfa
+{
+       struct dfa      dfa;
+       struct sset ssets[FEWSTATES * 2];
+       unsigned        statesarea[FEWSTATES * 2 + WORK];
+       struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
+       struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
+};
+
+#define DOMALLOC       ((struct smalldfa *)NULL)       /* force malloc */
+
+
+
+/* internal variables, bundled for easy passing around */
+struct vars
+{
+       regex_t    *re;
+       struct guts *g;
+       int                     eflags;                 /* copies of arguments */
+       size_t          nmatch;
+       regmatch_t *pmatch;
+       rm_detail_t *details;
+       chr                *start;                      /* start of string */
+       chr                *stop;                       /* just past end of string */
+       int                     err;                    /* error code if any (0 none) */
+       regoff_t   *mem;                        /* memory vector for backtracking */
+       struct smalldfa dfa1;
+       struct smalldfa dfa2;
+};
+
+#define VISERR(vv)     ((vv)->err != 0)        /* have we seen an error yet? */
+#define ISERR() VISERR(v)
+#define VERR(vv,e)     (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
+#define ERR(e) VERR(v, e)              /* record an error */
+#define NOERR() {if (ISERR()) return v->err;}  /* if error seen, return
+                                                                                                * it */
+#define OFF(p) ((p) - v->start)
+#define LOFF(p) ((long)OFF(p))
+
+
+
+/*
+ * forward declarations
+ */
+/* === regexec.c === */
+static int     find(struct vars *, struct cnfa *, struct colormap *);
+static int     cfind(struct vars *, struct cnfa *, struct colormap *);
+static int     cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
+static void zapsubs(regmatch_t *, size_t);
+static void zapmem(struct vars *, struct subre *);
+static void subset(struct vars *, struct subre *, chr *, chr *);
+static int     dissect(struct vars *, struct subre *, chr *, chr *);
+static int     condissect(struct vars *, struct subre *, chr *, chr *);
+static int     altdissect(struct vars *, struct subre *, chr *, chr *);
+static int     cdissect(struct vars *, struct subre *, chr *, chr *);
+static int     ccondissect(struct vars *, struct subre *, chr *, chr *);
+static int     crevdissect(struct vars *, struct subre *, chr *, chr *);
+static int     cbrdissect(struct vars *, struct subre *, chr *, chr *);
+static int     caltdissect(struct vars *, struct subre *, chr *, chr *);
+
+/* === rege_dfa.c === */
+static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
+static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
+static chr *lastcold(struct vars *, struct dfa *);
+static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
+static void freedfa(struct dfa *);
+static unsigned hash(unsigned *, int);
+static struct sset *initialize(struct vars *, struct dfa *, chr *);
+static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *);
+static int     lacon(struct vars *, struct cnfa *, chr *, pcolor);
+static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
+static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
+
+
+/*
+ * regexec - match regular expression
+ */
+int
+regexec(regex_t *re,
+                  const chr *string,
+                  size_t nmatch,
+                  regmatch_t pmatch[],
+                  int flags)
+{
+       rm_detail_t det;
+    return wx_regexec(re, string, wx_strlen(string), &det, nmatch, pmatch, flags);
+}
+int
+wx_regexec(regex_t *re,
+                  const chr *string,
+                  size_t len,
+                  rm_detail_t *details,
+                  size_t nmatch,
+                  regmatch_t pmatch[],
+                  int flags)
+{
+       struct vars var;
+       register struct vars *v = &var;
+       int                     st;
+       size_t          n;
+       int                     backref;
+
+#define  LOCALMAT       20
+       regmatch_t      mat[LOCALMAT];
+
+#define  LOCALMEM       40
+       regoff_t        mem[LOCALMEM];
+
+       /* sanity checks */
+       if (re == NULL || string == NULL || re->re_magic != REMAGIC)
+               return REG_INVARG;
+       if (re->re_csize != sizeof(chr))
+               return REG_MIXED;
+
+       /* setup */
+       v->re = re;
+       v->g = (struct guts *) re->re_guts;
+       if ((v->g->cflags & REG_EXPECT) && details == NULL)
+               return REG_INVARG;
+       if (v->g->info & REG_UIMPOSSIBLE)
+               return REG_NOMATCH;
+       backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
+       v->eflags = flags;
+       if (v->g->cflags & REG_NOSUB)
+               nmatch = 0;                             /* override client */
+       v->nmatch = nmatch;
+       if (backref)
+       {
+               /* need work area */
+               if (v->g->nsub + 1 <= LOCALMAT)
+                       v->pmatch = mat;
+               else
+                       v->pmatch = (regmatch_t *) MALLOC((v->g->nsub + 1) *
+                                                                                         sizeof(regmatch_t));
+               if (v->pmatch == NULL)
+                       return REG_ESPACE;
+               v->nmatch = v->g->nsub + 1;
+       }
+       else
+               v->pmatch = pmatch;
+       v->details = details;
+       v->start = (chr *) string;
+       v->stop = (chr *) string + len;
+       v->err = 0;
+       if (backref)
+       {
+               /* need retry memory */
+               assert(v->g->ntree >= 0);
+               n = (size_t) v->g->ntree;
+               if (n <= LOCALMEM)
+                       v->mem = mem;
+               else
+                       v->mem = (regoff_t *) MALLOC(n * sizeof(regoff_t));
+               if (v->mem == NULL)
+               {
+                       if (v->pmatch != pmatch && v->pmatch != mat)
+                               FREE(v->pmatch);
+                       return REG_ESPACE;
+               }
+       }
        else
-               return(lmatcher(g, (char *)string, nmatch, pmatch, eflags));
+               v->mem = NULL;
+
+       /* do it */
+       assert(v->g->tree != NULL);
+       if (backref)
+               st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
+       else
+               st = find(v, &v->g->tree->cnfa, &v->g->cmap);
+
+       /* copy (portion of) match vector over if necessary */
+       if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0)
+       {
+               zapsubs(pmatch, nmatch);
+               n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
+               memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t));
+       }
+
+       /* clean up */
+       if (v->pmatch != pmatch && v->pmatch != mat)
+               FREE(v->pmatch);
+       if (v->mem != NULL && v->mem != mem)
+               FREE(v->mem);
+       return st;
+}
+
+/*
+ * find - find a match for the main NFA (no-complications case)
+ */
+static int
+find(struct vars * v,
+        struct cnfa * cnfa,
+        struct colormap * cm)
+{
+       struct dfa *s;
+       struct dfa *d;
+       chr                *begin;
+       chr                *end = NULL;
+       chr                *cold;
+       chr                *open;                       /* open and close of range of possible
+                                                                * starts */
+       chr                *close;
+       int                     hitend;
+       int                     shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;
+
+       /* first, a shot with the search RE */
+       s = newdfa(v, &v->g->search, cm, &v->dfa1);
+       assert(!(ISERR() && s != NULL));
+       NOERR();
+       MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
+       cold = NULL;
+       close = shortest(v, s, v->start, v->start, v->stop, &cold, (int *) NULL);
+       freedfa(s);
+       NOERR();
+       if (v->g->cflags & REG_EXPECT)
+       {
+               assert(v->details != NULL);
+               if (cold != NULL)
+                       v->details->rm_extend.rm_so = OFF(cold);
+               else
+                       v->details->rm_extend.rm_so = OFF(v->stop);
+               v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
+       }
+       if (close == NULL)                      /* not found */
+               return REG_NOMATCH;
+       if (v->nmatch == 0)                     /* found, don't need exact location */
+               return REG_OKAY;
+
+       /* find starting point and match */
+       assert(cold != NULL);
+       open = cold;
+       cold = NULL;
+       MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
+       d = newdfa(v, cnfa, cm, &v->dfa1);
+       assert(!(ISERR() && d != NULL));
+       NOERR();
+       for (begin = open; begin <= close; begin++)
+       {
+               MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
+               if (shorter)
+                       end = shortest(v, d, begin, begin, v->stop,
+                                                  (chr **) NULL, &hitend);
+               else
+                       end = longest(v, d, begin, v->stop, &hitend);
+               NOERR();
+               if (hitend && cold == NULL)
+                       cold = begin;
+               if (end != NULL)
+                       break;                          /* NOTE BREAK OUT */
+       }
+       assert(end != NULL);            /* search RE succeeded so loop should */
+       freedfa(d);
+
+       /* and pin down details */
+       assert(v->nmatch > 0);
+       v->pmatch[0].rm_so = OFF(begin);
+       v->pmatch[0].rm_eo = OFF(end);
+       if (v->g->cflags & REG_EXPECT)
+       {
+               if (cold != NULL)
+                       v->details->rm_extend.rm_so = OFF(cold);
+               else
+                       v->details->rm_extend.rm_so = OFF(v->stop);
+               v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
+       }
+       if (v->nmatch == 1)                     /* no need for submatches */
+               return REG_OKAY;
+
+       /* submatches */
+       zapsubs(v->pmatch, v->nmatch);
+       return dissect(v, v->g->tree, begin, end);
+}
+
+/*
+ * cfind - find a match for the main NFA (with complications)
+ */
+static int
+cfind(struct vars * v,
+         struct cnfa * cnfa,
+         struct colormap * cm)
+{
+       struct dfa *s;
+       struct dfa *d;
+       chr                *cold;
+       int                     ret;
+
+       s = newdfa(v, &v->g->search, cm, &v->dfa1);
+       NOERR();
+       d = newdfa(v, cnfa, cm, &v->dfa2);
+       if (ISERR())
+       {
+               assert(d == NULL);
+               freedfa(s);
+               return v->err;
+       }
+
+       ret = cfindloop(v, cnfa, cm, d, s, &cold);
+
+       freedfa(d);
+       freedfa(s);
+       NOERR();
+       if (v->g->cflags & REG_EXPECT)
+       {
+               assert(v->details != NULL);
+               if (cold != NULL)
+                       v->details->rm_extend.rm_so = OFF(cold);
+               else
+                       v->details->rm_extend.rm_so = OFF(v->stop);
+               v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
+       }
+       return ret;
 }
+
+/*
+ * cfindloop - the heart of cfind
+ */
+static int
+cfindloop(struct vars * v,
+                 struct cnfa * cnfa,
+                 struct colormap * cm,
+                 struct dfa * d,
+                 struct dfa * s,
+                 chr **coldp)                  /* where to put coldstart pointer */
+{
+       chr                *begin;
+       chr                *end;
+       chr                *cold;
+       chr                *open;                       /* open and close of range of possible
+                                                                * starts */
+       chr                *close;
+       chr                *estart;
+       chr                *estop;
+       int                     er;
+       int                     shorter = v->g->tree->flags & SHORTER;
+       int                     hitend;
+
+       assert(d != NULL && s != NULL);
+       cold = NULL;
+       close = v->start;
+       do
+       {
+               MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
+               close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
+               if (close == NULL)
+                       break;                          /* NOTE BREAK */
+               assert(cold != NULL);
+               open = cold;
+               cold = NULL;
+               MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
+               for (begin = open; begin <= close; begin++)
+               {
+                       MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
+                       estart = begin;
+                       estop = v->stop;
+                       for (;;)
+                       {
+                               if (shorter)
+                                       end = shortest(v, d, begin, estart,
+                                                                  estop, (chr **) NULL, &hitend);
+                               else
+                                       end = longest(v, d, begin, estop,
+                                                                 &hitend);
+                               if (hitend && cold == NULL)
+                                       cold = begin;
+                               if (end == NULL)
+                                       break;          /* NOTE BREAK OUT */
+                               MDEBUG(("tentative end %ld\n", LOFF(end)));
+                               zapsubs(v->pmatch, v->nmatch);
+                               zapmem(v, v->g->tree);
+                               er = cdissect(v, v->g->tree, begin, end);
+                               if (er == REG_OKAY)
+                               {
+                                       if (v->nmatch > 0)
+                                       {
+                                               v->pmatch[0].rm_so = OFF(begin);
+                                               v->pmatch[0].rm_eo = OFF(end);
+                                       }
+                                       *coldp = cold;
+                                       return REG_OKAY;
+                               }
+                               if (er != REG_NOMATCH)
+                               {
+                                       ERR(er);
+                                       return er;
+                               }
+                               if ((shorter) ? end == estop : end == begin)
+                               {
+                                       /* no point in trying again */
+                                       *coldp = cold;
+                                       return REG_NOMATCH;
+                               }
+                               /* go around and try again */
+                               if (shorter)
+                                       estart = end + 1;
+                               else
+                                       estop = end - 1;
+                       }
+               }
+       } while (close < v->stop);
+
+       *coldp = cold;
+       return REG_NOMATCH;
+}
+
+/*
+ * zapsubs - initialize the subexpression matches to "no match"
+ */
+static void
+zapsubs(regmatch_t *p,
+               size_t n)
+{
+       size_t          i;
+
+       for (i = n - 1; i > 0; i--)
+       {
+               p[i].rm_so = -1;
+               p[i].rm_eo = -1;
+       }
+}
+
+/*
+ * zapmem - initialize the retry memory of a subtree to zeros
+ */
+static void
+zapmem(struct vars * v,
+          struct subre * t)
+{
+       if (t == NULL)
+               return;
+
+       assert(v->mem != NULL);
+       v->mem[t->retry] = 0;
+       if (t->op == '(')
+       {
+               assert(t->subno > 0);
+               v->pmatch[t->subno].rm_so = -1;
+               v->pmatch[t->subno].rm_eo = -1;
+       }
+
+       if (t->left != NULL)
+               zapmem(v, t->left);
+       if (t->right != NULL)
+               zapmem(v, t->right);
+}
+
+/*
+ * subset - set any subexpression relevant to a successful subre
+ */
+static void
+subset(struct vars * v,
+          struct subre * sub,
+          chr *begin,
+          chr *end)
+{
+       int                     n = sub->subno;
+
+       assert(n > 0);
+       if ((size_t) n >= v->nmatch)
+               return;
+
+       MDEBUG(("setting %d\n", n));
+       v->pmatch[n].rm_so = OFF(begin);
+       v->pmatch[n].rm_eo = OFF(end);
+}
+
+/*
+ * dissect - determine subexpression matches (uncomplicated case)
+ */
+static int                                             /* regexec return code */
+dissect(struct vars * v,
+               struct subre * t,
+               chr *begin,                             /* beginning of relevant substring */
+               chr *end)                               /* end of same */
+{
+       assert(t != NULL);
+       MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
+
+       switch (t->op)
+       {
+               case '=':                               /* terminal node */
+                       assert(t->left == NULL && t->right == NULL);
+                       return REG_OKAY;        /* no action, parent did the work */
+                       break;
+               case '|':                               /* alternation */
+                       assert(t->left != NULL);
+                       return altdissect(v, t, begin, end);
+                       break;
+               case 'b':                               /* back ref -- shouldn't be calling us! */
+                       return REG_ASSERT;
+                       break;
+               case '.':                               /* concatenation */
+                       assert(t->left != NULL && t->right != NULL);
+                       return condissect(v, t, begin, end);
+                       break;
+               case '(':                               /* capturing */
+                       assert(t->left != NULL && t->right == NULL);
+                       assert(t->subno > 0);
+                       subset(v, t, begin, end);
+                       return dissect(v, t->left, begin, end);
+                       break;
+               default:
+                       return REG_ASSERT;
+                       break;
+       }
+}
+
+/*
+ * condissect - determine concatenation subexpression matches (uncomplicated)
+ */
+static int                                             /* regexec return code */
+condissect(struct vars * v,
+                  struct subre * t,
+                  chr *begin,                  /* beginning of relevant substring */
+                  chr *end)                    /* end of same */
+{
+       struct dfa *d;
+       struct dfa *d2;
+       chr                *mid;
+       int                     i;
+       int                     shorter = (t->left->flags & SHORTER) ? 1 : 0;
+       chr                *stop = (shorter) ? end : begin;
+
+       assert(t->op == '.');
+       assert(t->left != NULL && t->left->cnfa.nstates > 0);
+       assert(t->right != NULL && t->right->cnfa.nstates > 0);
+
+       d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
+       NOERR();
+       d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
+       if (ISERR())
+       {
+               assert(d2 == NULL);
+               freedfa(d);
+               return v->err;
+       }
+
+       /* pick a tentative midpoint */
+       if (shorter)
+               mid = shortest(v, d, begin, begin, end, (chr **) NULL,
+                                          (int *) NULL);
+       else
+               mid = longest(v, d, begin, end, (int *) NULL);
+       if (mid == NULL)
+       {
+               freedfa(d);
+               freedfa(d2);
+               return REG_ASSERT;
+       }
+       MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
+
+       /* iterate until satisfaction or failure */
+       while (longest(v, d2, mid, end, (int *) NULL) != end)
+       {
+               /* that midpoint didn't work, find a new one */
+               if (mid == stop)
+               {
+                       /* all possibilities exhausted! */
+                       MDEBUG(("no midpoint!\n"));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_ASSERT;
+               }
+               if (shorter)
+                       mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL,
+                                                  (int *) NULL);
+               else
+                       mid = longest(v, d, begin, mid - 1, (int *) NULL);
+               if (mid == NULL)
+               {
+                       /* failed to find a new one! */
+                       MDEBUG(("failed midpoint!\n"));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_ASSERT;
+               }
+               MDEBUG(("new midpoint %ld\n", LOFF(mid)));
+       }
+
+       /* satisfaction */
+       MDEBUG(("successful\n"));
+       freedfa(d);
+       freedfa(d2);
+       i = dissect(v, t->left, begin, mid);
+       if (i != REG_OKAY)
+               return i;
+       return dissect(v, t->right, mid, end);
+}
+
+/*
+ * altdissect - determine alternative subexpression matches (uncomplicated)
+ */
+static int                                             /* regexec return code */
+altdissect(struct vars * v,
+                  struct subre * t,
+                  chr *begin,                  /* beginning of relevant substring */
+                  chr *end)                    /* end of same */
+{
+       struct dfa *d;
+       int                     i;
+
+       assert(t != NULL);
+       assert(t->op == '|');
+
+       for (i = 0; t != NULL; t = t->right, i++)
+       {
+               MDEBUG(("trying %dth\n", i));
+               assert(t->left != NULL && t->left->cnfa.nstates > 0);
+               d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
+               if (ISERR())
+                       return v->err;
+               if (longest(v, d, begin, end, (int *) NULL) == end)
+               {
+                       MDEBUG(("success\n"));
+                       freedfa(d);
+                       return dissect(v, t->left, begin, end);
+               }
+               freedfa(d);
+       }
+       return REG_ASSERT;                      /* none of them matched?!? */
+}
+
+/*
+ * cdissect - determine subexpression matches (with complications)
+ * The retry memory stores the offset of the trial midpoint from begin,
+ * plus 1 so that 0 uniquely means "clean slate".
+ */
+static int                                             /* regexec return code */
+cdissect(struct vars * v,
+                struct subre * t,
+                chr *begin,                    /* beginning of relevant substring */
+                chr *end)                              /* end of same */
+{
+       int                     er;
+
+       assert(t != NULL);
+       MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
+
+       switch (t->op)
+       {
+               case '=':                               /* terminal node */
+                       assert(t->left == NULL && t->right == NULL);
+                       return REG_OKAY;        /* no action, parent did the work */
+                       break;
+               case '|':                               /* alternation */
+                       assert(t->left != NULL);
+                       return caltdissect(v, t, begin, end);
+                       break;
+               case 'b':                               /* back ref -- shouldn't be calling us! */
+                       assert(t->left == NULL && t->right == NULL);
+                       return cbrdissect(v, t, begin, end);
+                       break;
+               case '.':                               /* concatenation */
+                       assert(t->left != NULL && t->right != NULL);
+                       return ccondissect(v, t, begin, end);
+                       break;
+               case '(':                               /* capturing */
+                       assert(t->left != NULL && t->right == NULL);
+                       assert(t->subno > 0);
+                       er = cdissect(v, t->left, begin, end);
+                       if (er == REG_OKAY)
+                               subset(v, t, begin, end);
+                       return er;
+                       break;
+               default:
+                       return REG_ASSERT;
+                       break;
+       }
+}
+
+/*
+ * ccondissect - concatenation subexpression matches (with complications)
+ * The retry memory stores the offset of the trial midpoint from begin,
+ * plus 1 so that 0 uniquely means "clean slate".
+ */
+static int                                             /* regexec return code */
+ccondissect(struct vars * v,
+                       struct subre * t,
+                       chr *begin,                     /* beginning of relevant substring */
+                       chr *end)                       /* end of same */
+{
+       struct dfa *d;
+       struct dfa *d2;
+       chr                *mid;
+       int                     er;
+
+       assert(t->op == '.');
+       assert(t->left != NULL && t->left->cnfa.nstates > 0);
+       assert(t->right != NULL && t->right->cnfa.nstates > 0);
+
+       if (t->left->flags & SHORTER)           /* reverse scan */
+               return crevdissect(v, t, begin, end);
+
+       d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+       if (ISERR())
+               return v->err;
+       d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
+       if (ISERR())
+       {
+               freedfa(d);
+               return v->err;
+       }
+       MDEBUG(("cconcat %d\n", t->retry));
+
+       /* pick a tentative midpoint */
+       if (v->mem[t->retry] == 0)
+       {
+               mid = longest(v, d, begin, end, (int *) NULL);
+               if (mid == NULL)
+               {
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
+               v->mem[t->retry] = (mid - begin) + 1;
+       }
+       else
+       {
+               mid = begin + (v->mem[t->retry] - 1);
+               MDEBUG(("working midpoint %ld\n", LOFF(mid)));
+       }
+
+       /* iterate until satisfaction or failure */
+       for (;;)
+       {
+               /* try this midpoint on for size */
+               er = cdissect(v, t->left, begin, mid);
+               if (er == REG_OKAY &&
+                       longest(v, d2, mid, end, (int *) NULL) == end &&
+                       (er = cdissect(v, t->right, mid, end)) ==
+                       REG_OKAY)
+                       break;                          /* NOTE BREAK OUT */
+               if (er != REG_OKAY && er != REG_NOMATCH)
+               {
+                       freedfa(d);
+                       freedfa(d2);
+                       return er;
+               }
+
+               /* that midpoint didn't work, find a new one */
+               if (mid == begin)
+               {
+                       /* all possibilities exhausted */
+                       MDEBUG(("%d no midpoint\n", t->retry));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               mid = longest(v, d, begin, mid - 1, (int *) NULL);
+               if (mid == NULL)
+               {
+                       /* failed to find a new one */
+                       MDEBUG(("%d failed midpoint\n", t->retry));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
+               v->mem[t->retry] = (mid - begin) + 1;
+               zapmem(v, t->left);
+               zapmem(v, t->right);
+       }
+
+       /* satisfaction */
+       MDEBUG(("successful\n"));
+       freedfa(d);
+       freedfa(d2);
+       return REG_OKAY;
+}
+
+/*
+ * crevdissect - determine backref shortest-first subexpression matches
+ * The retry memory stores the offset of the trial midpoint from begin,
+ * plus 1 so that 0 uniquely means "clean slate".
+ */
+static int                                             /* regexec return code */
+crevdissect(struct vars * v,
+                       struct subre * t,
+                       chr *begin,                     /* beginning of relevant substring */
+                       chr *end)                       /* end of same */
+{
+       struct dfa *d;
+       struct dfa *d2;
+       chr                *mid;
+       int                     er;
+
+       assert(t->op == '.');
+       assert(t->left != NULL && t->left->cnfa.nstates > 0);
+       assert(t->right != NULL && t->right->cnfa.nstates > 0);
+       assert(t->left->flags & SHORTER);
+
+       /* concatenation -- need to split the substring between parts */
+       d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+       if (ISERR())
+               return v->err;
+       d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
+       if (ISERR())
+       {
+               freedfa(d);
+               return v->err;
+       }
+       MDEBUG(("crev %d\n", t->retry));
+
+       /* pick a tentative midpoint */
+       if (v->mem[t->retry] == 0)
+       {
+               mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
+               if (mid == NULL)
+               {
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
+               v->mem[t->retry] = (mid - begin) + 1;
+       }
+       else
+       {
+               mid = begin + (v->mem[t->retry] - 1);
+               MDEBUG(("working midpoint %ld\n", LOFF(mid)));
+       }
+
+       /* iterate until satisfaction or failure */
+       for (;;)
+       {
+               /* try this midpoint on for size */
+               er = cdissect(v, t->left, begin, mid);
+               if (er == REG_OKAY &&
+                       longest(v, d2, mid, end, (int *) NULL) == end &&
+                       (er = cdissect(v, t->right, mid, end)) ==
+                       REG_OKAY)
+                       break;                          /* NOTE BREAK OUT */
+               if (er != REG_OKAY && er != REG_NOMATCH)
+               {
+                       freedfa(d);
+                       freedfa(d2);
+                       return er;
+               }
+
+               /* that midpoint didn't work, find a new one */
+               if (mid == end)
+               {
+                       /* all possibilities exhausted */
+                       MDEBUG(("%d no midpoint\n", t->retry));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
+               if (mid == NULL)
+               {
+                       /* failed to find a new one */
+                       MDEBUG(("%d failed midpoint\n", t->retry));
+                       freedfa(d);
+                       freedfa(d2);
+                       return REG_NOMATCH;
+               }
+               MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
+               v->mem[t->retry] = (mid - begin) + 1;
+               zapmem(v, t->left);
+               zapmem(v, t->right);
+       }
+
+       /* satisfaction */
+       MDEBUG(("successful\n"));
+       freedfa(d);
+       freedfa(d2);
+       return REG_OKAY;
+}
+
+/*
+ * cbrdissect - determine backref subexpression matches
+ */
+static int                                             /* regexec return code */
+cbrdissect(struct vars * v,
+                  struct subre * t,
+                  chr *begin,                  /* beginning of relevant substring */
+                  chr *end)                    /* end of same */
+{
+       int                     i;
+       int                     n = t->subno;
+       size_t          len;
+       chr                *paren;
+       chr                *p;
+       chr                *stop;
+       int                     min = t->min;
+       int                     max = t->max;
+
+       assert(t != NULL);
+       assert(t->op == 'b');
+       assert(n >= 0);
+       assert((size_t) n < v->nmatch);
+
+       MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
+
+       if (v->pmatch[n].rm_so == -1)
+               return REG_NOMATCH;
+       paren = v->start + v->pmatch[n].rm_so;
+       len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
+
+       /* no room to maneuver -- retries are pointless */
+       if (v->mem[t->retry])
+               return REG_NOMATCH;
+       v->mem[t->retry] = 1;
+
+       /* special-case zero-length string */
+       if (len == 0)
+       {
+               if (begin == end)
+                       return REG_OKAY;
+               return REG_NOMATCH;
+       }
+
+       /* and too-short string */
+       assert(end >= begin);
+       if ((size_t) (end - begin) < len)
+               return REG_NOMATCH;
+       stop = end - len;
+
+       /* count occurrences */
+       i = 0;
+       for (p = begin; p <= stop && (i < max || max == INFINITY); p += len)
+       {
+               if ((*v->g->compare) (paren, p, len) != 0)
+                       break;
+               i++;
+       }
+       MDEBUG(("cbackref found %d\n", i));
+
+       /* and sort it out */
+       if (p != end)                           /* didn't consume all of it */
+               return REG_NOMATCH;
+       if (min <= i && (i <= max || max == INFINITY))
+               return REG_OKAY;
+       return REG_NOMATCH;                     /* out of range */
+}
+
+/*
+ * caltdissect - determine alternative subexpression matches (w. complications)
+ */
+static int                                             /* regexec return code */
+caltdissect(struct vars * v,
+                       struct subre * t,
+                       chr *begin,                     /* beginning of relevant substring */
+                       chr *end)                       /* end of same */
+{
+       struct dfa *d;
+       int                     er;
+
+#define  UNTRIED 0                             /* not yet tried at all */
+#define  TRYING  1                             /* top matched, trying submatches */
+#define  TRIED  2                              /* top didn't match or submatches
+                                                                * exhausted */
+
+       if (t == NULL)
+               return REG_NOMATCH;
+       assert(t->op == '|');
+       if (v->mem[t->retry] == TRIED)
+               return caltdissect(v, t->right, begin, end);
+
+       MDEBUG(("calt n%d\n", t->retry));
+       assert(t->left != NULL);
+
+       if (v->mem[t->retry] == UNTRIED)
+       {
+               d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+               if (ISERR())
+                       return v->err;
+               if (longest(v, d, begin, end, (int *) NULL) != end)
+               {
+                       freedfa(d);
+                       v->mem[t->retry] = TRIED;
+                       return caltdissect(v, t->right, begin, end);
+               }
+               freedfa(d);
+               MDEBUG(("calt matched\n"));
+               v->mem[t->retry] = TRYING;
+       }
+
+       er = cdissect(v, t->left, begin, end);
+       if (er != REG_NOMATCH)
+               return er;
+
+       v->mem[t->retry] = TRIED;
+       return caltdissect(v, t->right, begin, end);
+}
+
+
+
+#include "rege_dfa.c"