LCOV - code coverage report
Current view: top level - src/backend/regex - regexec.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 390 482 80.9 %
Date: 2019-11-21 14:06:36 Functions: 16 16 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * re_*exec and friends - match REs
       3             :  *
       4             :  * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
       5             :  *
       6             :  * Development of this software was funded, in part, by Cray Research Inc.,
       7             :  * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
       8             :  * Corporation, none of whom are responsible for the results.  The author
       9             :  * thanks all of them.
      10             :  *
      11             :  * Redistribution and use in source and binary forms -- with or without
      12             :  * modification -- are permitted for any purpose, provided that
      13             :  * redistributions in source form retain this entire copyright notice and
      14             :  * indicate the origin and nature of any modifications.
      15             :  *
      16             :  * I'd appreciate being given credit for this package in the documentation
      17             :  * of software which uses it, but that is not a requirement.
      18             :  *
      19             :  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
      20             :  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
      21             :  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
      22             :  * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
      23             :  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
      24             :  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
      25             :  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
      26             :  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
      27             :  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
      28             :  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
      29             :  *
      30             :  * src/backend/regex/regexec.c
      31             :  *
      32             :  */
      33             : 
      34             : #include "regex/regguts.h"
      35             : 
      36             : 
      37             : 
      38             : /* lazy-DFA representation */
      39             : struct arcp
      40             : {                               /* "pointer" to an outarc */
      41             :     struct sset *ss;
      42             :     color       co;
      43             : };
      44             : 
      45             : struct sset
      46             : {                               /* state set */
      47             :     unsigned   *states;         /* pointer to bitvector */
      48             :     unsigned    hash;           /* hash of bitvector */
      49             : #define  HASH(bv, nw)    (((nw) == 1) ? *(bv) : hash(bv, nw))
      50             : #define  HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
      51             :         memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
      52             :     int         flags;
      53             : #define  STARTER     01         /* the initial state set */
      54             : #define  POSTSTATE   02         /* includes the goal state */
      55             : #define  LOCKED      04         /* locked in cache */
      56             : #define  NOPROGRESS  010        /* zero-progress state set */
      57             :     struct arcp ins;            /* chain of inarcs pointing here */
      58             :     chr        *lastseen;       /* last entered on arrival here */
      59             :     struct sset **outs;         /* outarc vector indexed by color */
      60             :     struct arcp *inchain;       /* chain-pointer vector for outarcs */
      61             : };
      62             : 
      63             : struct dfa
      64             : {
      65             :     int         nssets;         /* size of cache */
      66             :     int         nssused;        /* how many entries occupied yet */
      67             :     int         nstates;        /* number of states */
      68             :     int         ncolors;        /* length of outarc and inchain vectors */
      69             :     int         wordsper;       /* length of state-set bitvectors */
      70             :     struct sset *ssets;         /* state-set cache */
      71             :     unsigned   *statesarea;     /* bitvector storage */
      72             :     unsigned   *work;           /* pointer to work area within statesarea */
      73             :     struct sset **outsarea;     /* outarc-vector storage */
      74             :     struct arcp *incarea;       /* inchain storage */
      75             :     struct cnfa *cnfa;
      76             :     struct colormap *cm;
      77             :     chr        *lastpost;       /* location of last cache-flushed success */
      78             :     chr        *lastnopr;       /* location of last cache-flushed NOPROGRESS */
      79             :     struct sset *search;        /* replacement-search-pointer memory */
      80             :     int         cptsmalloced;   /* were the areas individually malloced? */
      81             :     char       *mallocarea;     /* self, or master malloced area, or NULL */
      82             : };
      83             : 
      84             : #define WORK    1               /* number of work bitvectors needed */
      85             : 
      86             : /* setup for non-malloc allocation for small cases */
      87             : #define FEWSTATES   20          /* must be less than UBITS */
      88             : #define FEWCOLORS   15
      89             : struct smalldfa
      90             : {
      91             :     struct dfa  dfa;
      92             :     struct sset ssets[FEWSTATES * 2];
      93             :     unsigned    statesarea[FEWSTATES * 2 + WORK];
      94             :     struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
      95             :     struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
      96             : };
      97             : 
      98             : #define DOMALLOC    ((struct smalldfa *)NULL)   /* force malloc */
      99             : 
     100             : 
     101             : 
     102             : /* internal variables, bundled for easy passing around */
     103             : struct vars
     104             : {
     105             :     regex_t    *re;
     106             :     struct guts *g;
     107             :     int         eflags;         /* copies of arguments */
     108             :     size_t      nmatch;
     109             :     regmatch_t *pmatch;
     110             :     rm_detail_t *details;
     111             :     chr        *start;          /* start of string */
     112             :     chr        *search_start;   /* search start of string */
     113             :     chr        *stop;           /* just past end of string */
     114             :     int         err;            /* error code if any (0 none) */
     115             :     struct dfa **subdfas;       /* per-tree-subre DFAs */
     116             :     struct dfa **ladfas;        /* per-lacon-subre DFAs */
     117             :     struct sset **lblastcss;    /* per-lacon-subre lookbehind restart data */
     118             :     chr       **lblastcp;       /* per-lacon-subre lookbehind restart data */
     119             :     struct smalldfa dfa1;
     120             :     struct smalldfa dfa2;
     121             : };
     122             : 
     123             : #define VISERR(vv)  ((vv)->err != 0) /* have we seen an error yet? */
     124             : #define ISERR() VISERR(v)
     125             : #define VERR(vv,e)  ((vv)->err = ((vv)->err ? (vv)->err : (e)))
     126             : #define ERR(e)  VERR(v, e)      /* record an error */
     127             : #define NOERR() {if (ISERR()) return v->err;}    /* if error seen, return it */
     128             : #define OFF(p)  ((p) - v->start)
     129             : #define LOFF(p) ((long)OFF(p))
     130             : 
     131             : 
     132             : 
     133             : /*
     134             :  * forward declarations
     135             :  */
     136             : /* === regexec.c === */
     137             : static struct dfa *getsubdfa(struct vars *, struct subre *);
     138             : static struct dfa *getladfa(struct vars *, int);
     139             : static int  find(struct vars *, struct cnfa *, struct colormap *);
     140             : static int  cfind(struct vars *, struct cnfa *, struct colormap *);
     141             : static int  cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
     142             : static void zapallsubs(regmatch_t *, size_t);
     143             : static void zaptreesubs(struct vars *, struct subre *);
     144             : static void subset(struct vars *, struct subre *, chr *, chr *);
     145             : static int  cdissect(struct vars *, struct subre *, chr *, chr *);
     146             : static int  ccondissect(struct vars *, struct subre *, chr *, chr *);
     147             : static int  crevcondissect(struct vars *, struct subre *, chr *, chr *);
     148             : static int  cbrdissect(struct vars *, struct subre *, chr *, chr *);
     149             : static int  caltdissect(struct vars *, struct subre *, chr *, chr *);
     150             : static int  citerdissect(struct vars *, struct subre *, chr *, chr *);
     151             : static int  creviterdissect(struct vars *, struct subre *, chr *, chr *);
     152             : 
     153             : /* === rege_dfa.c === */
     154             : static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
     155             : static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
     156             : static int  matchuntil(struct vars *, struct dfa *, chr *, struct sset **, chr **);
     157             : static chr *lastcold(struct vars *, struct dfa *);
     158             : static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
     159             : static void freedfa(struct dfa *);
     160             : static unsigned hash(unsigned *, int);
     161             : static struct sset *initialize(struct vars *, struct dfa *, chr *);
     162             : static struct sset *miss(struct vars *, struct dfa *, struct sset *, color, chr *, chr *);
     163             : static int  lacon(struct vars *, struct cnfa *, chr *, color);
     164             : static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
     165             : static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
     166             : 
     167             : 
     168             : /*
     169             :  * pg_regexec - match regular expression
     170             :  */
     171             : int
     172     1411668 : pg_regexec(regex_t *re,
     173             :            const chr *string,
     174             :            size_t len,
     175             :            size_t search_start,
     176             :            rm_detail_t *details,
     177             :            size_t nmatch,
     178             :            regmatch_t pmatch[],
     179             :            int flags)
     180             : {
     181             :     struct vars var;
     182     1411668 :     register struct vars *v = &var;
     183             :     int         st;
     184             :     size_t      n;
     185             :     size_t      i;
     186             :     int         backref;
     187             : 
     188             : #define  LOCALMAT    20
     189             :     regmatch_t  mat[LOCALMAT];
     190             : 
     191             : #define  LOCALDFAS   40
     192             :     struct dfa *subdfas[LOCALDFAS];
     193             : 
     194             :     /* sanity checks */
     195     1411668 :     if (re == NULL || string == NULL || re->re_magic != REMAGIC)
     196           0 :         return REG_INVARG;
     197     1411668 :     if (re->re_csize != sizeof(chr))
     198           0 :         return REG_MIXED;
     199             : 
     200             :     /* Initialize locale-dependent support */
     201     1411668 :     pg_set_regex_collation(re->re_collation);
     202             : 
     203             :     /* setup */
     204     1411668 :     v->re = re;
     205     1411668 :     v->g = (struct guts *) re->re_guts;
     206     1411668 :     if ((v->g->cflags & REG_EXPECT) && details == NULL)
     207           0 :         return REG_INVARG;
     208     1411668 :     if (v->g->info & REG_UIMPOSSIBLE)
     209          12 :         return REG_NOMATCH;
     210     1411656 :     backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
     211     1411656 :     v->eflags = flags;
     212     1411656 :     if (v->g->cflags & REG_NOSUB)
     213         224 :         nmatch = 0;             /* override client */
     214     1411656 :     v->nmatch = nmatch;
     215     1411656 :     if (backref)
     216             :     {
     217             :         /* need work area */
     218          76 :         if (v->g->nsub + 1 <= LOCALMAT)
     219          76 :             v->pmatch = mat;
     220             :         else
     221           0 :             v->pmatch = (regmatch_t *) MALLOC((v->g->nsub + 1) *
     222             :                                               sizeof(regmatch_t));
     223          76 :         if (v->pmatch == NULL)
     224           0 :             return REG_ESPACE;
     225          76 :         v->nmatch = v->g->nsub + 1;
     226             :     }
     227             :     else
     228     1411580 :         v->pmatch = pmatch;
     229     1411656 :     v->details = details;
     230     1411656 :     v->start = (chr *) string;
     231     1411656 :     v->search_start = (chr *) string + search_start;
     232     1411656 :     v->stop = (chr *) string + len;
     233     1411656 :     v->err = 0;
     234     1411656 :     v->subdfas = NULL;
     235     1411656 :     v->ladfas = NULL;
     236     1411656 :     v->lblastcss = NULL;
     237     1411656 :     v->lblastcp = NULL;
     238             :     /* below this point, "goto cleanup" will behave sanely */
     239             : 
     240             :     assert(v->g->ntree >= 0);
     241     1411656 :     n = (size_t) v->g->ntree;
     242     1411656 :     if (n <= LOCALDFAS)
     243     1411648 :         v->subdfas = subdfas;
     244             :     else
     245             :     {
     246           8 :         v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
     247           8 :         if (v->subdfas == NULL)
     248             :         {
     249           0 :             st = REG_ESPACE;
     250           0 :             goto cleanup;
     251             :         }
     252             :     }
     253     4425394 :     for (i = 0; i < n; i++)
     254     3013738 :         v->subdfas[i] = NULL;
     255             : 
     256             :     assert(v->g->nlacons >= 0);
     257     1411656 :     n = (size_t) v->g->nlacons;
     258     1411656 :     if (n > 0)
     259             :     {
     260         828 :         v->ladfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
     261         828 :         if (v->ladfas == NULL)
     262             :         {
     263           0 :             st = REG_ESPACE;
     264           0 :             goto cleanup;
     265             :         }
     266        2516 :         for (i = 0; i < n; i++)
     267        1688 :             v->ladfas[i] = NULL;
     268         828 :         v->lblastcss = (struct sset **) MALLOC(n * sizeof(struct sset *));
     269         828 :         v->lblastcp = (chr **) MALLOC(n * sizeof(chr *));
     270         828 :         if (v->lblastcss == NULL || v->lblastcp == NULL)
     271             :         {
     272           0 :             st = REG_ESPACE;
     273           0 :             goto cleanup;
     274             :         }
     275        2516 :         for (i = 0; i < n; i++)
     276             :         {
     277        1688 :             v->lblastcss[i] = NULL;
     278        1688 :             v->lblastcp[i] = NULL;
     279             :         }
     280             :     }
     281             : 
     282             :     /* do it */
     283             :     assert(v->g->tree != NULL);
     284     1411656 :     if (backref)
     285          76 :         st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
     286             :     else
     287     1411580 :         st = find(v, &v->g->tree->cnfa, &v->g->cmap);
     288             : 
     289             :     /* copy (portion of) match vector over if necessary */
     290     1411656 :     if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0)
     291             :     {
     292           8 :         zapallsubs(pmatch, nmatch);
     293           8 :         n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
     294           8 :         memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t));
     295             :     }
     296             : 
     297             :     /* clean up */
     298             : cleanup:
     299     1411656 :     if (v->pmatch != pmatch && v->pmatch != mat)
     300           0 :         FREE(v->pmatch);
     301     1411656 :     if (v->subdfas != NULL)
     302             :     {
     303     1411656 :         n = (size_t) v->g->ntree;
     304     4425394 :         for (i = 0; i < n; i++)
     305             :         {
     306     3013738 :             if (v->subdfas[i] != NULL)
     307        4900 :                 freedfa(v->subdfas[i]);
     308             :         }
     309     1411656 :         if (v->subdfas != subdfas)
     310           8 :             FREE(v->subdfas);
     311             :     }
     312     1411656 :     if (v->ladfas != NULL)
     313             :     {
     314         828 :         n = (size_t) v->g->nlacons;
     315        2516 :         for (i = 0; i < n; i++)
     316             :         {
     317        1688 :             if (v->ladfas[i] != NULL)
     318          52 :                 freedfa(v->ladfas[i]);
     319             :         }
     320         828 :         FREE(v->ladfas);
     321             :     }
     322     1411656 :     if (v->lblastcss != NULL)
     323         828 :         FREE(v->lblastcss);
     324     1411656 :     if (v->lblastcp != NULL)
     325         828 :         FREE(v->lblastcp);
     326             : 
     327     1411656 :     return st;
     328             : }
     329             : 
     330             : /*
     331             :  * getsubdfa - create or re-fetch the DFA for a tree subre node
     332             :  *
     333             :  * We only need to create the DFA once per overall regex execution.
     334             :  * The DFA will be freed by the cleanup step in pg_regexec().
     335             :  */
     336             : static struct dfa *
     337        6192 : getsubdfa(struct vars *v,
     338             :           struct subre *t)
     339             : {
     340        6192 :     if (v->subdfas[t->id] == NULL)
     341             :     {
     342        4900 :         v->subdfas[t->id] = newdfa(v, &t->cnfa, &v->g->cmap, DOMALLOC);
     343        4900 :         if (ISERR())
     344           0 :             return NULL;
     345             :     }
     346        6192 :     return v->subdfas[t->id];
     347             : }
     348             : 
     349             : /*
     350             :  * getladfa - create or re-fetch the DFA for a LACON subre node
     351             :  *
     352             :  * Same as above, but for LACONs.
     353             :  */
     354             : static struct dfa *
     355         108 : getladfa(struct vars *v,
     356             :          int n)
     357             : {
     358             :     assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);
     359             : 
     360         108 :     if (v->ladfas[n] == NULL)
     361             :     {
     362          52 :         struct subre *sub = &v->g->lacons[n];
     363             : 
     364          52 :         v->ladfas[n] = newdfa(v, &sub->cnfa, &v->g->cmap, DOMALLOC);
     365          52 :         if (ISERR())
     366           0 :             return NULL;
     367             :     }
     368         108 :     return v->ladfas[n];
     369             : }
     370             : 
     371             : /*
     372             :  * find - find a match for the main NFA (no-complications case)
     373             :  */
     374             : static int
     375     1411580 : find(struct vars *v,
     376             :      struct cnfa *cnfa,
     377             :      struct colormap *cm)
     378             : {
     379             :     struct dfa *s;
     380             :     struct dfa *d;
     381             :     chr        *begin;
     382     1411580 :     chr        *end = NULL;
     383             :     chr        *cold;
     384             :     chr        *open;           /* open and close of range of possible starts */
     385             :     chr        *close;
     386             :     int         hitend;
     387     1411580 :     int         shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;
     388             : 
     389             :     /* first, a shot with the search RE */
     390     1411580 :     s = newdfa(v, &v->g->search, cm, &v->dfa1);
     391             :     assert(!(ISERR() && s != NULL));
     392     1411580 :     NOERR();
     393             :     MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
     394     1411580 :     cold = NULL;
     395     1411580 :     close = shortest(v, s, v->search_start, v->search_start, v->stop,
     396             :                      &cold, (int *) NULL);
     397     1411580 :     freedfa(s);
     398     1411580 :     NOERR();
     399     1411580 :     if (v->g->cflags & REG_EXPECT)
     400             :     {
     401             :         assert(v->details != NULL);
     402           0 :         if (cold != NULL)
     403           0 :             v->details->rm_extend.rm_so = OFF(cold);
     404             :         else
     405           0 :             v->details->rm_extend.rm_so = OFF(v->stop);
     406           0 :         v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
     407             :     }
     408     1411580 :     if (close == NULL)          /* not found */
     409      390208 :         return REG_NOMATCH;
     410     1021372 :     if (v->nmatch == 0)          /* found, don't need exact location */
     411      218670 :         return REG_OKAY;
     412             : 
     413             :     /* find starting point and match */
     414             :     assert(cold != NULL);
     415      802702 :     open = cold;
     416      802702 :     cold = NULL;
     417             :     MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
     418      802702 :     d = newdfa(v, cnfa, cm, &v->dfa1);
     419             :     assert(!(ISERR() && d != NULL));
     420      802702 :     NOERR();
     421      802732 :     for (begin = open; begin <= close; begin++)
     422             :     {
     423             :         MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
     424      802732 :         if (shorter)
     425          54 :             end = shortest(v, d, begin, begin, v->stop,
     426             :                            (chr **) NULL, &hitend);
     427             :         else
     428      802678 :             end = longest(v, d, begin, v->stop, &hitend);
     429      802732 :         if (ISERR())
     430             :         {
     431           0 :             freedfa(d);
     432           0 :             return v->err;
     433             :         }
     434      802732 :         if (hitend && cold == NULL)
     435         944 :             cold = begin;
     436      802732 :         if (end != NULL)
     437      802702 :             break;              /* NOTE BREAK OUT */
     438             :     }
     439             :     assert(end != NULL);        /* search RE succeeded so loop should */
     440      802702 :     freedfa(d);
     441             : 
     442             :     /* and pin down details */
     443             :     assert(v->nmatch > 0);
     444      802702 :     v->pmatch[0].rm_so = OFF(begin);
     445      802702 :     v->pmatch[0].rm_eo = OFF(end);
     446      802702 :     if (v->g->cflags & REG_EXPECT)
     447             :     {
     448           0 :         if (cold != NULL)
     449           0 :             v->details->rm_extend.rm_so = OFF(cold);
     450             :         else
     451           0 :             v->details->rm_extend.rm_so = OFF(v->stop);
     452           0 :         v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
     453             :     }
     454      802702 :     if (v->nmatch == 1)          /* no need for submatches */
     455      801162 :         return REG_OKAY;
     456             : 
     457             :     /* find submatches */
     458        1540 :     zapallsubs(v->pmatch, v->nmatch);
     459        1540 :     return cdissect(v, v->g->tree, begin, end);
     460             : }
     461             : 
     462             : /*
     463             :  * cfind - find a match for the main NFA (with complications)
     464             :  */
     465             : static int
     466          76 : cfind(struct vars *v,
     467             :       struct cnfa *cnfa,
     468             :       struct colormap *cm)
     469             : {
     470             :     struct dfa *s;
     471             :     struct dfa *d;
     472             :     chr        *cold;
     473             :     int         ret;
     474             : 
     475          76 :     s = newdfa(v, &v->g->search, cm, &v->dfa1);
     476          76 :     NOERR();
     477          76 :     d = newdfa(v, cnfa, cm, &v->dfa2);
     478          76 :     if (ISERR())
     479             :     {
     480             :         assert(d == NULL);
     481           0 :         freedfa(s);
     482           0 :         return v->err;
     483             :     }
     484             : 
     485          76 :     ret = cfindloop(v, cnfa, cm, d, s, &cold);
     486             : 
     487          76 :     freedfa(d);
     488          76 :     freedfa(s);
     489          76 :     NOERR();
     490          76 :     if (v->g->cflags & REG_EXPECT)
     491             :     {
     492             :         assert(v->details != NULL);
     493           0 :         if (cold != NULL)
     494           0 :             v->details->rm_extend.rm_so = OFF(cold);
     495             :         else
     496           0 :             v->details->rm_extend.rm_so = OFF(v->stop);
     497           0 :         v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
     498             :     }
     499          76 :     return ret;
     500             : }
     501             : 
     502             : /*
     503             :  * cfindloop - the heart of cfind
     504             :  */
     505             : static int
     506          76 : cfindloop(struct vars *v,
     507             :           struct cnfa *cnfa,
     508             :           struct colormap *cm,
     509             :           struct dfa *d,
     510             :           struct dfa *s,
     511             :           chr **coldp)          /* where to put coldstart pointer */
     512             : {
     513             :     chr        *begin;
     514             :     chr        *end;
     515             :     chr        *cold;
     516             :     chr        *open;           /* open and close of range of possible starts */
     517             :     chr        *close;
     518             :     chr        *estart;
     519             :     chr        *estop;
     520             :     int         er;
     521          76 :     int         shorter = v->g->tree->flags & SHORTER;
     522             :     int         hitend;
     523             : 
     524             :     assert(d != NULL && s != NULL);
     525          76 :     cold = NULL;
     526          76 :     close = v->search_start;
     527             :     do
     528             :     {
     529             :         /* Search with the search RE for match range at/beyond "close" */
     530             :         MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
     531          76 :         close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
     532          76 :         if (ISERR())
     533             :         {
     534           0 :             *coldp = cold;
     535           0 :             return v->err;
     536             :         }
     537          76 :         if (close == NULL)
     538           4 :             break;              /* no more possible match anywhere */
     539             :         assert(cold != NULL);
     540          72 :         open = cold;
     541          72 :         cold = NULL;
     542             :         /* Search for matches starting between "open" and "close" inclusive */
     543             :         MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
     544         312 :         for (begin = open; begin <= close; begin++)
     545             :         {
     546             :             MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
     547         280 :             estart = begin;
     548         280 :             estop = v->stop;
     549             :             for (;;)
     550             :             {
     551             :                 /* Here we use the top node's detailed RE */
     552         504 :                 if (shorter)
     553         128 :                     end = shortest(v, d, begin, estart,
     554             :                                    estop, (chr **) NULL, &hitend);
     555             :                 else
     556         264 :                     end = longest(v, d, begin, estop,
     557             :                                   &hitend);
     558         392 :                 if (ISERR())
     559             :                 {
     560           0 :                     *coldp = cold;
     561           0 :                     return v->err;
     562             :                 }
     563         392 :                 if (hitend && cold == NULL)
     564          60 :                     cold = begin;
     565         392 :                 if (end == NULL)
     566         216 :                     break;      /* no match with this begin point, try next */
     567             :                 MDEBUG(("tentative end %ld\n", LOFF(end)));
     568             :                 /* Dissect the potential match to see if it really matches */
     569         176 :                 zapallsubs(v->pmatch, v->nmatch);
     570         176 :                 er = cdissect(v, v->g->tree, begin, end);
     571         176 :                 if (er == REG_OKAY)
     572             :                 {
     573          40 :                     if (v->nmatch > 0)
     574             :                     {
     575          40 :                         v->pmatch[0].rm_so = OFF(begin);
     576          40 :                         v->pmatch[0].rm_eo = OFF(end);
     577             :                     }
     578          40 :                     *coldp = cold;
     579          40 :                     return REG_OKAY;
     580             :                 }
     581         136 :                 if (er != REG_NOMATCH)
     582             :                 {
     583           0 :                     ERR(er);
     584           0 :                     *coldp = cold;
     585           0 :                     return er;
     586             :                 }
     587             :                 /* Try next longer/shorter match with same begin point */
     588         136 :                 if (shorter)
     589             :                 {
     590         108 :                     if (end == estop)
     591          16 :                         break;  /* no more, so try next begin point */
     592          92 :                     estart = end + 1;
     593             :                 }
     594             :                 else
     595             :                 {
     596          28 :                     if (end == begin)
     597           8 :                         break;  /* no more, so try next begin point */
     598          20 :                     estop = end - 1;
     599             :                 }
     600             :             }                   /* end loop over endpoint positions */
     601             :         }                       /* end loop over beginning positions */
     602             : 
     603             :         /*
     604             :          * If we get here, there is no possible match starting at or before
     605             :          * "close", so consider matches beyond that.  We'll do a fresh search
     606             :          * with the search RE to find a new promising match range.
     607             :          */
     608          32 :         close++;
     609          32 :     } while (close < v->stop);
     610             : 
     611          36 :     *coldp = cold;
     612          36 :     return REG_NOMATCH;
     613             : }
     614             : 
     615             : /*
     616             :  * zapallsubs - initialize all subexpression matches to "no match"
     617             :  */
     618             : static void
     619        1724 : zapallsubs(regmatch_t *p,
     620             :            size_t n)
     621             : {
     622             :     size_t      i;
     623             : 
     624       10264 :     for (i = n - 1; i > 0; i--)
     625             :     {
     626        8540 :         p[i].rm_so = -1;
     627        8540 :         p[i].rm_eo = -1;
     628             :     }
     629        1724 : }
     630             : 
     631             : /*
     632             :  * zaptreesubs - initialize subexpressions within subtree to "no match"
     633             :  */
     634             : static void
     635       14878 : zaptreesubs(struct vars *v,
     636             :             struct subre *t)
     637             : {
     638       14878 :     if (t->op == '(')
     639             :     {
     640        2514 :         int         n = t->subno;
     641             : 
     642             :         assert(n > 0);
     643        2514 :         if ((size_t) n < v->nmatch)
     644             :         {
     645        2498 :             v->pmatch[n].rm_so = -1;
     646        2498 :             v->pmatch[n].rm_eo = -1;
     647             :         }
     648             :     }
     649             : 
     650       14878 :     if (t->left != NULL)
     651        6018 :         zaptreesubs(v, t->left);
     652       14878 :     if (t->right != NULL)
     653        3224 :         zaptreesubs(v, t->right);
     654       14878 : }
     655             : 
     656             : /*
     657             :  * subset - set subexpression match data for a successful subre
     658             :  */
     659             : static void
     660        1206 : subset(struct vars *v,
     661             :        struct subre *sub,
     662             :        chr *begin,
     663             :        chr *end)
     664             : {
     665        1206 :     int         n = sub->subno;
     666             : 
     667             :     assert(n > 0);
     668        1206 :     if ((size_t) n >= v->nmatch)
     669          12 :         return;
     670             : 
     671             :     MDEBUG(("setting %d\n", n));
     672        1194 :     v->pmatch[n].rm_so = OFF(begin);
     673        1194 :     v->pmatch[n].rm_eo = OFF(end);
     674             : }
     675             : 
     676             : /*
     677             :  * cdissect - check backrefs and determine subexpression matches
     678             :  *
     679             :  * cdissect recursively processes a subre tree to check matching of backrefs
     680             :  * and/or identify submatch boundaries for capture nodes.  The proposed match
     681             :  * runs from "begin" to "end" (not including "end"), and we are basically
     682             :  * "dissecting" it to see where the submatches are.
     683             :  *
     684             :  * Before calling any level of cdissect, the caller must have run the node's
     685             :  * DFA and found that the proposed substring satisfies the DFA.  (We make
     686             :  * the caller do that because in concatenation and iteration nodes, it's
     687             :  * much faster to check all the substrings against the child DFAs before we
     688             :  * recurse.)  Also, caller must have cleared subexpression match data via
     689             :  * zaptreesubs (or zapallsubs at the top level).
     690             :  */
     691             : static int                      /* regexec return code */
     692        9006 : cdissect(struct vars *v,
     693             :          struct subre *t,
     694             :          chr *begin,            /* beginning of relevant substring */
     695             :          chr *end)              /* end of same */
     696             : {
     697             :     int         er;
     698             : 
     699             :     assert(t != NULL);
     700             :     MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
     701             : 
     702             :     /* handy place to check for operation cancel */
     703        9006 :     if (CANCEL_REQUESTED(v->re))
     704           0 :         return REG_CANCEL;
     705             :     /* ... and stack overrun */
     706        9006 :     if (STACK_TOO_DEEP(v->re))
     707           0 :         return REG_ETOOBIG;
     708             : 
     709        9006 :     switch (t->op)
     710             :     {
     711             :         case '=':               /* terminal node */
     712             :             assert(t->left == NULL && t->right == NULL);
     713        4358 :             er = REG_OKAY;      /* no action, parent did the work */
     714        4358 :             break;
     715             :         case 'b':               /* back reference */
     716             :             assert(t->left == NULL && t->right == NULL);
     717         216 :             er = cbrdissect(v, t, begin, end);
     718         216 :             break;
     719             :         case '.':               /* concatenation */
     720             :             assert(t->left != NULL && t->right != NULL);
     721        3062 :             if (t->left->flags & SHORTER) /* reverse scan */
     722         292 :                 er = crevcondissect(v, t, begin, end);
     723             :             else
     724        2770 :                 er = ccondissect(v, t, begin, end);
     725        3062 :             break;
     726             :         case '|':               /* alternation */
     727             :             assert(t->left != NULL);
     728          12 :             er = caltdissect(v, t, begin, end);
     729          12 :             break;
     730             :         case '*':               /* iteration */
     731             :             assert(t->left != NULL);
     732          48 :             if (t->left->flags & SHORTER) /* reverse scan */
     733           4 :                 er = creviterdissect(v, t, begin, end);
     734             :             else
     735          44 :                 er = citerdissect(v, t, begin, end);
     736          48 :             break;
     737             :         case '(':               /* capturing */
     738             :             assert(t->left != NULL && t->right == NULL);
     739             :             assert(t->subno > 0);
     740        1310 :             er = cdissect(v, t->left, begin, end);
     741        1310 :             if (er == REG_OKAY)
     742        1206 :                 subset(v, t, begin, end);
     743        1310 :             break;
     744             :         default:
     745           0 :             er = REG_ASSERT;
     746           0 :             break;
     747             :     }
     748             : 
     749             :     /*
     750             :      * We should never have a match failure unless backrefs lurk below;
     751             :      * otherwise, either caller failed to check the DFA, or there's some
     752             :      * inconsistency between the DFA and the node's innards.
     753             :      */
     754             :     assert(er != REG_NOMATCH || (t->flags & BACKR));
     755             : 
     756        9006 :     return er;
     757             : }
     758             : 
     759             : /*
     760             :  * ccondissect - dissect match for concatenation node
     761             :  */
     762             : static int                      /* regexec return code */
     763        2770 : ccondissect(struct vars *v,
     764             :             struct subre *t,
     765             :             chr *begin,         /* beginning of relevant substring */
     766             :             chr *end)           /* end of same */
     767             : {
     768             :     struct dfa *d;
     769             :     struct dfa *d2;
     770             :     chr        *mid;
     771             :     int         er;
     772             : 
     773             :     assert(t->op == '.');
     774             :     assert(t->left != NULL && t->left->cnfa.nstates > 0);
     775             :     assert(t->right != NULL && t->right->cnfa.nstates > 0);
     776             :     assert(!(t->left->flags & SHORTER));
     777             : 
     778        2770 :     d = getsubdfa(v, t->left);
     779        2770 :     NOERR();
     780        2770 :     d2 = getsubdfa(v, t->right);
     781        2770 :     NOERR();
     782             :     MDEBUG(("cconcat %d\n", t->id));
     783             : 
     784             :     /* pick a tentative midpoint */
     785        2770 :     mid = longest(v, d, begin, end, (int *) NULL);
     786        2770 :     NOERR();
     787        2770 :     if (mid == NULL)
     788           0 :         return REG_NOMATCH;
     789             :     MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
     790             : 
     791             :     /* iterate until satisfaction or failure */
     792             :     for (;;)
     793             :     {
     794             :         /* try this midpoint on for size */
     795        2082 :         if (longest(v, d2, mid, end, (int *) NULL) == end)
     796             :         {
     797        2782 :             er = cdissect(v, t->left, begin, mid);
     798        2782 :             if (er == REG_OKAY)
     799             :             {
     800        2594 :                 er = cdissect(v, t->right, mid, end);
     801        2594 :                 if (er == REG_OKAY)
     802             :                 {
     803             :                     /* satisfaction */
     804             :                     MDEBUG(("successful\n"));
     805        2182 :                     return REG_OKAY;
     806             :                 }
     807             :             }
     808         600 :             if (er != REG_NOMATCH)
     809           0 :                 return er;
     810             :         }
     811        2670 :         NOERR();
     812             : 
     813             :         /* that midpoint didn't work, find a new one */
     814        2670 :         if (mid == begin)
     815             :         {
     816             :             /* all possibilities exhausted */
     817             :             MDEBUG(("%d no midpoint\n", t->id));
     818         244 :             return REG_NOMATCH;
     819             :         }
     820        2426 :         mid = longest(v, d, begin, mid - 1, (int *) NULL);
     821        2426 :         NOERR();
     822        2426 :         if (mid == NULL)
     823             :         {
     824             :             /* failed to find a new one */
     825             :             MDEBUG(("%d failed midpoint\n", t->id));
     826         344 :             return REG_NOMATCH;
     827             :         }
     828             :         MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
     829        2082 :         zaptreesubs(v, t->left);
     830        2082 :         zaptreesubs(v, t->right);
     831             :     }
     832             : 
     833             :     /* can't get here */
     834             :     return REG_ASSERT;
     835             : }
     836             : 
     837             : /*
     838             :  * crevcondissect - dissect match for concatenation node, shortest-first
     839             :  */
     840             : static int                      /* regexec return code */
     841         292 : crevcondissect(struct vars *v,
     842             :                struct subre *t,
     843             :                chr *begin,      /* beginning of relevant substring */
     844             :                chr *end)        /* end of same */
     845             : {
     846             :     struct dfa *d;
     847             :     struct dfa *d2;
     848             :     chr        *mid;
     849             :     int         er;
     850             : 
     851             :     assert(t->op == '.');
     852             :     assert(t->left != NULL && t->left->cnfa.nstates > 0);
     853             :     assert(t->right != NULL && t->right->cnfa.nstates > 0);
     854             :     assert(t->left->flags & SHORTER);
     855             : 
     856         292 :     d = getsubdfa(v, t->left);
     857         292 :     NOERR();
     858         292 :     d2 = getsubdfa(v, t->right);
     859         292 :     NOERR();
     860             :     MDEBUG(("crevcon %d\n", t->id));
     861             : 
     862             :     /* pick a tentative midpoint */
     863         292 :     mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
     864         292 :     NOERR();
     865         292 :     if (mid == NULL)
     866           0 :         return REG_NOMATCH;
     867             :     MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
     868             : 
     869             :     /* iterate until satisfaction or failure */
     870             :     for (;;)
     871             :     {
     872             :         /* try this midpoint on for size */
     873         700 :         if (longest(v, d2, mid, end, (int *) NULL) == end)
     874             :         {
     875         292 :             er = cdissect(v, t->left, begin, mid);
     876         292 :             if (er == REG_OKAY)
     877             :             {
     878         228 :                 er = cdissect(v, t->right, mid, end);
     879         228 :                 if (er == REG_OKAY)
     880             :                 {
     881             :                     /* satisfaction */
     882             :                     MDEBUG(("successful\n"));
     883         120 :                     return REG_OKAY;
     884             :                 }
     885             :             }
     886         172 :             if (er != REG_NOMATCH)
     887           0 :                 return er;
     888             :         }
     889         872 :         NOERR();
     890             : 
     891             :         /* that midpoint didn't work, find a new one */
     892         872 :         if (mid == end)
     893             :         {
     894             :             /* all possibilities exhausted */
     895             :             MDEBUG(("%d no midpoint\n", t->id));
     896         172 :             return REG_NOMATCH;
     897             :         }
     898         700 :         mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
     899         700 :         NOERR();
     900         700 :         if (mid == NULL)
     901             :         {
     902             :             /* failed to find a new one */
     903             :             MDEBUG(("%d failed midpoint\n", t->id));
     904           0 :             return REG_NOMATCH;
     905             :         }
     906             :         MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
     907         700 :         zaptreesubs(v, t->left);
     908         700 :         zaptreesubs(v, t->right);
     909             :     }
     910             : 
     911             :     /* can't get here */
     912             :     return REG_ASSERT;
     913             : }
     914             : 
     915             : /*
     916             :  * cbrdissect - dissect match for backref node
     917             :  */
     918             : static int                      /* regexec return code */
     919         216 : cbrdissect(struct vars *v,
     920             :            struct subre *t,
     921             :            chr *begin,          /* beginning of relevant substring */
     922             :            chr *end)            /* end of same */
     923             : {
     924         216 :     int         n = t->subno;
     925             :     size_t      numreps;
     926             :     size_t      tlen;
     927             :     size_t      brlen;
     928             :     chr        *brstring;
     929             :     chr        *p;
     930         216 :     int         min = t->min;
     931         216 :     int         max = t->max;
     932             : 
     933             :     assert(t != NULL);
     934             :     assert(t->op == 'b');
     935             :     assert(n >= 0);
     936             :     assert((size_t) n < v->nmatch);
     937             : 
     938             :     MDEBUG(("cbackref n%d %d{%d-%d}\n", t->id, n, min, max));
     939             : 
     940             :     /* get the backreferenced string */
     941         216 :     if (v->pmatch[n].rm_so == -1)
     942           8 :         return REG_NOMATCH;
     943         208 :     brstring = v->start + v->pmatch[n].rm_so;
     944         208 :     brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
     945             : 
     946             :     /* special cases for zero-length strings */
     947         208 :     if (brlen == 0)
     948             :     {
     949             :         /*
     950             :          * matches only if target is zero length, but any number of
     951             :          * repetitions can be considered to be present
     952             :          */
     953           8 :         if (begin == end && min <= max)
     954             :         {
     955             :             MDEBUG(("cbackref matched trivially\n"));
     956           8 :             return REG_OKAY;
     957             :         }
     958           0 :         return REG_NOMATCH;
     959             :     }
     960         200 :     if (begin == end)
     961             :     {
     962             :         /* matches only if zero repetitions are okay */
     963           4 :         if (min == 0)
     964             :         {
     965             :             MDEBUG(("cbackref matched trivially\n"));
     966           4 :             return REG_OKAY;
     967             :         }
     968           0 :         return REG_NOMATCH;
     969             :     }
     970             : 
     971             :     /*
     972             :      * check target length to see if it could possibly be an allowed number of
     973             :      * repetitions of brstring
     974             :      */
     975             :     assert(end > begin);
     976         196 :     tlen = end - begin;
     977         196 :     if (tlen % brlen != 0)
     978          24 :         return REG_NOMATCH;
     979         172 :     numreps = tlen / brlen;
     980         172 :     if (numreps < min || (numreps > max && max != DUPINF))
     981           0 :         return REG_NOMATCH;
     982             : 
     983             :     /* okay, compare the actual string contents */
     984         172 :     p = begin;
     985         408 :     while (numreps-- > 0)
     986             :     {
     987         192 :         if ((*v->g->compare) (brstring, p, brlen) != 0)
     988         128 :             return REG_NOMATCH;
     989          64 :         p += brlen;
     990             :     }
     991             : 
     992             :     MDEBUG(("cbackref matched\n"));
     993          44 :     return REG_OKAY;
     994             : }
     995             : 
     996             : /*
     997             :  * caltdissect - dissect match for alternation node
     998             :  */
     999             : static int                      /* regexec return code */
    1000          12 : caltdissect(struct vars *v,
    1001             :             struct subre *t,
    1002             :             chr *begin,         /* beginning of relevant substring */
    1003             :             chr *end)           /* end of same */
    1004             : {
    1005             :     struct dfa *d;
    1006             :     int         er;
    1007             : 
    1008             :     /* We loop, rather than tail-recurse, to handle a chain of alternatives */
    1009          40 :     while (t != NULL)
    1010             :     {
    1011             :         assert(t->op == '|');
    1012             :         assert(t->left != NULL && t->left->cnfa.nstates > 0);
    1013             : 
    1014             :         MDEBUG(("calt n%d\n", t->id));
    1015             : 
    1016          20 :         d = getsubdfa(v, t->left);
    1017          20 :         NOERR();
    1018          20 :         if (longest(v, d, begin, end, (int *) NULL) == end)
    1019             :         {
    1020             :             MDEBUG(("calt matched\n"));
    1021          12 :             er = cdissect(v, t->left, begin, end);
    1022          12 :             if (er != REG_NOMATCH)
    1023           4 :                 return er;
    1024             :         }
    1025          16 :         NOERR();
    1026             : 
    1027          16 :         t = t->right;
    1028             :     }
    1029             : 
    1030           8 :     return REG_NOMATCH;
    1031             : }
    1032             : 
    1033             : /*
    1034             :  * citerdissect - dissect match for iteration node
    1035             :  */
    1036             : static int                      /* regexec return code */
    1037          44 : citerdissect(struct vars *v,
    1038             :              struct subre *t,
    1039             :              chr *begin,        /* beginning of relevant substring */
    1040             :              chr *end)          /* end of same */
    1041             : {
    1042             :     struct dfa *d;
    1043             :     chr       **endpts;
    1044             :     chr        *limit;
    1045             :     int         min_matches;
    1046             :     size_t      max_matches;
    1047             :     int         nverified;
    1048             :     int         k;
    1049             :     int         i;
    1050             :     int         er;
    1051             : 
    1052             :     assert(t->op == '*');
    1053             :     assert(t->left != NULL && t->left->cnfa.nstates > 0);
    1054             :     assert(!(t->left->flags & SHORTER));
    1055             :     assert(begin <= end);
    1056             : 
    1057             :     /*
    1058             :      * For the moment, assume the minimum number of matches is 1.  If zero
    1059             :      * matches are allowed, and the target string is empty, we are allowed to
    1060             :      * match regardless of the contents of the iter node --- but we would
    1061             :      * prefer to match once, so that capturing parens get set.  (An example of
    1062             :      * the concern here is a pattern like "()*\1", which historically this
    1063             :      * code has allowed to succeed.)  Therefore, we deal with the zero-matches
    1064             :      * case at the bottom, after failing to find any other way to match.
    1065             :      */
    1066          44 :     min_matches = t->min;
    1067          44 :     if (min_matches <= 0)
    1068           8 :         min_matches = 1;
    1069             : 
    1070             :     /*
    1071             :      * We need workspace to track the endpoints of each sub-match.  Normally
    1072             :      * we consider only nonzero-length sub-matches, so there can be at most
    1073             :      * end-begin of them.  However, if min is larger than that, we will also
    1074             :      * consider zero-length sub-matches in order to find enough matches.
    1075             :      *
    1076             :      * For convenience, endpts[0] contains the "begin" pointer and we store
    1077             :      * sub-match endpoints in endpts[1..max_matches].
    1078             :      */
    1079          44 :     max_matches = end - begin;
    1080          44 :     if (max_matches > t->max && t->max != DUPINF)
    1081           0 :         max_matches = t->max;
    1082          44 :     if (max_matches < min_matches)
    1083           8 :         max_matches = min_matches;
    1084          44 :     endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    1085          44 :     if (endpts == NULL)
    1086           0 :         return REG_ESPACE;
    1087          44 :     endpts[0] = begin;
    1088             : 
    1089          44 :     d = getsubdfa(v, t->left);
    1090          44 :     if (ISERR())
    1091             :     {
    1092           0 :         FREE(endpts);
    1093           0 :         return v->err;
    1094             :     }
    1095             :     MDEBUG(("citer %d\n", t->id));
    1096             : 
    1097             :     /*
    1098             :      * Our strategy is to first find a set of sub-match endpoints that are
    1099             :      * valid according to the child node's DFA, and then recursively dissect
    1100             :      * each sub-match to confirm validity.  If any validity check fails,
    1101             :      * backtrack the last sub-match and try again.  And, when we next try for
    1102             :      * a validity check, we need not recheck any successfully verified
    1103             :      * sub-matches that we didn't move the endpoints of.  nverified remembers
    1104             :      * how many sub-matches are currently known okay.
    1105             :      */
    1106             : 
    1107             :     /* initialize to consider first sub-match */
    1108          44 :     nverified = 0;
    1109          44 :     k = 1;
    1110          44 :     limit = end;
    1111             : 
    1112             :     /* iterate until satisfaction or failure */
    1113         448 :     while (k > 0)
    1114             :     {
    1115             :         /* try to find an endpoint for the k'th sub-match */
    1116         372 :         endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL);
    1117         372 :         if (ISERR())
    1118             :         {
    1119           0 :             FREE(endpts);
    1120           0 :             return v->err;
    1121             :         }
    1122         372 :         if (endpts[k] == NULL)
    1123             :         {
    1124             :             /* no match possible, so see if we can shorten previous one */
    1125         172 :             k--;
    1126         172 :             goto backtrack;
    1127             :         }
    1128             :         MDEBUG(("%d: working endpoint %d: %ld\n",
    1129             :                 t->id, k, LOFF(endpts[k])));
    1130             : 
    1131             :         /* k'th sub-match can no longer be considered verified */
    1132         200 :         if (nverified >= k)
    1133           8 :             nverified = k - 1;
    1134             : 
    1135         200 :         if (endpts[k] != end)
    1136             :         {
    1137             :             /* haven't reached end yet, try another iteration if allowed */
    1138         148 :             if (k >= max_matches)
    1139             :             {
    1140             :                 /* must try to shorten some previous match */
    1141           0 :                 k--;
    1142           0 :                 goto backtrack;
    1143             :             }
    1144             : 
    1145             :             /* reject zero-length match unless necessary to achieve min */
    1146         148 :             if (endpts[k] == endpts[k - 1] &&
    1147           0 :                 (k >= min_matches || min_matches - k < end - endpts[k]))
    1148             :                 goto backtrack;
    1149             : 
    1150         148 :             k++;
    1151         148 :             limit = end;
    1152         148 :             continue;
    1153             :         }
    1154             : 
    1155             :         /*
    1156             :          * We've identified a way to divide the string into k sub-matches that
    1157             :          * works so far as the child DFA can tell.  If k is an allowed number
    1158             :          * of matches, start the slow part: recurse to verify each sub-match.
    1159             :          * We always have k <= max_matches, needn't check that.
    1160             :          */
    1161          52 :         if (k < min_matches)
    1162           0 :             goto backtrack;
    1163             : 
    1164             :         MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
    1165             : 
    1166         160 :         for (i = nverified + 1; i <= k; i++)
    1167             :         {
    1168          68 :             zaptreesubs(v, t->left);
    1169          68 :             er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
    1170          68 :             if (er == REG_OKAY)
    1171             :             {
    1172          28 :                 nverified = i;
    1173          28 :                 continue;
    1174             :             }
    1175          40 :             if (er == REG_NOMATCH)
    1176          40 :                 break;
    1177             :             /* oops, something failed */
    1178           0 :             FREE(endpts);
    1179           0 :             return er;
    1180             :         }
    1181             : 
    1182          52 :         if (i > k)
    1183             :         {
    1184             :             /* satisfaction */
    1185             :             MDEBUG(("%d successful\n", t->id));
    1186          12 :             FREE(endpts);
    1187          12 :             return REG_OKAY;
    1188             :         }
    1189             : 
    1190             :         /* match failed to verify, so backtrack */
    1191             : 
    1192             : backtrack:
    1193             : 
    1194             :         /*
    1195             :          * Must consider shorter versions of the current sub-match.  However,
    1196             :          * we'll only ask for a zero-length match if necessary.
    1197             :          */
    1198         424 :         while (k > 0)
    1199             :         {
    1200         180 :             chr        *prev_end = endpts[k - 1];
    1201             : 
    1202         180 :             if (endpts[k] > prev_end)
    1203             :             {
    1204         180 :                 limit = endpts[k] - 1;
    1205         180 :                 if (limit > prev_end ||
    1206           0 :                     (k < min_matches && min_matches - k >= end - prev_end))
    1207             :                 {
    1208             :                     /* break out of backtrack loop, continue the outer one */
    1209             :                     break;
    1210             :                 }
    1211             :             }
    1212             :             /* can't shorten k'th sub-match any more, consider previous one */
    1213           0 :             k--;
    1214             :         }
    1215             :     }
    1216             : 
    1217             :     /* all possibilities exhausted */
    1218          32 :     FREE(endpts);
    1219             : 
    1220             :     /*
    1221             :      * Now consider the possibility that we can match to a zero-length string
    1222             :      * by using zero repetitions.
    1223             :      */
    1224          32 :     if (t->min == 0 && begin == end)
    1225             :     {
    1226             :         MDEBUG(("%d allowing zero matches\n", t->id));
    1227           4 :         return REG_OKAY;
    1228             :     }
    1229             : 
    1230             :     MDEBUG(("%d failed\n", t->id));
    1231          28 :     return REG_NOMATCH;
    1232             : }
    1233             : 
    1234             : /*
    1235             :  * creviterdissect - dissect match for iteration node, shortest-first
    1236             :  */
    1237             : static int                      /* regexec return code */
    1238           4 : creviterdissect(struct vars *v,
    1239             :                 struct subre *t,
    1240             :                 chr *begin,     /* beginning of relevant substring */
    1241             :                 chr *end)       /* end of same */
    1242             : {
    1243             :     struct dfa *d;
    1244             :     chr       **endpts;
    1245             :     chr        *limit;
    1246             :     int         min_matches;
    1247             :     size_t      max_matches;
    1248             :     int         nverified;
    1249             :     int         k;
    1250             :     int         i;
    1251             :     int         er;
    1252             : 
    1253             :     assert(t->op == '*');
    1254             :     assert(t->left != NULL && t->left->cnfa.nstates > 0);
    1255             :     assert(t->left->flags & SHORTER);
    1256             :     assert(begin <= end);
    1257             : 
    1258             :     /*
    1259             :      * If zero matches are allowed, and target string is empty, just declare
    1260             :      * victory.  OTOH, if target string isn't empty, zero matches can't work
    1261             :      * so we pretend the min is 1.
    1262             :      */
    1263           4 :     min_matches = t->min;
    1264           4 :     if (min_matches <= 0)
    1265             :     {
    1266           4 :         if (begin == end)
    1267           0 :             return REG_OKAY;
    1268           4 :         min_matches = 1;
    1269             :     }
    1270             : 
    1271             :     /*
    1272             :      * We need workspace to track the endpoints of each sub-match.  Normally
    1273             :      * we consider only nonzero-length sub-matches, so there can be at most
    1274             :      * end-begin of them.  However, if min is larger than that, we will also
    1275             :      * consider zero-length sub-matches in order to find enough matches.
    1276             :      *
    1277             :      * For convenience, endpts[0] contains the "begin" pointer and we store
    1278             :      * sub-match endpoints in endpts[1..max_matches].
    1279             :      */
    1280           4 :     max_matches = end - begin;
    1281           4 :     if (max_matches > t->max && t->max != DUPINF)
    1282           4 :         max_matches = t->max;
    1283           4 :     if (max_matches < min_matches)
    1284           0 :         max_matches = min_matches;
    1285           4 :     endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    1286           4 :     if (endpts == NULL)
    1287           0 :         return REG_ESPACE;
    1288           4 :     endpts[0] = begin;
    1289             : 
    1290           4 :     d = getsubdfa(v, t->left);
    1291           4 :     if (ISERR())
    1292             :     {
    1293           0 :         FREE(endpts);
    1294           0 :         return v->err;
    1295             :     }
    1296             :     MDEBUG(("creviter %d\n", t->id));
    1297             : 
    1298             :     /*
    1299             :      * Our strategy is to first find a set of sub-match endpoints that are
    1300             :      * valid according to the child node's DFA, and then recursively dissect
    1301             :      * each sub-match to confirm validity.  If any validity check fails,
    1302             :      * backtrack the last sub-match and try again.  And, when we next try for
    1303             :      * a validity check, we need not recheck any successfully verified
    1304             :      * sub-matches that we didn't move the endpoints of.  nverified remembers
    1305             :      * how many sub-matches are currently known okay.
    1306             :      */
    1307             : 
    1308             :     /* initialize to consider first sub-match */
    1309           4 :     nverified = 0;
    1310           4 :     k = 1;
    1311           4 :     limit = begin;
    1312             : 
    1313             :     /* iterate until satisfaction or failure */
    1314           8 :     while (k > 0)
    1315             :     {
    1316             :         /* disallow zero-length match unless necessary to achieve min */
    1317           4 :         if (limit == endpts[k - 1] &&
    1318           4 :             limit != end &&
    1319           0 :             (k >= min_matches || min_matches - k < end - limit))
    1320           4 :             limit++;
    1321             : 
    1322             :         /* if this is the last allowed sub-match, it must reach to the end */
    1323           4 :         if (k >= max_matches)
    1324           4 :             limit = end;
    1325             : 
    1326             :         /* try to find an endpoint for the k'th sub-match */
    1327           4 :         endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
    1328             :                              (chr **) NULL, (int *) NULL);
    1329           4 :         if (ISERR())
    1330             :         {
    1331           0 :             FREE(endpts);
    1332           0 :             return v->err;
    1333             :         }
    1334           4 :         if (endpts[k] == NULL)
    1335             :         {
    1336             :             /* no match possible, so see if we can lengthen previous one */
    1337           0 :             k--;
    1338           0 :             goto backtrack;
    1339             :         }
    1340             :         MDEBUG(("%d: working endpoint %d: %ld\n",
    1341             :                 t->id, k, LOFF(endpts[k])));
    1342             : 
    1343             :         /* k'th sub-match can no longer be considered verified */
    1344           4 :         if (nverified >= k)
    1345           0 :             nverified = k - 1;
    1346             : 
    1347           4 :         if (endpts[k] != end)
    1348             :         {
    1349             :             /* haven't reached end yet, try another iteration if allowed */
    1350           0 :             if (k >= max_matches)
    1351             :             {
    1352             :                 /* must try to lengthen some previous match */
    1353           0 :                 k--;
    1354           0 :                 goto backtrack;
    1355             :             }
    1356             : 
    1357           0 :             k++;
    1358           0 :             limit = endpts[k - 1];
    1359           0 :             continue;
    1360             :         }
    1361             : 
    1362             :         /*
    1363             :          * We've identified a way to divide the string into k sub-matches that
    1364             :          * works so far as the child DFA can tell.  If k is an allowed number
    1365             :          * of matches, start the slow part: recurse to verify each sub-match.
    1366             :          * We always have k <= max_matches, needn't check that.
    1367             :          */
    1368           4 :         if (k < min_matches)
    1369           0 :             goto backtrack;
    1370             : 
    1371             :         MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
    1372             : 
    1373          16 :         for (i = nverified + 1; i <= k; i++)
    1374             :         {
    1375           4 :             zaptreesubs(v, t->left);
    1376           4 :             er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
    1377           4 :             if (er == REG_OKAY)
    1378             :             {
    1379           4 :                 nverified = i;
    1380           4 :                 continue;
    1381             :             }
    1382           0 :             if (er == REG_NOMATCH)
    1383           0 :                 break;
    1384             :             /* oops, something failed */
    1385           0 :             FREE(endpts);
    1386           0 :             return er;
    1387             :         }
    1388             : 
    1389           4 :         if (i > k)
    1390             :         {
    1391             :             /* satisfaction */
    1392             :             MDEBUG(("%d successful\n", t->id));
    1393           4 :             FREE(endpts);
    1394           4 :             return REG_OKAY;
    1395             :         }
    1396             : 
    1397             :         /* match failed to verify, so backtrack */
    1398             : 
    1399             : backtrack:
    1400             : 
    1401             :         /*
    1402             :          * Must consider longer versions of the current sub-match.
    1403             :          */
    1404           0 :         while (k > 0)
    1405             :         {
    1406           0 :             if (endpts[k] < end)
    1407             :             {
    1408           0 :                 limit = endpts[k] + 1;
    1409             :                 /* break out of backtrack loop, continue the outer one */
    1410           0 :                 break;
    1411             :             }
    1412             :             /* can't lengthen k'th sub-match any more, consider previous one */
    1413           0 :             k--;
    1414             :         }
    1415             :     }
    1416             : 
    1417             :     /* all possibilities exhausted */
    1418             :     MDEBUG(("%d failed\n", t->id));
    1419           0 :     FREE(endpts);
    1420           0 :     return REG_NOMATCH;
    1421             : }
    1422             : 
    1423             : 
    1424             : 
    1425             : #include "rege_dfa.c"

Generated by: LCOV version 1.13