Return to regexp.c CVS log

Up to [Micropolis - Activity] / micropolis / src / tcl

Annotation of micropolis/src/tcl/regexp.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * regcomp and regexec -- regsub and regerror are elsewhere
        !             3:  *
        !             4:  *     Copyright (c) 1986 by University of Toronto.
        !             5:  *     Written by Henry Spencer.  Not derived from licensed software.
        !             6:  *
        !             7:  *     Permission is granted to anyone to use this software for any
        !             8:  *     purpose on any computer system, and to redistribute it freely,
        !             9:  *     subject to the following restrictions:
        !            10:  *
        !            11:  *     1. The author is not responsible for the consequences of use of
        !            12:  *             this software, no matter how awful, even if they arise
        !            13:  *             from defects in it.
        !            14:  *
        !            15:  *     2. The origin of this software must not be misrepresented, either
        !            16:  *             by explicit claim or by omission.
        !            17:  *
        !            18:  *     3. Altered versions must be plainly marked as such, and must not
        !            19:  *             be misrepresented as being the original software.
        !            20:  *
        !            21:  * Beware that some of this code is subtly aware of the way operator
        !            22:  * precedence is structured in regular expressions.  Serious changes in
        !            23:  * regular-expression syntax might require a total rethink.
        !            24:  *
        !            25:  * *** NOTE: this code has been altered slightly for use in Tcl. ***
        !            26:  * *** The only change is to use ckalloc and ckfree instead of   ***
        !            27:  * *** malloc and free.                                                 ***
        !            28:  */
        !            29: #include "tclint.h"
        !            30: 
        !            31: /*
        !            32:  * The "internal use only" fields in regexp.h are present to pass info from
        !            33:  * compile to execute that permits the execute phase to run lots faster on
        !            34:  * simple cases.  They are:
        !            35:  *
        !            36:  * regstart    char that must begin a match; '\0' if none obvious
        !            37:  * reganch     is the match anchored (at beginning-of-line only)?
        !            38:  * regmust     string (pointer into program) that match must include, or NULL
        !            39:  * regmlen     length of regmust string
        !            40:  *
        !            41:  * Regstart and reganch permit very fast decisions on suitable starting points
        !            42:  * for a match, cutting down the work a lot.  Regmust permits fast rejection
        !            43:  * of lines that cannot possibly match.  The regmust tests are costly enough
        !            44:  * that regcomp() supplies a regmust only if the r.e. contains something
        !            45:  * potentially expensive (at present, the only such thing detected is * or +
        !            46:  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
        !            47:  * supplied because the test in regexec() needs it and regcomp() is computing
        !            48:  * it anyway.
        !            49:  */
        !            50: 
        !            51: /*
        !            52:  * Structure for regexp "program".  This is essentially a linear encoding
        !            53:  * of a nondeterministic finite-state machine (aka syntax charts or
        !            54:  * "railroad normal form" in parsing technology).  Each node is an opcode
        !            55:  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
        !            56:  * all nodes except BRANCH implement concatenation; a "next" pointer with
        !            57:  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
        !            58:  * have one of the subtle syntax dependencies:  an individual BRANCH (as
        !            59:  * opposed to a collection of them) is never concatenated with anything
        !            60:  * because of operator precedence.)  The operand of some types of node is
        !            61:  * a literal string; for others, it is a node leading into a sub-FSM.  In
        !            62:  * particular, the operand of a BRANCH node is the first node of the branch.
        !            63:  * (NB this is *not* a tree structure:  the tail of the branch connects
        !            64:  * to the thing following the set of BRANCHes.)  The opcodes are:
        !            65:  */
        !            66: 
        !            67: /* definition  number  opnd?   meaning */
        !            68: #define        END     0       /* no   End of program. */
        !            69: #define        BOL     1       /* no   Match "" at beginning of line. */
        !            70: #define        EOL     2       /* no   Match "" at end of line. */
        !            71: #define        ANY     3       /* no   Match any one character. */
        !            72: #define        ANYOF   4       /* str  Match any character in this string. */
        !            73: #define        ANYBUT  5       /* str  Match any character not in this string. */
        !            74: #define        BRANCH  6       /* node Match this alternative, or the next... */
        !            75: #define        BACK    7       /* no   Match "", "next" ptr points backward. */
        !            76: #define        EXACTLY 8       /* str  Match this string. */
        !            77: #define        NOTHING 9       /* no   Match empty string. */
        !            78: #define        STAR    10      /* node Match this (simple) thing 0 or more times. */
        !            79: #define        PLUS    11      /* node Match this (simple) thing 1 or more times. */
        !            80: #define        OPEN    20      /* no   Mark this point in input as start of #n. */
        !            81:                        /*      OPEN+1 is number 1, etc. */
        !            82: #define        CLOSE   30      /* no   Analogous to OPEN. */
        !            83: 
        !            84: /*
        !            85:  * Opcode notes:
        !            86:  *
        !            87:  * BRANCH      The set of branches constituting a single choice are hooked
        !            88:  *             together with their "next" pointers, since precedence prevents
        !            89:  *             anything being concatenated to any individual branch.  The
        !            90:  *             "next" pointer of the last BRANCH in a choice points to the
        !            91:  *             thing following the whole choice.  This is also where the
        !            92:  *             final "next" pointer of each individual branch points; each
        !            93:  *             branch starts with the operand node of a BRANCH node.
        !            94:  *
        !            95:  * BACK                Normal "next" pointers all implicitly point forward; BACK
        !            96:  *             exists to make loop structures possible.
        !            97:  *
        !            98:  * STAR,PLUS   '?', and complex '*' and '+', are implemented as circular
        !            99:  *             BRANCH structures using BACK.  Simple cases (one character
        !           100:  *             per match) are implemented with STAR and PLUS for speed
        !           101:  *             and to minimize recursive plunges.
        !           102:  *
        !           103:  * OPEN,CLOSE  ...are numbered at compile time.
        !           104:  */
        !           105: 
        !           106: /*
        !           107:  * A node is one char of opcode followed by two chars of "next" pointer.
        !           108:  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
        !           109:  * value is a positive offset from the opcode of the node containing it.
        !           110:  * An operand, if any, simply follows the node.  (Note that much of the
        !           111:  * code generation knows about this implicit relationship.)
        !           112:  *
        !           113:  * Using two bytes for the "next" pointer is vast overkill for most things,
        !           114:  * but allows patterns to get big without disasters.
        !           115:  */
        !           116: #define        OP(p)   (*(p))
        !           117: #define        NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
        !           118: #define        OPERAND(p)      ((p) + 3)
        !           119: 
        !           120: /*
        !           121:  * See regmagic.h for one further detail of program structure.
        !           122:  */
        !           123: 
        !           124: 
        !           125: /*
        !           126:  * Utility definitions.
        !           127:  */
        !           128: #ifndef CHARBITS
        !           129: #define        UCHARAT(p)      ((int)*(unsigned char *)(p))
        !           130: #else
        !           131: #define        UCHARAT(p)      ((int)*(p)&CHARBITS)
        !           132: #endif
        !           133: 
        !           134: #define        FAIL(m) { regerror(m); return(NULL); }
        !           135: #define        ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')
        !           136: #define        META    "^$.[()|?+*\\"
        !           137: 
        !           138: /*
        !           139:  * Flags to be passed up and down.
        !           140:  */
        !           141: #define        HASWIDTH        01      /* Known never to match null string. */
        !           142: #define        SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
        !           143: #define        SPSTART         04      /* Starts with * or +. */
        !           144: #define        WORST           0       /* Worst case. */
        !           145: 
        !           146: /*
        !           147:  * Global work variables for regcomp().
        !           148:  */
        !           149: static char *regparse;         /* Input-scan pointer. */
        !           150: static int regnpar;            /* () count. */
        !           151: static char regdummy;
        !           152: static char *regcode;          /* Code-emit pointer; &regdummy = don't. */
        !           153: static long regsize;           /* Code size. */
        !           154: 
        !           155: /*
        !           156:  * The first byte of the regexp internal "program" is actually this magic
        !           157:  * number; the start node begins in the second byte.
        !           158:  */
        !           159: #define        MAGIC   0234
        !           160: 
        !           161: 
        !           162: /*
        !           163:  * Forward declarations for regcomp()'s friends.
        !           164:  */
        !           165: #ifndef STATIC
        !           166: #define        STATIC  static
        !           167: #endif
        !           168: STATIC char *reg();
        !           169: STATIC char *regbranch();
        !           170: STATIC char *regpiece();
        !           171: STATIC char *regatom();
        !           172: STATIC char *regnode();
        !           173: STATIC char *regnext();
        !           174: STATIC void regc();
        !           175: STATIC void reginsert();
        !           176: STATIC void regtail();
        !           177: STATIC void regoptail();
        !           178: #ifdef STRCSPN
        !           179: STATIC int strcspn();
        !           180: #endif
        !           181: 
        !           182: /*
        !           183:  - regcomp - compile a regular expression into internal code
        !           184:  *
        !           185:  * We can't allocate space until we know how big the compiled form will be,
        !           186:  * but we can't compile it (and thus know how big it is) until we've got a
        !           187:  * place to put the code.  So we cheat:  we compile it twice, once with code
        !           188:  * generation turned off and size counting turned on, and once "for real".
        !           189:  * This also means that we don't allocate space until we are sure that the
        !           190:  * thing really will compile successfully, and we never have to move the
        !           191:  * code and thus invalidate pointers into it.  (Note that it has to be in
        !           192:  * one piece because free() must be able to free it all.)
        !           193:  *
        !           194:  * Beware that the optimization-preparation code in here knows about some
        !           195:  * of the structure of the compiled regexp.
        !           196:  */
        !           197: regexp *
        !           198: regcomp(exp)
        !           199: char *exp;
        !           200: {
        !           201:        register regexp *r;
        !           202:        register char *scan;
        !           203:        register char *longest;
        !           204:        register int len;
        !           205:        int flags;
        !           206: 
        !           207:        if (exp == NULL)
        !           208:                FAIL("NULL argument");
        !           209: 
        !           210:        /* First pass: determine size, legality. */
        !           211:        regparse = exp;
        !           212:        regnpar = 1;
        !           213:        regsize = 0L;
        !           214:        regcode = &regdummy;
        !           215:        regc(MAGIC);
        !           216:        if (reg(0, &flags) == NULL)
        !           217:                return(NULL);
        !           218: 
        !           219:        /* Small enough for pointer-storage convention? */
        !           220:        if (regsize >= 32767L)          /* Probably could be 65535L. */
        !           221:                FAIL("regexp too big");
        !           222: 
        !           223:        /* Allocate space. */
        !           224:        r = (regexp *)ckalloc(sizeof(regexp) + (unsigned)regsize);
        !           225:        if (r == NULL)
        !           226:                FAIL("out of space");
        !           227: 
        !           228:        /* Second pass: emit code. */
        !           229:        regparse = exp;
        !           230:        regnpar = 1;
        !           231:        regcode = r->program;
        !           232:        regc(MAGIC);
        !           233:        if (reg(0, &flags) == NULL)
        !           234:                return(NULL);
        !           235: 
        !           236:        /* Dig out information for optimizations. */
        !           237:        r->regstart = '\0';     /* Worst-case defaults. */
        !           238:        r->reganch = 0;
        !           239:        r->regmust = NULL;
        !           240:        r->regmlen = 0;
        !           241:        scan = r->program+1;                    /* First BRANCH. */
        !           242:        if (OP(regnext(scan)) == END) {         /* Only one top-level choice. */
        !           243:                scan = OPERAND(scan);
        !           244: 
        !           245:                /* Starting-point info. */
        !           246:                if (OP(scan) == EXACTLY)
        !           247:                        r->regstart = *OPERAND(scan);
        !           248:                else if (OP(scan) == BOL)
        !           249:                        r->reganch++;
        !           250: 
        !           251:                /*
        !           252:                 * If there's something expensive in the r.e., find the
        !           253:                 * longest literal string that must appear and make it the
        !           254:                 * regmust.  Resolve ties in favor of later strings, since
        !           255:                 * the regstart check works with the beginning of the r.e.
        !           256:                 * and avoiding duplication strengthens checking.  Not a
        !           257:                 * strong reason, but sufficient in the absence of others.
        !           258:                 */
        !           259:                if (flags&SPSTART) {
        !           260:                        longest = NULL;
        !           261:                        len = 0;
        !           262:                        for (; scan != NULL; scan = regnext(scan))
        !           263:                                if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
        !           264:                                        longest = OPERAND(scan);
        !           265:                                        len = strlen(OPERAND(scan));
        !           266:                                }
        !           267:                        r->regmust = longest;
        !           268:                        r->regmlen = len;
        !           269:                }
        !           270:        }
        !           271: 
        !           272:        return(r);
        !           273: }
        !           274: 
        !           275: /*
        !           276:  - reg - regular expression, i.e. main body or parenthesized thing
        !           277:  *
        !           278:  * Caller must absorb opening parenthesis.
        !           279:  *
        !           280:  * Combining parenthesis handling with the base level of regular expression
        !           281:  * is a trifle forced, but the need to tie the tails of the branches to what
        !           282:  * follows makes it hard to avoid.
        !           283:  */
        !           284: static char *
        !           285: reg(paren, flagp)
        !           286: int paren;                     /* Parenthesized? */
        !           287: int *flagp;
        !           288: {
        !           289:        register char *ret;
        !           290:        register char *br;
        !           291:        register char *ender;
        !           292:        register int parno = 0;
        !           293:        int flags;
        !           294: 
        !           295:        *flagp = HASWIDTH;      /* Tentatively. */
        !           296: 
        !           297:        /* Make an OPEN node, if parenthesized. */
        !           298:        if (paren) {
        !           299:                if (regnpar >= NSUBEXP)
        !           300:                        FAIL("too many ()");
        !           301:                parno = regnpar;
        !           302:                regnpar++;
        !           303:                ret = regnode(OPEN+parno);
        !           304:        } else
        !           305:                ret = NULL;
        !           306: 
        !           307:        /* Pick up the branches, linking them together. */
        !           308:        br = regbranch(&flags);
        !           309:        if (br == NULL)
        !           310:                return(NULL);
        !           311:        if (ret != NULL)
        !           312:                regtail(ret, br);       /* OPEN -> first. */
        !           313:        else
        !           314:                ret = br;
        !           315:        if (!(flags&HASWIDTH))
        !           316:                *flagp &= ~HASWIDTH;
        !           317:        *flagp |= flags&SPSTART;
        !           318:        while (*regparse == '|') {
        !           319:                regparse++;
        !           320:                br = regbranch(&flags);
        !           321:                if (br == NULL)
        !           322:                        return(NULL);
        !           323:                regtail(ret, br);       /* BRANCH -> BRANCH. */
        !           324:                if (!(flags&HASWIDTH))
        !           325:                        *flagp &= ~HASWIDTH;
        !           326:                *flagp |= flags&SPSTART;
        !           327:        }
        !           328: 
        !           329:        /* Make a closing node, and hook it on the end. */
        !           330:        ender = regnode((paren) ? CLOSE+parno : END);   
        !           331:        regtail(ret, ender);
        !           332: 
        !           333:        /* Hook the tails of the branches to the closing node. */
        !           334:        for (br = ret; br != NULL; br = regnext(br))
        !           335:                regoptail(br, ender);
        !           336: 
        !           337:        /* Check for proper termination. */
        !           338:        if (paren && *regparse++ != ')') {
        !           339:                FAIL("unmatched ()");
        !           340:        } else if (!paren && *regparse != '\0') {
        !           341:                if (*regparse == ')') {
        !           342:                        FAIL("unmatched ()");
        !           343:                } else
        !           344:                        FAIL("junk on end");    /* "Can't happen". */
        !           345:                /* NOTREACHED */
        !           346:        }
        !           347: 
        !           348:        return(ret);
        !           349: }
        !           350: 
        !           351: /*
        !           352:  - regbranch - one alternative of an | operator
        !           353:  *
        !           354:  * Implements the concatenation operator.
        !           355:  */
        !           356: static char *
        !           357: regbranch(flagp)
        !           358: int *flagp;
        !           359: {
        !           360:        register char *ret;
        !           361:        register char *chain;
        !           362:        register char *latest;
        !           363:        int flags;
        !           364: 
        !           365:        *flagp = WORST;         /* Tentatively. */
        !           366: 
        !           367:        ret = regnode(BRANCH);
        !           368:        chain = NULL;
        !           369:        while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
        !           370:                latest = regpiece(&flags);
        !           371:                if (latest == NULL)
        !           372:                        return(NULL);
        !           373:                *flagp |= flags&HASWIDTH;
        !           374:                if (chain == NULL)      /* First piece. */
        !           375:                        *flagp |= flags&SPSTART;
        !           376:                else
        !           377:                        regtail(chain, latest);
        !           378:                chain = latest;
        !           379:        }
        !           380:        if (chain == NULL)      /* Loop ran zero times. */
        !           381:                (void) regnode(NOTHING);
        !           382: 
        !           383:        return(ret);
        !           384: }
        !           385: 
        !           386: /*
        !           387:  - regpiece - something followed by possible [*+?]
        !           388:  *
        !           389:  * Note that the branching code sequences used for ? and the general cases
        !           390:  * of * and + are somewhat optimized:  they use the same NOTHING node as
        !           391:  * both the endmarker for their branch list and the body of the last branch.
        !           392:  * It might seem that this node could be dispensed with entirely, but the
        !           393:  * endmarker role is not redundant.
        !           394:  */
        !           395: static char *
        !           396: regpiece(flagp)
        !           397: int *flagp;
        !           398: {
        !           399:        register char *ret;
        !           400:        register char op;
        !           401:        register char *next;
        !           402:        int flags;
        !           403: 
        !           404:        ret = regatom(&flags);
        !           405:        if (ret == NULL)
        !           406:                return(NULL);
        !           407: 
        !           408:        op = *regparse;
        !           409:        if (!ISMULT(op)) {
        !           410:                *flagp = flags;
        !           411:                return(ret);
        !           412:        }
        !           413: 
        !           414:        if (!(flags&HASWIDTH) && op != '?')
        !           415:                FAIL("*+ operand could be empty");
        !           416:        *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
        !           417: 
        !           418:        if (op == '*' && (flags&SIMPLE))
        !           419:                reginsert(STAR, ret);
        !           420:        else if (op == '*') {
        !           421:                /* Emit x* as (x&|), where & means "self". */
        !           422:                reginsert(BRANCH, ret);                 /* Either x */
        !           423:                regoptail(ret, regnode(BACK));          /* and loop */
        !           424:                regoptail(ret, ret);                    /* back */
        !           425:                regtail(ret, regnode(BRANCH));          /* or */
        !           426:                regtail(ret, regnode(NOTHING));         /* null. */
        !           427:        } else if (op == '+' && (flags&SIMPLE))
        !           428:                reginsert(PLUS, ret);
        !           429:        else if (op == '+') {
        !           430:                /* Emit x+ as x(&|), where & means "self". */
        !           431:                next = regnode(BRANCH);                 /* Either */
        !           432:                regtail(ret, next);
        !           433:                regtail(regnode(BACK), ret);            /* loop back */
        !           434:                regtail(next, regnode(BRANCH));         /* or */
        !           435:                regtail(ret, regnode(NOTHING));         /* null. */
        !           436:        } else if (op == '?') {
        !           437:                /* Emit x? as (x|) */
        !           438:                reginsert(BRANCH, ret);                 /* Either x */
        !           439:                regtail(ret, regnode(BRANCH));          /* or */
        !           440:                next = regnode(NOTHING);                /* null. */
        !           441:                regtail(ret, next);
        !           442:                regoptail(ret, next);
        !           443:        }
        !           444:        regparse++;
        !           445:        if (ISMULT(*regparse))
        !           446:                FAIL("nested *?+");
        !           447: 
        !           448:        return(ret);
        !           449: }
        !           450: 
        !           451: /*
        !           452:  - regatom - the lowest level
        !           453:  *
        !           454:  * Optimization:  gobbles an entire sequence of ordinary characters so that
        !           455:  * it can turn them into a single node, which is smaller to store and
        !           456:  * faster to run.  Backslashed characters are exceptions, each becoming a
        !           457:  * separate node; the code is simpler that way and it's not worth fixing.
        !           458:  */
        !           459: static char *
        !           460: regatom(flagp)
        !           461: int *flagp;
        !           462: {
        !           463:        register char *ret;
        !           464:        int flags;
        !           465: 
        !           466:        *flagp = WORST;         /* Tentatively. */
        !           467: 
        !           468:        switch (*regparse++) {
        !           469:        case '^':
        !           470:                ret = regnode(BOL);
        !           471:                break;
        !           472:        case '$':
        !           473:                ret = regnode(EOL);
        !           474:                break;
        !           475:        case '.':
        !           476:                ret = regnode(ANY);
        !           477:                *flagp |= HASWIDTH|SIMPLE;
        !           478:                break;
        !           479:        case '[': {
        !           480:                        register int clss;
        !           481:                        register int classend;
        !           482: 
        !           483:                        if (*regparse == '^') { /* Complement of range. */
        !           484:                                ret = regnode(ANYBUT);
        !           485:                                regparse++;
        !           486:                        } else
        !           487:                                ret = regnode(ANYOF);
        !           488:                        if (*regparse == ']' || *regparse == '-')
        !           489:                                regc(*regparse++);
        !           490:                        while (*regparse != '\0' && *regparse != ']') {
        !           491:                                if (*regparse == '-') {
        !           492:                                        regparse++;
        !           493:                                        if (*regparse == ']' || *regparse == '\0')
        !           494:                                                regc('-');
        !           495:                                        else {
        !           496:                                                clss = UCHARAT(regparse-2)+1;
        !           497:                                                classend = UCHARAT(regparse);
        !           498:                                                if (clss > classend+1)
        !           499:                                                        FAIL("invalid [] range");
        !           500:                                                for (; clss <= classend; clss++)
        !           501:                                                        regc(clss);
        !           502:                                                regparse++;
        !           503:                                        }
        !           504:                                } else
        !           505:                                        regc(*regparse++);
        !           506:                        }
        !           507:                        regc('\0');
        !           508:                        if (*regparse != ']')
        !           509:                                FAIL("unmatched []");
        !           510:                        regparse++;
        !           511:                        *flagp |= HASWIDTH|SIMPLE;
        !           512:                }
        !           513:                break;
        !           514:        case '(':
        !           515:                ret = reg(1, &flags);
        !           516:                if (ret == NULL)
        !           517:                        return(NULL);
        !           518:                *flagp |= flags&(HASWIDTH|SPSTART);
        !           519:                break;
        !           520:        case '\0':
        !           521:        case '|':
        !           522:        case ')':
        !           523:                FAIL("internal urp");   /* Supposed to be caught earlier. */
        !           524:                /* NOTREACHED */
        !           525:                break;
        !           526:        case '?':
        !           527:        case '+':
        !           528:        case '*':
        !           529:                FAIL("?+* follows nothing");
        !           530:                /* NOTREACHED */
        !           531:                break;
        !           532:        case '\\':
        !           533:                if (*regparse == '\0')
        !           534:                        FAIL("trailing \\");
        !           535:                ret = regnode(EXACTLY);
        !           536:                regc(*regparse++);
        !           537:                regc('\0');
        !           538:                *flagp |= HASWIDTH|SIMPLE;
        !           539:                break;
        !           540:        default: {
        !           541:                        register int len;
        !           542:                        register char ender;
        !           543: 
        !           544:                        regparse--;
        !           545:                        len = strcspn(regparse, META);
        !           546:                        if (len <= 0)
        !           547:                                FAIL("internal disaster");
        !           548:                        ender = *(regparse+len);
        !           549:                        if (len > 1 && ISMULT(ender))
        !           550:                                len--;          /* Back off clear of ?+* operand. */
        !           551:                        *flagp |= HASWIDTH;
        !           552:                        if (len == 1)
        !           553:                                *flagp |= SIMPLE;
        !           554:                        ret = regnode(EXACTLY);
        !           555:                        while (len > 0) {
        !           556:                                regc(*regparse++);
        !           557:                                len--;
        !           558:                        }
        !           559:                        regc('\0');
        !           560:                }
        !           561:                break;
        !           562:        }
        !           563: 
        !           564:        return(ret);
        !           565: }
        !           566: 
        !           567: /*
        !           568:  - regnode - emit a node
        !           569:  */
        !           570: static char *                  /* Location. */
        !           571: regnode(op)
        !           572: char op;
        !           573: {
        !           574:        register char *ret;
        !           575:        register char *ptr;
        !           576: 
        !           577:        ret = regcode;
        !           578:        if (ret == &regdummy) {
        !           579:                regsize += 3;
        !           580:                return(ret);
        !           581:        }
        !           582: 
        !           583:        ptr = ret;
        !           584:        *ptr++ = op;
        !           585:        *ptr++ = '\0';          /* Null "next" pointer. */
        !           586:        *ptr++ = '\0';
        !           587:        regcode = ptr;
        !           588: 
        !           589:        return(ret);
        !           590: }
        !           591: 
        !           592: /*
        !           593:  - regc - emit (if appropriate) a byte of code
        !           594:  */
        !           595: static void
        !           596: regc(b)
        !           597: char b;
        !           598: {
        !           599:        if (regcode != &regdummy)
        !           600:                *regcode++ = b;
        !           601:        else
        !           602:                regsize++;
        !           603: }
        !           604: 
        !           605: /*
        !           606:  - reginsert - insert an operator in front of already-emitted operand
        !           607:  *
        !           608:  * Means relocating the operand.
        !           609:  */
        !           610: static void
        !           611: reginsert(op, opnd)
        !           612: char op;
        !           613: char *opnd;
        !           614: {
        !           615:        register char *src;
        !           616:        register char *dst;
        !           617:        register char *place;
        !           618: 
        !           619:        if (regcode == &regdummy) {
        !           620:                regsize += 3;
        !           621:                return;
        !           622:        }
        !           623: 
        !           624:        src = regcode;
        !           625:        regcode += 3;
        !           626:        dst = regcode;
        !           627:        while (src > opnd)
        !           628:                *--dst = *--src;
        !           629: 
        !           630:        place = opnd;           /* Op node, where operand used to be. */
        !           631:        *place++ = op;
        !           632:        *place++ = '\0';
        !           633:        *place++ = '\0';
        !           634: }
        !           635: 
        !           636: /*
        !           637:  - regtail - set the next-pointer at the end of a node chain
        !           638:  */
        !           639: static void
        !           640: regtail(p, val)
        !           641: char *p;
        !           642: char *val;
        !           643: {
        !           644:        register char *scan;
        !           645:        register char *temp;
        !           646:        register int offset;
        !           647: 
        !           648:        if (p == &regdummy)
        !           649:                return;
        !           650: 
        !           651:        /* Find last node. */
        !           652:        scan = p;
        !           653:        for (;;) {
        !           654:                temp = regnext(scan);
        !           655:                if (temp == NULL)
        !           656:                        break;
        !           657:                scan = temp;
        !           658:        }
        !           659: 
        !           660:        if (OP(scan) == BACK)
        !           661:                offset = scan - val;
        !           662:        else
        !           663:                offset = val - scan;
        !           664:        *(scan+1) = (offset>>8)&0377;
        !           665:        *(scan+2) = offset&0377;
        !           666: }
        !           667: 
        !           668: /*
        !           669:  - regoptail - regtail on operand of first argument; nop if operandless
        !           670:  */
        !           671: static void
        !           672: regoptail(p, val)
        !           673: char *p;
        !           674: char *val;
        !           675: {
        !           676:        /* "Operandless" and "op != BRANCH" are synonymous in practice. */
        !           677:        if (p == NULL || p == &regdummy || OP(p) != BRANCH)
        !           678:                return;
        !           679:        regtail(OPERAND(p), val);
        !           680: }
        !           681: 
        !           682: /*
        !           683:  * regexec and friends
        !           684:  */
        !           685: 
        !           686: /*
        !           687:  * Global work variables for regexec().
        !           688:  */
        !           689: static char *reginput;         /* String-input pointer. */
        !           690: static char *regbol;           /* Beginning of input, for ^ check. */
        !           691: static char **regstartp;       /* Pointer to startp array. */
        !           692: static char **regendp;         /* Ditto for endp. */
        !           693: 
        !           694: /*
        !           695:  * Forwards.
        !           696:  */
        !           697: STATIC int regtry();
        !           698: STATIC int regmatch();
        !           699: STATIC int regrepeat();
        !           700: 
        !           701: #ifdef DEBUG
        !           702: int regnarrate = 0;
        !           703: void regdump();
        !           704: STATIC char *regprop();
        !           705: #endif
        !           706: 
        !           707: /*
        !           708:  - regexec - match a regexp against a string
        !           709:  */
        !           710: int
        !           711: regexec(prog, string)
        !           712: register regexp *prog;
        !           713: register char *string;
        !           714: {
        !           715:        register char *s;
        !           716: #ifndef IS_LINUX
        !           717:        extern char *strchr();
        !           718: #endif
        !           719: 
        !           720:        /* Be paranoid... */
        !           721:        if (prog == NULL || string == NULL) {
        !           722:                regerror("NULL parameter");
        !           723:                return(0);
        !           724:        }
        !           725: 
        !           726:        /* Check validity of program. */
        !           727:        if (UCHARAT(prog->program) != MAGIC) {
        !           728:                regerror("corrupted program");
        !           729:                return(0);
        !           730:        }
        !           731: 
        !           732:        /* If there is a "must appear" string, look for it. */
        !           733:        if (prog->regmust != NULL) {
        !           734:                s = string;
        !           735:                while ((s = strchr(s, prog->regmust[0])) != NULL) {
        !           736:                        if (strncmp(s, prog->regmust, prog->regmlen) == 0)
        !           737:                                break;  /* Found it. */
        !           738:                        s++;
        !           739:                }
        !           740:                if (s == NULL)  /* Not present. */
        !           741:                        return(0);
        !           742:        }
        !           743: 
        !           744:        /* Mark beginning of line for ^ . */
        !           745:        regbol = string;
        !           746: 
        !           747:        /* Simplest case:  anchored match need be tried only once. */
        !           748:        if (prog->reganch)
        !           749:                return(regtry(prog, string));
        !           750: 
        !           751:        /* Messy cases:  unanchored match. */
        !           752:        s = string;
        !           753:        if (prog->regstart != '\0')
        !           754:                /* We know what char it must start with. */
        !           755:                while ((s = strchr(s, prog->regstart)) != NULL) {
        !           756:                        if (regtry(prog, s))
        !           757:                                return(1);
        !           758:                        s++;
        !           759:                }
        !           760:        else
        !           761:                /* We don't -- general case. */
        !           762:                do {
        !           763:                        if (regtry(prog, s))
        !           764:                                return(1);
        !           765:                } while (*s++ != '\0');
        !           766: 
        !           767:        /* Failure. */
        !           768:        return(0);
        !           769: }
        !           770: 
        !           771: /*
        !           772:  - regtry - try match at specific point
        !           773:  */
        !           774: static int                     /* 0 failure, 1 success */
        !           775: regtry(prog, string)
        !           776: regexp *prog;
        !           777: char *string;
        !           778: {
        !           779:        register int i;
        !           780:        register char **sp;
        !           781:        register char **ep;
        !           782: 
        !           783:        reginput = string;
        !           784:        regstartp = prog->startp;
        !           785:        regendp = prog->endp;
        !           786: 
        !           787:        sp = prog->startp;
        !           788:        ep = prog->endp;
        !           789:        for (i = NSUBEXP; i > 0; i--) {
        !           790:                *sp++ = NULL;
        !           791:                *ep++ = NULL;
        !           792:        }
        !           793:        if (regmatch(prog->program + 1)) {
        !           794:                prog->startp[0] = string;
        !           795:                prog->endp[0] = reginput;
        !           796:                return(1);
        !           797:        } else
        !           798:                return(0);
        !           799: }
        !           800: 
        !           801: /*
        !           802:  - regmatch - main matching routine
        !           803:  *
        !           804:  * Conceptually the strategy is simple:  check to see whether the current
        !           805:  * node matches, call self recursively to see whether the rest matches,
        !           806:  * and then act accordingly.  In practice we make some effort to avoid
        !           807:  * recursion, in particular by going through "ordinary" nodes (that don't
        !           808:  * need to know whether the rest of the match failed) by a loop instead of
        !           809:  * by recursion.
        !           810:  */
        !           811: static int                     /* 0 failure, 1 success */
        !           812: regmatch(prog)
        !           813: char *prog;
        !           814: {
        !           815:        register char *scan;    /* Current node. */
        !           816:        char *next;             /* Next node. */
        !           817: #ifndef IS_LINUX
        !           818:        extern char *strchr();
        !           819: #endif
        !           820: 
        !           821:        scan = prog;
        !           822: #ifdef DEBUG
        !           823:        if (scan != NULL && regnarrate)
        !           824:                fprintf(stderr, "%s(\n", regprop(scan));
        !           825: #endif
        !           826:        while (scan != NULL) {
        !           827: #ifdef DEBUG
        !           828:                if (regnarrate)
        !           829:                        fprintf(stderr, "%s...\n", regprop(scan));
        !           830: #endif
        !           831:                next = regnext(scan);
        !           832: 
        !           833:                switch (OP(scan)) {
        !           834:                case BOL:
        !           835:                        if (reginput != regbol)
        !           836:                                return(0);
        !           837:                        break;
        !           838:                case EOL:
        !           839:                        if (*reginput != '\0')
        !           840:                                return(0);
        !           841:                        break;
        !           842:                case ANY:
        !           843:                        if (*reginput == '\0')
        !           844:                                return(0);
        !           845:                        reginput++;
        !           846:                        break;
        !           847:                case EXACTLY: {
        !           848:                                register int len;
        !           849:                                register char *opnd;
        !           850: 
        !           851:                                opnd = OPERAND(scan);
        !           852:                                /* Inline the first character, for speed. */
        !           853:                                if (*opnd != *reginput)
        !           854:                                        return(0);
        !           855:                                len = strlen(opnd);
        !           856:                                if (len > 1 && strncmp(opnd, reginput, len) != 0)
        !           857:                                        return(0);
        !           858:                                reginput += len;
        !           859:                        }
        !           860:                        break;
        !           861:                case ANYOF:
        !           862:                        if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
        !           863:                                return(0);
        !           864:                        reginput++;
        !           865:                        break;
        !           866:                case ANYBUT:
        !           867:                        if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
        !           868:                                return(0);
        !           869:                        reginput++;
        !           870:                        break;
        !           871:                case NOTHING:
        !           872:                        break;
        !           873:                case BACK:
        !           874:                        break;
        !           875:                case OPEN+1:
        !           876:                case OPEN+2:
        !           877:                case OPEN+3:
        !           878:                case OPEN+4:
        !           879:                case OPEN+5:
        !           880:                case OPEN+6:
        !           881:                case OPEN+7:
        !           882:                case OPEN+8:
        !           883:                case OPEN+9: {
        !           884:                                register int no;
        !           885:                                register char *save;
        !           886: 
        !           887:                                no = OP(scan) - OPEN;
        !           888:                                save = reginput;
        !           889: 
        !           890:                                if (regmatch(next)) {
        !           891:                                        /*
        !           892:                                         * Don't set startp if some later
        !           893:                                         * invocation of the same parentheses
        !           894:                                         * already has.
        !           895:                                         */
        !           896:                                        if (regstartp[no] == NULL)
        !           897:                                                regstartp[no] = save;
        !           898:                                        return(1);
        !           899:                                } else
        !           900:                                        return(0);
        !           901:                        }
        !           902:                        /* NOTREACHED */
        !           903:                        break;
        !           904:                case CLOSE+1:
        !           905:                case CLOSE+2:
        !           906:                case CLOSE+3:
        !           907:                case CLOSE+4:
        !           908:                case CLOSE+5:
        !           909:                case CLOSE+6:
        !           910:                case CLOSE+7:
        !           911:                case CLOSE+8:
        !           912:                case CLOSE+9: {
        !           913:                                register int no;
        !           914:                                register char *save;
        !           915: 
        !           916:                                no = OP(scan) - CLOSE;
        !           917:                                save = reginput;
        !           918: 
        !           919:                                if (regmatch(next)) {
        !           920:                                        /*
        !           921:                                         * Don't set endp if some later
        !           922:                                         * invocation of the same parentheses
        !           923:                                         * already has.
        !           924:                                         */
        !           925:                                        if (regendp[no] == NULL)
        !           926:                                                regendp[no] = save;
        !           927:                                        return(1);
        !           928:                                } else
        !           929:                                        return(0);
        !           930:                        }
        !           931:                        /* NOTREACHED */
        !           932:                        break;
        !           933:                case BRANCH: {
        !           934:                                register char *save;
        !           935: 
        !           936:                                if (OP(next) != BRANCH)         /* No choice. */
        !           937:                                        next = OPERAND(scan);   /* Avoid recursion. */
        !           938:                                else {
        !           939:                                        do {
        !           940:                                                save = reginput;
        !           941:                                                if (regmatch(OPERAND(scan)))
        !           942:                                                        return(1);
        !           943:                                                reginput = save;
        !           944:                                                scan = regnext(scan);
        !           945:                                        } while (scan != NULL && OP(scan) == BRANCH);
        !           946:                                        return(0);
        !           947:                                        /* NOTREACHED */
        !           948:                                }
        !           949:                        }
        !           950:                        /* NOTREACHED */
        !           951:                        break;
        !           952:                case STAR:
        !           953:                case PLUS: {
        !           954:                                register char nextch;
        !           955:                                register int no;
        !           956:                                register char *save;
        !           957:                                register int min;
        !           958: 
        !           959:                                /*
        !           960:                                 * Lookahead to avoid useless match attempts
        !           961:                                 * when we know what character comes next.
        !           962:                                 */
        !           963:                                nextch = '\0';
        !           964:                                if (OP(next) == EXACTLY)
        !           965:                                        nextch = *OPERAND(next);
        !           966:                                min = (OP(scan) == STAR) ? 0 : 1;
        !           967:                                save = reginput;
        !           968:                                no = regrepeat(OPERAND(scan));
        !           969:                                while (no >= min) {
        !           970:                                        /* If it could work, try it. */
        !           971:                                        if (nextch == '\0' || *reginput == nextch)
        !           972:                                                if (regmatch(next))
        !           973:                                                        return(1);
        !           974:                                        /* Couldn't or didn't -- back up. */
        !           975:                                        no--;
        !           976:                                        reginput = save + no;
        !           977:                                }
        !           978:                                return(0);
        !           979:                        }
        !           980:                        /* NOTREACHED */
        !           981:                        break;
        !           982:                case END:
        !           983:                        return(1);      /* Success! */
        !           984:                        /* NOTREACHED */
        !           985:                        break;
        !           986:                default:
        !           987:                        regerror("memory corruption");
        !           988:                        return(0);
        !           989:                        /* NOTREACHED */
        !           990:                        break;
        !           991:                }
        !           992: 
        !           993:                scan = next;
        !           994:        }
        !           995: 
        !           996:        /*
        !           997:         * We get here only if there's trouble -- normally "case END" is
        !           998:         * the terminating point.
        !           999:         */
        !          1000:        regerror("corrupted pointers");
        !          1001:        return(0);
        !          1002: }
        !          1003: 
        !          1004: /*
        !          1005:  - regrepeat - repeatedly match something simple, report how many
        !          1006:  */
        !          1007: static int
        !          1008: regrepeat(p)
        !          1009: char *p;
        !          1010: {
        !          1011:        register int count = 0;
        !          1012:        register char *scan;
        !          1013:        register char *opnd;
        !          1014: 
        !          1015:        scan = reginput;
        !          1016:        opnd = OPERAND(p);
        !          1017:        switch (OP(p)) {
        !          1018:        case ANY:
        !          1019:                count = strlen(scan);
        !          1020:                scan += count;
        !          1021:                break;
        !          1022:        case EXACTLY:
        !          1023:                while (*opnd == *scan) {
        !          1024:                        count++;
        !          1025:                        scan++;
        !          1026:                }
        !          1027:                break;
        !          1028:        case ANYOF:
        !          1029:                while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
        !          1030:                        count++;
        !          1031:                        scan++;
        !          1032:                }
        !          1033:                break;
        !          1034:        case ANYBUT:
        !          1035:                while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
        !          1036:                        count++;
        !          1037:                        scan++;
        !          1038:                }
        !          1039:                break;
        !          1040:        default:                /* Oh dear.  Called inappropriately. */
        !          1041:                regerror("internal foulup");
        !          1042:                count = 0;      /* Best compromise. */
        !          1043:                break;
        !          1044:        }
        !          1045:        reginput = scan;
        !          1046: 
        !          1047:        return(count);
        !          1048: }
        !          1049: 
        !          1050: /*
        !          1051:  - regnext - dig the "next" pointer out of a node
        !          1052:  */
        !          1053: static char *
        !          1054: regnext(p)
        !          1055: register char *p;
        !          1056: {
        !          1057:        register int offset;
        !          1058: 
        !          1059:        if (p == &regdummy)
        !          1060:                return(NULL);
        !          1061: 
        !          1062:        offset = NEXT(p);
        !          1063:        if (offset == 0)
        !          1064:                return(NULL);
        !          1065: 
        !          1066:        if (OP(p) == BACK)
        !          1067:                return(p-offset);
        !          1068:        else
        !          1069:                return(p+offset);
        !          1070: }
        !          1071: 
        !          1072: #ifdef DEBUG
        !          1073: 
        !          1074: STATIC char *regprop();
        !          1075: 
        !          1076: /*
        !          1077:  - regdump - dump a regexp onto stdout in vaguely comprehensible form
        !          1078:  */
        !          1079: void
        !          1080: regdump(r)
        !          1081: regexp *r;
        !          1082: {
        !          1083:        register char *s;
        !          1084:        register char op = EXACTLY;     /* Arbitrary non-END op. */
        !          1085:        register char *next;
        !          1086:        extern char *strchr();
        !          1087: 
        !          1088: 
        !          1089:        s = r->program + 1;
        !          1090:        while (op != END) {     /* While that wasn't END last time... */
        !          1091:                op = OP(s);
        !          1092:                printf("%2d%s", s-r->program, regprop(s));      /* Where, what. */
        !          1093:                next = regnext(s);
        !          1094:                if (next == NULL)               /* Next ptr. */
        !          1095:                        printf("(0)");
        !          1096:                else 
        !          1097:                        printf("(%d)", (s-r->program)+(next-s));
        !          1098:                s += 3;
        !          1099:                if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
        !          1100:                        /* Literal string, where present. */
        !          1101:                        while (*s != '\0') {
        !          1102:                                putchar(*s);
        !          1103:                                s++;
        !          1104:                        }
        !          1105:                        s++;
        !          1106:                }
        !          1107:                putchar('\n');
        !          1108:        }
        !          1109: 
        !          1110:        /* Header fields of interest. */
        !          1111:        if (r->regstart != '\0')
        !          1112:                printf("start `%c' ", r->regstart);
        !          1113:        if (r->reganch)
        !          1114:                printf("anchored ");
        !          1115:        if (r->regmust != NULL)
        !          1116:                printf("must have \"%s\"", r->regmust);
        !          1117:        printf("\n");
        !          1118: }
        !          1119: 
        !          1120: /*
        !          1121:  - regprop - printable representation of opcode
        !          1122:  */
        !          1123: static char *
        !          1124: regprop(op)
        !          1125: char *op;
        !          1126: {
        !          1127:        register char *p;
        !          1128:        static char buf[50];
        !          1129: 
        !          1130:        (void) strcpy(buf, ":");
        !          1131: 
        !          1132:        switch (OP(op)) {
        !          1133:        case BOL:
        !          1134:                p = "BOL";
        !          1135:                break;
        !          1136:        case EOL:
        !          1137:                p = "EOL";
        !          1138:                break;
        !          1139:        case ANY:
        !          1140:                p = "ANY";
        !          1141:                break;
        !          1142:        case ANYOF:
        !          1143:                p = "ANYOF";
        !          1144:                break;
        !          1145:        case ANYBUT:
        !          1146:                p = "ANYBUT";
        !          1147:                break;
        !          1148:        case BRANCH:
        !          1149:                p = "BRANCH";
        !          1150:                break;
        !          1151:        case EXACTLY:
        !          1152:                p = "EXACTLY";
        !          1153:                break;
        !          1154:        case NOTHING:
        !          1155:                p = "NOTHING";
        !          1156:                break;
        !          1157:        case BACK:
        !          1158:                p = "BACK";
        !          1159:                break;
        !          1160:        case END:
        !          1161:                p = "END";
        !          1162:                break;
        !          1163:        case OPEN+1:
        !          1164:        case OPEN+2:
        !          1165:        case OPEN+3:
        !          1166:        case OPEN+4:
        !          1167:        case OPEN+5:
        !          1168:        case OPEN+6:
        !          1169:        case OPEN+7:
        !          1170:        case OPEN+8:
        !          1171:        case OPEN+9:
        !          1172:                sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
        !          1173:                p = NULL;
        !          1174:                break;
        !          1175:        case CLOSE+1:
        !          1176:        case CLOSE+2:
        !          1177:        case CLOSE+3:
        !          1178:        case CLOSE+4:
        !          1179:        case CLOSE+5:
        !          1180:        case CLOSE+6:
        !          1181:        case CLOSE+7:
        !          1182:        case CLOSE+8:
        !          1183:        case CLOSE+9:
        !          1184:                sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
        !          1185:                p = NULL;
        !          1186:                break;
        !          1187:        case STAR:
        !          1188:                p = "STAR";
        !          1189:                break;
        !          1190:        case PLUS:
        !          1191:                p = "PLUS";
        !          1192:                break;
        !          1193:        default:
        !          1194:                regerror("corrupted opcode");
        !          1195:                break;
        !          1196:        }
        !          1197:        if (p != NULL)
        !          1198:                (void) strcat(buf, p);
        !          1199:        return(buf);
        !          1200: }
        !          1201: #endif
        !          1202: 
        !          1203: /*
        !          1204:  * The following is provided for those people who do not have strcspn() in
        !          1205:  * their C libraries.  They should get off their butts and do something
        !          1206:  * about it; at least one public-domain implementation of those (highly
        !          1207:  * useful) string routines has been published on Usenet.
        !          1208:  */
        !          1209: #ifdef STRCSPN
        !          1210: /*
        !          1211:  * strcspn - find length of initial segment of s1 consisting entirely
        !          1212:  * of characters not from s2
        !          1213:  */
        !          1214: 
        !          1215: static int
        !          1216: strcspn(s1, s2)
        !          1217: char *s1;
        !          1218: char *s2;
        !          1219: {
        !          1220:        register char *scan1;
        !          1221:        register char *scan2;
        !          1222:        register int count;
        !          1223: 
        !          1224:        count = 0;
        !          1225:        for (scan1 = s1; *scan1 != '\0'; scan1++) {
        !          1226:                for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */
        !          1227:                        if (*scan1 == *scan2++)
        !          1228:                                return(count);
        !          1229:                count++;
        !          1230:        }
        !          1231:        return(count);
        !          1232: }
        !          1233: #endif

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.