URL https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k

[/] [or1k/] [trunk/] [insight/] [tcl/] [generic/] [regexp.c] - Blame information for rev 1780

Go to most recent revision | Details | Compare with Previous | View Log

/*
 * TclRegComp and TclRegExec -- TclRegSub is 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: ***
 * *** 1. Use ckalloc and ckfree instead of  malloc and free.    ***
 * *** 2. Add extra argument to regexp to specify the real       ***
 * ***    start of the string separately from the start of the   ***
 * ***    current search. This is needed to search for multiple  ***
 * ***    matches within a string.                               ***
 * *** 3. Names have been changed, e.g. from regcomp to          ***
 * ***    TclRegComp, to avoid clashes with other                ***
 * ***    regexp implementations used by applications.           ***
 * *** 4. Added errMsg declaration and TclRegError procedure     ***
 * *** 5. Various lint-like things, such as casting arguments    ***
 * ***    in procedure calls.                                    ***
 *
 * *** NOTE: This code has been altered for use in MT-Sturdy Tcl ***
 * *** 1. All use of static variables has been changed to access ***
 * ***    fields of a structure.                                 ***
 * *** 2. This in addition to changes to TclRegError makes the   ***
 * ***    code multi-thread safe.                                ***
 *
 * RCS: @(#) $Id: regexp.c,v 1.1.1.1 2002-01-16 10:25:25 markom Exp $
 */
 
#include "tclInt.h"
#include "tclPort.h"
 
/*
 * The variable below is set to NULL before invoking regexp functions
 * and checked after those functions.  If an error occurred then TclRegError
 * will set the variable to point to a (static) error message.  This
 * mechanism unfortunately does not support multi-threading, but the
 * procedures TclRegError and TclGetRegError can be modified to use
 * thread-specific storage for the variable and thereby make the code
 * thread-safe.
 */
 
static char *errMsg = NULL;
 
/*
 * 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 TclRegComp() 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 TclRegExec() needs it and TclRegComp() 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) { TclRegError(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 TclRegComp().
 */
struct regcomp_state  {
    char *regparse;             /* Input-scan pointer. */
    int regnpar;                /* () count. */
    char *regcode;              /* Code-emit pointer; &regdummy = don't. */
    long regsize;               /* Code size. */
};
 
static char regdummy;
 
/*
 * 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 TclRegComp()'s friends.
 */
 
static char *           reg _ANSI_ARGS_((int paren, int *flagp,
                            struct regcomp_state *rcstate));
static char *           regatom _ANSI_ARGS_((int *flagp,
                            struct regcomp_state *rcstate));
static char *           regbranch _ANSI_ARGS_((int *flagp,
                            struct regcomp_state *rcstate));
static void             regc _ANSI_ARGS_((int b,
                            struct regcomp_state *rcstate));
static void             reginsert _ANSI_ARGS_((int op, char *opnd,
                            struct regcomp_state *rcstate));
static char *           regnext _ANSI_ARGS_((char *p));
static char *           regnode _ANSI_ARGS_((int op,
                            struct regcomp_state *rcstate));
static void             regoptail _ANSI_ARGS_((char *p, char *val));
static char *           regpiece _ANSI_ARGS_((int *flagp,
                            struct regcomp_state *rcstate));
static void             regtail _ANSI_ARGS_((char *p, char *val));
 
#ifdef STRCSPN
static int strcspn _ANSI_ARGS_((char *s1, char *s2));
#endif
 
/*
 - TclRegComp - 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 *
TclRegComp(exp)
char *exp;
{
        register regexp *r;
        register char *scan;
        register char *longest;
        register int len;
        int flags;
        struct regcomp_state state;
        struct regcomp_state *rcstate= &state;
 
        if (exp == NULL)
                FAIL("NULL argument");
 
        /* First pass: determine size, legality. */
        rcstate->regparse = exp;
        rcstate->regnpar = 1;
        rcstate->regsize = 0L;
        rcstate->regcode = &regdummy;
        regc(MAGIC, rcstate);
        if (reg(0, &flags, rcstate) == NULL)
                return(NULL);
 
        /* Small enough for pointer-storage convention? */
        if (rcstate->regsize >= 32767L)         /* Probably could be 65535L. */
                FAIL("regexp too big");
 
        /* Allocate space. */
        r = (regexp *)ckalloc(sizeof(regexp) + (unsigned)rcstate->regsize);
        if (r == NULL)
                FAIL("out of space");
 
        /* Second pass: emit code. */
        rcstate->regparse = exp;
        rcstate->regnpar = 1;
        rcstate->regcode = r->program;
        regc(MAGIC, rcstate);
        if (reg(0, &flags, rcstate) == 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 && ((int) 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, rcstate)
int paren;                      /* Parenthesized? */
int *flagp;
struct regcomp_state *rcstate;
{
        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 (rcstate->regnpar >= NSUBEXP)
                        FAIL("too many ()");
                parno = rcstate->regnpar;
                rcstate->regnpar++;
                ret = regnode(OPEN+parno,rcstate);
        } else
                ret = NULL;
 
        /* Pick up the branches, linking them together. */
        br = regbranch(&flags,rcstate);
        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 (*rcstate->regparse == '|') {
                rcstate->regparse++;
                br = regbranch(&flags,rcstate);
                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,rcstate);
        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 && *rcstate->regparse++ != ')') {
                FAIL("unmatched ()");
        } else if (!paren && *rcstate->regparse != '\0') {
                if (*rcstate->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, rcstate)
int *flagp;
struct regcomp_state *rcstate;
{
        register char *ret;
        register char *chain;
        register char *latest;
        int flags;
 
        *flagp = WORST;         /* Tentatively. */
 
        ret = regnode(BRANCH,rcstate);
        chain = NULL;
        while (*rcstate->regparse != '\0' && *rcstate->regparse != '|' &&
                                *rcstate->regparse != ')') {
                latest = regpiece(&flags, rcstate);
                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,rcstate);
 
        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, rcstate)
int *flagp;
struct regcomp_state *rcstate;
{
        register char *ret;
        register char op;
        register char *next;
        int flags;
 
        ret = regatom(&flags,rcstate);
        if (ret == NULL)
                return(NULL);
 
        op = *rcstate->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, rcstate);
        else if (op == '*') {
                /* Emit x* as (x&|), where & means "self". */
                reginsert(BRANCH, ret, rcstate);                        /* Either x */
                regoptail(ret, regnode(BACK,rcstate));          /* and loop */
                regoptail(ret, ret);                    /* back */
                regtail(ret, regnode(BRANCH,rcstate));          /* or */
                regtail(ret, regnode(NOTHING,rcstate));         /* null. */
        } else if (op == '+' && (flags&SIMPLE))
                reginsert(PLUS, ret, rcstate);
        else if (op == '+') {
                /* Emit x+ as x(&|), where & means "self". */
                next = regnode(BRANCH,rcstate);                 /* Either */
                regtail(ret, next);
                regtail(regnode(BACK,rcstate), ret);            /* loop back */
                regtail(next, regnode(BRANCH,rcstate));         /* or */
                regtail(ret, regnode(NOTHING,rcstate));         /* null. */
        } else if (op == '?') {
                /* Emit x? as (x|) */
                reginsert(BRANCH, ret, rcstate);                        /* Either x */
                regtail(ret, regnode(BRANCH,rcstate));          /* or */
                next = regnode(NOTHING,rcstate);                /* null. */
                regtail(ret, next);
                regoptail(ret, next);
        }
        rcstate->regparse++;
        if (ISMULT(*rcstate->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, rcstate)
int *flagp;
struct regcomp_state *rcstate;
{
        register char *ret;
        int flags;
 
        *flagp = WORST;         /* Tentatively. */
 
        switch (*rcstate->regparse++) {
        case '^':
                ret = regnode(BOL,rcstate);
                break;
        case '$':
                ret = regnode(EOL,rcstate);
                break;
        case '.':
                ret = regnode(ANY,rcstate);
                *flagp |= HASWIDTH|SIMPLE;
                break;
        case '[': {
                        register int clss;
                        register int classend;
 
                        if(rcstate->regparse[0] != '\\' &&
                           rcstate->regparse[0] != '^' &&
                           rcstate->regparse[1] == ']') {
                                ret = regnode(EXACTLY,rcstate);
                                regc(*rcstate->regparse++,rcstate);
                                regc('\0',rcstate);
                                rcstate->regparse++;
                                *flagp |= HASWIDTH|SIMPLE;
                                break;
                        }
                        if (*rcstate->regparse == '^') {        /* Complement of range. */
                                ret = regnode(ANYBUT,rcstate);
                                rcstate->regparse++;
                        } else
                                ret = regnode(ANYOF,rcstate);
                        if (*rcstate->regparse == ']' || *rcstate->regparse == '-')
                                regc(*rcstate->regparse++,rcstate);
                        while (*rcstate->regparse != '\0' && *rcstate->regparse != ']') {
                                if (*rcstate->regparse == '-') {
                                        rcstate->regparse++;
                                        if (*rcstate->regparse == ']' || *rcstate->regparse == '\0')
                                                regc('-',rcstate);
                                        else {
                                                clss = UCHARAT(rcstate->regparse-2)+1;
                                                classend = UCHARAT(rcstate->regparse);
                                                if (clss > classend+1)
                                                        FAIL("invalid [] range");
                                                for (; clss <= classend; clss++)
                                                        regc((char)clss,rcstate);
                                                rcstate->regparse++;
                                        }
                                } else
                                        regc(*rcstate->regparse++,rcstate);
                        }
                        regc('\0',rcstate);
                        if (*rcstate->regparse != ']')
                                FAIL("unmatched []");
                        rcstate->regparse++;
                        *flagp |= HASWIDTH|SIMPLE;
                }
                break;
        case '(':
                ret = reg(1, &flags, rcstate);
                if (ret == NULL)
                        return(NULL);
                *flagp |= flags&(HASWIDTH|SPSTART);
                break;
        case '\0':
        case '|':
        case ')':
                FAIL("internal urp");   /* Supposed to be caught earlier. */
                /* NOTREACHED */
        case '?':
        case '+':
        case '*':
                FAIL("?+* follows nothing");
                /* NOTREACHED */
        case '\\':
                if (*rcstate->regparse == '\0')
                        FAIL("trailing \\");
                ret = regnode(EXACTLY,rcstate);
                regc(*rcstate->regparse++,rcstate);
                regc('\0',rcstate);
                *flagp |= HASWIDTH|SIMPLE;
                break;
        default: {
                        register int len;
                        register char ender;
 
                        rcstate->regparse--;
                        len = strcspn(rcstate->regparse, META);
                        if (len <= 0)
                                FAIL("internal disaster");
                        ender = *(rcstate->regparse+len);
                        if (len > 1 && ISMULT(ender))
                                len--;          /* Back off clear of ?+* operand. */
                        *flagp |= HASWIDTH;
                        if (len == 1)
                                *flagp |= SIMPLE;
                        ret = regnode(EXACTLY,rcstate);
                        while (len > 0) {
                                regc(*rcstate->regparse++,rcstate);
                                len--;
                        }
                        regc('\0',rcstate);
                }
                break;
        }
 
        return(ret);
}
 
/*
 - regnode - emit a node
 */
static char *                   /* Location. */
regnode(op, rcstate)
int op;
struct regcomp_state *rcstate;
{
        register char *ret;
        register char *ptr;
 
        ret = rcstate->regcode;
        if (ret == &regdummy) {
                rcstate->regsize += 3;
                return(ret);
        }
 
        ptr = ret;
        *ptr++ = (char)op;
        *ptr++ = '\0';          /* Null "next" pointer. */
        *ptr++ = '\0';
        rcstate->regcode = ptr;
 
        return(ret);
}
 
/*
 - regc - emit (if appropriate) a byte of code
 */
static void
regc(b, rcstate)
int b;
struct regcomp_state *rcstate;
{
        if (rcstate->regcode != &regdummy)
                *rcstate->regcode++ = (char)b;
        else
                rcstate->regsize++;
}
 
/*
 - reginsert - insert an operator in front of already-emitted operand
 *
 * Means relocating the operand.
 */
static void
reginsert(op, opnd, rcstate)
int op;
char *opnd;
struct regcomp_state *rcstate;
{
        register char *src;
        register char *dst;
        register char *place;
 
        if (rcstate->regcode == &regdummy) {
                rcstate->regsize += 3;
                return;
        }
 
        src = rcstate->regcode;
        rcstate->regcode += 3;
        dst = rcstate->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);
}
 
/*
 * TclRegExec and friends
 */
 
/*
 * Global work variables for TclRegExec().
 */
struct regexec_state  {
    char *reginput;             /* String-input pointer. */
    char *regbol;               /* Beginning of input, for ^ check. */
    char **regstartp;   /* Pointer to startp array. */
    char **regendp;             /* Ditto for endp. */
};
 
/*
 * Forwards.
 */
static int              regtry _ANSI_ARGS_((regexp *prog, char *string,
                            struct regexec_state *restate));
static int              regmatch _ANSI_ARGS_((char *prog,
                            struct regexec_state *restate));
static int              regrepeat _ANSI_ARGS_((char *p,
                            struct regexec_state *restate));
 
#ifdef DEBUG
int regnarrate = 0;
void regdump _ANSI_ARGS_((regexp *r));
static char *regprop _ANSI_ARGS_((char *op));
#endif
 
/*
 - TclRegExec - match a regexp against a string
 */
int
TclRegExec(prog, string, start)
register regexp *prog;
register char *string;
char *start;
{
        register char *s;
        struct regexec_state state;
        struct regexec_state *restate= &state;
 
        /* Be paranoid... */
        if (prog == NULL || string == NULL) {
                TclRegError("NULL parameter");
                return(0);
        }
 
        /* Check validity of program. */
        if (UCHARAT(prog->program) != MAGIC) {
                TclRegError("corrupted program");
                return(0);
        }
 
        /* 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, (size_t) prog->regmlen)
                            == 0)
                                break;  /* Found it. */
                        s++;
                }
                if (s == NULL)  /* Not present. */
                        return(0);
        }
 
        /* Mark beginning of line for ^ . */
        restate->regbol = start;
 
        /* Simplest case:  anchored match need be tried only once. */
        if (prog->reganch)
                return(regtry(prog, string, restate));
 
        /* Messy cases:  unanchored match. */
        s = string;
        if (prog->regstart != '\0')
                /* We know what char it must start with. */
                while ((s = strchr(s, prog->regstart)) != NULL) {
                        if (regtry(prog, s, restate))
                                return(1);
                        s++;
                }
        else
                /* We don't -- general case. */
                do {
                        if (regtry(prog, s, restate))
                                return(1);
                } while (*s++ != '\0');
 
        /* Failure. */
        return(0);
}
 
/*
 - regtry - try match at specific point
 */
static int                      /* 0 failure, 1 success */
regtry(prog, string, restate)
regexp *prog;
char *string;
struct regexec_state *restate;
{
        register int i;
        register char **sp;
        register char **ep;
 
        restate->reginput = string;
        restate->regstartp = prog->startp;
        restate->regendp = prog->endp;
 
        sp = prog->startp;
        ep = prog->endp;
        for (i = NSUBEXP; i > 0; i--) {
                *sp++ = NULL;
                *ep++ = NULL;
        }
        if (regmatch(prog->program + 1,restate)) {
                prog->startp[0] = string;
                prog->endp[0] = restate->reginput;
                return(1);
        } else
                return(0);
}
 
/*
 - regmatch - main matching routine
 *
 * Conceptually the strategy is simple:  check to see whether the current
 * node matches, call self recursively to see whether the rest matches,
 * and then act accordingly.  In practice we make some effort to avoid
 * recursion, in particular by going through "ordinary" nodes (that don't
 * need to know whether the rest of the match failed) by a loop instead of
 * by recursion.
 */
static int                      /* 0 failure, 1 success */
regmatch(prog, restate)
char *prog;
struct regexec_state *restate;
{
    register char *scan;        /* Current node. */
    char *next;         /* Next node. */
 
    scan = prog;
#ifdef DEBUG
    if (scan != NULL && regnarrate)
        fprintf(stderr, "%s(\n", regprop(scan));
#endif
    while (scan != NULL) {
#ifdef DEBUG
        if (regnarrate)
            fprintf(stderr, "%s...\n", regprop(scan));
#endif
        next = regnext(scan);
 
        switch (OP(scan)) {
            case BOL:
                if (restate->reginput != restate->regbol) {
                    return 0;
                }
                break;
            case EOL:
                if (*restate->reginput != '\0') {
                    return 0;
                }
                break;
            case ANY:
                if (*restate->reginput == '\0') {
                    return 0;
                }
                restate->reginput++;
                break;
            case EXACTLY: {
                register int len;
                register char *opnd;
 
                opnd = OPERAND(scan);
                /* Inline the first character, for speed. */
                if (*opnd != *restate->reginput) {
                    return 0 ;
                }
                len = strlen(opnd);
                if (len > 1 && strncmp(opnd, restate->reginput, (size_t) len)
                        != 0) {
                    return 0;
                }
                restate->reginput += len;
                break;
            }
            case ANYOF:
                if (*restate->reginput == '\0'
                        || strchr(OPERAND(scan), *restate->reginput) == NULL) {
                    return 0;
                }
                restate->reginput++;
                break;
            case ANYBUT:
                if (*restate->reginput == '\0'
                        || strchr(OPERAND(scan), *restate->reginput) != NULL) {
                    return 0;
                }
                restate->reginput++;
                break;
            case NOTHING:
                break;
            case BACK:
                break;
            case OPEN+1:
            case OPEN+2:
            case OPEN+3:
            case OPEN+4:
            case OPEN+5:
            case OPEN+6:
            case OPEN+7:
            case OPEN+8:
            case OPEN+9: {
                register int no;
                register char *save;
 
        doOpen:
                no = OP(scan) - OPEN;
                save = restate->reginput;
 
                if (regmatch(next,restate)) {
                    /*
                     * Don't set startp if some later invocation of the
                     * same parentheses already has.
                     */
                    if (restate->regstartp[no] == NULL) {
                        restate->regstartp[no] = save;
                    }
                    return 1;
                } else {
                    return 0;
                }
            }
            case CLOSE+1:
            case CLOSE+2:
            case CLOSE+3:
            case CLOSE+4:
            case CLOSE+5:
            case CLOSE+6:
            case CLOSE+7:
            case CLOSE+8:
            case CLOSE+9: {
                register int no;
                register char *save;
 
        doClose:
                no = OP(scan) - CLOSE;
                save = restate->reginput;
 
                if (regmatch(next,restate)) {
                                /*
                                 * Don't set endp if some later
                                 * invocation of the same parentheses
                                 * already has.
                                 */
                    if (restate->regendp[no] == NULL)
                        restate->regendp[no] = save;
                    return 1;
                } else {
                    return 0;
                }
            }
            case BRANCH: {
                register char *save;
 
                if (OP(next) != BRANCH) { /* No choice. */
                    next = OPERAND(scan); /* Avoid recursion. */
                } else {
                    do {
                        save = restate->reginput;
                        if (regmatch(OPERAND(scan),restate))
                            return(1);
                        restate->reginput = save;
                        scan = regnext(scan);
                    } while (scan != NULL && OP(scan) == BRANCH);
                    return 0;
                }
                break;
            }
            case STAR:
            case PLUS: {
                register char nextch;
                register int no;
                register char *save;
                register int min;
 
                /*
                 * Lookahead to avoid useless match attempts
                 * when we know what character comes next.
                 */
                nextch = '\0';
                if (OP(next) == EXACTLY)
                    nextch = *OPERAND(next);
                min = (OP(scan) == STAR) ? 0 : 1;
                save = restate->reginput;
                no = regrepeat(OPERAND(scan),restate);
                while (no >= min) {
                    /* If it could work, try it. */
                    if (nextch == '\0' || *restate->reginput == nextch)
                        if (regmatch(next,restate))
                            return(1);
                    if (nextch != '\0' && no > (min + 1)) {
                        char tmp = *(save + no);
                        char *p;
                        *(save + no) = 0;
                        p = strrchr(save, nextch);
                        *(save + no) = tmp;
                        if (p != NULL)
                            no = p - save + 1;
                        else
                            no = 0;
                    }
 
                    /* Couldn't or didn't -- back up. */
                    no--;
                    restate->reginput = save + no;
                }
                return(0);
            }
            case END:
                return(1);      /* Success! */
            default:
                if (OP(scan) > OPEN && OP(scan) < OPEN+NSUBEXP) {
                    goto doOpen;
                } else if (OP(scan) > CLOSE && OP(scan) < CLOSE+NSUBEXP) {
                    goto doClose;
                }
                TclRegError("memory corruption");
                return 0;
        }
 
        scan = next;
    }
 
    /*
     * We get here only if there's trouble -- normally "case END" is
     * the terminating point.
     */
    TclRegError("corrupted pointers");
    return(0);
}
 
/*
 - regrepeat - repeatedly match something simple, report how many
 */
static int
regrepeat(p, restate)
char *p;
struct regexec_state *restate;
{
        register int count = 0;
        register char *scan;
        register char *opnd;
 
        scan = restate->reginput;
        opnd = OPERAND(p);
        switch (OP(p)) {
        case ANY:
                count = strlen(scan);
                scan += count;
                break;
        case EXACTLY:
                while (*opnd == *scan) {
                        count++;
                        scan++;
                }
                break;
        case ANYOF:
                while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
                        count++;
                        scan++;
                }
                break;
        case ANYBUT:
                while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
                        count++;
                        scan++;
                }
                break;
        default:                /* Oh dear.  Called inappropriately. */
                TclRegError("internal foulup");
                count = 0;       /* Best compromise. */
                break;
        }
        restate->reginput = scan;
 
        return(count);
}
 
/*
 - regnext - dig the "next" pointer out of a node
 */
static char *
regnext(p)
register char *p;
{
        register int offset;
 
        if (p == &regdummy)
                return(NULL);
 
        offset = NEXT(p);
        if (offset == 0)
                return(NULL);
 
        if (OP(p) == BACK)
                return(p-offset);
        else
                return(p+offset);
}
 
#ifdef DEBUG
 
static char *regprop();
 
/*
 - regdump - dump a regexp onto stdout in vaguely comprehensible form
 */
void
regdump(r)
regexp *r;
{
        register char *s;
        register char op = EXACTLY;     /* Arbitrary non-END op. */
        register char *next;
 
 
        s = r->program + 1;
        while (op != END) {     /* While that wasn't END last time... */
                op = OP(s);
                printf("%2d%s", s-r->program, regprop(s));      /* Where, what. */
                next = regnext(s);
                if (next == NULL)               /* Next ptr. */
                        printf("(0)");
                else
                        printf("(%d)", (s-r->program)+(next-s));
                s += 3;
                if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
                        /* Literal string, where present. */
                        while (*s != '\0') {
                                putchar(*s);
                                s++;
                        }
                        s++;
                }
                putchar('\n');
        }
 
        /* Header fields of interest. */
        if (r->regstart != '\0')
                printf("start `%c' ", r->regstart);
        if (r->reganch)
                printf("anchored ");
        if (r->regmust != NULL)
                printf("must have \"%s\"", r->regmust);
        printf("\n");
}
 
/*
 - regprop - printable representation of opcode
 */
static char *
regprop(op)
char *op;
{
        register char *p;
        static char buf[50];
 
        (void) strcpy(buf, ":");
 
        switch (OP(op)) {
        case BOL:
                p = "BOL";
                break;
        case EOL:
                p = "EOL";
                break;
        case ANY:
                p = "ANY";
                break;
        case ANYOF:
                p = "ANYOF";
                break;
        case ANYBUT:
                p = "ANYBUT";
                break;
        case BRANCH:
                p = "BRANCH";
                break;
        case EXACTLY:
                p = "EXACTLY";
                break;
        case NOTHING:
                p = "NOTHING";
                break;
        case BACK:
                p = "BACK";
                break;
        case END:
                p = "END";
                break;
        case OPEN+1:
        case OPEN+2:
        case OPEN+3:
        case OPEN+4:
        case OPEN+5:
        case OPEN+6:
        case OPEN+7:
        case OPEN+8:
        case OPEN+9:
                sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
                p = NULL;
                break;
        case CLOSE+1:
        case CLOSE+2:
        case CLOSE+3:
        case CLOSE+4:
        case CLOSE+5:
        case CLOSE+6:
        case CLOSE+7:
        case CLOSE+8:
        case CLOSE+9:
                sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
                p = NULL;
                break;
        case STAR:
                p = "STAR";
                break;
        case PLUS:
                p = "PLUS";
                break;
        default:
                if (OP(op) > OPEN && OP(op) < OPEN+NSUBEXP) {
                    sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
                    p = NULL;
                    break;
                } else if (OP(op) > CLOSE && OP(op) < CLOSE+NSUBEXP) {
                    sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
                    p = NULL;
                } else {
                    TclRegError("corrupted opcode");
                }
                break;
        }
        if (p != NULL)
                (void) strcat(buf, p);
        return(buf);
}
#endif
 
/*
 * The following is provided for those people who do not have strcspn() in
 * their C libraries.  They should get off their butts and do something
 * about it; at least one public-domain implementation of those (highly
 * useful) string routines has been published on Usenet.
 */
#ifdef STRCSPN
/*
 * strcspn - find length of initial segment of s1 consisting entirely
 * of characters not from s2
 */
 
static int
strcspn(s1, s2)
char *s1;
char *s2;
{
        register char *scan1;
        register char *scan2;
        register int count;
 
        count = 0;
        for (scan1 = s1; *scan1 != '\0'; scan1++) {
                for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */
                        if (*scan1 == *scan2++)
                                return(count);
                count++;
        }
        return(count);
}
#endif
 
/*
 *----------------------------------------------------------------------
 *
 * TclRegError --
 *
 *      This procedure is invoked by the regexp code when an error
 *      occurs.  It saves the error message so it can be seen by the
 *      code that called Spencer's code.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The value of "string" is saved in "errMsg".
 *
 *----------------------------------------------------------------------
 */
 
void
TclRegError(string)
    char *string;                       /* Error message. */
{
    errMsg = string;
}
 
char *
TclGetRegError()
{
    return errMsg;
}
Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [insight/] [tcl/] [generic/] [regexp.c] - Blame information for rev 1780

Line No.	Rev	Author	Line
1	578	markom	`/*`
2			`* TclRegComp and TclRegExec -- TclRegSub is elsewhere`
3			`*`
4			`* Copyright (c) 1986 by University of Toronto.`
5			`* Written by Henry Spencer. Not derived from licensed software.`
6			`*`
7			`* Permission is granted to anyone to use this software for any`
8			`* purpose on any computer system, and to redistribute it freely,`
9			`* subject to the following restrictions:`
10			`*`
11			`* 1. The author is not responsible for the consequences of use of`
12			`* this software, no matter how awful, even if they arise`
13			`* from defects in it.`
14			`*`
15			`* 2. The origin of this software must not be misrepresented, either`
16			`* by explicit claim or by omission.`
17			`*`
18			`* 3. Altered versions must be plainly marked as such, and must not`
19			`* be misrepresented as being the original software.`
20			`*`
21			`* Beware that some of this code is subtly aware of the way operator`
22			`* precedence is structured in regular expressions. Serious changes in`
23			`* regular-expression syntax might require a total rethink.`
24			`*`
25			`* * NOTE: this code has been altered slightly for use in Tcl: *`
26			`* * 1. Use ckalloc and ckfree instead of malloc and free. *`
27			`* * 2. Add extra argument to regexp to specify the real *`
28			`* * start of the string separately from the start of the *`
29			`* * current search. This is needed to search for multiple *`
30			`* * matches within a string. *`
31			`* * 3. Names have been changed, e.g. from regcomp to *`
32			`* * TclRegComp, to avoid clashes with other *`
33			`* * regexp implementations used by applications. *`
34			`* * 4. Added errMsg declaration and TclRegError procedure *`
35			`* * 5. Various lint-like things, such as casting arguments *`
36			`* * in procedure calls. *`
37			`*`
38			`* * NOTE: This code has been altered for use in MT-Sturdy Tcl *`
39			`* * 1. All use of static variables has been changed to access *`
40			`* * fields of a structure. *`