--- /dev/null
+/*****************************************************************
+ * 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*/
git://source.jalview.org / jabaws.git / blobdiff