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.

 *

 * *** NOTE: this code has been altered slightly for use in Tcl. ***

 * *** The only change is to use ckalloc and ckfree instead of   ***

 * *** malloc and free.                                          ***

 * *** and again for Expect!!! - DEL

 * *** More minor corrections stolen from tcl7.5p1/regexp.c - DEL

 */

#include "tcl.h"

#include "expect_cf.h"

#include "exp_prog.h"

#include "tclRegexp.h"

#include "exp_regexp.h"

#include "string.h"

#define NOTSTATIC       /* was at one time, but Expect needs access */

/*

 * 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   (OPEN+NSUBEXP)  /* 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. */

/*

 * The first byte of the regexp internal "program" is actually this magic

 * number; the start node begins in the second byte.

 */

#define MAGIC   0234

/*

 * 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 originally appeared here - DEL */

/*

 - 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 = 0;

        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 clss;

                        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 {

                                                clss = UCHARAT(regparse-2)+1;

                                                classend = UCHARAT(regparse);

                                                if (clss > classend+1)

                                                        FAIL("invalid [] range");

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

                                                        regc((char)clss);

                                                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. */

                /* NOTREACHED */

                break;

        case '?':

        case '+':

        case '*':

                FAIL("?+* follows nothing");

                /* NOTREACHED */

                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)

int op;

{

        register char *ret;

        register char *ptr;

        ret = regcode;

        if (ret == &regdummy) {

                regsize += 3;

                return(ret);

        }

        ptr = ret;

        *ptr++ = (char)op;

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

        *ptr++ = '\0';

        regcode = ptr;

        return(ret);

}

/*

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

 */

static void

regc(b)

int b;

{

        if (regcode != &regdummy)

                *regcode++ = (char)b;

        else

                regsize++;

}

/*

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

 *

 * Means relocating the operand.

 */

static void

reginsert(op, opnd)

int 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++ = (char)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) = (char)(offset>>8)&0377;

        *(scan+2) = (char)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. */

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

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

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

/*

 * Forwards.

 */

NOTSTATIC int regtry();

STATIC int regmatch();

STATIC int regrepeat();

#ifdef DEBUG

int regnarrate = 0;

void regdump();

STATIC char *regprop();

#endif

#if 0

/*

 - regexec - match a regexp against a string

 */

int

regexec(prog, string, stringlength, matchlength)

register regexp *prog;

register char *string;  /* note: CURRENTLY ASSUMED TO BE NULL-TERMINATED!!! */

int stringlength;       /* length of string */

int *matchlength;       /* number of chars matched (or to be skipped) */

                        /* set when MATCH or CANT_MATCH */

{

        register char *s;

        extern char *strchr();

        /* Be paranoid... */

        if (prog == NULL || string == NULL) {

                regerror("NULL parameter");

                return(EXP_TCLERROR);

        }

        /* Check validity of program. */

        if (UCHARAT(prog->program) != MAGIC) {

                regerror("corrupted program");

                return(EXP_KM_ERROR);

        }

#if THIS_RUINS_EXP

/* no need for this shortcut anyway */

        /* If there is a "must appear" string, look for it. */

        if (prog->regmust != NULL) {

                s = string;

                while ((s = strchr(s, prog->regmust[0])) != NULL) {

                        if (strncmp(s, prog->regmust, prog->regmlen) == 0)

                                break;  /* Found it. */

                        s++;

                }

                if (s == NULL)  /* Not present. */

                        return(0);

        }

#endif

        /* Mark beginning of line for ^ . */

        regbol = string;

        /* Simplest case:  anchored match need be tried only once. */

        if (prog->reganch) {

                int r = regtry(prog,string,matchlength);

                if (r == CANT_MATCH) *matchlength = stringlength;

                return(r);

        }

        /* Messy cases:  unanchored match. */

        s = string;

        if (prog->regstart != '\0') {

                register char *s2 = s;

                /* We know what char it must start with. */

                while (1) {

                        int r;

                        s2 = strchr(s2,prog->regstart);

                        if (s2 == 0) {

                                *matchlength = stringlength;

                                return(CANT_MATCH);

                        }

                        r = regtry(prog,s2,matchlength);

                        if (r == CANT_MATCH) {

                                s2++;

                                continue;

                        }

                        if (s2 == s) return(r);