Subversion Repositories or1k

/*

 * regcomp and regexec -- regsub and regerror are elsewhere

 *

 *      Copyright (c) 1986 by University of Toronto.

 *      Written by Henry Spencer.  Not derived from licensed software.

 *

 *      Permission is granted to anyone to use this software for any

 *      purpose on any computer system, and to redistribute it freely,

 *      subject to the following restrictions:

 *

 *      1. The author is not responsible for the consequences of use of

 *              this software, no matter how awful, even if they arise

 *              from defects in it.

 *

 *      2. The origin of this software must not be misrepresented, either

 *              by explicit claim or by omission.

 *

 *      3. Altered versions must be plainly marked as such, and must not

 *              be misrepresented as being the original software.

 *

 * Beware that some of this code is subtly aware of the way operator

 * precedence is structured in regular expressions.  Serious changes in

 * regular-expression syntax might require a total rethink.

 */

#include <stdio.h>

#include <regexp.h>

#include <malloc.h>

#include <string.h>

#include "regmagic.h"

/*

 * The "internal use only" fields in regexp.h are present to pass info from

 * compile to execute that permits the execute phase to run lots faster on

 * simple cases.  They are:

 *

 * regstart     char that must begin a match; '\0' if none obvious

 * reganch      is the match anchored (at beginning-of-line only)?

 * regmust      string (pointer into program) that match must include, or NULL

 * regmlen      length of regmust string

 *

 * Regstart and reganch permit very fast decisions on suitable starting points

 * for a match, cutting down the work a lot.  Regmust permits fast rejection

 * of lines that cannot possibly match.  The regmust tests are costly enough

 * that regcomp() supplies a regmust only if the r.e. contains something

 * potentially expensive (at present, the only such thing detected is * or +

 * at the start of the r.e., which can involve a lot of backup).  Regmlen is

 * supplied because the test in regexec() needs it and regcomp() is computing

 * it anyway.

 */

/*

 * Structure for regexp "program".  This is essentially a linear encoding

 * of a nondeterministic finite-state machine (aka syntax charts or

 * "railroad normal form" in parsing technology).  Each node is an opcode

 * plus a "next" pointer, possibly plus an operand.  "Next" pointers of

 * all nodes except BRANCH implement concatenation; a "next" pointer with

 * a BRANCH on both ends of it is connecting two alternatives.  (Here we

 * have one of the subtle syntax dependencies:  an individual BRANCH (as

 * opposed to a collection of them) is never concatenated with anything

 * because of operator precedence.)  The operand of some types of node is

 * a literal string; for others, it is a node leading into a sub-FSM.  In

 * particular, the operand of a BRANCH node is the first node of the branch.

 * (NB this is *not* a tree structure:  the tail of the branch connects

 * to the thing following the set of BRANCHes.)  The opcodes are:

 */

/* definition   number  opnd?   meaning */

#define END     0        /* no   End of program. */

#define BOL     1       /* no   Match "" at beginning of line. */

#define EOL     2       /* no   Match "" at end of line. */

#define ANY     3       /* no   Match any one character. */

#define ANYOF   4       /* str  Match any character in this string. */

#define ANYBUT  5       /* str  Match any character not in this string. */

#define BRANCH  6       /* node Match this alternative, or the next... */

#define BACK    7       /* no   Match "", "next" ptr points backward. */

#define EXACTLY 8       /* str  Match this string. */

#define NOTHING 9       /* no   Match empty string. */

#define STAR    10      /* node Match this (simple) thing 0 or more times. */

#define PLUS    11      /* node Match this (simple) thing 1 or more times. */

#define OPEN    20      /* no   Mark this point in input as start of #n. */

                        /*      OPEN+1 is number 1, etc. */

#define CLOSE   30      /* no   Analogous to OPEN. */

/*

 * Opcode notes:

 *

 * BRANCH       The set of branches constituting a single choice are hooked

 *              together with their "next" pointers, since precedence prevents

 *              anything being concatenated to any individual branch.  The

 *              "next" pointer of the last BRANCH in a choice points to the

 *              thing following the whole choice.  This is also where the

 *              final "next" pointer of each individual branch points; each

 *              branch starts with the operand node of a BRANCH node.

 *

 * BACK         Normal "next" pointers all implicitly point forward; BACK

 *              exists to make loop structures possible.

 *

 * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular

 *              BRANCH structures using BACK.  Simple cases (one character

 *              per match) are implemented with STAR and PLUS for speed

 *              and to minimize recursive plunges.

 *

 * OPEN,CLOSE   ...are numbered at compile time.

 */

/*

 * A node is one char of opcode followed by two chars of "next" pointer.

 * "Next" pointers are stored as two 8-bit pieces, high order first.  The

 * value is a positive offset from the opcode of the node containing it.

 * An operand, if any, simply follows the node.  (Note that much of the

 * code generation knows about this implicit relationship.)

 *

 * Using two bytes for the "next" pointer is vast overkill for most things,

 * but allows patterns to get big without disasters.

 */

#define OP(p)   (*(p))

#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))

#define OPERAND(p)      ((p) + 3)

/*

 * See regmagic.h for one further detail of program structure.

 */

/*

 * Utility definitions.

 */

#ifndef CHARBITS

#define UCHARAT(p)      ((int)*(unsigned char *)(p))

#else

#define UCHARAT(p)      ((int)*(p)&CHARBITS)

#endif

#define FAIL(m) { regerror(m); return(NULL); }

#define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')

#define META    "^$.[()|?+*\\"

/*

 * Flags to be passed up and down.

 */

#define HASWIDTH        01      /* Known never to match null string. */

#define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */

#define SPSTART         04      /* Starts with * or +. */

#define WORST           0        /* Worst case. */

/*

 * Global work variables for regcomp().

 */

static char *regparse;          /* Input-scan pointer. */

static int regnpar;             /* () count. */

static char regdummy;

static char *regcode;           /* Code-emit pointer; &regdummy = don't. */

static long regsize;            /* Code size. */

/*

 * Forward declarations for regcomp()'s friends.

 */

#ifndef STATIC

#define STATIC  static

#endif

STATIC char *reg();

STATIC char *regbranch();

STATIC char *regpiece();

STATIC char *regatom();

STATIC char *regnode();

STATIC char *regnext();

STATIC void regc();

STATIC void reginsert();

STATIC void regtail();

STATIC void regoptail();

#ifdef STRCSPN

STATIC int strcspn();

#endif

/*

 - regcomp - compile a regular expression into internal code

 *

 * We can't allocate space until we know how big the compiled form will be,

 * but we can't compile it (and thus know how big it is) until we've got a

 * place to put the code.  So we cheat:  we compile it twice, once with code

 * generation turned off and size counting turned on, and once "for real".

 * This also means that we don't allocate space until we are sure that the

 * thing really will compile successfully, and we never have to move the

 * code and thus invalidate pointers into it.  (Note that it has to be in

 * one piece because free() must be able to free it all.)

 *

 * Beware that the optimization-preparation code in here knows about some

 * of the structure of the compiled regexp.

 */

regexp *

regcomp(exp)

char *exp;

{

        register regexp *r;

        register char *scan;

        register char *longest;

        register int len;

        int flags;

        if (exp == NULL)

                FAIL("NULL argument");

        /* First pass: determine size, legality. */

        regparse = exp;

        regnpar = 1;

        regsize = 0L;

        regcode = &regdummy;

        regc(MAGIC);

        if (reg(0, &flags) == NULL)

                return(NULL);

        /* Small enough for pointer-storage convention? */

        if (regsize >= 32767L)          /* Probably could be 65535L. */

                FAIL("regexp too big");

        /* Allocate space. */

        r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);

        if (r == NULL)

                FAIL("out of space");

        /* Second pass: emit code. */

        regparse = exp;

        regnpar = 1;

        regcode = r->program;

        regc(MAGIC);

        if (reg(0, &flags) == NULL)

                return(NULL);

        /* Dig out information for optimizations. */

        r->regstart = '\0';     /* Worst-case defaults. */

        r->reganch = 0;

        r->regmust = NULL;

        r->regmlen = 0;

        scan = r->program+1;                    /* First BRANCH. */

        if (OP(regnext(scan)) == END) {         /* Only one top-level choice. */

                scan = OPERAND(scan);

                /* Starting-point info. */

                if (OP(scan) == EXACTLY)

                        r->regstart = *OPERAND(scan);

                else if (OP(scan) == BOL)

                        r->reganch++;

                /*

                 * If there's something expensive in the r.e., find the

                 * longest literal string that must appear and make it the

                 * regmust.  Resolve ties in favor of later strings, since

                 * the regstart check works with the beginning of the r.e.

                 * and avoiding duplication strengthens checking.  Not a

                 * strong reason, but sufficient in the absence of others.

                 */

                if (flags&SPSTART) {

                        longest = NULL;

                        len = 0;

                        for (; scan != NULL; scan = regnext(scan))

                                if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {

                                        longest = OPERAND(scan);

                                        len = strlen(OPERAND(scan));

                                }

                        r->regmust = longest;

                        r->regmlen = len;

                }

        }

        return(r);

}

/*

 - reg - regular expression, i.e. main body or parenthesized thing

 *

 * Caller must absorb opening parenthesis.

 *

 * Combining parenthesis handling with the base level of regular expression

 * is a trifle forced, but the need to tie the tails of the branches to what

 * follows makes it hard to avoid.

 */

static char *

reg(paren, flagp)

int paren;                      /* Parenthesized? */

int *flagp;

{

        register char *ret;

        register char *br;

        register char *ender;

        register int parno;

        int flags;

        *flagp = HASWIDTH;      /* Tentatively. */

        /* Make an OPEN node, if parenthesized. */

        if (paren) {

                if (regnpar >= NSUBEXP)

                        FAIL("too many ()");

                parno = regnpar;

                regnpar++;

                ret = regnode(OPEN+parno);

        } else

                ret = NULL;

        /* Pick up the branches, linking them together. */

        br = regbranch(&flags);

        if (br == NULL)

                return(NULL);

        if (ret != NULL)

                regtail(ret, br);       /* OPEN -> first. */

        else

                ret = br;

        if (!(flags&HASWIDTH))

                *flagp &= ~HASWIDTH;

        *flagp |= flags&SPSTART;

        while (*regparse == '|') {

                regparse++;

                br = regbranch(&flags);

                if (br == NULL)

                        return(NULL);

                regtail(ret, br);       /* BRANCH -> BRANCH. */

                if (!(flags&HASWIDTH))

                        *flagp &= ~HASWIDTH;

                *flagp |= flags&SPSTART;

        }

        /* Make a closing node, and hook it on the end. */

        ender = regnode((paren) ? CLOSE+parno : END);

        regtail(ret, ender);

        /* Hook the tails of the branches to the closing node. */

        for (br = ret; br != NULL; br = regnext(br))

                regoptail(br, ender);

        /* Check for proper termination. */

        if (paren && *regparse++ != ')') {

                FAIL("unmatched ()");

        } else if (!paren && *regparse != '\0') {

                if (*regparse == ')') {

                        FAIL("unmatched ()");

                } else

                        FAIL("junk on end");    /* "Can't happen". */

                /* NOTREACHED */

        }

        return(ret);

}

/*

 - regbranch - one alternative of an | operator

 *

 * Implements the concatenation operator.

 */

static char *

regbranch(flagp)

int *flagp;

{

        register char *ret;

        register char *chain;

        register char *latest;

        int flags;

        *flagp = WORST;         /* Tentatively. */

        ret = regnode(BRANCH);

        chain = NULL;

        while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {

                latest = regpiece(&flags);

                if (latest == NULL)

                        return(NULL);

                *flagp |= flags&HASWIDTH;

                if (chain == NULL)      /* First piece. */

                        *flagp |= flags&SPSTART;

                else

                        regtail(chain, latest);

                chain = latest;

        }

        if (chain == NULL)      /* Loop ran zero times. */

                (void) regnode(NOTHING);

        return(ret);

}

/*

 - regpiece - something followed by possible [*+?]

 *

 * Note that the branching code sequences used for ? and the general cases

 * of * and + are somewhat optimized:  they use the same NOTHING node as

 * both the endmarker for their branch list and the body of the last branch.

 * It might seem that this node could be dispensed with entirely, but the

 * endmarker role is not redundant.

 */

static char *

regpiece(flagp)

int *flagp;

{

        register char *ret;

        register char op;

        register char *next;

        int flags;

        ret = regatom(&flags);

        if (ret == NULL)

                return(NULL);

        op = *regparse;

        if (!ISMULT(op)) {

                *flagp = flags;

                return(ret);

        }

        if (!(flags&HASWIDTH) && op != '?')

                FAIL("*+ operand could be empty");

        *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);

        if (op == '*' && (flags&SIMPLE))

                reginsert(STAR, ret);

        else if (op == '*') {

                /* Emit x* as (x&|), where & means "self". */

                reginsert(BRANCH, ret);                 /* Either x */

                regoptail(ret, regnode(BACK));          /* and loop */

                regoptail(ret, ret);                    /* back */

                regtail(ret, regnode(BRANCH));          /* or */

                regtail(ret, regnode(NOTHING));         /* null. */

        } else if (op == '+' && (flags&SIMPLE))

                reginsert(PLUS, ret);

        else if (op == '+') {

                /* Emit x+ as x(&|), where & means "self". */

                next = regnode(BRANCH);                 /* Either */

                regtail(ret, next);

                regtail(regnode(BACK), ret);            /* loop back */

                regtail(next, regnode(BRANCH));         /* or */

                regtail(ret, regnode(NOTHING));         /* null. */

        } else if (op == '?') {

                /* Emit x? as (x|) */

                reginsert(BRANCH, ret);                 /* Either x */

                regtail(ret, regnode(BRANCH));          /* or */

                next = regnode(NOTHING);                /* null. */

                regtail(ret, next);

                regoptail(ret, next);

        }

        regparse++;

        if (ISMULT(*regparse))

                FAIL("nested *?+");

        return(ret);

}

/*

 - regatom - the lowest level

 *

 * Optimization:  gobbles an entire sequence of ordinary characters so that

 * it can turn them into a single node, which is smaller to store and

 * faster to run.  Backslashed characters are exceptions, each becoming a

 * separate node; the code is simpler that way and it's not worth fixing.

 */

static char *

regatom(flagp)

int *flagp;

{

        register char *ret;

        int flags;

        *flagp = WORST;         /* Tentatively. */

        switch (*regparse++) {

        case '^':

                ret = regnode(BOL);

                break;

        case '$':

                ret = regnode(EOL);

                break;

        case '.':

                ret = regnode(ANY);

                *flagp |= HASWIDTH|SIMPLE;

                break;

        case '[': {

                        register int class;

                        register int classend;

                        if (*regparse == '^') { /* Complement of range. */

                                ret = regnode(ANYBUT);

                                regparse++;

                        } else

                                ret = regnode(ANYOF);

                        if (*regparse == ']' || *regparse == '-')

                                regc(*regparse++);

                        while (*regparse != '\0' && *regparse != ']') {

                                if (*regparse == '-') {

                                        regparse++;

                                        if (*regparse == ']' || *regparse == '\0')

                                                regc('-');

                                        else {

                                                class = UCHARAT(regparse-2)+1;

                                                classend = UCHARAT(regparse);

                                                if (class > classend+1)

                                                        FAIL("invalid [] range");

                                                for (; class <= classend; class++)

                                                        regc(class);

                                                regparse++;

                                        }

                                } else

                                        regc(*regparse++);

                        }

                        regc('\0');

                        if (*regparse != ']')

                                FAIL("unmatched []");

                        regparse++;

                        *flagp |= HASWIDTH|SIMPLE;

                }

                break;

        case '(':

                ret = reg(1, &flags);

                if (ret == NULL)

                        return(NULL);

                *flagp |= flags&(HASWIDTH|SPSTART);

                break;

        case '\0':

        case '|':

        case ')':

                FAIL("internal urp");   /* Supposed to be caught earlier. */

                break;

        case '?':

        case '+':

        case '*':

                FAIL("?+* follows nothing");

                break;

        case '\\':

                if (*regparse == '\0')

                        FAIL("trailing \\");

                ret = regnode(EXACTLY);

                regc(*regparse++);

                regc('\0');

                *flagp |= HASWIDTH|SIMPLE;

                break;

        default: {

                        register int len;

                        register char ender;

                        regparse--;

                        len = strcspn(regparse, META);

                        if (len <= 0)

                                FAIL("internal disaster");

                        ender = *(regparse+len);

                        if (len > 1 && ISMULT(ender))

                                len--;          /* Back off clear of ?+* operand. */

                        *flagp |= HASWIDTH;

                        if (len == 1)

                                *flagp |= SIMPLE;

                        ret = regnode(EXACTLY);

                        while (len > 0) {

                                regc(*regparse++);

                                len--;

                        }

                        regc('\0');

                }

                break;

        }

        return(ret);

}

/*

 - regnode - emit a node

 */

static char *                   /* Location. */

regnode(op)

char op;

{

        register char *ret;

        register char *ptr;

        ret = regcode;

        if (ret == &regdummy) {

                regsize += 3;

                return(ret);

        }

        ptr = ret;

        *ptr++ = op;

        *ptr++ = '\0';          /* Null "next" pointer. */

        *ptr++ = '\0';

        regcode = ptr;

        return(ret);

}

/*

 - regc - emit (if appropriate) a byte of code

 */

static void

regc(b)

char b;

{

        if (regcode != &regdummy)

                *regcode++ = b;

        else

                regsize++;

}

/*

 - reginsert - insert an operator in front of already-emitted operand

 *

 * Means relocating the operand.

 */

static void

reginsert(op, opnd)

char op;

char *opnd;

{

        register char *src;

        register char *dst;

        register char *place;

        if (regcode == &regdummy) {

                regsize += 3;

                return;

        }

        src = regcode;

        regcode += 3;

        dst = regcode;

        while (src > opnd)

                *--dst = *--src;

        place = opnd;           /* Op node, where operand used to be. */

        *place++ = op;

        *place++ = '\0';

        *place++ = '\0';

}

/*

 - regtail - set the next-pointer at the end of a node chain

 */

static void

regtail(p, val)

char *p;

char *val;

{

        register char *scan;

        register char *temp;

        register int offset;

        if (p == &regdummy)

                return;

        /* Find last node. */

        scan = p;

        for (;;) {

                temp = regnext(scan);

                if (temp == NULL)

                        break;

                scan = temp;

        }

        if (OP(scan) == BACK)

                offset = scan - val;

        else

                offset = val - scan;

        *(scan+1) = (offset>>8)&0377;

        *(scan+2) = offset&0377;

}

/*

 - regoptail - regtail on operand of first argument; nop if operandless

 */

static void

regoptail(p, val)

char *p;

char *val;

{

        /* "Operandless" and "op != BRANCH" are synonymous in practice. */

        if (p == NULL || p == &regdummy || OP(p) != BRANCH)

                return;

        regtail(OPERAND(p), val);

}

/*

 * regexec and friends

 */

/*

 * Global work variables for regexec().

 */

static char *reginput;          /* String-input pointer. */

static char *regbol;            /* Beginning of input, for ^ check. */

static char **regstartp;        /* Pointer to startp array. */

static char **regendp;          /* Ditto for endp. */

/*

 * Forwards.

 */

STATIC int regtry();

STATIC int regmatch();

STATIC int regrepeat();

#ifdef DEBUG

int regnarrate = 0;

void regdump();

STATIC char *regprop();

#endif

/*

 - regexec - match a regexp against a string

 */

int

regexec(prog, string)