regexp.c
上传用户:tsgydb
上传日期:2007-04-14
资源大小:10674k
文件大小:32k
- /*
- *
- * regexp.c - regular expression matching
- *
- * DESCRIPTION
- *
- * Underneath the reformatting and comment blocks which were added to
- * make it consistent with the rest of the code, you will find a
- * modified version of Henry Specer's regular expression library.
- * Henry's functions were modified to provide the minimal regular
- * expression matching, as required by P1003. Henry's code was
- * copyrighted, and copy of the copyright message and restrictions
- * are provided, verbatim, below:
- *
- * 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.
- *
- *
- * This version modified by Ian Phillipps to return pointer to terminating
- * NUL on substitution string. [ Temp mail address ex-igp@camcon.co.uk ]
- *
- * Altered by amylaar to support excompatible option and the
- * operators < and > . ( 7.Sep. 1991 )
- *
- * regsub altered by amylaar to take an additional parameter specifying
- * maximum number of bytes that can be written to the memory region
- * pointed to by dest
- *
- * Also altered by Fredrik Hubinette to handle the + operator and
- * eight-bit chars. Mars 22 1996
- *
- *
- * 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.
- *
- * AUTHORS
- *
- * Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
- * Henry Spencer, University of Torronto (henry@utzoo.edu)
- *
- * Sponsored by The USENIX Association for public distribution.
- *
- */
- /* Headers */
- #include "global.h"
- #include <ctype.h>
- #include "regexp.h"
- #ifdef __WIN__
- #include <string.h>
- #else
- #include "memory.h"
- #include "error.h"
- #endif
- /*
- * 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; ' ' 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 "nxt" pointer, possibly plus an operand. "Nxt" pointers of
- * all nodes except BRANCH implement concatenation; a "nxt" 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
- * nxt... */
- #define BACK 7 /* no Match "", "nxt" 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 WORDSTART 11 /* node matching a start of a word */
- #define WORDEND 12 /* node matching an end of a word */
- #define OPEN 20 /* no Mark this point in input as start of
- * #n. */
- /* OPEN+1 is number 1, etc. */
- #define CLOSE 30 /* no Analogous to OPEN. */
- /*
- * Opcode notes:
- *
- * BRANCH The set of branches constituting a single choice are hooked
- * together with their "nxt" pointers, since precedence prevents
- * anything being concatenated to any individual branch. The
- * "nxt" pointer of the last BRANCH in a choice points to the
- * thing following the whole choice. This is also where the
- * final "nxt" pointer of each individual branch points; each
- * branch starts with the operand node of a BRANCH node.
- *
- * BACK Normal "nxt" pointers all implicitly point forward; BACK
- * exists to make loop structures possible.
- *
- * STAR complex '*', are implemented as circular BRANCH structures
- * using BACK. Simple cases (one character per match) are
- * implemented with STAR 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 "nxt" pointer.
- * "Nxt" 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 "nxt" 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)
- /*
- * The first byte of the regexp internal "program" is actually this magic
- * number; the start node begins in the second byte.
- */
- #define MAGIC 0234
- /*
- * Utility definitions.
- */
- #ifdef __WIN__
- #define error(X,Y) fprintf(stderr, X, Y)
- #endif
- #define regerror(X) error("Regexp: %sn",X);
- #define SPECIAL 0x100
- #define LBRAC ('('|SPECIAL)
- #define RBRAC (')'|SPECIAL)
- #define ASTERIX ('*'|SPECIAL)
- #define PLUS ('+'|SPECIAL)
- #define OR_OP ('|'|SPECIAL)
- #define DOLLAR ('$'|SPECIAL)
- #define DOT ('.'|SPECIAL)
- #define CARET ('^'|SPECIAL)
- #define LSQBRAC ('['|SPECIAL)
- #define RSQBRAC (']'|SPECIAL)
- #define LSHBRAC ('<'|SPECIAL)
- #define RSHBRAC ('>'|SPECIAL)
- #define FAIL(m) { regerror(m); return(NULL); }
- #define ISMULT(c) ((c) == ASTERIX || (c)==PLUS)
- #define META "^$.[()|*+\"
- #ifndef CHARBITS
- #define CHARBITS 0xff
- #define UCHARAT(p) ((int)*(unsigned char *)(p))
- #else
- #define UCHARAT(p) ((int)*(p)&CHARBITS)
- #endif
- #define ISWORDPART(c) ( isalnum(c) || (c) == '_' )
- /*
- * Flags to be passed up and down.
- */
- #define HASWIDTH 01 /* Known never to match null string. */
- #define SIMPLE 02 /* Simple enough to be STAR operand. */
- #define SPSTART 04 /* Starts with * */
- #define WORST 0 /* Worst case. */
- #ifdef __WIN__
- #define STRCHR(A,B) strchr(A,B)
- #endif
- /*
- * Global work variables for regcomp().
- */
- static short *regparse; /* Input-scan pointer. */
- static int regnpar; /* () count. */
- static char regdummy;
- static char *regcode; /* Code-emit pointer; ®dummy = don't. */
- static long regsize; /* Code size. */
- /*
- * Forward declarations for regcomp()'s friends.
- */
- #ifndef STATIC
- #define STATIC static
- #endif
- STATIC char *reg();
- STATIC char *regbranch();
- STATIC char *regpiece();
- STATIC char *regatom();
- STATIC char *regnode();
- STATIC char *regnext();
- STATIC void regc();
- STATIC void reginsert();
- STATIC void regtail();
- STATIC void regoptail();
- /*
- - regcomp - compile a regular expression into internal code
- *
- * We can't allocate space until we know how big the compiled form will be,
- * but we can't compile it (and thus know how big it is) until we've got a
- * place to put the code. So we cheat: we compile it twice, once with code
- * generation turned off and size counting turned on, and once "for real".
- * This also means that we don't allocate space until we are sure that the
- * thing really will compile successfully, and we never have to move the
- * code and thus invalidate pointers into it. (Note that it has to be in
- * one piece because free() must be able to free it all.)
- *
- * Beware that the optimization-preparation code in here knows about some
- * of the structure of the compiled regexp.
- */
- regexp *regcomp(exp,excompat)
- char *exp;
- int excompat; /* ( ) operators like in unix ex */
- {
- register regexp *r;
- register char *scan;
- register char *longest;
- register int len;
- int flags;
- short *exp2,*dest,c;
- if (exp == (char *)NULL)
- FAIL("NULL argument");
- exp2=(short*)malloc( (strlen(exp)+1) * (sizeof(short[8])/sizeof(char[8])) );
- for ( scan=exp,dest=exp2;( c= UCHARAT(scan++)); ) {
- switch (c) {
- case '(':
- case ')':
- *dest++ = excompat ? c : c | SPECIAL;
- break;
- case '.':
- case '*':
- case '+':
- case '|':
- case '$':
- case '^':
- case '[':
- case ']':
- *dest++ = c | SPECIAL;
- break;
- case '\':
- switch ( c = *scan++ ) {
- case '(':
- case ')':
- *dest++ = excompat ? c | SPECIAL : c;
- break;
- case '<':
- case '>':
- *dest++ = c | SPECIAL;
- break;
- case '{':
- case '}':
- FAIL("sorry, unimplemented operator");
- case 'b': *dest++ = 'b'; break;
- case 't': *dest++ = 't'; break;
- case 'r': *dest++ = 'r'; break;
- default:
- *dest++ = c;
- }
- break;
- default:
- *dest++ = c;
- }
- }
- *dest=0;
- /* First pass: determine size, legality. */
- regparse = exp2;
- regnpar = 1;
- regsize = 0L;
- regcode = ®dummy;
- regc(MAGIC);
- if (reg(0, &flags) == (char *)NULL)
- return ((regexp *)NULL);
- /* Small enough for pointer-storage convention? */
- if (regsize >= 32767L) /* Probably could be 65535L. */
- FAIL("regexp too big");
- /* Allocate space. */
- r = (regexp *) malloc(sizeof(regexp) + (unsigned) regsize);
- if (r == (regexp *) NULL)
- FAIL("out of space");
- (void) bzero(r, sizeof(regexp) + (unsigned)regsize);
- /* Second pass: emit code. */
- regparse = exp2;
- regnpar = 1;
- regcode = r->program;
- regc(MAGIC);
- if (reg(0, &flags) == NULL)
- return ((regexp *) NULL);
- /* Dig out information for optimizations. */
- r->regstart = ' '; /* 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;
- }
- }
- free((char*)exp2);
- return (r);
- }
- /*
- - reg - regular expression, i.e. main body or parenthesized thing
- *
- * Caller must absorb opening parenthesis.
- *
- * Combining parenthesis handling with the base level of regular expression
- * is a trifle forced, but the need to tie the tails of the branches to what
- * follows makes it hard to avoid.
- */
- static char *reg(paren, flagp)
- int paren; /* Parenthesized? */
- int *flagp;
- {
- register char *ret;
- register char *br;
- register char *ender;
- register int parno=0; /* make gcc happy */
- 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 = (char *)NULL;
- /* Pick up the branches, linking them together. */
- br = regbranch(&flags);
- if (br == (char *)NULL)
- return ((char *)NULL);
- if (ret != (char *)NULL)
- regtail(ret, br); /* OPEN -> first. */
- else
- ret = br;
- if (!(flags & HASWIDTH))
- *flagp &= ~HASWIDTH;
- *flagp |= flags & SPSTART;
- while (*regparse == OR_OP) {
- regparse++;
- br = regbranch(&flags);
- if (br == (char *)NULL)
- return ((char *)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 != (char *)NULL; br = regnext(br))
- regoptail(br, ender);
- /* Check for proper termination. */
- if (paren && *regparse++ != RBRAC) {
- FAIL("unmatched ()");
- } else if (!paren && *regparse != ' ') {
- if (*regparse == RBRAC) {
- 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 = (char *)NULL;
- while (*regparse != ' ' && *regparse != OR_OP && *regparse != RBRAC) {
- latest = regpiece(&flags);
- if (latest == (char *)NULL)
- return ((char *)NULL);
- *flagp |= flags & HASWIDTH;
- if (chain == (char *)NULL) /* First piece. */
- *flagp |= flags & SPSTART;
- else
- regtail(chain, latest);
- chain = latest;
- }
- if (chain == (char *)NULL) /* Loop ran zero times. */
- regnode(NOTHING);
- return (ret);
- }
- /*
- - regpiece - something followed by possible [*]
- *
- * Note that the branching code sequence used for * is 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 short op;
- /* register char *nxt; */
- int flags;
- ret = regatom(&flags);
- if (ret == (char *)NULL)
- return ((char *)NULL);
- op = *regparse;
- if (!ISMULT(op)) {
- *flagp = flags;
- return (ret);
- }
- if (!(flags & HASWIDTH))
- FAIL("* or + operand could be empty");
- *flagp = (WORST | SPSTART);
- if(op == ASTERIX)
- {
- if (flags & SIMPLE)
- {
- reginsert(STAR, ret);
- }
- else
- {
- /* 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 == PLUS)
- {
- /* Emit a+ as (a&) where & means "self" /Fredrik Hubinette */
- char *tmp;
- tmp=regnode(BACK);
- reginsert(BRANCH, tmp);
- regtail(ret, tmp);
- regoptail(tmp, ret);
- regtail(ret, regnode(BRANCH));
- regtail(ret, regnode(NOTHING));
- }
- regparse++;
- if (ISMULT(*regparse))
- FAIL("nested * or +");
- 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.
- */
- static char *regatom(flagp)
- int *flagp;
- {
- register char *ret;
- int flags;
- *flagp = WORST; /* Tentatively. */
- switch (*regparse++) {
- case CARET:
- ret = regnode(BOL);
- break;
- case DOLLAR:
- ret = regnode(EOL);
- break;
- case DOT:
- ret = regnode(ANY);
- *flagp |= HASWIDTH | SIMPLE;
- break;
- case LSHBRAC:
- ret = regnode(WORDSTART);
- break;
- case RSHBRAC:
- ret = regnode(WORDEND);
- break;
- case LSQBRAC:{
- register int class;
- register int classend;
- if (*regparse == CARET) { /* Complement of range. */
- ret = regnode(ANYBUT);
- regparse++;
- } else
- ret = regnode(ANYOF);
- if (*regparse == RSQBRAC || *regparse == '-')
- regc(*regparse++);
- while (*regparse != ' ' && *regparse != RSQBRAC) {
- if (*regparse == '-') {
- regparse++;
- if (*regparse == RSQBRAC || *regparse == ' ')
- regc('-');
- else {
- class = (CHARBITS & *(regparse - 2)) + 1;
- classend = (CHARBITS & *(regparse));
- if (class > classend + 1)
- FAIL("invalid [] range");
- for (; class <= classend; class++)
- regc(class);
- regparse++;
- }
- } else
- regc(*regparse++);
- }
- regc(' ');
- if (*regparse != RSQBRAC)
- FAIL("unmatched []");
- regparse++;
- *flagp |= HASWIDTH | SIMPLE;
- }
- break;
- case LBRAC:
- ret = reg(1, &flags);
- if (ret == (char *)NULL)
- return ((char *)NULL);
- *flagp |= flags & (HASWIDTH | SPSTART);
- break;
- case ' ':
- case OR_OP:
- case RBRAC:
- FAIL("internal urp"); /* Supposed to be caught earlier. */
- case ASTERIX:
- FAIL("* follows nothingn");
- default:{
- register int len;
- register short ender;
- regparse--;
- for (len=0; regparse[len] &&
- !(regparse[len]&SPECIAL) && regparse[len] != RSQBRAC; len++) ;
- 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(' ');
- }
- break;
- }
- return (ret);
- }
- /*
- - regnode - emit a node
- */
- static char *regnode(op)
- char op;
- {
- register char *ret;
- register char *ptr;
- ret = regcode;
- if (ret == ®dummy) {
- regsize += 3;
- return (ret);
- }
- ptr = ret;
- *ptr++ = op;
- *ptr++ = ' '; /* Null "nxt" pointer. */
- *ptr++ = ' ';
- regcode = ptr;
- return (ret);
- }
- /*
- - regc - emit (if appropriate) a byte of code
- */
- static void regc(b)
- char b;
- {
- if (regcode != ®dummy)
- *regcode++ = b;
- else
- regsize++;
- }
- /*
- - reginsert - insert an operator in front of already-emitted operand
- *
- * Means relocating the operand.
- */
- static void reginsert(op, opnd)
- char op;
- char *opnd;
- {
- register char *src;
- register char *dst;
- register char *place;
- if (regcode == ®dummy) {
- regsize += 3;
- return;
- }
- src = regcode;
- regcode += 3;
- dst = regcode;
- while (src > opnd)
- *--dst = *--src;
- place = opnd; /* Op node, where operand used to be. */
- *place++ = op;
- *place++ = ' ';
- *place++ = ' ';
- }
- /*
- - 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 == ®dummy)
- return;
- /* Find last node. */
- scan = p;
- for (;;) {
- temp = regnext(scan);
- if (temp == (char *)NULL)
- break;
- scan = temp;
- }
- if (OP(scan) == BACK)
- offset = scan - val;
- else
- offset = val - scan;
- *(scan + 1) = (offset >> 8) & 0377;
- *(scan + 2) = offset & 0377;
- }
- /*
- - regoptail - regtail on operand of first argument; nop if operandless
- */
- static void regoptail(p, val)
- char *p;
- char *val;
- {
- /* "Operandless" and "op != BRANCH" are synonymous in practice. */
- if (p == (char *)NULL || p == ®dummy || OP(p) != BRANCH)
- return;
- regtail(OPERAND(p), val);
- }
- /*
- * regexec and friends
- */
- /*
- * Global work variables for regexec().
- */
- static char *reginput; /* String-input pointer. */
- static char *regbol; /* Beginning of input, for ^ check. */
- static char **regstartp; /* Pointer to startp array. */
- static char **regendp; /* Ditto for endp. */
- /*
- * Forwards.
- */
- STATIC int regtry();
- STATIC int regmatch();
- STATIC int regrepeat();
- #ifdef DEBUG
- int regnarrate = 0;
- void regdump();
- STATIC char *regprop();
- #endif
- /*
- - regexec - match a regexp against a string
- */
- int regexec(prog, string)
- register regexp *prog;
- register char *string;
- {
- register char *s;
- /* Be paranoid... */
- if (prog == (regexp *)NULL || string == (char *)NULL) {
- regerror("NULL parameter");
- return (0);
- }
- /* Check validity of program. */
- if (UCHARAT(prog->program) != MAGIC) {
- regerror("corrupted program");
- return (0);
- }
- /* If there is a "must appear" string, look for it. */
- if (prog->regmust != (char *)NULL) {
- s = string;
- while ((s = STRCHR(s, prog->regmust[0])) != (char *)NULL) {
- if (strncmp(s, prog->regmust, prog->regmlen) == 0)
- break; /* Found it. */
- s++;
- }
- if (s == (char *)NULL) /* Not present. */
- return (0);
- }
- /* Mark beginning of line for ^ . */
- regbol = string;
- /* Simplest case: anchored match need be tried only once. */
- if (prog->reganch)
- return (regtry(prog, string));
- /* Messy cases: unanchored match. */
- s = string;
- if (prog->regstart != ' ')
- /* We know what char it must start with. */
- while ((s = STRCHR(s, prog->regstart)) != (char *)NULL) {
- if (regtry(prog, s))
- return (1);
- s++;
- }
- else
- /* We don't -- general case. */
- do {
- if (regtry(prog, s))
- return (1);
- } while (*s++ != ' ');
- /* Failure. */
- return (0);
- }
- /*
- - regtry - try match at specific point
- */
- static int regtry(regexp *prog, char *string)
- {
- register int i;
- register char **sp;
- register char **ep;
- reginput = string;
- regstartp = prog->startp;
- regendp = prog->endp;
- sp = prog->startp;
- ep = prog->endp;
- for (i = NSUBEXP; i > 0; i--) {
- *sp++ = (char *)NULL;
- *ep++ = (char *)NULL;
- }
- if (regmatch(prog->program + 1)) {
- prog->startp[0] = string;
- prog->endp[0] = 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 regmatch(char *prog)
- {
- register char *scan; /* Current node. */
- char *nxt; /* nxt node. */
- scan = prog;
- #ifdef DEBUG
- if (scan != (char *)NULL && regnarrate)
- fprintf(stderr, "%s(n", regprop(scan));
- #endif
- while (scan != (char *)NULL) {
- #ifdef DEBUG
- if (regnarrate)
- fprintf(stderr, "%s...n", regprop(scan));
- #endif
- nxt = regnext(scan);
- switch (OP(scan)) {
- case BOL:
- if (reginput != regbol)
- return (0);
- break;
- case EOL:
- if (*reginput != ' ')
- return (0);
- break;
- case ANY:
- if (*reginput == ' ')
- return (0);
- reginput++;
- break;
- case WORDSTART:
- if (reginput == regbol)
- break;
- if (*reginput == ' ' ||
- ISWORDPART( *(reginput-1) ) || !ISWORDPART( *reginput ) )
- return (0);
- break;
- case WORDEND:
- if (*reginput == ' ')
- break;
- if ( reginput == regbol ||
- !ISWORDPART( *(reginput-1) ) || ISWORDPART( *reginput ) )
- return (0);
- break;
- case EXACTLY:{
- register int len;
- register char *opnd;
- opnd = OPERAND(scan);
- /* Inline the first character, for speed. */
- if (*opnd != *reginput)
- return (0);
- len = strlen(opnd);
- if (len > 1 && strncmp(opnd, reginput, len) != 0)
- return (0);
- reginput += len;
- }
- break;
- case ANYOF:
- if (*reginput == ' ' ||
- STRCHR(OPERAND(scan), *reginput) == (char *)NULL)
- return (0);
- reginput++;
- break;
- case ANYBUT:
- if (*reginput == ' ' ||
- STRCHR(OPERAND(scan), *reginput) != (char *)NULL)
- return (0);
- 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;
- no = OP(scan) - OPEN;
- save = reginput;
- if (regmatch(nxt)) {
- /*
- * Don't set startp if some later invocation of the same
- * parentheses already has.
- */
- if (regstartp[no] == (char *)NULL)
- 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;
- no = OP(scan) - CLOSE;
- save = reginput;
- if (regmatch(nxt)) {
- /*
- * Don't set endp if some later invocation of the same
- * parentheses already has.
- */
- if (regendp[no] == (char *)NULL)
- regendp[no] = save;
- return (1);
- } else
- return (0);
- }
- case BRANCH:{
- register char *save;
- if (OP(nxt) != BRANCH) /* No choice. */
- nxt = OPERAND(scan); /* Avoid recursion. */
- else {
- do {
- save = reginput;
- if (regmatch(OPERAND(scan)))
- return (1);
- reginput = save;
- scan = regnext(scan);
- } while (scan != (char *)NULL && OP(scan) == BRANCH);
- return (0);
- /* NOTREACHED */
- }
- }
- break;
- case STAR:{
- register char nextch;
- register int no;
- register char *save;
- register int minimum;
- /*
- * Lookahead to avoid useless match attempts when we know
- * what character comes next.
- */
- nextch = ' ';
- if (OP(nxt) == EXACTLY)
- nextch = *OPERAND(nxt);
- minimum = (OP(scan) == STAR) ? 0 : 1;
- save = reginput;
- no = regrepeat(OPERAND(scan));
- while (no >= minimum) {
- /* If it could work, try it. */
- if (nextch == ' ' || *reginput == nextch)
- if (regmatch(nxt))
- return (1);
- /* Couldn't or didn't -- back up. */
- no--;
- reginput = save + no;
- }
- return (0);
- }
- case END:
- return (1); /* Success! */
- default:
- regerror("memory corruption");
- return (0);
- }
- scan = nxt;
- }
- /*
- * We get here only if there's trouble -- normally "case END" is the
- * terminating point.
- */
- regerror("corrupted pointers");
- return (0);
- }
- /*
- - regrepeat - repeatedly match something simple, report how many
- */
- static int regrepeat(char *p)
- {
- register int count = 0;
- register char *scan;
- register char *opnd;
- scan = 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 != ' ' && STRCHR(opnd, *scan) != (char *)NULL) {
- count++;
- scan++;
- }
- break;
- case ANYBUT:
- while (*scan != ' ' && STRCHR(opnd, *scan) == (char *)NULL) {
- count++;
- scan++;
- }
- break;
- default: /* Oh dear. Called inappropriately. */
- regerror("internal foulup");
- count = 0; /* Best compromise. */
- break;
- }
- reginput = scan;
- return (count);
- }
- /*
- - regnext - dig the "nxt" pointer out of a node
- */
- static char *regnext(register char *p)
- {
- register int offset;
- if (p == ®dummy)
- return ((char *)NULL);
- offset = NEXT(p);
- if (offset == 0)
- return ((char *)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(regexp *r)
- {
- register char *s;
- register char op = EXACTLY; /* Arbitrary non-END op. */
- register char *nxt;
- s = r->program + 1;
- while (op != END) { /* While that wasn't END last time... */
- op = OP(s);
- printf("%2ld%s", (long)(s - r->program), regprop(s)); /* Where, what. */
- nxt = regnext(s);
- if (nxt == (char *)NULL) /* nxt ptr. */
- printf("(0)");
- else
- printf("(%ld)", (long)( (s - r->program) + (nxt - s)));
- s += 3;
- if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
- /* Literal string, where present. */
- while (*s != ' ') {
- putchar(*s);
- s++;
- }
- s++;
- }
- putchar('n');
- }
- /* Header fields of interest. */
- if (r->regstart != ' ')
- printf("start `%c' ", r->regstart);
- if (r->reganch)
- printf("anchored ");
- if (r->regmust != (char *)NULL)
- printf("must have "%s"", r->regmust);
- printf("n");
- }
- /*
- - regprop - printable representation of opcode
- */
- static char *regprop(char *op)
- {
- register char *p;
- static char buf[50];
- 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 = (char *)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 = (char *)NULL;
- break;
- case STAR:
- p = "STAR";
- break;
- default:
- regerror("corrupted opcode");
- p=(char *)NULL;
- break;
- }
- if (p != (char *)NULL)
- strcat(buf, p);
- return (buf);
- }
- #endif
- /*
- - regsub - perform substitutions after a regexp match
- */
- char *regsub(regexp *prog, char *source, char *dest, int n)
- {
- register char *src;
- register char *dst;
- register char c;
- register int no;
- register int len;
- extern char *strncpy();
- if (prog == (regexp *)NULL ||
- source == (char *)NULL || dest == (char *)NULL) {
- regerror("NULL parm to regsub");
- return NULL;
- }
- if (UCHARAT(prog->program) != MAGIC) {
- regerror("damaged regexp fed to regsub");
- return NULL;
- }
- src = source;
- dst = dest;
- while ((c = *src++) != ' ') {
- if (c == '&')
- no = 0;
- else if (c == '\' && '0' <= *src && *src <= '9')
- no = *src++ - '0';
- else
- no = -1;
- if (no < 0) { /* Ordinary character. */
- if (c == '\' && (*src == '\' || *src == '&'))
- c = *src++;
- if (--n < 0) { /* amylaar */
- regerror("line too long");
- return NULL;
- }
- *dst++ = c;
- } else if (prog->startp[no] != (char *)NULL &&
- prog->endp[no] != (char *)NULL) {
- len = prog->endp[no] - prog->startp[no];
- if ( (n-=len) < 0 ) { /* amylaar */
- regerror("line too long");
- return NULL;
- }
- strncpy(dst, prog->startp[no], len);
- dst += len;
- if (len != 0 && *(dst - 1) == ' ') { /* strncpy hit NUL. */
- regerror("damaged match string");
- return NULL;
- }
- }
- }
- if (--n < 0) { /* amylaar */
- regerror("line too long");
- return NULL;
- }
- *dst = ' ';
- return dst;
- }
- #if 0 /* Use the local regerror() in ed.c */
- void regerror(char *s)
- {
- fprintf(stderr, "regexp(3): %s", s);
- exit(1);
- }
- #endif /* 0 */