This graph shows which files directly or indirectly include this file:

Functions
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)

Function Documentation

◆ dfa_backref()

static chr* dfa_backref	(	struct vars *	v,
		struct dfa *	d,
		chr *	start,
		chr *	min,
		chr *	max,
		bool	shortest
	)

static

Definition at line 506 of file rege_dfa.c.

 {
     int         n = d->backno;
     int         backmin = d->backmin;
     int         backmax = d->backmax;
     size_t      numreps;
     size_t      minreps;
     size_t      maxreps;
     size_t      brlen;
     chr        *brstring;
     chr        *p;
  
     /* get the backreferenced string (caller should have checked this) */
     if (v->pmatch[n].rm_so == -1)
         return NULL;
     brstring = v->start + v->pmatch[n].rm_so;
     brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
  
     /* special-case zero-length backreference to avoid divide by zero */
     if (brlen == 0)
     {
         /*
          * matches only a zero-length string, but any number of repetitions
          * can be considered to be present
          */
         if (min == start && backmin <= backmax)
             return start;
         return NULL;
     }
  
     /*
      * convert min and max into numbers of possible repetitions of the backref
      * string, rounding appropriately
      */
     if (min <= start)
         minreps = 0;
     else
         minreps = (min - start - 1) / brlen + 1;
     maxreps = (max - start) / brlen;
  
     /* apply bounds, then see if there is any allowed match length */
     if (minreps < backmin)
         minreps = backmin;
     if (backmax != DUPINF && maxreps > backmax)
         maxreps = backmax;
     if (maxreps < minreps)
         return NULL;
  
     /* quick exit if zero-repetitions match is valid and preferred */
     if (shortest && minreps == 0)
         return start;
  
     /* okay, compare the actual string contents */
     p = start;
     numreps = 0;
     while (numreps < maxreps)
     {
         if ((*v->g->compare) (brstring, p, brlen) != 0)
             break;
         p += brlen;
         numreps++;
         if (shortest && numreps >= minreps)
             break;
     }
  
     if (numreps >= minreps)
         return p;
     return NULL;
 }

References dfa::backmax, dfa::backmin, dfa::backno, DUPINF, vars::g, colormap::max, vars::pmatch, shortest(), vars::start, start, and colormap::v.

Referenced by longest(), and shortest().

◆ freedfa()

static void freedfa ( struct dfa * d )

static

Definition at line 691 of file rege_dfa.c.

 {
     if (d->arraysmalloced)
     {
         if (d->ssets != NULL)
             FREE(d->ssets);
         if (d->statesarea != NULL)
             FREE(d->statesarea);
         if (d->outsarea != NULL)
             FREE(d->outsarea);
         if (d->incarea != NULL)
             FREE(d->incarea);
     }
  
     if (d->ismalloced)
         FREE(d);
 }

References dfa::arraysmalloced, FREE, dfa::incarea, dfa::ismalloced, dfa::outsarea, dfa::ssets, and dfa::statesarea.

Referenced by newdfa().

◆ getvacant()

static struct sset* getvacant	(	struct vars *	v,
		struct dfa *	d,
		chr *	cp,
		chr *	start
	)

static

Definition at line 973 of file rege_dfa.c.

 {
     int         i;
     struct sset *ss;
     struct sset *p;
     struct arcp ap;
     color       co;
  
     ss = pickss(v, d, cp, start);
     if (ss == NULL)
         return NULL;
     assert(!(ss->flags & LOCKED));
  
     /* clear out its inarcs, including self-referential ones */
     ap = ss->ins;
     while ((p = ap.ss) != NULL)
     {
         co = ap.co;
         FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long) co));
         p->outs[co] = NULL;
         ap = p->inchain[co];
         p->inchain[co].ss = NULL;   /* paranoia */
     }
     ss->ins.ss = NULL;
  
     /* take it off the inarc chains of the ssets reached by its outarcs */
     for (i = 0; i < d->ncolors; i++)
     {
         p = ss->outs[i];
         assert(p != ss);        /* not self-referential */
         if (p == NULL)
             continue;           /* NOTE CONTINUE */
         FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets)));
         if (p->ins.ss == ss && p->ins.co == i)
             p->ins = ss->inchain[i];
         else
         {
             struct arcp lastap = {NULL, 0};
  
             assert(p->ins.ss != NULL);
             for (ap = p->ins; ap.ss != NULL &&
                  !(ap.ss == ss && ap.co == i);
                  ap = ap.ss->inchain[ap.co])
                 lastap = ap;
             assert(ap.ss != NULL);
             lastap.ss->inchain[lastap.co] = ss->inchain[i];
         }
         ss->outs[i] = NULL;
         ss->inchain[i].ss = NULL;
     }
  
     /* if ss was a success state, may need to remember location */
     if ((ss->flags & POSTSTATE) && ss->lastseen != d->lastpost &&
         (d->lastpost == NULL || d->lastpost < ss->lastseen))
         d->lastpost = ss->lastseen;
  
     /* likewise for a no-progress state */
     if ((ss->flags & NOPROGRESS) && ss->lastseen != d->lastnopr &&
         (d->lastnopr == NULL || d->lastnopr < ss->lastseen))
         d->lastnopr = ss->lastseen;
  
     return ss;
 }

References assert, arcp::co, FDEBUG, sset::flags, i, sset::inchain, sset::ins, dfa::lastnopr, dfa::lastpost, sset::lastseen, LOCKED, dfa::ncolors, NOPROGRESS, sset::outs, pickss(), POSTSTATE, arcp::ss, dfa::ssets, and start.

Referenced by initialize(), and miss().

◆ hash()

static unsigned hash	(	unsigned *	uv,
		int	n
	)

static

Definition at line 715 of file rege_dfa.c.

 {
     int         i;
     unsigned    h;
  
     h = 0;
     for (i = 0; i < n; i++)
         h ^= uv[i];
     return h;
 }

References i.

Referenced by addHyperLogLog(), agg_refill_hash_table(), be_tls_get_certificate_hash(), bernoulli_nextsampletuple(), calc_key_id(), ChooseTablespace(), compute_partition_hash_value(), delete_item(), dshash_delete_key(), dshash_find(), dshash_find_or_insert(), ExecInitHashJoin(), ExtendBufferedRelShared(), hashagg_batch_read(), hashagg_spill_tuple(), hashing(), InvalidateTSCacheCallBack(), InvalidateVictimBuffer(), json_unique_hash(), jsonb_hash(), jsonb_hash_extended(), jsonb_path_ops__extract_nodes(), JsonbHashScalarValue(), JsonbHashScalarValueExtended(), k_hashes(), lookup_hash_entries(), LookupTupleHashEntry(), LookupTupleHashEntry_internal(), LookupTupleHashEntryHash(), mdc_finish(), mdcbuf_finish(), pgtls_get_peer_certificate_hash(), ResetUnloggedRelationsInDbspaceDir(), saop_element_hash(), satisfies_hash_partition(), sepgsql_avc_compute(), sepgsql_avc_lookup(), system_nextsampleblock(), TupleHashTableHash(), and varstr_abbrev_convert().

◆ initialize()

static struct sset* initialize	(	struct vars *	v,
		struct dfa *	d,
		chr *	start
	)

static

Definition at line 731 of file rege_dfa.c.

 {
     struct sset *ss;
     int         i;
  
     /* is previous one still there? */
     if (d->nssused > 0 && (d->ssets[0].flags & STARTER))
         ss = &d->ssets[0];
     else
     {                           /* no, must (re)build it */
         ss = getvacant(v, d, start, start);
         if (ss == NULL)
             return NULL;
         for (i = 0; i < d->wordsper; i++)
             ss->states[i] = 0;
         BSET(ss->states, d->cnfa->pre);
         ss->hash = HASH(ss->states, d->wordsper);
         assert(d->cnfa->pre != d->cnfa->post);
         ss->flags = STARTER | LOCKED | NOPROGRESS;
         /* lastseen dealt with below */
     }
  
     for (i = 0; i < d->nssused; i++)
         d->ssets[i].lastseen = NULL;
     ss->lastseen = start;       /* maybe untrue, but harmless */
     d->lastpost = NULL;
     d->lastnopr = NULL;
     return ss;
 }

References assert, BSET, dfa::cnfa, sset::flags, getvacant(), HASH, sset::hash, i, dfa::lastnopr, dfa::lastpost, sset::lastseen, LOCKED, NOPROGRESS, dfa::nssused, cnfa::post, cnfa::pre, dfa::ssets, start, STARTER, sset::states, and dfa::wordsper.

Referenced by longest(), matchuntil(), and shortest().

◆ lacon()

static int lacon	(	struct vars *	v,
		struct cnfa *	pcnfa,
		chr *	cp,
		color	co
	)

static

Definition at line 916 of file rege_dfa.c.

 {
     int         n;
     struct subre *sub;
     struct dfa *d;
     chr        *end;
     int         satisfied;
  
     /* Since this is recursive, it could be driven to stack overflow */
     if (STACK_TOO_DEEP(v->re))
     {
         ERR(REG_ETOOBIG);
         return 0;
     }
  
     n = co - pcnfa->ncolors;
     assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);
     FDEBUG(("=== testing lacon %d\n", n));
     sub = &v->g->lacons[n];
     d = getladfa(v, n);
     if (d == NULL)
         return 0;
     if (LATYPE_IS_AHEAD(sub->latype))
     {
         /* used to use longest() here, but shortest() could be much cheaper */
         end = shortest(v, d, cp, cp, v->stop,
                        (chr **) NULL, (int *) NULL);
         satisfied = LATYPE_IS_POS(sub->latype) ? (end != NULL) : (end == NULL);
     }
     else
     {
         /*
          * To avoid doing O(N^2) work when repeatedly testing a lookbehind
          * constraint in an N-character string, we use matchuntil() which can
          * cache the DFA state across calls.  We only need to restart if the
          * probe point decreases, which is not common.  The NFA we're using is
          * a search NFA, so it doesn't mind scanning over stuff before the
          * nominal match.
          */
         satisfied = matchuntil(v, d, cp, &v->lblastcss[n], &v->lblastcp[n]);
         if (!LATYPE_IS_POS(sub->latype))
             satisfied = !satisfied;
     }
     FDEBUG(("=== lacon %d satisfied %d\n", n, satisfied));
     return satisfied;
 }

References assert, ERR, FDEBUG, vars::g, getladfa(), guts::lacons, subre::latype, LATYPE_IS_AHEAD, LATYPE_IS_POS, vars::lblastcp, vars::lblastcss, matchuntil(), cnfa::ncolors, vars::re, REG_ETOOBIG, shortest(), STACK_TOO_DEEP, and vars::stop.

Referenced by miss().

◆ lastcold()

static chr* lastcold	(	struct vars *	v,
		struct dfa *	d
	)

static

Definition at line 585 of file rege_dfa.c.

 {
     struct sset *ss;
     chr        *nopr;
     int         i;
  
     nopr = d->lastnopr;
     if (nopr == NULL)
         nopr = v->start;
     for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
         if ((ss->flags & NOPROGRESS) && nopr < ss->lastseen)
             nopr = ss->lastseen;
     return nopr;
 }

References sset::flags, i, dfa::lastnopr, sset::lastseen, NOPROGRESS, dfa::nssused, dfa::ssets, and vars::start.

Referenced by shortest().

◆ longest()

static chr* longest	(	struct vars *	v,
		struct dfa *	d,
		chr *	start,
		chr *	stop,
		int *	hitstopp
	)

static

Definition at line 42 of file rege_dfa.c.

 {
     chr        *cp;
     chr        *realstop = (stop == v->stop) ? stop : stop + 1;
     color       co;
     struct sset *css;
     struct sset *ss;
     chr        *post;
     int         i;
     struct colormap *cm = d->cm;
  
     /* prevent "uninitialized variable" warnings */
     if (hitstopp != NULL)
         *hitstopp = 0;
  
     /* if this is a backref to a known string, just match against that */
     if (d->backno >= 0)
     {
         assert((size_t) d->backno < v->nmatch);
         if (v->pmatch[d->backno].rm_so >= 0)
         {
             cp = dfa_backref(v, d, start, start, stop, false);
             if (cp == v->stop && stop == v->stop && hitstopp != NULL)
                 *hitstopp = 1;
             return cp;
         }
     }
  
     /* fast path for matchall NFAs */
     if (d->cnfa->flags & MATCHALL)
     {
         size_t      nchr = stop - start;
         size_t      maxmatchall = d->cnfa->maxmatchall;
  
         if (nchr < d->cnfa->minmatchall)
             return NULL;
         if (maxmatchall == DUPINF)
         {
             if (stop == v->stop && hitstopp != NULL)
                 *hitstopp = 1;
         }
         else
         {
             if (stop == v->stop && nchr <= maxmatchall + 1 && hitstopp != NULL)
                 *hitstopp = 1;
             if (nchr > maxmatchall)
                 return start + maxmatchall;
         }
         return stop;
     }
  
     /* initialize */
     css = initialize(v, d, start);
     if (css == NULL)
         return NULL;
     cp = start;
  
     /* startup */
     FDEBUG(("+++ startup +++\n"));
     if (cp == v->start)
     {
         co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
     }
     else
     {
         co = GETCOLOR(cm, *(cp - 1));
         FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co));
     }
     css = miss(v, d, css, co, cp, start);
     if (css == NULL)
         return NULL;
     css->lastseen = cp;
  
     /*
      * This is the main text-scanning loop.  It seems worth having two copies
      * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
      * builds, when you're not actively tracing.
      */
 #ifdef REG_DEBUG
     if (v->eflags & REG_FTRACE)
     {
         while (cp < realstop)
         {
             FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets)));
             co = GETCOLOR(cm, *cp);
             FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
         }
     }
     else
 #endif
     {
         while (cp < realstop)
         {
             co = GETCOLOR(cm, *cp);
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
         }
     }
  
     if (ISERR())
         return NULL;
  
     /* shutdown */
     FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets)));
     if (cp == v->stop && stop == v->stop)
     {
         if (hitstopp != NULL)
             *hitstopp = 1;
         co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
         ss = miss(v, d, css, co, cp, start);
         if (ISERR())
             return NULL;
         /* special case:  match ended at eol? */
         if (ss != NULL && (ss->flags & POSTSTATE))
             return cp;
         else if (ss != NULL)
             ss->lastseen = cp;  /* to be tidy */
     }
  
     /* find last match, if any */
     post = d->lastpost;
     for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)
         if ((ss->flags & POSTSTATE) && post != ss->lastseen &&
             (post == NULL || post < ss->lastseen))
             post = ss->lastseen;
     if (post != NULL)           /* found one */
         return post - 1;
  
     return NULL;
 }

References assert, dfa::backno, cnfa::bos, dfa::cm, dfa::cnfa, dfa_backref(), DUPINF, vars::eflags, cnfa::eos, FDEBUG, sset::flags, cnfa::flags, GETCOLOR, i, initialize(), ISERR, dfa::lastpost, sset::lastseen, MATCHALL, cnfa::maxmatchall, cnfa::minmatchall, miss(), vars::nmatch, dfa::nssused, sset::outs, vars::pmatch, POSTSTATE, REG_FTRACE, REG_NOTBOL, REG_NOTEOL, dfa::ssets, vars::start, start, vars::stop, and colormap::v.

Referenced by ProcessSyncRequests().

◆ matchuntil()

static int matchuntil	(	struct vars *	v,
		struct dfa *	d,
		chr *	probe,
		struct sset **	lastcss,
		chr **	lastcp
	)

static

Definition at line 371 of file rege_dfa.c.

 {
     chr        *cp = *lastcp;
     color       co;
     struct sset *css = *lastcss;
     struct sset *ss;
     struct colormap *cm = d->cm;
  
     /* fast path for matchall NFAs */
     if (d->cnfa->flags & MATCHALL)
     {
         size_t      nchr = probe - v->start;
  
         if (nchr < d->cnfa->minmatchall)
             return 0;
         /* maxmatchall will always be infinity, cf. makesearch() */
         assert(d->cnfa->maxmatchall == DUPINF);
         return 1;
     }
  
     /* initialize and startup, or restart, if necessary */
     if (cp == NULL || cp > probe)
     {
         cp = v->start;
         css = initialize(v, d, cp);
         if (css == NULL)
             return 0;
  
         FDEBUG((">>> startup >>>\n"));
         co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
  
         css = miss(v, d, css, co, cp, v->start);
         if (css == NULL)
             return 0;
         css->lastseen = cp;
     }
     else if (css == NULL)
     {
         /* we previously found that no match is possible beyond *lastcp */
         return 0;
     }
     ss = css;
  
     /*
      * This is the main text-scanning loop.  It seems worth having two copies
      * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
      * builds, when you're not actively tracing.
      */
 #ifdef REG_DEBUG
     if (v->eflags & REG_FTRACE)
     {
         while (cp < probe)
         {
             FDEBUG((">>> at c%d >>>\n", (int) (css - d->ssets)));
             co = GETCOLOR(cm, *cp);
             FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, v->start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
         }
     }
     else
 #endif
     {
         while (cp < probe)
         {
             co = GETCOLOR(cm, *cp);
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, v->start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
         }
     }
  
     *lastcss = ss;
     *lastcp = cp;
  
     if (ss == NULL)
         return 0;               /* impossible match, or internal error */
  
     /* We need to process one more chr, or the EOS symbol, to check match */
     if (cp < v->stop)
     {
         FDEBUG((">>> at c%d >>>\n", (int) (css - d->ssets)));
         co = GETCOLOR(cm, *cp);
         FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
         ss = css->outs[co];
         if (ss == NULL)
             ss = miss(v, d, css, co, cp + 1, v->start);
     }
     else
     {
         assert(cp == v->stop);
         co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
         ss = miss(v, d, css, co, cp, v->start);
     }
  
     if (ss == NULL || !(ss->flags & POSTSTATE))
         return 0;
  
     return 1;
 }

References assert, cnfa::bos, dfa::cm, dfa::cnfa, DUPINF, vars::eflags, cnfa::eos, FDEBUG, sset::flags, cnfa::flags, GETCOLOR, initialize(), sset::lastseen, MATCHALL, cnfa::maxmatchall, cnfa::minmatchall, miss(), sset::outs, POSTSTATE, REG_FTRACE, REG_NOTBOL, REG_NOTEOL, dfa::ssets, vars::start, vars::stop, and colormap::v.

Referenced by lacon().

◆ miss()

static struct sset* miss	(	struct vars *	v,
		struct dfa *	d,
		struct sset *	css,
		color	co,
		chr *	cp,
		chr *	start
	)

static

Definition at line 777 of file rege_dfa.c.

 {
     struct cnfa *cnfa = d->cnfa;
     int         i;
     unsigned    h;
     struct carc *ca;
     struct sset *p;
     int         ispseudocolor;
     int         ispost;
     int         noprogress;
     int         gotstate;
     int         dolacons;
     int         sawlacons;
  
     /* for convenience, we can be called even if it might not be a miss */
     if (css->outs[co] != NULL)
     {
         FDEBUG(("hit\n"));
         return css->outs[co];
     }
     FDEBUG(("miss\n"));
  
     /*
      * Checking for operation cancel in the inner text search loop seems
      * unduly expensive.  As a compromise, check during cache misses.
      */
     INTERRUPT(v->re);
  
     /*
      * What set of states would we end up in after consuming the co character?
      * We first consider PLAIN arcs that consume the character, and then look
      * to see what LACON arcs could be traversed after consuming it.
      */
     for (i = 0; i < d->wordsper; i++)
         d->work[i] = 0;         /* build new stateset bitmap in d->work */
     ispseudocolor = d->cm->cd[co].flags & PSEUDO;
     ispost = 0;
     noprogress = 1;
     gotstate = 0;
     for (i = 0; i < d->nstates; i++)
         if (ISBSET(css->states, i))
             for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++)
                 if (ca->co == co ||
                     (ca->co == RAINBOW && !ispseudocolor))
                 {
                     BSET(d->work, ca->to);
                     gotstate = 1;
                     if (ca->to == cnfa->post)
                         ispost = 1;
                     if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS))
                         noprogress = 0;
                     FDEBUG(("%d -> %d\n", i, ca->to));
                 }
     if (!gotstate)
         return NULL;            /* character cannot reach any new state */
     dolacons = (cnfa->flags & HASLACONS);
     sawlacons = 0;
     /* outer loop handles transitive closure of reachable-by-LACON states */
     while (dolacons)
     {
         dolacons = 0;
         for (i = 0; i < d->nstates; i++)
             if (ISBSET(d->work, i))
                 for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++)
                 {
                     if (ca->co < cnfa->ncolors)
                         continue;   /* not a LACON arc */
                     if (ISBSET(d->work, ca->to))
                         continue;   /* arc would be a no-op anyway */
                     sawlacons = 1;  /* this LACON affects our result */
                     if (!lacon(v, cnfa, cp, ca->co))
                     {
                         if (ISERR())
                             return NULL;
                         continue;   /* LACON arc cannot be traversed */
                     }
                     if (ISERR())
                         return NULL;
                     BSET(d->work, ca->to);
                     dolacons = 1;
                     if (ca->to == cnfa->post)
                         ispost = 1;
                     if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS))
                         noprogress = 0;
                     FDEBUG(("%d :> %d\n", i, ca->to));
                 }
     }
     h = HASH(d->work, d->wordsper);
  
     /* Is this stateset already in the cache? */
     for (p = d->ssets, i = d->nssused; i > 0; p++, i--)
         if (HIT(h, d->work, p, d->wordsper))
         {
             FDEBUG(("cached c%d\n", (int) (p - d->ssets)));
             break;              /* NOTE BREAK OUT */
         }
     if (i == 0)
     {                           /* nope, need a new cache entry */
         p = getvacant(v, d, cp, start);
         if (p == NULL)
             return NULL;
         assert(p != css);
         for (i = 0; i < d->wordsper; i++)
             p->states[i] = d->work[i];
         p->hash = h;
         p->flags = (ispost) ? POSTSTATE : 0;
         if (noprogress)
             p->flags |= NOPROGRESS;
         /* lastseen to be dealt with by caller */
     }
  
     /*
      * Link new stateset to old, unless a LACON affected the result, in which
      * case we don't create the link.  That forces future transitions across
      * this same arc (same prior stateset and character color) to come through
      * miss() again, so that we can recheck the LACON(s), which might or might
      * not pass since context will be different.
      */
     if (!sawlacons)
     {
         FDEBUG(("c%d[%d]->c%d\n",
                 (int) (css - d->ssets), co, (int) (p - d->ssets)));
         css->outs[co] = p;
         css->inchain[co] = p->ins;
         p->ins.ss = css;
         p->ins.co = co;
     }
     return p;
 }

References assert, BSET, colormap::cd, dfa::cm, dfa::cnfa, CNFA_NOPROGRESS, arcp::co, carc::co, COLORLESS, FDEBUG, sset::flags, colordesc::flags, cnfa::flags, for(), getvacant(), HASH, sset::hash, HASLACONS, HIT, i, sset::inchain, sset::ins, INTERRUPT, ISBSET, ISERR, lacon(), cnfa::ncolors, NOPROGRESS, dfa::nssused, dfa::nstates, sset::outs, cnfa::post, POSTSTATE, PSEUDO, RAINBOW, vars::re, arcp::ss, dfa::ssets, start, sset::states, cnfa::states, cnfa::stflags, carc::to, dfa::wordsper, and dfa::work.

Referenced by longest(), matchuntil(), and shortest().

◆ newdfa()

static struct dfa* newdfa	(	struct vars *	v,
		struct cnfa *	cnfa,
		struct colormap *	cm,
		struct smalldfa *	sml
	)

static

Definition at line 607 of file rege_dfa.c.

 {
     struct dfa *d;
     size_t      nss = cnfa->nstates * 2;
     int         wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
     bool        ismalloced = false;
  
     assert(cnfa != NULL && cnfa->nstates != 0);
  
     if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS)
     {
         assert(wordsper == 1);
         if (sml == NULL)
         {
             sml = (struct smalldfa *) MALLOC(sizeof(struct smalldfa));
             if (sml == NULL)
             {
                 ERR(REG_ESPACE);
                 return NULL;
             }
             ismalloced = true;
         }
         d = &sml->dfa;
         d->ssets = sml->ssets;
         d->statesarea = sml->statesarea;
         d->work = &d->statesarea[nss];
         d->outsarea = sml->outsarea;
         d->incarea = sml->incarea;
         d->ismalloced = ismalloced;
         d->arraysmalloced = false;  /* not separately allocated, anyway */
     }
     else
     {
         d = (struct dfa *) MALLOC(sizeof(struct dfa));
         if (d == NULL)
         {
             ERR(REG_ESPACE);
             return NULL;
         }
         d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset));
         d->statesarea = (unsigned *) MALLOC((nss + WORK) * wordsper *
                                             sizeof(unsigned));
         d->work = &d->statesarea[nss * wordsper];
         d->outsarea = (struct sset **) MALLOC(nss * cnfa->ncolors *
                                               sizeof(struct sset *));
         d->incarea = (struct arcp *) MALLOC(nss * cnfa->ncolors *
                                             sizeof(struct arcp));
         d->ismalloced = true;
         d->arraysmalloced = true;
         /* now freedfa() will behave sanely */
         if (d->ssets == NULL || d->statesarea == NULL ||
             d->outsarea == NULL || d->incarea == NULL)
         {
             freedfa(d);
             ERR(REG_ESPACE);
             return NULL;
         }
     }
  
     d->nssets = (v->eflags & REG_SMALL) ? 7 : nss;
     d->nssused = 0;
     d->nstates = cnfa->nstates;
     d->ncolors = cnfa->ncolors;
     d->wordsper = wordsper;
     d->cnfa = cnfa;
     d->cm = cm;
     d->lastpost = NULL;
     d->lastnopr = NULL;
     d->search = d->ssets;
     d->backno = -1;             /* may be set by caller */
     d->backmin = d->backmax = 0;
  
     /* initialization of sset fields is done as needed */
  
     return d;
 }

References dfa::arraysmalloced, assert, dfa::backmax, dfa::backmin, dfa::backno, dfa::cm, dfa::cnfa, smalldfa::dfa, vars::eflags, ERR, FEWCOLORS, freedfa(), dfa::incarea, smalldfa::incarea, dfa::ismalloced, dfa::lastnopr, dfa::lastpost, MALLOC, dfa::ncolors, cnfa::ncolors, dfa::nssets, dfa::nssused, dfa::nstates, cnfa::nstates, dfa::outsarea, smalldfa::outsarea, REG_ESPACE, REG_SMALL, dfa::search, dfa::ssets, smalldfa::ssets, dfa::statesarea, smalldfa::statesarea, UBITS, dfa::wordsper, dfa::work, and WORK.

◆ pickss()

static struct sset* pickss	(	struct vars *	v,
		struct dfa *	d,
		chr *	cp,
		chr *	start
	)

static

Definition at line 1044 of file rege_dfa.c.

 {
     int         i;
     struct sset *ss;
     struct sset *end;
     chr        *ancient;
  
     /* shortcut for cases where cache isn't full */
     if (d->nssused < d->nssets)
     {
         i = d->nssused;
         d->nssused++;
         ss = &d->ssets[i];
         FDEBUG(("new c%d\n", i));
         /* set up innards */
         ss->states = &d->statesarea[i * d->wordsper];
         ss->flags = 0;
         ss->ins.ss = NULL;
         ss->ins.co = WHITE;     /* give it some value */
         ss->outs = &d->outsarea[i * d->ncolors];
         ss->inchain = &d->incarea[i * d->ncolors];
         for (i = 0; i < d->ncolors; i++)
         {
             ss->outs[i] = NULL;
             ss->inchain[i].ss = NULL;
         }
         return ss;
     }
  
     /* look for oldest, or old enough anyway */
     if (cp - start > d->nssets * 2 / 3) /* oldest 33% are expendable */
         ancient = cp - d->nssets * 2 / 3;
     else
         ancient = start;
     for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)
         if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
             !(ss->flags & LOCKED))
         {
             d->search = ss + 1;
             FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
             return ss;
         }
     for (ss = d->ssets, end = d->search; ss < end; ss++)
         if ((ss->lastseen == NULL || ss->lastseen < ancient) &&
             !(ss->flags & LOCKED))
         {
             d->search = ss + 1;
             FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
             return ss;
         }
  
     /* nobody's old enough?!? -- something's really wrong */
     FDEBUG(("cannot find victim to replace!\n"));
     ERR(REG_ASSERT);
     return NULL;
 }

References arcp::co, ERR, FDEBUG, sset::flags, i, dfa::incarea, sset::inchain, sset::ins, sset::lastseen, LOCKED, dfa::ncolors, dfa::nssets, dfa::nssused, sset::outs, dfa::outsarea, REG_ASSERT, dfa::search, arcp::ss, dfa::ssets, start, sset::states, dfa::statesarea, WHITE, and dfa::wordsper.

Referenced by getvacant().

◆ shortest()

static chr* shortest	(	struct vars *	v,
		struct dfa *	d,
		chr *	start,
		chr *	min,
		chr *	max,
		chr **	coldp,
		int *	hitstopp
	)

static

Definition at line 204 of file rege_dfa.c.

 {
     chr        *cp;
     chr        *realmin = (min == v->stop) ? min : min + 1;
     chr        *realmax = (max == v->stop) ? max : max + 1;
     color       co;
     struct sset *css;
     struct sset *ss;
     struct colormap *cm = d->cm;
  
     /* prevent "uninitialized variable" warnings */
     if (coldp != NULL)
         *coldp = NULL;
     if (hitstopp != NULL)
         *hitstopp = 0;
  
     /* if this is a backref to a known string, just match against that */
     if (d->backno >= 0)
     {
         assert((size_t) d->backno < v->nmatch);
         if (v->pmatch[d->backno].rm_so >= 0)
         {
             cp = dfa_backref(v, d, start, min, max, true);
             if (cp != NULL && coldp != NULL)
                 *coldp = start;
             /* there is no case where we should set *hitstopp */
             return cp;
         }
     }
  
     /* fast path for matchall NFAs */
     if (d->cnfa->flags & MATCHALL)
     {
         size_t      nchr = min - start;
  
         if (d->cnfa->maxmatchall != DUPINF &&
             nchr > d->cnfa->maxmatchall)
             return NULL;
         if ((max - start) < d->cnfa->minmatchall)
             return NULL;
         if (nchr < d->cnfa->minmatchall)
             min = start + d->cnfa->minmatchall;
         if (coldp != NULL)
             *coldp = start;
         /* there is no case where we should set *hitstopp */
         return min;
     }
  
     /* initialize */
     css = initialize(v, d, start);
     if (css == NULL)
         return NULL;
     cp = start;
  
     /* startup */
     FDEBUG(("--- startup ---\n"));
     if (cp == v->start)
     {
         co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
     }
     else
     {
         co = GETCOLOR(cm, *(cp - 1));
         FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co));
     }
     css = miss(v, d, css, co, cp, start);
     if (css == NULL)
         return NULL;
     css->lastseen = cp;
     ss = css;
  
     /*
      * This is the main text-scanning loop.  It seems worth having two copies
      * to avoid the overhead of REG_FTRACE tests here, even in REG_DEBUG
      * builds, when you're not actively tracing.
      */
 #ifdef REG_DEBUG
     if (v->eflags & REG_FTRACE)
     {
         while (cp < realmax)
         {
             FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets)));
             co = GETCOLOR(cm, *cp);
             FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co));
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
             if ((ss->flags & POSTSTATE) && cp >= realmin)
                 break;          /* NOTE BREAK OUT */
         }
     }
     else
 #endif
     {
         while (cp < realmax)
         {
             co = GETCOLOR(cm, *cp);
             ss = css->outs[co];
             if (ss == NULL)
             {
                 ss = miss(v, d, css, co, cp + 1, start);
                 if (ss == NULL)
                     break;      /* NOTE BREAK OUT */
             }
             cp++;
             ss->lastseen = cp;
             css = ss;
             if ((ss->flags & POSTSTATE) && cp >= realmin)
                 break;          /* NOTE BREAK OUT */
         }
     }
  
     if (ss == NULL)
         return NULL;
  
     if (coldp != NULL)          /* report last no-progress state set, if any */
         *coldp = lastcold(v, d);
  
     if ((ss->flags & POSTSTATE) && cp > min)
     {
         assert(cp >= realmin);
         cp--;
     }
     else if (cp == v->stop && max == v->stop)
     {
         co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1];
         FDEBUG(("color %ld\n", (long) co));
         ss = miss(v, d, css, co, cp, start);
         /* match might have ended at eol */
         if ((ss == NULL || !(ss->flags & POSTSTATE)) && hitstopp != NULL)
             *hitstopp = 1;
     }
  
     if (ss == NULL || !(ss->flags & POSTSTATE))
         return NULL;
  
     return cp;
 }

References assert, dfa::backno, cnfa::bos, dfa::cm, dfa::cnfa, dfa_backref(), DUPINF, vars::eflags, cnfa::eos, FDEBUG, sset::flags, cnfa::flags, GETCOLOR, initialize(), lastcold(), sset::lastseen, MATCHALL, colormap::max, cnfa::maxmatchall, cnfa::minmatchall, miss(), vars::nmatch, sset::outs, vars::pmatch, POSTSTATE, REG_FTRACE, REG_NOTBOL, REG_NOTEOL, dfa::ssets, vars::start, start, vars::stop, and colormap::v.

Referenced by dfa_backref(), and lacon().

Functions

Function Documentation

◆ dfa_backref()

◆ freedfa()

◆ getvacant()

◆ hash()

◆ initialize()

◆ lacon()

◆ lastcold()

◆ longest()

◆ matchuntil()

◆ miss()

◆ newdfa()

◆ pickss()

◆ shortest()