summaryrefslogtreecommitdiffstats
path: root/Source/cmRegularExpression.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'Source/cmRegularExpression.cxx')
-rw-r--r--Source/cmRegularExpression.cxx1279
1 files changed, 1279 insertions, 0 deletions
diff --git a/Source/cmRegularExpression.cxx b/Source/cmRegularExpression.cxx
new file mode 100644
index 0000000..0867e97
--- /dev/null
+++ b/Source/cmRegularExpression.cxx
@@ -0,0 +1,1279 @@
+//
+// Copyright (C) 1991 Texas Instruments Incorporated.
+//
+// Permission is granted to any individual or institution to use, copy, modify,
+// and distribute this software, provided that this complete copyright and
+// permission notice is maintained, intact, in all copies and supporting
+// documentation.
+//
+// Texas Instruments Incorporated provides this software "as is" without
+// express or implied warranty.
+//
+//
+// Created: MNF 06/13/89 Initial Design and Implementation
+// Updated: LGO 08/09/89 Inherit from Generic
+// Updated: MBN 09/07/89 Added conditional exception handling
+// Updated: MBN 12/15/89 Sprinkled "const" qualifiers all over the place!
+// Updated: DLS 03/22/91 New lite version
+//
+// This is the header file for the regular expression class. An object of
+// this class contains a regular expression, in a special "compiled" format.
+// This compiled format consists of several slots all kept as the objects
+// private data. The cmRegularExpression class provides a convenient way to represent
+// regular expressions. It makes it easy to search for the same regular
+// expression in many different strings without having to compile a string to
+// regular expression format more than necessary.
+//
+// A regular expression allows a programmer to specify complex patterns that
+// can be searched for and matched against the character string of a String
+// object. In its simplest case, a regular expression is a sequence of
+// characters with which you can search for exact character matches. However,
+// many times you may not know the exact sequence you want to find, or you may
+// only want to find a match at the beginning or end of a String. The cmRegularExpression
+// object allows specification of such patterns by utilizing the following
+// regular expression meta-characters (note that more one of these
+// meta-characters can be used in a single regular expression in order to
+// create complex search patterns):
+//
+// ^ Match at beginning of line
+// $ Match at end of line
+// . Match any single character
+// [ ] Match any one character inside the brackets
+// [^ ] Match any character NOT inside the brackets
+// - Match any character in range on either side of dash
+// * Match preceding pattern zero or more times
+// + Match preceding pattern one or more times
+// ? Match preceding pattern zero or once only
+// () Save a matched expression and use it in a further match.
+//
+// There are three constructors for cmRegularExpression. One just creates an empty cmRegularExpression
+// object. Another creates a cmRegularExpression object and initializes it with a regular
+// expression that is given in the form of a char*. The third takes a
+// reference to a cmRegularExpression object as an argument and creates an object
+// initialized with the information from the given cmRegularExpression object.
+//
+// The find member function finds the first occurence of the regualr
+// expression of that object in the string given to find as an argument. Find
+// returns a boolean, and if true, mutates the private data appropriately.
+// Find sets pointers to the beginning and end of the thing last found, they
+// are pointers into the actual string that was searched. The start and end
+// member functions return indicies into the searched string that correspond
+// to the beginning and end pointers respectively. The compile member
+// function takes a char* and puts the compiled version of the char* argument
+// into the object's private data fields. The == and != operators only check
+// the to see if the compiled regular expression is the same, and the
+// deep_equal functions also checks to see if the start and end pointers are
+// the same. The is_valid function returns false if program is set to NULL,
+// (i.e. there is no valid compiled exression). The set_invalid function sets
+// the program to NULL (Warning: this deletes the compiled expression). The
+// following examples may help clarify regular expression usage:
+//
+// * The regular expression "^hello" matches a "hello" only at the
+// beginning of a line. It would match "hello there" but not "hi,
+// hello there".
+//
+// * The regular expression "long$" matches a "long" only at the end
+// of a line. It would match "so long\0", but not "long ago".
+//
+// * The regular expression "t..t..g" will match anything that has a
+// "t" then any two characters, another "t", any two characters and
+// then a "g". It will match "testing", or "test again" but would
+// not match "toasting"
+//
+// * The regular expression "[1-9ab]" matches any number one through
+// nine, and the characters "a" and "b". It would match "hello 1"
+// or "begin", but would not match "no-match".
+//
+// * The regular expression "[^1-9ab]" matches any character that is
+// not a number one through nine, or an "a" or "b". It would NOT
+// match "hello 1" or "begin", but would match "no-match".
+//
+// * The regular expression "br* " matches something that begins with
+// a "b", is followed by zero or more "r"s, and ends in a space. It
+// would match "brrrrr ", and "b ", but would not match "brrh ".
+//
+// * The regular expression "br+ " matches something that begins with
+// a "b", is followed by one or more "r"s, and ends in a space. It
+// would match "brrrrr ", and "br ", but would not match "b " or
+// "brrh ".
+//
+// * The regular expression "br? " matches something that begins with
+// a "b", is followed by zero or one "r"s, and ends in a space. It
+// would match "br ", and "b ", but would not match "brrrr " or
+// "brrh ".
+//
+// * The regular expression "(..p)b" matches something ending with pb
+// and beginning with whatever the two characters before the first p
+// encounterd in the line were. It would find "repb" in "rep drepa
+// qrepb". The regular expression "(..p)a" would find "repa qrepb"
+// in "rep drepa qrepb"
+//
+// * The regular expression "d(..p)" matches something ending with p,
+// beginning with d, and having two characters in between that are
+// the same as the two characters before the first p encounterd in
+// the line. It would match "drepa qrepb" in "rep drepa qrepb".
+//
+
+#include "cmRegularExpression.h" // Include class specification
+#include <stdio.h>
+#include <string>
+
+// cmRegularExpression -- Copies the given regular expression.
+
+cmRegularExpression::cmRegularExpression (const cmRegularExpression& rxp) {
+ int ind;
+ this->progsize = rxp.progsize; // Copy regular expression size
+ this->program = new char[this->progsize]; // Allocate storage
+ for(ind=this->progsize; ind-- != 0;) // Copy regular expresion
+ this->program[ind] = rxp.program[ind];
+ this->startp[0] = rxp.startp[0]; // Copy pointers into last
+ this->endp[0] = rxp.endp[0]; // Successful "find" operation
+ this->regmust = rxp.regmust; // Copy field
+ if (rxp.regmust != NULL) {
+ char* dum = rxp.program;
+ ind = 0;
+ while (dum != rxp.regmust) {
+ ++dum;
+ ++ind;
+ }
+ this->regmust = this->program + ind;
+ }
+ this->regstart = rxp.regstart; // Copy starting index
+ this->reganch = rxp.reganch; // Copy remaining private data
+ this->regmlen = rxp.regmlen; // Copy remaining private data
+}
+
+
+// operator== -- Returns true if two regular expressions have the same
+// compiled program for pattern matching.
+
+bool cmRegularExpression::operator== (const cmRegularExpression& rxp) const {
+ if (this != &rxp) { // Same address?
+ int ind = this->progsize; // Get regular expression size
+ if (ind != rxp.progsize) // If different size regexp
+ return false; // Return failure
+ while(ind-- != 0) // Else while still characters
+ if(this->program[ind] != rxp.program[ind]) // If regexp are different
+ return false; // Return failure
+ }
+ return true; // Else same, return success
+}
+
+
+// deep_equal -- Returns true if have the same compiled regular expressions
+// and the same start and end pointers.
+
+bool cmRegularExpression::deep_equal (const cmRegularExpression& rxp) const {
+ int ind = this->progsize; // Get regular expression size
+ if (ind != rxp.progsize) // If different size regexp
+ return false; // Return failure
+ while(ind-- != 0) // Else while still characters
+ if(this->program[ind] != rxp.program[ind]) // If regexp are different
+ return false; // Return failure
+ return (this->startp[0] == rxp.startp[0] && // Else if same start/end ptrs,
+ this->endp[0] == rxp.endp[0]); // Return true
+}
+
+// The remaining code in this file is derived from the regular expression code
+// whose copyright statement appears below. It has been changed to work
+// with the class concepts of C++ and COOL.
+
+/*
+ * compile and find
+ *
+ * Copyright (c) 1986 by University of Toronto.
+ * Written by Henry Spencer. Not derived from licensed software.
+ *
+ * Permission is granted to anyone to use this software for any
+ * purpose on any computer system, and to redistribute it freely,
+ * subject to the following restrictions:
+ *
+ * 1. The author is not responsible for the consequences of use of
+ * this software, no matter how awful, even if they arise
+ * from defects in it.
+ *
+ * 2. The origin of this software must not be misrepresented, either
+ * by explicit claim or by omission.
+ *
+ * 3. Altered versions must be plainly marked as such, and must not
+ * be misrepresented as being the original software.
+ *
+ * Beware that some of this code is subtly aware of the way operator
+ * precedence is structured in regular expressions. Serious changes in
+ * regular-expression syntax might require a total rethink.
+ */
+
+/*
+ * 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 compile() 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 find() needs it and compile() is computing
+ * it anyway.
+ */
+
+/*
+ * Structure for regexp "program". This is essentially a linear encoding
+ * of a nondeterministic finite-state machine (aka syntax charts or
+ * "railroad normal form" in parsing technology). Each node is an opcode
+ * plus a "next" pointer, possibly plus an operand. "Next" pointers of
+ * all nodes except BRANCH implement concatenation; a "next" pointer with
+ * a BRANCH on both ends of it is connecting two alternatives. (Here we
+ * have one of the subtle syntax dependencies: an individual BRANCH (as
+ * opposed to a collection of them) is never concatenated with anything
+ * because of operator precedence.) The operand of some types of node is
+ * a literal string; for others, it is a node leading into a sub-FSM. In
+ * particular, the operand of a BRANCH node is the first node of the branch.
+ * (NB this is *not* a tree structure: the tail of the branch connects
+ * to the thing following the set of BRANCHes.) The opcodes are:
+ */
+
+// definition number opnd? meaning
+#define END 0 // no End of program.
+#define BOL 1 // no Match "" at beginning of line.
+#define EOL 2 // no Match "" at end of line.
+#define ANY 3 // no Match any one character.
+#define ANYOF 4 // str Match any character in this string.
+#define ANYBUT 5 // str Match any character not in this
+ // string.
+#define BRANCH 6 // node Match this alternative, or the
+ // next...
+#define BACK 7 // no Match "", "next" ptr points backward.
+#define EXACTLY 8 // str Match this string.
+#define NOTHING 9 // no Match empty string.
+#define STAR 10 // node Match this (simple) thing 0 or more
+ // times.
+#define PLUS 11 // node Match this (simple) thing 1 or more
+ // times.
+#define OPEN 20 // no Mark this point in input as start of
+ // #n.
+// OPEN+1 is number 1, etc.
+#define CLOSE 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)&0377)<<8) + (*((p)+2)&0377))
+#define OPERAND(p) ((p) + 3)
+
+const unsigned char MAGIC = 0234;
+/*
+ * Utility definitions.
+ */
+
+#define UCHARAT(p) ((const unsigned char*)(p))[0]
+
+
+#define FAIL(m) { regerror(m); return(NULL); }
+#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
+#define META "^$.[()|?+*\\"
+
+
+/*
+ * Flags to be passed up and down.
+ */
+#define HASWIDTH 01 // Known never to match null string.
+#define SIMPLE 02 // Simple enough to be STAR/PLUS operand.
+#define SPSTART 04 // Starts with * or +.
+#define WORST 0 // Worst case.
+
+
+
+/////////////////////////////////////////////////////////////////////////
+//
+// COMPILE AND ASSOCIATED FUNCTIONS
+//
+/////////////////////////////////////////////////////////////////////////
+
+
+/*
+ * Global work variables for compile().
+ */
+static const char* regparse; // Input-scan pointer.
+static int regnpar; // () count.
+static char regdummy;
+static char* regcode; // Code-emit pointer; &regdummy = don't.
+static long regsize; // Code size.
+
+/*
+ * Forward declarations for compile()'s friends.
+ */
+// #ifndef static
+// #define static static
+// #endif
+static char* reg (int, int*);
+static char* regbranch (int*);
+static char* regpiece (int*);
+static char* regatom (int*);
+static char* regnode (char);
+static const char* regnext (register const char*);
+static char* regnext (register char*);
+static void regc (unsigned char);
+static void reginsert (char, char*);
+static void regtail (char*, const char*);
+static void regoptail (char*, const char*);
+
+#ifdef STRCSPN
+static int strcspn ();
+#endif
+
+
+
+/*
+ * 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.
+ */
+
+
+// compile -- compile a regular expression into internal code
+// for later pattern matching.
+
+void cmRegularExpression::compile (const char* exp) {
+ register const char* scan;
+ register const char* longest;
+ register unsigned long len;
+ int flags;
+
+ if (exp == NULL) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(No_Expr),
+ printf ("cmRegularExpression::compile(): No expression supplied.\n");
+ return;
+ }
+
+ // First pass: determine size, legality.
+ regparse = exp;
+ regnpar = 1;
+ regsize = 0L;
+ regcode = &regdummy;
+ regc(MAGIC);
+ if(!reg(0, &flags))
+ {
+ printf ("cmRegularExpression::compile(): Error in compile.\n");
+ return;
+ }
+ this->startp[0] = this->endp[0] = this->searchstring = NULL;
+
+ // Small enough for pointer-storage convention?
+ if (regsize >= 32767L) { // Probably could be 65535L.
+ //RAISE Error, SYM(cmRegularExpression), SYM(Expr_Too_Big),
+ printf ("cmRegularExpression::compile(): Expression too big.\n");
+ return;
+ }
+
+ // Allocate space.
+//#ifndef WIN32
+ if (this->program != NULL) delete [] this->program;
+//#endif
+ this->program = new char[regsize];
+ this->progsize = (int) regsize;
+
+ if (this->program == NULL) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Out_Of_Memory),
+ printf ("cmRegularExpression::compile(): Out of memory.\n");
+ return;
+ }
+
+ // Second pass: emit code.
+ regparse = exp;
+ regnpar = 1;
+ regcode = this->program;
+ regc(MAGIC);
+ reg(0, &flags);
+
+ // Dig out information for optimizations.
+ this->regstart = '\0'; // Worst-case defaults.
+ this->reganch = 0;
+ this->regmust = NULL;
+ this->regmlen = 0;
+ scan = this->program + 1; // First BRANCH.
+ if (OP(regnext(scan)) == END) { // Only one top-level choice.
+ scan = OPERAND(scan);
+
+ // Starting-point info.
+ if (OP(scan) == EXACTLY)
+ this->regstart = *OPERAND(scan);
+ else if (OP(scan) == BOL)
+ this->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 && strlen(OPERAND(scan)) >= len) {
+ longest = OPERAND(scan);
+ len = strlen(OPERAND(scan));
+ }
+ this->regmust = longest;
+ this->regmlen = len;
+ }
+ }
+}
+
+
+/*
+ - 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 (int paren, int *flagp) {
+ register char* ret;
+ register char* br;
+ register char* ender;
+ register int parno =0;
+ int flags;
+
+ *flagp = HASWIDTH; // Tentatively.
+
+ // Make an OPEN node, if parenthesized.
+ if (paren) {
+ if (regnpar >= NSUBEXP) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Too_Many_Parens),
+ printf ("cmRegularExpression::compile(): Too many parentheses.\n");
+ return 0;
+ }
+ parno = regnpar;
+ regnpar++;
+ ret = regnode(OPEN + parno);
+ }
+ else
+ ret = NULL;
+
+ // Pick up the branches, linking them together.
+ br = regbranch(&flags);
+ if (br == NULL)
+ return (NULL);
+ if (ret != NULL)
+ regtail(ret, br); // OPEN -> first.
+ else
+ ret = br;
+ if (!(flags & HASWIDTH))
+ *flagp &= ~HASWIDTH;
+ *flagp |= flags & SPSTART;
+ while (*regparse == '|') {
+ regparse++;
+ br = regbranch(&flags);
+ if (br == NULL)
+ return (NULL);
+ regtail(ret, br); // BRANCH -> BRANCH.
+ if (!(flags & HASWIDTH))
+ *flagp &= ~HASWIDTH;
+ *flagp |= flags & SPSTART;
+ }
+
+ // Make a closing node, and hook it on the end.
+ ender = regnode((paren) ? CLOSE + parno : END);
+ regtail(ret, ender);
+
+ // Hook the tails of the branches to the closing node.
+ for (br = ret; br != NULL; br = regnext(br))
+ regoptail(br, ender);
+
+ // Check for proper termination.
+ if (paren && *regparse++ != ')') {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Unmatched_Parens),
+ printf ("cmRegularExpression::compile(): Unmatched parentheses.\n");
+ return 0;
+ }
+ else if (!paren && *regparse != '\0') {
+ if (*regparse == ')') {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Unmatched_Parens),
+ printf ("cmRegularExpression::compile(): Unmatched parentheses.\n");
+ return 0;
+ }
+ else {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::compile(): Internal error.\n");
+ return 0;
+ }
+ // NOTREACHED
+ }
+ return (ret);
+}
+
+
+/*
+ - regbranch - one alternative of an | operator
+ *
+ * Implements the concatenation operator.
+ */
+static char* regbranch (int *flagp) {
+ register char* ret;
+ register char* chain;
+ register char* latest;
+ int flags;
+
+ *flagp = WORST; // Tentatively.
+
+ ret = regnode(BRANCH);
+ chain = NULL;
+ while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
+ latest = regpiece(&flags);
+ if (latest == NULL)
+ return (NULL);
+ *flagp |= flags & HASWIDTH;
+ if (chain == NULL) // First piece.
+ *flagp |= flags & SPSTART;
+ else
+ regtail(chain, latest);
+ chain = latest;
+ }
+ if (chain == NULL) // Loop ran zero times.
+ regnode(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 (int *flagp) {
+ register char* ret;
+ register char op;
+ register char* next;
+ int flags;
+
+ ret = regatom(&flags);
+ if (ret == NULL)
+ return (NULL);
+
+ op = *regparse;
+ if (!ISMULT(op)) {
+ *flagp = flags;
+ return (ret);
+ }
+
+ if (!(flags & HASWIDTH) && op != '?') {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Empty_Operand),
+ printf ("cmRegularExpression::compile() : *+ operand could be empty.\n");
+ return 0;
+ }
+ *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
+
+ if (op == '*' && (flags & SIMPLE))
+ reginsert(STAR, ret);
+ else if (op == '*') {
+ // 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 == '+' && (flags & SIMPLE))
+ reginsert(PLUS, ret);
+ else if (op == '+') {
+ // Emit x+ as x(&|), where & means "self".
+ next = regnode(BRANCH); // Either
+ regtail(ret, next);
+ regtail(regnode(BACK), ret); // loop back
+ regtail(next, regnode(BRANCH)); // or
+ regtail(ret, regnode(NOTHING)); // null.
+ }
+ else if (op == '?') {
+ // Emit x? as (x|)
+ reginsert(BRANCH, ret); // Either x
+ regtail(ret, regnode(BRANCH)); // or
+ next = regnode(NOTHING);// null.
+ regtail(ret, next);
+ regoptail(ret, next);
+ }
+ regparse++;
+ if (ISMULT(*regparse)) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Nested_Operand),
+ printf ("cmRegularExpression::compile(): Nested *?+.\n");
+ return 0;
+ }
+ 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 (int *flagp) {
+ register char* ret;
+ int flags;
+
+ *flagp = WORST; // Tentatively.
+
+ switch (*regparse++) {
+ case '^':
+ ret = regnode(BOL);
+ break;
+ case '$':
+ ret = regnode(EOL);
+ break;
+ case '.':
+ ret = regnode(ANY);
+ *flagp |= HASWIDTH | SIMPLE;
+ break;
+ case '[':{
+ register int rxpclass;
+ register int rxpclassend;
+
+ if (*regparse == '^') { // Complement of range.
+ ret = regnode(ANYBUT);
+ regparse++;
+ }
+ else
+ ret = regnode(ANYOF);
+ if (*regparse == ']' || *regparse == '-')
+ regc(*regparse++);
+ while (*regparse != '\0' && *regparse != ']') {
+ if (*regparse == '-') {
+ regparse++;
+ if (*regparse == ']' || *regparse == '\0')
+ regc('-');
+ else {
+ rxpclass = UCHARAT(regparse - 2) + 1;
+ rxpclassend = UCHARAT(regparse);
+ if (rxpclass > rxpclassend + 1) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Invalid_Range),
+ printf ("cmRegularExpression::compile(): Invalid range in [].\n");
+ return 0;
+ }
+ for (; rxpclass <= rxpclassend; rxpclass++)
+ regc(rxpclass);
+ regparse++;
+ }
+ }
+ else
+ regc(*regparse++);
+ }
+ regc('\0');
+ if (*regparse != ']') {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Unmatched_Bracket),
+ printf ("cmRegularExpression::compile(): Unmatched [].\n");
+ return 0;
+ }
+ regparse++;
+ *flagp |= HASWIDTH | SIMPLE;
+ }
+ break;
+ case '(':
+ ret = reg(1, &flags);
+ if (ret == NULL)
+ return (NULL);
+ *flagp |= flags & (HASWIDTH | SPSTART);
+ break;
+ case '\0':
+ case '|':
+ case ')':
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::compile(): Internal error.\n"); // Never here
+ return 0;
+ case '?':
+ case '+':
+ case '*':
+ //RAISE Error, SYM(cmRegularExpression), SYM(No_Operand),
+ printf ("cmRegularExpression::compile(): ?+* follows nothing.\n");
+ return 0;
+ case '\\':
+ if (*regparse == '\0') {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Trailing_Backslash),
+ printf ("cmRegularExpression::compile(): Trailing backslash.\n");
+ return 0;
+ }
+ ret = regnode(EXACTLY);
+ regc(*regparse++);
+ regc('\0');
+ *flagp |= HASWIDTH | SIMPLE;
+ break;
+ default:{
+ register int len;
+ register char ender;
+
+ regparse--;
+ len = strcspn(regparse, META);
+ if (len <= 0) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::compile(): Internal error.\n");
+ return 0;
+ }
+ 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('\0');
+ }
+ break;
+ }
+ return (ret);
+}
+
+
+/*
+ - regnode - emit a node
+ Location.
+ */
+static char* regnode (char op) {
+ register char* ret;
+ register char* ptr;
+
+ ret = regcode;
+ if (ret == &regdummy) {
+ regsize += 3;
+ return (ret);
+ }
+
+ ptr = ret;
+ *ptr++ = op;
+ *ptr++ = '\0'; // Null "next" pointer.
+ *ptr++ = '\0';
+ regcode = ptr;
+
+ return (ret);
+}
+
+
+/*
+ - regc - emit (if appropriate) a byte of code
+ */
+static void regc (unsigned char b) {
+ if (regcode != &regdummy)
+ *regcode++ = b;
+ else
+ regsize++;
+}
+
+
+/*
+ - reginsert - insert an operator in front of already-emitted operand
+ *
+ * Means relocating the operand.
+ */
+static void reginsert (char op, char* opnd) {
+ register char* src;
+ register char* dst;
+ register char* place;
+
+ if (regcode == &regdummy) {
+ 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++ = '\0';
+ *place++ = '\0';
+}
+
+
+/*
+ - regtail - set the next-pointer at the end of a node chain
+ */
+static void regtail (char* p, const char* val) {
+ register char* scan;
+ register char* temp;
+ register int offset;
+
+ if (p == &regdummy)
+ return;
+
+ // Find last node.
+ scan = p;
+ for (;;) {
+ temp = regnext(scan);
+ if (temp == NULL)
+ break;
+ scan = temp;
+ }
+
+ if (OP(scan) == BACK)
+ offset = (const char*)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 (char* p, const char* val) {
+ // "Operandless" and "op != BRANCH" are synonymous in practice.
+ if (p == NULL || p == &regdummy || OP(p) != BRANCH)
+ return;
+ regtail(OPERAND(p), val);
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+//
+// find and friends
+//
+////////////////////////////////////////////////////////////////////////
+
+
+/*
+ * Global work variables for find().
+ */
+static const char* reginput; // String-input pointer.
+static const char* regbol; // Beginning of input, for ^ check.
+static const char* *regstartp; // Pointer to startp array.
+static const char* *regendp; // Ditto for endp.
+
+/*
+ * Forwards.
+ */
+static int regtry (const char*, const char* *,
+ const char* *, const char*);
+static int regmatch (const char*);
+static int regrepeat (const char*);
+
+#ifdef DEBUG
+int regnarrate = 0;
+void regdump ();
+static char* regprop ();
+#endif
+
+bool cmRegularExpression::find (std::string const& s) {
+return find(s.c_str());
+}
+
+
+
+// find -- Matches the regular expression to the given string.
+// Returns true if found, and sets start and end indexes accordingly.
+
+bool cmRegularExpression::find (const char* string) {
+ register const char* s;
+
+ this->searchstring = string;
+
+ // Check validity of program.
+ if (!this->program || UCHARAT(this->program) != MAGIC) {
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::find(): Compiled regular expression corrupted.\n");
+ return 0;
+ }
+
+ // If there is a "must appear" string, look for it.
+ if (this->regmust != NULL) {
+ s = string;
+ while ((s = strchr(s, this->regmust[0])) != NULL) {
+ if (strncmp(s, this->regmust, this->regmlen) == 0)
+ break; // Found it.
+ s++;
+ }
+ if (s == NULL) // Not present.
+ return (0);
+ }
+
+ // Mark beginning of line for ^ .
+ regbol = string;
+
+ // Simplest case: anchored match need be tried only once.
+ if (this->reganch)
+ return (regtry(string, this->startp, this->endp, this->program) != 0);
+
+ // Messy cases: unanchored match.
+ s = string;
+ if (this->regstart != '\0')
+ // We know what char it must start with.
+ while ((s = strchr(s, this->regstart)) != NULL) {
+ if (regtry(s, this->startp, this->endp, this->program))
+ return (1);
+ s++;
+
+ }
+ else
+ // We don't -- general case.
+ do {
+ if (regtry(s, this->startp, this->endp, this->program))
+ return (1);
+ } while (*s++ != '\0');
+
+ // Failure.
+ return (0);
+}
+
+
+/*
+ - regtry - try match at specific point
+ 0 failure, 1 success
+ */
+static int regtry (const char* string, const char* *start,
+ const char* *end, const char* prog) {
+ register int i;
+ register const char* *sp1;
+ register const char* *ep;
+
+ reginput = string;
+ regstartp = start;
+ regendp = end;
+
+ sp1 = start;
+ ep = end;
+ for (i = NSUBEXP; i > 0; i--) {
+ *sp1++ = NULL;
+ *ep++ = NULL;
+ }
+ if (regmatch(prog + 1)) {
+ start[0] = string;
+ end[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.
+ * 0 failure, 1 success
+ */
+static int regmatch (const char* prog) {
+ register const char* scan; // Current node.
+ const char* next; // Next node.
+
+ scan = prog;
+
+ while (scan != NULL) {
+
+ next = regnext(scan);
+
+ switch (OP(scan)) {
+ case BOL:
+ if (reginput != regbol)
+ return (0);
+ break;
+ case EOL:
+ if (*reginput != '\0')
+ return (0);
+ break;
+ case ANY:
+ if (*reginput == '\0')
+ return (0);
+ reginput++;
+ break;
+ case EXACTLY:{
+ register int len;
+ register const 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 == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
+ return (0);
+ reginput++;
+ break;
+ case ANYBUT:
+ if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != 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 const char* save;
+
+ no = OP(scan) - OPEN;
+ save = reginput;
+
+ if (regmatch(next)) {
+
+ //
+ // Don't set startp if some later invocation of the
+ // same parentheses already has.
+ //
+ if (regstartp[no] == NULL)
+ regstartp[no] = save;
+ 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 int no;
+ register const char* save;
+
+ no = OP(scan) - CLOSE;
+ save = reginput;
+
+ if (regmatch(next)) {
+
+ //
+ // Don't set endp if some later invocation of the
+ // same parentheses already has.
+ //
+ if (regendp[no] == NULL)
+ regendp[no] = save;
+ return (1);
+ }
+ else
+ return (0);
+ }
+// break;
+ case BRANCH:{
+
+ register const char* save;
+
+ if (OP(next) != BRANCH) // No choice.
+ next = OPERAND(scan); // Avoid recursion.
+ else {
+ do {
+ save = reginput;
+ if (regmatch(OPERAND(scan)))
+ return (1);
+ reginput = save;
+ scan = regnext(scan);
+ } while (scan != NULL && OP(scan) == BRANCH);
+ return (0);
+ // NOTREACHED
+ }
+ }
+ break;
+ case STAR:
+ case PLUS:{
+ register char nextch;
+ register int no;
+ register const char* save;
+ register int min_no;
+
+ //
+ // Lookahead to avoid useless match attempts when we know
+ // what character comes next.
+ //
+ nextch = '\0';
+ if (OP(next) == EXACTLY)
+ nextch = *OPERAND(next);
+ min_no = (OP(scan) == STAR) ? 0 : 1;
+ save = reginput;
+ no = regrepeat(OPERAND(scan));
+ while (no >= min_no) {
+ // If it could work, try it.
+ if (nextch == '\0' || *reginput == nextch)
+ if (regmatch(next))
+ return (1);
+ // Couldn't or didn't -- back up.
+ no--;
+ reginput = save + no;
+ }
+ return (0);
+ }
+// break;
+ case END:
+ return (1); // Success!
+
+ default:
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::find(): Internal error -- memory corrupted.\n");
+ return 0;
+ }
+ scan = next;
+ }
+
+ //
+ // We get here only if there's trouble -- normally "case END" is the
+ // terminating point.
+ //
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cmRegularExpression::find(): Internal error -- corrupted pointers.\n");
+ return (0);
+}
+
+
+/*
+ - regrepeat - repeatedly match something simple, report how many
+ */
+static int regrepeat (const char* p) {
+ register int count = 0;
+ register const char* scan;
+ register const 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 != '\0' && strchr(opnd, *scan) != NULL) {
+ count++;
+ scan++;
+ }
+ break;
+ case ANYBUT:
+ while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
+ count++;
+ scan++;
+ }
+ break;
+ default: // Oh dear. Called inappropriately.
+ //RAISE Error, SYM(cmRegularExpression), SYM(Internal_Error),
+ printf ("cm RegularExpression::find(): Internal error.\n");
+ return 0;
+ }
+ reginput = scan;
+ return (count);
+}
+
+
+/*
+ - regnext - dig the "next" pointer out of a node
+ */
+static const char* regnext (register const char* p) {
+ register int offset;
+
+ if (p == &regdummy)
+ return (NULL);
+
+ offset = NEXT(p);
+ if (offset == 0)
+ return (NULL);
+
+ if (OP(p) == BACK)
+ return (p - offset);
+ else
+ return (p + offset);
+}
+
+
+static char* regnext (register char* p) {
+ register int offset;
+
+ if (p == &regdummy)
+ return (NULL);
+
+ offset = NEXT(p);
+ if (offset == 0)
+ return (NULL);
+
+ if (OP(p) == BACK)
+ return (p - offset);
+ else
+ return (p + offset);
+}
generated by cgit v0.12 at 2024-12-29 06:21:57 (GMT)