static const char CVSID[] = "$Id: regularExp.c,v 1.25 2004/08/20 16:37:30 edg Exp $"; /*------------------------------------------------------------------------* * `CompileRE', `ExecRE', and `substituteRE' -- regular expression parsing * * This is a HIGHLY ALTERED VERSION of Henry Spencer's `regcomp' and * `regexec' code adapted for NEdit. * * .-------------------------------------------------------------------. * | ORIGINAL COPYRIGHT NOTICE: | * | | * | Copyright (c) 1986 by University of Toronto. | * | Written by Henry Spencer. Not derived from licensed software. | * | | * | Permission is granted to anyone to use this software for any | * | purpose on any computer system, and to redistribute it freely, | * | subject to the following restrictions: | * | | * | 1. The author is not responsible for the consequences of use of | * | this software, no matter how awful, even if they arise | * | from defects in it. | * | | * | 2. The origin of this software must not be misrepresented, either | * | by explicit claim or by omission. | * | | * | 3. Altered versions must be plainly marked as such, and must not | * | be misrepresented as being the original software. | * `-------------------------------------------------------------------' * * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License as published by the Free Software * Foundation; either version 2 of the License, or (at your option) any later * version. In addition, you may distribute version of this program linked to * Motif or Open Motif. See README for details. * * This software is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * for more details. * * You should have received a copy of the GNU General Public License along with * software; if not, write to the Free Software Foundation, Inc., 59 Temple * Place, Suite 330, Boston, MA 02111-1307 USA * * * 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. * -- Henry Spencer * (Yes, it did!) -- Christopher Conrad, Dec. 1999 * * January, 1994, Mark Edel * Consolidated files, changed names of external functions to avoid * potential conflicts with native regcomp and regexec functions, changed * error reporting to NEdit form, added multi-line and reverse searching, * and added \n \t \u \U \l \L. * * June, 1996, Mark Edel * Bug in NEXT macro, didn't work for expressions which compiled to over * 256 bytes. * * December, 1999, Christopher Conrad * Reformatted code for readability, improved error output, added octal and * hexadecimal escapes, added back-references (\1-\9), added positive look * ahead: (?=...), added negative lookahead: (?!...), added non-capturing * parentheses: (?:...), added case insensitive constructs (?i...) and * (?I...), added newline matching constructs (?n...) and (?N...), added * regex comments: (?#...), added shortcut escapes: \d\D\l\L\s\S\w\W\y\Y. * Added "not a word boundary" anchor \B. * * July, 2002, Eddy De Greef * Added look behind, both positive (?<=...) and negative (? #include #include #include #include #ifdef HAVE_DEBUG_H #include "../debug.h" #endif /* The first byte of the regexp internal `program' is a magic number to help gaurd against corrupted data; the compiled regex code really begins in the second byte. */ #define MAGIC 0234 /* The "internal use only" fields in `regexp.h' are present to pass info from * `CompileRE' to `ExecRE' which permits the execute phase to run lots faster on * simple cases. They are: * * match_start Character that must begin a match; '\0' if none obvious. * anchor Is the match anchored (at beginning-of-line only)? * * `match_start' and `anchor' permit very fast decisions on suitable starting * points for a match, considerably reducing the work done by ExecRE. */ /* STRUCTURE FOR A REGULAR EXPRESSION (regex) `PROGRAM'. * * This is essentially a linear encoding of a nondeterministic finite-state * machine or NFA (aka syntax charts or `railroad normal form' in parsing * technology). Each node is an opcode plus a NEXT pointer, possibly * followed by operands. 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 nodes 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 VALUE MEANING */ #define END 1 /* End of program. */ /* Zero width positional assertions. */ #define BOL 2 /* Match position at beginning of line. */ #define EOL 3 /* Match position at end of line. */ #define BOWORD 4 /* Match "" representing word delimiter or BOL */ #define EOWORD 5 /* Match "" representing word delimiter or EOL */ #define NOT_BOUNDARY 6 /* Not word boundary (\B, opposite of < and >) */ /* Op codes with null terminated string operands. */ #define EXACTLY 7 /* Match this string. */ #define SIMILAR 8 /* Match this case insensitive string */ #define ANY_OF 9 /* Match any character in the set. */ #define ANY_BUT 10 /* Match any character not in the set. */ /* Op codes to match any character. */ #define ANY 11 /* Match any one character (implements '.') */ #define EVERY 12 /* Same as ANY but matches newline. */ /* Shortcut escapes, \d, \D, \l, \L, \s, \S, \w, \W, \y, \Y. */ #define DIGIT 13 /* Match any digit, i.e. [0123456789] */ #define NOT_DIGIT 14 /* Match any non-digit, i.e. [^0123456789] */ #define LETTER 15 /* Match any letter character [a-zA-Z] */ #define NOT_LETTER 16 /* Match any non-letter character [^a-zA-Z] */ #define SPACE 17 /* Match any whitespace character EXCEPT \n */ #define SPACE_NL 18 /* Match any whitespace character INCLUDING \n */ #define NOT_SPACE 19 /* Match any non-whitespace character */ #define NOT_SPACE_NL 20 /* Same as NOT_SPACE but matches newline. */ #define WORD_CHAR 21 /* Match any word character [a-zA-Z0-9_] */ #define NOT_WORD_CHAR 22 /* Match any non-word character [^a-zA-Z0-9_] */ #define IS_DELIM 23 /* Match any character that's a word delimiter */ #define NOT_DELIM 24 /* Match any character NOT a word delimiter */ /* Quantifier nodes. (Only applied to SIMPLE nodes. Quantifiers applied to non SIMPLE nodes or larger atoms are implemented using complex constructs.)*/ #define STAR 25 /* Match this (simple) thing 0 or more times. */ #define LAZY_STAR 26 /* Minimal matching STAR */ #define QUESTION 27 /* Match this (simple) thing 0 or 1 times. */ #define LAZY_QUESTION 28 /* Minimal matching QUESTION */ #define PLUS 29 /* Match this (simple) thing 1 or more times. */ #define LAZY_PLUS 30 /* Minimal matching PLUS */ #define BRACE 31 /* Match this (simple) thing m to n times. */ #define LAZY_BRACE 32 /* Minimal matching BRACE */ /* Nodes used to build complex constructs. */ #define NOTHING 33 /* Match empty string (always matches) */ #define BRANCH 34 /* Match this alternative, or the next... */ #define BACK 35 /* Always matches, NEXT ptr points backward. */ #define INIT_COUNT 36 /* Initialize {m,n} counter to zero */ #define INC_COUNT 37 /* Increment {m,n} counter by one */ #define TEST_COUNT 38 /* Test {m,n} counter against operand */ /* Back Reference nodes. */ #define BACK_REF 39 /* Match latest matched parenthesized text */ #define BACK_REF_CI 40 /* Case insensitive version of BACK_REF */ #define X_REGEX_BR 41 /* Cross-Regex Back-Ref for syntax highlighting */ #define X_REGEX_BR_CI 42 /* Case insensitive version of X_REGEX_BR_CI */ /* Various nodes used to implement parenthetical constructs. */ #define POS_AHEAD_OPEN 43 /* Begin positive look ahead */ #define NEG_AHEAD_OPEN 44 /* Begin negative look ahead */ #define LOOK_AHEAD_CLOSE 45 /* End positive or negative look ahead */ #define POS_BEHIND_OPEN 46 /* Begin positive look behind */ #define NEG_BEHIND_OPEN 47 /* Begin negative look behind */ #define LOOK_BEHIND_CLOSE 48 /* Close look behind */ #define OPEN 49 /* Open for capturing parentheses. */ /* OPEN+1 is number 1, etc. */ #define CLOSE (OPEN + NSUBEXP) /* Close for capturing parentheses. */ #define LAST_PAREN (CLOSE + NSUBEXP) #if (LAST_PAREN > UCHAR_MAX) #error "Too many parentheses for storage in an unsigned char (LAST_PAREN too big.)" #endif /* The next_ptr () function can consume up to 30% of the time during matching because it is called an immense number of times (an average of 25 next_ptr() calls per match() call was witnessed for Perl syntax highlighting). Therefore it is well worth removing some of the function call overhead by selectively inlining the next_ptr() calls. Moreover, the inlined code can be simplified for matching because one of the tests, only necessary during compilation, can be left out. The net result of using this inlined version at two critical places is a 25% speedup (again, witnesses on Perl syntax highlighting). */ #define NEXT_PTR(in_ptr, out_ptr)\ next_ptr_offset = GET_OFFSET (in_ptr);\ if (next_ptr_offset == 0)\ out_ptr = NULL;\ else {\ if (GET_OP_CODE (in_ptr) == BACK)\ out_ptr = in_ptr - next_ptr_offset;\ else \ out_ptr = in_ptr + next_ptr_offset;\ } /* OPCODE NOTES: ------------ All nodes consist of an 8 bit op code followed by 2 bytes that make up a 16 bit NEXT pointer. Some nodes have a null terminated character string operand following the NEXT pointer. Other nodes may have an 8 bit index operand. The TEST_COUNT node has an index operand followed by a 16 bit test value. The BRACE and LAZY_BRACE nodes have two 16 bit values for min and max but no index value. SIMILAR Operand(s): null terminated string Implements a case insensitive match of a string. Mostly intended for use in syntax highlighting patterns for keywords of languages like FORTRAN and Ada that are case insensitive. The regex text in this node is converted to lower case during regex compile. DIGIT, NOT_DIGIT, LETTER, NOT_LETTER, SPACE, NOT_SPACE, WORD_CHAR, NOT_WORD_CHAR Operand(s): None Implements shortcut escapes \d, \D, \l, \L, \s, \S, \w, \W. The locale aware ANSI functions isdigit(), isalpha(), isalnun(), and isspace() are used to implement these in the hopes of increasing portability. NOT_BOUNDARY Operand(s): None Implements \B as a zero width assertion that the current character is NOT on a word boundary. Word boundaries are defined to be the position between two characters where one of those characters is one of the dynamically defined word delimiters, and the other character is not. IS_DELIM Operand(s): None Implements \y as any character that is one of the dynamically specified word delimiters. NOT_DELIM Operand(s): None Implements \Y as any character that is NOT one of the dynamically specified word delimiters. STAR, PLUS, QUESTION, and complex '*', '+', and '?' Operand(s): None (Note: NEXT pointer is usually zero. The code that processes this node skips over it.) Complex (parenthesized) versions implemented as circular BRANCH structures using BACK. SIMPLE versions (one character per match) are implemented separately for speed and to minimize recursion. BRACE, LAZY_BRACE Operand(s): minimum value (2 bytes), maximum value (2 bytes) Implements the {m,n} construct for atoms that are SIMPLE. BRANCH Operand(s): None 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 Operand(s): None Normal NEXT pointers all implicitly point forward. Back implicitly points backward. BACK exists to make loop structures possible. INIT_COUNT Operand(s): index (1 byte) Initializes the count array element referenced by the index operand. This node is used to build general (i.e. parenthesized) {m,n} constructs. INC_COUNT Operand(s): index (1 byte) Increments the count array element referenced by the index operand. This node is used to build general (i.e. parenthesized) {m,n} constructs. TEST_COUNT Operand(s): index (1 byte), test value (2 bytes) Tests the current value of the count array element specified by the index operand against the test value. If the current value is less than the test value, control passes to the node after that TEST_COUNT node. Otherwise control passes to the node referenced by the NEXT pointer for the TEST_COUNT node. This node is used to build general (i.e. parenthesized) {m,n} constructs. BACK_REF, BACK_REF_CI Operand(s): index (1 byte, value 1-9) Implements back references. This node will attempt to match whatever text was most recently captured by the index'th set of parentheses. BACK_REF_CI is case insensitive version. X_REGEX_BR, X_REGEX_BR_CI (NOT IMPLEMENTED YET) Operand(s): index (1 byte, value 1-9) Implements back references into a previously matched but separate regular expression. This is used by syntax highlighting patterns. This node will attempt to match whatever text was most captured by the index'th set of parentheses of the separate regex passed to ExecRE. X_REGEX_BR_CI is case insensitive version. POS_AHEAD_OPEN, NEG_AHEAD_OPEN, LOOK_AHEAD_CLOSE Operand(s): None Implements positive and negative look ahead. Look ahead is an assertion that something is either there or not there. Once this is determined the regex engine backtracks to where it was just before the look ahead was encountered, i.e. look ahead is a zero width assertion. POS_BEHIND_OPEN, NEG_BEHIND_OPEN, LOOK_BEHIND_CLOSE Operand(s): 2x2 bytes for OPEN (match boundaries), None for CLOSE Implements positive and negative look behind. Look behind is an assertion that something is either there or not there in front of the current position. Look behind is a zero width assertion, with the additional constraint that it must have a bounded length (for complexity and efficiency reasons; note that most other implementation even impose fixed length). OPEN, CLOSE Operand(s): None OPEN + n = Start of parenthesis 'n', CLOSE + n = Close of parenthesis 'n', and are numbered at compile time. */ /* A node is one char of opcode followed by two chars of NEXT pointer plus * any operands. 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 NEXT_PTR_SIZE is vast overkill for most things, * but allows patterns to get big without disasters. */ #define OP_CODE_SIZE 1 #define NEXT_PTR_SIZE 2 #define INDEX_SIZE 1 #define LENGTH_SIZE 4 #define NODE_SIZE (NEXT_PTR_SIZE + OP_CODE_SIZE) #define GET_OP_CODE(p) (*(unsigned char *)(p)) #define OPERAND(p) ((p) + NODE_SIZE) #define GET_OFFSET(p) ((( *((p) + 1) & 0377) << 8) + (( *((p) + 2)) & 0377)) #define PUT_OFFSET_L(v) (unsigned char)(((v) >> 8) & 0377) #define PUT_OFFSET_R(v) (unsigned char) ((v) & 0377) #define GET_LOWER(p) ((( *((p) + NODE_SIZE) & 0377) << 8) + \ (( *((p) + NODE_SIZE+1)) & 0377)) #define GET_UPPER(p) ((( *((p) + NODE_SIZE+2) & 0377) << 8) + \ (( *((p) + NODE_SIZE+3)) & 0377)) /* Utility definitions. */ #define REG_FAIL(m) {*Error_Ptr = (m); return (NULL);} #define IS_QUANTIFIER(c) ((c) == '*' || (c) == '+' || \ (c) == '?' || (c) == Brace_Char) #define SET_BIT(i,n) ((i) |= (1 << ((n) - 1))) #define TEST_BIT(i,n) ((i) & (1 << ((n) - 1))) #define U_CHAR_AT(p) ((unsigned int) *(unsigned char *)(p)) /* Flags to be passed up and down via function parameters during compile. */ #define WORST 0 /* Worst case. No assumptions can be made.*/ #define HAS_WIDTH 1 /* Known never to match null string. */ #define SIMPLE 2 /* Simple enough to be STAR/PLUS operand. */ #define NO_PAREN 0 /* Only set by initial call to "chunk". */ #define PAREN 1 /* Used for normal capturing parentheses. */ #define NO_CAPTURE 2 /* Non-capturing parentheses (grouping only). */ #define INSENSITIVE 3 /* Case insensitive parenthetical construct */ #define SENSITIVE 4 /* Case sensitive parenthetical construct */ #define NEWLINE 5 /* Construct to match newlines in most cases */ #define NO_NEWLINE 6 /* Construct to match newlines normally */ #define REG_INFINITY 0UL #define REG_ZERO 0UL #define REG_ONE 1UL /* Flags for function shortcut_escape() */ #define CHECK_ESCAPE 0 /* Check an escape sequence for validity only. */ #define CHECK_CLASS_ESCAPE 1 /* Check the validity of an escape within a character class */ #define EMIT_CLASS_BYTES 2 /* Emit equivalent character class bytes, e.g \d=0123456789 */ #define EMIT_NODE 3 /* Emit the appropriate node. */ /* Array sizes for arrays used by function init_ansi_classes. */ #define WHITE_SPACE_SIZE 16 #define ALNUM_CHAR_SIZE 256 /* Number of bytes to offset from the beginning of the regex program to the start of the actual compiled regex code, i.e. skipping over the MAGIC number and the two counters at the front. */ #define REGEX_START_OFFSET 3 #define MAX_COMPILED_SIZE 32767UL /* Largest size a compiled regex can be. Probably could be 65535UL. */ /* Global work variables for `CompileRE'. */ static unsigned char *Reg_Parse; /* Input scan ptr (scans user's regex) */ static int Total_Paren; /* Parentheses, (), counter. */ static int Num_Braces; /* Number of general {m,n} constructs. {m,n} quantifiers of SIMPLE atoms are not included in this count. */ static int Closed_Parens; /* Bit flags indicating () closure. */ static int Paren_Has_Width; /* Bit flags indicating ()'s that are known to not match the empty string */ static unsigned char Compute_Size; /* Address of this used as flag. */ static unsigned char *Code_Emit_Ptr; /* When Code_Emit_Ptr is set to &Compute_Size no code is emitted. Instead, the size of code that WOULD have been generated is accumulated in Reg_Size. Otherwise, Code_Emit_Ptr points to where compiled regex code is to be written. */ static unsigned long Reg_Size; /* Size of compiled regex code. */ static char **Error_Ptr; /* Place to store error messages so they can be returned by `CompileRE' */ static char Error_Text [128];/* Sting to build error messages in. */ static unsigned char White_Space [WHITE_SPACE_SIZE]; /* Arrays used by */ static unsigned char Word_Char [ALNUM_CHAR_SIZE]; /* functions */ static unsigned char Letter_Char [ALNUM_CHAR_SIZE]; /* init_ansi_classes () */ /* and shortcut_escape (). */ static unsigned char ASCII_Digits [] = "0123456789"; /* Same for all */ /* locales. */ static int Is_Case_Insensitive; static int Match_Newline; static int Enable_Counting_Quantifier = 1; static unsigned char Brace_Char; static unsigned char Default_Meta_Char [] = "{.*+?[(|)^<>$"; static unsigned char *Meta_Char; typedef struct { long lower; long upper; } len_range; /* Forward declarations for functions used by `CompileRE'. */ static unsigned char * alternative (int *flag_param, len_range *range_param); static unsigned char * back_ref (unsigned char *c, int *flag_param, int emit); static unsigned char * chunk (int paren, int *flag_param, len_range *range_param); static void emit_byte (unsigned char c); static void emit_class_byte (unsigned char c); static unsigned char * emit_node (int op_code); static unsigned char * emit_special (unsigned char op_code, unsigned long test_val, int index); static unsigned char literal_escape (unsigned char c); static unsigned char numeric_escape (unsigned char c, unsigned char **parse); static unsigned char * atom (int *flag_param, len_range *range_param); static void reg_error (char *str); static unsigned char * insert (unsigned char op, unsigned char *opnd, long min, long max, int index); static unsigned char * next_ptr (unsigned char *ptr); static void offset_tail (unsigned char *ptr, int offset, unsigned char *val); static void branch_tail (unsigned char *ptr, int offset, unsigned char *val); static unsigned char * piece (int *flag_param, len_range *range_param); static void tail (unsigned char *search_from, unsigned char *point_t); static unsigned char * shortcut_escape (unsigned char c, int *flag_param, int emit); static int init_ansi_classes (void); /*----------------------------------------------------------------------* * CompileRE * * Compiles a regular expression into the internal format used by * `ExecRE'. * * The default behaviour wrt. case sensitivity and newline matching can * be controlled through the defaultFlags argument (Markus Schwarzenberg). * Future extensions are possible by using other flag bits. * Note that currently only the case sensitivity flag is effectively used. * * Beware that the optimization and preparation code in here knows about * some of the structure of the compiled regexp. *----------------------------------------------------------------------*/ regexp * CompileRE (const char *exp, char **errorText, int defaultFlags) { register regexp *comp_regex = NULL; register unsigned char *scan; int flags_local, pass; len_range range_local; if (Enable_Counting_Quantifier) { Brace_Char = '{'; Meta_Char = &Default_Meta_Char [0]; } else { Brace_Char = '*'; /* Bypass the '{' in */ Meta_Char = &Default_Meta_Char [1]; /* Default_Meta_Char */ } /* Set up errorText to receive failure reports. */ Error_Ptr = errorText; *Error_Ptr = ""; if (exp == NULL) REG_FAIL ("NULL argument, `CompileRE\'"); /* Initialize arrays used by function `shortcut_escape'. */ if (!init_ansi_classes ()) REG_FAIL ("internal error #1, `CompileRE\'"); Code_Emit_Ptr = &Compute_Size; Reg_Size = 0UL; /* 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.) */ for (pass = 1; pass <= 2; pass++) { /*-------------------------------------------* * FIRST PASS: Determine size and legality. * * SECOND PASS: Emit code. * *-------------------------------------------*/ /* Schwarzenberg: * If defaultFlags = 0 use standard defaults: * Is_Case_Insensitive: Case sensitive is the default * Match_Newline: Newlines are NOT matched by default * in character classes */ Is_Case_Insensitive = ((defaultFlags & REDFLT_CASE_INSENSITIVE) ? 1 : 0); Match_Newline = 0; /* ((defaultFlags & REDFLT_MATCH_NEWLINE) ? 1 : 0); Currently not used. Uncomment if needed. */ Reg_Parse = (unsigned char *) exp; Total_Paren = 1; Num_Braces = 0; Closed_Parens = 0; Paren_Has_Width = 0; emit_byte (MAGIC); emit_byte ('%'); /* Placeholder for num of capturing parentheses. */ emit_byte ('%'); /* Placeholder for num of general {m,n} constructs. */ if (chunk (NO_PAREN, &flags_local, &range_local) == NULL) return (NULL); /* Something went wrong */ if (pass == 1) { if (Reg_Size >= MAX_COMPILED_SIZE) { /* Too big for NEXT pointers NEXT_PTR_SIZE bytes long to span. This is a real issue since the first BRANCH node usually points to the end of the compiled regex code. */ sprintf (Error_Text, "regexp > %lu bytes", MAX_COMPILED_SIZE); REG_FAIL (Error_Text); } /* Allocate memory. */ comp_regex = (regexp *) malloc (sizeof (regexp) + Reg_Size); if (comp_regex == NULL) REG_FAIL ("out of memory in `CompileRE\'"); Code_Emit_Ptr = (unsigned char *) comp_regex->program; } } comp_regex->program [1] = (unsigned char) Total_Paren - 1; comp_regex->program [2] = (unsigned char) Num_Braces; /*----------------------------------------* * Dig out information for optimizations. * *----------------------------------------*/ comp_regex->match_start = '\0'; /* Worst-case defaults. */ comp_regex->anchor = 0; /* First BRANCH. */ scan = (unsigned char *) (comp_regex->program + REGEX_START_OFFSET); if (GET_OP_CODE (next_ptr (scan)) == END) { /* Only one top-level choice. */ scan = OPERAND (scan); /* Starting-point info. */ if (GET_OP_CODE (scan) == EXACTLY) { comp_regex->match_start = *OPERAND (scan); } else if (PLUS <= GET_OP_CODE (scan) && GET_OP_CODE (scan) <= LAZY_PLUS) { /* Allow x+ or x+? at the start of the regex to be optimized. */ if (GET_OP_CODE (scan + NODE_SIZE) == EXACTLY) { comp_regex->match_start = *OPERAND (scan + NODE_SIZE); } } else if (GET_OP_CODE (scan) == BOL) { comp_regex->anchor++; } } return (comp_regex); } /*----------------------------------------------------------------------* * chunk * * * * Process main body of regex or process a 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 unsigned char * chunk (int paren, int *flag_param, len_range *range_param) { register unsigned char *ret_val = NULL; register unsigned char *this_branch; register unsigned char *ender = NULL; register int this_paren = 0; int flags_local, first = 1, zero_width, i; int old_sensitive = Is_Case_Insensitive; int old_newline = Match_Newline; len_range range_local; int look_only = 0; unsigned char *emit_look_behind_bounds = NULL; *flag_param = HAS_WIDTH; /* Tentatively. */ range_param->lower = 0; /* Idem */ range_param->upper = 0; /* Make an OPEN node, if parenthesized. */ if (paren == PAREN) { if (Total_Paren >= NSUBEXP) { sprintf (Error_Text, "number of ()'s > %d", (int) NSUBEXP); REG_FAIL (Error_Text); } this_paren = Total_Paren; Total_Paren++; ret_val = emit_node (OPEN + this_paren); } else if (paren == POS_AHEAD_OPEN || paren == NEG_AHEAD_OPEN) { *flag_param = WORST; /* Look ahead is zero width. */ look_only = 1; ret_val = emit_node (paren); } else if (paren == POS_BEHIND_OPEN || paren == NEG_BEHIND_OPEN) { *flag_param = WORST; /* Look behind is zero width. */ look_only = 1; /* We'll overwrite the zero length later on, so we save the ptr */ ret_val = emit_special (paren, 0, 0); emit_look_behind_bounds = ret_val + NODE_SIZE; } else if (paren == INSENSITIVE) { Is_Case_Insensitive = 1; } else if (paren == SENSITIVE) { Is_Case_Insensitive = 0; } else if (paren == NEWLINE) { Match_Newline = 1; } else if (paren == NO_NEWLINE) { Match_Newline = 0; } /* Pick up the branches, linking them together. */ do { this_branch = alternative (&flags_local, &range_local); if (this_branch == NULL) return (NULL); if (first) { first = 0; *range_param = range_local; if (ret_val == NULL) ret_val = this_branch; } else if (range_param->lower >= 0) { if (range_local.lower >= 0) { if (range_local.lower < range_param->lower) range_param->lower = range_local.lower; if (range_local.upper > range_param->upper) range_param->upper = range_local.upper; } else { range_param->lower = -1; /* Branches have different lengths */ range_param->upper = -1; } } tail (ret_val, this_branch); /* Connect BRANCH -> BRANCH. */ /* If any alternative could be zero width, consider the whole parenthisized thing to be zero width. */ if (!(flags_local & HAS_WIDTH)) *flag_param &= ~HAS_WIDTH; /* Are there more alternatives to process? */ if (*Reg_Parse != '|') break; Reg_Parse++; } while (1); /* Make a closing node, and hook it on the end. */ if (paren == PAREN) { ender = emit_node (CLOSE + this_paren); } else if (paren == NO_PAREN) { ender = emit_node (END); } else if (paren == POS_AHEAD_OPEN || paren == NEG_AHEAD_OPEN) { ender = emit_node (LOOK_AHEAD_CLOSE); } else if (paren == POS_BEHIND_OPEN || paren == NEG_BEHIND_OPEN) { ender = emit_node (LOOK_BEHIND_CLOSE); } else { ender = emit_node (NOTHING); } tail (ret_val, ender); /* Hook the tails of the branch alternatives to the closing node. */ for (this_branch = ret_val; this_branch != NULL; ) { branch_tail (this_branch, NODE_SIZE, ender); this_branch = next_ptr (this_branch); } /* Check for proper termination. */ if (paren != NO_PAREN && *Reg_Parse++ != ')') { REG_FAIL ("missing right parenthesis \')\'"); } else if (paren == NO_PAREN && *Reg_Parse != '\0') { if (*Reg_Parse == ')') { REG_FAIL ("missing left parenthesis \'(\'"); } else { REG_FAIL ("junk on end"); /* "Can't happen" - NOTREACHED */ } } /* Check whether look behind has a fixed size */ if (emit_look_behind_bounds) { if (range_param->lower < 0) { REG_FAIL ("look-behind does not have a bounded size"); } if (range_param->upper > 65535L) { REG_FAIL ("max. look-behind size is too large (>65535)") } if (Code_Emit_Ptr != &Compute_Size) { *emit_look_behind_bounds++ = PUT_OFFSET_L (range_param->lower); *emit_look_behind_bounds++ = PUT_OFFSET_R (range_param->lower); *emit_look_behind_bounds++ = PUT_OFFSET_L (range_param->upper); *emit_look_behind_bounds = PUT_OFFSET_R (range_param->upper); } } /* For look ahead/behind, the length must be set to zero again */ if (look_only) { range_param->lower = 0; range_param->upper = 0; } zero_width = 0; /* Set a bit in Closed_Parens to let future calls to function `back_ref' know that we have closed this set of parentheses. */ if (paren == PAREN && this_paren <= (int)sizeof (Closed_Parens) * CHAR_BIT) { SET_BIT (Closed_Parens, this_paren); /* Determine if a parenthesized expression is modified by a quantifier that can have zero width. */ if (*(Reg_Parse) == '?' || *(Reg_Parse) == '*') { zero_width++; } else if (*(Reg_Parse) == '{' && Brace_Char == '{') { if (*(Reg_Parse + 1) == ',' || *(Reg_Parse + 1) == '}') { zero_width++; } else if (*(Reg_Parse + 1) == '0') { i = 2; while (*(Reg_Parse + i) == '0') i++; if (*(Reg_Parse + i) == ',') zero_width++; } } } /* If this set of parentheses is known to never match the empty string, set a bit in Paren_Has_Width to let future calls to function back_ref know that this set of parentheses has non-zero width. This will allow star (*) or question (?) quantifiers to be aplied to a back-reference that refers to this set of parentheses. */ if ((*flag_param & HAS_WIDTH) && paren == PAREN && !zero_width && this_paren <= (int)(sizeof (Paren_Has_Width) * CHAR_BIT)) { SET_BIT (Paren_Has_Width, this_paren); } Is_Case_Insensitive = old_sensitive; Match_Newline = old_newline; return (ret_val); } /*----------------------------------------------------------------------* * alternative * * Processes one alternative of an '|' operator. Connects the NEXT * pointers of each regex atom together sequentialy. *----------------------------------------------------------------------*/ static unsigned char * alternative (int *flag_param, len_range *range_param) { register unsigned char *ret_val; register unsigned char *chain; register unsigned char *latest; int flags_local; len_range range_local; *flag_param = WORST; /* Tentatively. */ range_param->lower = 0; /* Idem */ range_param->upper = 0; ret_val = emit_node (BRANCH); chain = NULL; /* Loop until we hit the start of the next alternative, the end of this set of alternatives (end of parentheses), or the end of the regex. */ while (*Reg_Parse != '|' && *Reg_Parse != ')' && *Reg_Parse != '\0') { latest = piece (&flags_local, &range_local); if (latest == NULL) return (NULL); /* Something went wrong. */ *flag_param |= flags_local & HAS_WIDTH; if (range_local.lower < 0) { /* Not a fixed length */ range_param->lower = -1; range_param->upper = -1; } else if (range_param->lower >= 0) { range_param->lower += range_local.lower; range_param->upper += range_local.upper; } if (chain != NULL) { /* Connect the regex atoms together sequentialy. */ tail (chain, latest); } chain = latest; } if (chain == NULL) { /* Loop ran zero times. */ (void) emit_node (NOTHING); } return (ret_val); } /*----------------------------------------------------------------------* * piece - something followed by possible '*', '+', '?', or "{m,n}" * * Note that the branching code sequences used for the general cases of * *, +. ?, and {m,n} 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 unsigned char * piece (int *flag_param, len_range *range_param) { register unsigned char *ret_val; register unsigned char *next; register unsigned char op_code; unsigned long min_max [2] = {REG_ZERO, REG_INFINITY}; int flags_local, i, brace_present = 0; int lazy = 0, comma_present = 0; int digit_present [2] = {0,0}; len_range range_local; ret_val = atom (&flags_local, &range_local); if (ret_val == NULL) return (NULL); /* Something went wrong. */ op_code = *Reg_Parse; if (!IS_QUANTIFIER (op_code)) { *flag_param = flags_local; *range_param = range_local; return (ret_val); } else if (op_code == '{') { /* {n,m} quantifier present */ brace_present++; Reg_Parse++; /* This code will allow specifying a counting range in any of the following forms: {m,n} between m and n. {,n} same as {0,n} or between 0 and infinity. {m,} same as {m,0} or between m and infinity. {m} same as {m,m} or exactly m. {,} same as {0,0} or between 0 and infinity or just '*'. {} same as {0,0} or between 0 and infinity or just '*'. Note that specifying a max of zero, {m,0} is not allowed in the regex itself, but it is implemented internally that way to support '*', '+', and {min,} constructs and signals an unlimited number. */ for (i = 0; i < 2; i++) { /* Look for digits of number and convert as we go. The numeric maximum value for max and min of 65,535 is due to using 2 bytes to store each value in the compiled regex code. */ while (isdigit (*Reg_Parse)) { /* (6553 * 10 + 6) > 65535 (16 bit max) */ if ((min_max [i] == 6553UL && (*Reg_Parse - '0') <= 5) || (min_max [i] <= 6552UL)) { min_max [i] = (min_max [i] * 10UL) + (unsigned long) (*Reg_Parse - '0'); Reg_Parse++; digit_present [i]++; } else { if (i == 0) { sprintf (Error_Text, "min operand of {%lu%c,???} > 65535", min_max [0], *Reg_Parse); } else { sprintf (Error_Text, "max operand of {%lu,%lu%c} > 65535", min_max [0], min_max [1], *Reg_Parse); } REG_FAIL (Error_Text); } } if (!comma_present && *Reg_Parse == ',') { comma_present++; Reg_Parse++; } } /* A max of zero can not be specified directly in the regex since it would signal a max of infinity. This code specifically disallows `{0,0}', `{,0}', and `{0}' which really means nothing to humans but would be interpreted as `{0,infinity}' or `*' if we didn't make this check. */ if (digit_present [0] && (min_max [0] == REG_ZERO) && !comma_present) { REG_FAIL ("{0} is an invalid range"); } else if (digit_present [0] && (min_max [0] == REG_ZERO) && digit_present [1] && (min_max [1] == REG_ZERO)) { REG_FAIL ("{0,0} is an invalid range"); } else if (digit_present [1] && (min_max [1] == REG_ZERO)) { if (digit_present [0]) { sprintf (Error_Text, "{%lu,0} is an invalid range", min_max [0]); REG_FAIL (Error_Text); } else { REG_FAIL ("{,0} is an invalid range"); } } if (!comma_present) min_max [1] = min_max [0]; /* {x} means {x,x} */ if (*Reg_Parse != '}') { REG_FAIL ("{m,n} specification missing right \'}\'"); } else if (min_max [1] != REG_INFINITY && min_max [0] > min_max [1]) { /* Disallow a backward range. */ sprintf (Error_Text, "{%lu,%lu} is an invalid range", min_max [0], min_max [1]); REG_FAIL (Error_Text); } } Reg_Parse++; /* Check for a minimal matching (non-greedy or "lazy") specification. */ if (*Reg_Parse == '?') { lazy = 1; Reg_Parse++; } /* Avoid overhead of counting if possible */ if (op_code == '{') { if (min_max [0] == REG_ZERO && min_max [1] == REG_INFINITY) { op_code = '*'; } else if (min_max [0] == REG_ONE && min_max [1] == REG_INFINITY) { op_code = '+'; } else if (min_max [0] == REG_ZERO && min_max [1] == REG_ONE) { op_code = '?'; } else if (min_max [0] == REG_ONE && min_max [1] == REG_ONE) { /* "x{1,1}" is the same as "x". No need to pollute the compiled regex with such nonsense. */ *flag_param = flags_local; *range_param = range_local; return (ret_val); } else if (Num_Braces > (int)UCHAR_MAX) { sprintf (Error_Text, "number of {m,n} constructs > %d", UCHAR_MAX); REG_FAIL (Error_Text); } } if (op_code == '+') min_max [0] = REG_ONE; if (op_code == '?') min_max [1] = REG_ONE; /* It is dangerous to apply certain quantifiers to a possibly zero width item. */ if (!(flags_local & HAS_WIDTH)) { if (brace_present) { sprintf (Error_Text, "{%lu,%lu} operand could be empty", min_max [0], min_max [1]); } else { sprintf (Error_Text, "%c operand could be empty", op_code); } REG_FAIL (Error_Text); } *flag_param = (min_max [0] > REG_ZERO) ? (WORST | HAS_WIDTH) : WORST; if (range_local.lower >= 0) { if (min_max[1] != REG_INFINITY) { range_param->lower = range_local.lower * min_max[0]; range_param->upper = range_local.upper * min_max[1]; } else { range_param->lower = -1; /* Not a fixed-size length */ range_param->upper = -1; } } else { range_param->lower = -1; /* Not a fixed-size length */ range_param->upper = -1; } /*---------------------------------------------------------------------* * Symbol Legend For Node Structure Diagrams *---------------------------------------------------------------------* * (...) = general grouped thing * B = (B)ranch, K = bac(K), N = (N)othing * I = (I)nitialize count, C = Increment (C)ount * T~m = (T)est against mini(m)um- go to NEXT pointer if >= operand * T~x = (T)est against ma(x)imum- go to NEXT pointer if >= operand * '~' = NEXT pointer, \___| = forward pointer, |___/ = Backward pointer *---------------------------------------------------------------------*/ if (op_code == '*' && (flags_local & SIMPLE)) { insert ((lazy ? LAZY_STAR : STAR), ret_val, 0UL, 0UL, 0); } else if (op_code == '+' && (flags_local & SIMPLE)) { insert (lazy ? LAZY_PLUS : PLUS, ret_val, 0UL, 0UL, 0); } else if (op_code == '?' && (flags_local & SIMPLE)) { insert (lazy ? LAZY_QUESTION : QUESTION, ret_val, 0UL, 0UL, 0); } else if (op_code == '{' && (flags_local & SIMPLE)) { insert (lazy ? LAZY_BRACE : BRACE, ret_val, min_max [0], min_max [1], 0); } else if ((op_code == '*' || op_code == '+') && lazy) { /* Node structure for (x)*? Node structure for (x)+? construct. * construct. (Same as (x)*? except for initial * forward jump into parenthesis.) * * ___6____ * _______5_______ /________|______ * | _4__ 1_\ /| ____ | _\ * |/ | / |\ / |/ | | / |\ * B~ N~ B~ (...)~ K~ N~ N~ B~ N~ B~ (...)~ K~ N~ * \ \___2_______| \ \___________| * \_____3_______| \_____________| * */ tail (ret_val, emit_node (BACK)); /* 1 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 2,4 */ (void) insert (NOTHING, ret_val, 0UL, 0UL, 0); /* 3 */ next = emit_node (NOTHING); /* 2,3 */ offset_tail (ret_val, NODE_SIZE, next); /* 2 */ tail (ret_val, next); /* 3 */ insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 4,5 */ tail (ret_val, ret_val + (2 * NODE_SIZE)); /* 4 */ offset_tail (ret_val, 3 * NODE_SIZE, ret_val); /* 5 */ if (op_code == '+') { insert (NOTHING, ret_val, 0UL, 0UL, 0); /* 6 */ tail (ret_val, ret_val + (4 * NODE_SIZE)); /* 6 */ } } else if (op_code == '*') { /* Node structure for (x)* construct. * ____1_____ * | \ * B~ (...)~ K~ B~ N~ * \ \_|2 |\_| * \__3_______| 4 */ insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 1,3 */ offset_tail (ret_val, NODE_SIZE, emit_node (BACK)); /* 2 */ offset_tail (ret_val, NODE_SIZE, ret_val); /* 1 */ tail (ret_val, emit_node (BRANCH)); /* 3 */ tail (ret_val, emit_node (NOTHING)); /* 4 */ } else if (op_code == '+') { /* Node structure for (x)+ construct. * * ____2_____ * | \ * (...)~ B~ K~ B~ N~ * \_|\____|\_| * 1 3 4 */ next = emit_node (BRANCH); /* 1 */ tail (ret_val, next); /* 1 */ tail (emit_node (BACK), ret_val); /* 2 */ tail (next, emit_node (BRANCH)); /* 3 */ tail (ret_val, emit_node (NOTHING)); /* 4 */ } else if (op_code == '?' && lazy) { /* Node structure for (x)?? construct. * _4__ 1_ * / | / | * B~ N~ B~ (...)~ N~ * \ \___2____| * \_____3____| */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 2,4 */ (void) insert (NOTHING, ret_val, 0UL, 0UL, 0); /* 3 */ next = emit_node (NOTHING); /* 1,2,3 */ offset_tail (ret_val, 2 * NODE_SIZE, next); /* 1 */ offset_tail (ret_val, NODE_SIZE, next); /* 2 */ tail (ret_val, next); /* 3 */ insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 4 */ tail (ret_val, (ret_val + (2 * NODE_SIZE))); /* 4 */ } else if (op_code == '?') { /* Node structure for (x)? construct. * ___1____ _2 * / |/ | * B~ (...)~ B~ N~ * \__3_| */ insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 1 */ tail (ret_val, emit_node (BRANCH)); /* 1 */ next = emit_node (NOTHING); /* 2,3 */ tail (ret_val, next); /* 2 */ offset_tail (ret_val, NODE_SIZE, next); /* 3 */ } else if (op_code == '{' && min_max [0] == min_max [1]) { /* Node structure for (x){m}, (x){m}?, (x){m,m}, or (x){m,m}? constructs. * Note that minimal and maximal matching mean the same thing when we * specify the minimum and maximum to be the same value. * _______3_____ * | 1_ _2 \ * | / |/ | \ * I~ (...)~ C~ T~m K~ N~ * \_| \_____| * 5 4 */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ tail (ret_val, emit_special (TEST_COUNT, min_max [0], Num_Braces));/* 2 */ tail (emit_node (BACK), ret_val); /* 3 */ tail (ret_val, emit_node (NOTHING)); /* 4 */ next = insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 5 */ tail (ret_val, next); /* 5 */ Num_Braces++; } else if (op_code == '{' && lazy) { if (min_max [0] == REG_ZERO && min_max [1] != REG_INFINITY) { /* Node structure for (x){0,n}? or {,n}? construct. * _________3____________ * 8_| _4__ 1_ _2 \ * / |/ | / |/ | \ * I~ B~ N~ B~ (...)~ C~ T~x K~ N~ * \ \ \__7__| * \ \_________6_______| * \______5____________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [0], Num_Braces); /* 2,7 */ tail (ret_val, next); /* 2 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, Num_Braces); /* 4,6 */ (void) insert (NOTHING, ret_val, 0UL, 0UL, Num_Braces); /* 5 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, Num_Braces); /* 3,4,8 */ tail (emit_node (BACK), ret_val); /* 3 */ tail (ret_val, ret_val + (2 * NODE_SIZE)); /* 4 */ next = emit_node (NOTHING); /* 5,6,7 */ offset_tail (ret_val, NODE_SIZE, next); /* 5 */ offset_tail (ret_val, 2 * NODE_SIZE, next); /* 6 */ offset_tail (ret_val, 3 * NODE_SIZE, next); /* 7 */ next = insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 8 */ tail (ret_val, next); /* 8 */ } else if (min_max [0] > REG_ZERO && min_max [1] == REG_INFINITY) { /* Node structure for (x){m,}? construct. * ______8_________________ * | _______3_____ \ * | _7__ | 1_ _2 \ \ * |/ | | / |/ | \ \ * I~ B~ N~ B~ (...)~ C~ T~m K~ K~ N~ * \_____\__\_| \_4___| | * 9 \ \_________5__________| * \_______6______________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [0], Num_Braces); /* 2,4 */ tail (ret_val, next); /* 2 */ tail (emit_node (BACK), ret_val); /* 3 */ tail (ret_val, emit_node (BACK)); /* 4 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 5,7 */ (void) insert (NOTHING, ret_val, 0UL, 0UL, 0); /* 6 */ next = emit_node (NOTHING); /* 5,6 */ offset_tail (ret_val, NODE_SIZE, next); /* 5 */ tail (ret_val, next); /* 6 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 7,8 */ tail (ret_val, ret_val + (2 * NODE_SIZE)); /* 7 */ offset_tail (ret_val, 3 * NODE_SIZE, ret_val); /* 8 */ (void) insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 9 */ tail (ret_val, ret_val + INDEX_SIZE + (4 * NODE_SIZE)); /* 9 */ } else { /* Node structure for (x){m,n}? construct. * ______9_____________________ * | _____________3___ \ * | __8_ | 1_ _2 \ \ * |/ | | / |/ | \ \ * I~ B~ N~ B~ (...)~ C~ T~x T~m K~ K~ N~ * \_____\__\_| \ \__4__| | * 10 \ \ \_7_________| * \ \_________6_____________| * \_______5_________________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [1], Num_Braces); /* 2,7 */ tail (ret_val, next); /* 2 */ next = emit_special (TEST_COUNT, min_max [0], Num_Braces); /* 4 */ tail (emit_node (BACK), ret_val); /* 3 */ tail (next, emit_node (BACK)); /* 4 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 6,8 */ (void) insert (NOTHING, ret_val, 0UL, 0UL, 0); /* 5 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 8,9 */ next = emit_node (NOTHING); /* 5,6,7 */ offset_tail (ret_val, NODE_SIZE, next); /* 5 */ offset_tail (ret_val, 2 * NODE_SIZE, next); /* 6 */ offset_tail (ret_val, 3 * NODE_SIZE, next); /* 7 */ tail (ret_val, ret_val + (2 * NODE_SIZE)); /* 8 */ offset_tail (next, -NODE_SIZE, ret_val); /* 9 */ insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 10 */ tail (ret_val, ret_val + INDEX_SIZE + (4 * NODE_SIZE)); /* 10 */ } Num_Braces++; } else if (op_code == '{') { if (min_max [0] == REG_ZERO && min_max [1] != REG_INFINITY) { /* Node structure for (x){0,n} or (x){,n} construct. * * ___3____________ * | 1_ _2 \ 5_ * | / |/ | \ / | * I~ B~ (...)~ C~ T~x K~ B~ N~ * \_|\ \_6___|__| * 7 \________4________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [1], Num_Braces); /* 2,6 */ tail (ret_val, next); /* 2 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 3,4,7 */ tail (emit_node (BACK), ret_val); /* 3 */ next = emit_node (BRANCH); /* 4,5 */ tail (ret_val, next); /* 4 */ tail (next, emit_node (NOTHING)); /* 5,6 */ offset_tail (ret_val, NODE_SIZE, next); /* 6 */ next = insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 7 */ tail (ret_val, next); /* 7 */ } else if (min_max [0] > REG_ZERO && min_max [1] == REG_INFINITY) { /* Node structure for (x){m,} construct. * __________4________ * | __3__________ \ * _|___| 1_ _2 \ \ _7 * / | 8 | / |/ | \ \ / | * I~ B~ (...)~ C~ T~m K~ K~ B~ N~ * \ \_5___| | * \__________6__________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [0], Num_Braces); /* 2 */ tail (ret_val, next); /* 2 */ tail (emit_node (BACK), ret_val); /* 3 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 4,6 */ next = emit_node (BACK); /* 4 */ tail (next, ret_val); /* 4 */ offset_tail (ret_val, NODE_SIZE, next); /* 5 */ tail (ret_val, emit_node (BRANCH)); /* 6 */ tail (ret_val, emit_node (NOTHING)); /* 7 */ insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 8 */ tail (ret_val, ret_val + INDEX_SIZE + (2 * NODE_SIZE)); /* 8 */ } else { /* Node structure for (x){m,n} construct. * _____6________________ * | _____________3___ \ * 9_|__| 1_ _2 \ \ _8 * / | | / |/ | \ \ / | * I~ B~ (...)~ C~ T~x T~m K~ K~ B~ N~ * \ \ \__4__| | | * \ \_7_________|__| * \_________5_____________| */ tail (ret_val, emit_special (INC_COUNT, 0UL, Num_Braces)); /* 1 */ next = emit_special (TEST_COUNT, min_max [1], Num_Braces); /* 2,4 */ tail (ret_val, next); /* 2 */ next = emit_special (TEST_COUNT, min_max [0], Num_Braces); /* 4 */ tail (emit_node (BACK), ret_val); /* 3 */ tail (next, emit_node (BACK)); /* 4 */ (void) insert (BRANCH, ret_val, 0UL, 0UL, 0); /* 5,6 */ next = emit_node (BRANCH); /* 5,8 */ tail (ret_val, next); /* 5 */ offset_tail (next, -NODE_SIZE, ret_val); /* 6 */ next = emit_node (NOTHING); /* 7,8 */ offset_tail (ret_val, NODE_SIZE, next); /* 7 */ offset_tail (next, -NODE_SIZE, next); /* 8 */ (void) insert (INIT_COUNT, ret_val, 0UL, 0UL, Num_Braces); /* 9 */ tail (ret_val, ret_val + INDEX_SIZE + (2 * NODE_SIZE)); /* 9 */ } Num_Braces++; } else { /* We get here if the IS_QUANTIFIER macro is not coordinated properly with this function. */ REG_FAIL ("internal error #2, `piece\'"); } if (IS_QUANTIFIER (*Reg_Parse)) { if (op_code == '{') { sprintf (Error_Text, "nested quantifiers, {m,n}%c", *Reg_Parse); } else { sprintf (Error_Text, "nested quantifiers, %c%c", op_code, *Reg_Parse); } REG_FAIL (Error_Text); } return (ret_val); } /*----------------------------------------------------------------------* * atom * * Process one regex item at the lowest level * * OPTIMIZATION: Lumps a continuous sequence of ordinary characters * together so that it can turn them into a single EXACTLY node, which * is smaller to store and faster to run. *----------------------------------------------------------------------*/ static unsigned char * atom (int *flag_param, len_range *range_param) { register unsigned char *ret_val; unsigned char test; int flags_local; len_range range_local; *flag_param = WORST; /* Tentatively. */ range_param->lower = 0; /* Idem */ range_param->upper = 0; /* Process any regex comments, e.g. `(?# match next token->)'. The terminating right parenthesis can not be escaped. The comment stops at the first right parenthesis encountered (or the end of the regex string)... period. Handles multiple sequential comments, e.g. `(?# one)(?# two)...' */ while (*Reg_Parse == '(' && *(Reg_Parse + 1) == '?' && *(Reg_Parse + 2) == '#') { Reg_Parse += 3; while (*Reg_Parse != ')' && *Reg_Parse != '\0') { Reg_Parse++; } if (*Reg_Parse == ')') { Reg_Parse++; } if (*Reg_Parse == ')' || *Reg_Parse == '|' || *Reg_Parse == '\0') { /* Hit end of regex string or end of parenthesized regex; have to return "something" (i.e. a NOTHING node) to avoid generating an error. */ ret_val = emit_node (NOTHING); return (ret_val); } } switch (*Reg_Parse++) { case '^': ret_val = emit_node (BOL); break; case '$': ret_val = emit_node (EOL); break; case '<': ret_val = emit_node (BOWORD); break; case '>': ret_val = emit_node (EOWORD); break; case '.': if (Match_Newline) { ret_val = emit_node (EVERY); } else { ret_val = emit_node (ANY); } *flag_param |= (HAS_WIDTH | SIMPLE); range_param->lower = 1; range_param->upper = 1; break; case '(': if (*Reg_Parse == '?') { /* Special parenthetical expression */ Reg_Parse++; range_local.lower = 0; /* Make sure it is always used */ range_local.upper = 0; if (*Reg_Parse == ':') { Reg_Parse++; ret_val = chunk (NO_CAPTURE, &flags_local, &range_local); } else if (*Reg_Parse == '=') { Reg_Parse++; ret_val = chunk (POS_AHEAD_OPEN, &flags_local, &range_local); } else if (*Reg_Parse == '!') { Reg_Parse++; ret_val = chunk (NEG_AHEAD_OPEN, &flags_local, &range_local); } else if (*Reg_Parse == 'i') { Reg_Parse++; ret_val = chunk (INSENSITIVE, &flags_local, &range_local); } else if (*Reg_Parse == 'I') { Reg_Parse++; ret_val = chunk (SENSITIVE, &flags_local, &range_local); } else if (*Reg_Parse == 'n') { Reg_Parse++; ret_val = chunk (NEWLINE, &flags_local, &range_local); } else if (*Reg_Parse == 'N') { Reg_Parse++; ret_val = chunk (NO_NEWLINE, &flags_local, &range_local); } else if (*Reg_Parse == '<') { Reg_Parse++; if (*Reg_Parse == '=') { Reg_Parse++; ret_val = chunk (POS_BEHIND_OPEN, &flags_local, &range_local); } else if (*Reg_Parse == '!') { Reg_Parse++; ret_val = chunk (NEG_BEHIND_OPEN, &flags_local, &range_local); } else { sprintf (Error_Text, "invalid look-behind syntax, \"(?<%c...)\"", *Reg_Parse); REG_FAIL (Error_Text); } } else { sprintf (Error_Text, "invalid grouping syntax, \"(?%c...)\"", *Reg_Parse); REG_FAIL (Error_Text); } } else { /* Normal capturing parentheses */ ret_val = chunk (PAREN, &flags_local, &range_local); } if (ret_val == NULL) return (NULL); /* Something went wrong. */ /* Add HAS_WIDTH flag if it was set by call to chunk. */ *flag_param |= flags_local & HAS_WIDTH; *range_param = range_local; break; case '\0': case '|': case ')': REG_FAIL ("internal error #3, `atom\'"); /* Supposed to be */ /* caught earlier. */ case '?': case '+': case '*': sprintf (Error_Text, "%c follows nothing", *(Reg_Parse - 1)); REG_FAIL (Error_Text); case '{': if (Enable_Counting_Quantifier) { REG_FAIL ("{m,n} follows nothing"); } else { ret_val = emit_node (EXACTLY); /* Treat braces as literals. */ emit_byte ('{'); emit_byte ('\0'); range_param->lower = 1; range_param->upper = 1; } break; case '[': { register unsigned int second_value; register unsigned int last_value; unsigned char last_emit = 0; /* Handle characters that can only occur at the start of a class. */ if (*Reg_Parse == '^') { /* Complement of range. */ ret_val = emit_node (ANY_BUT); Reg_Parse++; /* All negated classes include newline unless escaped with a "(?n)" switch. */ if (!Match_Newline) emit_byte ('\n'); } else { ret_val = emit_node (ANY_OF); } if (*Reg_Parse == ']' || *Reg_Parse == '-') { /* If '-' or ']' is the first character in a class, it is a literal character in the class. */ last_emit = *Reg_Parse; emit_byte (*Reg_Parse); Reg_Parse++; } /* Handle the rest of the class characters. */ while (*Reg_Parse != '\0' && *Reg_Parse != ']') { if (*Reg_Parse == '-') { /* Process a range, e.g [a-z]. */ Reg_Parse++; if (*Reg_Parse == ']' || *Reg_Parse == '\0') { /* If '-' is the last character in a class it is a literal character. If `Reg_Parse' points to the end of the regex string, an error will be generated later. */ emit_byte ('-'); last_emit = '-'; } else { /* We must get the range starting character value from the emitted code since it may have been an escaped character. `second_value' is set one larger than the just emitted character value. This is done since `second_value' is used as the start value for the loop that emits the values in the range. Since we have already emitted the first character of the class, we do not want to emit it again. */ second_value = ((unsigned int) last_emit) + 1; if (*Reg_Parse == '\\') { /* Handle escaped characters within a class range. Specifically disallow shortcut escapes as the end of a class range. To allow this would be ambiguous since shortcut escapes represent a set of characters, and it would not be clear which character of the class should be treated as the "last" character. */ Reg_Parse++; if ((test = numeric_escape (*Reg_Parse, &Reg_Parse))) { last_value = (unsigned int) test; } else if ((test = literal_escape (*Reg_Parse))) { last_value = (unsigned int) test; } else if (shortcut_escape (*Reg_Parse, NULL, CHECK_CLASS_ESCAPE)) { sprintf (Error_Text, "\\%c is not allowed as range operand", *Reg_Parse); REG_FAIL (Error_Text); } else { sprintf ( Error_Text, "\\%c is an invalid char class escape sequence", *Reg_Parse); REG_FAIL (Error_Text); } } else { last_value = U_CHAR_AT (Reg_Parse); } if (Is_Case_Insensitive) { second_value = (unsigned int) tolower ((int) second_value); last_value = (unsigned int) tolower ((int) last_value); } /* For case insensitive, something like [A-_] will generate an error here since ranges are converted to lower case. */ if (second_value - 1 > last_value) { REG_FAIL ("invalid [] range"); } /* If only one character in range (e.g [a-a]) then this loop is not run since the first character of any range was emitted by the previous iteration of while loop. */ for (; second_value <= last_value; second_value++) { emit_class_byte (second_value); } last_emit = (unsigned char) last_value; Reg_Parse++; } /* End class character range code. */ } else if (*Reg_Parse == '\\') { Reg_Parse++; if ((test = numeric_escape (*Reg_Parse, &Reg_Parse)) != '\0') { emit_class_byte (test); last_emit = test; } else if ((test = literal_escape (*Reg_Parse)) != '\0') { emit_byte (test); last_emit = test; } else if (shortcut_escape (*Reg_Parse, NULL, CHECK_CLASS_ESCAPE)) { if (*(Reg_Parse + 1) == '-') { /* Specifically disallow shortcut escapes as the start of a character class range (see comment above.) */ sprintf (Error_Text, "\\%c not allowed as range operand", *Reg_Parse); REG_FAIL (Error_Text); } else { /* Emit the bytes that are part of the shortcut escape sequence's range (e.g. \d = 0123456789) */ shortcut_escape (*Reg_Parse, NULL, EMIT_CLASS_BYTES); } } else { sprintf (Error_Text, "\\%c is an invalid char class escape sequence", *Reg_Parse); REG_FAIL (Error_Text); } Reg_Parse++; /* End of class escaped sequence code */ } else { emit_class_byte (*Reg_Parse); /* Ordinary class character. */ last_emit = *Reg_Parse; Reg_Parse++; } } /* End of while (*Reg_Parse != '\0' && *Reg_Parse != ']') */ if (*Reg_Parse != ']') REG_FAIL ("missing right \']\'"); emit_byte('\0'); /* NOTE: it is impossible to specify an empty class. This is because [] would be interpreted as "begin character class" followed by a literal ']' character and no "end character class" delimiter (']'). Because of this, it is always safe to assume that a class HAS_WIDTH. */ Reg_Parse++; *flag_param |= HAS_WIDTH | SIMPLE; range_param->lower = 1; range_param->upper = 1; } break; /* End of character class code. */ case '\\': /* Force Error_Text to have a length of zero. This way we can tell if either of the calls to shortcut_escape() or back_ref() fill Error_Text with an error message. */ Error_Text [0] = '\0'; if ((ret_val = shortcut_escape (*Reg_Parse, flag_param, EMIT_NODE))) { Reg_Parse++; range_param->lower = 1; range_param->upper = 1; break; } else if ((ret_val = back_ref (Reg_Parse, flag_param, EMIT_NODE))) { /* Can't make any assumptions about a back-reference as to SIMPLE or HAS_WIDTH. For example (^|<) is neither simple nor has width. So we don't flip bits in flag_param here. */ Reg_Parse++; /* Back-references always have an unknown length */ range_param->lower = -1; range_param->upper = -1; break; } if (strlen (Error_Text) > 0) REG_FAIL (Error_Text); /* At this point it is apparent that the escaped character is not a shortcut escape or back-reference. Back up one character to allow the default code to include it as an ordinary character. */ /* Fall through to Default case to handle literal escapes and numeric escapes. */ default: Reg_Parse--; /* If we fell through from the above code, we are now pointing at the back slash (\) character. */ { unsigned char *parse_save; int len = 0; if (Is_Case_Insensitive) { ret_val = emit_node (SIMILAR); } else { ret_val = emit_node (EXACTLY); } /* Loop until we find a meta character, shortcut escape, back reference, or end of regex string. */ for (; *Reg_Parse != '\0' && !strchr ((char *) Meta_Char, (int) *Reg_Parse); len++) { /* Save where we are in case we have to back this character out. */ parse_save = Reg_Parse; if (*Reg_Parse == '\\') { Reg_Parse++; /* Point to escaped character */ Error_Text [0] = '\0'; /* See comment above. */ if ((test = numeric_escape (*Reg_Parse, &Reg_Parse))) { if (Is_Case_Insensitive) { emit_byte (tolower (test)); } else { emit_byte (test); } } else if ((test = literal_escape (*Reg_Parse))) { emit_byte (test); } else if (back_ref (Reg_Parse, NULL, CHECK_ESCAPE)) { /* Leave back reference for next `atom' call */ Reg_Parse--; break; } else if (shortcut_escape (*Reg_Parse, NULL, CHECK_ESCAPE)) { /* Leave shortcut escape for next `atom' call */ Reg_Parse--; break; } else { if (strlen (Error_Text) == 0) { /* None of the above calls generated an error message so generate our own here. */ sprintf (Error_Text, "\\%c is an invalid escape sequence", *Reg_Parse); } REG_FAIL (Error_Text); } Reg_Parse++; } else { /* Ordinary character */ if (Is_Case_Insensitive) { emit_byte (tolower (*Reg_Parse)); } else { emit_byte (*Reg_Parse); } Reg_Parse++; } /* If next regex token is a quantifier (?, +. *, or {m,n}) and our EXACTLY node so far is more than one character, leave the last character to be made into an EXACTLY node one character wide for the multiplier to act on. For example 'abcd* would have an EXACTLY node with an 'abc' operand followed by a STAR node followed by another EXACTLY node with a 'd' operand. */ if (IS_QUANTIFIER (*Reg_Parse) && len > 0) { Reg_Parse = parse_save; /* Point to previous regex token. */ if (Code_Emit_Ptr == &Compute_Size) { Reg_Size--; } else { Code_Emit_Ptr--; /* Write over previously emitted byte. */ } break; } } if (len <= 0) REG_FAIL ("internal error #4, `atom\'"); *flag_param |= HAS_WIDTH; if (len == 1) *flag_param |= SIMPLE; range_param->lower = len; range_param->upper = len; emit_byte ('\0'); } } /* END switch (*Reg_Parse++) */ return (ret_val); } /*----------------------------------------------------------------------* * emit_node * * Emit (if appropriate) the op code for a regex node atom. * * The NEXT pointer is initialized to NULL. * * Returns a pointer to the START of the emitted node. *----------------------------------------------------------------------*/ static unsigned char * emit_node (int op_code) { register unsigned char *ret_val; register unsigned char *ptr; ret_val = Code_Emit_Ptr; /* Return address of start of node */ if (ret_val == &Compute_Size) { Reg_Size += NODE_SIZE; } else { ptr = ret_val; *ptr++ = (unsigned char) op_code; *ptr++ = '\0'; /* Null "NEXT" pointer. */ *ptr++ = '\0'; Code_Emit_Ptr = ptr; } return (ret_val); } /*----------------------------------------------------------------------* * emit_byte * * Emit (if appropriate) a byte of code (usually part of an operand.) *----------------------------------------------------------------------*/ static void emit_byte (unsigned char c) { if (Code_Emit_Ptr == &Compute_Size) { Reg_Size++; } else { *Code_Emit_Ptr++ = c; } } /*----------------------------------------------------------------------* * emit_class_byte * * Emit (if appropriate) a byte of code (usually part of a character * class operand.) *----------------------------------------------------------------------*/ static void emit_class_byte (unsigned char c) { if (Code_Emit_Ptr == &Compute_Size) { Reg_Size++; if (Is_Case_Insensitive && isalpha (c)) Reg_Size++; } else if (Is_Case_Insensitive && isalpha (c)) { /* For case insensitive character classes, emit both upper and lower case versions of alphabetical characters. */ *Code_Emit_Ptr++ = tolower (c); *Code_Emit_Ptr++ = toupper (c); } else { *Code_Emit_Ptr++ = c; } } /*----------------------------------------------------------------------* * emit_special * * Emit nodes that need special processing. *----------------------------------------------------------------------*/ static unsigned char * emit_special ( unsigned char op_code, unsigned long test_val, int index) { register unsigned char *ret_val = &Compute_Size; register unsigned char *ptr; if (Code_Emit_Ptr == &Compute_Size) { switch (op_code) { case POS_BEHIND_OPEN: case NEG_BEHIND_OPEN: Reg_Size += LENGTH_SIZE; /* Length of the look-behind match */ Reg_Size += NODE_SIZE; /* Make room for the node */ break; case TEST_COUNT: Reg_Size += NEXT_PTR_SIZE; /* Make room for a test value. */ case INC_COUNT: Reg_Size += INDEX_SIZE; /* Make room for an index value. */ default: Reg_Size += NODE_SIZE; /* Make room for the node. */ } } else { ret_val = emit_node (op_code); /* Return the address for start of node. */ ptr = Code_Emit_Ptr; if (op_code == INC_COUNT || op_code == TEST_COUNT) { *ptr++ = (unsigned char) index; if (op_code == TEST_COUNT) { *ptr++ = PUT_OFFSET_L (test_val); *ptr++ = PUT_OFFSET_R (test_val); } } else if (op_code == POS_BEHIND_OPEN || op_code == NEG_BEHIND_OPEN) { *ptr++ = PUT_OFFSET_L (test_val); *ptr++ = PUT_OFFSET_R (test_val); *ptr++ = PUT_OFFSET_L (test_val); *ptr++ = PUT_OFFSET_R (test_val); } Code_Emit_Ptr = ptr; } return (ret_val); } /*----------------------------------------------------------------------* * insert * * Insert a node in front of already emitted node(s). Means relocating * the operand. Code_Emit_Ptr points one byte past the just emitted * node and operand. The parameter `insert_pos' points to the location * where the new node is to be inserted. *----------------------------------------------------------------------*/ static unsigned char * insert ( unsigned char op, unsigned char *insert_pos, long min, long max, int index) { register unsigned char *src; register unsigned char *dst; unsigned char *place; int insert_size = NODE_SIZE; if (op == BRACE || op == LAZY_BRACE) { /* Make room for the min and max values. */ insert_size += (2 * NEXT_PTR_SIZE); } else if (op == INIT_COUNT) { /* Make room for an index value . */ insert_size += INDEX_SIZE; } if (Code_Emit_Ptr == &Compute_Size) { Reg_Size += insert_size; return &Compute_Size; } src = Code_Emit_Ptr; Code_Emit_Ptr += insert_size; dst = Code_Emit_Ptr; /* Relocate the existing emitted code to make room for the new node. */ while (src > insert_pos) *--dst = *--src; place = insert_pos; /* Where operand used to be. */ *place++ = op; /* Inserted operand. */ *place++ = '\0'; /* NEXT pointer for inserted operand. */ *place++ = '\0'; if (op == BRACE || op == LAZY_BRACE) { *place++ = PUT_OFFSET_L (min); *place++ = PUT_OFFSET_R (min); *place++ = PUT_OFFSET_L (max); *place++ = PUT_OFFSET_R (max); } else if (op == INIT_COUNT) { *place++ = (unsigned char) index; } return place; /* Return a pointer to the start of the code moved. */ } /*----------------------------------------------------------------------* * tail - Set the next-pointer at the end of a node chain. *----------------------------------------------------------------------*/ static void tail (unsigned char *search_from, unsigned char *point_to) { register unsigned char *scan; register unsigned char *next; register int offset; if (search_from == &Compute_Size) return; /* Find the last node in the chain (node with a null NEXT pointer) */ scan = search_from; for (;;) { next = next_ptr (scan); if (!next) break; scan = next; } if (GET_OP_CODE (scan) == BACK) { offset = scan - point_to; } else { offset = point_to - scan; } /* Set NEXT pointer */ *(scan + 1) = PUT_OFFSET_L (offset); *(scan + 2) = PUT_OFFSET_R (offset); } /*--------------------------------------------------------------------* * offset_tail * * Perform a tail operation on (ptr + offset). *--------------------------------------------------------------------*/ static void offset_tail (unsigned char *ptr, int offset, unsigned char *val) { if (ptr == &Compute_Size || ptr == NULL) return; tail (ptr + offset, val); } /*--------------------------------------------------------------------* * branch_tail * * Perform a tail operation on (ptr + offset) but only if `ptr' is a * BRANCH node. *--------------------------------------------------------------------*/ static void branch_tail (unsigned char *ptr, int offset, unsigned char *val) { if (ptr == &Compute_Size || ptr == NULL ||GET_OP_CODE (ptr) != BRANCH) { return; } tail (ptr + offset, val); } /*--------------------------------------------------------------------* * shortcut_escape * * Implements convenient escape sequences that represent entire * character classes or special location assertions (similar to escapes * supported by Perl) * _ * \d Digits [0-9] | * \D NOT a digit [^0-9] | (Examples * \l Letters [a-zA-Z] | at left * \L NOT a Letter [^a-zA-Z] | are * \s Whitespace [ \t\n\r\f\v] | for * \S NOT Whitespace [^ \t\n\r\f\v] | C * \w "Word" character [a-zA-Z0-9_] | Locale) * \W NOT a "Word" character [^a-zA-Z0-9_] _| * * \B Matches any character that is NOT a word-delimiter * * Codes for the "emit" parameter: * * EMIT_NODE * Emit a shortcut node. Shortcut nodes have an implied set of * class characters. This helps keep the compiled regex string * small. * * EMIT_CLASS_BYTES * Emit just the equivalent characters of the class. This makes * the escape usable from within a class, e.g. [a-fA-F\d]. Only * \d, \D, \s, \S, \w, and \W can be used within a class. * * CHECK_ESCAPE * Only verify that this is a valid shortcut escape. * * CHECK_CLASS_ESCAPE * Same as CHECK_ESCAPE but only allows characters valid within * a class. * *--------------------------------------------------------------------*/ static unsigned char * shortcut_escape ( unsigned char c, int *flag_param, int emit) { register unsigned char *class = NULL; static unsigned char *codes = (unsigned char *) "ByYdDlLsSwW"; unsigned char *ret_val = (unsigned char *) 1; /* Assume success. */ unsigned char *valid_codes; if (emit == EMIT_CLASS_BYTES || emit == CHECK_CLASS_ESCAPE) { valid_codes = codes + 3; /* \B, \y and \Y are not allowed in classes */ } else { valid_codes = codes; } if (!strchr ((char *) valid_codes, (int) c)) { return NULL; /* Not a valid shortcut escape sequence */ } else if (emit == CHECK_ESCAPE || emit == CHECK_CLASS_ESCAPE) { return ret_val; /* Just checking if this is a valid shortcut escape. */ } switch (c) { case 'd': case 'D': if (emit == EMIT_CLASS_BYTES) { class = ASCII_Digits; } else if (emit == EMIT_NODE) { ret_val = (islower (c) ? emit_node (DIGIT) : emit_node (NOT_DIGIT)); } break; case 'l': case 'L': if (emit == EMIT_CLASS_BYTES) { class = Letter_Char; } else if (emit == EMIT_NODE) { ret_val = (islower (c) ? emit_node (LETTER) : emit_node (NOT_LETTER)); } break; case 's': case 'S': if (emit == EMIT_CLASS_BYTES) { if (Match_Newline) emit_byte ('\n'); class = White_Space; } else if (emit == EMIT_NODE) { if (Match_Newline) { ret_val = (islower (c) ? emit_node (SPACE_NL) : emit_node (NOT_SPACE_NL)); } else { ret_val = (islower (c) ? emit_node (SPACE) : emit_node (NOT_SPACE)); } } break; case 'w': case 'W': if (emit == EMIT_CLASS_BYTES) { class = Word_Char; } else if (emit == EMIT_NODE) { ret_val = (islower (c) ? emit_node (WORD_CHAR) : emit_node (NOT_WORD_CHAR)); } break; /* Since the delimiter table is not available at regex compile time \B, \Y and \Y can only generate a node. At run time, the delimiter table will be available for these nodes to use. */ case 'y': if (emit == EMIT_NODE) { ret_val = emit_node (IS_DELIM); } else { REG_FAIL ("internal error #5 `shortcut_escape\'"); } break; case 'Y': if (emit == EMIT_NODE) { ret_val = emit_node (NOT_DELIM); } else { REG_FAIL ("internal error #6 `shortcut_escape\'"); } break; case 'B': if (emit == EMIT_NODE) { ret_val = emit_node (NOT_BOUNDARY); } else { REG_FAIL ("internal error #7 `shortcut_escape\'"); } break; default: /* We get here if there isn't a case for every character in the string "codes" */ REG_FAIL ("internal error #8 `shortcut_escape\'"); } if (emit == EMIT_NODE && c != 'B') { *flag_param |= (HAS_WIDTH | SIMPLE); } if (class) { /* Emit bytes within a character class operand. */ while (*class != '\0') { emit_byte (*class++); } } return ret_val; } /*--------------------------------------------------------------------* * numeric_escape * * Implements hex and octal numeric escape sequence syntax. * * Hexadecimal Escape: \x## Max of two digits Must have leading 'x'. * Octal Escape: \0### Max of three digits and not greater * than 377 octal. Must have leading zero. * * Returns the actual character value or NULL if not a valid hex or * octal escape. REG_FAIL is called if \x0, \x00, \0, \00, \000, or * \0000 is specified. *--------------------------------------------------------------------*/ static unsigned char numeric_escape ( unsigned char c, unsigned char **parse) { static unsigned char digits [] = "fedcbaFEDCBA9876543210"; static unsigned int digit_val [] = { 15, 14, 13, 12, 11, 10, /* Lower case Hex digits */ 15, 14, 13, 12, 11, 10, /* Upper case Hex digits */ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; /* Decimal Digits */ register unsigned char *scan; register unsigned char *pos_ptr; register unsigned char *digit_str; unsigned int value = 0; unsigned int radix = 8; int width = 3; /* Can not be bigger than \0377 */ int pos_delta = 14; int i, pos; switch (c) { case '0': digit_str = digits + pos_delta; /* Only use Octal digits, i.e. 0-7. */ break; case 'x': case 'X': width = 2; /* Can not be bigger than \0377 */ radix = 16; pos_delta = 0; digit_str = digits; /* Use all of the digit characters. */ break; default: return ('\0'); /* Not a numeric escape */ } scan = *parse; scan++; /* Only change *parse on success. */ pos_ptr = (unsigned char *) strchr ((char *) digit_str, (int) *scan); for (i = 0; pos_ptr != NULL && (i < width); i++) { pos = (pos_ptr - digit_str) + pos_delta; value = (value * radix) + digit_val [pos]; /* If this digit makes the value over 255, treat this digit as a literal character instead of part of the numeric escape. For example, \0777 will be processed as \077 (an 'M') and a literal '7' character, NOT 511 decimal which is > 255. */ if (value > 255) { /* Back out calculations for last digit processed. */ value -= digit_val [pos]; value /= radix; break; /* Note that scan will not be incremented and still points to the digit that caused overflow. It will be decremented by the "else" below to point to the last character that is considered to be part of the octal escape. */ } scan++; pos_ptr = (unsigned char *) strchr ((char *) digit_str, (int) *scan); } /* Handle the case of "\0" i.e. trying to specify a NULL character. */ if (value == 0) { if (c == '0') { sprintf (Error_Text, "\\00 is an invalid octal escape"); } else { sprintf (Error_Text, "\\%c0 is an invalid hexadecimal escape", c); } } else { /* Point to the last character of the number on success. */ scan--; *parse = scan; } return (unsigned char) value; } /*--------------------------------------------------------------------* * literal_escape * * Recognize escaped literal characters (prefixed with backslash), * and translate them into the corresponding character. * * Returns the proper character value or NULL if not a valid literal * escape. *--------------------------------------------------------------------*/ static unsigned char literal_escape (unsigned char c) { static unsigned char valid_escape [] = { 'a', 'b', 'e', 'f', 'n', 'r', 't', 'v', '(', ')', '-', '[', ']', '<', '>', '{', '}', '.', '\\', '|', '^', '$', '*', '+', '?', '&', '\0' }; static unsigned char value [] = { '\a', '\b', #ifdef EBCDIC_CHARSET 0x27, /* Escape character in IBM's EBCDIC character set. */ #else 0x1B, /* Escape character in ASCII character set. */ #endif '\f', '\n', '\r', '\t', '\v', '(', ')', '-', '[', ']', '<', '>', '{', '}', '.', '\\', '|', '^', '$', '*', '+', '?', '&', '\0' }; int i; for (i = 0; valid_escape [i] != '\0'; i++) { if (c == valid_escape [i]) return value [i]; } return '\0'; } /*--------------------------------------------------------------------* * back_ref * * Process a request to match a previous parenthesized thing. * Parenthetical entities are numbered beginning at 1 by counting * opening parentheses from left to to right. \0 would represent * whole match, but would confuse numeric_escape as an octal escape, * so it is forbidden. * * Constructs of the form \~1, \~2, etc. are cross-regex back * references and are used in syntax highlighting patterns to match * text previously matched by another regex. *** IMPLEMENT LATER *** *--------------------------------------------------------------------*/ static unsigned char * back_ref ( unsigned char *c, int *flag_param, int emit) { int paren_no, c_offset = 0, is_cross_regex = 0; unsigned char *ret_val; /* Implement cross regex backreferences later. */ /* if (*c == (unsigned char) ('~')) { c_offset++; is_cross_regex++; } */ paren_no = (int) (*(c + c_offset) - (unsigned char) ('0')); if (!isdigit (*(c + c_offset)) || /* Only \1, \2, ... \9 are supported. */ paren_no == 0) { /* Should be caught by numeric_escape. */ return NULL; } /* Make sure parentheses for requested back-reference are complete. */ if (!is_cross_regex && !TEST_BIT (Closed_Parens, paren_no)) { sprintf (Error_Text, "\\%d is an illegal back reference", paren_no); return NULL; } if (emit == EMIT_NODE) { if (is_cross_regex) { Reg_Parse++; /* Skip past the '~' in a cross regex back reference. We only do this if we are emitting code. */ if (Is_Case_Insensitive) { ret_val = emit_node (X_REGEX_BR_CI); } else { ret_val = emit_node (X_REGEX_BR); } } else { if (Is_Case_Insensitive) { ret_val = emit_node (BACK_REF_CI); } else { ret_val = emit_node (BACK_REF); } } emit_byte ((unsigned char) paren_no); if (is_cross_regex || TEST_BIT (Paren_Has_Width, paren_no)) { *flag_param |= HAS_WIDTH; } } else if (emit == CHECK_ESCAPE) { ret_val = (unsigned char *) 1; } else { ret_val = NULL; } return ret_val; } /*======================================================================* * Regex execution related code *======================================================================*/ /* Global work variables for `ExecRE'. */ static unsigned char *Reg_Input; /* String-input pointer. */ static unsigned char *Start_Of_String; /* Beginning of input, for ^ */ /* and < checks. */ static unsigned char *Look_Behind_To; /* Position till were look behind can safely check back */ static unsigned char **Start_Ptr_Ptr; /* Pointer to `startp' array. */ static unsigned char **End_Ptr_Ptr; /* Ditto for `endp'. */ static unsigned char *Extent_Ptr_FW; /* Forward extent pointer */ static unsigned char *Extent_Ptr_BW; /* Backward extent pointer */ static unsigned char *Back_Ref_Start [10]; /* Back_Ref_Start [0] and */ static unsigned char *Back_Ref_End [10]; /* Back_Ref_End [0] are not */ /* used. This simplifies */ /* indexing. */ /* * Measured recursion limits: * Linux: +/- 40 000 (up to 110 000) * Solaris: +/- 85 000 * HP-UX 11: +/- 325 000 * * So 10 000 ought to be safe. */ #define REGEX_RECURSION_LIMIT 10000 static int Recursion_Count; /* Recursion counter */ static int Recursion_Limit_Exceeded; /* Recursion limit exceeded flag */ /* static regexp *Cross_Regex_Backref; */ static int Prev_Is_BOL; static int Succ_Is_EOL; static int Prev_Is_Delim; static int Succ_Is_Delim; /* Define a pointer to an array to hold general (...){m,n} counts. */ typedef struct brace_counts { unsigned long count [1]; /* More unwarranted chumminess with compiler. */ } brace_counts; static struct brace_counts *Brace; /* Default table for determining whether a character is a word delimiter. */ static unsigned char Default_Delimiters [UCHAR_MAX] = {0}; static unsigned char *Current_Delimiters; /* Current delimiter table */ /* Forward declarations of functions used by `ExecRE' */ static int attempt (regexp *, unsigned char *); static int match (unsigned char *, int *); static unsigned long greedy (unsigned char *, long); static void adjustcase (unsigned char *, int, unsigned char); static unsigned char * makeDelimiterTable (unsigned char *, unsigned char *); /* * ExecRE - match a `regexp' structure against a string * * If `end' is non-NULL, matches may not BEGIN past end, but may extend past * it. If reverse is true, `end' must be specified, and searching begins at * `end'. "isbol" should be set to true if the beginning of the string is the * actual beginning of a line (since `ExecRE' can't look backwards from the * beginning to find whether there was a newline before). Likewise, "isbow" * asks whether the string is preceded by a word delimiter. End of string is * always treated as a word and line boundary (there may be cases where it * shouldn't be, in which case, this should be changed). "delimit" (if * non-null) specifies a null-terminated string of characters to be considered * word delimiters matching "<" and ">". if "delimit" is NULL, the default * delimiters (as set in SetREDefaultWordDelimiters) are used. * Finally, look_behind_to indicates the position till where it is safe to * perform look-behind matches. If set, it should be smaller than or equal * to the start position of the search (pointed at by string). If it is NULL, * it defaults to the start position. */ int ExecRE ( regexp *prog, regexp *cross_regex_backref, const char *string, const char *end, int reverse, char prev_char, char succ_char, const char *delimiters, const char *look_behind_to) { register unsigned char *str; unsigned char **s_ptr; unsigned char **e_ptr; int ret_val = 0; unsigned char tempDelimitTable [256]; int i; s_ptr = (unsigned char **) prog->startp; e_ptr = (unsigned char **) prog->endp; /* Check for valid parameters. */ if (prog == NULL || string == NULL) { reg_error ("NULL parameter to `ExecRE\'"); goto SINGLE_RETURN; } /* Check validity of program. */ if (U_CHAR_AT (prog->program) != MAGIC) { reg_error ("corrupted program"); goto SINGLE_RETURN; } /* If caller has supplied delimiters, make a delimiter table */ if (delimiters == NULL) { Current_Delimiters = Default_Delimiters; } else { Current_Delimiters = makeDelimiterTable ( (unsigned char *) delimiters, (unsigned char *) tempDelimitTable); } if (end == NULL && reverse) { for (end = string; *end != '\0'; end++) ; succ_char = '\n'; } else if (end == NULL) { succ_char = '\n'; } /* Initialize arrays used by shortcut_escape. */ if (!init_ansi_classes ()) goto SINGLE_RETURN; /* Remember the beginning of the string for matching BOL */ Start_Of_String = (unsigned char *) string; Look_Behind_To = (unsigned char *) (look_behind_to?look_behind_to:string); Prev_Is_BOL = ((prev_char == '\n') || (prev_char == '\0') ? 1 : 0); Succ_Is_EOL = ((succ_char == '\n') || (succ_char == '\0') ? 1 : 0); Prev_Is_Delim = (Current_Delimiters [(unsigned char)prev_char] ? 1 : 0); Succ_Is_Delim = (Current_Delimiters [(unsigned char)succ_char] ? 1 : 0); Total_Paren = (int) (prog->program [1]); Num_Braces = (int) (prog->program [2]); /* Reset the recursion detection flag */ Recursion_Limit_Exceeded = 0; /* Cross_Regex_Backref = cross_regex_backref; */ /* Allocate memory for {m,n} construct counting variables if need be. */ if (Num_Braces > 0) { Brace = (brace_counts *) malloc (sizeof (brace_counts) + (size_t) Num_Braces); if (Brace == NULL) { reg_error ("out of memory in `ExecRE\'"); goto SINGLE_RETURN; } } else { Brace = NULL; } /* Initialize the first nine (9) capturing parentheses start and end pointers to point to the start of the search string. This is to prevent crashes when later trying to reference captured parens that do not exist in the compiled regex. We only need to do the first nine since users can only specify \1, \2, ... \9. */ for (i = 9; i > 0; i--) { *s_ptr++ = (unsigned char *) string; *e_ptr++ = (unsigned char *) string; } if (!reverse) { /* Forward Search */ if (prog->anchor) { /* Search is anchored at BOL */ if (attempt (prog, (unsigned char *) string)) { ret_val = 1; goto SINGLE_RETURN; } for (str = (unsigned char *) string; *str != '\0' && str != (unsigned char *) end && !Recursion_Limit_Exceeded; str++) { if (*str == '\n') { if (attempt (prog, str + 1)) { ret_val = 1; break; } } } goto SINGLE_RETURN; } else if (prog->match_start != '\0') { /* We know what char match must start with. */ for (str = (unsigned char *) string; *str != '\0' && str != (unsigned char *) end && !Recursion_Limit_Exceeded; str++) { if (*str == (unsigned char)prog->match_start) { if (attempt (prog, str)) { ret_val = 1; break; } } } goto SINGLE_RETURN; } else { /* General case */ for (str = (unsigned char *) string; *str != '\0' && str != (unsigned char *) end && !Recursion_Limit_Exceeded; str++) { if (attempt (prog, str)) { ret_val = 1; break; } } /* Beware of a single $ matching \0 */ if (!Recursion_Limit_Exceeded && !ret_val && *str == '\0' && str != (unsigned char *) end) { if (attempt (prog, str)) { ret_val = 1; } } goto SINGLE_RETURN; } } else { /* Search reverse, same as forward, but loops run backward */ if (prog->anchor) { /* Search is anchored at BOL */ for (str = (unsigned char *)(end - 1); str >= (unsigned char *) string && !Recursion_Limit_Exceeded; str--) { if (*str == '\n') { if (attempt (prog, str + 1)) { ret_val = 1; goto SINGLE_RETURN; } } } if (!Recursion_Limit_Exceeded && attempt (prog, (unsigned char *) string)) { ret_val = 1; goto SINGLE_RETURN; } goto SINGLE_RETURN; } else if (prog->match_start != '\0') { /* We know what char match must start with. */ for (str = (unsigned char *) end; str >= (unsigned char *) string && !Recursion_Limit_Exceeded; str--) { if (*str == (unsigned char)prog->match_start) { if (attempt (prog, str)) { ret_val = 1; break; } } } goto SINGLE_RETURN; } else { /* General case */ for (str = (unsigned char *) end; str >= (unsigned char *) string && !Recursion_Limit_Exceeded; str--) { if (attempt (prog, str)) { ret_val = 1; break; } } } } SINGLE_RETURN: if (Brace) free (Brace); if (Recursion_Limit_Exceeded) return (0); return (ret_val); } /*--------------------------------------------------------------------* * init_ansi_classes * * Generate character class sets using locale aware ANSI C functions. * *--------------------------------------------------------------------*/ static int init_ansi_classes (void) { static int initialized = 0; static int underscore = (int) '_'; int i, word_count, letter_count, space_count; if (!initialized) { initialized = 1; /* Only need to generate character sets once. */ word_count = 0; letter_count = 0; space_count = 0; for (i = 1; i < (int)UCHAR_MAX; i++) { if (isalnum (i) || i == underscore) { Word_Char [word_count++] = (unsigned char) i; } if (isalpha (i)) { Letter_Char [letter_count++] = (unsigned char) i; } /* Note: Whether or not newline is considered to be whitespace is handled by switches within the original regex and is thus omitted here. */ if (isspace (i) && (i != (int) '\n')) { White_Space [space_count++] = (unsigned char) i; } /* Make sure arrays are big enough. ("- 2" because of zero array origin and we need to leave room for the NULL terminator.) */ if (word_count > (ALNUM_CHAR_SIZE - 2) || space_count > (WHITE_SPACE_SIZE - 2) || letter_count > (ALNUM_CHAR_SIZE - 2)) { reg_error ("internal error #9 `init_ansi_classes\'"); return (0); } } Word_Char [word_count] = '\0'; Letter_Char [word_count] = '\0'; White_Space [space_count] = '\0'; } return (1); } /*----------------------------------------------------------------------* * attempt - try match at specific point, returns: 0 failure, 1 success *----------------------------------------------------------------------*/ static int attempt (regexp *prog, unsigned char *string) { register int i; register unsigned char **s_ptr; register unsigned char **e_ptr; int branch_index = 0; /* Must be set to zero ! */ Reg_Input = string; Start_Ptr_Ptr = (unsigned char **) prog->startp; End_Ptr_Ptr = (unsigned char **) prog->endp; s_ptr = (unsigned char **) prog->startp; e_ptr = (unsigned char **) prog->endp; /* Reset the recursion counter. */ Recursion_Count = 0; /* Overhead due to capturing parentheses. */ Extent_Ptr_BW = string; Extent_Ptr_FW = NULL; for (i = Total_Paren + 1; i > 0; i--) { *s_ptr++ = NULL; *e_ptr++ = NULL; } if (match ((unsigned char *) (prog->program + REGEX_START_OFFSET), &branch_index)) { prog->startp [0] = (char *) string; prog->endp [0] = (char *) Reg_Input; /* <-- One char AFTER */ prog->extentpBW = (char *) Extent_Ptr_BW; /* matched string! */ prog->extentpFW = (char *) Extent_Ptr_FW; prog->top_branch = branch_index; return (1); } else { return (0); } } /*----------------------------------------------------------------------* * match - 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. Returns 0 failure, 1 success. *----------------------------------------------------------------------*/ #define MATCH_RETURN(X)\ { --Recursion_Count; return (X); } #define CHECK_RECURSION_LIMIT\ if (Recursion_Limit_Exceeded) MATCH_RETURN (0); static int match (unsigned char *prog, int *branch_index_param) { register unsigned char *scan; /* Current node. */ unsigned char *next; /* Next node. */ register int next_ptr_offset; /* Used by the NEXT_PTR () macro */ if (++Recursion_Count > REGEX_RECURSION_LIMIT) { if (!Recursion_Limit_Exceeded) /* Prevent duplicate errors */ reg_error("recursion limit exceeded, please respecify expression"); Recursion_Limit_Exceeded = 1; MATCH_RETURN (0); } scan = prog; while (scan != NULL) { NEXT_PTR (scan, next); switch (GET_OP_CODE (scan)) { case BRANCH: { register unsigned char *save; register int branch_index_local = 0; if (GET_OP_CODE (next) != BRANCH) { /* No choice. */ next = OPERAND (scan); /* Avoid recursion. */ } else { do { save = Reg_Input; if (match (OPERAND (scan), NULL)) { if (branch_index_param) *branch_index_param = branch_index_local; MATCH_RETURN (1); } CHECK_RECURSION_LIMIT ++branch_index_local; Reg_Input = save; /* Backtrack. */ NEXT_PTR (scan, scan); } while (scan != NULL && GET_OP_CODE (scan) == BRANCH); MATCH_RETURN (0); /* NOT REACHED */ } } break; case EXACTLY: { register int len; register unsigned char *opnd; opnd = OPERAND (scan); /* Inline the first character, for speed. */ if (*opnd != *Reg_Input) MATCH_RETURN (0); len = strlen ((char *) opnd); if (len > 1 && strncmp ((char *) opnd, (char *) Reg_Input, len) != 0) { MATCH_RETURN (0); } Reg_Input += len; } break; case SIMILAR: { register unsigned char *opnd; register unsigned char test; opnd = OPERAND (scan); /* Note: the SIMILAR operand was converted to lower case during regex compile. */ while ((test = *opnd++) != '\0') { if (tolower (*Reg_Input++) != test) MATCH_RETURN (0); } } break; case BOL: /* `^' (beginning of line anchor) */ if (Reg_Input == Start_Of_String) { if (Prev_Is_BOL) break; } else if (*(Reg_Input - 1) == '\n') { break; } MATCH_RETURN (0); case EOL: /* `$' anchor matches end of line and end of string */ if (*Reg_Input == '\n' || (*Reg_Input == '\0' && Succ_Is_EOL)) { break; } MATCH_RETURN (0); case BOWORD: /* `<' (beginning of word anchor) */ /* Check to see if the current character is not a delimiter and the preceding character is. */ { int prev_is_delim; if (Reg_Input == Start_Of_String) { prev_is_delim = Prev_Is_Delim; } else { prev_is_delim = Current_Delimiters [ *(Reg_Input - 1) ]; } if (prev_is_delim) { int current_is_delim; if (*Reg_Input == '\0') { current_is_delim = Succ_Is_Delim; } else { current_is_delim = Current_Delimiters [ *Reg_Input ]; } if (!current_is_delim) break; } } MATCH_RETURN (0); case EOWORD: /* `>' (end of word anchor) */ /* Check to see if the current character is a delimiter and the preceding character is not. */ { int prev_is_delim; if (Reg_Input == Start_Of_String) { prev_is_delim = Prev_Is_Delim; } else { prev_is_delim = Current_Delimiters [ *(Reg_Input-1) ]; } if (!prev_is_delim) { int current_is_delim; if (*Reg_Input == '\0') { current_is_delim = Succ_Is_Delim; } else { current_is_delim = Current_Delimiters [ *Reg_Input ]; } if (current_is_delim) break; } } MATCH_RETURN (0); case NOT_BOUNDARY: /* \B (NOT a word boundary) */ { int prev_is_delim; int current_is_delim; if (Reg_Input == Start_Of_String) { prev_is_delim = Prev_Is_Delim; } else { prev_is_delim = Current_Delimiters [ *(Reg_Input-1) ]; } if (*Reg_Input == '\0') { current_is_delim = Succ_Is_Delim; } else { current_is_delim = Current_Delimiters [ *Reg_Input ]; } if (!(prev_is_delim ^ current_is_delim)) break; } MATCH_RETURN (0); case IS_DELIM: /* \y (A word delimiter character.) */ if (Current_Delimiters [ *Reg_Input ]) { Reg_Input++; break; } MATCH_RETURN (0); case NOT_DELIM: /* \Y (NOT a word delimiter character.) */ if (!Current_Delimiters [ *Reg_Input ]) { Reg_Input++; break; } MATCH_RETURN (0); case WORD_CHAR: /* \w (word character; alpha-numeric or underscore) */ if (isalnum ((int) *Reg_Input) || *Reg_Input == '_') { Reg_Input++; break; } MATCH_RETURN (0); case NOT_WORD_CHAR:/* \W (NOT a word character) */ if (isalnum ((int) *Reg_Input) || *Reg_Input == '_' || *Reg_Input == '\n' || *Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case ANY: /* `.' (matches any character EXCEPT newline) */ if (*Reg_Input == '\0' || *Reg_Input == '\n') MATCH_RETURN (0); Reg_Input++; break; case EVERY: /* `.' (matches any character INCLUDING newline) */ if (*Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case DIGIT: /* \d, same as [0123456789] */ if (!isdigit ((int) *Reg_Input)) MATCH_RETURN (0); Reg_Input++; break; case NOT_DIGIT: /* \D, same as [^0123456789] */ if (isdigit ((int) *Reg_Input) || *Reg_Input == '\n' || *Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case LETTER: /* \l, same as [a-zA-Z] */ if (!isalpha ((int) *Reg_Input)) MATCH_RETURN (0); Reg_Input++; break; case NOT_LETTER: /* \L, same as [^0123456789] */ if (isalpha ((int) *Reg_Input) || *Reg_Input == '\n' || *Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case SPACE: /* \s, same as [ \t\r\f\v] */ if (!isspace ((int) *Reg_Input) || *Reg_Input == '\n') MATCH_RETURN (0); Reg_Input++; break; case SPACE_NL: /* \s, same as [\n \t\r\f\v] */ if (!isspace ((int) *Reg_Input)) MATCH_RETURN (0); Reg_Input++; break; case NOT_SPACE: /* \S, same as [^\n \t\r\f\v] */ if (isspace ((int) *Reg_Input) || *Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case NOT_SPACE_NL: /* \S, same as [^ \t\r\f\v] */ if ((isspace ((int) *Reg_Input) && *Reg_Input != '\n') || *Reg_Input == '\0') MATCH_RETURN (0); Reg_Input++; break; case ANY_OF: /* [...] character class. */ if (*Reg_Input == '\0') MATCH_RETURN (0); /* Needed because strchr () considers \0 as a member of the character set. */ if (strchr ((char *) OPERAND (scan), (int) *Reg_Input) == NULL) { MATCH_RETURN (0); } Reg_Input++; break; case ANY_BUT: /* [^...] Negated character class-- does NOT normally match newline (\n added usually to operand at compile time.) */ if (*Reg_Input == '\0') MATCH_RETURN (0); /* See comment for ANY_OF. */ if (strchr ((char *) OPERAND (scan), (int) *Reg_Input) != NULL) { MATCH_RETURN (0); } Reg_Input++; break; case NOTHING: case BACK: break; case STAR: case PLUS: case QUESTION: case BRACE: case LAZY_STAR: case LAZY_PLUS: case LAZY_QUESTION: case LAZY_BRACE: { register unsigned long num_matched = REG_ZERO; register unsigned long min = ULONG_MAX, max = REG_ZERO; register unsigned char *save; register unsigned char next_char; unsigned char *next_op; int lazy = 0; /* Lookahead (when possible) to avoid useless match attempts when we know what character comes next. */ if (GET_OP_CODE (next) == EXACTLY) { next_char = *OPERAND (next); } else { next_char = '\0';/* i.e. Don't know what next character is. */ } next_op = OPERAND (scan); switch (GET_OP_CODE (scan)) { case LAZY_STAR: lazy = 1; case STAR: min = REG_ZERO; max = ULONG_MAX; break; case LAZY_PLUS: lazy = 1; case PLUS: min = REG_ONE; max = ULONG_MAX; break; case LAZY_QUESTION: lazy = 1; case QUESTION: min = REG_ZERO; max = REG_ONE; break; case LAZY_BRACE: lazy = 1; case BRACE: min = (unsigned long) GET_OFFSET (scan + NEXT_PTR_SIZE); max = (unsigned long) GET_OFFSET (scan + (2 * NEXT_PTR_SIZE)); if (max <= REG_INFINITY) max = ULONG_MAX; next_op = OPERAND (scan + (2 * NEXT_PTR_SIZE)); } save = Reg_Input; if (lazy) { if ( min > REG_ZERO) num_matched = greedy (next_op, min); } else { num_matched = greedy (next_op, max); } while (min <= num_matched && num_matched <= max) { if (next_char == '\0' || next_char == *Reg_Input) { if (match (next, NULL)) MATCH_RETURN (1); CHECK_RECURSION_LIMIT } /* Couldn't or didn't match. */ if (lazy) { if (!greedy (next_op, 1)) MATCH_RETURN (0); num_matched++; /* Inch forward. */ } else if (num_matched > REG_ZERO) { num_matched--; /* Back up. */ } else if (min == REG_ZERO && num_matched == REG_ZERO) { break; } Reg_Input = save + num_matched; } MATCH_RETURN (0); } break; case END: if (Extent_Ptr_FW == NULL || (Reg_Input - Extent_Ptr_FW) > 0) { Extent_Ptr_FW = Reg_Input; } MATCH_RETURN (1); /* Success! */ break; case INIT_COUNT: Brace->count [*OPERAND (scan)] = REG_ZERO; break; case INC_COUNT: Brace->count [*OPERAND (scan)]++; break; case TEST_COUNT: if (Brace->count [*OPERAND (scan)] < (unsigned long) GET_OFFSET (scan + NEXT_PTR_SIZE + INDEX_SIZE)) { next = scan + NODE_SIZE + INDEX_SIZE + NEXT_PTR_SIZE; } break; case BACK_REF: case BACK_REF_CI: /* case X_REGEX_BR: */ /* case X_REGEX_BR_CI: *** IMPLEMENT LATER */ { register unsigned char *captured, *finish; int paren_no; paren_no = (int) *OPERAND (scan); /* if (GET_OP_CODE (scan) == X_REGEX_BR || GET_OP_CODE (scan) == X_REGEX_BR_CI) { if (Cross_Regex_Backref == NULL) MATCH_RETURN (0); captured = (unsigned char *) Cross_Regex_Backref->startp [paren_no]; finish = (unsigned char *) Cross_Regex_Backref->endp [paren_no]; } else { */ captured = Back_Ref_Start [paren_no]; finish = Back_Ref_End [paren_no]; /* } */ if ((captured != NULL) && (finish != NULL)) { if (captured > finish) MATCH_RETURN (0); if (GET_OP_CODE (scan) == BACK_REF_CI /* || GET_OP_CODE (scan) == X_REGEX_BR_CI*/ ) { while (captured < finish) { if (tolower (*captured++) != tolower (*Reg_Input++)) { MATCH_RETURN (0); } } } else { while (captured < finish) { if (*captured++ != *Reg_Input++) MATCH_RETURN (0); } } break; } else { MATCH_RETURN (0); } } case POS_AHEAD_OPEN: case NEG_AHEAD_OPEN: { register unsigned char *save; int answer; save = Reg_Input; answer = match (next, NULL); /* Does the look-ahead regex match? */ CHECK_RECURSION_LIMIT if ((GET_OP_CODE (scan) == POS_AHEAD_OPEN) ? answer : !answer) { /* Remember the last (most to the right) character position that we consume in the input for a successful match. This is info that may be needed should an attempt be made to match the exact same text at the exact same place. Since look-aheads backtrack, a regex with a trailing look-ahead may need more text than it matches to accomplish a re-match. */ if (Extent_Ptr_FW == NULL || (Reg_Input - Extent_Ptr_FW) > 0) { Extent_Ptr_FW = Reg_Input; } Reg_Input = save; /* Backtrack to look-ahead start. */ /* Jump to the node just after the (?=...) or (?!...) Construct. */ next = next_ptr (OPERAND (scan)); /* Skip 1st branch */ /* Skip the chain of branches inside the look-ahead */ while(GET_OP_CODE(next) == BRANCH) next = next_ptr (next); next = next_ptr (next); /* Skip the LOOK_AHEAD_CLOSE */ } else { Reg_Input = save; /* Backtrack to look-ahead start. */ MATCH_RETURN (0); } } break; case POS_BEHIND_OPEN: case NEG_BEHIND_OPEN: { register unsigned char *save; int answer; register int offset, upper; int lower; int found = 0; unsigned char save_char; save = Reg_Input; save_char = *Reg_Input; /* Prevent overshoot (greedy matching could end past the current position). This means that look-ahead at the end of a look-behind pattern won't work, but it is highly unlikely that anyone ever needs this. It is documented as being not supported anyway. It is possible to lift this limitation, but only at the cost of increased complexity and an overall decrease in performance of the regex matching code, so it's probably not worth it. */ *Reg_Input = '\0'; lower = GET_LOWER (scan); upper = GET_UPPER (scan); /* Start with the shortest match first. This is the most efficient direction in general. Note! Negative look behind is _very_ tricky when the length is not constant: we have to make sure the expression doesn't match for _any_ of the starting positions. */ for (offset = lower; offset <= upper; ++offset) { Reg_Input = save - offset; if (Reg_Input < Look_Behind_To) { /* No need to look any further */ break; } answer = match (next, NULL); /* Does the look-behind regex match? */ CHECK_RECURSION_LIMIT /* The match must have ended at the current position; otherwise it is invalid */ if (answer && Reg_Input == save) { /* It matched, exactly far enough */ found = 1; /* Remember the last (most to the left) character position that we consume in the input for a successful match. This is info that may be needed should an attempt be made to match the exact same text at the exact same place. Since look-behind backtracks, a regex with a leading look-behind may need more text than it matches to accomplish a re-match. */ if (Extent_Ptr_BW == NULL || (Extent_Ptr_BW - (save - offset)) > 0) { Extent_Ptr_BW = save - offset; } break; } } /* Always restore the position and repair the string */ Reg_Input = save; *Reg_Input = save_char; if ((GET_OP_CODE (scan) == POS_BEHIND_OPEN) ? found : !found) { /* The look-behind matches, so we must jump to the next node. The look-behind node is followed by a chain of branches (contents of the look-behind expression), and terminated by a look-behind-close node. */ next = next_ptr (OPERAND (scan) + LENGTH_SIZE); /* 1st branch */ /* Skip the chained branches inside the look-ahead */ while (GET_OP_CODE (next) == BRANCH) next = next_ptr (next); next = next_ptr (next); /* Skip LOOK_BEHIND_CLOSE */ } else { /* Not a match */ MATCH_RETURN (0); } } break; case LOOK_AHEAD_CLOSE: case LOOK_BEHIND_CLOSE: MATCH_RETURN (1); /* We have reached the end of the look-ahead or look-behind which implies that we matched it, so return TRUE. */ default: if ((GET_OP_CODE (scan) > OPEN) && (GET_OP_CODE (scan) < OPEN + NSUBEXP)) { register int no; register unsigned char *save; no = GET_OP_CODE (scan) - OPEN; save = Reg_Input; if (no < 10) { Back_Ref_Start [no] = save; Back_Ref_End [no] = NULL; } if (match (next, NULL)) { /* Do not set `Start_Ptr_Ptr' if some later invocation (think recursion) of the same parentheses already has. */ if (Start_Ptr_Ptr [no] == NULL) Start_Ptr_Ptr [no] = save; MATCH_RETURN (1); } else { MATCH_RETURN (0); } } else if ((GET_OP_CODE (scan) > CLOSE) && (GET_OP_CODE (scan) < CLOSE + NSUBEXP)) { register int no; register unsigned char *save; no = GET_OP_CODE (scan) - CLOSE; save = Reg_Input; if (no < 10) Back_Ref_End [no] = save; if (match (next, NULL)) { /* Do not set `End_Ptr_Ptr' if some later invocation of the same parentheses already has. */ if (End_Ptr_Ptr [no] == NULL) End_Ptr_Ptr [no] = save; MATCH_RETURN (1); } else { MATCH_RETURN (0); } } else { reg_error ("memory corruption, `match\'"); MATCH_RETURN (0); } break; } scan = next; } /* We get here only if there's trouble -- normally "case END" is the terminating point. */ reg_error ("corrupted pointers, `match\'"); MATCH_RETURN (0); } /*----------------------------------------------------------------------* * greedy * * Repeatedly match something simple up to "max" times. If max <= 0 * then match as much as possible (max = infinity). Uses unsigned long * variables to maximize the amount of text matchable for unbounded * qualifiers like '*' and '+'. This will allow at least 4,294,967,295 * matches (4 Gig!) for an ANSI C compliant compiler. If you are * applying a regex to something bigger than that, you shouldn't be * using NEdit! * * Returns the actual number of matches. *----------------------------------------------------------------------*/ static unsigned long greedy (unsigned char *p, long max) { register unsigned char *input_str; register unsigned char *operand; register unsigned long count = REG_ZERO; register unsigned long max_cmp; input_str = Reg_Input; operand = OPERAND (p); /* Literal char or start of class characters. */ max_cmp = (max > 0) ? (unsigned long) max : ULONG_MAX; switch (GET_OP_CODE (p)) { case ANY: /* Race to the end of the line or string. Dot DOESN'T match newline. */ while (count < max_cmp && *input_str != '\0' && *input_str != '\n') { count++; input_str++; } break; case EVERY: /* Race to the end of the line or string. Dot DOES match newline. */ while (count < max_cmp && *input_str != '\0') { count++; input_str++; } break; case EXACTLY: /* Count occurrences of single character operand. */ while (count < max_cmp && *operand == *input_str) { count++; input_str++; } break; case SIMILAR: /* Case insensitive version of EXACTLY */ while (count < max_cmp && *operand == tolower (*input_str)) { count++; input_str++; } break; case ANY_OF: /* [...] character class. */ while (count < max_cmp && *input_str != '\0' && strchr ((char *) operand, (int) *input_str) != NULL) { count++; input_str++; } break; case ANY_BUT: /* [^...] Negated character class- does NOT normally match newline (\n added usually to operand at compile time.) */ while (count < max_cmp && *input_str != '\0' && strchr ((char *) operand, (int) *input_str) == NULL) { count++; input_str++; } break; case IS_DELIM: /* \y (not a word delimiter char) NOTE: '\n' and '\0' are always word delimiters. */ while (count < max_cmp && Current_Delimiters [ *input_str ]) { count++; input_str++; } break; case NOT_DELIM: /* \Y (not a word delimiter char) NOTE: '\n' and '\0' are always word delimiters. */ while (count < max_cmp && !Current_Delimiters [ *input_str ]) { count++; input_str++; } break; case WORD_CHAR: /* \w (word character, alpha-numeric or underscore) */ while (count < max_cmp && (isalnum ((int) *input_str) || *input_str == (unsigned char) '_')) { count++; input_str++; } break; case NOT_WORD_CHAR:/* \W (NOT a word character) */ while (count < max_cmp && !isalnum ((int) *input_str) && *input_str != (unsigned char) '_' && *input_str != (unsigned char) '\n' && *input_str != (unsigned char) '\0') { count++; input_str++; } break; case DIGIT: /* same as [0123456789] */ while (count < max_cmp && isdigit ((int) *input_str)) { count++; input_str++; } break; case NOT_DIGIT: /* same as [^0123456789] */ while (count < max_cmp && !isdigit ((int) *input_str) && *input_str != '\n' && *input_str != '\0') { count++; input_str++; } break; case SPACE: /* same as [ \t\r\f\v]-- doesn't match newline. */ while (count < max_cmp && isspace ((int) *input_str) && *input_str != '\n' && *input_str != '\0') { count++; input_str++; } break; case SPACE_NL: /* same as [\n \t\r\f\v]-- matches newline. */ while (count < max_cmp && isspace ((int) *input_str) && *input_str != '\0') { count++; input_str++; } break; case NOT_SPACE: /* same as [^\n \t\r\f\v]-- doesn't match newline. */ while (count < max_cmp && !isspace ((int) *input_str) && *input_str != '\0') { count++; input_str++; } break; case NOT_SPACE_NL: /* same as [^ \t\r\f\v]-- matches newline. */ while (count < max_cmp && (!isspace ((int) *input_str) || *input_str == '\n') && *input_str != '\0') { count++; input_str++; } break; case LETTER: /* same as [a-zA-Z] */ while (count < max_cmp && isalpha ((int) *input_str) && *input_str != '\0') { count++; input_str++; } break; case NOT_LETTER: /* same as [^a-zA-Z] */ while (count < max_cmp && !isalpha ((int) *input_str) && *input_str != '\n' && *input_str != '\0') { count++; input_str++; } break; default: /* Called inappropriately. Only atoms that are SIMPLE should generate a call to greedy. The above cases should cover all the atoms that are SIMPLE. */ reg_error ("internal error #10 `greedy\'"); count = 0U; /* Best we can do. */ } /* Point to character just after last matched character. */ Reg_Input = input_str; return (count); } /*----------------------------------------------------------------------* * next_ptr - compute the address of a node's "NEXT" pointer. * Note: a simplified inline version is available via the NEXT_PTR() macro, * but that one is only to be used at time-critical places (see the * description of the macro). *----------------------------------------------------------------------*/ static unsigned char * next_ptr (unsigned char *ptr) { register int offset; if (ptr == &Compute_Size) return (NULL); offset = GET_OFFSET (ptr); if (offset == 0) return (NULL); if (GET_OP_CODE (ptr) == BACK) { return (ptr - offset); } else { return (ptr + offset); } } /*----------------------------------------------------------------------* * SubstituteRE - Perform substitutions after a `regexp' match. *----------------------------------------------------------------------*/ void SubstituteRE ( regexp *prog, const char *source, char *dest, int max) { register unsigned char *src; unsigned char *src_alias; register unsigned char *dst; register unsigned char c; register unsigned char test; register int paren_no; register int len; register unsigned char chgcase; if (prog == NULL || source == NULL || dest == NULL) { reg_error ("NULL parm to `SubstituteRE\'"); return; } if (U_CHAR_AT (prog->program) != MAGIC) { reg_error ("damaged regexp passed to `SubstituteRE\'"); return; } src = (unsigned char *) source; dst = (unsigned char *) dest; while ((c = *src++) != '\0') { chgcase = '\0'; paren_no = -1; if (c == '\\') { /* Process any case altering tokens, i.e \u, \U, \l, \L. */ if (*src == 'u' || *src == 'U' || *src == 'l' || *src == 'L') { chgcase = *src; src++; c = *src++; if (c == '\0') break; } } if (c == '&') { paren_no = 0; } else if (c == '\\') { /* Can not pass register variable `&src' to function `numeric_escape' so make a non-register copy that we can take the address of. */ src_alias = src; if ('1' <= *src && *src <= '9') { paren_no = (int) *src++ - (int) '0'; } else if ((test = literal_escape (*src)) != '\0') { c = test; src++; } else if ((test = numeric_escape (*src, &src_alias)) != '\0') { c = test; src = src_alias; src++; /* NOTE: if an octal escape for zero is attempted (e.g. \000), it will be treated as a literal string. */ } else if (*src == '\0') { /* If '\' is the last character of the replacement string, it is interpreted as a literal backslash. */ c = '\\'; } else { c = *src++; /* Allow any escape sequence (This is */ } /* INCONSISTENT with the `CompileRE' */ } /* mind set of issuing an error! */ if (paren_no < 0) { /* Ordinary character. */ if (((char *) dst - (char *) dest) >= (max - 1)) { break; } else { *dst++ = c; } } else if (prog->startp [paren_no] != NULL && prog->endp [paren_no] != NULL) { len = prog->endp [paren_no] - prog->startp [paren_no]; if (((char *) dst + len - (char *) dest) >= max-1) { len = max - ((char *) dst - (char *) dest) - 1; } (void) strncpy ((char *) dst, (char *) prog->startp [paren_no], len); if (chgcase != '\0') adjustcase (dst, len, chgcase); dst += len; if (len != 0 && *(dst - 1) == '\0') { /* strncpy hit NUL. */ reg_error ("damaged match string in `SubstituteRE\'"); return; } } } *dst = '\0'; } static void adjustcase (unsigned char *str, int len, unsigned char chgcase) { register unsigned char *string = str; int i; /* The tokens \u and \l only modify the first character while the tokens \U and \L modify the entire string. */ if (islower (chgcase) && len > 0) len = 1; switch (chgcase) { case 'u': case 'U': for (i = 0; i < len; i++) { *(string + i) = toupper ((int) *(string + i)); } break; case 'l': case 'L': for (i = 0; i < len; i++) { *(string + i) = tolower ((int) *(string + i)); } break; } } /*----------------------------------------------------------------------* * reg_error *----------------------------------------------------------------------*/ static void reg_error (char *str) { fprintf ( stderr, "NEdit: Internal error processing regular expression (%s)\n", str); } /*----------------------------------------------------------------------* * makeDelimiterTable * * Translate a null-terminated string of delimiters into a 256 byte * lookup table for determining whether a character is a delimiter or * not. * * Table must be allocated by the caller. * * Return value is a pointer to the table. *----------------------------------------------------------------------*/ static unsigned char * makeDelimiterTable ( unsigned char *delimiters, unsigned char *table) { unsigned char *c; memset (table, 0, 256); for (c = (unsigned char *) delimiters; *c != '\0'; c++) { table [*c] = 1; } table [(int) NULL] = 1; /* These */ table [(int) '\t'] = 1; /* characters */ table [(int) '\n'] = 1; /* are always */ table [(int) ' ' ] = 1; /* delimiters. */ return table; } /*----------------------------------------------------------------------* * SetREDefaultWordDelimiters * * Builds a default delimiter table that persists across `ExecRE' calls. *----------------------------------------------------------------------*/ void SetREDefaultWordDelimiters (char *delimiters) { makeDelimiterTable ((unsigned char *) delimiters, Default_Delimiters); } void EnableCountingQuantifier (int is_enabled) { Enable_Counting_Quantifier = is_enabled; }