[BACK]Return to engine.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / regex

Annotation of src/lib/libc/regex/engine.c, Revision 1.21

1.21    ! junyoung    1: /*     $NetBSD: engine.c,v 1.20 2007/02/08 05:07:23 junyoung Exp $     */
1.5       cgd         2:
1.4       cgd         3: /*-
                      4:  * Copyright (c) 1992, 1993, 1994
                      5:  *     The Regents of the University of California.  All rights reserved.
1.15      agc         6:  *
                      7:  * This code is derived from software contributed to Berkeley by
                      8:  * Henry Spencer.
                      9:  *
                     10:  * Redistribution and use in source and binary forms, with or without
                     11:  * modification, are permitted provided that the following conditions
                     12:  * are met:
                     13:  * 1. Redistributions of source code must retain the above copyright
                     14:  *    notice, this list of conditions and the following disclaimer.
                     15:  * 2. Redistributions in binary form must reproduce the above copyright
                     16:  *    notice, this list of conditions and the following disclaimer in the
                     17:  *    documentation and/or other materials provided with the distribution.
                     18:  * 3. Neither the name of the University nor the names of its contributors
                     19:  *    may be used to endorse or promote products derived from this software
                     20:  *    without specific prior written permission.
                     21:  *
                     22:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     23:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     24:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     25:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     26:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     27:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     28:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     29:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     30:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     31:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     32:  * SUCH DAMAGE.
                     33:  *
                     34:  *     @(#)engine.c    8.5 (Berkeley) 3/20/94
                     35:  */
                     36:
                     37: /*-
                     38:  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
1.4       cgd        39:  *
                     40:  * This code is derived from software contributed to Berkeley by
                     41:  * Henry Spencer.
                     42:  *
                     43:  * Redistribution and use in source and binary forms, with or without
                     44:  * modification, are permitted provided that the following conditions
                     45:  * are met:
                     46:  * 1. Redistributions of source code must retain the above copyright
                     47:  *    notice, this list of conditions and the following disclaimer.
                     48:  * 2. Redistributions in binary form must reproduce the above copyright
                     49:  *    notice, this list of conditions and the following disclaimer in the
                     50:  *    documentation and/or other materials provided with the distribution.
                     51:  * 3. All advertising materials mentioning features or use of this software
                     52:  *    must display the following acknowledgement:
                     53:  *     This product includes software developed by the University of
                     54:  *     California, Berkeley and its contributors.
                     55:  * 4. Neither the name of the University nor the names of its contributors
                     56:  *    may be used to endorse or promote products derived from this software
                     57:  *    without specific prior written permission.
                     58:  *
                     59:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     60:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     61:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     62:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     63:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     64:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     65:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     66:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     67:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     68:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     69:  * SUCH DAMAGE.
                     70:  *
                     71:  *     @(#)engine.c    8.5 (Berkeley) 3/20/94
                     72:  */
                     73:
1.1       jtc        74: /*
                     75:  * The matching engine and friends.  This file is #included by regexec.c
                     76:  * after suitable #defines of a variety of macros used herein, so that
                     77:  * different state representations can be used without duplicating masses
                     78:  * of code.
                     79:  */
                     80:
                     81: #ifdef SNAMES
                     82: #define        matcher smatcher
                     83: #define        fast    sfast
                     84: #define        slow    sslow
                     85: #define        dissect sdissect
                     86: #define        backref sbackref
                     87: #define        step    sstep
                     88: #define        print   sprint
                     89: #define        at      sat
                     90: #define        match   smat
1.14      christos   91: #define        nope    snope
1.1       jtc        92: #endif
                     93: #ifdef LNAMES
                     94: #define        matcher lmatcher
                     95: #define        fast    lfast
                     96: #define        slow    lslow
                     97: #define        dissect ldissect
                     98: #define        backref lbackref
                     99: #define        step    lstep
                    100: #define        print   lprint
                    101: #define        at      lat
                    102: #define        match   lmat
1.14      christos  103: #define        nope    lnope
1.1       jtc       104: #endif
                    105:
                    106: /* another structure passed up and down to avoid zillions of parameters */
                    107: struct match {
                    108:        struct re_guts *g;
                    109:        int eflags;
                    110:        regmatch_t *pmatch;     /* [nsub+1] (0 element unused) */
1.19      yamt      111:        const char *offp;       /* offsets work from here */
                    112:        const char *beginp;     /* start of string -- virtual NUL precedes */
                    113:        const char *endp;       /* end of string -- virtual NUL here */
                    114:        const char *coldp;      /* can be no match starting before here */
                    115:        const char **lastpos;   /* [nplus+1] */
1.1       jtc       116:        STATEVARS;
                    117:        states st;              /* current states */
                    118:        states fresh;           /* states for a fresh start */
                    119:        states tmp;             /* temporary */
                    120:        states empty;           /* empty set of states */
                    121: };
                    122:
1.4       cgd       123: /* ========= begin header generated by ./mkh ========= */
                    124: #ifdef __cplusplus
                    125: extern "C" {
                    126: #endif
                    127:
                    128: /* === engine.c === */
1.20      junyoung  129: static int matcher(struct re_guts *g, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
                    130: static const char *dissect(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
                    131: static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev);
                    132: static const char *fast(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
                    133: static const char *slow(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
                    134: static states step(struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft);
1.4       cgd       135: #define        BOL     (OUT+1)
                    136: #define        EOL     (BOL+1)
                    137: #define        BOLEOL  (BOL+2)
                    138: #define        NOTHING (BOL+3)
                    139: #define        BOW     (BOL+4)
                    140: #define        EOW     (BOL+5)
                    141: #define        CODEMAX (BOL+5)         /* highest code used */
                    142: #define        NONCHAR(c)      ((c) > CHAR_MAX)
                    143: #define        NNONCHAR        (CODEMAX-CHAR_MAX)
                    144: #ifdef REDEBUG
1.20      junyoung  145: static void print(struct match *m, char *caption, states st, int ch, FILE *d);
1.4       cgd       146: #endif
                    147: #ifdef REDEBUG
1.20      junyoung  148: static void at(struct match *m, char *title, char *start, char *stop, sopno startst, sopno stopst);
1.4       cgd       149: #endif
                    150: #ifdef REDEBUG
1.20      junyoung  151: static char *pchar(int ch);
1.4       cgd       152: #endif
                    153:
                    154: #ifdef __cplusplus
                    155: }
                    156: #endif
                    157: /* ========= end header generated by ./mkh ========= */
1.1       jtc       158:
                    159: #ifdef REDEBUG
                    160: #define        SP(t, s, c)     print(m, t, s, c, stdout)
                    161: #define        AT(t, p1, p2, s1, s2)   at(m, t, p1, p2, s1, s2)
                    162: #define        NOTE(str)       { if (m->eflags&REG_TRACE) printf("=%s\n", (str)); }
1.14      christos  163: static int nope = 0;
1.1       jtc       164: #else
                    165: #define        SP(t, s, c)     /* nothing */
                    166: #define        AT(t, p1, p2, s1, s2)   /* nothing */
                    167: #define        NOTE(s) /* nothing */
                    168: #endif
                    169:
                    170: /*
                    171:  - matcher - the actual matching engine
1.8       perry     172:  == static int matcher(struct re_guts *g, char *string, \
1.1       jtc       173:  ==    size_t nmatch, regmatch_t pmatch[], int eflags);
                    174:  */
                    175: static int                     /* 0 success, REG_NOMATCH failure */
1.21    ! junyoung  176: matcher(
        !           177:     struct re_guts *g,
        !           178:     const char *string,
        !           179:     size_t nmatch,
        !           180:     regmatch_t pmatch[],
        !           181:     int eflags)
1.1       jtc       182: {
1.19      yamt      183:        const char *endp;
1.8       perry     184:        int i;
1.1       jtc       185:        struct match mv;
1.8       perry     186:        struct match *m = &mv;
1.19      yamt      187:        const char *dp;
1.8       perry     188:        const sopno gf = g->firststate+1;       /* +1 for OEND */
                    189:        const sopno gl = g->laststate;
1.19      yamt      190:        const char *start;
                    191:        const char *stop;
1.13      christos  192:        int error = 0;
1.1       jtc       193:
1.12      lukem     194:        _DIAGASSERT(g != NULL);
                    195:        _DIAGASSERT(string != NULL);
                    196:        /* pmatch checked below */
                    197:
1.1       jtc       198:        /* simplify the situation where possible */
                    199:        if (g->cflags&REG_NOSUB)
                    200:                nmatch = 0;
                    201:        if (eflags&REG_STARTEND) {
1.12      lukem     202:                _DIAGASSERT(pmatch != NULL);
1.11      christos  203:                start = string + (size_t)pmatch[0].rm_so;
                    204:                stop = string + (size_t)pmatch[0].rm_eo;
1.1       jtc       205:        } else {
                    206:                start = string;
                    207:                stop = start + strlen(start);
                    208:        }
                    209:        if (stop < start)
                    210:                return(REG_INVARG);
                    211:
                    212:        /* prescreening; this does wonders for this rather slow code */
                    213:        if (g->must != NULL) {
                    214:                for (dp = start; dp < stop; dp++)
                    215:                        if (*dp == g->must[0] && stop - dp >= g->mlen &&
                    216:                                memcmp(dp, g->must, (size_t)g->mlen) == 0)
                    217:                                break;
                    218:                if (dp == stop)         /* we didn't find g->must */
                    219:                        return(REG_NOMATCH);
                    220:        }
                    221:
                    222:        /* match struct setup */
                    223:        m->g = g;
                    224:        m->eflags = eflags;
                    225:        m->pmatch = NULL;
                    226:        m->lastpos = NULL;
                    227:        m->offp = string;
                    228:        m->beginp = start;
                    229:        m->endp = stop;
                    230:        STATESETUP(m, 4);
                    231:        SETUP(m->st);
                    232:        SETUP(m->fresh);
                    233:        SETUP(m->tmp);
                    234:        SETUP(m->empty);
                    235:        CLEAR(m->empty);
                    236:
                    237:        /* this loop does only one repetition except for backrefs */
                    238:        for (;;) {
                    239:                endp = fast(m, start, stop, gf, gl);
                    240:                if (endp == NULL) {             /* a miss */
1.13      christos  241:                        error = REG_NOMATCH;
                    242:                        goto done;
1.1       jtc       243:                }
                    244:                if (nmatch == 0 && !g->backrefs)
                    245:                        break;          /* no further info needed */
                    246:
                    247:                /* where? */
                    248:                assert(m->coldp != NULL);
                    249:                for (;;) {
                    250:                        NOTE("finding start");
                    251:                        endp = slow(m, m->coldp, stop, gf, gl);
                    252:                        if (endp != NULL)
                    253:                                break;
                    254:                        assert(m->coldp < m->endp);
                    255:                        m->coldp++;
                    256:                }
                    257:                if (nmatch == 1 && !g->backrefs)
                    258:                        break;          /* no further info needed */
                    259:
                    260:                /* oh my, he wants the subexpressions... */
                    261:                if (m->pmatch == NULL)
                    262:                        m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
                    263:                                                        sizeof(regmatch_t));
                    264:                if (m->pmatch == NULL) {
1.13      christos  265:                        error = REG_ESPACE;
                    266:                        goto done;
1.1       jtc       267:                }
                    268:                for (i = 1; i <= m->g->nsub; i++)
1.10      drochner  269:                        m->pmatch[i].rm_so = m->pmatch[i].rm_eo = (regoff_t)-1;
1.1       jtc       270:                if (!g->backrefs && !(m->eflags&REG_BACKR)) {
                    271:                        NOTE("dissecting");
                    272:                        dp = dissect(m, m->coldp, endp, gf, gl);
                    273:                } else {
                    274:                        if (g->nplus > 0 && m->lastpos == NULL)
1.19      yamt      275:                                m->lastpos = malloc((g->nplus+1) *
                    276:                                                        sizeof(const char *));
1.1       jtc       277:                        if (g->nplus > 0 && m->lastpos == NULL) {
1.13      christos  278:                                error = REG_ESPACE;
                    279:                                goto done;
1.1       jtc       280:                        }
                    281:                        NOTE("backref dissect");
                    282:                        dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
                    283:                }
                    284:                if (dp != NULL)
                    285:                        break;
                    286:
                    287:                /* uh-oh... we couldn't find a subexpression-level match */
                    288:                assert(g->backrefs);    /* must be back references doing it */
                    289:                assert(g->nplus == 0 || m->lastpos != NULL);
                    290:                for (;;) {
                    291:                        if (dp != NULL || endp <= m->coldp)
                    292:                                break;          /* defeat */
                    293:                        NOTE("backoff");
                    294:                        endp = slow(m, m->coldp, endp-1, gf, gl);
                    295:                        if (endp == NULL)
                    296:                                break;          /* defeat */
                    297:                        /* try it on a shorter possibility */
                    298: #ifndef NDEBUG
                    299:                        for (i = 1; i <= m->g->nsub; i++) {
1.10      drochner  300:                                assert(m->pmatch[i].rm_so == (regoff_t)-1);
                    301:                                assert(m->pmatch[i].rm_eo == (regoff_t)-1);
1.1       jtc       302:                        }
                    303: #endif
                    304:                        NOTE("backoff dissect");
                    305:                        dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
                    306:                }
                    307:                assert(dp == NULL || dp == endp);
                    308:                if (dp != NULL)         /* found a shorter one */
                    309:                        break;
                    310:
                    311:                /* despite initial appearances, there is no match here */
                    312:                NOTE("false alarm");
                    313:                start = m->coldp + 1;   /* recycle starting later */
                    314:                assert(start <= stop);
                    315:        }
                    316:
                    317:        /* fill in the details if requested */
                    318:        if (nmatch > 0) {
1.12      lukem     319:                _DIAGASSERT(pmatch != NULL);
1.1       jtc       320:                pmatch[0].rm_so = m->coldp - m->offp;
                    321:                pmatch[0].rm_eo = endp - m->offp;
                    322:        }
                    323:        if (nmatch > 1) {
                    324:                assert(m->pmatch != NULL);
                    325:                for (i = 1; i < nmatch; i++)
                    326:                        if (i <= m->g->nsub)
                    327:                                pmatch[i] = m->pmatch[i];
                    328:                        else {
1.10      drochner  329:                                pmatch[i].rm_so = (regoff_t)-1;
                    330:                                pmatch[i].rm_eo = (regoff_t)-1;
1.1       jtc       331:                        }
                    332:        }
                    333:
1.13      christos  334: done:
                    335:        if (m->pmatch != NULL) {
1.9       christos  336:                free(m->pmatch);
1.13      christos  337:                m->pmatch = NULL;
                    338:        }
                    339:        if (m->lastpos != NULL) {
1.9       christos  340:                free(m->lastpos);
1.13      christos  341:                m->lastpos = NULL;
                    342:        }
1.1       jtc       343:        STATETEARDOWN(m);
1.13      christos  344:        return error;
1.1       jtc       345: }
                    346:
                    347: /*
                    348:  - dissect - figure out what matched what, no back references
1.19      yamt      349:  == static const char *dissect(struct match *m, const char *start, \
                    350:  ==    const char *stop, sopno startst, sopno stopst);
1.1       jtc       351:  */
1.19      yamt      352: static const char *                    /* == stop (success) always */
1.21    ! junyoung  353: dissect(
        !           354:     struct match *m,
        !           355:     const char *start,
        !           356:     const char *stop,
        !           357:     sopno startst,
        !           358:     sopno stopst)
1.1       jtc       359: {
1.8       perry     360:        int i;
                    361:        sopno ss;       /* start sop of current subRE */
                    362:        sopno es;       /* end sop of current subRE */
1.19      yamt      363:        const char *sp; /* start of string matched by it */
                    364:        const char *stp; /* string matched by it cannot pass here */
                    365:        const char *rest; /* start of rest of string */
                    366:        const char *tail; /* string unmatched by rest of RE */
1.8       perry     367:        sopno ssub;     /* start sop of subsubRE */
                    368:        sopno esub;     /* end sop of subsubRE */
1.19      yamt      369:        const char *ssp; /* start of string matched by subsubRE */
                    370:        const char *sep; /* end of string matched by subsubRE */
                    371:        const char *oldssp; /* previous ssp */
1.9       christos  372: #ifndef NDEBUG
1.19      yamt      373:        const char *dp;
1.9       christos  374: #endif
1.1       jtc       375:
1.12      lukem     376:        _DIAGASSERT(m != NULL);
                    377:        _DIAGASSERT(start != NULL);
                    378:        _DIAGASSERT(stop != NULL);
                    379:
1.1       jtc       380:        AT("diss", start, stop, startst, stopst);
                    381:        sp = start;
                    382:        for (ss = startst; ss < stopst; ss = es) {
                    383:                /* identify end of subRE */
                    384:                es = ss;
                    385:                switch (OP(m->g->strip[es])) {
                    386:                case OPLUS_:
                    387:                case OQUEST_:
                    388:                        es += OPND(m->g->strip[es]);
                    389:                        break;
                    390:                case OCH_:
                    391:                        while (OP(m->g->strip[es]) != O_CH)
                    392:                                es += OPND(m->g->strip[es]);
                    393:                        break;
                    394:                }
                    395:                es++;
                    396:
                    397:                /* figure out what it matched */
                    398:                switch (OP(m->g->strip[ss])) {
                    399:                case OEND:
                    400:                        assert(nope);
                    401:                        break;
                    402:                case OCHAR:
                    403:                        sp++;
                    404:                        break;
                    405:                case OBOL:
                    406:                case OEOL:
                    407:                case OBOW:
                    408:                case OEOW:
                    409:                        break;
                    410:                case OANY:
                    411:                case OANYOF:
                    412:                        sp++;
                    413:                        break;
                    414:                case OBACK_:
                    415:                case O_BACK:
                    416:                        assert(nope);
                    417:                        break;
                    418:                /* cases where length of match is hard to find */
                    419:                case OQUEST_:
                    420:                        stp = stop;
                    421:                        for (;;) {
                    422:                                /* how long could this one be? */
                    423:                                rest = slow(m, sp, stp, ss, es);
                    424:                                assert(rest != NULL);   /* it did match */
                    425:                                /* could the rest match the rest? */
                    426:                                tail = slow(m, rest, stop, es, stopst);
                    427:                                if (tail == stop)
                    428:                                        break;          /* yes! */
                    429:                                /* no -- try a shorter match for this one */
                    430:                                stp = rest - 1;
                    431:                                assert(stp >= sp);      /* it did work */
                    432:                        }
                    433:                        ssub = ss + 1;
                    434:                        esub = es - 1;
                    435:                        /* did innards match? */
                    436:                        if (slow(m, sp, rest, ssub, esub) != NULL) {
1.9       christos  437: #ifdef NDEBUG
                    438:                                (void)
                    439: #else
                    440:                                dp =
                    441: #endif
                    442:                                    dissect(m, sp, rest, ssub, esub);
1.1       jtc       443:                                assert(dp == rest);
                    444:                        } else          /* no */
                    445:                                assert(sp == rest);
                    446:                        sp = rest;
                    447:                        break;
                    448:                case OPLUS_:
                    449:                        stp = stop;
                    450:                        for (;;) {
                    451:                                /* how long could this one be? */
                    452:                                rest = slow(m, sp, stp, ss, es);
                    453:                                assert(rest != NULL);   /* it did match */
                    454:                                /* could the rest match the rest? */
                    455:                                tail = slow(m, rest, stop, es, stopst);
                    456:                                if (tail == stop)
                    457:                                        break;          /* yes! */
                    458:                                /* no -- try a shorter match for this one */
                    459:                                stp = rest - 1;
                    460:                                assert(stp >= sp);      /* it did work */
                    461:                        }
                    462:                        ssub = ss + 1;
                    463:                        esub = es - 1;
                    464:                        ssp = sp;
                    465:                        oldssp = ssp;
                    466:                        for (;;) {      /* find last match of innards */
                    467:                                sep = slow(m, ssp, rest, ssub, esub);
                    468:                                if (sep == NULL || sep == ssp)
                    469:                                        break;  /* failed or matched null */
                    470:                                oldssp = ssp;   /* on to next try */
                    471:                                ssp = sep;
                    472:                        }
                    473:                        if (sep == NULL) {
                    474:                                /* last successful match */
                    475:                                sep = ssp;
                    476:                                ssp = oldssp;
                    477:                        }
                    478:                        assert(sep == rest);    /* must exhaust substring */
                    479:                        assert(slow(m, ssp, sep, ssub, esub) == rest);
1.9       christos  480: #ifdef NDEBUG
                    481:                        (void)
                    482: #else
                    483:                        dp =
                    484: #endif
                    485:                            dissect(m, ssp, sep, ssub, esub);
1.1       jtc       486:                        assert(dp == sep);
                    487:                        sp = rest;
                    488:                        break;
                    489:                case OCH_:
                    490:                        stp = stop;
                    491:                        for (;;) {
                    492:                                /* how long could this one be? */
                    493:                                rest = slow(m, sp, stp, ss, es);
                    494:                                assert(rest != NULL);   /* it did match */
                    495:                                /* could the rest match the rest? */
                    496:                                tail = slow(m, rest, stop, es, stopst);
                    497:                                if (tail == stop)
                    498:                                        break;          /* yes! */
                    499:                                /* no -- try a shorter match for this one */
                    500:                                stp = rest - 1;
                    501:                                assert(stp >= sp);      /* it did work */
                    502:                        }
                    503:                        ssub = ss + 1;
                    504:                        esub = ss + OPND(m->g->strip[ss]) - 1;
                    505:                        assert(OP(m->g->strip[esub]) == OOR1);
                    506:                        for (;;) {      /* find first matching branch */
                    507:                                if (slow(m, sp, rest, ssub, esub) == rest)
                    508:                                        break;  /* it matched all of it */
                    509:                                /* that one missed, try next one */
                    510:                                assert(OP(m->g->strip[esub]) == OOR1);
                    511:                                esub++;
                    512:                                assert(OP(m->g->strip[esub]) == OOR2);
                    513:                                ssub = esub + 1;
                    514:                                esub += OPND(m->g->strip[esub]);
                    515:                                if (OP(m->g->strip[esub]) == OOR2)
                    516:                                        esub--;
                    517:                                else
                    518:                                        assert(OP(m->g->strip[esub]) == O_CH);
                    519:                        }
1.9       christos  520: #ifdef NDEBUG
                    521:                        (void)
                    522: #else
                    523:                        dp =
                    524: #endif
                    525:                            dissect(m, sp, rest, ssub, esub);
1.1       jtc       526:                        assert(dp == rest);
                    527:                        sp = rest;
                    528:                        break;
                    529:                case O_PLUS:
                    530:                case O_QUEST:
                    531:                case OOR1:
                    532:                case OOR2:
                    533:                case O_CH:
                    534:                        assert(nope);
                    535:                        break;
                    536:                case OLPAREN:
                    537:                        i = OPND(m->g->strip[ss]);
1.2       jtc       538:                        assert(0 < i && i <= m->g->nsub);
1.1       jtc       539:                        m->pmatch[i].rm_so = sp - m->offp;
                    540:                        break;
                    541:                case ORPAREN:
                    542:                        i = OPND(m->g->strip[ss]);
1.2       jtc       543:                        assert(0 < i && i <= m->g->nsub);
1.1       jtc       544:                        m->pmatch[i].rm_eo = sp - m->offp;
                    545:                        break;
                    546:                default:                /* uh oh */
                    547:                        assert(nope);
                    548:                        break;
                    549:                }
                    550:        }
                    551:
                    552:        assert(sp == stop);
                    553:        return(sp);
                    554: }
                    555:
                    556: /*
                    557:  - backref - figure out what matched what, figuring in back references
1.19      yamt      558:  == static const char *backref(struct match *m, const char *start, \
                    559:  ==    const char *stop, sopno startst, sopno stopst, sopno lev);
1.1       jtc       560:  */
1.19      yamt      561: static const char *            /* == stop (success) or NULL (failure) */
1.21    ! junyoung  562: backref(
        !           563:     struct match *m,
        !           564:     const char *start,
        !           565:     const char *stop,
        !           566:     sopno startst,
        !           567:     sopno stopst,
        !           568:     sopno lev)                 /* PLUS nesting level */
1.1       jtc       569: {
1.8       perry     570:        int i;
                    571:        sopno ss;       /* start sop of current subRE */
1.19      yamt      572:        const char *sp; /* start of string matched by it */
1.8       perry     573:        sopno ssub;     /* start sop of subsubRE */
                    574:        sopno esub;     /* end sop of subsubRE */
1.19      yamt      575:        const char *ssp; /* start of string matched by subsubRE */
                    576:        const char *dp;
1.8       perry     577:        size_t len;
                    578:        int hard;
                    579:        sop s;
                    580:        regoff_t offsave;
                    581:        cset *cs;
1.1       jtc       582:
1.12      lukem     583:        _DIAGASSERT(m != NULL);
                    584:        _DIAGASSERT(start != NULL);
                    585:        _DIAGASSERT(stop != NULL);
                    586:
1.1       jtc       587:        AT("back", start, stop, startst, stopst);
                    588:        sp = start;
                    589:
                    590:        /* get as far as we can with easy stuff */
                    591:        hard = 0;
                    592:        for (ss = startst; !hard && ss < stopst; ss++)
                    593:                switch (OP(s = m->g->strip[ss])) {
                    594:                case OCHAR:
                    595:                        if (sp == stop || *sp++ != (char)OPND(s))
                    596:                                return(NULL);
                    597:                        break;
                    598:                case OANY:
                    599:                        if (sp == stop)
                    600:                                return(NULL);
                    601:                        sp++;
                    602:                        break;
                    603:                case OANYOF:
                    604:                        cs = &m->g->sets[OPND(s)];
                    605:                        if (sp == stop || !CHIN(cs, *sp++))
                    606:                                return(NULL);
                    607:                        break;
                    608:                case OBOL:
                    609:                        if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
                    610:                                        (sp < m->endp && *(sp-1) == '\n' &&
                    611:                                                (m->g->cflags&REG_NEWLINE)) )
                    612:                                { /* yes */ }
                    613:                        else
                    614:                                return(NULL);
                    615:                        break;
                    616:                case OEOL:
                    617:                        if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
                    618:                                        (sp < m->endp && *sp == '\n' &&
                    619:                                                (m->g->cflags&REG_NEWLINE)) )
                    620:                                { /* yes */ }
                    621:                        else
                    622:                                return(NULL);
                    623:                        break;
                    624:                case OBOW:
1.17      enami     625:                        if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
                    626:                                        (sp < m->endp && *(sp-1) == '\n' &&
                    627:                                                (m->g->cflags&REG_NEWLINE)) ||
                    628:                                        (sp > m->beginp &&
                    629:                                                        !ISWORD(*(sp-1))) ) &&
                    630:                                        (sp < m->endp && ISWORD(*sp)) )
1.1       jtc       631:                                { /* yes */ }
                    632:                        else
                    633:                                return(NULL);
                    634:                        break;
                    635:                case OEOW:
1.17      enami     636:                        if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
                    637:                                        (sp < m->endp && *sp == '\n' &&
                    638:                                                (m->g->cflags&REG_NEWLINE)) ||
                    639:                                        (sp < m->endp && !ISWORD(*sp)) ) &&
                    640:                                        (sp > m->beginp && ISWORD(*(sp-1))) )
1.1       jtc       641:                                { /* yes */ }
                    642:                        else
                    643:                                return(NULL);
                    644:                        break;
                    645:                case O_QUEST:
                    646:                        break;
                    647:                case OOR1:      /* matches null but needs to skip */
                    648:                        ss++;
                    649:                        s = m->g->strip[ss];
                    650:                        do {
                    651:                                assert(OP(s) == OOR2);
                    652:                                ss += OPND(s);
                    653:                        } while (OP(s = m->g->strip[ss]) != O_CH);
                    654:                        /* note that the ss++ gets us past the O_CH */
                    655:                        break;
                    656:                default:        /* have to make a choice */
                    657:                        hard = 1;
                    658:                        break;
                    659:                }
                    660:        if (!hard) {            /* that was it! */
                    661:                if (sp != stop)
                    662:                        return(NULL);
                    663:                return(sp);
                    664:        }
                    665:        ss--;                   /* adjust for the for's final increment */
                    666:
                    667:        /* the hard stuff */
                    668:        AT("hard", sp, stop, ss, stopst);
                    669:        s = m->g->strip[ss];
                    670:        switch (OP(s)) {
                    671:        case OBACK_:            /* the vilest depths */
                    672:                i = OPND(s);
1.2       jtc       673:                assert(0 < i && i <= m->g->nsub);
1.10      drochner  674:                if (m->pmatch[i].rm_eo == (regoff_t)-1)
1.1       jtc       675:                        return(NULL);
1.10      drochner  676:                assert(m->pmatch[i].rm_so != (regoff_t)-1);
1.11      christos  677:                len = (size_t)(m->pmatch[i].rm_eo - m->pmatch[i].rm_so);
1.18      christos  678:                if (len == 0)
                    679:                        return(NULL);
1.1       jtc       680:                assert(stop - m->beginp >= len);
                    681:                if (sp > stop - len)
                    682:                        return(NULL);   /* not enough left to match */
1.11      christos  683:                ssp = m->offp + (size_t)m->pmatch[i].rm_so;
1.1       jtc       684:                if (memcmp(sp, ssp, len) != 0)
                    685:                        return(NULL);
                    686:                while (m->g->strip[ss] != SOP(O_BACK, i))
                    687:                        ss++;
                    688:                return(backref(m, sp+len, stop, ss+1, stopst, lev));
1.9       christos  689:
1.1       jtc       690:        case OQUEST_:           /* to null or not */
                    691:                dp = backref(m, sp, stop, ss+1, stopst, lev);
                    692:                if (dp != NULL)
                    693:                        return(dp);     /* not */
                    694:                return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
1.9       christos  695:
1.1       jtc       696:        case OPLUS_:
                    697:                assert(m->lastpos != NULL);
                    698:                assert(lev+1 <= m->g->nplus);
                    699:                m->lastpos[lev+1] = sp;
                    700:                return(backref(m, sp, stop, ss+1, stopst, lev+1));
1.9       christos  701:
1.1       jtc       702:        case O_PLUS:
                    703:                if (sp == m->lastpos[lev])      /* last pass matched null */
                    704:                        return(backref(m, sp, stop, ss+1, stopst, lev-1));
                    705:                /* try another pass */
                    706:                m->lastpos[lev] = sp;
                    707:                dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
                    708:                if (dp == NULL)
1.9       christos  709:                        dp = backref(m, sp, stop, ss+1, stopst, lev-1);
                    710:                return(dp);
                    711:
1.1       jtc       712:        case OCH_:              /* find the right one, if any */
                    713:                ssub = ss + 1;
                    714:                esub = ss + OPND(s) - 1;
                    715:                assert(OP(m->g->strip[esub]) == OOR1);
                    716:                for (;;) {      /* find first matching branch */
                    717:                        dp = backref(m, sp, stop, ssub, esub, lev);
                    718:                        if (dp != NULL)
                    719:                                return(dp);
                    720:                        /* that one missed, try next one */
                    721:                        if (OP(m->g->strip[esub]) == O_CH)
                    722:                                return(NULL);   /* there is none */
                    723:                        esub++;
                    724:                        assert(OP(m->g->strip[esub]) == OOR2);
                    725:                        ssub = esub + 1;
                    726:                        esub += OPND(m->g->strip[esub]);
                    727:                        if (OP(m->g->strip[esub]) == OOR2)
                    728:                                esub--;
                    729:                        else
                    730:                                assert(OP(m->g->strip[esub]) == O_CH);
                    731:                }
1.9       christos  732:
1.1       jtc       733:        case OLPAREN:           /* must undo assignment if rest fails */
                    734:                i = OPND(s);
1.2       jtc       735:                assert(0 < i && i <= m->g->nsub);
1.1       jtc       736:                offsave = m->pmatch[i].rm_so;
                    737:                m->pmatch[i].rm_so = sp - m->offp;
                    738:                dp = backref(m, sp, stop, ss+1, stopst, lev);
                    739:                if (dp != NULL)
                    740:                        return(dp);
                    741:                m->pmatch[i].rm_so = offsave;
                    742:                return(NULL);
1.9       christos  743:
1.1       jtc       744:        case ORPAREN:           /* must undo assignment if rest fails */
                    745:                i = OPND(s);
1.2       jtc       746:                assert(0 < i && i <= m->g->nsub);
1.1       jtc       747:                offsave = m->pmatch[i].rm_eo;
                    748:                m->pmatch[i].rm_eo = sp - m->offp;
                    749:                dp = backref(m, sp, stop, ss+1, stopst, lev);
                    750:                if (dp != NULL)
                    751:                        return(dp);
                    752:                m->pmatch[i].rm_eo = offsave;
                    753:                return(NULL);
1.9       christos  754:
1.1       jtc       755:        default:                /* uh oh */
                    756:                assert(nope);
                    757:                break;
                    758:        }
                    759:
                    760:        /* "can't happen" */
                    761:        assert(nope);
                    762:        /* NOTREACHED */
1.7       christos  763:        return NULL;
1.1       jtc       764: }
                    765:
                    766: /*
                    767:  - fast - step through the string at top speed
1.19      yamt      768:  == static const char *fast(struct match *m, const char *start, \
                    769:  ==    const char *stop, sopno startst, sopno stopst);
1.1       jtc       770:  */
1.19      yamt      771: static const char *            /* where tentative match ended, or NULL */
1.21    ! junyoung  772: fast(
        !           773:     struct match *m,
        !           774:     const char *start,
        !           775:     const char *stop,
        !           776:     sopno startst,
        !           777:     sopno stopst)
1.1       jtc       778: {
1.8       perry     779:        states st = m->st;
                    780:        states fresh = m->fresh;
                    781:        states tmp = m->tmp;
1.19      yamt      782:        const char *p = start;
1.17      enami     783:        int c = (start == m->beginp) ? OUT : *(start-1);
1.8       perry     784:        int lastc;      /* previous c */
                    785:        int flagch;
                    786:        int i;
1.19      yamt      787:        const char *coldp; /* last p after which no match was underway */
1.1       jtc       788:
1.12      lukem     789:        _DIAGASSERT(m != NULL);
                    790:        _DIAGASSERT(start != NULL);
                    791:        _DIAGASSERT(stop != NULL);
                    792:
1.1       jtc       793:        CLEAR(st);
                    794:        SET1(st, startst);
                    795:        st = step(m->g, startst, stopst, st, NOTHING, st);
                    796:        ASSIGN(fresh, st);
                    797:        SP("start", st, *p);
                    798:        coldp = NULL;
                    799:        for (;;) {
                    800:                /* next character */
                    801:                lastc = c;
1.17      enami     802:                c = (p == m->endp) ? OUT : *p;
1.1       jtc       803:                if (EQ(st, fresh))
                    804:                        coldp = p;
                    805:
                    806:                /* is there an EOL and/or BOL between lastc and c? */
                    807:                flagch = '\0';
                    808:                i = 0;
                    809:                if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
                    810:                                (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
                    811:                        flagch = BOL;
                    812:                        i = m->g->nbol;
                    813:                }
                    814:                if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
                    815:                                (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
                    816:                        flagch = (flagch == BOL) ? BOLEOL : EOL;
                    817:                        i += m->g->neol;
                    818:                }
                    819:                if (i != 0) {
                    820:                        for (; i > 0; i--)
                    821:                                st = step(m->g, startst, stopst, st, flagch, st);
                    822:                        SP("boleol", st, c);
                    823:                }
                    824:
                    825:                /* how about a word boundary? */
1.3       jtc       826:                if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
                    827:                                        (c != OUT && ISWORD(c)) ) {
1.1       jtc       828:                        flagch = BOW;
                    829:                }
1.3       jtc       830:                if ( (lastc != OUT && ISWORD(lastc)) &&
                    831:                                (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
1.1       jtc       832:                        flagch = EOW;
                    833:                }
                    834:                if (flagch == BOW || flagch == EOW) {
                    835:                        st = step(m->g, startst, stopst, st, flagch, st);
                    836:                        SP("boweow", st, c);
                    837:                }
                    838:
                    839:                /* are we done? */
                    840:                if (ISSET(st, stopst) || p == stop)
                    841:                        break;          /* NOTE BREAK OUT */
                    842:
                    843:                /* no, we must deal with this character */
                    844:                ASSIGN(tmp, st);
                    845:                ASSIGN(st, fresh);
                    846:                assert(c != OUT);
                    847:                st = step(m->g, startst, stopst, tmp, c, st);
                    848:                SP("aft", st, c);
                    849:                assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
                    850:                p++;
                    851:        }
                    852:
                    853:        assert(coldp != NULL);
                    854:        m->coldp = coldp;
                    855:        if (ISSET(st, stopst))
                    856:                return(p+1);
                    857:        else
                    858:                return(NULL);
                    859: }
                    860:
                    861: /*
                    862:  - slow - step through the string more deliberately
1.19      yamt      863:  == static const char *slow(struct match *m, const char *start, \
                    864:  ==    const char *stop, sopno startst, sopno stopst);
1.1       jtc       865:  */
1.19      yamt      866: static const char *                    /* where it ended */
1.21    ! junyoung  867: slow(
        !           868:     struct match *m,
        !           869:     const char *start,
        !           870:     const char *stop,
        !           871:     sopno startst,
        !           872:     sopno stopst)
1.1       jtc       873: {
1.8       perry     874:        states st = m->st;
                    875:        states empty = m->empty;
                    876:        states tmp = m->tmp;
1.19      yamt      877:        const char *p = start;
1.17      enami     878:        int c = (start == m->beginp) ? OUT : *(start-1);
1.8       perry     879:        int lastc;      /* previous c */
                    880:        int flagch;
                    881:        int i;
1.19      yamt      882:        const char *matchp;     /* last p at which a match ended */
1.1       jtc       883:
1.12      lukem     884:        _DIAGASSERT(m != NULL);
                    885:        _DIAGASSERT(start != NULL);
                    886:        _DIAGASSERT(stop != NULL);
                    887:
1.1       jtc       888:        AT("slow", start, stop, startst, stopst);
                    889:        CLEAR(st);
                    890:        SET1(st, startst);
                    891:        SP("sstart", st, *p);
                    892:        st = step(m->g, startst, stopst, st, NOTHING, st);
                    893:        matchp = NULL;
                    894:        for (;;) {
                    895:                /* next character */
                    896:                lastc = c;
1.17      enami     897:                c = (p == m->endp) ? OUT : *p;
1.1       jtc       898:
                    899:                /* is there an EOL and/or BOL between lastc and c? */
                    900:                flagch = '\0';
                    901:                i = 0;
                    902:                if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
                    903:                                (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
                    904:                        flagch = BOL;
                    905:                        i = m->g->nbol;
                    906:                }
                    907:                if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
                    908:                                (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
                    909:                        flagch = (flagch == BOL) ? BOLEOL : EOL;
                    910:                        i += m->g->neol;
                    911:                }
                    912:                if (i != 0) {
                    913:                        for (; i > 0; i--)
                    914:                                st = step(m->g, startst, stopst, st, flagch, st);
                    915:                        SP("sboleol", st, c);
                    916:                }
                    917:
                    918:                /* how about a word boundary? */
1.3       jtc       919:                if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
                    920:                                        (c != OUT && ISWORD(c)) ) {
1.1       jtc       921:                        flagch = BOW;
                    922:                }
1.3       jtc       923:                if ( (lastc != OUT && ISWORD(lastc)) &&
                    924:                                (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
1.1       jtc       925:                        flagch = EOW;
                    926:                }
                    927:                if (flagch == BOW || flagch == EOW) {
                    928:                        st = step(m->g, startst, stopst, st, flagch, st);
                    929:                        SP("sboweow", st, c);
                    930:                }
                    931:
                    932:                /* are we done? */
                    933:                if (ISSET(st, stopst))
                    934:                        matchp = p;
                    935:                if (EQ(st, empty) || p == stop)
                    936:                        break;          /* NOTE BREAK OUT */
                    937:
                    938:                /* no, we must deal with this character */
                    939:                ASSIGN(tmp, st);
                    940:                ASSIGN(st, empty);
                    941:                assert(c != OUT);
                    942:                st = step(m->g, startst, stopst, tmp, c, st);
                    943:                SP("saft", st, c);
                    944:                assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
                    945:                p++;
                    946:        }
                    947:
                    948:        return(matchp);
                    949: }
                    950:
                    951:
                    952: /*
                    953:  - step - map set of states reachable before char to set reachable after
1.8       perry     954:  == static states step(struct re_guts *g, sopno start, sopno stop, \
                    955:  ==    states bef, int ch, states aft);
1.1       jtc       956:  == #define    BOL     (OUT+1)
                    957:  == #define    EOL     (BOL+1)
                    958:  == #define    BOLEOL  (BOL+2)
                    959:  == #define    NOTHING (BOL+3)
                    960:  == #define    BOW     (BOL+4)
                    961:  == #define    EOW     (BOL+5)
                    962:  == #define    CODEMAX (BOL+5)         // highest code used
                    963:  == #define    NONCHAR(c)      ((c) > CHAR_MAX)
                    964:  == #define    NNONCHAR        (CODEMAX-CHAR_MAX)
                    965:  */
                    966: static states
1.21    ! junyoung  967: step(
        !           968:     struct re_guts *g,
        !           969:     sopno start,               /* start state within strip */
        !           970:     sopno stop,                        /* state after stop state within strip */
        !           971:     states bef,                        /* states reachable before */
        !           972:     int ch,                    /* character or NONCHAR code */
        !           973:     states aft)                        /* states already known reachable after */
1.1       jtc       974: {
1.8       perry     975:        cset *cs;
                    976:        sop s;
                    977:        sopno pc;
                    978:        onestate here;          /* note, macros know this name */
                    979:        sopno look;
                    980:        int i;
1.1       jtc       981:
1.12      lukem     982:        _DIAGASSERT(g != NULL);
                    983:
1.1       jtc       984:        for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
                    985:                s = g->strip[pc];
                    986:                switch (OP(s)) {
                    987:                case OEND:
                    988:                        assert(pc == stop-1);
                    989:                        break;
                    990:                case OCHAR:
                    991:                        /* only characters can match */
                    992:                        assert(!NONCHAR(ch) || ch != (char)OPND(s));
                    993:                        if (ch == (char)OPND(s))
                    994:                                FWD(aft, bef, 1);
                    995:                        break;
                    996:                case OBOL:
                    997:                        if (ch == BOL || ch == BOLEOL)
                    998:                                FWD(aft, bef, 1);
                    999:                        break;
                   1000:                case OEOL:
                   1001:                        if (ch == EOL || ch == BOLEOL)
                   1002:                                FWD(aft, bef, 1);
                   1003:                        break;
                   1004:                case OBOW:
                   1005:                        if (ch == BOW)
                   1006:                                FWD(aft, bef, 1);
                   1007:                        break;
                   1008:                case OEOW:
                   1009:                        if (ch == EOW)
                   1010:                                FWD(aft, bef, 1);
                   1011:                        break;
                   1012:                case OANY:
                   1013:                        if (!NONCHAR(ch))
                   1014:                                FWD(aft, bef, 1);
                   1015:                        break;
                   1016:                case OANYOF:
                   1017:                        cs = &g->sets[OPND(s)];
                   1018:                        if (!NONCHAR(ch) && CHIN(cs, ch))
                   1019:                                FWD(aft, bef, 1);
                   1020:                        break;
                   1021:                case OBACK_:            /* ignored here */
                   1022:                case O_BACK:
                   1023:                        FWD(aft, aft, 1);
                   1024:                        break;
                   1025:                case OPLUS_:            /* forward, this is just an empty */
                   1026:                        FWD(aft, aft, 1);
                   1027:                        break;
                   1028:                case O_PLUS:            /* both forward and back */
                   1029:                        FWD(aft, aft, 1);
                   1030:                        i = ISSETBACK(aft, OPND(s));
                   1031:                        BACK(aft, aft, OPND(s));
                   1032:                        if (!i && ISSETBACK(aft, OPND(s))) {
                   1033:                                /* oho, must reconsider loop body */
                   1034:                                pc -= OPND(s) + 1;
                   1035:                                INIT(here, pc);
                   1036:                        }
                   1037:                        break;
                   1038:                case OQUEST_:           /* two branches, both forward */
                   1039:                        FWD(aft, aft, 1);
                   1040:                        FWD(aft, aft, OPND(s));
                   1041:                        break;
                   1042:                case O_QUEST:           /* just an empty */
                   1043:                        FWD(aft, aft, 1);
                   1044:                        break;
                   1045:                case OLPAREN:           /* not significant here */
                   1046:                case ORPAREN:
                   1047:                        FWD(aft, aft, 1);
                   1048:                        break;
                   1049:                case OCH_:              /* mark the first two branches */
                   1050:                        FWD(aft, aft, 1);
                   1051:                        assert(OP(g->strip[pc+OPND(s)]) == OOR2);
                   1052:                        FWD(aft, aft, OPND(s));
                   1053:                        break;
                   1054:                case OOR1:              /* done a branch, find the O_CH */
                   1055:                        if (ISSTATEIN(aft, here)) {
                   1056:                                for (look = 1;
                   1057:                                                OP(s = g->strip[pc+look]) != O_CH;
                   1058:                                                look += OPND(s))
                   1059:                                        assert(OP(s) == OOR2);
                   1060:                                FWD(aft, aft, look);
                   1061:                        }
                   1062:                        break;
                   1063:                case OOR2:              /* propagate OCH_'s marking */
                   1064:                        FWD(aft, aft, 1);
                   1065:                        if (OP(g->strip[pc+OPND(s)]) != O_CH) {
                   1066:                                assert(OP(g->strip[pc+OPND(s)]) == OOR2);
                   1067:                                FWD(aft, aft, OPND(s));
                   1068:                        }
                   1069:                        break;
                   1070:                case O_CH:              /* just empty */
                   1071:                        FWD(aft, aft, 1);
                   1072:                        break;
                   1073:                default:                /* ooooops... */
                   1074:                        assert(nope);
                   1075:                        break;
                   1076:                }
                   1077:        }
                   1078:
                   1079:        return(aft);
                   1080: }
                   1081:
                   1082: #ifdef REDEBUG
                   1083: /*
                   1084:  - print - print a set of states
                   1085:  == #ifdef REDEBUG
                   1086:  == static void print(struct match *m, char *caption, states st, \
                   1087:  ==    int ch, FILE *d);
                   1088:  == #endif
                   1089:  */
                   1090: static void
1.21    ! junyoung 1091: print(
        !          1092:     struct match *m,
        !          1093:     char *caption,
        !          1094:     states st,
        !          1095:     int ch,
        !          1096:     FILE *d)
1.1       jtc      1097: {
1.8       perry    1098:        struct re_guts *g = m->g;
                   1099:        int i;
                   1100:        int first = 1;
1.1       jtc      1101:
1.12      lukem    1102:        _DIAGASSERT(m != NULL);
                   1103:        _DIAGASSERT(caption != NULL);
                   1104:
1.1       jtc      1105:        if (!(m->eflags&REG_TRACE))
                   1106:                return;
                   1107:
1.12      lukem    1108:        _DIAGASSERT(d != NULL);
                   1109:
1.1       jtc      1110:        fprintf(d, "%s", caption);
                   1111:        if (ch != '\0')
                   1112:                fprintf(d, " %s", pchar(ch));
                   1113:        for (i = 0; i < g->nstates; i++)
                   1114:                if (ISSET(st, i)) {
                   1115:                        fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
                   1116:                        first = 0;
                   1117:                }
                   1118:        fprintf(d, "\n");
                   1119: }
                   1120:
                   1121: /*
                   1122:  - at - print current situation
                   1123:  == #ifdef REDEBUG
                   1124:  == static void at(struct match *m, char *title, char *start, char *stop, \
                   1125:  ==                                            sopno startst, sopno stopst);
                   1126:  == #endif
                   1127:  */
                   1128: static void
1.21    ! junyoung 1129: at(
        !          1130:     struct match *m,
        !          1131:     char *title,
        !          1132:     char *start,
        !          1133:     char *stop,
        !          1134:     sopno startst,
        !          1135:     sopno stopst)
1.1       jtc      1136: {
1.12      lukem    1137:
                   1138:        _DIAGASSERT(m != NULL);
                   1139:        _DIAGASSERT(title != NULL);
                   1140:        _DIAGASSERT(start != NULL);
                   1141:        _DIAGASSERT(stop != NULL);
                   1142:
1.1       jtc      1143:        if (!(m->eflags&REG_TRACE))
                   1144:                return;
                   1145:
                   1146:        printf("%s %s-", title, pchar(*start));
                   1147:        printf("%s ", pchar(*stop));
                   1148:        printf("%ld-%ld\n", (long)startst, (long)stopst);
                   1149: }
                   1150:
                   1151: #ifndef PCHARDONE
                   1152: #define        PCHARDONE       /* never again */
                   1153: /*
                   1154:  - pchar - make a character printable
                   1155:  == #ifdef REDEBUG
                   1156:  == static char *pchar(int ch);
                   1157:  == #endif
                   1158:  *
                   1159:  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
                   1160:  * duplicate here avoids having a debugging-capable regexec.o tied to
                   1161:  * a matching debug.o, and this is convenient.  It all disappears in
                   1162:  * the non-debug compilation anyway, so it doesn't matter much.
                   1163:  */
                   1164: static char *                  /* -> representation */
1.21    ! junyoung 1165: pchar(
        !          1166:     int ch)
1.1       jtc      1167: {
                   1168:        static char pbuf[10];
                   1169:
                   1170:        if (isprint(ch) || ch == ' ')
1.6       mrg      1171:                (void)snprintf(pbuf, sizeof pbuf, "%c", ch);
1.1       jtc      1172:        else
1.6       mrg      1173:                (void)snprintf(pbuf, sizeof pbuf, "\\%o", ch);
1.1       jtc      1174:        return(pbuf);
                   1175: }
                   1176: #endif
                   1177: #endif
                   1178:
                   1179: #undef matcher
                   1180: #undef fast
                   1181: #undef slow
                   1182: #undef dissect
                   1183: #undef backref
                   1184: #undef step
                   1185: #undef print
                   1186: #undef at
                   1187: #undef match
1.14      christos 1188: #undef nope

CVSweb <webmaster@jp.NetBSD.org>