/src/postgres/src/backend/regex/regexec.c

Source
/*
 * re_*exec and friends - match REs
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * 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.
 *
 * src/backend/regex/regexec.c
 *
 */

#include "regex/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     backno;     /* if DFA for a backref, subno it refers to */
  short   backmin;    /* min repetitions for backref */
  short   backmax;    /* max repetitions for backref */
  bool    ismalloced;   /* should this struct dfa be freed? */
  bool    arraysmalloced; /* should its subsidiary arrays be freed? */
};

#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;      /* must be first */
  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      *search_start; /* search start of string */
  chr      *stop;     /* just past end of string */
  int     err;      /* error code if any (0 none) */
  struct dfa **subdfas;   /* per-tree-subre DFAs */
  struct dfa **ladfas;    /* per-lacon-subre DFAs */
  struct sset **lblastcss;  /* per-lacon-subre lookbehind restart data */
  chr     **lblastcp;   /* per-lacon-subre lookbehind restart data */
  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 struct dfa *getsubdfa(struct vars *v, struct subre *t);
static struct dfa *getladfa(struct vars *v, int n);
static int  find(struct vars *v, struct cnfa *cnfa, struct colormap *cm);
static int  cfind(struct vars *v, struct cnfa *cnfa, struct colormap *cm);
static int  cfindloop(struct vars *v, struct cnfa *cnfa, struct colormap *cm,
            struct dfa *d, struct dfa *s, chr **coldp);
static void zapallsubs(regmatch_t *p, size_t n);
static void zaptreesubs(struct vars *v, struct subre *t);
static void subset(struct vars *v, struct subre *sub, chr *begin, chr *end);
static int  cdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  ccondissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  crevcondissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  cbrdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  caltdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  citerdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
static int  creviterdissect(struct vars *v, struct subre *t, chr *begin, chr *end);

/* === rege_dfa.c === */
static chr *longest(struct vars *v, struct dfa *d,
          chr *start, chr *stop, int *hitstopp);
static chr *shortest(struct vars *v, struct dfa *d, chr *start, chr *min,
           chr *max, chr **coldp, int *hitstopp);
static int  matchuntil(struct vars *v, struct dfa *d, chr *probe,
             struct sset **lastcss, chr **lastcp);
static chr *dfa_backref(struct vars *v, struct dfa *d, chr *start,
            chr *min, chr *max, bool shortest);
static chr *lastcold(struct vars *v, struct dfa *d);
static struct dfa *newdfa(struct vars *v, struct cnfa *cnfa,
              struct colormap *cm, struct smalldfa *sml);
static void freedfa(struct dfa *d);
static unsigned hash(unsigned *uv, int n);
static struct sset *initialize(struct vars *v, struct dfa *d, chr *start);
static struct sset *miss(struct vars *v, struct dfa *d, struct sset *css,
             color co, chr *cp, chr *start);
static int  lacon(struct vars *v, struct cnfa *pcnfa, chr *cp, color co);
static struct sset *getvacant(struct vars *v, struct dfa *d, chr *cp,
                chr *start);
static struct sset *pickss(struct vars *v, struct dfa *d, chr *cp,
               chr *start);


/*
 * pg_regexec - match regular expression
 */
int
pg_regexec(regex_t *re,
       const chr *string,
       size_t len,
       size_t search_start,
       rm_detail_t *details,
       size_t nmatch,
       regmatch_t pmatch[],
       int flags)
{
  struct vars var;
  struct vars *v = &var;
  int     st;
  size_t    n;
  size_t    i;
  int     backref;

#define  LOCALMAT  20
  regmatch_t  mat[LOCALMAT];

#define  LOCALDFAS   40
  struct dfa *subdfas[LOCALDFAS];

  /* sanity checks */
  if (re == NULL || string == NULL || re->re_magic != REMAGIC)
    return REG_INVARG;
  if (re->re_csize != sizeof(chr))
    return REG_MIXED;
  if (search_start > len)
    return REG_NOMATCH;

  /* Initialize locale-dependent support */
  pg_set_regex_collation(re->re_collation);

  /* 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 (backref && nmatch <= v->g->nsub)
  {
    /* need larger work area */
    v->nmatch = v->g->nsub + 1;
    if (v->nmatch <= LOCALMAT)
      v->pmatch = mat;
    else
      v->pmatch = MALLOC_ARRAY(regmatch_t, v->nmatch);
    if (v->pmatch == NULL)
      return REG_ESPACE;
    zapallsubs(v->pmatch, v->nmatch);
  }
  else
  {
    /* we can store results directly in caller's array */
    v->pmatch = pmatch;
    /* ensure any extra entries in caller's array are filled with -1 */
    if (nmatch > 0)
      zapallsubs(pmatch, nmatch);
    /* then forget about extra entries, to avoid useless work in find() */
    if (nmatch > v->g->nsub + 1)
      nmatch = v->g->nsub + 1;
    v->nmatch = nmatch;
  }
  v->details = details;
  v->start = (chr *) string;
  v->search_start = (chr *) string + search_start;
  v->stop = (chr *) string + len;
  v->err = 0;
  v->subdfas = NULL;
  v->ladfas = NULL;
  v->lblastcss = NULL;
  v->lblastcp = NULL;
  /* below this point, "goto cleanup" will behave sanely */

  assert(v->g->ntree >= 0);
  n = (size_t) v->g->ntree;
  if (n <= LOCALDFAS)
    v->subdfas = subdfas;
  else
  {
    /* ntree is surely less than the number of states, so this is safe: */
    v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
    if (v->subdfas == NULL)
    {
      st = REG_ESPACE;
      goto cleanup;
    }
  }
  for (i = 0; i < n; i++)
    v->subdfas[i] = NULL;

  assert(v->g->nlacons >= 0);
  n = (size_t) v->g->nlacons;
  if (n > 0)
  {
    /* nlacons is surely less than the number of arcs, so this is safe: */
    v->ladfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
    if (v->ladfas == NULL)
    {
      st = REG_ESPACE;
      goto cleanup;
    }
    for (i = 0; i < n; i++)
      v->ladfas[i] = NULL;
    v->lblastcss = (struct sset **) MALLOC(n * sizeof(struct sset *));
    v->lblastcp = (chr **) MALLOC(n * sizeof(chr *));
    if (v->lblastcss == NULL || v->lblastcp == NULL)
    {
      st = REG_ESPACE;
      goto cleanup;
    }
    for (i = 0; i < n; i++)
    {
      v->lblastcss[i] = NULL;
      v->lblastcp[i] = 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);

  /* on success, ensure caller's match vector is filled correctly */
  if (st == REG_OKAY && nmatch > 0)
  {
    if (v->pmatch != pmatch)
    {
      /* copy portion of match vector over from (larger) work area */
      assert(nmatch <= v->nmatch);
      memcpy(VS(pmatch), VS(v->pmatch), nmatch * sizeof(regmatch_t));
    }
    if (v->g->cflags & REG_NOSUB)
    {
      /* don't expose possibly-partial sub-match results to caller */
      zapallsubs(pmatch, nmatch);
    }
  }

  /* clean up */
cleanup:
  if (v->pmatch != pmatch && v->pmatch != mat)
    FREE(v->pmatch);
  if (v->subdfas != NULL)
  {
    n = (size_t) v->g->ntree;
    for (i = 0; i < n; i++)
    {
      if (v->subdfas[i] != NULL)
        freedfa(v->subdfas[i]);
    }
    if (v->subdfas != subdfas)
      FREE(v->subdfas);
  }
  if (v->ladfas != NULL)
  {
    n = (size_t) v->g->nlacons;
    for (i = 0; i < n; i++)
    {
      if (v->ladfas[i] != NULL)
        freedfa(v->ladfas[i]);
    }
    FREE(v->ladfas);
  }
  if (v->lblastcss != NULL)
    FREE(v->lblastcss);
  if (v->lblastcp != NULL)
    FREE(v->lblastcp);

#ifdef REG_DEBUG
  if (v->eflags & (REG_FTRACE | REG_MTRACE))
    fflush(stdout);
#endif

  return st;
}

/*
 * getsubdfa - create or re-fetch the DFA for a tree subre node
 *
 * We only need to create the DFA once per overall regex execution.
 * The DFA will be freed by the cleanup step in pg_regexec().
 */
static struct dfa *
getsubdfa(struct vars *v,
      struct subre *t)
{
  struct dfa *d = v->subdfas[t->id];

  if (d == NULL)
  {
    d = newdfa(v, &t->cnfa, &v->g->cmap, DOMALLOC);
    if (d == NULL)
      return NULL;
    /* set up additional info if this is a backref node */
    if (t->op == 'b')
    {
      d->backno = t->backno;
      d->backmin = t->min;
      d->backmax = t->max;
    }
    v->subdfas[t->id] = d;
  }
  return d;
}

/*
 * getladfa - create or re-fetch the DFA for a LACON subre node
 *
 * Same as above, but for LACONs.
 */
static struct dfa *
getladfa(struct vars *v,
     int n)
{
  assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);

  if (v->ladfas[n] == NULL)
  {
    struct subre *sub = &v->g->lacons[n];

    v->ladfas[n] = newdfa(v, &sub->cnfa, &v->g->cmap, DOMALLOC);
    /* a LACON can't contain a backref, so nothing else to do */
  }
  return v->ladfas[n];
}

/*
 * 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);
  if (s == NULL)
    return v->err;
  MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
  cold = NULL;
  close = shortest(v, s, v->search_start, v->search_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);
  if (d == NULL)
    return v->err;
  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);
    if (ISERR())
    {
      freedfa(d);
      return v->err;
    }
    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;

  /* find submatches */
  return cdissect(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);
  if (s == NULL)
    return v->err;
  d = newdfa(v, cnfa, cm, &v->dfa2);
  if (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->search_start;
  do
  {
    /* Search with the search RE for match range at/beyond "close" */
    MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
    close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
    if (ISERR())
    {
      *coldp = cold;
      return v->err;
    }
    if (close == NULL)
      break;       /* no more possible match anywhere */
    assert(cold != NULL);
    open = cold;
    cold = NULL;
    /* Search for matches starting between "open" and "close" inclusive */
    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 (;;)
      {
        /* Here we use the top node's detailed RE */
        if (shorter)
          end = shortest(v, d, begin, estart,
                   estop, (chr **) NULL, &hitend);
        else
          end = longest(v, d, begin, estop,
                  &hitend);
        if (ISERR())
        {
          *coldp = cold;
          return v->err;
        }
        if (hitend && cold == NULL)
          cold = begin;
        if (end == NULL)
          break;   /* no match with this begin point, try next */
        MDEBUG(("tentative end %ld\n", LOFF(end)));
        /* Dissect the potential match to see if it really matches */
        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);
          *coldp = cold;
          return er;
        }
        /* Try next longer/shorter match with same begin point */
        if (shorter)
        {
          if (end == estop)
            break; /* no more, so try next begin point */
          estart = end + 1;
        }
        else
        {
          if (end == begin)
            break; /* no more, so try next begin point */
          estop = end - 1;
        }
      }         /* end loop over endpoint positions */
    }           /* end loop over beginning positions */

    /*
     * If we get here, there is no possible match starting at or before
     * "close", so consider matches beyond that.  We'll do a fresh search
     * with the search RE to find a new promising match range.
     */
    close++;
  } while (close < v->stop);

  *coldp = cold;
  return REG_NOMATCH;
}

/*
 * zapallsubs - initialize all subexpression matches to "no match"
 *
 * Note that p[0], the overall-match location, is not touched.
 */
static void
zapallsubs(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;
  }
}

/*
 * zaptreesubs - initialize subexpressions within subtree to "no match"
 */
static void
zaptreesubs(struct vars *v,
      struct subre *t)
{
  int     n = t->capno;
  struct subre *t2;

  if (n > 0)
  {
    if ((size_t) n < v->nmatch)
    {
      v->pmatch[n].rm_so = -1;
      v->pmatch[n].rm_eo = -1;
    }
  }

  for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
    zaptreesubs(v, t2);
}

/*
 * subset - set subexpression match data for a successful subre
 */
static void
subset(struct vars *v,
     struct subre *sub,
     chr *begin,
     chr *end)
{
  int     n = sub->capno;

  assert(n > 0);
  if ((size_t) n >= v->nmatch)
    return;

  MDEBUG(("%d: setting %d = %ld-%ld\n", sub->id, n, LOFF(begin), LOFF(end)));
  v->pmatch[n].rm_so = OFF(begin);
  v->pmatch[n].rm_eo = OFF(end);
}

/*
 * cdissect - check backrefs and determine subexpression matches
 *
 * cdissect recursively processes a subre tree to check matching of backrefs
 * and/or identify submatch boundaries for capture nodes.  The proposed match
 * runs from "begin" to "end" (not including "end"), and we are basically
 * "dissecting" it to see where the submatches are.
 *
 * Before calling any level of cdissect, the caller must have run the node's
 * DFA and found that the proposed substring satisfies the DFA.  (We make
 * the caller do that because in concatenation and iteration nodes, it's
 * much faster to check all the substrings against the child DFAs before we
 * recurse.)
 *
 * A side-effect of a successful match is to save match locations for
 * capturing subexpressions in v->pmatch[].  This is a little bit tricky,
 * so we make the following rules:
 * 1. Before initial entry to cdissect, all match data must have been
 *    cleared (this is seen to by zapallsubs).
 * 2. Before any recursive entry to cdissect, the match data for that
 *    subexpression tree must be guaranteed clear (see zaptreesubs).
 * 3. When returning REG_OKAY, each level of cdissect will have saved
 *    any relevant match locations.
 * 4. When returning REG_NOMATCH, each level of cdissect will guarantee
 *    that its subexpression match locations are again clear.
 * 5. No guarantees are made for error cases (i.e., other result codes).
 * 6. When a level of cdissect abandons a successful sub-match, it will
 *    clear that subtree's match locations with zaptreesubs before trying
 *    any new DFA match or cdissect call for that subtree or any subtree
 *    to its right (that is, any subtree that could have a backref into the
 *    abandoned match).
 * This may seem overly complicated, but it's difficult to simplify it
 * because of the provision that match locations must be reset before
 * any fresh DFA match (a rule that is needed to make dfa_backref safe).
 * That means it won't work to just reset relevant match locations at the
 * start of each cdissect level.
 */
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(("%d: cdissect %c %ld-%ld\n", t->id, t->op, LOFF(begin), LOFF(end)));

  /* handy place to check for operation cancel */
  INTERRUPT(v->re);
  /* ... and stack overrun */
  if (STACK_TOO_DEEP(v->re))
    return REG_ETOOBIG;

  switch (t->op)
  {
    case '=':       /* terminal node */
      assert(t->child == NULL);
      er = REG_OKAY;   /* no action, parent did the work */
      break;
    case 'b':       /* back reference */
      assert(t->child == NULL);
      er = cbrdissect(v, t, begin, end);
      break;
    case '.':       /* concatenation */
      assert(t->child != NULL);
      if (t->child->flags & SHORTER) /* reverse scan */
        er = crevcondissect(v, t, begin, end);
      else
        er = ccondissect(v, t, begin, end);
      break;
    case '|':       /* alternation */
      assert(t->child != NULL);
      er = caltdissect(v, t, begin, end);
      break;
    case '*':       /* iteration */
      assert(t->child != NULL);
      if (t->child->flags & SHORTER) /* reverse scan */
        er = creviterdissect(v, t, begin, end);
      else
        er = citerdissect(v, t, begin, end);
      break;
    case '(':       /* no-op capture node */
      assert(t->child != NULL);
      er = cdissect(v, t->child, begin, end);
      break;
    default:
      er = REG_ASSERT;
      break;
  }

  /*
   * We should never have a match failure unless backrefs lurk below;
   * otherwise, either caller failed to check the DFA, or there's some
   * inconsistency between the DFA and the node's innards.
   */
  assert(er != REG_NOMATCH || (t->flags & BACKR));

  /*
   * If this node is marked as capturing, save successful match's location.
   */
  if (t->capno > 0 && er == REG_OKAY)
    subset(v, t, begin, end);

  return er;
}

/*
 * ccondissect - dissect match for concatenation node
 */
static int            /* regexec return code */
ccondissect(struct vars *v,
      struct subre *t,
      chr *begin,     /* beginning of relevant substring */
      chr *end)     /* end of same */
{
  struct subre *left = t->child;
  struct subre *right = left->sibling;
  struct dfa *d;
  struct dfa *d2;
  chr      *mid;
  int     er;

  assert(t->op == '.');
  assert(left != NULL && left->cnfa.nstates > 0);
  assert(right != NULL && right->cnfa.nstates > 0);
  assert(right->sibling == NULL);
  assert(!(left->flags & SHORTER));

  d = getsubdfa(v, left);
  NOERR();
  d2 = getsubdfa(v, right);
  NOERR();
  MDEBUG(("%d: ccondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));

  /* pick a tentative midpoint */
  mid = longest(v, d, begin, end, (int *) NULL);
  NOERR();
  if (mid == NULL)
    return REG_NOMATCH;
  MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid)));

  /* iterate until satisfaction or failure */
  for (;;)
  {
    /* try this midpoint on for size */
    if (longest(v, d2, mid, end, (int *) NULL) == end)
    {
      er = cdissect(v, left, begin, mid);
      if (er == REG_OKAY)
      {
        er = cdissect(v, right, mid, end);
        if (er == REG_OKAY)
        {
          /* satisfaction */
          MDEBUG(("%d: successful\n", t->id));
          return REG_OKAY;
        }
        /* Reset left's matches (right should have done so itself) */
        zaptreesubs(v, left);
      }
      if (er != REG_NOMATCH)
        return er;
    }
    NOERR();

    /* that midpoint didn't work, find a new one */
    if (mid == begin)
    {
      /* all possibilities exhausted */
      MDEBUG(("%d: no midpoint\n", t->id));
      return REG_NOMATCH;
    }
    mid = longest(v, d, begin, mid - 1, (int *) NULL);
    NOERR();
    if (mid == NULL)
    {
      /* failed to find a new one */
      MDEBUG(("%d: failed midpoint\n", t->id));
      return REG_NOMATCH;
    }
    MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
  }

  /* can't get here */
  return REG_ASSERT;
}

/*
 * crevcondissect - dissect match for concatenation node, shortest-first
 */
static int            /* regexec return code */
crevcondissect(struct vars *v,
         struct subre *t,
         chr *begin,    /* beginning of relevant substring */
         chr *end)    /* end of same */
{
  struct subre *left = t->child;
  struct subre *right = left->sibling;
  struct dfa *d;
  struct dfa *d2;
  chr      *mid;
  int     er;

  assert(t->op == '.');
  assert(left != NULL && left->cnfa.nstates > 0);
  assert(right != NULL && right->cnfa.nstates > 0);
  assert(right->sibling == NULL);
  assert(left->flags & SHORTER);

  d = getsubdfa(v, left);
  NOERR();
  d2 = getsubdfa(v, right);
  NOERR();
  MDEBUG(("%d: crevcondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));

  /* pick a tentative midpoint */
  mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
  NOERR();
  if (mid == NULL)
    return REG_NOMATCH;
  MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid)));

  /* iterate until satisfaction or failure */
  for (;;)
  {
    /* try this midpoint on for size */
    if (longest(v, d2, mid, end, (int *) NULL) == end)
    {
      er = cdissect(v, left, begin, mid);
      if (er == REG_OKAY)
      {
        er = cdissect(v, right, mid, end);
        if (er == REG_OKAY)
        {
          /* satisfaction */
          MDEBUG(("%d: successful\n", t->id));
          return REG_OKAY;
        }
        /* Reset left's matches (right should have done so itself) */
        zaptreesubs(v, left);
      }
      if (er != REG_NOMATCH)
        return er;
    }
    NOERR();

    /* that midpoint didn't work, find a new one */
    if (mid == end)
    {
      /* all possibilities exhausted */
      MDEBUG(("%d: no midpoint\n", t->id));
      return REG_NOMATCH;
    }
    mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
    NOERR();
    if (mid == NULL)
    {
      /* failed to find a new one */
      MDEBUG(("%d: failed midpoint\n", t->id));
      return REG_NOMATCH;
    }
    MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
  }

  /* can't get here */
  return REG_ASSERT;
}

/*
 * cbrdissect - dissect match for backref node
 *
 * The backref match might already have been verified by dfa_backref(),
 * but we don't know that for sure so must check it here.
 */
static int            /* regexec return code */
cbrdissect(struct vars *v,
       struct subre *t,
       chr *begin,      /* beginning of relevant substring */
       chr *end)      /* end of same */
{
  int     n = t->backno;
  size_t    numreps;
  size_t    tlen;
  size_t    brlen;
  chr      *brstring;
  chr      *p;
  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(("%d: cbrdissect %d{%d-%d} %ld-%ld\n", t->id, n, min, max,
      LOFF(begin), LOFF(end)));

  /* get the backreferenced string */
  if (v->pmatch[n].rm_so == -1)
    return REG_NOMATCH;
  brstring = v->start + v->pmatch[n].rm_so;
  brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;

  /* special cases for zero-length strings */
  if (brlen == 0)
  {
    /*
     * matches only if target is zero length, but any number of
     * repetitions can be considered to be present
     */
    if (begin == end && min <= max)
    {
      MDEBUG(("%d: backref matched trivially\n", t->id));
      return REG_OKAY;
    }
    return REG_NOMATCH;
  }
  if (begin == end)
  {
    /* matches only if zero repetitions are okay */
    if (min == 0)
    {
      MDEBUG(("%d: backref matched trivially\n", t->id));
      return REG_OKAY;
    }
    return REG_NOMATCH;
  }

  /*
   * check target length to see if it could possibly be an allowed number of
   * repetitions of brstring
   */
  assert(end > begin);
  tlen = end - begin;
  if (tlen % brlen != 0)
    return REG_NOMATCH;
  numreps = tlen / brlen;
  if (numreps < min || (numreps > max && max != DUPINF))
    return REG_NOMATCH;

  /* okay, compare the actual string contents */
  p = begin;
  while (numreps-- > 0)
  {
    if ((*v->g->compare) (brstring, p, brlen) != 0)
      return REG_NOMATCH;
    p += brlen;
  }

  MDEBUG(("%d: backref matched\n", t->id));
  return REG_OKAY;
}

/*
 * caltdissect - dissect match for alternation node
 */
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;

  assert(t->op == '|');

  t = t->child;
  /* there should be at least 2 alternatives */
  assert(t != NULL && t->sibling != NULL);

  while (t != NULL)
  {
    assert(t->cnfa.nstates > 0);

    MDEBUG(("%d: caltdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));

    d = getsubdfa(v, t);
    NOERR();
    if (longest(v, d, begin, end, (int *) NULL) == end)
    {
      MDEBUG(("%d: caltdissect matched\n", t->id));
      er = cdissect(v, t, begin, end);
      if (er != REG_NOMATCH)
        return er;
    }
    NOERR();

    t = t->sibling;
  }

  return REG_NOMATCH;
}

/*
 * citerdissect - dissect match for iteration node
 */
static int            /* regexec return code */
citerdissect(struct vars *v,
       struct subre *t,
       chr *begin,    /* beginning of relevant substring */
       chr *end)      /* end of same */
{
  struct dfa *d;
  chr     **endpts;
  chr      *limit;
  int     min_matches;
  size_t    max_matches;
  int     nverified;
  int     k;
  int     i;
  int     er;

  assert(t->op == '*');
  assert(t->child != NULL && t->child->cnfa.nstates > 0);
  assert(!(t->child->flags & SHORTER));
  assert(begin <= end);

  MDEBUG(("%d: citerdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));

  /*
   * For the moment, assume the minimum number of matches is 1.  If zero
   * matches are allowed, and the target string is empty, we are allowed to
   * match regardless of the contents of the iter node --- but we would
   * prefer to match once, so that capturing parens get set.  (An example of
   * the concern here is a pattern like "()*\1", which historically this
   * code has allowed to succeed.)  Therefore, we deal with the zero-matches
   * case at the bottom, after failing to find any other way to match.
   */
  min_matches = t->min;
  if (min_matches <= 0)
    min_matches = 1;

  /*
   * We need workspace to track the endpoints of each sub-match.  Normally
   * we consider only nonzero-length sub-matches, so there can be at most
   * end-begin of them.  However, if min is larger than that, we will also
   * consider zero-length sub-matches in order to find enough matches.
   *
   * For convenience, endpts[0] contains the "begin" pointer and we store
   * sub-match endpoints in endpts[1..max_matches].
   */
  max_matches = end - begin;
  if (max_matches > t->max && t->max != DUPINF)
    max_matches = t->max;
  if (max_matches < min_matches)
    max_matches = min_matches;
  endpts = MALLOC_ARRAY(chr *, max_matches + 1);
  if (endpts == NULL)
    return REG_ESPACE;
  endpts[0] = begin;

  d = getsubdfa(v, t->child);
  if (ISERR())
  {
    FREE(endpts);
    return v->err;
  }

  /*
   * Our strategy is to first find a set of sub-match endpoints that are
   * valid according to the child node's DFA, and then recursively dissect
   * each sub-match to confirm validity.  If any validity check fails,
   * backtrack that sub-match and try again.  And, when we next try for a
   * validity check, we need not recheck any successfully verified
   * sub-matches that we didn't move the endpoints of.  nverified remembers
   * how many sub-matches are currently known okay.
   */

  /* initialize to consider first sub-match */
  nverified = 0;
  k = 1;
  limit = end;

  /* iterate until satisfaction or failure */
  while (k > 0)
  {
    /* try to find an endpoint for the k'th sub-match */
    endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL);
    if (ISERR())
    {
      FREE(endpts);
      return v->err;
    }
    if (endpts[k] == NULL)
    {
      /* no match possible, so see if we can shorten previous one */
      k--;
      goto backtrack;
    }
    MDEBUG(("%d: working endpoint %d: %ld\n",
        t->id, k, LOFF(endpts[k])));

    /* k'th sub-match can no longer be considered verified */
    if (nverified >= k)
      nverified = k - 1;

    if (endpts[k] != end)
    {
      /* haven't reached end yet, try another iteration if allowed */
      if (k >= max_matches)
      {
        /* must try to shorten some previous match */
        k--;
        goto backtrack;
      }

      /* reject zero-length match unless necessary to achieve min */
      if (endpts[k] == endpts[k - 1] &&
        (k >= min_matches || min_matches - k < end - endpts[k]))
        goto backtrack;

      k++;
      limit = end;
      continue;
    }

    /*
     * We've identified a way to divide the string into k sub-matches that
     * works so far as the child DFA can tell.  If k is an allowed number
     * of matches, start the slow part: recurse to verify each sub-match.
     * We always have k <= max_matches, needn't check that.
     */
    if (k < min_matches)
      goto backtrack;

    MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

    for (i = nverified + 1; i <= k; i++)
    {
      /* zap any match data from a non-last iteration */
      zaptreesubs(v, t->child);
      er = cdissect(v, t->child, endpts[i - 1], endpts[i]);
      if (er == REG_OKAY)
      {
        nverified = i;
        continue;
      }
      if (er == REG_NOMATCH)
        break;
      /* oops, something failed */
      FREE(endpts);
      return er;
    }

    if (i > k)
    {
      /* satisfaction */
      MDEBUG(("%d: successful\n", t->id));
      FREE(endpts);
      return REG_OKAY;
    }

    /* i'th match failed to verify, so backtrack it */
    k = i;

backtrack:

    /*
     * Must consider shorter versions of the k'th sub-match.  However,
     * we'll only ask for a zero-length match if necessary.
     */
    while (k > 0)
    {
      chr      *prev_end = endpts[k - 1];

      if (endpts[k] > prev_end)
      {
        limit = endpts[k] - 1;
        if (limit > prev_end ||
          (k < min_matches && min_matches - k >= end - prev_end))
        {
          /* break out of backtrack loop, continue the outer one */
          break;
        }
      }
      /* can't shorten k'th sub-match any more, consider previous one */
      k--;
    }
  }

  /* all possibilities exhausted */
  FREE(endpts);

  /*
   * Now consider the possibility that we can match to a zero-length string
   * by using zero repetitions.
   */
  if (t->min == 0 && begin == end)
  {
    MDEBUG(("%d: allowing zero matches\n", t->id));
    return REG_OKAY;
  }

  MDEBUG(("%d: failed\n", t->id));
  return REG_NOMATCH;
}

/*
 * creviterdissect - dissect match for iteration node, shortest-first
 */
static int            /* regexec return code */
creviterdissect(struct vars *v,
        struct subre *t,
        chr *begin,   /* beginning of relevant substring */
        chr *end)   /* end of same */
{
  struct dfa *d;
  chr     **endpts;
  chr      *limit;
  int     min_matches;
  size_t    max_matches;
  int     nverified;
  int     k;
  int     i;
  int     er;

  assert(t->op == '*');
  assert(t->child != NULL && t->child->cnfa.nstates > 0);
  assert(t->child->flags & SHORTER);
  assert(begin <= end);

  MDEBUG(("%d: creviterdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));

  /*
   * If zero matches are allowed, and target string is empty, just declare
   * victory.  OTOH, if target string isn't empty, zero matches can't work
   * so we pretend the min is 1.
   */
  min_matches = t->min;
  if (min_matches <= 0)
  {
    if (begin == end)
    {
      MDEBUG(("%d: allowing zero matches\n", t->id));
      return REG_OKAY;
    }
    min_matches = 1;
  }

  /*
   * We need workspace to track the endpoints of each sub-match.  Normally
   * we consider only nonzero-length sub-matches, so there can be at most
   * end-begin of them.  However, if min is larger than that, we will also
   * consider zero-length sub-matches in order to find enough matches.
   *
   * For convenience, endpts[0] contains the "begin" pointer and we store
   * sub-match endpoints in endpts[1..max_matches].
   */
  max_matches = end - begin;
  if (max_matches > t->max && t->max != DUPINF)
    max_matches = t->max;
  if (max_matches < min_matches)
    max_matches = min_matches;
  endpts = MALLOC_ARRAY(chr *, max_matches + 1);
  if (endpts == NULL)
    return REG_ESPACE;
  endpts[0] = begin;

  d = getsubdfa(v, t->child);
  if (ISERR())
  {
    FREE(endpts);
    return v->err;
  }

  /*
   * Our strategy is to first find a set of sub-match endpoints that are
   * valid according to the child node's DFA, and then recursively dissect
   * each sub-match to confirm validity.  If any validity check fails,
   * backtrack that sub-match and try again.  And, when we next try for a
   * validity check, we need not recheck any successfully verified
   * sub-matches that we didn't move the endpoints of.  nverified remembers
   * how many sub-matches are currently known okay.
   */

  /* initialize to consider first sub-match */
  nverified = 0;
  k = 1;
  limit = begin;

  /* iterate until satisfaction or failure */
  while (k > 0)
  {
    /* disallow zero-length match unless necessary to achieve min */
    if (limit == endpts[k - 1] &&
      limit != end &&
      (k >= min_matches || min_matches - k < end - limit))
      limit++;

    /* if this is the last allowed sub-match, it must reach to the end */
    if (k >= max_matches)
      limit = end;

    /* try to find an endpoint for the k'th sub-match */
    endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
               (chr **) NULL, (int *) NULL);
    if (ISERR())
    {
      FREE(endpts);
      return v->err;
    }
    if (endpts[k] == NULL)
    {
      /* no match possible, so see if we can lengthen previous one */
      k--;
      goto backtrack;
    }
    MDEBUG(("%d: working endpoint %d: %ld\n",
        t->id, k, LOFF(endpts[k])));

    /* k'th sub-match can no longer be considered verified */
    if (nverified >= k)
      nverified = k - 1;

    if (endpts[k] != end)
    {
      /* haven't reached end yet, try another iteration if allowed */
      if (k >= max_matches)
      {
        /* must try to lengthen some previous match */
        k--;
        goto backtrack;
      }

      k++;
      limit = endpts[k - 1];
      continue;
    }

    /*
     * We've identified a way to divide the string into k sub-matches that
     * works so far as the child DFA can tell.  If k is an allowed number
     * of matches, start the slow part: recurse to verify each sub-match.
     * We always have k <= max_matches, needn't check that.
     */
    if (k < min_matches)
      goto backtrack;

    MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

    for (i = nverified + 1; i <= k; i++)
    {
      /* zap any match data from a non-last iteration */
      zaptreesubs(v, t->child);
      er = cdissect(v, t->child, endpts[i - 1], endpts[i]);
      if (er == REG_OKAY)
      {
        nverified = i;
        continue;
      }
      if (er == REG_NOMATCH)
        break;
      /* oops, something failed */
      FREE(endpts);
      return er;
    }

    if (i > k)
    {
      /* satisfaction */
      MDEBUG(("%d: successful\n", t->id));
      FREE(endpts);
      return REG_OKAY;
    }

    /* i'th match failed to verify, so backtrack it */
    k = i;

backtrack:

    /*
     * Must consider longer versions of the k'th sub-match.
     */
    while (k > 0)
    {
      if (endpts[k] < end)
      {
        limit = endpts[k] + 1;
        /* break out of backtrack loop, continue the outer one */
        break;
      }
      /* can't lengthen k'th sub-match any more, consider previous one */
      k--;
    }
  }

  /* all possibilities exhausted */
  MDEBUG(("%d: failed\n", t->id));
  FREE(endpts);
  return REG_NOMATCH;
}



#include "rege_dfa.c"

Coverage Report

Created: 2026-08-14 06:37