summaryrefslogtreecommitdiffstats
path: root/generic/regexp.c
diff options
context:
space:
mode:
authorstanton <stanton>1999-04-16 00:46:29 (GMT)
committerstanton <stanton>1999-04-16 00:46:29 (GMT)
commit97464e6cba8eb0008cf2727c15718671992b913f (patch)
treece9959f2747257d98d52ec8d18bf3b0de99b9535 /generic/regexp.c
parenta8c96ddb94d1483a9de5e340b740cb74ef6cafa7 (diff)
downloadtcl-97464e6cba8eb0008cf2727c15718671992b913f.zip
tcl-97464e6cba8eb0008cf2727c15718671992b913f.tar.gz
tcl-97464e6cba8eb0008cf2727c15718671992b913f.tar.bz2
merged tcl 8.1 branch back into the main trunk
Diffstat (limited to 'generic/regexp.c')
-rw-r--r--generic/regexp.c1333
1 files changed, 0 insertions, 1333 deletions
diff --git a/generic/regexp.c b/generic/regexp.c
deleted file mode 100644
index 8d95c45..0000000
--- a/generic/regexp.c
+++ /dev/null
@@ -1,1333 +0,0 @@
-/*
- * 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.2 1998/09/14 18:39:57 stanton 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 == '^') { /* 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);
- /* 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;
-}