[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.36

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

CVSweb <webmaster@jp.NetBSD.org>