Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/tcl8.5.2/generic/regexec.c @ 35

Last change on this file since 35 was 25, checked in by landauf, 17 years ago

added tcl to libs
File size: 29.1 KB
Line 
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 of
17 * 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
31#include "regguts.h"
32
33/*
34 * Lazy-DFA representation.
35 */
36
37struct arcp {                   /* "pointer" to an outarc */
38    struct sset *ss;
39    color co;
40};
41
42struct sset {                   /* state set */
43    unsigned *states;           /* pointer to bitvector */
44    unsigned hash;              /* hash of bitvector */
45#define HASH(bv, nw)    (((nw) == 1) ? *(bv) : hash(bv, nw))
46#define HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
47        memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
48    int flags;
49#define STARTER         01      /* the initial state set */
50#define POSTSTATE       02      /* includes the goal state */
51#define LOCKED          04      /* locked in cache */
52#define NOPROGRESS      010     /* zero-progress state set */
53    struct arcp ins;            /* chain of inarcs pointing here */
54    chr *lastseen;              /* last entered on arrival here */
55    struct sset **outs;         /* outarc vector indexed by color */
56    struct arcp *inchain;       /* chain-pointer vector for outarcs */
57};
58
59struct dfa {
60    int nssets;                 /* size of cache */
61    int nssused;                /* how many entries occupied yet */
62    int nstates;                /* number of states */
63    int ncolors;                /* length of outarc and inchain vectors */
64    int wordsper;               /* length of state-set bitvectors */
65    struct sset *ssets;         /* state-set cache */
66    unsigned *statesarea;       /* bitvector storage */
67    unsigned *work;             /* pointer to work area within statesarea */
68    struct sset **outsarea;     /* outarc-vector storage */
69    struct arcp *incarea;       /* inchain storage */
70    struct cnfa *cnfa;
71    struct colormap *cm;
72    chr *lastpost;              /* location of last cache-flushed success */
73    chr *lastnopr;              /* location of last cache-flushed NOPROGRESS */
74    struct sset *search;        /* replacement-search-pointer memory */
75    int cptsmalloced;           /* were the areas individually malloced? */
76    char *mallocarea;           /* self, or master malloced area, or NULL */
77};
78
79#define WORK    1               /* number of work bitvectors needed */
80
81/*
82 * Setup for non-malloc allocation for small cases.
83 */
84
85#define FEWSTATES       20      /* must be less than UBITS */
86#define FEWCOLORS       15
87struct smalldfa {
88    struct dfa dfa;
89    struct sset ssets[FEWSTATES*2];
90    unsigned statesarea[FEWSTATES*2 + WORK];
91    struct sset *outsarea[FEWSTATES*2 * FEWCOLORS];
92    struct arcp incarea[FEWSTATES*2 * FEWCOLORS];
93};
94#define DOMALLOC        ((struct smalldfa *)NULL)       /* force malloc */
95
96/*
97 * Internal variables, bundled for easy passing around.
98 */
99
100struct vars {
101    regex_t *re;
102    struct guts *g;
103    int eflags;                 /* copies of arguments */
104    size_t nmatch;
105    regmatch_t *pmatch;
106    rm_detail_t *details;
107    chr *start;                 /* start of string */
108    chr *stop;                  /* just past end of string */
109    int err;                    /* error code if any (0 none) */
110    regoff_t *mem;              /* memory vector for backtracking */
111    struct smalldfa dfa1;
112    struct smalldfa dfa2;
113};
114#define VISERR(vv) ((vv)->err != 0)     /* have we seen an error yet? */
115#define ISERR() VISERR(v)
116#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
117#define ERR(e)  VERR(v, e)      /* record an error */
118#define NOERR() {if (ISERR()) return v->err;}   /* if error seen, return it */
119#define OFF(p)  ((p) - v->start)
120#define LOFF(p) ((long)OFF(p))
121
122/*
123 * forward declarations
124 */
125/* =====^!^===== begin forwards =====^!^===== */
126/* automatically gathered by fwd; do not hand-edit */
127/* === regexec.c === */
128int exec(regex_t *, CONST chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
129static int find(struct vars *, struct cnfa *, struct colormap *);
130static int cfind(struct vars *, struct cnfa *, struct colormap *);
131static int cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
132static VOID zapsubs(regmatch_t *, size_t);
133static VOID zapmem(struct vars *, struct subre *);
134static VOID subset(struct vars *, struct subre *, chr *, chr *);
135static int dissect(struct vars *, struct subre *, chr *, chr *);
136static int condissect(struct vars *, struct subre *, chr *, chr *);
137static int altdissect(struct vars *, struct subre *, chr *, chr *);
138static int cdissect(struct vars *, struct subre *, chr *, chr *);
139static int ccondissect(struct vars *, struct subre *, chr *, chr *);
140static int crevdissect(struct vars *, struct subre *, chr *, chr *);
141static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
142static int caltdissect(struct vars *, struct subre *, chr *, chr *);
143/* === rege_dfa.c === */
144static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
145static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
146static chr *lastcold(struct vars *, struct dfa *);
147static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
148static VOID freedfa(struct dfa *);
149static unsigned hash(unsigned *, int);
150static struct sset *initialize(struct vars *, struct dfa *, chr *);
151static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *);
152static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
153static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
154static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
155/* automatically gathered by fwd; do not hand-edit */
156/* =====^!^===== end forwards =====^!^===== */
157
158/*
159 - exec - match regular expression
160 ^ int exec(regex_t *, CONST chr *, size_t, rm_detail_t *,
161 ^                                      size_t, regmatch_t [], int);
162 */
163int
164exec(
165    regex_t *re,
166    CONST chr *string,
167    size_t len,
168    rm_detail_t *details,
169    size_t nmatch,
170    regmatch_t pmatch[],
171    int flags)
172{
173    AllocVars(v);
174    int st;
175    size_t n;
176    int backref;
177#define LOCALMAT        20
178    regmatch_t mat[LOCALMAT];
179#define LOCALMEM        40
180    regoff_t mem[LOCALMEM];
181
182    /*
183     * Sanity checks.
184     */
185
186    if (re == NULL || string == NULL || re->re_magic != REMAGIC) {
187        FreeVars(v);
188        return REG_INVARG;
189    }
190    if (re->re_csize != sizeof(chr)) {
191        FreeVars(v);
192        return REG_MIXED;
193    }
194
195    /*
196     * Setup.
197     */
198
199    v->re = re;
200    v->g = (struct guts *)re->re_guts;
201    if ((v->g->cflags&REG_EXPECT) && details == NULL) {
202        FreeVars(v);
203        return REG_INVARG;
204    }
205    if (v->g->info&REG_UIMPOSSIBLE) {
206        FreeVars(v);
207        return REG_NOMATCH;
208    }
209    backref = (v->g->info&REG_UBACKREF) ? 1 : 0;
210    v->eflags = flags;
211    if (v->g->cflags&REG_NOSUB) {
212        nmatch = 0;             /* override client */
213    }
214    v->nmatch = nmatch;
215    if (backref) {
216        /*
217         * Need work area.
218         */
219
220        if (v->g->nsub + 1 <= LOCALMAT) {
221            v->pmatch = mat;
222        } else {
223            v->pmatch = (regmatch_t *)
224                    MALLOC((v->g->nsub + 1) * sizeof(regmatch_t));
225        }
226        if (v->pmatch == NULL) {
227            FreeVars(v);
228            return REG_ESPACE;
229        }
230        v->nmatch = v->g->nsub + 1;
231    } else {
232        v->pmatch = pmatch;
233    }
234    v->details = details;
235    v->start = (chr *)string;
236    v->stop = (chr *)string + len;
237    v->err = 0;
238    if (backref) {
239        /*
240         * Need retry memory.
241         */
242
243        assert(v->g->ntree >= 0);
244        n = (size_t)v->g->ntree;
245        if (n <= LOCALMEM) {
246            v->mem = mem;
247        } else {
248            v->mem = (regoff_t *) MALLOC(n*sizeof(regoff_t));
249        }
250        if (v->mem == NULL) {
251            if (v->pmatch != pmatch && v->pmatch != mat) {
252                FREE(v->pmatch);
253            }
254            FreeVars(v);
255            return REG_ESPACE;
256        }
257    } else {
258        v->mem = NULL;
259    }
260
261    /*
262     * Do it.
263     */
264
265    assert(v->g->tree != NULL);
266    if (backref) {
267        st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
268    } else {
269        st = find(v, &v->g->tree->cnfa, &v->g->cmap);
270    }
271
272    /*
273     * Copy (portion of) match vector over if necessary.
274     */
275
276    if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
277        zapsubs(pmatch, nmatch);
278        n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
279        memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
280    }
281
282    /*
283     * Clean up.
284     */
285
286    if (v->pmatch != pmatch && v->pmatch != mat) {
287        FREE(v->pmatch);
288    }
289    if (v->mem != NULL && v->mem != mem) {
290        FREE(v->mem);
291    }
292    FreeVars(v);
293    return st;
294}
295
296/*
297 - find - find a match for the main NFA (no-complications case)
298 ^ static int find(struct vars *, struct cnfa *, struct colormap *);
299 */
300static int
301find(
302    struct vars *v,
303    struct cnfa *cnfa,
304    struct colormap *cm)
305{
306    struct dfa *s;
307    struct dfa *d;
308    chr *begin;
309    chr *end = NULL;
310    chr *cold;
311    chr *open;                  /* Open and close of range of possible
312                                 * starts */
313    chr *close;
314    int hitend;
315    int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0;
316
317    /*
318     * First, a shot with the search RE.
319     */
320
321    s = newdfa(v, &v->g->search, cm, &v->dfa1);
322    assert(!(ISERR() && s != NULL));
323    NOERR();
324    MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
325    cold = NULL;
326    close = shortest(v, s, v->start, v->start, v->stop, &cold, NULL);
327    freedfa(s);
328    NOERR();
329    if (v->g->cflags&REG_EXPECT) {
330        assert(v->details != NULL);
331        if (cold != NULL) {
332            v->details->rm_extend.rm_so = OFF(cold);
333        } else {
334            v->details->rm_extend.rm_so = OFF(v->stop);
335        }
336        v->details->rm_extend.rm_eo = OFF(v->stop);     /* unknown */
337    }
338    if (close == NULL) {        /* not found */
339        return REG_NOMATCH;
340    }
341    if (v->nmatch == 0) {       /* found, don't need exact location */
342        return REG_OKAY;
343    }
344
345    /*
346     * Find starting point and match.
347     */
348
349    assert(cold != NULL);
350    open = cold;
351    cold = NULL;
352    MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
353    d = newdfa(v, cnfa, cm, &v->dfa1);
354    assert(!(ISERR() && d != NULL));
355    NOERR();
356    for (begin = open; begin <= close; begin++) {
357        MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
358        if (shorter) {
359            end = shortest(v, d, begin, begin, v->stop, NULL, &hitend);
360        } else {
361            end = longest(v, d, begin, v->stop, &hitend);
362        }
363        NOERR();
364        if (hitend && cold == NULL) {
365            cold = begin;
366        }
367        if (end != NULL) {
368            break;              /* NOTE BREAK OUT */
369        }
370    }
371    assert(end != NULL);        /* search RE succeeded so loop should */
372    freedfa(d);
373
374    /*
375     * And pin down details.
376     */
377
378    assert(v->nmatch > 0);
379    v->pmatch[0].rm_so = OFF(begin);
380    v->pmatch[0].rm_eo = OFF(end);
381    if (v->g->cflags&REG_EXPECT) {
382        if (cold != NULL) {
383            v->details->rm_extend.rm_so = OFF(cold);
384        } else {
385            v->details->rm_extend.rm_so = OFF(v->stop);
386        }
387        v->details->rm_extend.rm_eo = OFF(v->stop);     /* unknown */
388    }
389    if (v->nmatch == 1) {       /* no need for submatches */
390        return REG_OKAY;
391    }
392
393    /*
394     * Submatches.
395     */
396
397    zapsubs(v->pmatch, v->nmatch);
398    return dissect(v, v->g->tree, begin, end);
399}
400
401/*
402 - cfind - find a match for the main NFA (with complications)
403 ^ static int cfind(struct vars *, struct cnfa *, struct colormap *);
404 */
405static int
406cfind(
407    struct vars *v,
408    struct cnfa *cnfa,
409    struct colormap *cm)
410{
411    struct dfa *s;
412    struct dfa *d;
413    chr *cold = NULL; /* silence gcc 4 warning */
414    int ret;
415
416    s = newdfa(v, &v->g->search, cm, &v->dfa1);
417    NOERR();
418    d = newdfa(v, cnfa, cm, &v->dfa2);
419    if (ISERR()) {
420        assert(d == NULL);
421        freedfa(s);
422        return v->err;
423    }
424
425    ret = cfindloop(v, cnfa, cm, d, s, &cold);
426
427    freedfa(d);
428    freedfa(s);
429    NOERR();
430    if (v->g->cflags&REG_EXPECT) {
431        assert(v->details != NULL);
432        if (cold != NULL) {
433            v->details->rm_extend.rm_so = OFF(cold);
434        } else {
435            v->details->rm_extend.rm_so = OFF(v->stop);
436        }
437        v->details->rm_extend.rm_eo = OFF(v->stop);     /* unknown */
438    }
439    return ret;
440}
441
442/*
443 - cfindloop - the heart of cfind
444 ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *,
445 ^      struct dfa *, struct dfa *, chr **);
446 */
447static int
448cfindloop(
449    struct vars *v,
450    struct cnfa *cnfa,
451    struct colormap *cm,
452    struct dfa *d,
453    struct dfa *s,
454    chr **coldp)                /* where to put coldstart pointer */
455{
456    chr *begin;
457    chr *end;
458    chr *cold;
459    chr *open;                  /* Open and close of range of possible
460                                 * starts */
461    chr *close;
462    chr *estart;
463    chr *estop;
464    int er;
465    int shorter = v->g->tree->flags&SHORTER;
466    int hitend;
467
468    assert(d != NULL && s != NULL);
469    cold = NULL;
470    close = v->start;
471    do {
472        MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
473        close = shortest(v, s, close, close, v->stop, &cold, NULL);
474        if (close == NULL) {
475            break;              /* NOTE BREAK */
476        }
477        assert(cold != NULL);
478        open = cold;
479        cold = NULL;
480        MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
481        for (begin = open; begin <= close; begin++) {
482            MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
483            estart = begin;
484            estop = v->stop;
485            for (;;) {
486                if (shorter) {
487                    end = shortest(v, d, begin, estart, estop, NULL, &hitend);
488                } else {
489                    end = longest(v, d, begin, estop, &hitend);
490                }
491                if (hitend && cold == NULL) {
492                    cold = begin;
493                }
494                if (end == NULL) {
495                    break;      /* NOTE BREAK OUT */
496                }
497
498                MDEBUG(("tentative end %ld\n", LOFF(end)));
499                zapsubs(v->pmatch, v->nmatch);
500                zapmem(v, v->g->tree);
501                er = cdissect(v, v->g->tree, begin, end);
502                if (er == REG_OKAY) {
503                    if (v->nmatch > 0) {
504                        v->pmatch[0].rm_so = OFF(begin);
505                        v->pmatch[0].rm_eo = OFF(end);
506                    }
507                    *coldp = cold;
508                    return REG_OKAY;
509                }
510                if (er != REG_NOMATCH) {
511                    ERR(er);
512                    return er;
513                }
514                if ((shorter) ? end == estop : end == begin) {
515                    /*
516                     * No point in trying again.
517                     */
518
519                    *coldp = cold;
520                    return REG_NOMATCH;
521                }
522
523                /*
524                 * Go around and try again
525                 */
526
527                if (shorter) {
528                    estart = end + 1;
529                } else {
530                    estop = end - 1;
531                }
532            }
533        }
534    } while (close < v->stop);
535
536    *coldp = cold;
537    return REG_NOMATCH;
538}
539
540/*
541 - zapsubs - initialize the subexpression matches to "no match"
542 ^ static VOID zapsubs(regmatch_t *, size_t);
543 */
544static void
545zapsubs(
546    regmatch_t *p,
547    size_t n)
548{
549    size_t i;
550
551    for (i = n-1; i > 0; i--) {
552        p[i].rm_so = -1;
553        p[i].rm_eo = -1;
554    }
555}
556
557/*
558 - zapmem - initialize the retry memory of a subtree to zeros
559 ^ static VOID zapmem(struct vars *, struct subre *);
560 */
561static void
562zapmem(
563    struct vars *v,
564    struct subre *t)
565{
566    if (t == NULL) {
567        return;
568    }
569
570    assert(v->mem != NULL);
571    v->mem[t->retry] = 0;
572    if (t->op == '(') {
573        assert(t->subno > 0);
574        v->pmatch[t->subno].rm_so = -1;
575                v->pmatch[t->subno].rm_eo = -1;
576    }
577
578    if (t->left != NULL) {
579        zapmem(v, t->left);
580    }
581    if (t->right != NULL) {
582        zapmem(v, t->right);
583    }
584}
585
586/*
587 - subset - set any subexpression relevant to a successful subre
588 ^ static VOID subset(struct vars *, struct subre *, chr *, chr *);
589 */
590static void
591subset(
592    struct vars *v,
593    struct subre *sub,
594    chr *begin,
595    chr *end)
596{
597    int n = sub->subno;
598
599    assert(n > 0);
600    if ((size_t)n >= v->nmatch) {
601        return;
602    }
603
604    MDEBUG(("setting %d\n", n));
605    v->pmatch[n].rm_so = OFF(begin);
606    v->pmatch[n].rm_eo = OFF(end);
607}
608
609/*
610 - dissect - determine subexpression matches (uncomplicated case)
611 ^ static int dissect(struct vars *, struct subre *, chr *, chr *);
612 */
613static int                      /* regexec return code */
614dissect(
615    struct vars *v,
616    struct subre *t,
617    chr *begin,                 /* beginning of relevant substring */
618    chr *end)                   /* end of same */
619{
620    assert(t != NULL);
621    MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
622
623    switch (t->op) {
624    case '=':                   /* terminal node */
625        assert(t->left == NULL && t->right == NULL);
626        return REG_OKAY;        /* no action, parent did the work */
627        break;
628    case '|':                   /* alternation */
629        assert(t->left != NULL);
630        return altdissect(v, t, begin, end);
631        break;
632    case 'b':                   /* back ref -- shouldn't be calling us! */
633        return REG_ASSERT;
634        break;
635    case '.':                   /* concatenation */
636        assert(t->left != NULL && t->right != NULL);
637        return condissect(v, t, begin, end);
638        break;
639    case '(':                   /* capturing */
640        assert(t->left != NULL && t->right == NULL);
641        assert(t->subno > 0);
642        subset(v, t, begin, end);
643        return dissect(v, t->left, begin, end);
644        break;
645    default:
646        return REG_ASSERT;
647        break;
648    }
649}
650
651/*
652 - condissect - determine concatenation subexpression matches (uncomplicated)
653 ^ static int condissect(struct vars *, struct subre *, chr *, chr *);
654 */
655static int                      /* regexec return code */
656condissect(
657    struct vars *v,
658    struct subre *t,
659    chr *begin,                 /* beginning of relevant substring */
660    chr *end)                   /* end of same */
661{
662    struct dfa *d;
663    struct dfa *d2;
664    chr *mid;
665    int i;
666    int shorter = (t->left->flags&SHORTER) ? 1 : 0;
667    chr *stop = (shorter) ? end : begin;
668
669    assert(t->op == '.');
670    assert(t->left != NULL && t->left->cnfa.nstates > 0);
671    assert(t->right != NULL && t->right->cnfa.nstates > 0);
672
673    d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
674    NOERR();
675    d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
676    if (ISERR()) {
677        assert(d2 == NULL);
678        freedfa(d);
679        return v->err;
680    }
681
682    /*
683     * Pick a tentative midpoint.
684     */
685
686    if (shorter) {
687        mid = shortest(v, d, begin, begin, end, NULL, NULL);
688    } else {
689        mid = longest(v, d, begin, end, NULL);
690    }
691    if (mid == NULL) {
692        freedfa(d);
693        freedfa(d2);
694        return REG_ASSERT;
695    }
696    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
697
698    /*
699     * Iterate until satisfaction or failure.
700     */
701
702    while (longest(v, d2, mid, end, NULL) != end) {
703        /*
704         * That midpoint didn't work, find a new one.
705         */
706
707        if (mid == stop) {
708            /*
709             * All possibilities exhausted!
710             */
711
712            MDEBUG(("no midpoint!\n"));
713            freedfa(d);
714            freedfa(d2);
715            return REG_ASSERT;
716        }
717        if (shorter) {
718            mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
719        } else {
720            mid = longest(v, d, begin, mid-1, NULL);
721        }
722        if (mid == NULL) {
723            /*
724             * Failed to find a new one!
725             */
726
727            MDEBUG(("failed midpoint!\n"));
728            freedfa(d);
729            freedfa(d2);
730            return REG_ASSERT;
731        }
732        MDEBUG(("new midpoint %ld\n", LOFF(mid)));
733    }
734
735    /*
736     * Satisfaction.
737     */
738
739    MDEBUG(("successful\n"));
740    freedfa(d);
741    freedfa(d2);
742    i = dissect(v, t->left, begin, mid);
743    if (i != REG_OKAY) {
744        return i;
745    }
746    return dissect(v, t->right, mid, end);
747}
748
749/*
750 - altdissect - determine alternative subexpression matches (uncomplicated)
751 ^ static int altdissect(struct vars *, struct subre *, chr *, chr *);
752 */
753static int                      /* regexec return code */
754altdissect(
755    struct vars *v,
756    struct subre *t,
757    chr *begin,                 /* beginning of relevant substring */
758    chr *end)                   /* end of same */
759{
760    struct dfa *d;
761    int i;
762
763    assert(t != NULL);
764    assert(t->op == '|');
765
766    for (i = 0; t != NULL; t = t->right, i++) {
767        MDEBUG(("trying %dth\n", i));
768        assert(t->left != NULL && t->left->cnfa.nstates > 0);
769        d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
770        if (ISERR()) {
771            return v->err;
772        }
773        if (longest(v, d, begin, end, NULL) == end) {
774            MDEBUG(("success\n"));
775            freedfa(d);
776            return dissect(v, t->left, begin, end);
777        }
778        freedfa(d);
779    }
780    return REG_ASSERT;          /* none of them matched?!? */
781}
782
783/*
784 - cdissect - determine subexpression matches (with complications)
785 * The retry memory stores the offset of the trial midpoint from begin, plus 1
786 * so that 0 uniquely means "clean slate".
787 ^ static int cdissect(struct vars *, struct subre *, chr *, chr *);
788 */
789static int                      /* regexec return code */
790cdissect(
791    struct vars *v,
792    struct subre *t,
793    chr *begin,                 /* beginning of relevant substring */
794    chr *end)                   /* end of same */
795{
796    int er;
797
798    assert(t != NULL);
799    MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
800
801    switch (t->op) {
802    case '=':                   /* terminal node */
803        assert(t->left == NULL && t->right == NULL);
804        return REG_OKAY;        /* no action, parent did the work */
805        break;
806    case '|':                   /* alternation */
807        assert(t->left != NULL);
808        return caltdissect(v, t, begin, end);
809        break;
810    case 'b':                   /* back ref -- shouldn't be calling us! */
811        assert(t->left == NULL && t->right == NULL);
812        return cbrdissect(v, t, begin, end);
813        break;
814    case '.':                   /* concatenation */
815        assert(t->left != NULL && t->right != NULL);
816        return ccondissect(v, t, begin, end);
817        break;
818    case '(':                   /* capturing */
819        assert(t->left != NULL && t->right == NULL);
820        assert(t->subno > 0);
821        er = cdissect(v, t->left, begin, end);
822        if (er == REG_OKAY) {
823            subset(v, t, begin, end);
824        }
825        return er;
826        break;
827    default:
828        return REG_ASSERT;
829        break;
830    }
831}
832
833/*
834 - ccondissect - concatenation subexpression matches (with complications)
835 * The retry memory stores the offset of the trial midpoint from begin, plus 1
836 * so that 0 uniquely means "clean slate".
837 ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
838 */
839static int                      /* regexec return code */
840ccondissect(
841    struct vars *v,
842    struct subre *t,
843    chr *begin,                 /* beginning of relevant substring */
844    chr *end)                   /* end of same */
845{
846    struct dfa *d;
847    struct dfa *d2;
848    chr *mid;
849    int er;
850
851    assert(t->op == '.');
852    assert(t->left != NULL && t->left->cnfa.nstates > 0);
853    assert(t->right != NULL && t->right->cnfa.nstates > 0);
854
855    if (t->left->flags&SHORTER) { /* reverse scan */
856        return crevdissect(v, t, begin, end);
857    }
858
859    d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
860    if (ISERR()) {
861        return v->err;
862    }
863    d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
864    if (ISERR()) {
865        freedfa(d);
866        return v->err;
867    }
868    MDEBUG(("cconcat %d\n", t->retry));
869
870    /*
871     * Pick a tentative midpoint.
872     */
873
874    if (v->mem[t->retry] == 0) {
875        mid = longest(v, d, begin, end, NULL);
876        if (mid == NULL) {
877            freedfa(d);
878            freedfa(d2);
879            return REG_NOMATCH;
880        }
881        MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
882        v->mem[t->retry] = (mid - begin) + 1;
883    } else {
884        mid = begin + (v->mem[t->retry] - 1);
885        MDEBUG(("working midpoint %ld\n", LOFF(mid)));
886    }
887
888    /*
889     * Iterate until satisfaction or failure.
890     */
891
892    for (;;) {
893        /*
894         * Try this midpoint on for size.
895         */
896
897        er = cdissect(v, t->left, begin, mid);
898        if ((er == REG_OKAY) && (longest(v, d2, mid, end, NULL) == end)
899                && (er = cdissect(v, t->right, mid, end)) == REG_OKAY) {
900            break;              /* NOTE BREAK OUT */
901        }
902        if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
903            freedfa(d);
904            freedfa(d2);
905            return er;
906        }
907
908        /*
909         * That midpoint didn't work, find a new one.
910         */
911
912        if (mid == begin) {
913            /*
914             * All possibilities exhausted.
915             */
916
917            MDEBUG(("%d no midpoint\n", t->retry));
918            freedfa(d);
919            freedfa(d2);
920            return REG_NOMATCH;
921        }
922        mid = longest(v, d, begin, mid-1, NULL);
923        if (mid == NULL) {
924            /*
925             * Failed to find a new one.
926             */
927
928            MDEBUG(("%d failed midpoint\n", t->retry));
929            freedfa(d);
930            freedfa(d2);
931            return REG_NOMATCH;
932        }
933        MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
934        v->mem[t->retry] = (mid - begin) + 1;
935        zapmem(v, t->left);
936        zapmem(v, t->right);
937    }
938
939    /*
940     * Satisfaction.
941     */
942
943    MDEBUG(("successful\n"));
944    freedfa(d);
945    freedfa(d2);
946    return REG_OKAY;
947}
948
949/*
950 - crevdissect - determine backref shortest-first subexpression matches
951 * The retry memory stores the offset of the trial midpoint from begin, plus 1
952 * so that 0 uniquely means "clean slate".
953 ^ static int crevdissect(struct vars *, struct subre *, chr *, chr *);
954 */
955static int                      /* regexec return code */
956crevdissect(
957    struct vars *v,
958    struct subre *t,
959    chr *begin,                 /* beginning of relevant substring */
960    chr *end)                   /* end of same */
961{
962    struct dfa *d;
963    struct dfa *d2;
964    chr *mid;
965    int er;
966
967    assert(t->op == '.');
968    assert(t->left != NULL && t->left->cnfa.nstates > 0);
969    assert(t->right != NULL && t->right->cnfa.nstates > 0);
970    assert(t->left->flags&SHORTER);
971
972    /*
973     * Concatenation -- need to split the substring between parts.
974     */
975
976    d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
977    if (ISERR()) {
978        return v->err;
979    }
980    d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
981    if (ISERR()) {
982        freedfa(d);
983        return v->err;
984    }
985    MDEBUG(("crev %d\n", t->retry));
986
987    /*
988     * Pick a tentative midpoint.
989     */
990
991    if (v->mem[t->retry] == 0) {
992        mid = shortest(v, d, begin, begin, end, NULL, NULL);
993        if (mid == NULL) {
994            freedfa(d);
995            freedfa(d2);
996            return REG_NOMATCH;
997        }
998        MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
999        v->mem[t->retry] = (mid - begin) + 1;
1000    } else {
1001        mid = begin + (v->mem[t->retry] - 1);
1002        MDEBUG(("working midpoint %ld\n", LOFF(mid)));
1003    }
1004
1005    /*
1006     * Iterate until satisfaction or failure.
1007     */
1008
1009    for (;;) {
1010        /*
1011         * Try this midpoint on for size.
1012         */
1013
1014        er = cdissect(v, t->left, begin, mid);
1015        if ((er == REG_OKAY) && (longest(v, d2, mid, end, NULL) == end)
1016                && (er = cdissect(v, t->right, mid, end)) == REG_OKAY) {
1017            break;              /* NOTE BREAK OUT */
1018        }
1019        if (er != REG_OKAY && er != REG_NOMATCH) {
1020            freedfa(d);
1021            freedfa(d2);
1022            return er;
1023        }
1024
1025        /*
1026         * That midpoint didn't work, find a new one.
1027         */
1028
1029        if (mid == end) {
1030            /*
1031             * All possibilities exhausted.
1032             */
1033
1034            MDEBUG(("%d no midpoint\n", t->retry));
1035            freedfa(d);
1036            freedfa(d2);
1037            return REG_NOMATCH;
1038        }
1039        mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
1040        if (mid == NULL) {
1041            /*
1042             * Failed to find a new one.
1043             */
1044
1045            MDEBUG(("%d failed midpoint\n", t->retry));
1046            freedfa(d);
1047            freedfa(d2);
1048            return REG_NOMATCH;
1049        }
1050        MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
1051        v->mem[t->retry] = (mid - begin) + 1;
1052        zapmem(v, t->left);
1053        zapmem(v, t->right);
1054    }
1055
1056    /*
1057     * Satisfaction.
1058     */
1059
1060    MDEBUG(("successful\n"));
1061    freedfa(d);
1062    freedfa(d2);
1063    return REG_OKAY;
1064}
1065
1066/*
1067 - cbrdissect - determine backref subexpression matches
1068 ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
1069 */
1070static int                      /* regexec return code */
1071cbrdissect(
1072    struct vars *v,
1073    struct subre *t,
1074    chr *begin,                 /* beginning of relevant substring */
1075    chr *end)                   /* end of same */
1076{
1077    int i;
1078    int n = t->subno;
1079    size_t len;
1080    chr *paren;
1081    chr *p;
1082    chr *stop;
1083    int min = t->min;
1084    int max = t->max;
1085
1086    assert(t != NULL);
1087    assert(t->op == 'b');
1088    assert(n >= 0);
1089    assert((size_t)n < v->nmatch);
1090
1091    MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
1092
1093    if (v->pmatch[n].rm_so == -1) {
1094        return REG_NOMATCH;
1095    }
1096    paren = v->start + v->pmatch[n].rm_so;
1097    len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
1098
1099    /*
1100     * No room to maneuver -- retries are pointless.
1101     */
1102
1103    if (v->mem[t->retry]) {
1104        return REG_NOMATCH;
1105    }
1106    v->mem[t->retry] = 1;
1107
1108    /*
1109     * Special-case zero-length string.
1110     */
1111
1112    if (len == 0) {
1113        if (begin == end) {
1114            return REG_OKAY;
1115        }
1116        return REG_NOMATCH;
1117    }
1118
1119    /*
1120     * And too-short string.
1121     */
1122
1123    assert(end >= begin);
1124    if ((size_t)(end - begin) < len) {
1125        return REG_NOMATCH;
1126    }
1127    stop = end - len;
1128
1129    /*
1130     * Count occurrences.
1131     */
1132
1133    i = 0;
1134    for (p = begin; p <= stop && (i < max || max == INFINITY); p += len) {
1135        if ((*v->g->compare)(paren, p, len) != 0) {
1136            break;
1137        }
1138        i++;
1139    }
1140    MDEBUG(("cbackref found %d\n", i));
1141
1142    /*
1143     * And sort it out.
1144     */
1145
1146    if (p != end) {             /* didn't consume all of it */
1147        return REG_NOMATCH;
1148    }
1149    if (min <= i && (i <= max || max == INFINITY)) {
1150        return REG_OKAY;
1151    }
1152    return REG_NOMATCH;         /* out of range */
1153}
1154
1155/*
1156 - caltdissect - determine alternative subexpression matches (w. complications)
1157 ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
1158 */
1159static int                      /* regexec return code */
1160caltdissect(
1161    struct vars *v,
1162    struct subre *t,
1163    chr *begin,                 /* beginning of relevant substring */
1164    chr *end)                   /* end of same */
1165{
1166    struct dfa *d;
1167    int er;
1168#define UNTRIED 0               /* not yet tried at all */
1169#define TRYING  1               /* top matched, trying submatches */
1170#define TRIED   2               /* top didn't match or submatches exhausted */
1171
1172    if (t == NULL) {
1173        return REG_NOMATCH;
1174    }
1175    assert(t->op == '|');
1176    if (v->mem[t->retry] == TRIED) {
1177        return caltdissect(v, t->right, begin, end);
1178    }
1179
1180    MDEBUG(("calt n%d\n", t->retry));
1181    assert(t->left != NULL);
1182
1183    if (v->mem[t->retry] == UNTRIED) {
1184        d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
1185        if (ISERR()) {
1186            return v->err;
1187        }
1188        if (longest(v, d, begin, end, NULL) != end) {
1189            freedfa(d);
1190            v->mem[t->retry] = TRIED;
1191            return caltdissect(v, t->right, begin, end);
1192        }
1193        freedfa(d);
1194        MDEBUG(("calt matched\n"));
1195        v->mem[t->retry] = TRYING;
1196    }
1197
1198    er = cdissect(v, t->left, begin, end);
1199    if (er != REG_NOMATCH) {
1200        return er;
1201    }
1202
1203    v->mem[t->retry] = TRIED;
1204    return caltdissect(v, t->right, begin, end);
1205}
1206
1207#include "rege_dfa.c"
1208
1209/*
1210 * Local Variables:
1211 * mode: c
1212 * c-basic-offset: 4
1213 * fill-column: 78
1214 * End:
1215 */
Note: See TracBrowser for help on using the repository browser.