Branch data 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 backno; /* if DFA for a backref, subno it refers to */
81 : : short backmin; /* min repetitions for backref */
82 : : short backmax; /* max repetitions for backref */
83 : : bool ismalloced; /* should this struct dfa be freed? */
84 : : bool arraysmalloced; /* should its subsidiary arrays be freed? */
85 : : };
86 : :
87 : : #define WORK 1 /* number of work bitvectors needed */
88 : :
89 : : /* setup for non-malloc allocation for small cases */
90 : : #define FEWSTATES 20 /* must be less than UBITS */
91 : : #define FEWCOLORS 15
92 : : struct smalldfa
93 : : {
94 : : struct dfa dfa; /* must be first */
95 : : struct sset ssets[FEWSTATES * 2];
96 : : unsigned statesarea[FEWSTATES * 2 + WORK];
97 : : struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
98 : : struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
99 : : };
100 : :
101 : : #define DOMALLOC ((struct smalldfa *)NULL) /* force malloc */
102 : :
103 : :
104 : :
105 : : /* internal variables, bundled for easy passing around */
106 : : struct vars
107 : : {
108 : : regex_t *re;
109 : : struct guts *g;
110 : : int eflags; /* copies of arguments */
111 : : size_t nmatch;
112 : : regmatch_t *pmatch;
113 : : rm_detail_t *details;
114 : : chr *start; /* start of string */
115 : : chr *search_start; /* search start of string */
116 : : chr *stop; /* just past end of string */
117 : : int err; /* error code if any (0 none) */
118 : : struct dfa **subdfas; /* per-tree-subre DFAs */
119 : : struct dfa **ladfas; /* per-lacon-subre DFAs */
120 : : struct sset **lblastcss; /* per-lacon-subre lookbehind restart data */
121 : : chr **lblastcp; /* per-lacon-subre lookbehind restart data */
122 : : struct smalldfa dfa1;
123 : : struct smalldfa dfa2;
124 : : };
125 : :
126 : : #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */
127 : : #define ISERR() VISERR(v)
128 : : #define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e)))
129 : : #define ERR(e) VERR(v, e) /* record an error */
130 : : #define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */
131 : : #define OFF(p) ((p) - v->start)
132 : : #define LOFF(p) ((long)OFF(p))
133 : :
134 : :
135 : :
136 : : /*
137 : : * forward declarations
138 : : */
139 : : /* === regexec.c === */
140 : : static struct dfa *getsubdfa(struct vars *v, struct subre *t);
141 : : static struct dfa *getladfa(struct vars *v, int n);
142 : : static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm);
143 : : static int cfind(struct vars *v, struct cnfa *cnfa, struct colormap *cm);
144 : : static int cfindloop(struct vars *v, struct cnfa *cnfa, struct colormap *cm,
145 : : struct dfa *d, struct dfa *s, chr **coldp);
146 : : static void zapallsubs(regmatch_t *p, size_t n);
147 : : static void zaptreesubs(struct vars *v, struct subre *t);
148 : : static void subset(struct vars *v, struct subre *sub, chr *begin, chr *end);
149 : : static int cdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
150 : : static int ccondissect(struct vars *v, struct subre *t, chr *begin, chr *end);
151 : : static int crevcondissect(struct vars *v, struct subre *t, chr *begin, chr *end);
152 : : static int cbrdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
153 : : static int caltdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
154 : : static int citerdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
155 : : static int creviterdissect(struct vars *v, struct subre *t, chr *begin, chr *end);
156 : :
157 : : /* === rege_dfa.c === */
158 : : static chr *longest(struct vars *v, struct dfa *d,
159 : : chr *start, chr *stop, int *hitstopp);
160 : : static chr *shortest(struct vars *v, struct dfa *d, chr *start, chr *min,
161 : : chr *max, chr **coldp, int *hitstopp);
162 : : static int matchuntil(struct vars *v, struct dfa *d, chr *probe,
163 : : struct sset **lastcss, chr **lastcp);
164 : : static chr *dfa_backref(struct vars *v, struct dfa *d, chr *start,
165 : : chr *min, chr *max, bool shortest);
166 : : static chr *lastcold(struct vars *v, struct dfa *d);
167 : : static struct dfa *newdfa(struct vars *v, struct cnfa *cnfa,
168 : : struct colormap *cm, struct smalldfa *sml);
169 : : static void freedfa(struct dfa *d);
170 : : static unsigned hash(unsigned *uv, int n);
171 : : static struct sset *initialize(struct vars *v, struct dfa *d, chr *start);
172 : : static struct sset *miss(struct vars *v, struct dfa *d, struct sset *css,
173 : : color co, chr *cp, chr *start);
174 : : static int lacon(struct vars *v, struct cnfa *pcnfa, chr *cp, color co);
175 : : static struct sset *getvacant(struct vars *v, struct dfa *d, chr *cp,
176 : : chr *start);
177 : : static struct sset *pickss(struct vars *v, struct dfa *d, chr *cp,
178 : : chr *start);
179 : :
180 : :
181 : : /*
182 : : * pg_regexec - match regular expression
183 : : */
184 : : int
185 : 5758172 : pg_regexec(regex_t *re,
186 : : const chr *string,
187 : : size_t len,
188 : : size_t search_start,
189 : : rm_detail_t *details,
190 : : size_t nmatch,
191 : : regmatch_t pmatch[],
192 : : int flags)
193 : : {
194 : : struct vars var;
195 : 5758172 : struct vars *v = &var;
196 : : int st;
197 : : size_t n;
198 : : size_t i;
199 : : int backref;
200 : :
201 : : #define LOCALMAT 20
202 : : regmatch_t mat[LOCALMAT];
203 : :
204 : : #define LOCALDFAS 40
205 : : struct dfa *subdfas[LOCALDFAS];
206 : :
207 : : /* sanity checks */
208 [ + - + - : 5758172 : if (re == NULL || string == NULL || re->re_magic != REMAGIC)
- + ]
209 : 0 : return REG_INVARG;
210 [ - + ]: 5758172 : if (re->re_csize != sizeof(chr))
211 : 0 : return REG_MIXED;
212 [ + + ]: 5758172 : if (search_start > len)
213 : 5 : return REG_NOMATCH;
214 : :
215 : : /* Initialize locale-dependent support */
216 : 5758167 : pg_set_regex_collation(re->re_collation);
217 : :
218 : : /* setup */
219 : 5758167 : v->re = re;
220 : 5758167 : v->g = (struct guts *) re->re_guts;
221 [ + + - + ]: 5758167 : if ((v->g->cflags & REG_EXPECT) && details == NULL)
222 : 0 : return REG_INVARG;
223 [ + + ]: 5758167 : if (v->g->info & REG_UIMPOSSIBLE)
224 : 721 : return REG_NOMATCH;
225 : 5757446 : backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
226 : 5757446 : v->eflags = flags;
227 [ + + + + ]: 5757446 : if (backref && nmatch <= v->g->nsub)
228 : : {
229 : : /* need larger work area */
230 : 149 : v->nmatch = v->g->nsub + 1;
231 [ + + ]: 149 : if (v->nmatch <= LOCALMAT)
232 : 148 : v->pmatch = mat;
233 : : else
234 : 1 : v->pmatch = MALLOC_ARRAY(regmatch_t, v->nmatch);
235 [ - + ]: 149 : if (v->pmatch == NULL)
236 : 0 : return REG_ESPACE;
237 : 149 : zapallsubs(v->pmatch, v->nmatch);
238 : : }
239 : : else
240 : : {
241 : : /* we can store results directly in caller's array */
242 : 5757297 : v->pmatch = pmatch;
243 : : /* ensure any extra entries in caller's array are filled with -1 */
244 [ + + ]: 5757297 : if (nmatch > 0)
245 : 583228 : zapallsubs(pmatch, nmatch);
246 : : /* then forget about extra entries, to avoid useless work in find() */
247 [ + + ]: 5757297 : if (nmatch > v->g->nsub + 1)
248 : 670 : nmatch = v->g->nsub + 1;
249 : 5757297 : v->nmatch = nmatch;
250 : : }
251 : 5757446 : v->details = details;
252 : 5757446 : v->start = (chr *) string;
253 : 5757446 : v->search_start = (chr *) string + search_start;
254 : 5757446 : v->stop = (chr *) string + len;
255 : 5757446 : v->err = 0;
256 : 5757446 : v->subdfas = NULL;
257 : 5757446 : v->ladfas = NULL;
258 : 5757446 : v->lblastcss = NULL;
259 : 5757446 : v->lblastcp = NULL;
260 : : /* below this point, "goto cleanup" will behave sanely */
261 : :
262 : : assert(v->g->ntree >= 0);
263 : 5757446 : n = (size_t) v->g->ntree;
264 [ + + ]: 5757446 : if (n <= LOCALDFAS)
265 : 5757444 : v->subdfas = subdfas;
266 : : else
267 : : {
268 : : /* ntree is surely less than the number of states, so this is safe: */
269 : 2 : v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
270 [ - + ]: 2 : if (v->subdfas == NULL)
271 : : {
272 : 0 : st = REG_ESPACE;
273 : 0 : goto cleanup;
274 : : }
275 : : }
276 [ + + ]: 17294068 : for (i = 0; i < n; i++)
277 : 11536622 : v->subdfas[i] = NULL;
278 : :
279 : : assert(v->g->nlacons >= 0);
280 : 5757446 : n = (size_t) v->g->nlacons;
281 [ + + ]: 5757446 : if (n > 0)
282 : : {
283 : : /* nlacons is surely less than the number of arcs, so this is safe: */
284 : 1040 : v->ladfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
285 [ - + ]: 1040 : if (v->ladfas == NULL)
286 : : {
287 : 0 : st = REG_ESPACE;
288 : 0 : goto cleanup;
289 : : }
290 [ + + ]: 3168 : for (i = 0; i < n; i++)
291 : 2128 : v->ladfas[i] = NULL;
292 : 1040 : v->lblastcss = (struct sset **) MALLOC(n * sizeof(struct sset *));
293 : 1040 : v->lblastcp = (chr **) MALLOC(n * sizeof(chr *));
294 [ + - - + ]: 1040 : if (v->lblastcss == NULL || v->lblastcp == NULL)
295 : : {
296 : 0 : st = REG_ESPACE;
297 : 0 : goto cleanup;
298 : : }
299 [ + + ]: 3168 : for (i = 0; i < n; i++)
300 : : {
301 : 2128 : v->lblastcss[i] = NULL;
302 : 2128 : v->lblastcp[i] = NULL;
303 : : }
304 : : }
305 : :
306 : : /* do it */
307 : : assert(v->g->tree != NULL);
308 [ + + ]: 5757446 : if (backref)
309 : 208 : st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
310 : : else
311 : 5757238 : st = find(v, &v->g->tree->cnfa, &v->g->cmap);
312 : :
313 : : /* on success, ensure caller's match vector is filled correctly */
314 [ + + + + ]: 5757446 : if (st == REG_OKAY && nmatch > 0)
315 : : {
316 [ + + ]: 470768 : if (v->pmatch != pmatch)
317 : : {
318 : : /* copy portion of match vector over from (larger) work area */
319 : : assert(nmatch <= v->nmatch);
320 : 33 : memcpy(VS(pmatch), VS(v->pmatch), nmatch * sizeof(regmatch_t));
321 : : }
322 [ + + ]: 470768 : if (v->g->cflags & REG_NOSUB)
323 : : {
324 : : /* don't expose possibly-partial sub-match results to caller */
325 : 466900 : zapallsubs(pmatch, nmatch);
326 : : }
327 : : }
328 : :
329 : : /* clean up */
330 : 5290546 : cleanup:
331 [ + + + + ]: 5757446 : if (v->pmatch != pmatch && v->pmatch != mat)
332 : 1 : FREE(v->pmatch);
333 [ + - ]: 5757446 : if (v->subdfas != NULL)
334 : : {
335 : 5757446 : n = (size_t) v->g->ntree;
336 [ + + ]: 17294068 : for (i = 0; i < n; i++)
337 : : {
338 [ + + ]: 11536622 : if (v->subdfas[i] != NULL)
339 : 16876 : freedfa(v->subdfas[i]);
340 : : }
341 [ + + ]: 5757446 : if (v->subdfas != subdfas)
342 : 2 : FREE(v->subdfas);
343 : : }
344 [ + + ]: 5757446 : if (v->ladfas != NULL)
345 : : {
346 : 1040 : n = (size_t) v->g->nlacons;
347 [ + + ]: 3168 : for (i = 0; i < n; i++)
348 : : {
349 [ + + ]: 2128 : if (v->ladfas[i] != NULL)
350 : 75 : freedfa(v->ladfas[i]);
351 : : }
352 : 1040 : FREE(v->ladfas);
353 : : }
354 [ + + ]: 5757446 : if (v->lblastcss != NULL)
355 : 1040 : FREE(v->lblastcss);
356 [ + + ]: 5757446 : if (v->lblastcp != NULL)
357 : 1040 : FREE(v->lblastcp);
358 : :
359 : : #ifdef REG_DEBUG
360 : : if (v->eflags & (REG_FTRACE | REG_MTRACE))
361 : : fflush(stdout);
362 : : #endif
363 : :
364 : 5757446 : return st;
365 : : }
366 : :
367 : : /*
368 : : * getsubdfa - create or re-fetch the DFA for a tree subre node
369 : : *
370 : : * We only need to create the DFA once per overall regex execution.
371 : : * The DFA will be freed by the cleanup step in pg_regexec().
372 : : */
373 : : static struct dfa *
374 : 17860 : getsubdfa(struct vars *v,
375 : : struct subre *t)
376 : : {
377 : 17860 : struct dfa *d = v->subdfas[t->id];
378 : :
379 [ + + ]: 17860 : if (d == NULL)
380 : : {
381 : 16876 : d = newdfa(v, &t->cnfa, &v->g->cmap, DOMALLOC);
382 [ - + ]: 16876 : if (d == NULL)
383 : 0 : return NULL;
384 : : /* set up additional info if this is a backref node */
385 [ + + ]: 16876 : if (t->op == 'b')
386 : : {
387 : 199 : d->backno = t->backno;
388 : 199 : d->backmin = t->min;
389 : 199 : d->backmax = t->max;
390 : : }
391 : 16876 : v->subdfas[t->id] = d;
392 : : }
393 : 17860 : return d;
394 : : }
395 : :
396 : : /*
397 : : * getladfa - create or re-fetch the DFA for a LACON subre node
398 : : *
399 : : * Same as above, but for LACONs.
400 : : */
401 : : static struct dfa *
402 : 158 : getladfa(struct vars *v,
403 : : int n)
404 : : {
405 : : assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);
406 : :
407 [ + + ]: 158 : if (v->ladfas[n] == NULL)
408 : : {
409 : 75 : struct subre *sub = &v->g->lacons[n];
410 : :
411 : 75 : v->ladfas[n] = newdfa(v, &sub->cnfa, &v->g->cmap, DOMALLOC);
412 : : /* a LACON can't contain a backref, so nothing else to do */
413 : : }
414 : 158 : return v->ladfas[n];
415 : : }
416 : :
417 : : /*
418 : : * find - find a match for the main NFA (no-complications case)
419 : : */
420 : : static int
421 : 5757238 : find(struct vars *v,
422 : : struct cnfa *cnfa,
423 : : struct colormap *cm)
424 : : {
425 : : struct dfa *s;
426 : : struct dfa *d;
427 : : chr *begin;
428 : 5757238 : chr *end = NULL;
429 : : chr *cold;
430 : : chr *open; /* open and close of range of possible starts */
431 : : chr *close;
432 : : int hitend;
433 : 5757238 : int shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;
434 : :
435 : : /* first, a shot with the search RE */
436 : 5757238 : s = newdfa(v, &v->g->search, cm, &v->dfa1);
437 [ - + ]: 5757238 : if (s == NULL)
438 : 0 : return v->err;
439 : : MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
440 : 5757238 : cold = NULL;
441 : 5757238 : close = shortest(v, s, v->search_start, v->search_start, v->stop,
442 : : &cold, (int *) NULL);
443 : 5757238 : freedfa(s);
444 [ - + ]: 5757238 : NOERR();
445 [ + + ]: 5757238 : if (v->g->cflags & REG_EXPECT)
446 : : {
447 : : assert(v->details != NULL);
448 [ + - ]: 27 : if (cold != NULL)
449 : 27 : v->details->rm_extend.rm_so = OFF(cold);
450 : : else
451 : 0 : v->details->rm_extend.rm_so = OFF(v->stop);
452 : 27 : v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
453 : : }
454 [ + + ]: 5757238 : if (close == NULL) /* not found */
455 : 5156553 : return REG_NOMATCH;
456 [ + + ]: 600685 : if (v->nmatch == 0) /* found, don't need exact location */
457 : 129991 : return REG_OKAY;
458 : :
459 : : /* find starting point and match */
460 : : assert(cold != NULL);
461 : 470694 : open = cold;
462 : 470694 : cold = NULL;
463 : : MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
464 : 470694 : d = newdfa(v, cnfa, cm, &v->dfa1);
465 [ - + ]: 470694 : if (d == NULL)
466 : 0 : return v->err;
467 [ + - ]: 470725 : for (begin = open; begin <= close; begin++)
468 : : {
469 : : MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
470 [ + + ]: 470725 : if (shorter)
471 : 86 : end = shortest(v, d, begin, begin, v->stop,
472 : : (chr **) NULL, &hitend);
473 : : else
474 : 470639 : end = longest(v, d, begin, v->stop, &hitend);
475 [ - + ]: 470725 : if (ISERR())
476 : : {
477 : 0 : freedfa(d);
478 : 0 : return v->err;
479 : : }
480 [ + + + + ]: 470725 : if (hitend && cold == NULL)
481 : 4766 : cold = begin;
482 [ + + ]: 470725 : if (end != NULL)
483 : 470694 : break; /* NOTE BREAK OUT */
484 : : }
485 : : assert(end != NULL); /* search RE succeeded so loop should */
486 : 470694 : freedfa(d);
487 : :
488 : : /* and pin down details */
489 : : assert(v->nmatch > 0);
490 : 470694 : v->pmatch[0].rm_so = OFF(begin);
491 : 470694 : v->pmatch[0].rm_eo = OFF(end);
492 [ + + ]: 470694 : if (v->g->cflags & REG_EXPECT)
493 : : {
494 [ + + ]: 10 : if (cold != NULL)
495 : 5 : v->details->rm_extend.rm_so = OFF(cold);
496 : : else
497 : 5 : v->details->rm_extend.rm_so = OFF(v->stop);
498 : 10 : v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
499 : : }
500 [ + + ]: 470694 : if (v->nmatch == 1) /* no need for submatches */
501 : 467701 : return REG_OKAY;
502 : :
503 : : /* find submatches */
504 : 2993 : return cdissect(v, v->g->tree, begin, end);
505 : : }
506 : :
507 : : /*
508 : : * cfind - find a match for the main NFA (with complications)
509 : : */
510 : : static int
511 : 208 : cfind(struct vars *v,
512 : : struct cnfa *cnfa,
513 : : struct colormap *cm)
514 : : {
515 : : struct dfa *s;
516 : : struct dfa *d;
517 : : chr *cold;
518 : : int ret;
519 : :
520 : 208 : s = newdfa(v, &v->g->search, cm, &v->dfa1);
521 [ - + ]: 208 : if (s == NULL)
522 : 0 : return v->err;
523 : 208 : d = newdfa(v, cnfa, cm, &v->dfa2);
524 [ - + ]: 208 : if (d == NULL)
525 : : {
526 : 0 : freedfa(s);
527 : 0 : return v->err;
528 : : }
529 : :
530 : 208 : ret = cfindloop(v, cnfa, cm, d, s, &cold);
531 : :
532 : 208 : freedfa(d);
533 : 208 : freedfa(s);
534 [ - + ]: 208 : NOERR();
535 [ - + ]: 208 : if (v->g->cflags & REG_EXPECT)
536 : : {
537 : : assert(v->details != NULL);
538 [ # # ]: 0 : if (cold != NULL)
539 : 0 : v->details->rm_extend.rm_so = OFF(cold);
540 : : else
541 : 0 : v->details->rm_extend.rm_so = OFF(v->stop);
542 : 0 : v->details->rm_extend.rm_eo = OFF(v->stop); /* unknown */
543 : : }
544 : 208 : return ret;
545 : : }
546 : :
547 : : /*
548 : : * cfindloop - the heart of cfind
549 : : */
550 : : static int
551 : 208 : cfindloop(struct vars *v,
552 : : struct cnfa *cnfa,
553 : : struct colormap *cm,
554 : : struct dfa *d,
555 : : struct dfa *s,
556 : : chr **coldp) /* where to put coldstart pointer */
557 : : {
558 : : chr *begin;
559 : : chr *end;
560 : : chr *cold;
561 : : chr *open; /* open and close of range of possible starts */
562 : : chr *close;
563 : : chr *estart;
564 : : chr *estop;
565 : : int er;
566 : 208 : int shorter = v->g->tree->flags & SHORTER;
567 : : int hitend;
568 : :
569 : : assert(d != NULL && s != NULL);
570 : 208 : cold = NULL;
571 : 208 : close = v->search_start;
572 : : do
573 : : {
574 : : /* Search with the search RE for match range at/beyond "close" */
575 : : MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
576 : 232 : close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
577 [ - + ]: 232 : if (ISERR())
578 : : {
579 : 0 : *coldp = cold;
580 : 0 : return v->err;
581 : : }
582 [ + + ]: 232 : if (close == NULL)
583 : 23 : break; /* no more possible match anywhere */
584 : : assert(cold != NULL);
585 : 209 : open = cold;
586 : 209 : cold = NULL;
587 : : /* Search for matches starting between "open" and "close" inclusive */
588 : : MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
589 [ + + ]: 749 : for (begin = open; begin <= close; begin++)
590 : : {
591 : : MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
592 : 659 : estart = begin;
593 : 659 : estop = v->stop;
594 : : for (;;)
595 : : {
596 : : /* Here we use the top node's detailed RE */
597 [ + + ]: 942 : if (shorter)
598 : 141 : end = shortest(v, d, begin, estart,
599 : : estop, (chr **) NULL, &hitend);
600 : : else
601 : 801 : end = longest(v, d, begin, estop,
602 : : &hitend);
603 [ - + ]: 942 : if (ISERR())
604 : : {
605 : 0 : *coldp = cold;
606 : 0 : return v->err;
607 : : }
608 [ + + + + ]: 942 : if (hitend && cold == NULL)
609 : 147 : cold = begin;
610 [ + + ]: 942 : if (end == NULL)
611 : 513 : break; /* no match with this begin point, try next */
612 : : MDEBUG(("tentative end %ld\n", LOFF(end)));
613 : : /* Dissect the potential match to see if it really matches */
614 : 429 : er = cdissect(v, v->g->tree, begin, end);
615 [ + + ]: 429 : if (er == REG_OKAY)
616 : : {
617 [ + - ]: 119 : if (v->nmatch > 0)
618 : : {
619 : 119 : v->pmatch[0].rm_so = OFF(begin);
620 : 119 : v->pmatch[0].rm_eo = OFF(end);
621 : : }
622 : 119 : *coldp = cold;
623 : 119 : return REG_OKAY;
624 : : }
625 [ - + ]: 310 : if (er != REG_NOMATCH)
626 : : {
627 [ # # ]: 0 : ERR(er);
628 : 0 : *coldp = cold;
629 : 0 : return er;
630 : : }
631 : : /* Try next longer/shorter match with same begin point */
632 [ + + ]: 310 : if (shorter)
633 : : {
634 [ + + ]: 119 : if (end == estop)
635 : 17 : break; /* no more, so try next begin point */
636 : 102 : estart = end + 1;
637 : : }
638 : : else
639 : : {
640 [ + + ]: 191 : if (end == begin)
641 : 10 : break; /* no more, so try next begin point */
642 : 181 : estop = end - 1;
643 : : }
644 : : } /* end loop over endpoint positions */
645 : : } /* end loop over beginning positions */
646 : :
647 : : /*
648 : : * If we get here, there is no possible match starting at or before
649 : : * "close", so consider matches beyond that. We'll do a fresh search
650 : : * with the search RE to find a new promising match range.
651 : : */
652 : 90 : close++;
653 [ + + ]: 90 : } while (close < v->stop);
654 : :
655 : 89 : *coldp = cold;
656 : 89 : return REG_NOMATCH;
657 : : }
658 : :
659 : : /*
660 : : * zapallsubs - initialize all subexpression matches to "no match"
661 : : *
662 : : * Note that p[0], the overall-match location, is not touched.
663 : : */
664 : : static void
665 : 1050277 : zapallsubs(regmatch_t *p,
666 : : size_t n)
667 : : {
668 : : size_t i;
669 : :
670 [ + + ]: 1061332 : for (i = n - 1; i > 0; i--)
671 : : {
672 : 11055 : p[i].rm_so = -1;
673 : 11055 : p[i].rm_eo = -1;
674 : : }
675 : 1050277 : }
676 : :
677 : : /*
678 : : * zaptreesubs - initialize subexpressions within subtree to "no match"
679 : : */
680 : : static void
681 : 739 : zaptreesubs(struct vars *v,
682 : : struct subre *t)
683 : : {
684 : 739 : int n = t->capno;
685 : : struct subre *t2;
686 : :
687 [ + + ]: 739 : if (n > 0)
688 : : {
689 [ + - ]: 328 : if ((size_t) n < v->nmatch)
690 : : {
691 : 328 : v->pmatch[n].rm_so = -1;
692 : 328 : v->pmatch[n].rm_eo = -1;
693 : : }
694 : : }
695 : :
696 [ + + ]: 988 : for (t2 = t->child; t2 != NULL; t2 = t2->sibling)
697 : 249 : zaptreesubs(v, t2);
698 : 739 : }
699 : :
700 : : /*
701 : : * subset - set subexpression match data for a successful subre
702 : : */
703 : : static void
704 : 5538 : subset(struct vars *v,
705 : : struct subre *sub,
706 : : chr *begin,
707 : : chr *end)
708 : : {
709 : 5538 : int n = sub->capno;
710 : :
711 : : assert(n > 0);
712 [ + + ]: 5538 : if ((size_t) n >= v->nmatch)
713 : 15 : return;
714 : :
715 : : MDEBUG(("%d: setting %d = %ld-%ld\n", sub->id, n, LOFF(begin), LOFF(end)));
716 : 5523 : v->pmatch[n].rm_so = OFF(begin);
717 : 5523 : v->pmatch[n].rm_eo = OFF(end);
718 : : }
719 : :
720 : : /*
721 : : * cdissect - check backrefs and determine subexpression matches
722 : : *
723 : : * cdissect recursively processes a subre tree to check matching of backrefs
724 : : * and/or identify submatch boundaries for capture nodes. The proposed match
725 : : * runs from "begin" to "end" (not including "end"), and we are basically
726 : : * "dissecting" it to see where the submatches are.
727 : : *
728 : : * Before calling any level of cdissect, the caller must have run the node's
729 : : * DFA and found that the proposed substring satisfies the DFA. (We make
730 : : * the caller do that because in concatenation and iteration nodes, it's
731 : : * much faster to check all the substrings against the child DFAs before we
732 : : * recurse.)
733 : : *
734 : : * A side-effect of a successful match is to save match locations for
735 : : * capturing subexpressions in v->pmatch[]. This is a little bit tricky,
736 : : * so we make the following rules:
737 : : * 1. Before initial entry to cdissect, all match data must have been
738 : : * cleared (this is seen to by zapallsubs).
739 : : * 2. Before any recursive entry to cdissect, the match data for that
740 : : * subexpression tree must be guaranteed clear (see zaptreesubs).
741 : : * 3. When returning REG_OKAY, each level of cdissect will have saved
742 : : * any relevant match locations.
743 : : * 4. When returning REG_NOMATCH, each level of cdissect will guarantee
744 : : * that its subexpression match locations are again clear.
745 : : * 5. No guarantees are made for error cases (i.e., other result codes).
746 : : * 6. When a level of cdissect abandons a successful sub-match, it will
747 : : * clear that subtree's match locations with zaptreesubs before trying
748 : : * any new DFA match or cdissect call for that subtree or any subtree
749 : : * to its right (that is, any subtree that could have a backref into the
750 : : * abandoned match).
751 : : * This may seem overly complicated, but it's difficult to simplify it
752 : : * because of the provision that match locations must be reset before
753 : : * any fresh DFA match (a rule that is needed to make dfa_backref safe).
754 : : * That means it won't work to just reset relevant match locations at the
755 : : * start of each cdissect level.
756 : : */
757 : : static int /* regexec return code */
758 : 20811 : cdissect(struct vars *v,
759 : : struct subre *t,
760 : : chr *begin, /* beginning of relevant substring */
761 : : chr *end) /* end of same */
762 : : {
763 : : int er;
764 : :
765 : : assert(t != NULL);
766 : : MDEBUG(("%d: cdissect %c %ld-%ld\n", t->id, t->op, LOFF(begin), LOFF(end)));
767 : :
768 : : /* handy place to check for operation cancel */
769 [ - + ]: 20811 : INTERRUPT(v->re);
770 : : /* ... and stack overrun */
771 [ - + ]: 20811 : if (STACK_TOO_DEEP(v->re))
772 : 0 : return REG_ETOOBIG;
773 : :
774 [ + + + + : 20811 : switch (t->op)
+ + - ]
775 : : {
776 : 11429 : case '=': /* terminal node */
777 : : assert(t->child == NULL);
778 : 11429 : er = REG_OKAY; /* no action, parent did the work */
779 : 11429 : break;
780 : 303 : case 'b': /* back reference */
781 : : assert(t->child == NULL);
782 : 303 : er = cbrdissect(v, t, begin, end);
783 : 303 : break;
784 : 8767 : case '.': /* concatenation */
785 : : assert(t->child != NULL);
786 [ + + ]: 8767 : if (t->child->flags & SHORTER) /* reverse scan */
787 : 237 : er = crevcondissect(v, t, begin, end);
788 : : else
789 : 8530 : er = ccondissect(v, t, begin, end);
790 : 8767 : break;
791 : 113 : case '|': /* alternation */
792 : : assert(t->child != NULL);
793 : 113 : er = caltdissect(v, t, begin, end);
794 : 113 : break;
795 : 167 : case '*': /* iteration */
796 : : assert(t->child != NULL);
797 [ + + ]: 167 : if (t->child->flags & SHORTER) /* reverse scan */
798 : 8 : er = creviterdissect(v, t, begin, end);
799 : : else
800 : 159 : er = citerdissect(v, t, begin, end);
801 : 167 : break;
802 : 32 : case '(': /* no-op capture node */
803 : : assert(t->child != NULL);
804 : 32 : er = cdissect(v, t->child, begin, end);
805 : 32 : break;
806 : 0 : default:
807 : 0 : er = REG_ASSERT;
808 : 0 : break;
809 : : }
810 : :
811 : : /*
812 : : * We should never have a match failure unless backrefs lurk below;
813 : : * otherwise, either caller failed to check the DFA, or there's some
814 : : * inconsistency between the DFA and the node's innards.
815 : : */
816 : : assert(er != REG_NOMATCH || (t->flags & BACKR));
817 : :
818 : : /*
819 : : * If this node is marked as capturing, save successful match's location.
820 : : */
821 [ + + + + ]: 20811 : if (t->capno > 0 && er == REG_OKAY)
822 : 5538 : subset(v, t, begin, end);
823 : :
824 : 20811 : return er;
825 : : }
826 : :
827 : : /*
828 : : * ccondissect - dissect match for concatenation node
829 : : */
830 : : static int /* regexec return code */
831 : 8530 : ccondissect(struct vars *v,
832 : : struct subre *t,
833 : : chr *begin, /* beginning of relevant substring */
834 : : chr *end) /* end of same */
835 : : {
836 : 8530 : struct subre *left = t->child;
837 : 8530 : struct subre *right = left->sibling;
838 : : struct dfa *d;
839 : : struct dfa *d2;
840 : : chr *mid;
841 : : int er;
842 : :
843 : : assert(t->op == '.');
844 : : assert(left != NULL && left->cnfa.nstates > 0);
845 : : assert(right != NULL && right->cnfa.nstates > 0);
846 : : assert(right->sibling == NULL);
847 : : assert(!(left->flags & SHORTER));
848 : :
849 : 8530 : d = getsubdfa(v, left);
850 [ - + ]: 8530 : NOERR();
851 : 8530 : d2 = getsubdfa(v, right);
852 [ - + ]: 8530 : NOERR();
853 : : MDEBUG(("%d: ccondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));
854 : :
855 : : /* pick a tentative midpoint */
856 : 8530 : mid = longest(v, d, begin, end, (int *) NULL);
857 [ - + ]: 8530 : NOERR();
858 [ + + ]: 8530 : if (mid == NULL)
859 : 8 : return REG_NOMATCH;
860 : : MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid)));
861 : :
862 : : /* iterate until satisfaction or failure */
863 : : for (;;)
864 : : {
865 : : /* try this midpoint on for size */
866 [ + + ]: 10114 : if (longest(v, d2, mid, end, (int *) NULL) == end)
867 : : {
868 : 8465 : er = cdissect(v, left, begin, mid);
869 [ + + ]: 8465 : if (er == REG_OKAY)
870 : : {
871 : 8391 : er = cdissect(v, right, mid, end);
872 [ + + ]: 8391 : if (er == REG_OKAY)
873 : : {
874 : : /* satisfaction */
875 : : MDEBUG(("%d: successful\n", t->id));
876 : 8033 : return REG_OKAY;
877 : : }
878 : : /* Reset left's matches (right should have done so itself) */
879 : 358 : zaptreesubs(v, left);
880 : : }
881 [ - + ]: 432 : if (er != REG_NOMATCH)
882 : 0 : return er;
883 : : }
884 [ - + ]: 2081 : NOERR();
885 : :
886 : : /* that midpoint didn't work, find a new one */
887 [ + + ]: 2081 : if (mid == begin)
888 : : {
889 : : /* all possibilities exhausted */
890 : : MDEBUG(("%d: no midpoint\n", t->id));
891 : 105 : return REG_NOMATCH;
892 : : }
893 : 1976 : mid = longest(v, d, begin, mid - 1, (int *) NULL);
894 [ - + ]: 1976 : NOERR();
895 [ + + ]: 1976 : if (mid == NULL)
896 : : {
897 : : /* failed to find a new one */
898 : : MDEBUG(("%d: failed midpoint\n", t->id));
899 : 384 : return REG_NOMATCH;
900 : : }
901 : : MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
902 : : }
903 : :
904 : : /* can't get here */
905 : : return REG_ASSERT;
906 : : }
907 : :
908 : : /*
909 : : * crevcondissect - dissect match for concatenation node, shortest-first
910 : : */
911 : : static int /* regexec return code */
912 : 237 : crevcondissect(struct vars *v,
913 : : struct subre *t,
914 : : chr *begin, /* beginning of relevant substring */
915 : : chr *end) /* end of same */
916 : : {
917 : 237 : struct subre *left = t->child;
918 : 237 : struct subre *right = left->sibling;
919 : : struct dfa *d;
920 : : struct dfa *d2;
921 : : chr *mid;
922 : : int er;
923 : :
924 : : assert(t->op == '.');
925 : : assert(left != NULL && left->cnfa.nstates > 0);
926 : : assert(right != NULL && right->cnfa.nstates > 0);
927 : : assert(right->sibling == NULL);
928 : : assert(left->flags & SHORTER);
929 : :
930 : 237 : d = getsubdfa(v, left);
931 [ - + ]: 237 : NOERR();
932 : 237 : d2 = getsubdfa(v, right);
933 [ - + ]: 237 : NOERR();
934 : : MDEBUG(("%d: crevcondissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));
935 : :
936 : : /* pick a tentative midpoint */
937 : 237 : mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
938 [ - + ]: 237 : NOERR();
939 [ + - ]: 237 : if (mid == NULL)
940 : 0 : return REG_NOMATCH;
941 : : MDEBUG(("%d: tentative midpoint %ld\n", t->id, LOFF(mid)));
942 : :
943 : : /* iterate until satisfaction or failure */
944 : : for (;;)
945 : : {
946 : : /* try this midpoint on for size */
947 [ + + ]: 853 : if (longest(v, d2, mid, end, (int *) NULL) == end)
948 : : {
949 : 128 : er = cdissect(v, left, begin, mid);
950 [ + - ]: 128 : if (er == REG_OKAY)
951 : : {
952 : 128 : er = cdissect(v, right, mid, end);
953 [ + + ]: 128 : if (er == REG_OKAY)
954 : : {
955 : : /* satisfaction */
956 : : MDEBUG(("%d: successful\n", t->id));
957 : 116 : return REG_OKAY;
958 : : }
959 : : /* Reset left's matches (right should have done so itself) */
960 : 12 : zaptreesubs(v, left);
961 : : }
962 [ - + ]: 12 : if (er != REG_NOMATCH)
963 : 0 : return er;
964 : : }
965 [ - + ]: 737 : NOERR();
966 : :
967 : : /* that midpoint didn't work, find a new one */
968 [ + + ]: 737 : if (mid == end)
969 : : {
970 : : /* all possibilities exhausted */
971 : : MDEBUG(("%d: no midpoint\n", t->id));
972 : 121 : return REG_NOMATCH;
973 : : }
974 : 616 : mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
975 [ - + ]: 616 : NOERR();
976 [ - + ]: 616 : if (mid == NULL)
977 : : {
978 : : /* failed to find a new one */
979 : : MDEBUG(("%d: failed midpoint\n", t->id));
980 : 0 : return REG_NOMATCH;
981 : : }
982 : : MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));
983 : : }
984 : :
985 : : /* can't get here */
986 : : return REG_ASSERT;
987 : : }
988 : :
989 : : /*
990 : : * cbrdissect - dissect match for backref node
991 : : *
992 : : * The backref match might already have been verified by dfa_backref(),
993 : : * but we don't know that for sure so must check it here.
994 : : */
995 : : static int /* regexec return code */
996 : 303 : cbrdissect(struct vars *v,
997 : : struct subre *t,
998 : : chr *begin, /* beginning of relevant substring */
999 : : chr *end) /* end of same */
1000 : : {
1001 : 303 : int n = t->backno;
1002 : : size_t numreps;
1003 : : size_t tlen;
1004 : : size_t brlen;
1005 : : chr *brstring;
1006 : : chr *p;
1007 : 303 : int min = t->min;
1008 : 303 : int max = t->max;
1009 : :
1010 : : assert(t != NULL);
1011 : : assert(t->op == 'b');
1012 : : assert(n >= 0);
1013 : : assert((size_t) n < v->nmatch);
1014 : :
1015 : : MDEBUG(("%d: cbrdissect %d{%d-%d} %ld-%ld\n", t->id, n, min, max,
1016 : : LOFF(begin), LOFF(end)));
1017 : :
1018 : : /* get the backreferenced string */
1019 [ + + ]: 303 : if (v->pmatch[n].rm_so == -1)
1020 : 83 : return REG_NOMATCH;
1021 : 220 : brstring = v->start + v->pmatch[n].rm_so;
1022 : 220 : brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
1023 : :
1024 : : /* special cases for zero-length strings */
1025 [ + + ]: 220 : if (brlen == 0)
1026 : : {
1027 : : /*
1028 : : * matches only if target is zero length, but any number of
1029 : : * repetitions can be considered to be present
1030 : : */
1031 [ + - + - ]: 11 : if (begin == end && min <= max)
1032 : : {
1033 : : MDEBUG(("%d: backref matched trivially\n", t->id));
1034 : 11 : return REG_OKAY;
1035 : : }
1036 : 0 : return REG_NOMATCH;
1037 : : }
1038 [ + + ]: 209 : if (begin == end)
1039 : : {
1040 : : /* matches only if zero repetitions are okay */
1041 [ + + ]: 8 : if (min == 0)
1042 : : {
1043 : : MDEBUG(("%d: backref matched trivially\n", t->id));
1044 : 7 : return REG_OKAY;
1045 : : }
1046 : 1 : return REG_NOMATCH;
1047 : : }
1048 : :
1049 : : /*
1050 : : * check target length to see if it could possibly be an allowed number of
1051 : : * repetitions of brstring
1052 : : */
1053 : : assert(end > begin);
1054 : 201 : tlen = end - begin;
1055 [ + + ]: 201 : if (tlen % brlen != 0)
1056 : 5 : return REG_NOMATCH;
1057 : 196 : numreps = tlen / brlen;
1058 [ + - + + : 196 : if (numreps < min || (numreps > max && max != DUPINF))
+ - ]
1059 : 3 : return REG_NOMATCH;
1060 : :
1061 : : /* okay, compare the actual string contents */
1062 : 193 : p = begin;
1063 [ + + ]: 338 : while (numreps-- > 0)
1064 : : {
1065 [ + + ]: 219 : if ((*v->g->compare) (brstring, p, brlen) != 0)
1066 : 74 : return REG_NOMATCH;
1067 : 145 : p += brlen;
1068 : : }
1069 : :
1070 : : MDEBUG(("%d: backref matched\n", t->id));
1071 : 119 : return REG_OKAY;
1072 : : }
1073 : :
1074 : : /*
1075 : : * caltdissect - dissect match for alternation node
1076 : : */
1077 : : static int /* regexec return code */
1078 : 113 : caltdissect(struct vars *v,
1079 : : struct subre *t,
1080 : : chr *begin, /* beginning of relevant substring */
1081 : : chr *end) /* end of same */
1082 : : {
1083 : : struct dfa *d;
1084 : : int er;
1085 : :
1086 : : assert(t->op == '|');
1087 : :
1088 : 113 : t = t->child;
1089 : : /* there should be at least 2 alternatives */
1090 : : assert(t != NULL && t->sibling != NULL);
1091 : :
1092 [ + + ]: 200 : while (t != NULL)
1093 : : {
1094 : : assert(t->cnfa.nstates > 0);
1095 : :
1096 : : MDEBUG(("%d: caltdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));
1097 : :
1098 : 160 : d = getsubdfa(v, t);
1099 [ - + ]: 160 : NOERR();
1100 [ + + ]: 160 : if (longest(v, d, begin, end, (int *) NULL) == end)
1101 : : {
1102 : : MDEBUG(("%d: caltdissect matched\n", t->id));
1103 : 125 : er = cdissect(v, t, begin, end);
1104 [ + + ]: 125 : if (er != REG_NOMATCH)
1105 : 73 : return er;
1106 : : }
1107 [ - + ]: 87 : NOERR();
1108 : :
1109 : 87 : t = t->sibling;
1110 : : }
1111 : :
1112 : 40 : return REG_NOMATCH;
1113 : : }
1114 : :
1115 : : /*
1116 : : * citerdissect - dissect match for iteration node
1117 : : */
1118 : : static int /* regexec return code */
1119 : 159 : citerdissect(struct vars *v,
1120 : : struct subre *t,
1121 : : chr *begin, /* beginning of relevant substring */
1122 : : chr *end) /* end of same */
1123 : : {
1124 : : struct dfa *d;
1125 : : chr **endpts;
1126 : : chr *limit;
1127 : : int min_matches;
1128 : : size_t max_matches;
1129 : : int nverified;
1130 : : int k;
1131 : : int i;
1132 : : int er;
1133 : :
1134 : : assert(t->op == '*');
1135 : : assert(t->child != NULL && t->child->cnfa.nstates > 0);
1136 : : assert(!(t->child->flags & SHORTER));
1137 : : assert(begin <= end);
1138 : :
1139 : : MDEBUG(("%d: citerdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));
1140 : :
1141 : : /*
1142 : : * For the moment, assume the minimum number of matches is 1. If zero
1143 : : * matches are allowed, and the target string is empty, we are allowed to
1144 : : * match regardless of the contents of the iter node --- but we would
1145 : : * prefer to match once, so that capturing parens get set. (An example of
1146 : : * the concern here is a pattern like "()*\1", which historically this
1147 : : * code has allowed to succeed.) Therefore, we deal with the zero-matches
1148 : : * case at the bottom, after failing to find any other way to match.
1149 : : */
1150 : 159 : min_matches = t->min;
1151 [ + + ]: 159 : if (min_matches <= 0)
1152 : 105 : min_matches = 1;
1153 : :
1154 : : /*
1155 : : * We need workspace to track the endpoints of each sub-match. Normally
1156 : : * we consider only nonzero-length sub-matches, so there can be at most
1157 : : * end-begin of them. However, if min is larger than that, we will also
1158 : : * consider zero-length sub-matches in order to find enough matches.
1159 : : *
1160 : : * For convenience, endpts[0] contains the "begin" pointer and we store
1161 : : * sub-match endpoints in endpts[1..max_matches].
1162 : : */
1163 : 159 : max_matches = end - begin;
1164 [ - + - - ]: 159 : if (max_matches > t->max && t->max != DUPINF)
1165 : 0 : max_matches = t->max;
1166 [ + + ]: 159 : if (max_matches < min_matches)
1167 : 97 : max_matches = min_matches;
1168 : 159 : endpts = MALLOC_ARRAY(chr *, max_matches + 1);
1169 [ - + ]: 159 : if (endpts == NULL)
1170 : 0 : return REG_ESPACE;
1171 : 159 : endpts[0] = begin;
1172 : :
1173 : 159 : d = getsubdfa(v, t->child);
1174 [ - + ]: 159 : if (ISERR())
1175 : : {
1176 : 0 : FREE(endpts);
1177 : 0 : return v->err;
1178 : : }
1179 : :
1180 : : /*
1181 : : * Our strategy is to first find a set of sub-match endpoints that are
1182 : : * valid according to the child node's DFA, and then recursively dissect
1183 : : * each sub-match to confirm validity. If any validity check fails,
1184 : : * backtrack that sub-match and try again. And, when we next try for a
1185 : : * validity check, we need not recheck any successfully verified
1186 : : * sub-matches that we didn't move the endpoints of. nverified remembers
1187 : : * how many sub-matches are currently known okay.
1188 : : */
1189 : :
1190 : : /* initialize to consider first sub-match */
1191 : 159 : nverified = 0;
1192 : 159 : k = 1;
1193 : 159 : limit = end;
1194 : :
1195 : : /* iterate until satisfaction or failure */
1196 [ + + ]: 725 : while (k > 0)
1197 : : {
1198 : : /* try to find an endpoint for the k'th sub-match */
1199 : 593 : endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL);
1200 [ - + ]: 593 : if (ISERR())
1201 : : {
1202 : 0 : FREE(endpts);
1203 : 0 : return v->err;
1204 : : }
1205 [ + + ]: 593 : if (endpts[k] == NULL)
1206 : : {
1207 : : /* no match possible, so see if we can shorten previous one */
1208 : 306 : k--;
1209 : 306 : goto backtrack;
1210 : : }
1211 : : MDEBUG(("%d: working endpoint %d: %ld\n",
1212 : : t->id, k, LOFF(endpts[k])));
1213 : :
1214 : : /* k'th sub-match can no longer be considered verified */
1215 [ + + ]: 287 : if (nverified >= k)
1216 : 12 : nverified = k - 1;
1217 : :
1218 [ + + ]: 287 : if (endpts[k] != end)
1219 : : {
1220 : : /* haven't reached end yet, try another iteration if allowed */
1221 [ - + ]: 200 : if (k >= max_matches)
1222 : : {
1223 : : /* must try to shorten some previous match */
1224 : 0 : k--;
1225 : 0 : goto backtrack;
1226 : : }
1227 : :
1228 : : /* reject zero-length match unless necessary to achieve min */
1229 [ - + - - ]: 200 : if (endpts[k] == endpts[k - 1] &&
1230 [ # # ]: 0 : (k >= min_matches || min_matches - k < end - endpts[k]))
1231 : 0 : goto backtrack;
1232 : :
1233 : 200 : k++;
1234 : 200 : limit = end;
1235 : 200 : continue;
1236 : : }
1237 : :
1238 : : /*
1239 : : * We've identified a way to divide the string into k sub-matches that
1240 : : * works so far as the child DFA can tell. If k is an allowed number
1241 : : * of matches, start the slow part: recurse to verify each sub-match.
1242 : : * We always have k <= max_matches, needn't check that.
1243 : : */
1244 [ - + ]: 87 : if (k < min_matches)
1245 : 0 : goto backtrack;
1246 : :
1247 : : MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
1248 : :
1249 [ + + ]: 140 : for (i = nverified + 1; i <= k; i++)
1250 : : {
1251 : : /* zap any match data from a non-last iteration */
1252 : 113 : zaptreesubs(v, t->child);
1253 : 113 : er = cdissect(v, t->child, endpts[i - 1], endpts[i]);
1254 [ + + ]: 113 : if (er == REG_OKAY)
1255 : : {
1256 : 53 : nverified = i;
1257 : 53 : continue;
1258 : : }
1259 [ + - ]: 60 : if (er == REG_NOMATCH)
1260 : 60 : break;
1261 : : /* oops, something failed */
1262 : 0 : FREE(endpts);
1263 : 0 : return er;
1264 : : }
1265 : :
1266 [ + + ]: 87 : if (i > k)
1267 : : {
1268 : : /* satisfaction */
1269 : : MDEBUG(("%d: successful\n", t->id));
1270 : 27 : FREE(endpts);
1271 : 27 : return REG_OKAY;
1272 : : }
1273 : :
1274 : : /* i'th match failed to verify, so backtrack it */
1275 : 60 : k = i;
1276 : :
1277 : 366 : backtrack:
1278 : :
1279 : : /*
1280 : : * Must consider shorter versions of the k'th sub-match. However,
1281 : : * we'll only ask for a zero-length match if necessary.
1282 : : */
1283 [ + + ]: 366 : while (k > 0)
1284 : : {
1285 : 234 : chr *prev_end = endpts[k - 1];
1286 : :
1287 [ + - ]: 234 : if (endpts[k] > prev_end)
1288 : : {
1289 : 234 : limit = endpts[k] - 1;
1290 [ - + - - ]: 234 : if (limit > prev_end ||
1291 [ # # ]: 0 : (k < min_matches && min_matches - k >= end - prev_end))
1292 : : {
1293 : : /* break out of backtrack loop, continue the outer one */
1294 : : break;
1295 : : }
1296 : : }
1297 : : /* can't shorten k'th sub-match any more, consider previous one */
1298 : 0 : k--;
1299 : : }
1300 : : }
1301 : :
1302 : : /* all possibilities exhausted */
1303 : 132 : FREE(endpts);
1304 : :
1305 : : /*
1306 : : * Now consider the possibility that we can match to a zero-length string
1307 : : * by using zero repetitions.
1308 : : */
1309 [ + + + - ]: 132 : if (t->min == 0 && begin == end)
1310 : : {
1311 : : MDEBUG(("%d: allowing zero matches\n", t->id));
1312 : 90 : return REG_OKAY;
1313 : : }
1314 : :
1315 : : MDEBUG(("%d: failed\n", t->id));
1316 : 42 : return REG_NOMATCH;
1317 : : }
1318 : :
1319 : : /*
1320 : : * creviterdissect - dissect match for iteration node, shortest-first
1321 : : */
1322 : : static int /* regexec return code */
1323 : 8 : creviterdissect(struct vars *v,
1324 : : struct subre *t,
1325 : : chr *begin, /* beginning of relevant substring */
1326 : : chr *end) /* end of same */
1327 : : {
1328 : : struct dfa *d;
1329 : : chr **endpts;
1330 : : chr *limit;
1331 : : int min_matches;
1332 : : size_t max_matches;
1333 : : int nverified;
1334 : : int k;
1335 : : int i;
1336 : : int er;
1337 : :
1338 : : assert(t->op == '*');
1339 : : assert(t->child != NULL && t->child->cnfa.nstates > 0);
1340 : : assert(t->child->flags & SHORTER);
1341 : : assert(begin <= end);
1342 : :
1343 : : MDEBUG(("%d: creviterdissect %ld-%ld\n", t->id, LOFF(begin), LOFF(end)));
1344 : :
1345 : : /*
1346 : : * If zero matches are allowed, and target string is empty, just declare
1347 : : * victory. OTOH, if target string isn't empty, zero matches can't work
1348 : : * so we pretend the min is 1.
1349 : : */
1350 : 8 : min_matches = t->min;
1351 [ + - ]: 8 : if (min_matches <= 0)
1352 : : {
1353 [ + + ]: 8 : if (begin == end)
1354 : : {
1355 : : MDEBUG(("%d: allowing zero matches\n", t->id));
1356 : 1 : return REG_OKAY;
1357 : : }
1358 : 7 : min_matches = 1;
1359 : : }
1360 : :
1361 : : /*
1362 : : * We need workspace to track the endpoints of each sub-match. Normally
1363 : : * we consider only nonzero-length sub-matches, so there can be at most
1364 : : * end-begin of them. However, if min is larger than that, we will also
1365 : : * consider zero-length sub-matches in order to find enough matches.
1366 : : *
1367 : : * For convenience, endpts[0] contains the "begin" pointer and we store
1368 : : * sub-match endpoints in endpts[1..max_matches].
1369 : : */
1370 : 7 : max_matches = end - begin;
1371 [ + - + - ]: 7 : if (max_matches > t->max && t->max != DUPINF)
1372 : 7 : max_matches = t->max;
1373 [ - + ]: 7 : if (max_matches < min_matches)
1374 : 0 : max_matches = min_matches;
1375 : 7 : endpts = MALLOC_ARRAY(chr *, max_matches + 1);
1376 [ - + ]: 7 : if (endpts == NULL)
1377 : 0 : return REG_ESPACE;
1378 : 7 : endpts[0] = begin;
1379 : :
1380 : 7 : d = getsubdfa(v, t->child);
1381 [ - + ]: 7 : if (ISERR())
1382 : : {
1383 : 0 : FREE(endpts);
1384 : 0 : return v->err;
1385 : : }
1386 : :
1387 : : /*
1388 : : * Our strategy is to first find a set of sub-match endpoints that are
1389 : : * valid according to the child node's DFA, and then recursively dissect
1390 : : * each sub-match to confirm validity. If any validity check fails,
1391 : : * backtrack that sub-match and try again. And, when we next try for a
1392 : : * validity check, we need not recheck any successfully verified
1393 : : * sub-matches that we didn't move the endpoints of. nverified remembers
1394 : : * how many sub-matches are currently known okay.
1395 : : */
1396 : :
1397 : : /* initialize to consider first sub-match */
1398 : 7 : nverified = 0;
1399 : 7 : k = 1;
1400 : 7 : limit = begin;
1401 : :
1402 : : /* iterate until satisfaction or failure */
1403 [ + + ]: 9 : while (k > 0)
1404 : : {
1405 : : /* disallow zero-length match unless necessary to achieve min */
1406 [ + - + - ]: 7 : if (limit == endpts[k - 1] &&
1407 [ - + ]: 7 : limit != end &&
1408 [ # # ]: 0 : (k >= min_matches || min_matches - k < end - limit))
1409 : 7 : limit++;
1410 : :
1411 : : /* if this is the last allowed sub-match, it must reach to the end */
1412 [ + - ]: 7 : if (k >= max_matches)
1413 : 7 : limit = end;
1414 : :
1415 : : /* try to find an endpoint for the k'th sub-match */
1416 : 7 : endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
1417 : : (chr **) NULL, (int *) NULL);
1418 [ - + ]: 7 : if (ISERR())
1419 : : {
1420 : 0 : FREE(endpts);
1421 : 0 : return v->err;
1422 : : }
1423 [ - + ]: 7 : if (endpts[k] == NULL)
1424 : : {
1425 : : /* no match possible, so see if we can lengthen previous one */
1426 : 0 : k--;
1427 : 0 : goto backtrack;
1428 : : }
1429 : : MDEBUG(("%d: working endpoint %d: %ld\n",
1430 : : t->id, k, LOFF(endpts[k])));
1431 : :
1432 : : /* k'th sub-match can no longer be considered verified */
1433 [ - + ]: 7 : if (nverified >= k)
1434 : 0 : nverified = k - 1;
1435 : :
1436 [ - + ]: 7 : if (endpts[k] != end)
1437 : : {
1438 : : /* haven't reached end yet, try another iteration if allowed */
1439 [ # # ]: 0 : if (k >= max_matches)
1440 : : {
1441 : : /* must try to lengthen some previous match */
1442 : 0 : k--;
1443 : 0 : goto backtrack;
1444 : : }
1445 : :
1446 : 0 : k++;
1447 : 0 : limit = endpts[k - 1];
1448 : 0 : continue;
1449 : : }
1450 : :
1451 : : /*
1452 : : * We've identified a way to divide the string into k sub-matches that
1453 : : * works so far as the child DFA can tell. If k is an allowed number
1454 : : * of matches, start the slow part: recurse to verify each sub-match.
1455 : : * We always have k <= max_matches, needn't check that.
1456 : : */
1457 [ - + ]: 7 : if (k < min_matches)
1458 : 0 : goto backtrack;
1459 : :
1460 : : MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
1461 : :
1462 [ + + ]: 12 : for (i = nverified + 1; i <= k; i++)
1463 : : {
1464 : : /* zap any match data from a non-last iteration */
1465 : 7 : zaptreesubs(v, t->child);
1466 : 7 : er = cdissect(v, t->child, endpts[i - 1], endpts[i]);
1467 [ + + ]: 7 : if (er == REG_OKAY)
1468 : : {
1469 : 5 : nverified = i;
1470 : 5 : continue;
1471 : : }
1472 [ + - ]: 2 : if (er == REG_NOMATCH)
1473 : 2 : break;
1474 : : /* oops, something failed */
1475 : 0 : FREE(endpts);
1476 : 0 : return er;
1477 : : }
1478 : :
1479 [ + + ]: 7 : if (i > k)
1480 : : {
1481 : : /* satisfaction */
1482 : : MDEBUG(("%d: successful\n", t->id));
1483 : 5 : FREE(endpts);
1484 : 5 : return REG_OKAY;
1485 : : }
1486 : :
1487 : : /* i'th match failed to verify, so backtrack it */
1488 : 2 : k = i;
1489 : :
1490 : 2 : backtrack:
1491 : :
1492 : : /*
1493 : : * Must consider longer versions of the k'th sub-match.
1494 : : */
1495 [ + + ]: 4 : while (k > 0)
1496 : : {
1497 [ - + ]: 2 : if (endpts[k] < end)
1498 : : {
1499 : 0 : limit = endpts[k] + 1;
1500 : : /* break out of backtrack loop, continue the outer one */
1501 : 0 : break;
1502 : : }
1503 : : /* can't lengthen k'th sub-match any more, consider previous one */
1504 : 2 : k--;
1505 : : }
1506 : : }
1507 : :
1508 : : /* all possibilities exhausted */
1509 : : MDEBUG(("%d: failed\n", t->id));
1510 : 2 : FREE(endpts);
1511 : 2 : return REG_NOMATCH;
1512 : : }
1513 : :
1514 : :
1515 : :
1516 : : #include "rege_dfa.c"
|
