/
githubmirror
/
postgres
Обзор
Документация
Войти
/
githubmirror
/
postgres
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/backend/regex/regexec.c
1 516 строк
39 KB
Tom Lane
Harden our regex engine against integer overflow in size calculations.
11 май 2026, 15:13
11 май 2026, 15:13
0dc1fdc
Код
Авторство
О чём код?
/* * re_*exec and friends - match REs * * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. * * Development of this software was funded, in part, by Cray Research Inc., * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics * Corporation, none of whom are responsible for the results. The author * thanks all of them. * * Redistribution and use in source and binary forms -- with or without * modification -- are permitted for any purpose, provided that * redistributions in source form retain this entire copyright notice and * indicate the origin and nature of any modifications. * * I'd appreciate being given credit for this package in the documentation * of software which uses it, but that is not a requirement. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * src/backend/regex/regexec.c * */ #include "regex/regguts.h" /* lazy-DFA representation */ struct arcp { /* "pointer" to an outarc */ struct sset *ss; color co; }; struct sset { /* state set */ unsigned *states; /* pointer to bitvector */ unsigned hash; /* hash of bitvector */ #define HASH(bv, nw) (((nw) == 1) ? *(bv) : hash(bv, nw)) #define HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \ memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0)) int flags; #define STARTER 01 /* the initial state set */ #define POSTSTATE 02 /* includes the goal state */ #define LOCKED 04 /* locked in cache */ #define NOPROGRESS 010 /* zero-progress state set */ struct arcp ins; /* chain of inarcs pointing here */ chr *lastseen; /* last entered on arrival here */ struct sset **outs; /* outarc vector indexed by color */ struct arcp *inchain; /* chain-pointer vector for outarcs */ }; struct dfa { int nssets; /* size of cache */ int nssused; /* how many entries occupied yet */ int nstates; /* number of states */ int ncolors; /* length of outarc and inchain vectors */ int wordsper; /* length of state-set bitvectors */ struct sset *ssets; /* state-set cache */ unsigned *statesarea; /* bitvector storage */ unsigned *work; /* pointer to work area within statesarea */ struct sset **outsarea; /* outarc-vector storage */ struct arcp *incarea; /* inchain storage */ struct cnfa *cnfa; struct colormap *cm; chr *lastpost; /* location of last cache-flushed success */ chr *lastnopr; /* location of last cache-flushed NOPROGRESS */ struct sset *search; /* replacement-search-pointer memory */ int backno; /* if DFA for a backref, subno it refers to */ short backmin; /* min repetitions for backref */ short backmax; /* max repetitions for backref */ bool ismalloced; /* should this struct dfa be freed? */ bool arraysmalloced; /* should its subsidiary arrays be freed? */ }; #define WORK 1 /* number of work bitvectors needed */ /* setup for non-malloc allocation for small cases */ #define FEWSTATES 20 /* must be less than UBITS */ #define FEWCOLORS 15 struct smalldfa { struct dfa dfa; /* must be first */ struct sset ssets[FEWSTATES * 2]; unsigned statesarea[FEWSTATES * 2 + WORK]; struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS]; struct arcp incarea[FEWSTATES * 2 * FEWCOLORS]; }; #define DOMALLOC ((struct smalldfa *)NULL) /* force malloc */ /* internal variables, bundled for easy passing around */ struct vars { regex_t *re; struct guts *g; int eflags; /* copies of arguments */ size_t nmatch; regmatch_t *pmatch; rm_detail_t *details; chr *start; /* start of string */ chr *search_start; /* search start of string */ chr *stop; /* just past end of string */ int err; /* error code if any (0 none) */ struct dfa **subdfas; /* per-tree-subre DFAs */ struct dfa **ladfas; /* per-lacon-subre DFAs */ struct sset **lblastcss; /* per-lacon-subre lookbehind restart data */ chr **lblastcp; /* per-lacon-subre lookbehind restart data */ struct smalldfa dfa1; struct smalldfa dfa2; }; #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ #define ISERR() VISERR(v) #define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e))) #define ERR(e) VERR(v, e) /* record an error */ #define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */ #define OFF(p) ((p) - v->start) #define LOFF(p) ((long)OFF(p)) /* * forward declarations */ /* === regexec.c === */ static struct dfa *getsubdfa(struct vars *v, struct subre *t); static struct dfa *getladfa(struct vars *v, int n); static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm); static int cfind(struct vars *v, struct cnfa *cnfa, struct colormap *cm); static int cfindloop(struct vars *v, struct cnfa *cnfa, struct colormap *cm, struct dfa *d, struct dfa *s, chr **coldp); static void zapallsubs(regmatch_t *p, size_t n); static void zaptreesubs(struct vars *v, struct subre *t); static void subset(struct vars *v, struct subre *sub, chr *begin, chr *end); static int cdissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int ccondissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int crevcondissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int cbrdissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int caltdissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int citerdissect(struct vars *v, struct subre *t, chr *begin, chr *end); static int creviterdissect(struct vars *v, struct subre *t, chr *begin, chr *end); /* === rege_dfa.c === */ static chr *longest(struct vars *v, struct dfa *d, chr *start, chr *stop, int *hitstopp); static chr *shortest(struct vars *v, struct dfa *d, chr *start, chr *min, chr *max, chr **coldp, int *hitstopp); static int matchuntil(struct vars *v, struct dfa *d, chr *probe, struct sset **lastcss, chr **lastcp); static chr *dfa_backref(struct vars *v, struct dfa *d, chr *start, chr *min, chr *max, bool shortest); static chr *lastcold(struct vars *v, struct dfa *d); static struct dfa *newdfa(struct vars *v, struct cnfa *cnfa, struct colormap *cm, struct smalldfa *sml); static void freedfa(struct dfa *d); static unsigned hash(unsigned *uv, int n); static struct sset *initialize(struct vars *v, struct dfa *d, chr *start); static struct sset *miss(struct vars *v, struct dfa *d, struct sset *css, color co, chr *cp, chr *start); static int lacon(struct vars *v, struct cnfa *pcnfa, chr *cp, color co); static struct sset *getvacant(struct vars *v, struct dfa *d, chr *cp, chr *start); static struct sset *pickss(struct vars *v, struct dfa *d, chr *cp, chr *start); /* * pg_regexec - match regular expression */ int pg_regexec(regex_t *re, const chr *string, size_t len, size_t search_start, rm_detail_t *details, size_t nmatch, regmatch_t pmatch[], int flags) { struct vars var; struct vars *v = &var; int st; size_t n; size_t i; int backref; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; #define LOCALDFAS 40 struct dfa *subdfas[LOCALDFAS]; /* sanity checks */ if (re == NULL || string == NULL || re->re_magic != REMAGIC) return REG_INVARG; if (re->re_csize != sizeof(chr)) return REG_MIXED; if (search_start > len) return REG_NOMATCH; /* Initialize locale-dependent support */ pg_set_regex_collation(re->re_collation); /* setup */ v->re = re; v->g = (struct guts *) re->re_guts; if ((v->g->cflags & REG_EXPECT) && details == NULL) return REG_INVARG; if (v->g->info & REG_UIMPOSSIBLE) return REG_NOMATCH; backref = (v->g->info & REG_UBACKREF) ? 1 : 0; v->eflags = flags; if (backref && nmatch <= v->g->nsub) { /* need larger work area */ v->nmatch = v->g->nsub + 1; if (v->nmatch <= LOCALMAT) v->pmatch = mat; else v->pmatch = MALLOC_ARRAY(regmatch_t, v->nmatch); if (v->pmatch == NULL) return REG_ESPACE; zapallsubs(v->pmatch, v->nmatch); } else { /* we can store results directly in caller's array */ v->pmatch = pmatch; /* ensure any extra entries in caller's array are filled with -1 */ if (nmatch > 0) zapallsubs(pmatch, nmatch); /* then forget about extra entries, to avoid useless work in find() */ if (nmatch > v->g->nsub + 1) nmatch = v->g->nsub + 1; v->nmatch = nmatch; } v->details = details; v->start = (chr *) string; v->search_start = (chr *) string + search_start; v->stop = (chr *) string + len; v->err = 0; v->subdfas = NULL; v->ladfas = NULL; v->lblastcss = NULL; v->lblastcp = NULL; /* below this point, "goto cleanup" will behave sanely */ assert(v->g->ntree >= 0); n = (size_t) v->g->ntree; if (n <= LOCALDFAS) v->subdfas = subdfas; else { /* ntree is surely less than the number of states, so this is safe: */ v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *)); if (v->subdfas == NULL) { st = REG_ESPACE; goto cleanup; } } for (i = 0; i < n; i++) v->subdfas[i] = NULL; assert(v->g->nlacons >= 0); n = (size_t) v->g->nlacons; if (n > 0) { /* nlacons is surely less than the number of arcs, so this is safe: */ v->ladfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *)); if (v->ladfas == NULL) { st = REG_ESPACE; goto cleanup; } for (i = 0; i < n; i++) v->ladfas[i] = NULL; v->lblastcss = (struct sset **) MALLOC(n * sizeof(struct sset *)); v->lblastcp = (chr **) MALLOC(n * sizeof(chr *)); if (v->lblastcss == NULL || v->lblastcp == NULL) { st = REG_ESPACE; goto cleanup; } for (i = 0; i < n; i++) { v->lblastcss[i] = NULL; v->lblastcp[i] = NULL; } } /* do it */ assert(v->g->tree != NULL); if (backref) st = cfind(v, &v->g->tree->cnfa, &v->g->cmap); else st = find(v, &v->g->tree->cnfa, &v->g->cmap); /* on success, ensure caller's match vector is filled correctly */ if (st == REG_OKAY && nmatch > 0) { if (v->pmatch != pmatch) { /* copy portion of match vector over from (larger) work area */ assert(nmatch <= v->nmatch); memcpy(VS(pmatch), VS(v->pmatch), nmatch * sizeof(regmatch_t)); } if (v->g->cflags & REG_NOSUB) { /* don't expose possibly-partial sub-match results to caller */ zapallsubs(pmatch, nmatch); } } /* clean up */ cleanup: if (v->pmatch != pmatch && v->pmatch != mat) FREE(v->pmatch); if (v->subdfas != NULL) { n = (size_t) v->g->ntree; for (i = 0; i < n; i++) { if (v->subdfas[i] != NULL) freedfa(v->subdfas[i]); } if (v->subdfas != subdfas) FREE(v->subdfas); } if (v->ladfas != NULL) { n = (size_t) v->g->nlacons; for (i = 0; i < n; i++) { if (v->ladfas[i] != NULL) freedfa(v->ladfas[i]); } FREE(v->ladfas); } if (v->lblastcss != NULL) FREE(v->lblastcss); if (v->lblastcp != NULL) FREE(v->lblastcp); #ifdef REG_DEBUG if (v->eflags & (REG_FTRACE | REG_MTRACE)) fflush(stdout); #endif return st; } /* * getsubdfa - create or re-fetch the DFA for a tree subre node * * We only need to create the DFA once per overall regex execution. * The DFA will be freed by the cleanup step in pg_regexec(). */ static struct dfa * getsubdfa(struct vars *v, struct subre *t) { struct dfa *d = v->subdfas[t->id]; if (d == NULL) { d = newdfa(v, &t->cnfa, &v->g->cmap, DOMALLOC); if (d == NULL) return NULL; /* set up additional info if this is a backref node */ if (t->op == 'b') { d->backno = t->backno; d->backmin = t->min; d->backmax = t->max; } v->subdfas[t->id] = d; } return d; } /* * getladfa - create or re-fetch the DFA for a LACON subre node * * Same as above, but for LACONs. */ static struct dfa * getladfa(struct vars *v, int n) { assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL); if (v->ladfas[n] == NULL) { struct subre *sub = &v->g->lacons[n]; v->ladfas[n] = newdfa(v, &sub->cnfa, &v->g->cmap, DOMALLOC); /* a LACON can't contain a backref, so nothing else to do */ } return v->ladfas[n]; } /* * find - find a match for the main NFA (no-complications case) */ static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm) { struct dfa *s; struct dfa *d; chr *begin; chr *end = NULL; chr *cold; chr *open; /* open and close of range of possible starts */ chr *close; int hitend; int shorter = (v->g->tree->flags & SHORTER) ? 1 : 0; /* first, a shot with the search RE */ s = newdfa(v, &v->g->search, cm, &v->dfa1); if (s == NULL) return v->err; MDEBUG(("\nsearch at %ld\n", LOFF(v->start))); cold = NULL; close = shortest(v, s, v->search_start, v->search_start, v->stop, &cold, (int *) NULL); freedfa(s); NOERR(); if (v->g->cflags & REG_EXPECT) { assert(v->details != NULL); if (cold != NULL) v->details->rm_extend.rm_so = OFF(cold); else v->details->rm_extend.rm_so = OFF(v->stop); v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ } if (close == NULL) /* not found */ return REG_NOMATCH; if (v->nmatch == 0) /* found, don't need exact location */ return REG_OKAY; /* find starting point and match */ assert(cold != NULL); open = cold; cold = NULL; MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close))); d = newdfa(v, cnfa, cm, &v->dfa1); if (d == NULL) return v->err; for (begin = open; begin <= close; begin++) { MDEBUG(("\nfind trying at %ld\n", LOFF(begin))); if (shorter) end = shortest(v, d, begin, begin, v->stop, (chr **) NULL, &hitend); else end = longest(v, d, begin, v->stop, &hitend); if (ISERR()) { freedfa(d); return v->err; } if (hitend && cold == NULL) cold = begin; if (end != NULL) break; /* NOTE BREAK OUT */ } assert(end != NULL); /* search RE succeeded so loop should */ freedfa(d); /* and pin down details */ assert(v->nmatch > 0); v->pmatch[0].rm_so = OFF(begin); v->pmatch[0].rm_eo = OFF(end); if (v->g->cflags & REG_EXPECT) { if (cold != NULL) v->details->rm_extend.rm_so = OFF(cold); else v->details->rm_extend.rm_so = OFF(v->stop); v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ } if (v->nmatch == 1) /* no need for submatches */ return REG_OKAY; /* find submatches */ return cdissect(v, v->g->tree, begin, end); } /* * cfind - find a match for the main NFA (with complications) */ static int cfind(struct vars *v, struct cnfa *cnfa, struct colormap *cm) { struct dfa *s; struct dfa *d; chr *cold; int ret; s = newdfa(v, &v->g->search, cm, &v->dfa1); if (s == NULL) return v->err; d = newdfa(v, cnfa, cm, &v->dfa2); if (d == NULL) { freedfa(s); return v->err; } ret = cfindloop(v, cnfa, cm, d, s, &cold); freedfa(d); freedfa(s); NOERR(); if (v->g->cflags & REG_EXPECT) { assert(v->details != NULL); if (cold != NULL) v->details->rm_extend.rm_so = OFF(cold); else v->details->rm_extend.rm_so = OFF(v->stop); v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */ } return ret; } /* * cfindloop - the heart of cfind */ static int cfindloop(struct vars *v, struct cnfa *cnfa, struct colormap *cm, struct dfa *d, struct dfa *s, chr **coldp) /* where to put coldstart pointer */ { chr *begin; chr *end; chr *cold; chr *open; /* open and close of range of possible starts */ chr *close; chr *estart; chr *estop; int er; int shorter = v->g->tree->flags & SHORTER; int hitend; assert(d != NULL && s != NULL); cold = NULL; close = v->search_start; do { /* Search with the search RE for match range at/beyond "close" */ MDEBUG(("\ncsearch at %ld\n", LOFF(close))); close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL); if (ISERR()) { *coldp = cold; return v->err; } if (close == NULL) break; /* no more possible match anywhere */ assert(cold != NULL); open = cold; cold = NULL; /* Search for matches starting between "open" and "close" inclusive */ MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close))); for (begin = open; begin <= close; begin++) { MDEBUG(("\ncfind trying at %ld\n", LOFF(begin))); estart = begin; estop = v->stop; for (;;) { /* Here we use the top node's detailed RE */ if (shorter) end = shortest(v, d, begin, estart, estop, (chr **) NULL, &hitend); else end = longest(v, d, begin, estop, &hitend); if (ISERR()) { *coldp = cold; return v->err; } if (hitend && cold == NULL) cold = begin; if (end == NULL) break; /* no match with this begin point, try next */ MDEBUG(("tentative end %ld\n", LOFF(end))); /* Dissect the potential match to see if it really matches */ er = cdissect(v, v->g->tree, begin, end); if (er == REG_OKAY) { if (v->nmatch > 0) { v->pmatch[0].rm_so = OFF(begin); v->pmatch[0].rm_eo = OFF(end); } *coldp = cold; return REG_OKAY; } if (er != REG_NOMATCH) { ERR(er); *coldp = cold; return er; } /* Try next longer/shorter match with same begin point */ if (shorter) { if (end == estop) break; /* no more, so try next begin point */ estart = end + 1; } else { if (end == begin) break; /* no more, so try next begin point */ estop = end - 1; } } /* end loop over endpoint positions */ } /* end loop over beginning positions */ /* * If we get here, there is no possible match starting at or before * "close", so consider matches beyond that. We'll do a fresh search * with the search RE to find a new promising match range. */ close++; } while (close < v->stop); *coldp = cold; return REG_NOMATCH; } /* * zapallsubs - initialize all subexpression matches to "no match" * * Note that p[0], the overall-match location, is not touched. */ static void zapallsubs(regmatch_t *p, size_t n) { size_t i; for (i = n - 1; i > 0; i--) { p[i].rm_so = -1; p[i].rm_eo = -1; } } /* * zaptreesubs - initialize subexpressions within subtree to "no match" */ static void zaptreesubs(struct vars *v, struct subre *t) { int n = t->capno; struct subre *t2; if (n > 0) { if ((size_t) n < v->nmatch) { v->pmatch[n].rm_so = -1; v->pmatch[n].rm_eo = -1; } } for (t2 = t->child; t2 != NULL; t2 = t2->sibling) zaptreesubs(v, t2); } /* * subset - set subexpression match data for a successful subre */ static void subset(struct vars *v, struct subre *sub, chr *begin, chr *end) { int n = sub->capno; assert(n > 0); if ((size_t) n >= v->nmatch) return; MDEBUG(("%d: setting %d = %ld-%ld\n", sub->id, n, LOFF(begin), LOFF(end))); v->pmatch[n].rm_so = OFF(begin); v->pmatch[n].rm_eo = OFF(end); } /* * cdissect - check backrefs and determine subexpression matches * * cdissect recursively processes a subre tree to check matching of backrefs * and/or identify submatch boundaries for capture nodes. The proposed match * runs from "begin" to "end" (not including "end"), and we are basically * "dissecting" it to see where the submatches are. * * Before calling any level of cdissect, the caller must have run the node's * DFA and found that the proposed substring satisfies the DFA. (We make * the caller do that because in concatenation and iteration nodes, it's * much faster to check all the substrings against the child DFAs before we * recurse.) * * A side-effect of a successful match is to save match locations for * capturing subexpressions in v->pmatch[]. This is a little bit tricky, * so we make the following rules: * 1. Before initial entry to cdissect, all match data must have been * cleared (this is seen to by zapallsubs). * 2. Before any recursive entry to cdissect, the match data for that * subexpression tree must be guaranteed clear (see zaptreesubs). * 3. When returning REG_OKAY, each level of cdissect will have saved * any relevant match locations. * 4. When returning REG_NOMATCH, each level of cdissect will guarantee * that its subexpression match locations are again clear. * 5. No guarantees are made for error cases (i.e., other result codes). * 6. When a level of cdissect abandons a successful sub-match, it will * clear that subtree's match locations with zaptreesubs before trying * any new DFA match or cdissect call for that subtree or any subtree * to its right (that is, any subtree that could have a backref into the * abandoned match). * This may seem overly complicated, but it's difficult to simplify it * because of the provision that match locations must be reset before * any fresh DFA match (a rule that is needed to make dfa_backref safe). * That means it won't work to just reset relevant match locations at the * start of each cdissect level. */ static int /* regexec return code */ cdissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { int er; assert(t != NULL); MDEBUG(("%d: cdissect %c %ld-%ld\n", t->id, t->op, LOFF(begin), LOFF(end))); /* handy place to check for operation cancel */ INTERRUPT(v->re); /* ... and stack overrun */ if (STACK_TOO_DEEP(v->re)) return REG_ETOOBIG; switch (t->op) { case '=': /* terminal node */ assert(t->child == NULL); er = REG_OKAY; /* no action, parent did the work */ break; case 'b': /* back reference */ assert(t->child == NULL); er = cbrdissect(v, t, begin, end); break; case '.': /* concatenation */ assert(t->child != NULL); if (t->child->flags & SHORTER) /* reverse scan */ er = crevcondissect(v, t, begin, end); else er = ccondissect(v, t, begin, end); break; case '|': /* alternation */ assert(t->child != NULL); er = caltdissect(v, t, begin, end); break; case '*': /* iteration */ assert(t->child != NULL); if (t->child->flags & SHORTER) /* reverse scan */ er = creviterdissect(v, t, begin, end); else er = citerdissect(v, t, begin, end); break; case '(': /* no-op capture node */ assert(t->child != NULL); er = cdissect(v, t->child, begin, end); break; default: er = REG_ASSERT; break; } /* * We should never have a match failure unless backrefs lurk below; * otherwise, either caller failed to check the DFA, or there's some * inconsistency between the DFA and the node's innards. */ assert(er != REG_NOMATCH || (t->flags & BACKR)); /* * If this node is marked as capturing, save successful match's location. */ if (t->capno > 0 && er == REG_OKAY) subset(v, t, begin, end); return er; } /* * ccondissect - dissect match for concatenation node */ static int /* regexec return code */ ccondissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { struct subre *left = t->child; struct subre *right = left->sibling; struct dfa *d; struct dfa *d2; chr *mid; int er; assert(t->op == '.'); assert(left != NULL && left->cnfa.nstates > 0); assert(right != NULL && right->cnfa.nstates > 0); assert(right->sibling == NULL); assert(!(left->flags & SHORTER)); d = getsubdfa(v, left); NOERR(); d2 = getsubdfa(v, right); NOERR(); MDEBUG(("%d: ccondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end))); /* pick a tentative midpoint */ mid = longest(v, d, begin, end, (int *) NULL); NOERR(); if (mid == NULL) return REG_NOMATCH; MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid))); /* iterate until satisfaction or failure */ for (;;) { /* try this midpoint on for size */ if (longest(v, d2, mid, end, (int *) NULL) == end) { er = cdissect(v, left, begin, mid); if (er == REG_OKAY) { er = cdissect(v, right, mid, end); if (er == REG_OKAY) { /* satisfaction */ MDEBUG(("%d: successful\n", t->id)); return REG_OKAY; } /* Reset left's matches (right should have done so itself) */ zaptreesubs(v, left); } if (er != REG_NOMATCH) return er; } NOERR(); /* that midpoint didn't work, find a new one */ if (mid == begin) { /* all possibilities exhausted */ MDEBUG(("%d: no midpoint\n", t->id)); return REG_NOMATCH; } mid = longest(v, d, begin, mid - 1, (int *) NULL); NOERR(); if (mid == NULL) { /* failed to find a new one */ MDEBUG(("%d: failed midpoint\n", t->id)); return REG_NOMATCH; } MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); } /* can't get here */ return REG_ASSERT; } /* * crevcondissect - dissect match for concatenation node, shortest-first */ static int /* regexec return code */ crevcondissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { struct subre *left = t->child; struct subre *right = left->sibling; struct dfa *d; struct dfa *d2; chr *mid; int er; assert(t->op == '.'); assert(left != NULL && left->cnfa.nstates > 0); assert(right != NULL && right->cnfa.nstates > 0); assert(right->sibling == NULL); assert(left->flags & SHORTER); d = getsubdfa(v, left); NOERR(); d2 = getsubdfa(v, right); NOERR(); MDEBUG(("%d: crevcondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end))); /* pick a tentative midpoint */ mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL); NOERR(); if (mid == NULL) return REG_NOMATCH; MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid))); /* iterate until satisfaction or failure */ for (;;) { /* try this midpoint on for size */ if (longest(v, d2, mid, end, (int *) NULL) == end) { er = cdissect(v, left, begin, mid); if (er == REG_OKAY) { er = cdissect(v, right, mid, end); if (er == REG_OKAY) { /* satisfaction */ MDEBUG(("%d: successful\n", t->id)); return REG_OKAY; } /* Reset left's matches (right should have done so itself) */ zaptreesubs(v, left); } if (er != REG_NOMATCH) return er; } NOERR(); /* that midpoint didn't work, find a new one */ if (mid == end) { /* all possibilities exhausted */ MDEBUG(("%d: no midpoint\n", t->id)); return REG_NOMATCH; } mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL); NOERR(); if (mid == NULL) { /* failed to find a new one */ MDEBUG(("%d: failed midpoint\n", t->id)); return REG_NOMATCH; } MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); } /* can't get here */ return REG_ASSERT; } /* * cbrdissect - dissect match for backref node * * The backref match might already have been verified by dfa_backref(), * but we don't know that for sure so must check it here. */ static int /* regexec return code */ cbrdissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { int n = t->backno; size_t numreps; size_t tlen; size_t brlen; chr *brstring; chr *p; int min = t->min; int max = t->max; assert(t != NULL); assert(t->op == 'b'); assert(n >= 0); assert((size_t) n < v->nmatch); MDEBUG(("%d: cbrdissect %d{%d-%d} %ld-%ld\n", t->id, n, min, max, LOFF(begin), LOFF(end))); /* get the backreferenced string */ if (v->pmatch[n].rm_so == -1) return REG_NOMATCH; brstring = v->start + v->pmatch[n].rm_so; brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so; /* special cases for zero-length strings */ if (brlen == 0) { /* * matches only if target is zero length, but any number of * repetitions can be considered to be present */ if (begin == end && min <= max) { MDEBUG(("%d: backref matched trivially\n", t->id)); return REG_OKAY; } return REG_NOMATCH; } if (begin == end) { /* matches only if zero repetitions are okay */ if (min == 0) { MDEBUG(("%d: backref matched trivially\n", t->id)); return REG_OKAY; } return REG_NOMATCH; } /* * check target length to see if it could possibly be an allowed number of * repetitions of brstring */ assert(end > begin); tlen = end - begin; if (tlen % brlen != 0) return REG_NOMATCH; numreps = tlen / brlen; if (numreps < min || (numreps > max && max != DUPINF)) return REG_NOMATCH; /* okay, compare the actual string contents */ p = begin; while (numreps-- > 0) { if ((*v->g->compare) (brstring, p, brlen) != 0) return REG_NOMATCH; p += brlen; } MDEBUG(("%d: backref matched\n", t->id)); return REG_OKAY; } /* * caltdissect - dissect match for alternation node */ static int /* regexec return code */ caltdissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { struct dfa *d; int er; assert(t->op == '|'); t = t->child; /* there should be at least 2 alternatives */ assert(t != NULL && t->sibling != NULL); while (t != NULL) { assert(t->cnfa.nstates > 0); MDEBUG(("%d: caltdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end))); d = getsubdfa(v, t); NOERR(); if (longest(v, d, begin, end, (int *) NULL) == end) { MDEBUG(("%d: caltdissect matched\n", t->id)); er = cdissect(v, t, begin, end); if (er != REG_NOMATCH) return er; } NOERR(); t = t->sibling; } return REG_NOMATCH; } /* * citerdissect - dissect match for iteration node */ static int /* regexec return code */ citerdissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { struct dfa *d; chr **endpts; chr *limit; int min_matches; size_t max_matches; int nverified; int k; int i; int er; assert(t->op == '*'); assert(t->child != NULL && t->child->cnfa.nstates > 0); assert(!(t->child->flags & SHORTER)); assert(begin <= end); MDEBUG(("%d: citerdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end))); /* * For the moment, assume the minimum number of matches is 1. If zero * matches are allowed, and the target string is empty, we are allowed to * match regardless of the contents of the iter node --- but we would * prefer to match once, so that capturing parens get set. (An example of * the concern here is a pattern like "()*\1", which historically this * code has allowed to succeed.) Therefore, we deal with the zero-matches * case at the bottom, after failing to find any other way to match. */ min_matches = t->min; if (min_matches <= 0) min_matches = 1; /* * We need workspace to track the endpoints of each sub-match. Normally * we consider only nonzero-length sub-matches, so there can be at most * end-begin of them. However, if min is larger than that, we will also * consider zero-length sub-matches in order to find enough matches. * * For convenience, endpts[0] contains the "begin" pointer and we store * sub-match endpoints in endpts[1..max_matches]. */ max_matches = end - begin; if (max_matches > t->max && t->max != DUPINF) max_matches = t->max; if (max_matches < min_matches) max_matches = min_matches; endpts = MALLOC_ARRAY(chr *, max_matches + 1); if (endpts == NULL) return REG_ESPACE; endpts[0] = begin; d = getsubdfa(v, t->child); if (ISERR()) { FREE(endpts); return v->err; } /* * Our strategy is to first find a set of sub-match endpoints that are * valid according to the child node's DFA, and then recursively dissect * each sub-match to confirm validity. If any validity check fails, * backtrack that sub-match and try again. And, when we next try for a * validity check, we need not recheck any successfully verified * sub-matches that we didn't move the endpoints of. nverified remembers * how many sub-matches are currently known okay. */ /* initialize to consider first sub-match */ nverified = 0; k = 1; limit = end; /* iterate until satisfaction or failure */ while (k > 0) { /* try to find an endpoint for the k'th sub-match */ endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL); if (ISERR()) { FREE(endpts); return v->err; } if (endpts[k] == NULL) { /* no match possible, so see if we can shorten previous one */ k--; goto backtrack; } MDEBUG(("%d: working endpoint %d: %ld\n", t->id, k, LOFF(endpts[k]))); /* k'th sub-match can no longer be considered verified */ if (nverified >= k) nverified = k - 1; if (endpts[k] != end) { /* haven't reached end yet, try another iteration if allowed */ if (k >= max_matches) { /* must try to shorten some previous match */ k--; goto backtrack; } /* reject zero-length match unless necessary to achieve min */ if (endpts[k] == endpts[k - 1] && (k >= min_matches || min_matches - k < end - endpts[k])) goto backtrack; k++; limit = end; continue; } /* * We've identified a way to divide the string into k sub-matches that * works so far as the child DFA can tell. If k is an allowed number * of matches, start the slow part: recurse to verify each sub-match. * We always have k <= max_matches, needn't check that. */ if (k < min_matches) goto backtrack; MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); for (i = nverified + 1; i <= k; i++) { /* zap any match data from a non-last iteration */ zaptreesubs(v, t->child); er = cdissect(v, t->child, endpts[i - 1], endpts[i]); if (er == REG_OKAY) { nverified = i; continue; } if (er == REG_NOMATCH) break; /* oops, something failed */ FREE(endpts); return er; } if (i > k) { /* satisfaction */ MDEBUG(("%d: successful\n", t->id)); FREE(endpts); return REG_OKAY; } /* i'th match failed to verify, so backtrack it */ k = i; backtrack: /* * Must consider shorter versions of the k'th sub-match. However, * we'll only ask for a zero-length match if necessary. */ while (k > 0) { chr *prev_end = endpts[k - 1]; if (endpts[k] > prev_end) { limit = endpts[k] - 1; if (limit > prev_end || (k < min_matches && min_matches - k >= end - prev_end)) { /* break out of backtrack loop, continue the outer one */ break; } } /* can't shorten k'th sub-match any more, consider previous one */ k--; } } /* all possibilities exhausted */ FREE(endpts); /* * Now consider the possibility that we can match to a zero-length string * by using zero repetitions. */ if (t->min == 0 && begin == end) { MDEBUG(("%d: allowing zero matches\n", t->id)); return REG_OKAY; } MDEBUG(("%d: failed\n", t->id)); return REG_NOMATCH; } /* * creviterdissect - dissect match for iteration node, shortest-first */ static int /* regexec return code */ creviterdissect(struct vars *v, struct subre *t, chr *begin, /* beginning of relevant substring */ chr *end) /* end of same */ { struct dfa *d; chr **endpts; chr *limit; int min_matches; size_t max_matches; int nverified; int k; int i; int er; assert(t->op == '*'); assert(t->child != NULL && t->child->cnfa.nstates > 0); assert(t->child->flags & SHORTER); assert(begin <= end); MDEBUG(("%d: creviterdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end))); /* * If zero matches are allowed, and target string is empty, just declare * victory. OTOH, if target string isn't empty, zero matches can't work * so we pretend the min is 1. */ min_matches = t->min; if (min_matches <= 0) { if (begin == end) { MDEBUG(("%d: allowing zero matches\n", t->id)); return REG_OKAY; } min_matches = 1; } /* * We need workspace to track the endpoints of each sub-match. Normally * we consider only nonzero-length sub-matches, so there can be at most * end-begin of them. However, if min is larger than that, we will also * consider zero-length sub-matches in order to find enough matches. * * For convenience, endpts[0] contains the "begin" pointer and we store * sub-match endpoints in endpts[1..max_matches]. */ max_matches = end - begin; if (max_matches > t->max && t->max != DUPINF) max_matches = t->max; if (max_matches < min_matches) max_matches = min_matches; endpts = MALLOC_ARRAY(chr *, max_matches + 1); if (endpts == NULL) return REG_ESPACE; endpts[0] = begin; d = getsubdfa(v, t->child); if (ISERR()) { FREE(endpts); return v->err; } /* * Our strategy is to first find a set of sub-match endpoints that are * valid according to the child node's DFA, and then recursively dissect * each sub-match to confirm validity. If any validity check fails, * backtrack that sub-match and try again. And, when we next try for a * validity check, we need not recheck any successfully verified * sub-matches that we didn't move the endpoints of. nverified remembers * how many sub-matches are currently known okay. */ /* initialize to consider first sub-match */ nverified = 0; k = 1; limit = begin; /* iterate until satisfaction or failure */ while (k > 0) { /* disallow zero-length match unless necessary to achieve min */ if (limit == endpts[k - 1] && limit != end && (k >= min_matches || min_matches - k < end - limit)) limit++; /* if this is the last allowed sub-match, it must reach to the end */ if (k >= max_matches) limit = end; /* try to find an endpoint for the k'th sub-match */ endpts[k] = shortest(v, d, endpts[k - 1], limit, end, (chr **) NULL, (int *) NULL); if (ISERR()) { FREE(endpts); return v->err; } if (endpts[k] == NULL) { /* no match possible, so see if we can lengthen previous one */ k--; goto backtrack; } MDEBUG(("%d: working endpoint %d: %ld\n", t->id, k, LOFF(endpts[k]))); /* k'th sub-match can no longer be considered verified */ if (nverified >= k) nverified = k - 1; if (endpts[k] != end) { /* haven't reached end yet, try another iteration if allowed */ if (k >= max_matches) { /* must try to lengthen some previous match */ k--; goto backtrack; } k++; limit = endpts[k - 1]; continue; } /* * We've identified a way to divide the string into k sub-matches that * works so far as the child DFA can tell. If k is an allowed number * of matches, start the slow part: recurse to verify each sub-match. * We always have k <= max_matches, needn't check that. */ if (k < min_matches) goto backtrack; MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); for (i = nverified + 1; i <= k; i++) { /* zap any match data from a non-last iteration */ zaptreesubs(v, t->child); er = cdissect(v, t->child, endpts[i - 1], endpts[i]); if (er == REG_OKAY) { nverified = i; continue; } if (er == REG_NOMATCH) break; /* oops, something failed */ FREE(endpts); return er; } if (i > k) { /* satisfaction */ MDEBUG(("%d: successful\n", t->id)); FREE(endpts); return REG_OKAY; } /* i'th match failed to verify, so backtrack it */ k = i; backtrack: /* * Must consider longer versions of the k'th sub-match. */ while (k > 0) { if (endpts[k] < end) { limit = endpts[k] + 1; /* break out of backtrack loop, continue the outer one */ break; } /* can't lengthen k'th sub-match any more, consider previous one */ k--; } } /* all possibilities exhausted */ MDEBUG(("%d: failed\n", t->id)); FREE(endpts); return REG_NOMATCH; } #include "rege_dfa.c"