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

Annotation of src/lib/libc/regex/regcomp.c, Revision 1.28

1.28    ! junyoung    1: /*     $NetBSD: regcomp.c,v 1.27 2007/02/08 05:44:18 junyoung Exp $    */
1.6       cgd         2:
1.5       cgd         3: /*-
                      4:  * Copyright (c) 1992, 1993, 1994
                      5:  *     The Regents of the University of California.  All rights reserved.
                      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.
1.18      agc        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:  *     @(#)regcomp.c   8.5 (Berkeley) 3/20/94
                     35:  */
                     36:
                     37: /*-
                     38:  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
                     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.
1.5       cgd        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:  *     @(#)regcomp.c   8.5 (Berkeley) 3/20/94
                     72:  */
                     73:
1.7       christos   74: #include <sys/cdefs.h>
1.5       cgd        75: #if defined(LIBC_SCCS) && !defined(lint)
1.6       cgd        76: #if 0
1.5       cgd        77: static char sccsid[] = "@(#)regcomp.c  8.5 (Berkeley) 3/20/94";
1.6       cgd        78: #else
1.28    ! junyoung   79: __RCSID("$NetBSD: regcomp.c,v 1.27 2007/02/08 05:44:18 junyoung Exp $");
1.6       cgd        80: #endif
1.5       cgd        81: #endif /* LIBC_SCCS and not lint */
                     82:
1.8       jtc        83: #include "namespace.h"
1.1       jtc        84: #include <sys/types.h>
1.14      lukem      85:
                     86: #include <assert.h>
1.1       jtc        87: #include <ctype.h>
                     88: #include <limits.h>
1.14      lukem      89: #include <stdio.h>
1.1       jtc        90: #include <stdlib.h>
1.14      lukem      91: #include <string.h>
1.28    ! junyoung   92: #include <regex.h>
1.8       jtc        93:
                     94: #ifdef __weak_alias
1.16      mycroft    95: __weak_alias(regcomp,_regcomp)
1.8       jtc        96: #endif
1.1       jtc        97:
                     98: #include "utils.h"
                     99: #include "regex2.h"
                    100:
                    101: #include "cclass.h"
                    102: #include "cname.h"
                    103:
                    104: /*
                    105:  * parse structure, passed up and down to avoid global variables and
                    106:  * other clumsinesses
                    107:  */
                    108: struct parse {
1.21      yamt      109:        const char *next;       /* next character in RE */
                    110:        const char *end;        /* end of string (-> NUL normally) */
1.1       jtc       111:        int error;              /* has an error been seen? */
                    112:        sop *strip;             /* malloced strip */
                    113:        sopno ssize;            /* malloced strip size (allocated) */
                    114:        sopno slen;             /* malloced strip length (used) */
                    115:        int ncsalloc;           /* number of csets allocated */
                    116:        struct re_guts *g;
                    117: #      define  NPAREN  10      /* we need to remember () 1-9 for back refs */
                    118:        sopno pbegin[NPAREN];   /* -> ( ([0] unused) */
                    119:        sopno pend[NPAREN];     /* -> ) ([0] unused) */
                    120: };
                    121:
1.5       cgd       122: /* ========= begin header generated by ./mkh ========= */
                    123: #ifdef __cplusplus
                    124: extern "C" {
                    125: #endif
                    126:
                    127: /* === regcomp.c === */
1.26      junyoung  128: static void p_ere(struct parse *p, int stop);
                    129: static void p_ere_exp(struct parse *p);
                    130: static void p_str(struct parse *p);
                    131: static void p_bre(struct parse *p, int end1, int end2);
                    132: static int p_simp_re(struct parse *p, int starordinary);
                    133: static int p_count(struct parse *p);
                    134: static void p_bracket(struct parse *p);
                    135: static void p_b_term(struct parse *p, cset *cs);
                    136: static void p_b_cclass(struct parse *p, cset *cs);
                    137: static void p_b_eclass(struct parse *p, cset *cs);
                    138: static char p_b_symbol(struct parse *p);
                    139: static char p_b_coll_elem(struct parse *p, int endc);
                    140: static int othercase(int ch);
                    141: static void bothcases(struct parse *p, int ch);
                    142: static void ordinary(struct parse *p, int ch);
                    143: static void nonnewline(struct parse *p);
                    144: static void repeat(struct parse *p, sopno start, int from, int to);
                    145: static int seterr(struct parse *p, int e);
                    146: static cset *allocset(struct parse *p);
                    147: static void freeset(struct parse *p, cset *cs);
                    148: static int freezeset(struct parse *p, cset *cs);
                    149: static int firstch(struct parse *p, cset *cs);
                    150: static int nch(struct parse *p, cset *cs);
                    151: static void mcadd(struct parse *p, cset *cs, const char *cp);
1.7       christos  152: #if 0
1.26      junyoung  153: static void mcsub(cset *cs, char *cp);
                    154: static int mcin(cset *cs, char *cp);
                    155: static char *mcfind(cset *cs, char *cp);
1.7       christos  156: #endif
1.26      junyoung  157: static void mcinvert(struct parse *p, cset *cs);
                    158: static void mccase(struct parse *p, cset *cs);
                    159: static int isinsets(struct re_guts *g, int c);
                    160: static int samesets(struct re_guts *g, int c1, int c2);
                    161: static void categorize(struct parse *p, struct re_guts *g);
                    162: static sopno dupl(struct parse *p, sopno start, sopno finish);
                    163: static void doemit(struct parse *p, sop op, sopno opnd);
                    164: static void doinsert(struct parse *p, sop op, sopno opnd, sopno pos);
                    165: static void dofwd(struct parse *p, sopno pos, sopno value);
                    166: static void enlarge(struct parse *p, sopno size);
                    167: static void stripsnug(struct parse *p, struct re_guts *g);
                    168: static void findmust(struct parse *p, struct re_guts *g);
                    169: static sopno pluscount(struct parse *p, struct re_guts *g);
1.5       cgd       170:
                    171: #ifdef __cplusplus
                    172: }
                    173: #endif
                    174: /* ========= end header generated by ./mkh ========= */
1.1       jtc       175:
                    176: static char nuls[10];          /* place to point scanner in event of error */
                    177:
                    178: /*
                    179:  * macros for use with parse structure
                    180:  * BEWARE:  these know that the parse structure is named `p' !!!
                    181:  */
                    182: #define        PEEK()  (*p->next)
                    183: #define        PEEK2() (*(p->next+1))
                    184: #define        MORE()  (p->next < p->end)
                    185: #define        MORE2() (p->next+1 < p->end)
                    186: #define        SEE(c)  (MORE() && PEEK() == (c))
                    187: #define        SEETWO(a, b)    (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
                    188: #define        EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)
                    189: #define        EATTWO(a, b)    ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
                    190: #define        NEXT()  (p->next++)
                    191: #define        NEXT2() (p->next += 2)
                    192: #define        NEXTn(n)        (p->next += (n))
                    193: #define        GETNEXT()       (*p->next++)
                    194: #define        SETERROR(e)     seterr(p, (e))
1.7       christos  195: #define        REQUIRE(co, e)  (void) ((co) || SETERROR(e))
1.1       jtc       196: #define        MUSTSEE(c, e)   (REQUIRE(MORE() && PEEK() == (c), e))
1.7       christos  197: #define        MUSTEAT(c, e)   (void) (REQUIRE(MORE() && GETNEXT() == (c), e))
1.1       jtc       198: #define        MUSTNOTSEE(c, e)        (REQUIRE(!MORE() || PEEK() != (c), e))
1.12      drochner  199: #define        EMIT(op, sopnd) doemit(p, (sop)(op), sopnd)
                    200: #define        INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
                    201: #define        AHEAD(pos)              dofwd(p, pos, HERE()-(pos))
1.1       jtc       202: #define        ASTERN(sop, pos)        EMIT(sop, HERE()-pos)
                    203: #define        HERE()          (p->slen)
                    204: #define        THERE()         (p->slen - 1)
1.4       jtc       205: #define        THERETHERE()    (p->slen - 2)
1.1       jtc       206: #define        DROP(n) (p->slen -= (n))
                    207:
                    208: #ifndef NDEBUG
                    209: static int never = 0;          /* for use in asserts; shuts lint up */
1.3       jtc       210: #else
                    211: #define        never   0               /* some <assert.h>s have bugs too */
1.1       jtc       212: #endif
                    213:
                    214: /*
                    215:  - regcomp - interface for parser and compilation
1.2       jtc       216:  = extern int regcomp(regex_t *, const char *, int);
1.1       jtc       217:  = #define     REG_BASIC       0000
                    218:  = #define     REG_EXTENDED    0001
                    219:  = #define     REG_ICASE       0002
                    220:  = #define     REG_NOSUB       0004
                    221:  = #define     REG_NEWLINE     0010
                    222:  = #define     REG_NOSPEC      0020
                    223:  = #define     REG_PEND        0040
                    224:  = #define     REG_DUMP        0200
                    225:  */
                    226: int                            /* 0 success, otherwise REG_something */
1.27      junyoung  227: regcomp(
                    228:     regex_t *preg,
                    229:     const char *pattern,
                    230:     int cflags)
1.1       jtc       231: {
                    232:        struct parse pa;
1.9       perry     233:        struct re_guts *g;
                    234:        struct parse *p = &pa;
                    235:        int i;
                    236:        size_t len;
1.3       jtc       237: #ifdef REDEBUG
                    238: #      define  GOODFLAGS(f)    (f)
                    239: #else
                    240: #      define  GOODFLAGS(f)    ((f)&~REG_DUMP)
                    241: #endif
1.1       jtc       242:
1.14      lukem     243:        _DIAGASSERT(preg != NULL);
                    244:        _DIAGASSERT(pattern != NULL);
                    245:
1.3       jtc       246:        cflags = GOODFLAGS(cflags);
1.1       jtc       247:        if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
                    248:                return(REG_INVARG);
                    249:
                    250:        if (cflags&REG_PEND) {
                    251:                if (preg->re_endp < pattern)
                    252:                        return(REG_INVARG);
                    253:                len = preg->re_endp - pattern;
                    254:        } else
1.11      christos  255:                len = strlen(pattern);
1.1       jtc       256:
                    257:        /* do the mallocs early so failure handling is easy */
                    258:        g = (struct re_guts *)malloc(sizeof(struct re_guts) +
                    259:                                                        (NC-1)*sizeof(cat_t));
                    260:        if (g == NULL)
                    261:                return(REG_ESPACE);
                    262:        p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
                    263:        p->strip = (sop *)malloc(p->ssize * sizeof(sop));
                    264:        p->slen = 0;
                    265:        if (p->strip == NULL) {
1.11      christos  266:                free(g);
1.1       jtc       267:                return(REG_ESPACE);
                    268:        }
                    269:
                    270:        /* set things up */
                    271:        p->g = g;
1.21      yamt      272:        p->next = pattern;
1.1       jtc       273:        p->end = p->next + len;
                    274:        p->error = 0;
                    275:        p->ncsalloc = 0;
                    276:        for (i = 0; i < NPAREN; i++) {
                    277:                p->pbegin[i] = 0;
                    278:                p->pend[i] = 0;
                    279:        }
                    280:        g->csetsize = NC;
                    281:        g->sets = NULL;
                    282:        g->setbits = NULL;
                    283:        g->ncsets = 0;
                    284:        g->cflags = cflags;
                    285:        g->iflags = 0;
                    286:        g->nbol = 0;
                    287:        g->neol = 0;
                    288:        g->must = NULL;
                    289:        g->mlen = 0;
                    290:        g->nsub = 0;
                    291:        g->ncategories = 1;     /* category 0 is "everything else" */
                    292:        g->categories = &g->catspace[-(CHAR_MIN)];
                    293:        (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
                    294:        g->backrefs = 0;
                    295:
                    296:        /* do it */
                    297:        EMIT(OEND, 0);
                    298:        g->firststate = THERE();
                    299:        if (cflags&REG_EXTENDED)
                    300:                p_ere(p, OUT);
                    301:        else if (cflags&REG_NOSPEC)
                    302:                p_str(p);
                    303:        else
                    304:                p_bre(p, OUT, OUT);
                    305:        EMIT(OEND, 0);
                    306:        g->laststate = THERE();
                    307:
                    308:        /* tidy up loose ends and fill things in */
                    309:        categorize(p, g);
                    310:        stripsnug(p, g);
                    311:        findmust(p, g);
                    312:        g->nplus = pluscount(p, g);
                    313:        g->magic = MAGIC2;
                    314:        preg->re_nsub = g->nsub;
                    315:        preg->re_g = g;
                    316:        preg->re_magic = MAGIC1;
                    317: #ifndef REDEBUG
                    318:        /* not debugging, so can't rely on the assert() in regexec() */
                    319:        if (g->iflags&BAD)
                    320:                SETERROR(REG_ASSERT);
                    321: #endif
                    322:
                    323:        /* win or lose, we're done */
                    324:        if (p->error != 0)      /* lose */
                    325:                regfree(preg);
                    326:        return(p->error);
                    327: }
                    328:
                    329: /*
                    330:  - p_ere - ERE parser top level, concatenation and alternation
1.9       perry     331:  == static void p_ere(struct parse *p, int stop);
1.1       jtc       332:  */
                    333: static void
1.27      junyoung  334: p_ere(
                    335:     struct parse *p,
                    336:     int stop)                  /* character this ERE should end at */
1.1       jtc       337: {
1.9       perry     338:        char c;
                    339:        sopno prevback = 0;     /* pacify gcc */
                    340:        sopno prevfwd = 0;      /* pacify gcc */
                    341:        sopno conc;
                    342:        int first = 1;          /* is this the first alternative? */
1.1       jtc       343:
1.14      lukem     344:        _DIAGASSERT(p != NULL);
                    345:
1.1       jtc       346:        for (;;) {
                    347:                /* do a bunch of concatenated expressions */
                    348:                conc = HERE();
                    349:                while (MORE() && (c = PEEK()) != '|' && c != stop)
                    350:                        p_ere_exp(p);
                    351:                REQUIRE(HERE() != conc, REG_EMPTY);     /* require nonempty */
                    352:
                    353:                if (!EAT('|'))
                    354:                        break;          /* NOTE BREAK OUT */
                    355:
                    356:                if (first) {
                    357:                        INSERT(OCH_, conc);     /* offset is wrong */
                    358:                        prevfwd = conc;
                    359:                        prevback = conc;
                    360:                        first = 0;
                    361:                }
                    362:                ASTERN(OOR1, prevback);
                    363:                prevback = THERE();
                    364:                AHEAD(prevfwd);                 /* fix previous offset */
                    365:                prevfwd = HERE();
                    366:                EMIT(OOR2, 0);                  /* offset is very wrong */
                    367:        }
                    368:
                    369:        if (!first) {           /* tail-end fixups */
                    370:                AHEAD(prevfwd);
                    371:                ASTERN(O_CH, prevback);
                    372:        }
                    373:
                    374:        assert(!MORE() || SEE(stop));
                    375: }
                    376:
                    377: /*
                    378:  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
1.9       perry     379:  == static void p_ere_exp(struct parse *p);
1.1       jtc       380:  */
                    381: static void
1.27      junyoung  382: p_ere_exp(
                    383:     struct parse *p)
1.1       jtc       384: {
1.9       perry     385:        char c;
                    386:        sopno pos;
                    387:        int count;
                    388:        int count2;
                    389:        sopno subno;
1.1       jtc       390:        int wascaret = 0;
                    391:
1.14      lukem     392:        _DIAGASSERT(p != NULL);
                    393:
1.1       jtc       394:        assert(MORE());         /* caller should have ensured this */
                    395:        c = GETNEXT();
                    396:
                    397:        pos = HERE();
                    398:        switch (c) {
                    399:        case '(':
                    400:                REQUIRE(MORE(), REG_EPAREN);
                    401:                p->g->nsub++;
                    402:                subno = p->g->nsub;
                    403:                if (subno < NPAREN)
                    404:                        p->pbegin[subno] = HERE();
                    405:                EMIT(OLPAREN, subno);
                    406:                if (!SEE(')'))
                    407:                        p_ere(p, ')');
                    408:                if (subno < NPAREN) {
                    409:                        p->pend[subno] = HERE();
                    410:                        assert(p->pend[subno] != 0);
                    411:                }
                    412:                EMIT(ORPAREN, subno);
                    413:                MUSTEAT(')', REG_EPAREN);
                    414:                break;
                    415: #ifndef POSIX_MISTAKE
                    416:        case ')':               /* happens only if no current unmatched ( */
                    417:                /*
                    418:                 * You may ask, why the ifndef?  Because I didn't notice
                    419:                 * this until slightly too late for 1003.2, and none of the
                    420:                 * other 1003.2 regular-expression reviewers noticed it at
                    421:                 * all.  So an unmatched ) is legal POSIX, at least until
                    422:                 * we can get it fixed.
                    423:                 */
                    424:                SETERROR(REG_EPAREN);
                    425:                break;
                    426: #endif
                    427:        case '^':
                    428:                EMIT(OBOL, 0);
                    429:                p->g->iflags |= USEBOL;
                    430:                p->g->nbol++;
                    431:                wascaret = 1;
                    432:                break;
                    433:        case '$':
                    434:                EMIT(OEOL, 0);
                    435:                p->g->iflags |= USEEOL;
                    436:                p->g->neol++;
                    437:                break;
                    438:        case '|':
                    439:                SETERROR(REG_EMPTY);
                    440:                break;
                    441:        case '*':
                    442:        case '+':
                    443:        case '?':
                    444:                SETERROR(REG_BADRPT);
                    445:                break;
                    446:        case '.':
                    447:                if (p->g->cflags&REG_NEWLINE)
                    448:                        nonnewline(p);
                    449:                else
                    450:                        EMIT(OANY, 0);
                    451:                break;
                    452:        case '[':
                    453:                p_bracket(p);
                    454:                break;
                    455:        case '\\':
                    456:                REQUIRE(MORE(), REG_EESCAPE);
                    457:                c = GETNEXT();
                    458:                ordinary(p, c);
                    459:                break;
                    460:        case '{':               /* okay as ordinary except if digit follows */
1.17      itohy     461:                REQUIRE(!MORE() || !isdigit((unsigned char)PEEK()), REG_BADRPT);
1.1       jtc       462:                /* FALLTHROUGH */
                    463:        default:
                    464:                ordinary(p, c);
                    465:                break;
                    466:        }
                    467:
                    468:        if (!MORE())
                    469:                return;
                    470:        c = PEEK();
                    471:        /* we call { a repetition if followed by a digit */
                    472:        if (!( c == '*' || c == '+' || c == '?' ||
1.17      itohy     473:            (c == '{' && MORE2() && isdigit((unsigned char)PEEK2())) ))
1.1       jtc       474:                return;         /* no repetition, we're done */
                    475:        NEXT();
                    476:
                    477:        REQUIRE(!wascaret, REG_BADRPT);
                    478:        switch (c) {
                    479:        case '*':       /* implemented as +? */
1.4       jtc       480:                /* this case does not require the (y|) trick, noKLUDGE */
1.1       jtc       481:                INSERT(OPLUS_, pos);
                    482:                ASTERN(O_PLUS, pos);
                    483:                INSERT(OQUEST_, pos);
                    484:                ASTERN(O_QUEST, pos);
                    485:                break;
                    486:        case '+':
                    487:                INSERT(OPLUS_, pos);
                    488:                ASTERN(O_PLUS, pos);
                    489:                break;
                    490:        case '?':
1.4       jtc       491:                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
                    492:                INSERT(OCH_, pos);              /* offset slightly wrong */
                    493:                ASTERN(OOR1, pos);              /* this one's right */
                    494:                AHEAD(pos);                     /* fix the OCH_ */
                    495:                EMIT(OOR2, 0);                  /* offset very wrong... */
                    496:                AHEAD(THERE());                 /* ...so fix it */
                    497:                ASTERN(O_CH, THERETHERE());
1.1       jtc       498:                break;
                    499:        case '{':
                    500:                count = p_count(p);
                    501:                if (EAT(',')) {
1.17      itohy     502:                        if (isdigit((unsigned char)PEEK())) {
1.1       jtc       503:                                count2 = p_count(p);
                    504:                                REQUIRE(count <= count2, REG_BADBR);
                    505:                        } else          /* single number with comma */
                    506:                                count2 = INFINITY;
                    507:                } else          /* just a single number */
                    508:                        count2 = count;
                    509:                repeat(p, pos, count, count2);
                    510:                if (!EAT('}')) {        /* error heuristics */
                    511:                        while (MORE() && PEEK() != '}')
                    512:                                NEXT();
                    513:                        REQUIRE(MORE(), REG_EBRACE);
                    514:                        SETERROR(REG_BADBR);
                    515:                }
                    516:                break;
                    517:        }
                    518:
                    519:        if (!MORE())
                    520:                return;
                    521:        c = PEEK();
                    522:        if (!( c == '*' || c == '+' || c == '?' ||
1.17      itohy     523:            (c == '{' && MORE2() && isdigit((unsigned char)PEEK2())) ) )
1.1       jtc       524:                return;
                    525:        SETERROR(REG_BADRPT);
                    526: }
                    527:
                    528: /*
                    529:  - p_str - string (no metacharacters) "parser"
1.9       perry     530:  == static void p_str(struct parse *p);
1.1       jtc       531:  */
                    532: static void
1.27      junyoung  533: p_str(
                    534:     struct parse *p)
1.1       jtc       535: {
1.14      lukem     536:
                    537:        _DIAGASSERT(p != NULL);
                    538:
1.1       jtc       539:        REQUIRE(MORE(), REG_EMPTY);
                    540:        while (MORE())
                    541:                ordinary(p, GETNEXT());
                    542: }
                    543:
                    544: /*
                    545:  - p_bre - BRE parser top level, anchoring and concatenation
1.9       perry     546:  == static void p_bre(struct parse *p, int end1, \
                    547:  ==    int end2);
1.1       jtc       548:  * Giving end1 as OUT essentially eliminates the end1/end2 check.
                    549:  *
                    550:  * This implementation is a bit of a kludge, in that a trailing $ is first
                    551:  * taken as an ordinary character and then revised to be an anchor.  The
                    552:  * only undesirable side effect is that '$' gets included as a character
                    553:  * category in such cases.  This is fairly harmless; not worth fixing.
                    554:  * The amount of lookahead needed to avoid this kludge is excessive.
                    555:  */
                    556: static void
1.27      junyoung  557: p_bre(
                    558:     struct parse *p,
                    559:     int end1,          /* first terminating character */
                    560:     int end2)          /* second terminating character */
1.9       perry     561: {
1.14      lukem     562:        sopno start;
1.9       perry     563:        int first = 1;                  /* first subexpression? */
                    564:        int wasdollar = 0;
1.1       jtc       565:
1.14      lukem     566:        _DIAGASSERT(p != NULL);
                    567:
                    568:        start = HERE();
                    569:
1.1       jtc       570:        if (EAT('^')) {
                    571:                EMIT(OBOL, 0);
                    572:                p->g->iflags |= USEBOL;
                    573:                p->g->nbol++;
                    574:        }
                    575:        while (MORE() && !SEETWO(end1, end2)) {
                    576:                wasdollar = p_simp_re(p, first);
                    577:                first = 0;
                    578:        }
                    579:        if (wasdollar) {        /* oops, that was a trailing anchor */
                    580:                DROP(1);
                    581:                EMIT(OEOL, 0);
                    582:                p->g->iflags |= USEEOL;
                    583:                p->g->neol++;
                    584:        }
                    585:
                    586:        REQUIRE(HERE() != start, REG_EMPTY);    /* require nonempty */
                    587: }
                    588:
                    589: /*
                    590:  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
1.9       perry     591:  == static int p_simp_re(struct parse *p, int starordinary);
1.1       jtc       592:  */
                    593: static int                     /* was the simple RE an unbackslashed $? */
1.27      junyoung  594: p_simp_re(
                    595:     struct parse *p,
                    596:     int starordinary)          /* is a leading * an ordinary character? */
1.1       jtc       597: {
1.9       perry     598:        int c;
                    599:        int count;
                    600:        int count2;
                    601:        sopno pos;
                    602:        int i;
                    603:        sopno subno;
1.1       jtc       604: #      define  BACKSL  (1<<CHAR_BIT)
                    605:
1.14      lukem     606:        _DIAGASSERT(p != NULL);
                    607:
1.1       jtc       608:        pos = HERE();           /* repetion op, if any, covers from here */
                    609:
                    610:        assert(MORE());         /* caller should have ensured this */
                    611:        c = GETNEXT();
                    612:        if (c == '\\') {
                    613:                REQUIRE(MORE(), REG_EESCAPE);
                    614:                c = BACKSL | (unsigned char)GETNEXT();
                    615:        }
                    616:        switch (c) {
                    617:        case '.':
                    618:                if (p->g->cflags&REG_NEWLINE)
                    619:                        nonnewline(p);
                    620:                else
                    621:                        EMIT(OANY, 0);
                    622:                break;
                    623:        case '[':
                    624:                p_bracket(p);
                    625:                break;
                    626:        case BACKSL|'{':
                    627:                SETERROR(REG_BADRPT);
                    628:                break;
                    629:        case BACKSL|'(':
                    630:                p->g->nsub++;
                    631:                subno = p->g->nsub;
                    632:                if (subno < NPAREN)
                    633:                        p->pbegin[subno] = HERE();
                    634:                EMIT(OLPAREN, subno);
                    635:                /* the MORE here is an error heuristic */
                    636:                if (MORE() && !SEETWO('\\', ')'))
                    637:                        p_bre(p, '\\', ')');
                    638:                if (subno < NPAREN) {
                    639:                        p->pend[subno] = HERE();
                    640:                        assert(p->pend[subno] != 0);
                    641:                }
                    642:                EMIT(ORPAREN, subno);
                    643:                REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
                    644:                break;
                    645:        case BACKSL|')':        /* should not get here -- must be user */
                    646:        case BACKSL|'}':
                    647:                SETERROR(REG_EPAREN);
                    648:                break;
                    649:        case BACKSL|'1':
                    650:        case BACKSL|'2':
                    651:        case BACKSL|'3':
                    652:        case BACKSL|'4':
                    653:        case BACKSL|'5':
                    654:        case BACKSL|'6':
                    655:        case BACKSL|'7':
                    656:        case BACKSL|'8':
                    657:        case BACKSL|'9':
                    658:                i = (c&~BACKSL) - '0';
                    659:                assert(i < NPAREN);
                    660:                if (p->pend[i] != 0) {
                    661:                        assert(i <= p->g->nsub);
                    662:                        EMIT(OBACK_, i);
                    663:                        assert(p->pbegin[i] != 0);
                    664:                        assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
                    665:                        assert(OP(p->strip[p->pend[i]]) == ORPAREN);
                    666:                        (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
                    667:                        EMIT(O_BACK, i);
                    668:                } else
                    669:                        SETERROR(REG_ESUBREG);
                    670:                p->g->backrefs = 1;
                    671:                break;
                    672:        case '*':
                    673:                REQUIRE(starordinary, REG_BADRPT);
                    674:                /* FALLTHROUGH */
                    675:        default:
                    676:                ordinary(p, c &~ BACKSL);
                    677:                break;
                    678:        }
                    679:
                    680:        if (EAT('*')) {         /* implemented as +? */
1.4       jtc       681:                /* this case does not require the (y|) trick, noKLUDGE */
1.1       jtc       682:                INSERT(OPLUS_, pos);
                    683:                ASTERN(O_PLUS, pos);
                    684:                INSERT(OQUEST_, pos);
                    685:                ASTERN(O_QUEST, pos);
                    686:        } else if (EATTWO('\\', '{')) {
                    687:                count = p_count(p);
                    688:                if (EAT(',')) {
1.17      itohy     689:                        if (MORE() && isdigit((unsigned char)PEEK())) {
1.1       jtc       690:                                count2 = p_count(p);
                    691:                                REQUIRE(count <= count2, REG_BADBR);
                    692:                        } else          /* single number with comma */
                    693:                                count2 = INFINITY;
                    694:                } else          /* just a single number */
                    695:                        count2 = count;
                    696:                repeat(p, pos, count, count2);
                    697:                if (!EATTWO('\\', '}')) {       /* error heuristics */
                    698:                        while (MORE() && !SEETWO('\\', '}'))
                    699:                                NEXT();
                    700:                        REQUIRE(MORE(), REG_EBRACE);
                    701:                        SETERROR(REG_BADBR);
                    702:                }
                    703:        } else if (c == (unsigned char)'$')     /* $ (but not \$) ends it */
                    704:                return(1);
                    705:
                    706:        return(0);
                    707: }
                    708:
                    709: /*
                    710:  - p_count - parse a repetition count
1.9       perry     711:  == static int p_count(struct parse *p);
1.1       jtc       712:  */
                    713: static int                     /* the value */
1.27      junyoung  714: p_count(
                    715:     struct parse *p)
1.1       jtc       716: {
1.9       perry     717:        int count = 0;
                    718:        int ndigits = 0;
1.1       jtc       719:
1.14      lukem     720:        _DIAGASSERT(p != NULL);
                    721:
1.17      itohy     722:        while (MORE() && isdigit((unsigned char)PEEK()) && count <= DUPMAX) {
1.1       jtc       723:                count = count*10 + (GETNEXT() - '0');
                    724:                ndigits++;
                    725:        }
                    726:
                    727:        REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
                    728:        return(count);
                    729: }
                    730:
                    731: /*
                    732:  - p_bracket - parse a bracketed character list
1.9       perry     733:  == static void p_bracket(struct parse *p);
1.1       jtc       734:  *
                    735:  * Note a significant property of this code:  if the allocset() did SETERROR,
                    736:  * no set operations are done.
                    737:  */
                    738: static void
1.27      junyoung  739: p_bracket(
                    740:     struct parse *p)
1.1       jtc       741: {
1.14      lukem     742:        cset *cs;
1.9       perry     743:        int invert = 0;
1.1       jtc       744:
1.14      lukem     745:        _DIAGASSERT(p != NULL);
                    746:
                    747:        cs = allocset(p);
                    748:
1.1       jtc       749:        /* Dept of Truly Sickening Special-Case Kludges */
1.13      drochner  750:        if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]",
                    751:                                            (size_t)6) == 0) {
1.1       jtc       752:                EMIT(OBOW, 0);
                    753:                NEXTn(6);
                    754:                return;
                    755:        }
1.13      drochner  756:        if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]",
                    757:                                            (size_t)6) == 0) {
1.1       jtc       758:                EMIT(OEOW, 0);
                    759:                NEXTn(6);
                    760:                return;
                    761:        }
                    762:
                    763:        if (EAT('^'))
                    764:                invert++;       /* make note to invert set at end */
                    765:        if (EAT(']'))
                    766:                CHadd(cs, ']');
                    767:        else if (EAT('-'))
                    768:                CHadd(cs, '-');
                    769:        while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
                    770:                p_b_term(p, cs);
                    771:        if (EAT('-'))
                    772:                CHadd(cs, '-');
                    773:        MUSTEAT(']', REG_EBRACK);
                    774:
                    775:        if (p->error != 0)      /* don't mess things up further */
                    776:                return;
                    777:
                    778:        if (p->g->cflags&REG_ICASE) {
1.9       perry     779:                int i;
                    780:                int ci;
1.1       jtc       781:
                    782:                for (i = p->g->csetsize - 1; i >= 0; i--)
                    783:                        if (CHIN(cs, i) && isalpha(i)) {
                    784:                                ci = othercase(i);
                    785:                                if (ci != i)
                    786:                                        CHadd(cs, ci);
                    787:                        }
                    788:                if (cs->multis != NULL)
1.2       jtc       789:                        mccase(p, cs);
1.1       jtc       790:        }
                    791:        if (invert) {
1.9       perry     792:                int i;
1.1       jtc       793:
                    794:                for (i = p->g->csetsize - 1; i >= 0; i--)
                    795:                        if (CHIN(cs, i))
                    796:                                CHsub(cs, i);
                    797:                        else
                    798:                                CHadd(cs, i);
                    799:                if (p->g->cflags&REG_NEWLINE)
                    800:                        CHsub(cs, '\n');
                    801:                if (cs->multis != NULL)
1.2       jtc       802:                        mcinvert(p, cs);
1.1       jtc       803:        }
                    804:
                    805:        assert(cs->multis == NULL);             /* xxx */
                    806:
                    807:        if (nch(p, cs) == 1) {          /* optimize singleton sets */
                    808:                ordinary(p, firstch(p, cs));
                    809:                freeset(p, cs);
                    810:        } else
                    811:                EMIT(OANYOF, freezeset(p, cs));
                    812: }
                    813:
                    814: /*
                    815:  - p_b_term - parse one term of a bracketed character list
1.9       perry     816:  == static void p_b_term(struct parse *p, cset *cs);
1.1       jtc       817:  */
                    818: static void
1.27      junyoung  819: p_b_term(
                    820:     struct parse *p,
                    821:     cset *cs)
1.1       jtc       822: {
1.9       perry     823:        char c;
                    824:        char start, finish;
                    825:        int i;
1.1       jtc       826:
1.14      lukem     827:        _DIAGASSERT(p != NULL);
                    828:        _DIAGASSERT(cs != NULL);
                    829:
1.1       jtc       830:        /* classify what we've got */
                    831:        switch ((MORE()) ? PEEK() : '\0') {
                    832:        case '[':
                    833:                c = (MORE2()) ? PEEK2() : '\0';
                    834:                break;
1.11      christos  835:
1.1       jtc       836:        case '-':
                    837:                SETERROR(REG_ERANGE);
                    838:                return;                 /* NOTE RETURN */
1.11      christos  839:
1.1       jtc       840:        default:
                    841:                c = '\0';
                    842:                break;
                    843:        }
                    844:
                    845:        switch (c) {
                    846:        case ':':               /* character class */
                    847:                NEXT2();
                    848:                REQUIRE(MORE(), REG_EBRACK);
                    849:                c = PEEK();
                    850:                REQUIRE(c != '-' && c != ']', REG_ECTYPE);
                    851:                p_b_cclass(p, cs);
                    852:                REQUIRE(MORE(), REG_EBRACK);
                    853:                REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
                    854:                break;
                    855:        case '=':               /* equivalence class */
                    856:                NEXT2();
                    857:                REQUIRE(MORE(), REG_EBRACK);
                    858:                c = PEEK();
                    859:                REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
                    860:                p_b_eclass(p, cs);
                    861:                REQUIRE(MORE(), REG_EBRACK);
                    862:                REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
                    863:                break;
                    864:        default:                /* symbol, ordinary character, or range */
                    865: /* xxx revision needed for multichar stuff */
                    866:                start = p_b_symbol(p);
                    867:                if (SEE('-') && MORE2() && PEEK2() != ']') {
                    868:                        /* range */
                    869:                        NEXT();
                    870:                        if (EAT('-'))
                    871:                                finish = '-';
                    872:                        else
                    873:                                finish = p_b_symbol(p);
                    874:                } else
                    875:                        finish = start;
                    876: /* xxx what about signed chars here... */
                    877:                REQUIRE(start <= finish, REG_ERANGE);
                    878:                for (i = start; i <= finish; i++)
                    879:                        CHadd(cs, i);
                    880:                break;
                    881:        }
                    882: }
                    883:
                    884: /*
                    885:  - p_b_cclass - parse a character-class name and deal with it
1.9       perry     886:  == static void p_b_cclass(struct parse *p, cset *cs);
1.1       jtc       887:  */
                    888: static void
1.27      junyoung  889: p_b_cclass(
                    890:     struct parse *p,
                    891:     cset *cs)
1.1       jtc       892: {
1.21      yamt      893:        const char *sp;
1.10      mycroft   894:        const struct cclass *cp;
1.9       perry     895:        size_t len;
1.10      mycroft   896:        const char *u;
1.9       perry     897:        char c;
1.1       jtc       898:
1.14      lukem     899:        _DIAGASSERT(p != NULL);
                    900:        _DIAGASSERT(cs != NULL);
                    901:
                    902:        sp = p->next;
                    903:
1.17      itohy     904:        while (MORE() && isalpha((unsigned char)PEEK()))
1.1       jtc       905:                NEXT();
                    906:        len = p->next - sp;
                    907:        for (cp = cclasses; cp->name != NULL; cp++)
                    908:                if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
                    909:                        break;
                    910:        if (cp->name == NULL) {
                    911:                /* oops, didn't find it */
                    912:                SETERROR(REG_ECTYPE);
                    913:                return;
                    914:        }
                    915:
                    916:        u = cp->chars;
                    917:        while ((c = *u++) != '\0')
                    918:                CHadd(cs, c);
                    919:        for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
1.2       jtc       920:                MCadd(p, cs, u);
1.1       jtc       921: }
                    922:
                    923: /*
                    924:  - p_b_eclass - parse an equivalence-class name and deal with it
1.9       perry     925:  == static void p_b_eclass(struct parse *p, cset *cs);
1.1       jtc       926:  *
                    927:  * This implementation is incomplete. xxx
                    928:  */
                    929: static void
1.27      junyoung  930: p_b_eclass(
                    931:     struct parse *p,
                    932:     cset *cs)
1.1       jtc       933: {
1.9       perry     934:        char c;
1.1       jtc       935:
1.14      lukem     936:        _DIAGASSERT(p != NULL);
                    937:        _DIAGASSERT(cs != NULL);
                    938:
1.1       jtc       939:        c = p_b_coll_elem(p, '=');
                    940:        CHadd(cs, c);
                    941: }
                    942:
                    943: /*
                    944:  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
1.9       perry     945:  == static char p_b_symbol(struct parse *p);
1.1       jtc       946:  */
                    947: static char                    /* value of symbol */
1.27      junyoung  948: p_b_symbol(
                    949:     struct parse *p)
1.1       jtc       950: {
1.9       perry     951:        char value;
1.1       jtc       952:
1.14      lukem     953:        _DIAGASSERT(p != NULL);
                    954:
1.1       jtc       955:        REQUIRE(MORE(), REG_EBRACK);
                    956:        if (!EATTWO('[', '.'))
                    957:                return(GETNEXT());
                    958:
                    959:        /* collating symbol */
                    960:        value = p_b_coll_elem(p, '.');
                    961:        REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
                    962:        return(value);
                    963: }
                    964:
                    965: /*
                    966:  - p_b_coll_elem - parse a collating-element name and look it up
1.9       perry     967:  == static char p_b_coll_elem(struct parse *p, int endc);
1.1       jtc       968:  */
                    969: static char                    /* value of collating element */
1.27      junyoung  970: p_b_coll_elem(
                    971:     struct parse *p,
                    972:     int endc)                  /* name ended by endc,']' */
1.1       jtc       973: {
1.21      yamt      974:        const char *sp;
1.10      mycroft   975:        const struct cname *cp;
1.11      christos  976:        size_t len;
1.1       jtc       977:
1.14      lukem     978:        _DIAGASSERT(p != NULL);
                    979:
                    980:        sp = p->next;
                    981:
1.1       jtc       982:        while (MORE() && !SEETWO(endc, ']'))
                    983:                NEXT();
                    984:        if (!MORE()) {
                    985:                SETERROR(REG_EBRACK);
                    986:                return(0);
                    987:        }
                    988:        len = p->next - sp;
                    989:        for (cp = cnames; cp->name != NULL; cp++)
                    990:                if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
                    991:                        return(cp->code);       /* known name */
                    992:        if (len == 1)
                    993:                return(*sp);    /* single character */
                    994:        SETERROR(REG_ECOLLATE);                 /* neither */
                    995:        return(0);
                    996: }
                    997:
                    998: /*
                    999:  - othercase - return the case counterpart of an alphabetic
1.19      jdolecek 1000:  == static int othercase(int ch);
1.1       jtc      1001:  */
1.19      jdolecek 1002: static int                     /* if no counterpart, return ch */
1.27      junyoung 1003: othercase(
                   1004:     int ch)
1.1       jtc      1005: {
                   1006:        assert(isalpha(ch));
                   1007:        if (isupper(ch))
                   1008:                return(tolower(ch));
                   1009:        else if (islower(ch))
                   1010:                return(toupper(ch));
                   1011:        else                    /* peculiar, but could happen */
                   1012:                return(ch);
                   1013: }
                   1014:
                   1015: /*
                   1016:  - bothcases - emit a dualcase version of a two-case character
1.9       perry    1017:  == static void bothcases(struct parse *p, int ch);
1.1       jtc      1018:  *
                   1019:  * Boy, is this implementation ever a kludge...
                   1020:  */
                   1021: static void
1.27      junyoung 1022: bothcases(
                   1023:     struct parse *p,
                   1024:     int ch)
1.1       jtc      1025: {
1.21      yamt     1026:        const char *oldnext;
                   1027:        const char *oldend;
1.1       jtc      1028:        char bracket[3];
                   1029:
1.14      lukem    1030:        _DIAGASSERT(p != NULL);
                   1031:
                   1032:        oldnext = p->next;
                   1033:        oldend = p->end;
                   1034:
1.1       jtc      1035:        assert(othercase(ch) != ch);    /* p_bracket() would recurse */
                   1036:        p->next = bracket;
                   1037:        p->end = bracket+2;
                   1038:        bracket[0] = ch;
                   1039:        bracket[1] = ']';
                   1040:        bracket[2] = '\0';
                   1041:        p_bracket(p);
                   1042:        assert(p->next == bracket+2);
                   1043:        p->next = oldnext;
                   1044:        p->end = oldend;
                   1045: }
                   1046:
                   1047: /*
                   1048:  - ordinary - emit an ordinary character
1.9       perry    1049:  == static void ordinary(struct parse *p, int ch);
1.1       jtc      1050:  */
                   1051: static void
1.27      junyoung 1052: ordinary(
                   1053:     struct parse *p,
                   1054:     int ch)
1.1       jtc      1055: {
1.14      lukem    1056:        cat_t *cap;
1.1       jtc      1057:
1.14      lukem    1058:        _DIAGASSERT(p != NULL);
                   1059:
                   1060:        cap = p->g->categories;
1.17      itohy    1061:        if ((p->g->cflags&REG_ICASE) && isalpha((unsigned char) ch)
                   1062:            && othercase((unsigned char) ch) != (unsigned char) ch)
                   1063:                bothcases(p, (unsigned char) ch);
1.1       jtc      1064:        else {
                   1065:                EMIT(OCHAR, (unsigned char)ch);
                   1066:                if (cap[ch] == 0)
                   1067:                        cap[ch] = p->g->ncategories++;
                   1068:        }
                   1069: }
                   1070:
                   1071: /*
                   1072:  - nonnewline - emit REG_NEWLINE version of OANY
1.9       perry    1073:  == static void nonnewline(struct parse *p);
1.1       jtc      1074:  *
                   1075:  * Boy, is this implementation ever a kludge...
                   1076:  */
                   1077: static void
1.27      junyoung 1078: nonnewline(
                   1079:     struct parse *p)
1.1       jtc      1080: {
1.21      yamt     1081:        const char *oldnext;
                   1082:        const char *oldend;
1.1       jtc      1083:        char bracket[4];
                   1084:
1.14      lukem    1085:        _DIAGASSERT(p != NULL);
                   1086:
                   1087:        oldnext = p->next;
                   1088:        oldend = p->end;
                   1089:
1.1       jtc      1090:        p->next = bracket;
                   1091:        p->end = bracket+3;
                   1092:        bracket[0] = '^';
                   1093:        bracket[1] = '\n';
                   1094:        bracket[2] = ']';
                   1095:        bracket[3] = '\0';
                   1096:        p_bracket(p);
                   1097:        assert(p->next == bracket+3);
                   1098:        p->next = oldnext;
                   1099:        p->end = oldend;
                   1100: }
                   1101:
                   1102: /*
                   1103:  - repeat - generate code for a bounded repetition, recursively if needed
1.9       perry    1104:  == static void repeat(struct parse *p, sopno start, int from, int to);
1.1       jtc      1105:  */
                   1106: static void
1.27      junyoung 1107: repeat(
                   1108:     struct parse *p,
                   1109:     sopno start,               /* operand from here to end of strip */
                   1110:     int from,                  /* repeated from this number */
                   1111:     int to)                    /* to this number of times (maybe INFINITY) */
1.1       jtc      1112: {
1.14      lukem    1113:        sopno finish;
1.1       jtc      1114: #      define  N       2
                   1115: #      define  INF     3
                   1116: #      define  REP(f, t)       ((f)*8 + (t))
                   1117: #      define  MAP(n)  (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1.9       perry    1118:        sopno copy;
1.1       jtc      1119:
1.14      lukem    1120:        _DIAGASSERT(p != NULL);
                   1121:
                   1122:        finish = HERE();
                   1123:
1.1       jtc      1124:        if (p->error != 0)      /* head off possible runaway recursion */
                   1125:                return;
                   1126:
                   1127:        assert(from <= to);
                   1128:
                   1129:        switch (REP(MAP(from), MAP(to))) {
                   1130:        case REP(0, 0):                 /* must be user doing this */
                   1131:                DROP(finish-start);     /* drop the operand */
                   1132:                break;
                   1133:        case REP(0, 1):                 /* as x{1,1}? */
                   1134:        case REP(0, N):                 /* as x{1,n}? */
                   1135:        case REP(0, INF):               /* as x{1,}? */
1.4       jtc      1136:                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
                   1137:                INSERT(OCH_, start);            /* offset is wrong... */
1.1       jtc      1138:                repeat(p, start+1, 1, to);
1.4       jtc      1139:                ASTERN(OOR1, start);
1.1       jtc      1140:                AHEAD(start);                   /* ... fix it */
1.4       jtc      1141:                EMIT(OOR2, 0);
                   1142:                AHEAD(THERE());
                   1143:                ASTERN(O_CH, THERETHERE());
1.1       jtc      1144:                break;
                   1145:        case REP(1, 1):                 /* trivial case */
                   1146:                /* done */
                   1147:                break;
                   1148:        case REP(1, N):                 /* as x?x{1,n-1} */
1.4       jtc      1149:                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
                   1150:                INSERT(OCH_, start);
                   1151:                ASTERN(OOR1, start);
                   1152:                AHEAD(start);
                   1153:                EMIT(OOR2, 0);                  /* offset very wrong... */
                   1154:                AHEAD(THERE());                 /* ...so fix it */
                   1155:                ASTERN(O_CH, THERETHERE());
1.1       jtc      1156:                copy = dupl(p, start+1, finish+1);
1.4       jtc      1157:                assert(copy == finish+4);
1.1       jtc      1158:                repeat(p, copy, 1, to-1);
                   1159:                break;
                   1160:        case REP(1, INF):               /* as x+ */
                   1161:                INSERT(OPLUS_, start);
                   1162:                ASTERN(O_PLUS, start);
                   1163:                break;
                   1164:        case REP(N, N):                 /* as xx{m-1,n-1} */
                   1165:                copy = dupl(p, start, finish);
                   1166:                repeat(p, copy, from-1, to-1);
                   1167:                break;
                   1168:        case REP(N, INF):               /* as xx{n-1,INF} */
                   1169:                copy = dupl(p, start, finish);
                   1170:                repeat(p, copy, from-1, to);
                   1171:                break;
                   1172:        default:                        /* "can't happen" */
                   1173:                SETERROR(REG_ASSERT);   /* just in case */
                   1174:                break;
                   1175:        }
                   1176: }
                   1177:
                   1178: /*
                   1179:  - seterr - set an error condition
1.9       perry    1180:  == static int seterr(struct parse *p, int e);
1.1       jtc      1181:  */
                   1182: static int                     /* useless but makes type checking happy */
1.27      junyoung 1183: seterr(
                   1184:     struct parse *p,
                   1185:     int e)
1.1       jtc      1186: {
1.14      lukem    1187:
                   1188:        _DIAGASSERT(p != NULL);
                   1189:
1.1       jtc      1190:        if (p->error == 0)      /* keep earliest error condition */
                   1191:                p->error = e;
                   1192:        p->next = nuls;         /* try to bring things to a halt */
                   1193:        p->end = nuls;
                   1194:        return(0);              /* make the return value well-defined */
                   1195: }
                   1196:
                   1197: /*
                   1198:  - allocset - allocate a set of characters for []
1.9       perry    1199:  == static cset *allocset(struct parse *p);
1.1       jtc      1200:  */
                   1201: static cset *
1.27      junyoung 1202: allocset(
                   1203:     struct parse *p)
1.1       jtc      1204: {
1.14      lukem    1205:        int no;
1.9       perry    1206:        size_t nc;
                   1207:        size_t nbytes;
                   1208:        cset *cs;
1.14      lukem    1209:        size_t css;
1.9       perry    1210:        int i;
1.1       jtc      1211:
1.14      lukem    1212:        _DIAGASSERT(p != NULL);
                   1213:
                   1214:        no = p->g->ncsets++;
                   1215:        css = (size_t)p->g->csetsize;
1.1       jtc      1216:        if (no >= p->ncsalloc) {        /* need another column of space */
                   1217:                p->ncsalloc += CHAR_BIT;
                   1218:                nc = p->ncsalloc;
                   1219:                assert(nc % CHAR_BIT == 0);
                   1220:                nbytes = nc / CHAR_BIT * css;
                   1221:                if (p->g->sets == NULL)
1.11      christos 1222:                        p->g->sets = malloc(nc * sizeof(cset));
1.1       jtc      1223:                else
1.11      christos 1224:                        p->g->sets = realloc(p->g->sets, nc * sizeof(cset));
1.1       jtc      1225:                if (p->g->setbits == NULL)
1.11      christos 1226:                        p->g->setbits = malloc(nbytes);
1.2       jtc      1227:                else {
1.11      christos 1228:                        p->g->setbits = realloc(p->g->setbits, nbytes);
1.2       jtc      1229:                        /* xxx this isn't right if setbits is now NULL */
                   1230:                        for (i = 0; i < no; i++)
                   1231:                                p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
                   1232:                }
1.1       jtc      1233:                if (p->g->sets != NULL && p->g->setbits != NULL)
                   1234:                        (void) memset((char *)p->g->setbits + (nbytes - css),
                   1235:                                                                0, css);
                   1236:                else {
                   1237:                        no = 0;
                   1238:                        SETERROR(REG_ESPACE);
                   1239:                        /* caller's responsibility not to do set ops */
                   1240:                }
                   1241:        }
                   1242:
                   1243:        assert(p->g->sets != NULL);     /* xxx */
                   1244:        cs = &p->g->sets[no];
                   1245:        cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
                   1246:        cs->mask = 1 << ((no) % CHAR_BIT);
                   1247:        cs->hash = 0;
                   1248:        cs->smultis = 0;
                   1249:        cs->multis = NULL;
                   1250:
                   1251:        return(cs);
                   1252: }
                   1253:
                   1254: /*
                   1255:  - freeset - free a now-unused set
1.9       perry    1256:  == static void freeset(struct parse *p, cset *cs);
1.1       jtc      1257:  */
                   1258: static void
1.27      junyoung 1259: freeset(
                   1260:     struct parse *p,
                   1261:     cset *cs)
1.1       jtc      1262: {
1.9       perry    1263:        int i;
1.14      lukem    1264:        cset *top;
                   1265:        size_t css;
                   1266:
                   1267:        _DIAGASSERT(p != NULL);
                   1268:        _DIAGASSERT(cs != NULL);
                   1269:
                   1270:        top = &p->g->sets[p->g->ncsets];
                   1271:        css = (size_t)p->g->csetsize;
1.1       jtc      1272:
                   1273:        for (i = 0; i < css; i++)
                   1274:                CHsub(cs, i);
                   1275:        if (cs == top-1)        /* recover only the easy case */
                   1276:                p->g->ncsets--;
                   1277: }
                   1278:
                   1279: /*
                   1280:  - freezeset - final processing on a set of characters
1.9       perry    1281:  == static int freezeset(struct parse *p, cset *cs);
1.1       jtc      1282:  *
                   1283:  * The main task here is merging identical sets.  This is usually a waste
                   1284:  * of time (although the hash code minimizes the overhead), but can win
                   1285:  * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
                   1286:  * is done using addition rather than xor -- all ASCII [aA] sets xor to
                   1287:  * the same value!
                   1288:  */
                   1289: static int                     /* set number */
1.27      junyoung 1290: freezeset(
                   1291:     struct parse *p,
                   1292:     cset *cs)
1.1       jtc      1293: {
1.14      lukem    1294:        uch h;
1.9       perry    1295:        int i;
1.14      lukem    1296:        cset *top;
1.9       perry    1297:        cset *cs2;
1.14      lukem    1298:        size_t css;
                   1299:
                   1300:        _DIAGASSERT(p != NULL);
                   1301:        _DIAGASSERT(cs != NULL);
                   1302:
                   1303:        h = cs->hash;
                   1304:        top = &p->g->sets[p->g->ncsets];
                   1305:        css = (size_t)p->g->csetsize;
1.1       jtc      1306:
                   1307:        /* look for an earlier one which is the same */
                   1308:        for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
                   1309:                if (cs2->hash == h && cs2 != cs) {
                   1310:                        /* maybe */
                   1311:                        for (i = 0; i < css; i++)
                   1312:                                if (!!CHIN(cs2, i) != !!CHIN(cs, i))
                   1313:                                        break;          /* no */
                   1314:                        if (i == css)
                   1315:                                break;                  /* yes */
                   1316:                }
                   1317:
                   1318:        if (cs2 < top) {        /* found one */
                   1319:                freeset(p, cs);
                   1320:                cs = cs2;
                   1321:        }
                   1322:
                   1323:        return((int)(cs - p->g->sets));
                   1324: }
                   1325:
                   1326: /*
                   1327:  - firstch - return first character in a set (which must have at least one)
1.9       perry    1328:  == static int firstch(struct parse *p, cset *cs);
1.1       jtc      1329:  */
                   1330: static int                     /* character; there is no "none" value */
1.27      junyoung 1331: firstch(
                   1332:     struct parse *p,
                   1333:     cset *cs)
1.1       jtc      1334: {
1.9       perry    1335:        int i;
1.14      lukem    1336:        size_t css;
                   1337:
                   1338:        _DIAGASSERT(p != NULL);
                   1339:        _DIAGASSERT(cs != NULL);
                   1340:
                   1341:        css = (size_t)p->g->csetsize;
1.1       jtc      1342:
                   1343:        for (i = 0; i < css; i++)
                   1344:                if (CHIN(cs, i))
                   1345:                        return((char)i);
                   1346:        assert(never);
                   1347:        return(0);              /* arbitrary */
                   1348: }
                   1349:
                   1350: /*
                   1351:  - nch - number of characters in a set
1.9       perry    1352:  == static int nch(struct parse *p, cset *cs);
1.1       jtc      1353:  */
                   1354: static int
1.27      junyoung 1355: nch(
                   1356:     struct parse *p,
                   1357:     cset *cs)
1.1       jtc      1358: {
1.9       perry    1359:        int i;
1.14      lukem    1360:        size_t css;
1.9       perry    1361:        int n = 0;
1.1       jtc      1362:
1.14      lukem    1363:        _DIAGASSERT(p != NULL);
                   1364:        _DIAGASSERT(cs != NULL);
                   1365:
                   1366:        css = (size_t)p->g->csetsize;
                   1367:
1.1       jtc      1368:        for (i = 0; i < css; i++)
                   1369:                if (CHIN(cs, i))
                   1370:                        n++;
                   1371:        return(n);
                   1372: }
                   1373:
                   1374: /*
                   1375:  - mcadd - add a collating element to a cset
1.9       perry    1376:  == static void mcadd(struct parse *p, cset *cs, \
                   1377:  ==    char *cp);
1.1       jtc      1378:  */
                   1379: static void
1.27      junyoung 1380: mcadd(
                   1381:     struct parse *p,
                   1382:     cset *cs,
                   1383:     const char *cp)
1.1       jtc      1384: {
1.14      lukem    1385:        size_t oldend;
                   1386:
                   1387:        _DIAGASSERT(p != NULL);
                   1388:        _DIAGASSERT(cs != NULL);
                   1389:        _DIAGASSERT(cp != NULL);
                   1390:
                   1391:        oldend = cs->smultis;
1.1       jtc      1392:
                   1393:        cs->smultis += strlen(cp) + 1;
                   1394:        if (cs->multis == NULL)
                   1395:                cs->multis = malloc(cs->smultis);
                   1396:        else
                   1397:                cs->multis = realloc(cs->multis, cs->smultis);
                   1398:        if (cs->multis == NULL) {
                   1399:                SETERROR(REG_ESPACE);
                   1400:                return;
                   1401:        }
                   1402:
                   1403:        (void) strcpy(cs->multis + oldend - 1, cp);
                   1404:        cs->multis[cs->smultis - 1] = '\0';
                   1405: }
                   1406:
1.7       christos 1407: #if 0
1.1       jtc      1408: /*
                   1409:  - mcsub - subtract a collating element from a cset
1.9       perry    1410:  == static void mcsub(cset *cs, char *cp);
1.1       jtc      1411:  */
                   1412: static void
1.27      junyoung 1413: mcsub(
                   1414:     cset *cs,
                   1415:     char *cp)
1.1       jtc      1416: {
1.14      lukem    1417:        char *fp;
                   1418:        size_t len;
                   1419:
                   1420:        _DIAGASSERT(cs != NULL);
                   1421:        _DIAGASSERT(cp != NULL);
                   1422:
                   1423:        fp = mcfind(cs, cp);
                   1424:        len = strlen(fp);
1.1       jtc      1425:
                   1426:        assert(fp != NULL);
                   1427:        (void) memmove(fp, fp + len + 1,
                   1428:                                cs->smultis - (fp + len + 1 - cs->multis));
                   1429:        cs->smultis -= len;
                   1430:
                   1431:        if (cs->smultis == 0) {
                   1432:                free(cs->multis);
                   1433:                cs->multis = NULL;
                   1434:                return;
                   1435:        }
                   1436:
                   1437:        cs->multis = realloc(cs->multis, cs->smultis);
                   1438:        assert(cs->multis != NULL);
                   1439: }
                   1440:
                   1441: /*
                   1442:  - mcin - is a collating element in a cset?
1.9       perry    1443:  == static int mcin(cset *cs, char *cp);
1.1       jtc      1444:  */
                   1445: static int
1.27      junyoung 1446: mcin(
                   1447:     cset *cs,
                   1448:     char *cp)
1.1       jtc      1449: {
1.14      lukem    1450:
                   1451:        _DIAGASSERT(cs != NULL);
                   1452:        _DIAGASSERT(cp != NULL);
                   1453:
1.1       jtc      1454:        return(mcfind(cs, cp) != NULL);
                   1455: }
                   1456:
                   1457: /*
                   1458:  - mcfind - find a collating element in a cset
1.9       perry    1459:  == static char *mcfind(cset *cs, char *cp);
1.1       jtc      1460:  */
                   1461: static char *
1.27      junyoung 1462: mcfind(
                   1463:     cset *cs,
                   1464:     char *cp)
1.1       jtc      1465: {
1.9       perry    1466:        char *p;
1.1       jtc      1467:
1.14      lukem    1468:        _DIAGASSERT(cs != NULL);
                   1469:        _DIAGASSERT(cp != NULL);
                   1470:
1.1       jtc      1471:        if (cs->multis == NULL)
                   1472:                return(NULL);
                   1473:        for (p = cs->multis; *p != '\0'; p += strlen(p) + 1)
                   1474:                if (strcmp(cp, p) == 0)
                   1475:                        return(p);
                   1476:        return(NULL);
                   1477: }
1.7       christos 1478: #endif
1.1       jtc      1479:
                   1480: /*
                   1481:  - mcinvert - invert the list of collating elements in a cset
1.9       perry    1482:  == static void mcinvert(struct parse *p, cset *cs);
1.1       jtc      1483:  *
                   1484:  * This would have to know the set of possibilities.  Implementation
                   1485:  * is deferred.
                   1486:  */
1.11      christos 1487: /* ARGSUSED */
1.1       jtc      1488: static void
1.27      junyoung 1489: mcinvert(
                   1490:     struct parse *p,
                   1491:     cset *cs)
1.1       jtc      1492: {
1.14      lukem    1493:
                   1494:        _DIAGASSERT(p != NULL);
                   1495:        _DIAGASSERT(cs != NULL);
                   1496:
1.1       jtc      1497:        assert(cs->multis == NULL);     /* xxx */
                   1498: }
                   1499:
                   1500: /*
                   1501:  - mccase - add case counterparts of the list of collating elements in a cset
1.9       perry    1502:  == static void mccase(struct parse *p, cset *cs);
1.1       jtc      1503:  *
                   1504:  * This would have to know the set of possibilities.  Implementation
                   1505:  * is deferred.
                   1506:  */
1.11      christos 1507: /* ARGSUSED */
1.1       jtc      1508: static void
1.27      junyoung 1509: mccase(
                   1510:     struct parse *p,
                   1511:     cset *cs)
1.1       jtc      1512: {
1.14      lukem    1513:
                   1514:        _DIAGASSERT(p != NULL);
                   1515:        _DIAGASSERT(cs != NULL);
                   1516:
1.1       jtc      1517:        assert(cs->multis == NULL);     /* xxx */
                   1518: }
                   1519:
                   1520: /*
                   1521:  - isinsets - is this character in any sets?
1.9       perry    1522:  == static int isinsets(struct re_guts *g, int c);
1.1       jtc      1523:  */
                   1524: static int                     /* predicate */
1.27      junyoung 1525: isinsets(
                   1526:     struct re_guts *g,
                   1527:     int c)
1.1       jtc      1528: {
1.9       perry    1529:        uch *col;
                   1530:        int i;
1.14      lukem    1531:        int ncols;
1.9       perry    1532:        unsigned uc = (unsigned char)c;
1.1       jtc      1533:
1.14      lukem    1534:        _DIAGASSERT(g != NULL);
                   1535:
                   1536:        ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
                   1537:
1.1       jtc      1538:        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
                   1539:                if (col[uc] != 0)
                   1540:                        return(1);
                   1541:        return(0);
                   1542: }
                   1543:
                   1544: /*
                   1545:  - samesets - are these two characters in exactly the same sets?
1.9       perry    1546:  == static int samesets(struct re_guts *g, int c1, int c2);
1.1       jtc      1547:  */
                   1548: static int                     /* predicate */
1.27      junyoung 1549: samesets(
                   1550:     struct re_guts *g,
                   1551:     int c1,
                   1552:     int c2)
1.1       jtc      1553: {
1.9       perry    1554:        uch *col;
                   1555:        int i;
1.14      lukem    1556:        int ncols;
1.9       perry    1557:        unsigned uc1 = (unsigned char)c1;
                   1558:        unsigned uc2 = (unsigned char)c2;
1.1       jtc      1559:
1.14      lukem    1560:        _DIAGASSERT(g != NULL);
                   1561:
                   1562:        ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
                   1563:
1.1       jtc      1564:        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
                   1565:                if (col[uc1] != col[uc2])
                   1566:                        return(0);
                   1567:        return(1);
                   1568: }
                   1569:
                   1570: /*
                   1571:  - categorize - sort out character categories
1.9       perry    1572:  == static void categorize(struct parse *p, struct re_guts *g);
1.1       jtc      1573:  */
                   1574: static void
1.27      junyoung 1575: categorize(
                   1576:     struct parse *p,
                   1577:     struct re_guts *g)
1.1       jtc      1578: {
1.14      lukem    1579:        cat_t *cats;
1.9       perry    1580:        int c;
                   1581:        int c2;
                   1582:        cat_t cat;
1.1       jtc      1583:
1.14      lukem    1584:        _DIAGASSERT(p != NULL);
                   1585:        _DIAGASSERT(g != NULL);
                   1586:
                   1587:        cats = g->categories;
                   1588:
1.1       jtc      1589:        /* avoid making error situations worse */
                   1590:        if (p->error != 0)
                   1591:                return;
                   1592:
                   1593:        for (c = CHAR_MIN; c <= CHAR_MAX; c++)
                   1594:                if (cats[c] == 0 && isinsets(g, c)) {
                   1595:                        cat = g->ncategories++;
                   1596:                        cats[c] = cat;
                   1597:                        for (c2 = c+1; c2 <= CHAR_MAX; c2++)
                   1598:                                if (cats[c2] == 0 && samesets(g, c, c2))
                   1599:                                        cats[c2] = cat;
                   1600:                }
                   1601: }
                   1602:
                   1603: /*
                   1604:  - dupl - emit a duplicate of a bunch of sops
1.9       perry    1605:  == static sopno dupl(struct parse *p, sopno start, sopno finish);
1.1       jtc      1606:  */
                   1607: static sopno                   /* start of duplicate */
1.27      junyoung 1608: dupl(
                   1609:     struct parse *p,
                   1610:     sopno start,                       /* from here */
                   1611:     sopno finish)                      /* to this less one */
1.1       jtc      1612: {
1.14      lukem    1613:        sopno ret;
1.9       perry    1614:        sopno len = finish - start;
1.1       jtc      1615:
1.14      lukem    1616:        _DIAGASSERT(p != NULL);
                   1617:
                   1618:        ret = HERE();
                   1619:
1.1       jtc      1620:        assert(finish >= start);
                   1621:        if (len == 0)
                   1622:                return(ret);
                   1623:        enlarge(p, p->ssize + len);     /* this many unexpected additions */
                   1624:        assert(p->ssize >= p->slen + len);
1.12      drochner 1625:        (void)memcpy(p->strip + p->slen, p->strip + start,
1.11      christos 1626:            (size_t)len * sizeof(sop));
1.1       jtc      1627:        p->slen += len;
                   1628:        return(ret);
                   1629: }
                   1630:
                   1631: /*
                   1632:  - doemit - emit a strip operator
1.9       perry    1633:  == static void doemit(struct parse *p, sop op, size_t opnd);
1.1       jtc      1634:  *
                   1635:  * It might seem better to implement this as a macro with a function as
                   1636:  * hard-case backup, but it's just too big and messy unless there are
                   1637:  * some changes to the data structures.  Maybe later.
                   1638:  */
                   1639: static void
1.27      junyoung 1640: doemit(
                   1641:     struct parse *p,
                   1642:     sop op,
                   1643:     sopno opnd)
1.1       jtc      1644: {
1.14      lukem    1645:
                   1646:        _DIAGASSERT(p != NULL);
                   1647:
1.1       jtc      1648:        /* avoid making error situations worse */
                   1649:        if (p->error != 0)
                   1650:                return;
                   1651:
                   1652:        /* deal with oversize operands ("can't happen", more or less) */
                   1653:        assert(opnd < 1<<OPSHIFT);
                   1654:
                   1655:        /* deal with undersized strip */
                   1656:        if (p->slen >= p->ssize)
                   1657:                enlarge(p, (p->ssize+1) / 2 * 3);       /* +50% */
                   1658:        assert(p->slen < p->ssize);
                   1659:
                   1660:        /* finally, it's all reduced to the easy case */
                   1661:        p->strip[p->slen++] = SOP(op, opnd);
                   1662: }
                   1663:
                   1664: /*
                   1665:  - doinsert - insert a sop into the strip
1.9       perry    1666:  == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
1.1       jtc      1667:  */
                   1668: static void
1.27      junyoung 1669: doinsert(
                   1670:     struct parse *p,
                   1671:     sop op,
                   1672:     sopno opnd,
                   1673:     sopno pos)
1.1       jtc      1674: {
1.9       perry    1675:        sopno sn;
                   1676:        sop s;
                   1677:        int i;
1.1       jtc      1678:
1.14      lukem    1679:        _DIAGASSERT(p != NULL);
                   1680:
1.1       jtc      1681:        /* avoid making error situations worse */
                   1682:        if (p->error != 0)
                   1683:                return;
                   1684:
                   1685:        sn = HERE();
                   1686:        EMIT(op, opnd);         /* do checks, ensure space */
                   1687:        assert(HERE() == sn+1);
                   1688:        s = p->strip[sn];
                   1689:
                   1690:        /* adjust paren pointers */
                   1691:        assert(pos > 0);
                   1692:        for (i = 1; i < NPAREN; i++) {
                   1693:                if (p->pbegin[i] >= pos) {
                   1694:                        p->pbegin[i]++;
                   1695:                }
                   1696:                if (p->pend[i] >= pos) {
                   1697:                        p->pend[i]++;
                   1698:                }
                   1699:        }
                   1700:
1.11      christos 1701:        memmove(&p->strip[pos+1], &p->strip[pos], (HERE()-pos-1)*sizeof(sop));
1.1       jtc      1702:        p->strip[pos] = s;
                   1703: }
                   1704:
                   1705: /*
                   1706:  - dofwd - complete a forward reference
1.9       perry    1707:  == static void dofwd(struct parse *p, sopno pos, sop value);
1.1       jtc      1708:  */
                   1709: static void
1.27      junyoung 1710: dofwd(
                   1711:     struct parse *p,
                   1712:     sopno pos,
                   1713:     sopno value)
1.1       jtc      1714: {
1.14      lukem    1715:
                   1716:        _DIAGASSERT(p != NULL);
                   1717:
1.1       jtc      1718:        /* avoid making error situations worse */
                   1719:        if (p->error != 0)
                   1720:                return;
                   1721:
                   1722:        assert(value < 1<<OPSHIFT);
                   1723:        p->strip[pos] = OP(p->strip[pos]) | value;
                   1724: }
                   1725:
                   1726: /*
                   1727:  - enlarge - enlarge the strip
1.9       perry    1728:  == static void enlarge(struct parse *p, sopno size);
1.1       jtc      1729:  */
                   1730: static void
1.27      junyoung 1731: enlarge(
                   1732:     struct parse *p,
                   1733:     sopno size)
1.1       jtc      1734: {
1.9       perry    1735:        sop *sp;
1.1       jtc      1736:
1.14      lukem    1737:        _DIAGASSERT(p != NULL);
                   1738:
1.1       jtc      1739:        if (p->ssize >= size)
                   1740:                return;
                   1741:
                   1742:        sp = (sop *)realloc(p->strip, size*sizeof(sop));
                   1743:        if (sp == NULL) {
                   1744:                SETERROR(REG_ESPACE);
                   1745:                return;
                   1746:        }
                   1747:        p->strip = sp;
                   1748:        p->ssize = size;
                   1749: }
                   1750:
                   1751: /*
                   1752:  - stripsnug - compact the strip
1.9       perry    1753:  == static void stripsnug(struct parse *p, struct re_guts *g);
1.1       jtc      1754:  */
                   1755: static void
1.27      junyoung 1756: stripsnug(
                   1757:     struct parse *p,
                   1758:     struct re_guts *g)
1.1       jtc      1759: {
1.14      lukem    1760:
                   1761:        _DIAGASSERT(p != NULL);
                   1762:        _DIAGASSERT(g != NULL);
                   1763:
1.1       jtc      1764:        g->nstates = p->slen;
1.11      christos 1765:        g->strip = realloc(p->strip, p->slen * sizeof(sop));
1.1       jtc      1766:        if (g->strip == NULL) {
                   1767:                SETERROR(REG_ESPACE);
                   1768:                g->strip = p->strip;
                   1769:        }
                   1770: }
                   1771:
                   1772: /*
                   1773:  - findmust - fill in must and mlen with longest mandatory literal string
1.9       perry    1774:  == static void findmust(struct parse *p, struct re_guts *g);
1.1       jtc      1775:  *
                   1776:  * This algorithm could do fancy things like analyzing the operands of |
                   1777:  * for common subsequences.  Someday.  This code is simple and finds most
                   1778:  * of the interesting cases.
                   1779:  *
                   1780:  * Note that must and mlen got initialized during setup.
                   1781:  */
                   1782: static void
1.27      junyoung 1783: findmust(
                   1784:     struct parse *p,
                   1785:     struct re_guts *g)
1.1       jtc      1786: {
1.9       perry    1787:        sop *scan;
1.7       christos 1788:        sop *start = NULL;
1.9       perry    1789:        sop *newstart = NULL;
                   1790:        sopno newlen;
                   1791:        sop s;
                   1792:        char *cp;
                   1793:        sopno i;
1.1       jtc      1794:
1.14      lukem    1795:        _DIAGASSERT(p != NULL);
                   1796:        _DIAGASSERT(g != NULL);
                   1797:
1.1       jtc      1798:        /* avoid making error situations worse */
                   1799:        if (p->error != 0)
                   1800:                return;
                   1801:
                   1802:        /* find the longest OCHAR sequence in strip */
                   1803:        newlen = 0;
                   1804:        scan = g->strip + 1;
                   1805:        do {
                   1806:                s = *scan++;
                   1807:                switch (OP(s)) {
                   1808:                case OCHAR:             /* sequence member */
                   1809:                        if (newlen == 0)                /* new sequence */
                   1810:                                newstart = scan - 1;
                   1811:                        newlen++;
                   1812:                        break;
                   1813:                case OPLUS_:            /* things that don't break one */
                   1814:                case OLPAREN:
                   1815:                case ORPAREN:
                   1816:                        break;
                   1817:                case OQUEST_:           /* things that must be skipped */
                   1818:                case OCH_:
                   1819:                        scan--;
                   1820:                        do {
                   1821:                                scan += OPND(s);
                   1822:                                s = *scan;
                   1823:                                /* assert() interferes w debug printouts */
                   1824:                                if (OP(s) != O_QUEST && OP(s) != O_CH &&
                   1825:                                                        OP(s) != OOR2) {
                   1826:                                        g->iflags |= BAD;
                   1827:                                        return;
                   1828:                                }
                   1829:                        } while (OP(s) != O_QUEST && OP(s) != O_CH);
1.11      christos 1830:                        /* FALLTHROUGH */
1.1       jtc      1831:                default:                /* things that break a sequence */
                   1832:                        if (newlen > g->mlen) {         /* ends one */
                   1833:                                start = newstart;
                   1834:                                g->mlen = newlen;
                   1835:                        }
                   1836:                        newlen = 0;
                   1837:                        break;
                   1838:                }
                   1839:        } while (OP(s) != OEND);
                   1840:
1.23      christos 1841:        if (start == NULL)
                   1842:                g->mlen = 0;
                   1843:
                   1844:        if (g->mlen == 0)       /* there isn't one */
1.1       jtc      1845:                return;
                   1846:
                   1847:        /* turn it into a character string */
                   1848:        g->must = malloc((size_t)g->mlen + 1);
                   1849:        if (g->must == NULL) {          /* argh; just forget it */
                   1850:                g->mlen = 0;
                   1851:                return;
                   1852:        }
                   1853:        cp = g->must;
                   1854:        scan = start;
                   1855:        for (i = g->mlen; i > 0; i--) {
                   1856:                while (OP(s = *scan++) != OCHAR)
                   1857:                        continue;
1.2       jtc      1858:                assert(cp < g->must + g->mlen);
1.1       jtc      1859:                *cp++ = (char)OPND(s);
                   1860:        }
1.2       jtc      1861:        assert(cp == g->must + g->mlen);
1.1       jtc      1862:        *cp++ = '\0';           /* just on general principles */
                   1863: }
                   1864:
                   1865: /*
                   1866:  - pluscount - count + nesting
1.9       perry    1867:  == static sopno pluscount(struct parse *p, struct re_guts *g);
1.1       jtc      1868:  */
                   1869: static sopno                   /* nesting depth */
1.27      junyoung 1870: pluscount(
                   1871:     struct parse *p,
                   1872:     struct re_guts *g)
1.1       jtc      1873: {
1.9       perry    1874:        sop *scan;
                   1875:        sop s;
                   1876:        sopno plusnest = 0;
                   1877:        sopno maxnest = 0;
1.14      lukem    1878:
                   1879:        _DIAGASSERT(p != NULL);
                   1880:        _DIAGASSERT(g != NULL);
1.1       jtc      1881:
                   1882:        if (p->error != 0)
                   1883:                return(0);      /* there may not be an OEND */
                   1884:
                   1885:        scan = g->strip + 1;
                   1886:        do {
                   1887:                s = *scan++;
                   1888:                switch (OP(s)) {
                   1889:                case OPLUS_:
                   1890:                        plusnest++;
                   1891:                        break;
                   1892:                case O_PLUS:
                   1893:                        if (plusnest > maxnest)
                   1894:                                maxnest = plusnest;
                   1895:                        plusnest--;
                   1896:                        break;
                   1897:                }
                   1898:        } while (OP(s) != OEND);
                   1899:        if (plusnest != 0)
                   1900:                g->iflags |= BAD;
                   1901:        return(maxnest);
                   1902: }

CVSweb <webmaster@jp.NetBSD.org>