Mercurial > repos > clustalomega > clustalomega
diff clustalomega/clustal-omega-1.0.2/src/squid/hsregex.c @ 1:bc707542e5de
Uploaded
author | clustalomega |
---|---|
date | Thu, 21 Jul 2011 13:35:08 -0400 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/clustalomega/clustal-omega-1.0.2/src/squid/hsregex.c Thu Jul 21 13:35:08 2011 -0400 @@ -0,0 +1,1350 @@ +/***************************************************************** + * SQUID - a library of functions for biological sequence analysis + * Copyright (C) 1992-2002 Washington University School of Medicine + * + * This source code is freely distributed under the terms of the + * GNU General Public License. See the files COPYRIGHT and LICENSE + * for details. + *****************************************************************/ + +/***************************************************************** + * This code is an altered version of Henry Spencer's + * regex library. Alterations are limited to minor streamlining, + * and some name changes to protect the SQUID namespace. + * Henry's copyright notice appears below. + * You can obtain the original from + * ftp://ftp.zoo.toronto.edu/pub/bookregex.tar.Z + * Thanks, Henry! + * + * The magic word for compiling a testdriver: NBA_TEAM_IN_STL + * gcc -o test -g -DNBA_TEAM_IN_STL -L. hsregex.c -lsquid -lm + * + * Usage: + * test <pattern> <ntok> <string> + * + * SRE, Fri Aug 28 11:10:17 1998 + * CVS $Id: hsregex.c,v 1.7 2001/08/09 17:50:17 eddy Exp) + *****************************************************************/ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> +#include "squid.h" + +/* global sqd_parse[] are managed by Strparse(). + * WARNING: TODO: this code is not threadsafe, and needs to be revised. + */ +char *sqd_parse[10]; + +/* Function: Strparse() + * + * Purpose: Match a regexp to a string. Returns 1 if pattern matches, + * else 0. + * + * Much like Perl, Strparse() makes copies of the matching + * substrings available via globals, sqd_parse[]. + * sqd_parse[0] contains a copy of the complete matched + * text. sqd_parse[1-9] contain copies of up to nine + * different substrings matched within parentheses. + * The memory for these strings is internally managed and + * volatile; the next call to Strparse() may destroy them. + * If the caller needs the matched substrings to persist + * beyond a new Strparse() call, it must make its own + * copies. + * + * A minor drawback of the memory management is that + * there will be a small amount of unfree'd memory being + * managed by Strparse() when a program exits; this may + * confuse memory debugging (Purify, dbmalloc). The + * general cleanup function SqdClean() is provided; + * you can call this before exiting. + * + * Uses an extended POSIX regular expression interface. + * A copylefted GNU implementation is included in the squid + * implementation (gnuregex.c) for use on non-POSIX compliant + * systems. POSIX 1003.2-compliant systems (all UNIX, + * some WinNT, I believe) can omit the GNU code if necessary. + * + * I built this for ease of use, not speed nor efficiency. + * + * Example: Strparse("foo-...-baz", "foo-bar-baz") returns 0 + * Strparse("foo-(...)-baz", "foo-bar-baz") + * returns 0; sqd_parse[0] is "foo-bar-baz"; + * sqd_parse[1] is "bar". + * + * A real example: + * s = ">gnl|ti|3 G10P69425RH2.T0 {SUB 81..737} /len=657" + * pat = "SUB ([0-9]+)" + * Strparse(pat, s, 1) + * returns 1; sqd_parse[1] is "81". + * + * Args: rexp - regular expression, extended POSIX form + * s - string to match against + * ntok - number of () substrings we will save (maximum NSUBEXP-1) + * + * Return: 1 on match, 0 if no match + */ +int +Strparse(char *rexp, char *s, int ntok) +{ + sqd_regexp *pat; + int code; + int len; + int i; + /* sanity check */ + if (ntok >= NSUBEXP ) Die("Strparse(): ntok must be <= %d", NSUBEXP-1); + + /* Free previous global substring buffers + */ + for (i = 0; i <= ntok; i++) + if (sqd_parse[i] != NULL) + { + free(sqd_parse[i]); + sqd_parse[i] = NULL; + } + + /* Compile and match the pattern, using our modified + * copy of Henry Spencer's regexp library + */ + if ((pat = sqd_regcomp(rexp)) == NULL) + Die("regexp compilation failed."); + code = sqd_regexec(pat, s); + + /* Fill the global substring buffers + */ + if (code == 1) + for (i = 0; i <= ntok; i++) + if (pat->startp[i] != NULL && pat->endp[i] != NULL) + { + len = pat->endp[i] - pat->startp[i]; + sqd_parse[i] = (char *) MallocOrDie(sizeof(char) * (len+1)); + strncpy(sqd_parse[i], pat->startp[i], len); + sqd_parse[i][len] = '\0'; + } + + free(pat); + return code; +} + +/* Function: SqdClean() + * Date: SRE, Wed Oct 29 12:52:08 1997 [TWA 721] + * + * Purpose: Clean up any squid library allocations before exiting + * a program, so we don't leave unfree'd memory around + * and confuse a malloc debugger like Purify or dbmalloc. + */ +void +SqdClean(void) +{ + int i; + + /* Free global substring buffers that Strparse() uses + */ + for (i = 0; i <= 9; i++) + if (sqd_parse[i] != NULL) { + free(sqd_parse[i]); + sqd_parse[i] = NULL; + } +} + + + +/* all code below is: + * Copyright (c) 1986, 1993, 1995 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 in any way, + * 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 (by explicit claim or omission) as being + * the original software. + * + * 4. This notice must not be removed or altered. + */ + +/* + * sqd_regcomp and sqd_regexec -- sqd_regsub and sqd_regerror are elsewhere + */ + +/* + * The first byte of the regexp internal "program" is actually this magic + * number; the start node begins in the second byte. + */ +#define SQD_REGMAGIC 0234 + +/* + * 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 sqd_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 sqd_regexec() needs it and sqd_regcomp() is computing + * it anyway. + */ + +/* + * Structure for regexp "program". This is essentially a linear encoding + * of a nondeterministic finite-state machine (aka syntax charts or + * "railroad normal form" in parsing technology). Each node is an opcode + * plus a "next" pointer, possibly plus an operand. "Next" pointers of + * all nodes except BRANCH implement concatenation; a "next" pointer with + * a BRANCH on both ends of it is connecting two alternatives. (Here we + * have one of the subtle syntax dependencies: an individual BRANCH (as + * opposed to a collection of them) is never concatenated with anything + * because of operator precedence.) The operand of some types of node is + * a literal string; for others, it is a node leading into a sub-FSM. In + * particular, the operand of a BRANCH node is the first node of the branch. + * (NB this is *not* a tree structure: the tail of the branch connects + * to the thing following the set of BRANCHes.) The opcodes are: + */ + +/* definition number opnd? meaning */ +#define END 0 /* no End of program. */ +#define BOL 1 /* no Match beginning of line. */ +#define EOL 2 /* no Match end of line. */ +#define ANY 3 /* no Match any character. */ +#define ANYOF 4 /* str Match any of these. */ +#define ANYBUT 5 /* str Match any but one of these. */ +#define BRANCH 6 /* node Match this, or the next..\&. */ +#define BACK 7 /* no "next" ptr points backward. */ +#define EXACTLY 8 /* str Match this string. */ +#define NOTHING 9 /* no Match empty string. */ +#define STAR 10 /* node Match this 0 or more times. */ +#define PLUS 11 /* node Match this 1 or more times. */ +#define OPEN 20 /* no Sub-RE starts here. */ + /* OPEN+1 is number 1, etc. */ +#define CLOSE 30 /* no Analogous to OPEN. */ + +/* + * Opcode notes: + * + * BRANCH The set of branches constituting a single choice are hooked + * together with their "next" pointers, since precedence prevents + * anything being concatenated to any individual branch. The + * "next" pointer of the last BRANCH in a choice points to the + * thing following the whole choice. This is also where the + * final "next" pointer of each individual branch points; each + * branch starts with the operand node of a BRANCH node. + * + * BACK Normal "next" pointers all implicitly point forward; BACK + * exists to make loop structures possible. + * + * STAR,PLUS '?', and complex '*' and '+', are implemented as circular + * BRANCH structures using BACK. Simple cases (one character + * per match) are implemented with STAR and PLUS for speed + * and to minimize recursive plunges. + * + * OPEN,CLOSE ...are numbered at compile time. + */ + +/* + * A node is one char of opcode followed by two chars of "next" pointer. + * "Next" pointers are stored as two 8-bit pieces, high order first. The + * value is a positive offset from the opcode of the node containing it. + * An operand, if any, simply follows the node. (Note that much of the + * code generation knows about this implicit relationship.) + * + * Using two bytes for the "next" pointer is vast overkill for most things, + * but allows patterns to get big without disasters. + */ +#define OP(p) (*(p)) +#define NEXT(p) (((*((p)+1)&0177)<<8) + (*((p)+2)&0377)) +#define OPERAND(p) ((p) + 3) + +/* + * Utility definitions. + */ +#define FAIL(m) { sqd_regerror(m); return(NULL); } +#define ISREPN(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. */ + +/* + * Work-variable struct for sqd_regcomp(). + */ +struct comp { + char *regparse; /* Input-scan pointer. */ + int regnpar; /* () count. */ + char *regcode; /* Code-emit pointer; ®dummy = don't. */ + char regdummy[3]; /* NOTHING, 0 next ptr */ + long regsize; /* Code size. */ +}; +#define EMITTING(cp) ((cp)->regcode != (cp)->regdummy) + +/* + * Forward declarations for sqd_regcomp()'s friends. + */ +static char *reg(struct comp *cp, int paren, int *flagp); +static char *regbranch(struct comp *cp, int *flagp); +static char *regpiece(struct comp *cp, int *flagp); +static char *regatom(struct comp *cp, int *flagp); +static char *regnode(struct comp *cp, int op); +static char *regnext(char *node); +static void regc(struct comp *cp, int c); +static void reginsert(struct comp *cp, int op, char *opnd); +static void regtail(struct comp *cp, char *p, char *val); +static void regoptail(struct comp *cp, char *p, char *val); + +/* + - sqd_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. + */ +sqd_regexp * +sqd_regcomp(exp) +const char *exp; +{ + register sqd_regexp *r; + register char *scan; + int flags; + struct comp co; + + if (exp == NULL) + FAIL("NULL argument to sqd_regcomp"); + + /* First pass: determine size, legality. */ + co.regparse = (char *)exp; + co.regnpar = 1; + co.regsize = 0L; + co.regdummy[0] = NOTHING; + co.regdummy[1] = co.regdummy[2] = 0; + co.regcode = co.regdummy; + regc(&co, SQD_REGMAGIC); + if (reg(&co, 0, &flags) == NULL) + return(NULL); + + /* Small enough for pointer-storage convention? */ + if (co.regsize >= 0x7fffL) /* Probably could be 0xffffL. */ + FAIL("regexp too big"); + + /* Allocate space. */ + r = (sqd_regexp *)malloc(sizeof(sqd_regexp) + (size_t)co.regsize); + if (r == NULL) + FAIL("out of space"); + + /* Second pass: emit code. */ + co.regparse = (char *)exp; + co.regnpar = 1; + co.regcode = r->program; + regc(&co, SQD_REGMAGIC); + if (reg(&co, 0, &flags) == NULL) + return(NULL); + + /* Dig out information for optimizations. */ + r->regstart = '\0'; /* Worst-case defaults. */ + r->reganch = 0; + r->regmust = NULL; + r->regmlen = 0; + scan = r->program+1; /* First BRANCH. */ + if (OP(regnext(scan)) == END) { /* Only one top-level choice. */ + scan = OPERAND(scan); + + /* Starting-point info. */ + if (OP(scan) == EXACTLY) + r->regstart = *OPERAND(scan); + else if (OP(scan) == BOL) + r->reganch = 1; + + /* + * 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) { + register char *longest = NULL; + register size_t len = 0; + + for (; scan != NULL; scan = regnext(scan)) + if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) { + longest = OPERAND(scan); + len = strlen(OPERAND(scan)); + } + r->regmust = longest; + r->regmlen = (int)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(cp, paren, flagp) +register struct comp *cp; +int paren; /* Parenthesized? */ +int *flagp; +{ + register char *ret = NULL; /* SRE: NULL init added to silence gcc */ + register char *br; + register char *ender; + register int parno = 0; /* SRE: init added to silence gcc */ + int flags; + + *flagp = HASWIDTH; /* Tentatively. */ + + if (paren) { + /* Make an OPEN node. */ + if (cp->regnpar >= NSUBEXP) + FAIL("too many ()"); + parno = cp->regnpar; + cp->regnpar++; + ret = regnode(cp, OPEN+parno); + } + + /* Pick up the branches, linking them together. */ + br = regbranch(cp, &flags); + if (br == NULL) + return(NULL); + if (paren) + regtail(cp, ret, br); /* OPEN -> first. */ + else + ret = br; + *flagp &= ~(~flags&HASWIDTH); /* Clear bit if bit 0. */ + *flagp |= flags&SPSTART; + while (*cp->regparse == '|') { + cp->regparse++; + br = regbranch(cp, &flags); + if (br == NULL) + return(NULL); + regtail(cp, ret, br); /* BRANCH -> BRANCH. */ + *flagp &= ~(~flags&HASWIDTH); + *flagp |= flags&SPSTART; + } + + /* Make a closing node, and hook it on the end. */ + ender = regnode(cp, (paren) ? CLOSE+parno : END); + regtail(cp, ret, ender); + + /* Hook the tails of the branches to the closing node. */ + for (br = ret; br != NULL; br = regnext(br)) + regoptail(cp, br, ender); + + /* Check for proper termination. */ + if (paren && *cp->regparse++ != ')') { + FAIL("unterminated ()"); + } else if (!paren && *cp->regparse != '\0') { + if (*cp->regparse == ')') { + FAIL("unmatched ()"); + } else + FAIL("internal error: junk on end"); + /* NOTREACHED */ + } + + return(ret); +} + +/* + - regbranch - one alternative of an | operator + * + * Implements the concatenation operator. + */ +static char * +regbranch(cp, flagp) +register struct comp *cp; +int *flagp; +{ + register char *ret; + register char *chain; + register char *latest; + int flags; + register int c; + + *flagp = WORST; /* Tentatively. */ + + ret = regnode(cp, BRANCH); + chain = NULL; + while ((c = *cp->regparse) != '\0' && c != '|' && c != ')') { + latest = regpiece(cp, &flags); + if (latest == NULL) + return(NULL); + *flagp |= flags&HASWIDTH; + if (chain == NULL) /* First piece. */ + *flagp |= flags&SPSTART; + else + regtail(cp, chain, latest); + chain = latest; + } + if (chain == NULL) /* Loop ran zero times. */ + (void) regnode(cp, NOTHING); + + return(ret); +} + +/* + - regpiece - something followed by possible [*+?] + * + * Note that the branching code sequences used for ? and the general cases + * of * and + are somewhat optimized: they use the same NOTHING node as + * both the endmarker for their branch list and the body of the last branch. + * It might seem that this node could be dispensed with entirely, but the + * endmarker role is not redundant. + */ +static char * +regpiece(cp, flagp) +register struct comp *cp; +int *flagp; +{ + register char *ret; + register char op; + register char *next; + int flags; + + ret = regatom(cp, &flags); + if (ret == NULL) + return(NULL); + + op = *cp->regparse; + if (!ISREPN(op)) { + *flagp = flags; + return(ret); + } + + if (!(flags&HASWIDTH) && op != '?') + FAIL("*+ operand could be empty"); + switch (op) { + case '*': *flagp = WORST|SPSTART; break; + case '+': *flagp = WORST|SPSTART|HASWIDTH; break; + case '?': *flagp = WORST; break; + } + + if (op == '*' && (flags&SIMPLE)) + reginsert(cp, STAR, ret); + else if (op == '*') { + /* Emit x* as (x&|), where & means "self". */ + reginsert(cp, BRANCH, ret); /* Either x */ + regoptail(cp, ret, regnode(cp, BACK)); /* and loop */ + regoptail(cp, ret, ret); /* back */ + regtail(cp, ret, regnode(cp, BRANCH)); /* or */ + regtail(cp, ret, regnode(cp, NOTHING)); /* null. */ + } else if (op == '+' && (flags&SIMPLE)) + reginsert(cp, PLUS, ret); + else if (op == '+') { + /* Emit x+ as x(&|), where & means "self". */ + next = regnode(cp, BRANCH); /* Either */ + regtail(cp, ret, next); + regtail(cp, regnode(cp, BACK), ret); /* loop back */ + regtail(cp, next, regnode(cp, BRANCH)); /* or */ + regtail(cp, ret, regnode(cp, NOTHING)); /* null. */ + } else if (op == '?') { + /* Emit x? as (x|) */ + reginsert(cp, BRANCH, ret); /* Either x */ + regtail(cp, ret, regnode(cp, BRANCH)); /* or */ + next = regnode(cp, NOTHING); /* null. */ + regtail(cp, ret, next); + regoptail(cp, ret, next); + } + cp->regparse++; + if (ISREPN(*cp->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(cp, flagp) +register struct comp *cp; +int *flagp; +{ + register char *ret; + int flags; + + *flagp = WORST; /* Tentatively. */ + + switch (*cp->regparse++) { + case '^': + ret = regnode(cp, BOL); + break; + case '$': + ret = regnode(cp, EOL); + break; + case '.': + ret = regnode(cp, ANY); + *flagp |= HASWIDTH|SIMPLE; + break; + case '[': { + register int range; + register int rangeend; + register int c; + + if (*cp->regparse == '^') { /* Complement of range. */ + ret = regnode(cp, ANYBUT); + cp->regparse++; + } else + ret = regnode(cp, ANYOF); + if ((c = *cp->regparse) == ']' || c == '-') { + regc(cp, c); + cp->regparse++; + } + while ((c = *cp->regparse++) != '\0' && c != ']') { + if (c != '-') + regc(cp, c); + else if ((c = *cp->regparse) == ']' || c == '\0') + regc(cp, '-'); + else { + range = (unsigned char)*(cp->regparse-2); + rangeend = (unsigned char)c; + if (range > rangeend) + FAIL("invalid [] range"); + for (range++; range <= rangeend; range++) + regc(cp, range); + cp->regparse++; + } + } + regc(cp, '\0'); + if (c != ']') + FAIL("unmatched []"); + *flagp |= HASWIDTH|SIMPLE; + break; + } + case '(': + ret = reg(cp, 1, &flags); + if (ret == NULL) + return(NULL); + *flagp |= flags&(HASWIDTH|SPSTART); + break; + case '\0': + case '|': + case ')': + /* supposed to be caught earlier */ + FAIL("internal error: \\0|) unexpected"); + break; + case '?': + case '+': + case '*': + FAIL("?+* follows nothing"); + break; + case '\\': + if (*cp->regparse == '\0') + FAIL("trailing \\"); + ret = regnode(cp, EXACTLY); + regc(cp, *cp->regparse++); + regc(cp, '\0'); + *flagp |= HASWIDTH|SIMPLE; + break; + default: { + register size_t len; + register char ender; + + cp->regparse--; + len = strcspn(cp->regparse, META); + if (len == 0) + FAIL("internal error: strcspn 0"); + ender = *(cp->regparse+len); + if (len > 1 && ISREPN(ender)) + len--; /* Back off clear of ?+* operand. */ + *flagp |= HASWIDTH; + if (len == 1) + *flagp |= SIMPLE; + ret = regnode(cp, EXACTLY); + for (; len > 0; len--) + regc(cp, *cp->regparse++); + regc(cp, '\0'); + break; + } + } + + return(ret); +} + +/* + - regnode - emit a node + */ +static char * /* Location. */ +regnode(cp, op) +register struct comp *cp; +char op; +{ + register char *const ret = cp->regcode; + register char *ptr; + + if (!EMITTING(cp)) { + cp->regsize += 3; + return(ret); + } + + ptr = ret; + *ptr++ = op; + *ptr++ = '\0'; /* Null next pointer. */ + *ptr++ = '\0'; + cp->regcode = ptr; + + return(ret); +} + +/* + - regc - emit (if appropriate) a byte of code + */ +static void +regc(cp, b) +register struct comp *cp; +char b; +{ + if (EMITTING(cp)) + *cp->regcode++ = b; + else + cp->regsize++; +} + +/* + - reginsert - insert an operator in front of already-emitted operand + * + * Means relocating the operand. + */ +static void +reginsert(cp, op, opnd) +register struct comp *cp; +char op; +char *opnd; +{ + register char *place; + + if (!EMITTING(cp)) { + cp->regsize += 3; + return; + } + + (void) memmove(opnd+3, opnd, (size_t)(cp->regcode - opnd)); + cp->regcode += 3; + + place = opnd; /* Op node, where operand used to be. */ + *place++ = op; + *place++ = '\0'; + *place++ = '\0'; +} + +/* + - regtail - set the next-pointer at the end of a node chain + */ +static void +regtail(cp, p, val) +register struct comp *cp; +char *p; +char *val; +{ + register char *scan; + register char *temp; + register int offset; + + if (!EMITTING(cp)) + return; + + /* Find last node. */ + for (scan = p; (temp = regnext(scan)) != NULL; scan = temp) + continue; + + offset = (OP(scan) == BACK) ? scan - val : val - scan; + *(scan+1) = (offset>>8)&0177; + *(scan+2) = offset&0377; +} + +/* + - regoptail - regtail on operand of first argument; nop if operandless + */ +static void +regoptail(cp, p, val) +register struct comp *cp; +char *p; +char *val; +{ + /* "Operandless" and "op != BRANCH" are synonymous in practice. */ + if (!EMITTING(cp) || OP(p) != BRANCH) + return; + regtail(cp, OPERAND(p), val); +} + +/* + * sqd_regexec and friends + */ + +/* + * Work-variable struct for sqd_regexec(). + */ +struct exec { + 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(struct exec *ep, sqd_regexp *rp, char *string); +static int regmatch(struct exec *ep, char *prog); +static size_t regrepeat(struct exec *ep, char *node); + +#ifdef DEBUG +int regnarrate = 0; +void regdump(); +static char *regprop(); +#endif + +/* + - sqd_regexec - match a regexp against a string + */ +int +sqd_regexec(prog, str) +register sqd_regexp *prog; +const char *str; +{ + register char *string = (char *)str; /* avert const poisoning */ + register char *s; + struct exec ex; + + /* Be paranoid. */ + if (prog == NULL || string == NULL) { + sqd_regerror("NULL argument to sqd_regexec"); + return(0); + } + + /* Check validity of program. */ + if ((unsigned char)*prog->program != SQD_REGMAGIC) { + sqd_regerror("corrupted regexp"); + return(0); + } + + /* If there is a "must appear" string, look for it. */ + if (prog->regmust != NULL && strstr(string, prog->regmust) == NULL) + return(0); + + /* Mark beginning of line for ^ . */ + ex.regbol = string; + ex.regstartp = prog->startp; + ex.regendp = prog->endp; + + /* Simplest case: anchored match need be tried only once. */ + if (prog->reganch) + return(regtry(&ex, prog, string)); + + /* Messy cases: unanchored match. */ + if (prog->regstart != '\0') { + /* We know what char it must start with. */ + for (s = string; s != NULL; s = strchr(s+1, prog->regstart)) + if (regtry(&ex, prog, s)) + return(1); + return(0); + } else { + /* We don't -- general case. */ + for (s = string; !regtry(&ex, prog, s); s++) + if (*s == '\0') + return(0); + return(1); + } + /* NOTREACHED */ +} + +/* + - regtry - try match at specific point + */ +static int /* 0 failure, 1 success */ +regtry(ep, prog, string) +register struct exec *ep; +sqd_regexp *prog; +char *string; +{ + register int i; + register char **stp; + register char **enp; + + ep->reginput = string; + + stp = prog->startp; + enp = prog->endp; + for (i = NSUBEXP; i > 0; i--) { + *stp++ = NULL; + *enp++ = NULL; + } + if (regmatch(ep, prog->program + 1)) { + prog->startp[0] = string; + prog->endp[0] = ep->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(ep, prog) +register struct exec *ep; +char *prog; +{ + register char *scan; /* Current node. */ + char *next; /* Next node. */ + +#ifdef DEBUG + if (prog != NULL && regnarrate) + fprintf(stderr, "%s(\n", regprop(prog)); +#endif + for (scan = prog; scan != NULL; scan = next) { +#ifdef DEBUG + if (regnarrate) + fprintf(stderr, "%s...\n", regprop(scan)); +#endif + next = regnext(scan); + + switch (OP(scan)) { + case BOL: + if (ep->reginput != ep->regbol) + return(0); + break; + case EOL: + if (*ep->reginput != '\0') + return(0); + break; + case ANY: + if (*ep->reginput == '\0') + return(0); + ep->reginput++; + break; + case EXACTLY: { + register size_t len; + register char *const opnd = OPERAND(scan); + + /* Inline the first character, for speed. */ + if (*opnd != *ep->reginput) + return(0); + len = strlen(opnd); + if (len > 1 && strncmp(opnd, ep->reginput, len) != 0) + return(0); + ep->reginput += len; + break; + } + case ANYOF: + if (*ep->reginput == '\0' || + strchr(OPERAND(scan), *ep->reginput) == NULL) + return(0); + ep->reginput++; + break; + case ANYBUT: + if (*ep->reginput == '\0' || + strchr(OPERAND(scan), *ep->reginput) != NULL) + return(0); + ep->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 const int no = OP(scan) - OPEN; + register char *const input = ep->reginput; + + if (regmatch(ep, next)) { + /* + * Don't set startp if some later + * invocation of the same parentheses + * already has. + */ + if (ep->regstartp[no] == NULL) + ep->regstartp[no] = input; + return(1); + } else + return(0); + 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: { + register const int no = OP(scan) - CLOSE; + register char *const input = ep->reginput; + + if (regmatch(ep, next)) { + /* + * Don't set endp if some later + * invocation of the same parentheses + * already has. + */ + if (ep->regendp[no] == NULL) + ep->regendp[no] = input; + return(1); + } else + return(0); + break; + } + case BRANCH: { + register char *const save = ep->reginput; + + if (OP(next) != BRANCH) /* No choice. */ + next = OPERAND(scan); /* Avoid recursion. */ + else { + while (OP(scan) == BRANCH) { + if (regmatch(ep, OPERAND(scan))) + return(1); + ep->reginput = save; + scan = regnext(scan); + } + return(0); + /* NOTREACHED */ + } + break; + } + case STAR: case PLUS: { + register const char nextch = + (OP(next) == EXACTLY) ? *OPERAND(next) : '\0'; + register size_t no; + register char *const save = ep->reginput; + register const size_t min = (OP(scan) == STAR) ? 0 : 1; + + for (no = regrepeat(ep, OPERAND(scan)) + 1; no > min; no--) { + ep->reginput = save + no - 1; + /* If it could work, try it. */ + if (nextch == '\0' || *ep->reginput == nextch) + if (regmatch(ep, next)) + return(1); + } + return(0); + break; + } + case END: + return(1); /* Success! */ + break; + default: + sqd_regerror("regexp corruption"); + return(0); + break; + } + } + + /* + * We get here only if there's trouble -- normally "case END" is + * the terminating point. + */ + sqd_regerror("corrupted pointers"); + return(0); +} + +/* + - regrepeat - report how many times something simple would match + */ +static size_t +regrepeat(ep, node) +register struct exec *ep; +char *node; +{ + register size_t count; + register char *scan; + register char ch; + + switch (OP(node)) { + case ANY: + return(strlen(ep->reginput)); + break; + case EXACTLY: + ch = *OPERAND(node); + count = 0; + for (scan = ep->reginput; *scan == ch; scan++) + count++; + return(count); + break; + case ANYOF: + return(strspn(ep->reginput, OPERAND(node))); + break; + case ANYBUT: + return(strcspn(ep->reginput, OPERAND(node))); + break; + default: /* Oh dear. Called inappropriately. */ + sqd_regerror("internal error: bad call of regrepeat"); + return(0); /* Best compromise. */ + break; + } + /* NOTREACHED */ +} + +/* + - regnext - dig the "next" pointer out of a node + */ +static char * +regnext(p) +register char *p; +{ + register const int offset = NEXT(p); + + if (offset == 0) + return(NULL); + + return((OP(p) == BACK) ? p-offset : p+offset); +} + +#ifdef DEBUG + +static char *regprop(); + +/* + - regdump - dump a regexp onto stdout in vaguely comprehensible form + */ +void +regdump(r) +sqd_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: + sqd_regerror("corrupted opcode"); + break; + } + if (p != NULL) + (void) strcat(buf, p); + return(buf); +} +#endif + + +/* + - sqd_regsub - perform substitutions after a regexp match + */ +void +sqd_regsub(rp, source, dest) +const sqd_regexp *rp; +const char *source; +char *dest; +{ + register sqd_regexp * const prog = (sqd_regexp *)rp; + register char *src = (char *)source; + register char *dst = dest; + register char c; + register int no; + register size_t len; + + if (prog == NULL || source == NULL || dest == NULL) { + sqd_regerror("NULL parameter to sqd_regsub"); + return; + } + if ((unsigned char)*(prog->program) != SQD_REGMAGIC) { + sqd_regerror("damaged regexp"); + return; + } + + while ((c = *src++) != '\0') { + if (c == '&') + no = 0; + else if (c == '\\' && isdigit((int) (*src))) + no = *src++ - '0'; + else + no = -1; + + if (no < 0) { /* Ordinary character. */ + if (c == '\\' && (*src == '\\' || *src == '&')) + c = *src++; + *dst++ = c; + } else if (prog->startp[no] != NULL && prog->endp[no] != NULL && + prog->endp[no] > prog->startp[no]) { + len = prog->endp[no] - prog->startp[no]; + (void) strncpy(dst, prog->startp[no], len); + dst += len; + if (*(dst-1) == '\0') { /* strncpy hit NUL. */ + sqd_regerror("damaged match string"); + return; + } + } + } + *dst++ = '\0'; +} + + +void +sqd_regerror(s) +char *s; +{ + fprintf(stderr, "regexp(3): %s\n", s); + exit(EXIT_FAILURE); + /* NOTREACHED */ +} + +#ifdef NBA_TEAM_IN_STL +int +main(int argc, char **argv) +{ + char *pat; + int ntok; + char *s; + int status; + + pat = argv[1]; + ntok = atoi(argv[2]); + s = argv[3]; + + status = Strparse(pat, s, ntok); + if (status == 0) { + printf("no match\n"); + } else { + int i; + printf("MATCH.\n"); + for (i = 1; i <= ntok; i++) + printf("matched token %1d: %s\n", i, sqd_parse[i]); + } +} +#endif /*NBA_TEAM_IN_STL*/