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