Return to regexp.c CVS log

Up to [MW Coherent from dump] / coherent / e / bin / pax

Annotation of coherent/e/bin/pax/regexp.c, revision 1.1

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

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