diff options
Diffstat (limited to 'gnu/usr.bin/awk/regex.c')
| -rw-r--r-- | gnu/usr.bin/awk/regex.c | 2854 |
1 files changed, 2854 insertions, 0 deletions
diff --git a/gnu/usr.bin/awk/regex.c b/gnu/usr.bin/awk/regex.c new file mode 100644 index 000000000000..f4dd4c2cd24d --- /dev/null +++ b/gnu/usr.bin/awk/regex.c @@ -0,0 +1,2854 @@ +/* Extended regular expression matching and search library. + Copyright (C) 1985, 1989-90 Free Software Foundation, Inc. + + This program 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 1, or (at your option) + any later version. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + + +/* To test, compile with -Dtest. This Dtestable feature turns this into + a self-contained program which reads a pattern, describes how it + compiles, then reads a string and searches for it. + + On the other hand, if you compile with both -Dtest and -Dcanned you + can run some tests we've already thought of. */ + + +#ifdef emacs + +/* The `emacs' switch turns on certain special matching commands + that make sense only in emacs. */ + +#include "lisp.h" +#include "buffer.h" +#include "syntax.h" + +/* We write fatal error messages on standard error. */ +#include <stdio.h> + +/* isalpha(3) etc. are used for the character classes. */ +#include <ctype.h> + +#else /* not emacs */ + +#include "awk.h" + +#define NO_ALLOCA /* try it out for now */ +#ifndef NO_ALLOCA +/* Make alloca work the best possible way. */ +#ifdef __GNUC__ +#ifndef atarist +#ifndef alloca +#define alloca __builtin_alloca +#endif +#endif /* atarist */ +#else +#if defined(sparc) && !defined(__GNUC__) +#include <alloca.h> +#else +char *alloca (); +#endif +#endif /* __GNUC__ */ + +#define FREE_AND_RETURN_VOID(stackb) return +#define FREE_AND_RETURN(stackb,val) return(val) +#define DOUBLE_STACK(stackx,stackb,len) \ + (stackx = (unsigned char **) alloca (2 * len \ + * sizeof (unsigned char *)),\ + /* Only copy what is in use. */ \ + (unsigned char **) memcpy (stackx, stackb, len * sizeof (char *))) +#else /* NO_ALLOCA defined */ +#define FREE_AND_RETURN_VOID(stackb) free(stackb);return +#define FREE_AND_RETURN(stackb,val) free(stackb);return(val) +#define DOUBLE_STACK(stackx,stackb,len) \ + (unsigned char **) realloc (stackb, 2 * len * sizeof (unsigned char *)) +#endif /* NO_ALLOCA */ + +static void store_jump P((char *, int, char *)); +static void insert_jump P((int, char *, char *, char *)); +static void store_jump_n P((char *, int, char *, unsigned)); +static void insert_jump_n P((int, char *, char *, char *, unsigned)); +static void insert_op_2 P((int, char *, char *, int, int )); +static int memcmp_translate P((unsigned char *, unsigned char *, + int, unsigned char *)); +long re_set_syntax P((long)); + +/* Define the syntax stuff, so we can do the \<, \>, etc. */ + +/* This must be nonzero for the wordchar and notwordchar pattern + commands in re_match_2. */ +#ifndef Sword +#define Sword 1 +#endif + +#define SYNTAX(c) re_syntax_table[c] + + +#ifdef SYNTAX_TABLE + +char *re_syntax_table; + +#else /* not SYNTAX_TABLE */ + +static char re_syntax_table[256]; +static void init_syntax_once P((void)); + + +static void +init_syntax_once () +{ + register int c; + static int done = 0; + + if (done) + return; + + memset (re_syntax_table, 0, sizeof re_syntax_table); + + for (c = 'a'; c <= 'z'; c++) + re_syntax_table[c] = Sword; + + for (c = 'A'; c <= 'Z'; c++) + re_syntax_table[c] = Sword; + + for (c = '0'; c <= '9'; c++) + re_syntax_table[c] = Sword; + + /* Add specific syntax for ISO Latin-1. */ + for (c = 0300; c <= 0377; c++) + re_syntax_table[c] = Sword; + re_syntax_table[0327] = 0; + re_syntax_table[0367] = 0; + + done = 1; +} + +#endif /* SYNTAX_TABLE */ +#undef P +#endif /* emacs */ + + +/* Sequents are missing isgraph. */ +#ifndef isgraph +#define isgraph(c) (isprint((c)) && !isspace((c))) +#endif + +/* Get the interface, including the syntax bits. */ +#include "regex.h" + + +/* These are the command codes that appear in compiled regular + expressions, one per byte. Some command codes are followed by + argument bytes. A command code can specify any interpretation + whatsoever for its arguments. Zero-bytes may appear in the compiled + regular expression. + + The value of `exactn' is needed in search.c (search_buffer) in emacs. + So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of + `exactn' we use here must also be 1. */ + +enum regexpcode + { + unused=0, + exactn=1, /* Followed by one byte giving n, then by n literal bytes. */ + begline, /* Fail unless at beginning of line. */ + endline, /* Fail unless at end of line. */ + jump, /* Followed by two bytes giving relative address to jump to. */ + on_failure_jump, /* Followed by two bytes giving relative address of + place to resume at in case of failure. */ + finalize_jump, /* Throw away latest failure point and then jump to + address. */ + maybe_finalize_jump, /* Like jump but finalize if safe to do so. + This is used to jump back to the beginning + of a repeat. If the command that follows + this jump is clearly incompatible with the + one at the beginning of the repeat, such that + we can be sure that there is no use backtracking + out of repetitions already completed, + then we finalize. */ + dummy_failure_jump, /* Jump, and push a dummy failure point. This + failure point will be thrown away if an attempt + is made to use it for a failure. A + construct + makes this before the first repeat. Also + use it as an intermediary kind of jump when + compiling an or construct. */ + succeed_n, /* Used like on_failure_jump except has to succeed n times; + then gets turned into an on_failure_jump. The relative + address following it is useless until then. The + address is followed by two bytes containing n. */ + jump_n, /* Similar to jump, but jump n times only; also the relative + address following is in turn followed by yet two more bytes + containing n. */ + set_number_at, /* Set the following relative location to the + subsequent number. */ + anychar, /* Matches any (more or less) one character. */ + charset, /* Matches any one char belonging to specified set. + First following byte is number of bitmap bytes. + Then come bytes for a bitmap saying which chars are in. + Bits in each byte are ordered low-bit-first. + A character is in the set if its bit is 1. + A character too large to have a bit in the map + is automatically not in the set. */ + charset_not, /* Same parameters as charset, but match any character + that is not one of those specified. */ + start_memory, /* Start remembering the text that is matched, for + storing in a memory register. Followed by one + byte containing the register number. Register numbers + must be in the range 0 through RE_NREGS. */ + stop_memory, /* Stop remembering the text that is matched + and store it in a memory register. Followed by + one byte containing the register number. Register + numbers must be in the range 0 through RE_NREGS. */ + duplicate, /* Match a duplicate of something remembered. + Followed by one byte containing the index of the memory + register. */ + before_dot, /* Succeeds if before point. */ + at_dot, /* Succeeds if at point. */ + after_dot, /* Succeeds if after point. */ + begbuf, /* Succeeds if at beginning of buffer. */ + endbuf, /* Succeeds if at end of buffer. */ + wordchar, /* Matches any word-constituent character. */ + notwordchar, /* Matches any char that is not a word-constituent. */ + wordbeg, /* Succeeds if at word beginning. */ + wordend, /* Succeeds if at word end. */ + wordbound, /* Succeeds if at a word boundary. */ + notwordbound,/* Succeeds if not at a word boundary. */ + syntaxspec, /* Matches any character whose syntax is specified. + followed by a byte which contains a syntax code, + e.g., Sword. */ + notsyntaxspec /* Matches any character whose syntax differs from + that specified. */ + }; + + +/* Number of failure points to allocate space for initially, + when matching. If this number is exceeded, more space is allocated, + so it is not a hard limit. */ + +#ifndef NFAILURES +#define NFAILURES 80 +#endif + +#ifdef CHAR_UNSIGNED +#define SIGN_EXTEND_CHAR(c) ((c)>(char)127?(c)-256:(c)) /* for IBM RT */ +#endif +#ifndef SIGN_EXTEND_CHAR +#define SIGN_EXTEND_CHAR(x) (x) +#endif + + +/* Store NUMBER in two contiguous bytes starting at DESTINATION. */ +#define STORE_NUMBER(destination, number) \ + { (destination)[0] = (number) & 0377; \ + (destination)[1] = (number) >> 8; } + +/* Same as STORE_NUMBER, except increment the destination pointer to + the byte after where the number is stored. Watch out that values for + DESTINATION such as p + 1 won't work, whereas p will. */ +#define STORE_NUMBER_AND_INCR(destination, number) \ + { STORE_NUMBER(destination, number); \ + (destination) += 2; } + + +/* Put into DESTINATION a number stored in two contingous bytes starting + at SOURCE. */ +#define EXTRACT_NUMBER(destination, source) \ + { (destination) = *(source) & 0377; \ + (destination) += SIGN_EXTEND_CHAR (*(char *)((source) + 1)) << 8; } + +/* Same as EXTRACT_NUMBER, except increment the pointer for source to + point to second byte of SOURCE. Note that SOURCE has to be a value + such as p, not, e.g., p + 1. */ +#define EXTRACT_NUMBER_AND_INCR(destination, source) \ + { EXTRACT_NUMBER (destination, source); \ + (source) += 2; } + + +/* Specify the precise syntax of regexps for compilation. This provides + for compatibility for various utilities which historically have + different, incompatible syntaxes. + + The argument SYNTAX is a bit-mask comprised of the various bits + defined in regex.h. */ + +long +re_set_syntax (syntax) + long syntax; +{ + long ret; + + ret = obscure_syntax; + obscure_syntax = syntax; + return ret; +} + +/* Set by re_set_syntax to the current regexp syntax to recognize. */ +long obscure_syntax = 0; + + + +/* Macros for re_compile_pattern, which is found below these definitions. */ + +#define CHAR_CLASS_MAX_LENGTH 6 + +/* Fetch the next character in the uncompiled pattern, translating it if + necessary. */ +#define PATFETCH(c) \ + {if (p == pend) goto end_of_pattern; \ + c = * (unsigned char *) p++; \ + if (translate) c = translate[c]; } + +/* Fetch the next character in the uncompiled pattern, with no + translation. */ +#define PATFETCH_RAW(c) \ + {if (p == pend) goto end_of_pattern; \ + c = * (unsigned char *) p++; } + +#define PATUNFETCH p-- + + +/* If the buffer isn't allocated when it comes in, use this. */ +#define INIT_BUF_SIZE 28 + +/* Make sure we have at least N more bytes of space in buffer. */ +#define GET_BUFFER_SPACE(n) \ + { \ + while (b - bufp->buffer + (n) >= bufp->allocated) \ + EXTEND_BUFFER; \ + } + +/* Make sure we have one more byte of buffer space and then add CH to it. */ +#define BUFPUSH(ch) \ + { \ + GET_BUFFER_SPACE (1); \ + *b++ = (char) (ch); \ + } + +/* Extend the buffer by twice its current size via reallociation and + reset the pointers that pointed into the old allocation to point to + the correct places in the new allocation. If extending the buffer + results in it being larger than 1 << 16, then flag memory exhausted. */ +#define EXTEND_BUFFER \ + { char *old_buffer = bufp->buffer; \ + if (bufp->allocated == (1L<<16)) goto too_big; \ + bufp->allocated *= 2; \ + if (bufp->allocated > (1L<<16)) bufp->allocated = (1L<<16); \ + bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated); \ + if (bufp->buffer == 0) \ + goto memory_exhausted; \ + b = (b - old_buffer) + bufp->buffer; \ + if (fixup_jump) \ + fixup_jump = (fixup_jump - old_buffer) + bufp->buffer; \ + if (laststart) \ + laststart = (laststart - old_buffer) + bufp->buffer; \ + begalt = (begalt - old_buffer) + bufp->buffer; \ + if (pending_exact) \ + pending_exact = (pending_exact - old_buffer) + bufp->buffer; \ + } + +/* Set the bit for character C in a character set list. */ +#define SET_LIST_BIT(c) (b[(c) / BYTEWIDTH] |= 1 << ((c) % BYTEWIDTH)) + +/* Get the next unsigned number in the uncompiled pattern. */ +#define GET_UNSIGNED_NUMBER(num) \ + { if (p != pend) \ + { \ + PATFETCH (c); \ + while (isdigit (c)) \ + { \ + if (num < 0) \ + num = 0; \ + num = num * 10 + c - '0'; \ + if (p == pend) \ + break; \ + PATFETCH (c); \ + } \ + } \ + } + +/* Subroutines for re_compile_pattern. */ +/* static void store_jump (), insert_jump (), store_jump_n (), + insert_jump_n (), insert_op_2 (); */ + + +/* re_compile_pattern takes a regular-expression string + and converts it into a buffer full of byte commands for matching. + + PATTERN is the address of the pattern string + SIZE is the length of it. + BUFP is a struct re_pattern_buffer * which points to the info + on where to store the byte commands. + This structure contains a char * which points to the + actual space, which should have been obtained with malloc. + re_compile_pattern may use realloc to grow the buffer space. + + The number of bytes of commands can be found out by looking in + the `struct re_pattern_buffer' that bufp pointed to, after + re_compile_pattern returns. */ + +char * +re_compile_pattern (pattern, size, bufp) + char *pattern; + size_t size; + struct re_pattern_buffer *bufp; +{ + register char *b = bufp->buffer; + register char *p = pattern; + char *pend = pattern + size; + register unsigned c, c1; + char *p0; + unsigned char *translate = (unsigned char *) bufp->translate; + + /* Address of the count-byte of the most recently inserted `exactn' + command. This makes it possible to tell whether a new exact-match + character can be added to that command or requires a new `exactn' + command. */ + + char *pending_exact = 0; + + /* Address of the place where a forward-jump should go to the end of + the containing expression. Each alternative of an `or', except the + last, ends with a forward-jump of this sort. */ + + char *fixup_jump = 0; + + /* Address of start of the most recently finished expression. + This tells postfix * where to find the start of its operand. */ + + char *laststart = 0; + + /* In processing a repeat, 1 means zero matches is allowed. */ + + char zero_times_ok; + + /* In processing a repeat, 1 means many matches is allowed. */ + + char many_times_ok; + + /* Address of beginning of regexp, or inside of last \(. */ + + char *begalt = b; + + /* In processing an interval, at least this many matches must be made. */ + int lower_bound; + + /* In processing an interval, at most this many matches can be made. */ + int upper_bound; + + /* Place in pattern (i.e., the {) to which to go back if the interval + is invalid. */ + char *beg_interval = 0; + + /* Stack of information saved by \( and restored by \). + Four stack elements are pushed by each \(: + First, the value of b. + Second, the value of fixup_jump. + Third, the value of regnum. + Fourth, the value of begalt. */ + + int stackb[40]; + int *stackp = stackb; + int *stacke = stackb + 40; + int *stackt; + + /* Counts \('s as they are encountered. Remembered for the matching \), + where it becomes the register number to put in the stop_memory + command. */ + + int regnum = 1; + + bufp->fastmap_accurate = 0; + +#ifndef emacs +#ifndef SYNTAX_TABLE + /* Initialize the syntax table. */ + init_syntax_once(); +#endif +#endif + + if (bufp->allocated == 0) + { + bufp->allocated = INIT_BUF_SIZE; + if (bufp->buffer) + /* EXTEND_BUFFER loses when bufp->allocated is 0. */ + bufp->buffer = (char *) realloc (bufp->buffer, INIT_BUF_SIZE); + else + /* Caller did not allocate a buffer. Do it for them. */ + bufp->buffer = (char *) malloc (INIT_BUF_SIZE); + if (!bufp->buffer) goto memory_exhausted; + begalt = b = bufp->buffer; + } + + while (p != pend) + { + PATFETCH (c); + + switch (c) + { + case '$': + { + char *p1 = p; + /* When testing what follows the $, + look past the \-constructs that don't consume anything. */ + if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + while (p1 != pend) + { + if (*p1 == '\\' && p1 + 1 != pend + && (p1[1] == '<' || p1[1] == '>' + || p1[1] == '`' || p1[1] == '\'' +#ifdef emacs + || p1[1] == '=' +#endif + || p1[1] == 'b' || p1[1] == 'B')) + p1 += 2; + else + break; + } + if (obscure_syntax & RE_TIGHT_VBAR) + { + if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p1 != pend) + goto normal_char; + /* Make operand of last vbar end before this `$'. */ + if (fixup_jump) + store_jump (fixup_jump, jump, b); + fixup_jump = 0; + BUFPUSH (endline); + break; + } + /* $ means succeed if at end of line, but only in special contexts. + If validly in the middle of a pattern, it is a normal character. */ + + if ((obscure_syntax & RE_CONTEXTUAL_INVALID_OPS) && p1 != pend) + goto invalid_pattern; + if (p1 == pend || *p1 == '\n' + || (obscure_syntax & RE_CONTEXT_INDEP_OPS) + || (obscure_syntax & RE_NO_BK_PARENS + ? *p1 == ')' + : *p1 == '\\' && p1[1] == ')') + || (obscure_syntax & RE_NO_BK_VBAR + ? *p1 == '|' + : *p1 == '\\' && p1[1] == '|')) + { + BUFPUSH (endline); + break; + } + goto normal_char; + } + case '^': + /* ^ means succeed if at beg of line, but only if no preceding + pattern. */ + + if ((obscure_syntax & RE_CONTEXTUAL_INVALID_OPS) && laststart) + goto invalid_pattern; + if (laststart && p - 2 >= pattern && p[-2] != '\n' + && !(obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + if (obscure_syntax & RE_TIGHT_VBAR) + { + if (p != pattern + 1 + && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + BUFPUSH (begline); + begalt = b; + } + else + BUFPUSH (begline); + break; + + case '+': + case '?': + if ((obscure_syntax & RE_BK_PLUS_QM) + || (obscure_syntax & RE_LIMITED_OPS)) + goto normal_char; + handle_plus: + case '*': + /* If there is no previous pattern, char not special. */ + if (!laststart) + { + if (obscure_syntax & RE_CONTEXTUAL_INVALID_OPS) + goto invalid_pattern; + else if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS)) + goto normal_char; + } + /* If there is a sequence of repetition chars, + collapse it down to just one. */ + zero_times_ok = 0; + many_times_ok = 0; + while (1) + { + zero_times_ok |= c != '+'; + many_times_ok |= c != '?'; + if (p == pend) + break; + PATFETCH (c); + if (c == '*') + ; + else if (!(obscure_syntax & RE_BK_PLUS_QM) + && (c == '+' || c == '?')) + ; + else if ((obscure_syntax & RE_BK_PLUS_QM) + && c == '\\') + { + /* int c1; */ + PATFETCH (c1); + if (!(c1 == '+' || c1 == '?')) + { + PATUNFETCH; + PATUNFETCH; + break; + } + c = c1; + } + else + { + PATUNFETCH; + break; + } + } + + /* Star, etc. applied to an empty pattern is equivalent + to an empty pattern. */ + if (!laststart) + break; + + /* Now we know whether or not zero matches is allowed + and also whether or not two or more matches is allowed. */ + if (many_times_ok) + { + /* If more than one repetition is allowed, put in at the + end a backward relative jump from b to before the next + jump we're going to put in below (which jumps from + laststart to after this jump). */ + GET_BUFFER_SPACE (3); + store_jump (b, maybe_finalize_jump, laststart - 3); + b += 3; /* Because store_jump put stuff here. */ + } + /* On failure, jump from laststart to b + 3, which will be the + end of the buffer after this jump is inserted. */ + GET_BUFFER_SPACE (3); + insert_jump (on_failure_jump, laststart, b + 3, b); + pending_exact = 0; + b += 3; + if (!zero_times_ok) + { + /* At least one repetition is required, so insert a + dummy-failure before the initial on-failure-jump + instruction of the loop. This effects a skip over that + instruction the first time we hit that loop. */ + GET_BUFFER_SPACE (6); + insert_jump (dummy_failure_jump, laststart, laststart + 6, b); + b += 3; + } + break; + + case '.': + laststart = b; + BUFPUSH (anychar); + break; + + case '[': + if (p == pend) + goto invalid_pattern; + while (b - bufp->buffer + > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH) + EXTEND_BUFFER; + + laststart = b; + if (*p == '^') + { + BUFPUSH (charset_not); + p++; + } + else + BUFPUSH (charset); + p0 = p; + + BUFPUSH ((1 << BYTEWIDTH) / BYTEWIDTH); + /* Clear the whole map */ + memset (b, 0, (1 << BYTEWIDTH) / BYTEWIDTH); + + if ((obscure_syntax & RE_HAT_NOT_NEWLINE) && b[-2] == charset_not) + SET_LIST_BIT ('\n'); + + + /* Read in characters and ranges, setting map bits. */ + while (1) + { + /* Don't translate while fetching, in case it's a range bound. + When we set the bit for the character, we translate it. */ + PATFETCH_RAW (c); + + /* If set, \ escapes characters when inside [...]. */ + if ((obscure_syntax & RE_AWK_CLASS_HACK) && c == '\\') + { + PATFETCH(c1); + SET_LIST_BIT (c1); + continue; + } + if (c == ']') + { + if (p == p0 + 1) + { + /* If this is an empty bracket expression. */ + if ((obscure_syntax & RE_NO_EMPTY_BRACKETS) + && p == pend) + goto invalid_pattern; + } + else + /* Stop if this isn't merely a ] inside a bracket + expression, but rather the end of a bracket + expression. */ + break; + } + /* Get a range. */ + if (p[0] == '-' && p[1] != ']') + { + PATFETCH (c1); + /* Don't translate the range bounds while fetching them. */ + PATFETCH_RAW (c1); + + if ((obscure_syntax & RE_NO_EMPTY_RANGES) && c > c1) + goto invalid_pattern; + + if ((obscure_syntax & RE_NO_HYPHEN_RANGE_END) + && c1 == '-' && *p != ']') + goto invalid_pattern; + + while (c <= c1) + { + /* Translate each char that's in the range. */ + if (translate) + SET_LIST_BIT (translate[c]); + else + SET_LIST_BIT (c); + c++; + } + } + else if ((obscure_syntax & RE_CHAR_CLASSES) + && c == '[' && p[0] == ':') + { + /* Longest valid character class word has six characters. */ + char str[CHAR_CLASS_MAX_LENGTH]; + PATFETCH (c); + c1 = 0; + /* If no ] at end. */ + if (p == pend) + goto invalid_pattern; + while (1) + { + /* Don't translate the ``character class'' characters. */ + PATFETCH_RAW (c); + if (c == ':' || c == ']' || p == pend + || c1 == CHAR_CLASS_MAX_LENGTH) + break; + str[c1++] = c; + } + str[c1] = '\0'; + if (p == pend + || c == ']' /* End of the bracket expression. */ + || p[0] != ']' + || p + 1 == pend + || (strcmp (str, "alpha") != 0 + && strcmp (str, "upper") != 0 + && strcmp (str, "lower") != 0 + && strcmp (str, "digit") != 0 + && strcmp (str, "alnum") != 0 + && strcmp (str, "xdigit") != 0 + && strcmp (str, "space") != 0 + && strcmp (str, "print") != 0 + && strcmp (str, "punct") != 0 + && strcmp (str, "graph") != 0 + && strcmp (str, "cntrl") != 0)) + { + /* Undo the ending character, the letters, and leave + the leading : and [ (but set bits for them). */ + c1++; + while (c1--) + PATUNFETCH; + SET_LIST_BIT ('['); + SET_LIST_BIT (':'); + } + else + { + /* The ] at the end of the character class. */ + PATFETCH (c); + if (c != ']') + goto invalid_pattern; + for (c = 0; c < (1 << BYTEWIDTH); c++) + { + if ((strcmp (str, "alpha") == 0 && isalpha (c)) + || (strcmp (str, "upper") == 0 && isupper (c)) + || (strcmp (str, "lower") == 0 && islower (c)) + || (strcmp (str, "digit") == 0 && isdigit (c)) + || (strcmp (str, "alnum") == 0 && isalnum (c)) + || (strcmp (str, "xdigit") == 0 && isxdigit (c)) + || (strcmp (str, "space") == 0 && isspace (c)) + || (strcmp (str, "print") == 0 && isprint (c)) + || (strcmp (str, "punct") == 0 && ispunct (c)) + || (strcmp (str, "graph") == 0 && isgraph (c)) + || (strcmp (str, "cntrl") == 0 && iscntrl (c))) + SET_LIST_BIT (c); + } + } + } + else if (translate) + SET_LIST_BIT (translate[c]); + else + SET_LIST_BIT (c); + } + + /* Discard any character set/class bitmap bytes that are all + 0 at the end of the map. Decrement the map-length byte too. */ + while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) + b[-1]--; + b += b[-1]; + break; + + case '(': + if (! (obscure_syntax & RE_NO_BK_PARENS)) + goto normal_char; + else + goto handle_open; + + case ')': + if (! (obscure_syntax & RE_NO_BK_PARENS)) + goto normal_char; + else + goto handle_close; + + case '\n': + if (! (obscure_syntax & RE_NEWLINE_OR)) + goto normal_char; + else + goto handle_bar; + + case '|': + if ((obscure_syntax & RE_CONTEXTUAL_INVALID_OPS) + && (! laststart || p == pend)) + goto invalid_pattern; + else if (! (obscure_syntax & RE_NO_BK_VBAR)) + goto normal_char; + else + goto handle_bar; + + case '{': + if (! ((obscure_syntax & RE_NO_BK_CURLY_BRACES) + && (obscure_syntax & RE_INTERVALS))) + goto normal_char; + else + goto handle_interval; + + case '\\': + if (p == pend) goto invalid_pattern; + PATFETCH_RAW (c); + switch (c) + { + case '(': + if (obscure_syntax & RE_NO_BK_PARENS) + goto normal_backsl; + handle_open: + if (stackp == stacke) goto nesting_too_deep; + + /* Laststart should point to the start_memory that we are about + to push (unless the pattern has RE_NREGS or more ('s). */ + *stackp++ = b - bufp->buffer; + if (regnum < RE_NREGS) + { + BUFPUSH (start_memory); + BUFPUSH (regnum); + } + *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0; + *stackp++ = regnum++; + *stackp++ = begalt - bufp->buffer; + fixup_jump = 0; + laststart = 0; + begalt = b; + break; + + case ')': + if (obscure_syntax & RE_NO_BK_PARENS) + goto normal_backsl; + handle_close: + if (stackp == stackb) goto unmatched_close; + begalt = *--stackp + bufp->buffer; + if (fixup_jump) + store_jump (fixup_jump, jump, b); + if (stackp[-1] < RE_NREGS) + { + BUFPUSH (stop_memory); + BUFPUSH (stackp[-1]); + } + stackp -= 2; + fixup_jump = *stackp ? *stackp + bufp->buffer - 1 : 0; + laststart = *--stackp + bufp->buffer; + break; + + case '|': + if ((obscure_syntax & RE_LIMITED_OPS) + || (obscure_syntax & RE_NO_BK_VBAR)) + goto normal_backsl; + handle_bar: + if (obscure_syntax & RE_LIMITED_OPS) + goto normal_char; + /* Insert before the previous alternative a jump which + jumps to this alternative if the former fails. */ + GET_BUFFER_SPACE (6); + insert_jump (on_failure_jump, begalt, b + 6, b); + pending_exact = 0; + b += 3; + /* The alternative before the previous alternative has a + jump after it which gets executed if it gets matched. + Adjust that jump so it will jump to the previous + alternative's analogous jump (put in below, which in + turn will jump to the next (if any) alternative's such + jump, etc.). The last such jump jumps to the correct + final destination. */ + if (fixup_jump) + store_jump (fixup_jump, jump, b); + + /* Leave space for a jump after previous alternative---to be + filled in later. */ + fixup_jump = b; + b += 3; + + laststart = 0; + begalt = b; + break; + + case '{': + if (! (obscure_syntax & RE_INTERVALS) + /* Let \{ be a literal. */ + || ((obscure_syntax & RE_INTERVALS) + && (obscure_syntax & RE_NO_BK_CURLY_BRACES)) + /* If it's the string "\{". */ + || (p - 2 == pattern && p == pend)) + goto normal_backsl; + handle_interval: + beg_interval = p - 1; /* The {. */ + /* If there is no previous pattern, this isn't an interval. */ + if (!laststart) + { + if (obscure_syntax & RE_CONTEXTUAL_INVALID_OPS) + goto invalid_pattern; + else + goto normal_backsl; + } + /* It also isn't an interval if not preceded by an re + matching a single character or subexpression, or if + the current type of intervals can't handle back + references and the previous thing is a back reference. */ + if (! (*laststart == anychar + || *laststart == charset + || *laststart == charset_not + || *laststart == start_memory + || (*laststart == exactn && laststart[1] == 1) + || (! (obscure_syntax & RE_NO_BK_REFS) + && *laststart == duplicate))) + { + if (obscure_syntax & RE_NO_BK_CURLY_BRACES) + goto normal_char; + + /* Posix extended syntax is handled in previous + statement; this is for Posix basic syntax. */ + if (obscure_syntax & RE_INTERVALS) + goto invalid_pattern; + + goto normal_backsl; + } + lower_bound = -1; /* So can see if are set. */ + upper_bound = -1; + GET_UNSIGNED_NUMBER (lower_bound); + if (c == ',') + { + GET_UNSIGNED_NUMBER (upper_bound); + if (upper_bound < 0) + upper_bound = RE_DUP_MAX; + } + if (upper_bound < 0) + upper_bound = lower_bound; + if (! (obscure_syntax & RE_NO_BK_CURLY_BRACES)) + { + if (c != '\\') + goto invalid_pattern; + PATFETCH (c); + } + if (c != '}' || lower_bound < 0 || upper_bound > RE_DUP_MAX + || lower_bound > upper_bound + || ((obscure_syntax & RE_NO_BK_CURLY_BRACES) + && p != pend && *p == '{')) + { + if (obscure_syntax & RE_NO_BK_CURLY_BRACES) + goto unfetch_interval; + else + goto invalid_pattern; + } + + /* If upper_bound is zero, don't want to succeed at all; + jump from laststart to b + 3, which will be the end of + the buffer after this jump is inserted. */ + + if (upper_bound == 0) + { + GET_BUFFER_SPACE (3); + insert_jump (jump, laststart, b + 3, b); + b += 3; + } + + /* Otherwise, after lower_bound number of succeeds, jump + to after the jump_n which will be inserted at the end + of the buffer, and insert that jump_n. */ + else + { /* Set to 5 if only one repetition is allowed and + hence no jump_n is inserted at the current end of + the buffer; then only space for the succeed_n is + needed. Otherwise, need space for both the + succeed_n and the jump_n. */ + + unsigned slots_needed = upper_bound == 1 ? 5 : 10; + + GET_BUFFER_SPACE (slots_needed); + /* Initialize the succeed_n to n, even though it will + be set by its attendant set_number_at, because + re_compile_fastmap will need to know it. Jump to + what the end of buffer will be after inserting + this succeed_n and possibly appending a jump_n. */ + insert_jump_n (succeed_n, laststart, b + slots_needed, + b, lower_bound); + b += 5; /* Just increment for the succeed_n here. */ + + /* More than one repetition is allowed, so put in at + the end of the buffer a backward jump from b to the + succeed_n we put in above. By the time we've gotten + to this jump when matching, we'll have matched once + already, so jump back only upper_bound - 1 times. */ + + if (upper_bound > 1) + { + store_jump_n (b, jump_n, laststart, upper_bound - 1); + b += 5; + /* When hit this when matching, reset the + preceding jump_n's n to upper_bound - 1. */ + BUFPUSH (set_number_at); + GET_BUFFER_SPACE (2); + STORE_NUMBER_AND_INCR (b, -5); + STORE_NUMBER_AND_INCR (b, upper_bound - 1); + } + /* When hit this when matching, set the succeed_n's n. */ + GET_BUFFER_SPACE (5); + insert_op_2 (set_number_at, laststart, b, 5, lower_bound); + b += 5; + } + pending_exact = 0; + beg_interval = 0; + break; + + + unfetch_interval: + /* If an invalid interval, match the characters as literals. */ + if (beg_interval) + p = beg_interval; + else + { + fprintf (stderr, + "regex: no interval beginning to which to backtrack.\n"); + exit (1); + } + + beg_interval = 0; + PATFETCH (c); /* normal_char expects char in `c'. */ + goto normal_char; + break; + +#ifdef emacs + case '=': + BUFPUSH (at_dot); + break; + + case 's': + laststart = b; + BUFPUSH (syntaxspec); + PATFETCH (c); + BUFPUSH (syntax_spec_code[c]); + break; + + case 'S': + laststart = b; + BUFPUSH (notsyntaxspec); + PATFETCH (c); + BUFPUSH (syntax_spec_code[c]); + break; +#endif /* emacs */ + + case 'w': + laststart = b; + BUFPUSH (wordchar); + break; + + case 'W': + laststart = b; + BUFPUSH (notwordchar); + break; + + case '<': + BUFPUSH (wordbeg); + break; + + case '>': + BUFPUSH (wordend); + break; + + case 'b': + BUFPUSH (wordbound); + break; + + case 'B': + BUFPUSH (notwordbound); + break; + + case '`': + BUFPUSH (begbuf); + break; + + case '\'': + BUFPUSH (endbuf); + break; + + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + if (obscure_syntax & RE_NO_BK_REFS) + goto normal_char; + c1 = c - '0'; + if (c1 >= regnum) + { + if (obscure_syntax & RE_NO_EMPTY_BK_REF) + goto invalid_pattern; + else + goto normal_char; + } + /* Can't back reference to a subexpression if inside of it. */ + for (stackt = stackp - 2; stackt > stackb; stackt -= 4) + if (*stackt == c1) + goto normal_char; + laststart = b; + BUFPUSH (duplicate); + BUFPUSH (c1); + break; + + case '+': + case '?': + if (obscure_syntax & RE_BK_PLUS_QM) + goto handle_plus; + else + goto normal_backsl; + break; + + default: + normal_backsl: + /* You might think it would be useful for \ to mean + not to translate; but if we don't translate it + it will never match anything. */ + if (translate) c = translate[c]; + goto normal_char; + } + break; + + default: + normal_char: /* Expects the character in `c'. */ + if (!pending_exact || pending_exact + *pending_exact + 1 != b + || *pending_exact == 0177 || *p == '*' || *p == '^' + || ((obscure_syntax & RE_BK_PLUS_QM) + ? *p == '\\' && (p[1] == '+' || p[1] == '?') + : (*p == '+' || *p == '?')) + || ((obscure_syntax & RE_INTERVALS) + && ((obscure_syntax & RE_NO_BK_CURLY_BRACES) + ? *p == '{' + : (p[0] == '\\' && p[1] == '{')))) + { + laststart = b; + BUFPUSH (exactn); + pending_exact = b; + BUFPUSH (0); + } + BUFPUSH (c); + (*pending_exact)++; + } + } + + if (fixup_jump) + store_jump (fixup_jump, jump, b); + + if (stackp != stackb) goto unmatched_open; + + bufp->used = b - bufp->buffer; + return 0; + + invalid_pattern: + return "Invalid regular expression"; + + unmatched_open: + return "Unmatched \\("; + + unmatched_close: + return "Unmatched \\)"; + + end_of_pattern: + return "Premature end of regular expression"; + + nesting_too_deep: + return "Nesting too deep"; + + too_big: + return "Regular expression too big"; + + memory_exhausted: + return "Memory exhausted"; +} + + +/* Store a jump of the form <OPCODE> <relative address>. + Store in the location FROM a jump operation to jump to relative + address FROM - TO. OPCODE is the opcode to store. */ + +static void +store_jump (from, opcode, to) + char *from, *to; + int opcode; +{ + from[0] = (char)opcode; + STORE_NUMBER(from + 1, to - (from + 3)); +} + + +/* Open up space before char FROM, and insert there a jump to TO. + CURRENT_END gives the end of the storage not in use, so we know + how much data to copy up. OP is the opcode of the jump to insert. + + If you call this function, you must zero out pending_exact. */ + +static void +insert_jump (op, from, to, current_end) + int op; + char *from, *to, *current_end; +{ + register char *pfrom = current_end; /* Copy from here... */ + register char *pto = current_end + 3; /* ...to here. */ + + while (pfrom != from) + *--pto = *--pfrom; + store_jump (from, op, to); +} + + +/* Store a jump of the form <opcode> <relative address> <n> . + + Store in the location FROM a jump operation to jump to relative + address FROM - TO. OPCODE is the opcode to store, N is a number the + jump uses, say, to decide how many times to jump. + + If you call this function, you must zero out pending_exact. */ + +static void +store_jump_n (from, opcode, to, n) + char *from, *to; + int opcode; + unsigned n; +{ + from[0] = (char)opcode; + STORE_NUMBER (from + 1, to - (from + 3)); + STORE_NUMBER (from + 3, n); +} + + +/* Similar to insert_jump, but handles a jump which needs an extra + number to handle minimum and maximum cases. Open up space at + location FROM, and insert there a jump to TO. CURRENT_END gives the + end of the storage in use, so we know how much data to copy up. OP is + the opcode of the jump to insert. + + If you call this function, you must zero out pending_exact. */ + +static void +insert_jump_n (op, from, to, current_end, n) + int op; + char *from, *to, *current_end; + unsigned n; +{ + register char *pfrom = current_end; /* Copy from here... */ + register char *pto = current_end + 5; /* ...to here. */ + + while (pfrom != from) + *--pto = *--pfrom; + store_jump_n (from, op, to, n); +} + + +/* Open up space at location THERE, and insert operation OP followed by + NUM_1 and NUM_2. CURRENT_END gives the end of the storage in use, so + we know how much data to copy up. + + If you call this function, you must zero out pending_exact. */ + +static void +insert_op_2 (op, there, current_end, num_1, num_2) + int op; + char *there, *current_end; + int num_1, num_2; +{ + register char *pfrom = current_end; /* Copy from here... */ + register char *pto = current_end + 5; /* ...to here. */ + + while (pfrom != there) + *--pto = *--pfrom; + + there[0] = (char)op; + STORE_NUMBER (there + 1, num_1); + STORE_NUMBER (there + 3, num_2); +} + + + +/* Given a pattern, compute a fastmap from it. The fastmap records + which of the (1 << BYTEWIDTH) possible characters can start a string + that matches the pattern. This fastmap is used by re_search to skip + quickly over totally implausible text. + + The caller must supply the address of a (1 << BYTEWIDTH)-byte data + area as bufp->fastmap. + The other components of bufp describe the pattern to be used. */ + +void +re_compile_fastmap (bufp) + struct re_pattern_buffer *bufp; +{ + unsigned char *pattern = (unsigned char *) bufp->buffer; + int size = bufp->used; + register char *fastmap = bufp->fastmap; + register unsigned char *p = pattern; + register unsigned char *pend = pattern + size; + register int j, k; + unsigned char *translate = (unsigned char *) bufp->translate; + unsigned is_a_succeed_n; + +#ifndef NO_ALLOCA + unsigned char *stackb[NFAILURES]; + unsigned char **stackp = stackb; + +#else + unsigned char **stackb; + unsigned char **stackp; + stackb = (unsigned char **) malloc (NFAILURES * sizeof (unsigned char *)); + stackp = stackb; + +#endif /* NO_ALLOCA */ + memset (fastmap, 0, (1 << BYTEWIDTH)); + bufp->fastmap_accurate = 1; + bufp->can_be_null = 0; + + while (p) + { + is_a_succeed_n = 0; + if (p == pend) + { + bufp->can_be_null = 1; + break; + } +#ifdef SWITCH_ENUM_BUG + switch ((int) ((enum regexpcode) *p++)) +#else + switch ((enum regexpcode) *p++) +#endif + { + case exactn: + if (translate) + fastmap[translate[p[1]]] = 1; + else + fastmap[p[1]] = 1; + break; + + case begline: + case before_dot: + case at_dot: + case after_dot: + case begbuf: + case endbuf: + case wordbound: + case notwordbound: + case wordbeg: + case wordend: + continue; + + case endline: + if (translate) + fastmap[translate['\n']] = 1; + else + fastmap['\n'] = 1; + + if (bufp->can_be_null != 1) + bufp->can_be_null = 2; + break; + + case jump_n: + case finalize_jump: + case maybe_finalize_jump: + case jump: + case dummy_failure_jump: + EXTRACT_NUMBER_AND_INCR (j, p); + p += j; + if (j > 0) + continue; + /* Jump backward reached implies we just went through + the body of a loop and matched nothing. + Opcode jumped to should be an on_failure_jump. + Just treat it like an ordinary jump. + For a * loop, it has pushed its failure point already; + If so, discard that as redundant. */ + + if ((enum regexpcode) *p != on_failure_jump + && (enum regexpcode) *p != succeed_n) + continue; + p++; + EXTRACT_NUMBER_AND_INCR (j, p); + p += j; + if (stackp != stackb && *stackp == p) + stackp--; + continue; + + case on_failure_jump: + handle_on_failure_jump: + EXTRACT_NUMBER_AND_INCR (j, p); + *++stackp = p + j; + if (is_a_succeed_n) + EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */ + continue; + + case succeed_n: + is_a_succeed_n = 1; + /* Get to the number of times to succeed. */ + p += 2; + /* Increment p past the n for when k != 0. */ + EXTRACT_NUMBER_AND_INCR (k, p); + if (k == 0) + { + p -= 4; + goto handle_on_failure_jump; + } + continue; + + case set_number_at: + p += 4; + continue; + + case start_memory: + case stop_memory: + p++; + continue; + + case duplicate: + bufp->can_be_null = 1; + fastmap['\n'] = 1; + case anychar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (j != '\n') + fastmap[j] = 1; + if (bufp->can_be_null) + { + FREE_AND_RETURN_VOID(stackb); + } + /* Don't return; check the alternative paths + so we can set can_be_null if appropriate. */ + break; + + case wordchar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) == Sword) + fastmap[j] = 1; + break; + + case notwordchar: + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) != Sword) + fastmap[j] = 1; + break; + +#ifdef emacs + case syntaxspec: + k = *p++; + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) == (enum syntaxcode) k) + fastmap[j] = 1; + break; + + case notsyntaxspec: + k = *p++; + for (j = 0; j < (1 << BYTEWIDTH); j++) + if (SYNTAX (j) != (enum syntaxcode) k) + fastmap[j] = 1; + break; + +#else /* not emacs */ + case syntaxspec: + case notsyntaxspec: + break; +#endif /* not emacs */ + + case charset: + for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) + if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) + { + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + } + break; + + case charset_not: + /* Chars beyond end of map must be allowed */ + for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++) + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + + for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) + if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))) + { + if (translate) + fastmap[translate[j]] = 1; + else + fastmap[j] = 1; + } + break; + + case unused: /* pacify gcc -Wall */ + break; + } + + /* Get here means we have successfully found the possible starting + characters of one path of the pattern. We need not follow this + path any farther. Instead, look at the next alternative + remembered in the stack. */ + if (stackp != stackb) + p = *stackp--; + else + break; + } + FREE_AND_RETURN_VOID(stackb); +} + + + +/* Like re_search_2, below, but only one string is specified, and + doesn't let you say where to stop matching. */ + +int +re_search (pbufp, string, size, startpos, range, regs) + struct re_pattern_buffer *pbufp; + char *string; + int size, startpos, range; + struct re_registers *regs; +{ + return re_search_2 (pbufp, (char *) 0, 0, string, size, startpos, range, + regs, size); +} + + +/* Using the compiled pattern in PBUFP->buffer, first tries to match the + virtual concatenation of STRING1 and STRING2, starting first at index + STARTPOS, then at STARTPOS + 1, and so on. RANGE is the number of + places to try before giving up. If RANGE is negative, it searches + backwards, i.e., the starting positions tried are STARTPOS, STARTPOS + - 1, etc. STRING1 and STRING2 are of SIZE1 and SIZE2, respectively. + In REGS, return the indices of the virtual concatenation of STRING1 + and STRING2 that matched the entire PBUFP->buffer and its contained + subexpressions. Do not consider matching one past the index MSTOP in + the virtual concatenation of STRING1 and STRING2. + + The value returned is the position in the strings at which the match + was found, or -1 if no match was found, or -2 if error (such as + failure stack overflow). */ + +int +re_search_2 (pbufp, string1, size1, string2, size2, startpos, range, + regs, mstop) + struct re_pattern_buffer *pbufp; + char *string1, *string2; + int size1, size2; + int startpos; + register int range; + struct re_registers *regs; + int mstop; +{ + register char *fastmap = pbufp->fastmap; + register unsigned char *translate = (unsigned char *) pbufp->translate; + int total_size = size1 + size2; + int endpos = startpos + range; + int val; + + /* Check for out-of-range starting position. */ + if (startpos < 0 || startpos > total_size) + return -1; + + /* Fix up range if it would eventually take startpos outside of the + virtual concatenation of string1 and string2. */ + if (endpos < -1) + range = -1 - startpos; + else if (endpos > total_size) + range = total_size - startpos; + + /* Update the fastmap now if not correct already. */ + if (fastmap && !pbufp->fastmap_accurate) + re_compile_fastmap (pbufp); + + /* If the search isn't to be a backwards one, don't waste time in a + long search for a pattern that says it is anchored. */ + if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf + && range > 0) + { + if (startpos > 0) + return -1; + else + range = 1; + } + + while (1) + { + /* If a fastmap is supplied, skip quickly over characters that + cannot possibly be the start of a match. Note, however, that + if the pattern can possibly match the null string, we must + test it at each starting point so that we take the first null + string we get. */ + + if (fastmap && startpos < total_size && pbufp->can_be_null != 1) + { + if (range > 0) /* Searching forwards. */ + { + register int lim = 0; + register unsigned char *p; + int irange = range; + if (startpos < size1 && startpos + range >= size1) + lim = range - (size1 - startpos); + + p = ((unsigned char *) + &(startpos >= size1 ? string2 - size1 : string1)[startpos]); + + while (range > lim && !fastmap[translate + ? translate[*p++] + : *p++]) + range--; + startpos += irange - range; + } + else /* Searching backwards. */ + { + register unsigned char c; + + if (string1 == 0 || startpos >= size1) + c = string2[startpos - size1]; + else + c = string1[startpos]; + + c &= 0xff; + if (translate ? !fastmap[translate[c]] : !fastmap[c]) + goto advance; + } + } + + if (range >= 0 && startpos == total_size + && fastmap && pbufp->can_be_null == 0) + return -1; + + val = re_match_2 (pbufp, string1, size1, string2, size2, startpos, + regs, mstop); + if (val >= 0) + return startpos; + if (val == -2) + return -2; + +#ifndef NO_ALLOCA +#ifdef C_ALLOCA + alloca (0); +#endif /* C_ALLOCA */ + +#endif /* NO_ALLOCA */ + advance: + if (!range) + break; + else if (range > 0) + { + range--; + startpos++; + } + else + { + range++; + startpos--; + } + } + return -1; +} + + + +#ifndef emacs /* emacs never uses this. */ +int +re_match (pbufp, string, size, pos, regs) + struct re_pattern_buffer *pbufp; + char *string; + int size, pos; + struct re_registers *regs; +{ + return re_match_2 (pbufp, (char *) 0, 0, string, size, pos, regs, size); +} +#endif /* not emacs */ + + +/* The following are used for re_match_2, defined below: */ + +/* Roughly the maximum number of failure points on the stack. Would be + exactly that if always pushed MAX_NUM_FAILURE_ITEMS each time we failed. */ + +int re_max_failures = 2000; + +/* Routine used by re_match_2. */ +/* static int memcmp_translate (); *//* already declared */ + + +/* Structure and accessing macros used in re_match_2: */ + +struct register_info +{ + unsigned is_active : 1; + unsigned matched_something : 1; +}; + +#define IS_ACTIVE(R) ((R).is_active) +#define MATCHED_SOMETHING(R) ((R).matched_something) + + +/* Macros used by re_match_2: */ + + +/* I.e., regstart, regend, and reg_info. */ + +#define NUM_REG_ITEMS 3 + +/* We push at most this many things on the stack whenever we + fail. The `+ 2' refers to PATTERN_PLACE and STRING_PLACE, which are + arguments to the PUSH_FAILURE_POINT macro. */ + +#define MAX_NUM_FAILURE_ITEMS (RE_NREGS * NUM_REG_ITEMS + 2) + + +/* We push this many things on the stack whenever we fail. */ + +#define NUM_FAILURE_ITEMS (last_used_reg * NUM_REG_ITEMS + 2) + + +/* This pushes most of the information about the current state we will want + if we ever fail back to it. */ + +#define PUSH_FAILURE_POINT(pattern_place, string_place) \ + { \ + long last_used_reg, this_reg; \ + \ + /* Find out how many registers are active or have been matched. \ + (Aside from register zero, which is only set at the end.) */ \ + for (last_used_reg = RE_NREGS - 1; last_used_reg > 0; last_used_reg--)\ + if (regstart[last_used_reg] != (unsigned char *)(-1L)) \ + break; \ + \ + if (stacke - stackp < NUM_FAILURE_ITEMS) \ + { \ + unsigned char **stackx; \ + unsigned int len = stacke - stackb; \ + if (len > re_max_failures * MAX_NUM_FAILURE_ITEMS) \ + { \ + FREE_AND_RETURN(stackb,(-2)); \ + } \ + \ + /* Roughly double the size of the stack. */ \ + stackx = DOUBLE_STACK(stackx,stackb,len); \ + /* Rearrange the pointers. */ \ + stackp = stackx + (stackp - stackb); \ + stackb = stackx; \ + stacke = stackb + 2 * len; \ + } \ + \ + /* Now push the info for each of those registers. */ \ + for (this_reg = 1; this_reg <= last_used_reg; this_reg++) \ + { \ + *stackp++ = regstart[this_reg]; \ + *stackp++ = regend[this_reg]; \ + *stackp++ = (unsigned char *) ®_info[this_reg]; \ + } \ + \ + /* Push how many registers we saved. */ \ + *stackp++ = (unsigned char *) last_used_reg; \ + \ + *stackp++ = pattern_place; \ + *stackp++ = string_place; \ + } + + +/* This pops what PUSH_FAILURE_POINT pushes. */ + +#define POP_FAILURE_POINT() \ + { \ + int temp; \ + stackp -= 2; /* Remove failure points. */ \ + temp = (int) *--stackp; /* How many regs pushed. */ \ + temp *= NUM_REG_ITEMS; /* How much to take off the stack. */ \ + stackp -= temp; /* Remove the register info. */ \ + } + + +#define MATCHING_IN_FIRST_STRING (dend == end_match_1) + +/* Is true if there is a first string and if PTR is pointing anywhere + inside it or just past the end. */ + +#define IS_IN_FIRST_STRING(ptr) \ + (size1 && string1 <= (ptr) && (ptr) <= string1 + size1) + +/* Call before fetching a character with *d. This switches over to + string2 if necessary. */ + +#define PREFETCH \ + while (d == dend) \ + { \ + /* end of string2 => fail. */ \ + if (dend == end_match_2) \ + goto fail; \ + /* end of string1 => advance to string2. */ \ + d = string2; \ + dend = end_match_2; \ + } + + +/* Call this when have matched something; it sets `matched' flags for the + registers corresponding to the subexpressions of which we currently + are inside. */ +#define SET_REGS_MATCHED \ + { unsigned this_reg; \ + for (this_reg = 0; this_reg < RE_NREGS; this_reg++) \ + { \ + if (IS_ACTIVE(reg_info[this_reg])) \ + MATCHED_SOMETHING(reg_info[this_reg]) = 1; \ + else \ + MATCHED_SOMETHING(reg_info[this_reg]) = 0; \ + } \ + } + +/* Test if at very beginning or at very end of the virtual concatenation + of string1 and string2. If there is only one string, we've put it in + string2. */ + +#define AT_STRINGS_BEG (d == (size1 ? string1 : string2) || !size2) +#define AT_STRINGS_END (d == end2) + +#define AT_WORD_BOUNDARY \ + (AT_STRINGS_BEG || AT_STRINGS_END || IS_A_LETTER (d - 1) != IS_A_LETTER (d)) + +/* We have two special cases to check for: + 1) if we're past the end of string1, we have to look at the first + character in string2; + 2) if we're before the beginning of string2, we have to look at the + last character in string1; we assume there is a string1, so use + this in conjunction with AT_STRINGS_BEG. */ +#define IS_A_LETTER(d) \ + (SYNTAX ((d) == end1 ? *string2 : (d) == string2 - 1 ? *(end1 - 1) : *(d))\ + == Sword) + + +/* Match the pattern described by PBUFP against the virtual + concatenation of STRING1 and STRING2, which are of SIZE1 and SIZE2, + respectively. Start the match at index POS in the virtual + concatenation of STRING1 and STRING2. In REGS, return the indices of + the virtual concatenation of STRING1 and STRING2 that matched the + entire PBUFP->buffer and its contained subexpressions. Do not + consider matching one past the index MSTOP in the virtual + concatenation of STRING1 and STRING2. + + If pbufp->fastmap is nonzero, then it had better be up to date. + + The reason that the data to match are specified as two components + which are to be regarded as concatenated is so this function can be + used directly on the contents of an Emacs buffer. + + -1 is returned if there is no match. -2 is returned if there is an + error (such as match stack overflow). Otherwise the value is the + length of the substring which was matched. */ + +int +re_match_2 (pbufp, string1_arg, size1, string2_arg, size2, pos, regs, mstop) + struct re_pattern_buffer *pbufp; + char *string1_arg, *string2_arg; + int size1, size2; + int pos; + struct re_registers *regs; + int mstop; +{ + register unsigned char *p = (unsigned char *) pbufp->buffer; + + /* Pointer to beyond end of buffer. */ + register unsigned char *pend = p + pbufp->used; + + unsigned char *string1 = (unsigned char *) string1_arg; + unsigned char *string2 = (unsigned char *) string2_arg; + unsigned char *end1; /* Just past end of first string. */ + unsigned char *end2; /* Just past end of second string. */ + + /* Pointers into string1 and string2, just past the last characters in + each to consider matching. */ + unsigned char *end_match_1, *end_match_2; + + register unsigned char *d, *dend; + register int mcnt; /* Multipurpose. */ + unsigned char *translate = (unsigned char *) pbufp->translate; + unsigned is_a_jump_n = 0; + + /* Failure point stack. Each place that can handle a failure further + down the line pushes a failure point on this stack. It consists of + restart, regend, and reg_info for all registers corresponding to the + subexpressions we're currently inside, plus the number of such + registers, and, finally, two char *'s. The first char * is where to + resume scanning the pattern; the second one is where to resume + scanning the strings. If the latter is zero, the failure point is a + ``dummy''; if a failure happens and the failure point is a dummy, it + gets discarded and the next next one is tried. */ + +#ifndef NO_ALLOCA + unsigned char *initial_stack[MAX_NUM_FAILURE_ITEMS * NFAILURES]; +#endif + unsigned char **stackb; + unsigned char **stackp; + unsigned char **stacke; + + + /* Information on the contents of registers. These are pointers into + the input strings; they record just what was matched (on this + attempt) by a subexpression part of the pattern, that is, the + regnum-th regstart pointer points to where in the pattern we began + matching and the regnum-th regend points to right after where we + stopped matching the regnum-th subexpression. (The zeroth register + keeps track of what the whole pattern matches.) */ + + unsigned char *regstart[RE_NREGS]; + unsigned char *regend[RE_NREGS]; + + /* The is_active field of reg_info helps us keep track of which (possibly + nested) subexpressions we are currently in. The matched_something + field of reg_info[reg_num] helps us tell whether or not we have + matched any of the pattern so far this time through the reg_num-th + subexpression. These two fields get reset each time through any + loop their register is in. */ + + struct register_info reg_info[RE_NREGS]; + + + /* The following record the register info as found in the above + variables when we find a match better than any we've seen before. + This happens as we backtrack through the failure points, which in + turn happens only if we have not yet matched the entire string. */ + + unsigned best_regs_set = 0; + unsigned char *best_regstart[RE_NREGS]; + unsigned char *best_regend[RE_NREGS]; + + /* Initialize the stack. */ +#ifdef NO_ALLOCA + stackb = (unsigned char **) malloc (MAX_NUM_FAILURE_ITEMS * NFAILURES * sizeof (char *)); +#else + stackb = initial_stack; +#endif + stackp = stackb; + stacke = &stackb[MAX_NUM_FAILURE_ITEMS * NFAILURES]; + +#ifdef DEBUG_REGEX + fprintf (stderr, "Entering re_match_2(%s%s)\n", string1_arg, string2_arg); +#endif + + /* Initialize subexpression text positions to -1 to mark ones that no + \( or ( and \) or ) has been seen for. Also set all registers to + inactive and mark them as not having matched anything or ever + failed. */ + for (mcnt = 0; mcnt < RE_NREGS; mcnt++) + { + regstart[mcnt] = regend[mcnt] = (unsigned char *) (-1L); + IS_ACTIVE (reg_info[mcnt]) = 0; + MATCHED_SOMETHING (reg_info[mcnt]) = 0; + } + + if (regs) + for (mcnt = 0; mcnt < RE_NREGS; mcnt++) + regs->start[mcnt] = regs->end[mcnt] = -1; + + /* Set up pointers to ends of strings. + Don't allow the second string to be empty unless both are empty. */ + if (size2 == 0) + { + string2 = string1; + size2 = size1; + string1 = 0; + size1 = 0; + } + end1 = string1 + size1; + end2 = string2 + size2; + + /* Compute where to stop matching, within the two strings. */ + if (mstop <= size1) + { + end_match_1 = string1 + mstop; + end_match_2 = string2; + } + else + { + end_match_1 = end1; + end_match_2 = string2 + mstop - size1; + } + + /* `p' scans through the pattern as `d' scans through the data. `dend' + is the end of the input string that `d' points within. `d' is + advanced into the following input string whenever necessary, but + this happens before fetching; therefore, at the beginning of the + loop, `d' can be pointing at the end of a string, but it cannot + equal string2. */ + + if (size1 != 0 && pos <= size1) + d = string1 + pos, dend = end_match_1; + else + d = string2 + pos - size1, dend = end_match_2; + + + /* This loops over pattern commands. It exits by returning from the + function if match is complete, or it drops through if match fails + at this starting point in the input data. */ + + while (1) + { +#ifdef DEBUG_REGEX + fprintf (stderr, + "regex loop(%d): matching 0x%02d\n", + p - (unsigned char *) pbufp->buffer, + *p); +#endif + is_a_jump_n = 0; + /* End of pattern means we might have succeeded. */ + if (p == pend) + { + /* If not end of string, try backtracking. Otherwise done. */ + if (d != end_match_2) + { + if (stackp != stackb) + { + /* More failure points to try. */ + + unsigned in_same_string = + IS_IN_FIRST_STRING (best_regend[0]) + == MATCHING_IN_FIRST_STRING; + + /* If exceeds best match so far, save it. */ + if (! best_regs_set + || (in_same_string && d > best_regend[0]) + || (! in_same_string && ! MATCHING_IN_FIRST_STRING)) + { + best_regs_set = 1; + best_regend[0] = d; /* Never use regstart[0]. */ + + for (mcnt = 1; mcnt < RE_NREGS; mcnt++) + { + best_regstart[mcnt] = regstart[mcnt]; + best_regend[mcnt] = regend[mcnt]; + } + } + goto fail; + } + /* If no failure points, don't restore garbage. */ + else if (best_regs_set) + { + restore_best_regs: + /* Restore best match. */ + d = best_regend[0]; + + for (mcnt = 0; mcnt < RE_NREGS; mcnt++) + { + regstart[mcnt] = best_regstart[mcnt]; + regend[mcnt] = best_regend[mcnt]; + } + } + } + + /* If caller wants register contents data back, convert it + to indices. */ + if (regs) + { + regs->start[0] = pos; + if (MATCHING_IN_FIRST_STRING) + regs->end[0] = d - string1; + else + regs->end[0] = d - string2 + size1; + for (mcnt = 1; mcnt < RE_NREGS; mcnt++) + { + if (regend[mcnt] == (unsigned char *)(-1L)) + { + regs->start[mcnt] = -1; + regs->end[mcnt] = -1; + continue; + } + if (IS_IN_FIRST_STRING (regstart[mcnt])) + regs->start[mcnt] = regstart[mcnt] - string1; + else + regs->start[mcnt] = regstart[mcnt] - string2 + size1; + + if (IS_IN_FIRST_STRING (regend[mcnt])) + regs->end[mcnt] = regend[mcnt] - string1; + else + regs->end[mcnt] = regend[mcnt] - string2 + size1; + } + } + FREE_AND_RETURN(stackb, + (d - pos - (MATCHING_IN_FIRST_STRING ? + string1 : + string2 - size1))); + } + + /* Otherwise match next pattern command. */ +#ifdef SWITCH_ENUM_BUG + switch ((int) ((enum regexpcode) *p++)) +#else + switch ((enum regexpcode) *p++) +#endif + { + + /* \( [or `(', as appropriate] is represented by start_memory, + \) by stop_memory. Both of those commands are followed by + a register number in the next byte. The text matched + within the \( and \) is recorded under that number. */ + case start_memory: + regstart[*p] = d; + IS_ACTIVE (reg_info[*p]) = 1; + MATCHED_SOMETHING (reg_info[*p]) = 0; + p++; + break; + + case stop_memory: + regend[*p] = d; + IS_ACTIVE (reg_info[*p]) = 0; + + /* If just failed to match something this time around with a sub- + expression that's in a loop, try to force exit from the loop. */ + if ((! MATCHED_SOMETHING (reg_info[*p]) + || (enum regexpcode) p[-3] == start_memory) + && (p + 1) != pend) + { + register unsigned char *p2 = p + 1; + mcnt = 0; + switch (*p2++) + { + case jump_n: + is_a_jump_n = 1; + case finalize_jump: + case maybe_finalize_jump: + case jump: + case dummy_failure_jump: + EXTRACT_NUMBER_AND_INCR (mcnt, p2); + if (is_a_jump_n) + p2 += 2; + break; + } + p2 += mcnt; + + /* If the next operation is a jump backwards in the pattern + to an on_failure_jump, exit from the loop by forcing a + failure after pushing on the stack the on_failure_jump's + jump in the pattern, and d. */ + if (mcnt < 0 && (enum regexpcode) *p2++ == on_failure_jump) + { + EXTRACT_NUMBER_AND_INCR (mcnt, p2); + PUSH_FAILURE_POINT (p2 + mcnt, d); + goto fail; + } + } + p++; + break; + + /* \<digit> has been turned into a `duplicate' command which is + followed by the numeric value of <digit> as the register number. */ + case duplicate: + { + int regno = *p++; /* Get which register to match against */ + register unsigned char *d2, *dend2; + + /* Where in input to try to start matching. */ + d2 = regstart[regno]; + + /* Where to stop matching; if both the place to start and + the place to stop matching are in the same string, then + set to the place to stop, otherwise, for now have to use + the end of the first string. */ + + dend2 = ((IS_IN_FIRST_STRING (regstart[regno]) + == IS_IN_FIRST_STRING (regend[regno])) + ? regend[regno] : end_match_1); + while (1) + { + /* If necessary, advance to next segment in register + contents. */ + while (d2 == dend2) + { + if (dend2 == end_match_2) break; + if (dend2 == regend[regno]) break; + d2 = string2, dend2 = regend[regno]; /* end of string1 => advance to string2. */ + } + /* At end of register contents => success */ + if (d2 == dend2) break; + + /* If necessary, advance to next segment in data. */ + PREFETCH; + + /* How many characters left in this segment to match. */ + mcnt = dend - d; + + /* Want how many consecutive characters we can match in + one shot, so, if necessary, adjust the count. */ + if (mcnt > dend2 - d2) + mcnt = dend2 - d2; + + /* Compare that many; failure if mismatch, else move + past them. */ + if (translate + ? memcmp_translate (d, d2, mcnt, translate) + : memcmp ((char *)d, (char *)d2, mcnt)) + goto fail; + d += mcnt, d2 += mcnt; + } + } + break; + + case anychar: + PREFETCH; /* Fetch a data character. */ + /* Match anything but a newline, maybe even a null. */ + if ((translate ? translate[*d] : *d) == '\n' + || ((obscure_syntax & RE_DOT_NOT_NULL) + && (translate ? translate[*d] : *d) == '\000')) + goto fail; + SET_REGS_MATCHED; + d++; + break; + + case charset: + case charset_not: + { + int not = 0; /* Nonzero for charset_not. */ + register int c; + if (*(p - 1) == (unsigned char) charset_not) + not = 1; + + PREFETCH; /* Fetch a data character. */ + + if (translate) + c = translate[*d]; + else + c = *d; + + if (c < *p * BYTEWIDTH + && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) + not = !not; + + p += 1 + *p; + + if (!not) goto fail; + SET_REGS_MATCHED; + d++; + break; + } + + case begline: + if ((size1 != 0 && d == string1) + || (size1 == 0 && size2 != 0 && d == string2) + || (d && d[-1] == '\n') + || (size1 == 0 && size2 == 0)) + break; + else + goto fail; + + case endline: + if (d == end2 + || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n')) + break; + goto fail; + + /* `or' constructs are handled by starting each alternative with + an on_failure_jump that points to the start of the next + alternative. Each alternative except the last ends with a + jump to the joining point. (Actually, each jump except for + the last one really jumps to the following jump, because + tensioning the jumps is a hassle.) */ + + /* The start of a stupid repeat has an on_failure_jump that points + past the end of the repeat text. This makes a failure point so + that on failure to match a repetition, matching restarts past + as many repetitions have been found with no way to fail and + look for another one. */ + + /* A smart repeat is similar but loops back to the on_failure_jump + so that each repetition makes another failure point. */ + + case on_failure_jump: + on_failure: + EXTRACT_NUMBER_AND_INCR (mcnt, p); + PUSH_FAILURE_POINT (p + mcnt, d); + break; + + /* The end of a smart repeat has a maybe_finalize_jump back. + Change it either to a finalize_jump or an ordinary jump. */ + case maybe_finalize_jump: + EXTRACT_NUMBER_AND_INCR (mcnt, p); + { + register unsigned char *p2 = p; + /* Compare what follows with the beginning of the repeat. + If we can establish that there is nothing that they would + both match, we can change to finalize_jump. */ + while (p2 + 1 != pend + && (*p2 == (unsigned char) stop_memory + || *p2 == (unsigned char) start_memory)) + p2 += 2; /* Skip over reg number. */ + if (p2 == pend) + p[-3] = (unsigned char) finalize_jump; + else if (*p2 == (unsigned char) exactn + || *p2 == (unsigned char) endline) + { + register int c = *p2 == (unsigned char) endline ? '\n' : p2[2]; + register unsigned char *p1 = p + mcnt; + /* p1[0] ... p1[2] are an on_failure_jump. + Examine what follows that. */ + if (p1[3] == (unsigned char) exactn && p1[5] != c) + p[-3] = (unsigned char) finalize_jump; + else if (p1[3] == (unsigned char) charset + || p1[3] == (unsigned char) charset_not) + { + int not = p1[3] == (unsigned char) charset_not; + if (c < p1[4] * BYTEWIDTH + && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) + not = !not; + /* `not' is 1 if c would match. */ + /* That means it is not safe to finalize. */ + if (!not) + p[-3] = (unsigned char) finalize_jump; + } + } + } + p -= 2; /* Point at relative address again. */ + if (p[-1] != (unsigned char) finalize_jump) + { + p[-1] = (unsigned char) jump; + goto nofinalize; + } + /* Note fall through. */ + + /* The end of a stupid repeat has a finalize_jump back to the + start, where another failure point will be made which will + point to after all the repetitions found so far. */ + + /* Take off failure points put on by matching on_failure_jump + because didn't fail. Also remove the register information + put on by the on_failure_jump. */ + case finalize_jump: + POP_FAILURE_POINT (); + /* Note fall through. */ + + /* Jump without taking off any failure points. */ + case jump: + nofinalize: + EXTRACT_NUMBER_AND_INCR (mcnt, p); + p += mcnt; + break; + + case dummy_failure_jump: + /* Normally, the on_failure_jump pushes a failure point, which + then gets popped at finalize_jump. We will end up at + finalize_jump, also, and with a pattern of, say, `a+', we + are skipping over the on_failure_jump, so we have to push + something meaningless for finalize_jump to pop. */ + PUSH_FAILURE_POINT (0, 0); + goto nofinalize; + + + /* Have to succeed matching what follows at least n times. Then + just handle like an on_failure_jump. */ + case succeed_n: + EXTRACT_NUMBER (mcnt, p + 2); + /* Originally, this is how many times we HAVE to succeed. */ + if (mcnt) + { + mcnt--; + p += 2; + STORE_NUMBER_AND_INCR (p, mcnt); + } + else if (mcnt == 0) + { + p[2] = unused; + p[3] = unused; + goto on_failure; + } + else + { + fprintf (stderr, "regex: the succeed_n's n is not set.\n"); + exit (1); + } + break; + + case jump_n: + EXTRACT_NUMBER (mcnt, p + 2); + /* Originally, this is how many times we CAN jump. */ + if (mcnt) + { + mcnt--; + STORE_NUMBER(p + 2, mcnt); + goto nofinalize; /* Do the jump without taking off + any failure points. */ + } + /* If don't have to jump any more, skip over the rest of command. */ + else + p += 4; + break; + + case set_number_at: + { + register unsigned char *p1; + + EXTRACT_NUMBER_AND_INCR (mcnt, p); + p1 = p + mcnt; + EXTRACT_NUMBER_AND_INCR (mcnt, p); + STORE_NUMBER (p1, mcnt); + break; + } + + /* Ignore these. Used to ignore the n of succeed_n's which + currently have n == 0. */ + case unused: + break; + + case wordbound: + if (AT_WORD_BOUNDARY) + break; + goto fail; + + case notwordbound: + if (AT_WORD_BOUNDARY) + goto fail; + break; + + case wordbeg: + if (IS_A_LETTER (d) && (!IS_A_LETTER (d - 1) || AT_STRINGS_BEG)) + break; + goto fail; + + case wordend: + /* Have to check if AT_STRINGS_BEG before looking at d - 1. */ + if (!AT_STRINGS_BEG && IS_A_LETTER (d - 1) + && (!IS_A_LETTER (d) || AT_STRINGS_END)) + break; + goto fail; + +#ifdef emacs + case before_dot: + if (PTR_CHAR_POS (d) >= point) + goto fail; + break; + + case at_dot: + if (PTR_CHAR_POS (d) != point) + goto fail; + break; + + case after_dot: + if (PTR_CHAR_POS (d) <= point) + goto fail; + break; + + case wordchar: + mcnt = (int) Sword; + goto matchsyntax; + + case syntaxspec: + mcnt = *p++; + matchsyntax: + PREFETCH; + if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail; + SET_REGS_MATCHED; + break; + + case notwordchar: + mcnt = (int) Sword; + goto matchnotsyntax; + + case notsyntaxspec: + mcnt = *p++; + matchnotsyntax: + PREFETCH; + if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail; + SET_REGS_MATCHED; + break; + +#else /* not emacs */ + + case wordchar: + PREFETCH; + if (!IS_A_LETTER (d)) + goto fail; + SET_REGS_MATCHED; + break; + + case notwordchar: + PREFETCH; + if (IS_A_LETTER (d)) + goto fail; + SET_REGS_MATCHED; + break; + + case before_dot: + case at_dot: + case after_dot: + case syntaxspec: + case notsyntaxspec: + break; + +#endif /* not emacs */ + + case begbuf: + if (AT_STRINGS_BEG) + break; + goto fail; + + case endbuf: + if (AT_STRINGS_END) + break; + goto fail; + + case exactn: + /* Match the next few pattern characters exactly. + mcnt is how many characters to match. */ + mcnt = *p++; + /* This is written out as an if-else so we don't waste time + testing `translate' inside the loop. */ + if (translate) + { + do + { + PREFETCH; + if (translate[*d++] != *p++) goto fail; + } + while (--mcnt); + } + else + { + do + { + PREFETCH; + if (*d++ != *p++) goto fail; + } + while (--mcnt); + } + SET_REGS_MATCHED; + break; + } + continue; /* Successfully executed one pattern command; keep going. */ + + /* Jump here if any matching operation fails. */ + fail: + if (stackp != stackb) + /* A restart point is known. Restart there and pop it. */ + { + short last_used_reg, this_reg; + + /* If this failure point is from a dummy_failure_point, just + skip it. */ + if (!stackp[-2]) + { + POP_FAILURE_POINT (); + goto fail; + } + + d = *--stackp; + p = *--stackp; + if (d >= string1 && d <= end1) + dend = end_match_1; + /* Restore register info. */ + last_used_reg = (long) *--stackp; + + /* Make the ones that weren't saved -1 or 0 again. */ + for (this_reg = RE_NREGS - 1; this_reg > last_used_reg; this_reg--) + { + regend[this_reg] = (unsigned char *) (-1L); + regstart[this_reg] = (unsigned char *) (-1L); + IS_ACTIVE (reg_info[this_reg]) = 0; + MATCHED_SOMETHING (reg_info[this_reg]) = 0; + } + + /* And restore the rest from the stack. */ + for ( ; this_reg > 0; this_reg--) + { + reg_info[this_reg] = *(struct register_info *) *--stackp; + regend[this_reg] = *--stackp; + regstart[this_reg] = *--stackp; + } + } + else + break; /* Matching at this starting point really fails. */ + } + + if (best_regs_set) + goto restore_best_regs; + + FREE_AND_RETURN(stackb,(-1)); /* Failure to match. */ +} + + +static int +memcmp_translate (s1, s2, len, translate) + unsigned char *s1, *s2; + register int len; + unsigned char *translate; +{ + register unsigned char *p1 = s1, *p2 = s2; + while (len) + { + if (translate [*p1++] != translate [*p2++]) return 1; + len--; + } + return 0; +} + + + +/* Entry points compatible with 4.2 BSD regex library. */ + +#if !defined(emacs) && !defined(GAWK) + +static struct re_pattern_buffer re_comp_buf; + +char * +re_comp (s) + char *s; +{ + if (!s) + { + if (!re_comp_buf.buffer) + return "No previous regular expression"; + return 0; + } + + if (!re_comp_buf.buffer) + { + if (!(re_comp_buf.buffer = (char *) malloc (200))) + return "Memory exhausted"; + re_comp_buf.allocated = 200; + if (!(re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH))) + return "Memory exhausted"; + } + return re_compile_pattern (s, strlen (s), &re_comp_buf); +} + +int +re_exec (s) + char *s; +{ + int len = strlen (s); + return 0 <= re_search (&re_comp_buf, s, len, 0, len, + (struct re_registers *) 0); +} +#endif /* not emacs && not GAWK */ + + + +#ifdef test + +#ifdef atarist +long _stksize = 2L; /* reserve memory for stack */ +#endif +#include <stdio.h> + +/* Indexed by a character, gives the upper case equivalent of the + character. */ + +char upcase[0400] = + { 000, 001, 002, 003, 004, 005, 006, 007, + 010, 011, 012, 013, 014, 015, 016, 017, + 020, 021, 022, 023, 024, 025, 026, 027, + 030, 031, 032, 033, 034, 035, 036, 037, + 040, 041, 042, 043, 044, 045, 046, 047, + 050, 051, 052, 053, 054, 055, 056, 057, + 060, 061, 062, 063, 064, 065, 066, 067, + 070, 071, 072, 073, 074, 075, 076, 077, + 0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107, + 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, + 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, + 0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137, + 0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107, + 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, + 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, + 0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177, + 0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207, + 0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217, + 0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227, + 0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237, + 0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247, + 0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257, + 0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267, + 0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277, + 0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307, + 0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317, + 0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327, + 0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337, + 0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347, + 0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357, + 0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367, + 0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377 + }; + +#ifdef canned + +#include "tests.h" + +typedef enum { extended_test, basic_test } test_type; + +/* Use this to run the tests we've thought of. */ + +void +main () +{ + test_type t = extended_test; + + if (t == basic_test) + { + printf ("Running basic tests:\n\n"); + test_posix_basic (); + } + else if (t == extended_test) + { + printf ("Running extended tests:\n\n"); + test_posix_extended (); + } +} + +#else /* not canned */ + +/* Use this to run interactive tests. */ + +void +main (argc, argv) + int argc; + char **argv; +{ + char pat[80]; + struct re_pattern_buffer buf; + int i; + char c; + char fastmap[(1 << BYTEWIDTH)]; + + /* Allow a command argument to specify the style of syntax. */ + if (argc > 1) + obscure_syntax = atol (argv[1]); + + buf.allocated = 40; + buf.buffer = (char *) malloc (buf.allocated); + buf.fastmap = fastmap; + buf.translate = upcase; + + while (1) + { + gets (pat); + + if (*pat) + { + re_compile_pattern (pat, strlen(pat), &buf); + + for (i = 0; i < buf.used; i++) + printchar (buf.buffer[i]); + + putchar ('\n'); + + printf ("%d allocated, %d used.\n", buf.allocated, buf.used); + + re_compile_fastmap (&buf); + printf ("Allowed by fastmap: "); + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (fastmap[i]) printchar (i); + putchar ('\n'); + } + + gets (pat); /* Now read the string to match against */ + + i = re_match (&buf, pat, strlen (pat), 0, 0); + printf ("Match value %d.\n", i); + } +} + +#endif + + +#ifdef NOTDEF +print_buf (bufp) + struct re_pattern_buffer *bufp; +{ + int i; + + printf ("buf is :\n----------------\n"); + for (i = 0; i < bufp->used; i++) + printchar (bufp->buffer[i]); + + printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used); + + printf ("Allowed by fastmap: "); + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (bufp->fastmap[i]) + printchar (i); + printf ("\nAllowed by translate: "); + if (bufp->translate) + for (i = 0; i < (1 << BYTEWIDTH); i++) + if (bufp->translate[i]) + printchar (i); + printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't"); + printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not"); +} +#endif /* NOTDEF */ + +printchar (c) + char c; +{ + if (c < 040 || c >= 0177) + { + putchar ('\\'); + putchar (((c >> 6) & 3) + '0'); + putchar (((c >> 3) & 7) + '0'); + putchar ((c & 7) + '0'); + } + else + putchar (c); +} + +error (string) + char *string; +{ + puts (string); + exit (1); +} +#endif /* test */ |