USA. */
/* TODO:
- - detect nasty infinite loops like "\\(\\)+?ab" when matching "ac".
- - use `keep_string' more often than just .*\n.
- structure the opcode space into opcode+flag.
- - merge with glic's regex.[ch]
-
- That's it for now -sm */
+ - merge with glibc's regex.[ch]
+ */
/* AIX requires this to be the first thing in the file. */
#if defined (_AIX) && !defined (REGEX_MALLOC)
#ifdef emacs
/* Converts the pointer to the char to BEG-based offset from the start. */
-#define PTR_TO_OFFSET(d) \
- POS_AS_IN_BUFFER (MATCHING_IN_FIRST_STRING \
- ? (d) - string1 : (d) - (string2 - size1))
+#define PTR_TO_OFFSET(d) POS_AS_IN_BUFFER (POINTER_TO_OFFSET (d))
#define POS_AS_IN_BUFFER(p) ((p) + (NILP (re_match_object) || BUFFERP (re_match_object)))
-#else
-#define PTR_TO_OFFSET(d) 0
#endif
#ifdef HAVE_CONFIG_H
#define realloc xrealloc
#define free xfree
+#define RE_MULTIBYTE_P(bufp) ((bufp)->multibyte)
+#define RE_STRING_CHAR(p, s) \
+ (multibyte ? (STRING_CHAR (p, s)) : (*(p)))
+#define RE_STRING_CHAR_AND_LENGTH(p, s, len) \
+ (multibyte ? (STRING_CHAR_AND_LENGTH (p, s, len)) : ((len) = 1, *(p)))
+
+/* Set C a (possibly multibyte) character before P. P points into a
+ string which is the virtual concatenation of STR1 (which ends at
+ END1) or STR2 (which ends at END2). */
+#define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
+ do { \
+ if (multibyte) \
+ { \
+ re_char *dtemp = (p) == (str2) ? (end1) : (p); \
+ re_char *dlimit = ((p) > (str2) && (p) <= (end2)) ? (str2) : (str1); \
+ while (dtemp-- > dlimit && !CHAR_HEAD_P (*dtemp)); \
+ c = STRING_CHAR (dtemp, (p) - dtemp); \
+ } \
+ else \
+ (c = ((p) == (str2) ? (end1) : (p))[-1]); \
+ } while (0)
+
+
#else /* not emacs */
/* If we are not linking with Emacs proper,
/* Define the syntax stuff for \<, \>, etc. */
-/* This must be nonzero for the wordchar and notwordchar pattern
- commands in re_match_2. */
-#ifndef Sword
-#define Sword 1
-#endif
+/* Sword must be nonzero for the wordchar pattern commands in re_match_2. */
+enum syntaxcode { Swhitespace = 0, Sword = 1 };
#ifdef SWITCH_ENUM_BUG
#define SWITCH_ENUM_CAST(x) ((int)(x))
/* Dummy macros for non-Emacs environments. */
#define BASE_LEADING_CODE_P(c) (0)
+#define CHAR_CHARSET(c) 0
+#define CHARSET_LEADING_CODE_BASE(c) 0
+#define MAX_MULTIBYTE_LENGTH 1
+#define RE_MULTIBYTE_P(x) 0
#define WORD_BOUNDARY_P(c1, c2) (0)
#define CHAR_HEAD_P(p) (1)
#define SINGLE_BYTE_CHAR_P(c) (1)
#define SAME_CHARSET_P(c1, c2) (1)
#define MULTIBYTE_FORM_LENGTH(p, s) (1)
#define STRING_CHAR(p, s) (*(p))
+#define RE_STRING_CHAR STRING_CHAR
+#define CHAR_STRING(c, s) (*(s) = (c), 1)
#define STRING_CHAR_AND_LENGTH(p, s, actual_len) ((actual_len) = 1, *(p))
-#define GET_CHAR_AFTER_2(c, p, str1, end1, str2, end2) \
- (c = ((p) == (end1) ? *(str2) : *(p)))
+#define RE_STRING_CHAR_AND_LENGTH STRING_CHAR_AND_LENGTH
#define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
(c = ((p) == (str2) ? *((end1) - 1) : *((p) - 1)))
+#define MAKE_CHAR(charset, c1, c2) (c1)
#endif /* not emacs */
+
+#ifndef RE_TRANSLATE
+#define RE_TRANSLATE(TBL, C) ((unsigned char)(TBL)[C])
+#define RE_TRANSLATE_P(TBL) (TBL)
+#endif
\f
/* Get the interface, including the syntax bits. */
#include "regex.h"
#define REGEX_REALLOCATE_STACK(source, osize, nsize) \
REGEX_REALLOCATE (source, osize, nsize)
/* No need to explicitly free anything. */
-#define REGEX_FREE_STACK(arg)
+#define REGEX_FREE_STACK(arg) ((void)0)
#endif /* not REGEX_MALLOC */
#endif /* not using relocating allocator */
current string position when executed. */
on_failure_keep_string_jump,
- /* Like `on_failure_jump', except that it assumes that the
- pattern following it is mutually exclusive with the pattern
- at the destination of the jump: if one matches something,
- the other won't match at all.
- Always used via `on_failure_jump_smart'. */
- on_failure_jump_exclusive,
-
/* Just like `on_failure_jump', except that it checks that we
don't get stuck in an infinite loop (matching an empty string
indefinitely). */
on_failure_jump_loop,
+ /* Just like `on_failure_jump_loop', except that it checks for
+ a different kind of loop (the kind that shows up with non-greedy
+ operators). This operation has to be immediately preceded
+ by a `no_op'. */
+ on_failure_jump_nastyloop,
+
/* A smart `on_failure_jump' used for greedy * and + operators.
It analyses the loop before which it is put and if the
loop does not require backtracking, it changes itself to
- `on_failure_jump_exclusive', else it just defaults to
- changing itself into `on_failure_jump_loop'. */
+ `on_failure_keep_string_jump' and short-circuits the loop,
+ else it just defaults to changing itself into `on_failure_jump'.
+ It assumes that it is pointing to just past a `jump'. */
on_failure_jump_smart,
/* Followed by two-byte relative address and two-byte number n.
- After matching N times, jump to the address upon failure. */
+ After matching N times, jump to the address upon failure.
+ Does not work if N starts at 0: use on_failure_jump_loop
+ instead. */
succeed_n,
/* Followed by two-byte relative address, and two-byte number n.
bytes of number. */
set_number_at,
- 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. */
-
-#ifdef emacs
- ,before_dot, /* Succeeds if before point. */
- at_dot, /* Succeeds if at point. */
- after_dot, /* Succeeds if after point. */
+ notwordbound, /* Succeeds if not at a word boundary. */
/* Matches any character whose syntax is specified. Followed by
a byte which contains a syntax code, e.g., Sword. */
syntaxspec,
/* Matches any character whose syntax is not that specified. */
- notsyntaxspec,
+ notsyntaxspec
+
+#ifdef emacs
+ ,before_dot, /* Succeeds if before point. */
+ at_dot, /* Succeeds if at point. */
+ after_dot, /* Succeeds if after point. */
/* Matches any character whose category-set contains the specified
category. The operator is followed by a byte which contains a
/* It is useful to test things that ``must'' be true when debugging. */
#include <assert.h>
-static int debug = 0;
+static int debug = -100000;
#define DEBUG_STATEMENT(e) e
-#define DEBUG_PRINT1(x) if (debug) printf (x)
-#define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
-#define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
-#define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
+#define DEBUG_PRINT1(x) if (debug > 0) printf (x)
+#define DEBUG_PRINT2(x1, x2) if (debug > 0) printf (x1, x2)
+#define DEBUG_PRINT3(x1, x2, x3) if (debug > 0) printf (x1, x2, x3)
+#define DEBUG_PRINT4(x1, x2, x3, x4) if (debug > 0) printf (x1, x2, x3, x4)
#define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
- if (debug) print_partial_compiled_pattern (s, e)
+ if (debug > 0) print_partial_compiled_pattern (s, e)
#define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
- if (debug) print_double_string (w, s1, sz1, s2, sz2)
+ if (debug > 0) print_double_string (w, s1, sz1, s2, sz2)
/* Print the fastmap in human-readable form. */
printf ("/no_op");
break;
+ case succeed:
+ printf ("/succeed");
+ break;
+
case exactn:
mcnt = *p++;
printf ("/exactn/%d", mcnt);
{
register int c, last = -100;
register int in_range = 0;
- int length = *p & 0x7f;
- int has_range_table = *p & 0x80;
- int range_length = p[length + 2] + p[length + 3] * 0x100;
+ int length = CHARSET_BITMAP_SIZE (p - 1);
+ int has_range_table = CHARSET_RANGE_TABLE_EXISTS_P (p - 1);
printf ("/charset [%s",
(re_opcode_t) *(p - 1) == charset_not ? "^" : "");
last = c;
}
- p += 1 + length;
-
if (in_range)
putchar (last);
putchar (']');
- if (has_range_table)
- printf ("has-range-table");
+ p += 1 + length;
- /* ??? Should print the range table; for now,
- just skip it. */
if (has_range_table)
- p += 4 + 6 * range_length;
+ {
+ int count;
+ printf ("has-range-table");
+
+ /* ??? Should print the range table; for now, just skip it. */
+ p += 2; /* skip range table bits */
+ EXTRACT_NUMBER_AND_INCR (count, p);
+ p = CHARSET_RANGE_TABLE_END (p, count);
+ }
}
break;
printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
break;
- case on_failure_jump_exclusive:
+ case on_failure_jump_nastyloop:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_jump_exclusive to %d", p + mcnt - start);
+ printf ("/on_failure_jump_nastyloop to %d", p + mcnt - start);
break;
case on_failure_jump_loop:
case succeed_n:
extract_number_and_incr (&mcnt, &p);
extract_number_and_incr (&mcnt2, &p);
- printf ("/succeed_n to %d, %d times", p + mcnt - start, mcnt2);
+ printf ("/succeed_n to %d, %d times", p - 2 + mcnt - start, mcnt2);
break;
case jump_n:
extract_number_and_incr (&mcnt, &p);
extract_number_and_incr (&mcnt2, &p);
- printf ("/jump_n to %d, %d times", p + mcnt - start, mcnt2);
+ printf ("/jump_n to %d, %d times", p - 2 + mcnt - start, mcnt2);
break;
case set_number_at:
extract_number_and_incr (&mcnt, &p);
extract_number_and_incr (&mcnt2, &p);
- printf ("/set_number_at location %d to %d", p + mcnt - start, mcnt2);
+ printf ("/set_number_at location %d to %d", p - 2 + mcnt - start, mcnt2);
break;
case wordbound:
case wordend:
printf ("/wordend");
+ case syntaxspec:
+ printf ("/syntaxspec");
+ mcnt = *p++;
+ printf ("/%d", mcnt);
+ break;
+
+ case notsyntaxspec:
+ printf ("/notsyntaxspec");
+ mcnt = *p++;
+ printf ("/%d", mcnt);
+ break;
+
#ifdef emacs
case before_dot:
printf ("/before_dot");
printf ("/after_dot");
break;
- case syntaxspec:
- printf ("/syntaxspec");
+ case categoryspec:
+ printf ("/categoryspec");
mcnt = *p++;
printf ("/%d", mcnt);
break;
- case notsyntaxspec:
- printf ("/notsyntaxspec");
+ case notcategoryspec:
+ printf ("/notcategoryspec");
mcnt = *p++;
printf ("/%d", mcnt);
break;
#endif /* emacs */
- case wordchar:
- printf ("/wordchar");
- break;
-
- case notwordchar:
- printf ("/notwordchar");
- break;
-
case begbuf:
printf ("/begbuf");
break;
fail_stack.frame = 0; \
} while (0)
-#define RESET_FAIL_STACK()
+#define RESET_FAIL_STACK() ((void)0)
#endif
\f
/* Subroutine declarations and macros for regex_compile. */
-static void store_op1 (), store_op2 ();
-static void insert_op1 (), insert_op2 ();
-static boolean at_begline_loc_p (), at_endline_loc_p ();
-static boolean group_in_compile_stack ();
+static void store_op1 _RE_ARGS((re_opcode_t op, unsigned char *loc, int arg));
+static void store_op2 _RE_ARGS((re_opcode_t op, unsigned char *loc,
+ int arg1, int arg2));
+static void insert_op1 _RE_ARGS((re_opcode_t op, unsigned char *loc,
+ int arg, unsigned char *end));
+static void insert_op2 _RE_ARGS((re_opcode_t op, unsigned char *loc,
+ int arg1, int arg2, unsigned char *end));
+static boolean at_begline_loc_p _RE_ARGS((const unsigned char *pattern,
+ const unsigned char *p,
+ reg_syntax_t syntax));
+static boolean at_endline_loc_p _RE_ARGS((const unsigned char *p,
+ const unsigned char *pend,
+ reg_syntax_t syntax));
+static unsigned char *skip_one_char _RE_ARGS((unsigned char *p));
+static int analyse_first _RE_ARGS((unsigned char *p, unsigned char *pend,
+ char *fastmap, const int multibyte));
/* Fetch the next character in the uncompiled pattern---translating it
if necessary. Also cast from a signed character in the constant
string passed to us by the user to an unsigned char that we can use
as an array index (in, e.g., `translate'). */
-#ifndef PATFETCH
#define PATFETCH(c) \
- do {if (p == pend) return REG_EEND; \
- c = *p++; \
- if (RE_TRANSLATE_P (translate)) c = RE_TRANSLATE (translate, c); \
+ do { \
+ PATFETCH_RAW (c); \
+ c = TRANSLATE (c); \
} while (0)
-#endif
/* Fetch the next character in the uncompiled pattern, with no
translation. */
#define PATFETCH_RAW(c) \
- do {if (p == pend) return REG_EEND; \
- c = *p++; \
+ do { \
+ int len; \
+ if (p == pend) return REG_EEND; \
+ c = RE_STRING_CHAR_AND_LENGTH (p, pend - p, len); \
+ p += len; \
} while (0)
-/* Go backwards one character in the pattern. */
-#define PATUNFETCH p--
-
/* If `translate' is non-null, return translate[D], else just D. We
cast the subscript to translate because some data is declared as
/* Get the next unsigned number in the uncompiled pattern. */
#define GET_UNSIGNED_NUMBER(num) \
- { if (p != pend) \
+ do { if (p != pend) \
{ \
PATFETCH (c); \
while (ISDIGIT (c)) \
PATFETCH (c); \
} \
} \
- }
+ } while (0)
#define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
|| STREQ (string, "word") \
|| STREQ (string, "ascii") || STREQ (string, "nonascii") \
|| STREQ (string, "unibyte") || STREQ (string, "multibyte"))
+
+/* QUIT is only used on NTemacs. */
+#if !defined (WINDOWSNT) || !defined (emacs)
+#undef QUIT
+#define QUIT
+#endif
\f
#ifndef MATCH_MAY_ALLOCATE
#endif /* not MATCH_MAY_ALLOCATE */
\f
+static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
+ compile_stack,
+ regnum_t regnum));
+
/* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
Returns one of error codes defined in `regex.h', or zero for success.
/* Work area for range table of charset. */
struct range_table_work_area range_table_work;
+ /* If the object matched can contain multibyte characters. */
+ const boolean multibyte = RE_MULTIBYTE_P (bufp);
+
#ifdef DEBUG
- /* debug = 1; */
+ debug++;
DEBUG_PRINT1 ("\nCompiling pattern: ");
- if (debug)
+ if (debug > 0)
{
unsigned debug_count;
/* Always count groups, whether or not bufp->no_sub is set. */
bufp->re_nsub = 0;
-#ifdef emacs
- /* bufp->multibyte is set before regex_compile is called, so don't alter
- it. */
-#else /* not emacs */
- /* Nothing is recognized as a multibyte character. */
- bufp->multibyte = 0;
-#endif
-
#if !defined (emacs) && !defined (SYNTAX_TABLE)
/* Initialize the syntax table. */
init_syntax_once ();
}
{
- /* Are we optimizing this jump? */
- boolean keep_string_p = false;
-
/* 1 means zero (many) matches is allowed. */
boolean zero_times_ok = 0, many_times_ok = 0;
boolean greedy = 1;
if (p == pend)
break;
-
- PATFETCH (c);
-
- if (c == '*'
- || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
+ else if (*p == '*'
+ || (!(syntax & RE_BK_PLUS_QM)
+ && (*p == '+' || *p == '?')))
;
-
- else if (syntax & RE_BK_PLUS_QM && c == '\\')
+ else if (syntax & RE_BK_PLUS_QM && *p == '\\')
{
- if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
-
- PATFETCH (c1);
- if (!(c1 == '+' || c1 == '?'))
- {
- PATUNFETCH;
- PATUNFETCH;
- break;
- }
-
- c = c1;
+ if (p+1 == pend)
+ FREE_STACK_RETURN (REG_EESCAPE);
+ if (p[1] == '+' || p[1] == '?')
+ PATFETCH (c); /* Gobble up the backslash. */
+ else
+ break;
}
else
- {
- PATUNFETCH;
- break;
- }
-
+ break;
/* If we get here, we found another repeat character. */
+ PATFETCH (c);
}
/* Star, etc. applied to an empty pattern is equivalent
to an empty pattern. */
- if (!laststart)
+ if (!laststart || laststart == b)
break;
/* Now we know whether or not zero matches is allowed
and also whether or not two or more matches is allowed. */
if (greedy)
{
- if (many_times_ok)
- { /* More than one repetition is allowed, so 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).
-
- But if we are at the `*' in the exact sequence `.*\n',
- insert an unconditional jump backwards to the .,
- instead of the beginning of the loop. This way we only
- push a failure point once, instead of every time
- through the loop. */
- assert (p - 1 > pattern);
-
- /* Allocate the space for the jump. */
- GET_BUFFER_SPACE (3);
-
- /* We know we are not at the first character of the pattern,
- because laststart was nonzero. And we've already
- incremented `p', by the way, to be the character after
- the `*'. Do we have to do something analogous here
- for null bytes, because of RE_DOT_NOT_NULL? */
- if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
- && zero_times_ok
- && p < pend
- && TRANSLATE (*p) == TRANSLATE ('\n')
- && !(syntax & RE_DOT_NEWLINE))
- { /* We have .*\n. */
- STORE_JUMP (jump, b, laststart);
- keep_string_p = true;
+ if (many_times_ok)
+ {
+ boolean simple = skip_one_char (laststart) == b;
+ unsigned int startoffset = 0;
+ re_opcode_t ofj =
+ (simple || !analyse_first (laststart, b, NULL, 0)) ?
+ on_failure_jump : on_failure_jump_loop;
+ assert (skip_one_char (laststart) <= b);
+
+ if (!zero_times_ok && simple)
+ { /* Since simple * loops can be made faster by using
+ on_failure_keep_string_jump, we turn simple P+
+ into PP* if P is simple. */
+ unsigned char *p1, *p2;
+ startoffset = b - laststart;
+ GET_BUFFER_SPACE (startoffset);
+ p1 = b; p2 = laststart;
+ while (p2 < p1)
+ *b++ = *p2++;
+ zero_times_ok = 1;
+ }
+
+ GET_BUFFER_SPACE (6);
+ if (!zero_times_ok)
+ /* A + loop. */
+ STORE_JUMP (ofj, b, b + 6);
+ else
+ /* Simple * loops can use on_failure_keep_string_jump
+ depending on what follows. But since we don't know
+ that yet, we leave the decision up to
+ on_failure_jump_smart. */
+ INSERT_JUMP (simple ? on_failure_jump_smart : ofj,
+ laststart + startoffset, b + 6);
+ b += 3;
+ STORE_JUMP (jump, b, laststart + startoffset);
+ b += 3;
}
else
- STORE_JUMP (jump, b, laststart - 3);
-
- /* We've added more stuff to the buffer. */
- b += 3;
- }
-
- /* 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);
- if (!zero_times_ok)
- {
- assert (many_times_ok);
- INSERT_JUMP (on_failure_jump_smart, b - 3, b + 3);
- pending_exact = 0;
- b += 3;
- }
- else
- {
- INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
- : !many_times_ok ?
- on_failure_jump : on_failure_jump_smart,
- laststart, b + 3);
- pending_exact = 0;
- b += 3;
- }
+ {
+ /* A simple ? pattern. */
+ assert (zero_times_ok);
+ GET_BUFFER_SPACE (3);
+ INSERT_JUMP (on_failure_jump, laststart, b + 3);
+ b += 3;
+ }
}
else /* not greedy */
{ /* I wish the greedy and non-greedy cases could be merged. */
+ GET_BUFFER_SPACE (7); /* We might use less. */
if (many_times_ok)
{
+ boolean emptyp = analyse_first (laststart, b, NULL, 0);
+
/* The non-greedy multiple match looks like a repeat..until:
we only need a conditional jump at the end of the loop */
- GET_BUFFER_SPACE (3);
- STORE_JUMP (on_failure_jump, b, laststart);
+ if (emptyp) BUF_PUSH (no_op);
+ STORE_JUMP (emptyp ? on_failure_jump_nastyloop
+ : on_failure_jump, b, laststart);
b += 3;
if (zero_times_ok)
{
/* The repeat...until naturally matches one or more.
To also match zero times, we need to first jump to
the end of the loop (its conditional jump). */
- GET_BUFFER_SPACE (3);
INSERT_JUMP (jump, laststart, b);
b += 3;
}
else
{
/* non-greedy a?? */
- GET_BUFFER_SPACE (6);
INSERT_JUMP (jump, laststart, b + 3);
b += 3;
INSERT_JUMP (on_failure_jump, laststart, laststart + 6);
}
}
}
+ pending_exact = 0;
break;
/* Read in characters and ranges, setting map bits. */
for (;;)
{
- int len;
boolean escaped_char = false;
+ const unsigned char *p2 = p;
if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
/* Could be the end of the bracket expression. If it's
not (i.e., when the bracket expression is `[]' so
far), the ']' character bit gets set way below. */
- if (c == ']' && p != p1 + 1)
+ if (c == ']' && p2 != p1)
break;
}
- /* If C indicates start of multibyte char, get the
- actual character code in C, and set the pattern
- pointer P to the next character boundary. */
- if (bufp->multibyte && BASE_LEADING_CODE_P (c))
- {
- PATUNFETCH;
- c = STRING_CHAR_AND_LENGTH (p, pend - p, len);
- p += len;
- }
/* What should we do for the character which is
greater than 0x7F, but not BASE_LEADING_CODE_P?
XXX */
/* See if we're at the beginning of a possible character
class. */
- else if (!escaped_char &&
- syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
+ if (!escaped_char &&
+ syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
{
/* Leave room for the null. */
char str[CHAR_CLASS_MAX_LENGTH + 1];
+ const unsigned char *class_beg;
PATFETCH (c);
c1 = 0;
+ class_beg = p;
/* If pattern is `[[:'. */
if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
they can only match ASCII characters. We
don't need to handle them for multibyte. */
- if (bufp->multibyte)
+ if (multibyte)
{
int bit = 0;
}
else
{
- c1++;
- while (c1--)
- PATUNFETCH;
+ /* Go back to right after the "[:". */
+ p = class_beg;
SET_LIST_BIT ('[');
/* Because the `:' may starts the range, we
/* Fetch the character which ends the range. */
PATFETCH (c1);
- if (bufp->multibyte && BASE_LEADING_CODE_P (c1))
- {
- PATUNFETCH;
- c1 = STRING_CHAR_AND_LENGTH (p, pend - p, len);
- p += len;
- }
- if (SINGLE_BYTE_CHAR_P (c)
- && ! SINGLE_BYTE_CHAR_P (c1))
+ if (SINGLE_BYTE_CHAR_P (c))
{
- /* Handle a range such as \177-\377 in multibyte mode.
- Split that into two ranges,,
- the low one ending at 0237, and the high one
- starting at ...040. */
- /* Unless I'm missing something,
- this line is useless. -sm
- int c1_base = (c1 & ~0177) | 040; */
- SET_RANGE_TABLE_WORK_AREA (range_table_work, c, c1);
- c1 = 0237;
+ if (! SINGLE_BYTE_CHAR_P (c1))
+ {
+ /* Handle a range such as \177-\377 in
+ multibyte mode. Split that into two
+ ranges, the low one ending at 0237, and
+ the high one starting at the smallest
+ character in the charset of C1 and
+ ending at C1. */
+ int charset = CHAR_CHARSET (c1);
+ int c2 = MAKE_CHAR (charset, 0, 0);
+
+ SET_RANGE_TABLE_WORK_AREA (range_table_work,
+ c2, c1);
+ c1 = 0237;
+ }
}
else if (!SAME_CHARSET_P (c, c1))
FREE_STACK_RETURN (REG_ERANGE);
if (p+1 < pend)
{
/* Look for a special (?...) construct */
- PATFETCH (c);
- if ((syntax & RE_SHY_GROUPS) && c == '?')
+ if ((syntax & RE_SHY_GROUPS) && *p == '?')
{
+ PATFETCH (c); /* Gobble up the '?'. */
PATFETCH (c);
switch (c)
{
FREE_STACK_RETURN (REG_BADPAT);
}
}
- else PATUNFETCH;
}
if (!shy)
regnum++;
}
- if (COMPILE_STACK_FULL)
- {
- RETALLOC (compile_stack.stack, compile_stack.size << 1,
- compile_stack_elt_t);
- if (compile_stack.stack == NULL) return REG_ESPACE;
+ if (COMPILE_STACK_FULL)
+ {
+ RETALLOC (compile_stack.stack, compile_stack.size << 1,
+ compile_stack_elt_t);
+ if (compile_stack.stack == NULL) return REG_ESPACE;
- compile_stack.size <<= 1;
- }
+ compile_stack.size <<= 1;
+ }
- /* These are the values to restore when we hit end of this
- group. They are all relative offsets, so that if the
- whole pattern moves because of realloc, they will still
- be valid. */
- COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
- COMPILE_STACK_TOP.fixup_alt_jump
- = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
- COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
- COMPILE_STACK_TOP.regnum = shy ? -regnum : regnum;
-
- /* Do not push a
- start_memory for groups beyond the last one we can
- represent in the compiled pattern. */
- if (regnum <= MAX_REGNUM && !shy)
- BUF_PUSH_2 (start_memory, regnum);
-
- compile_stack.avail++;
-
- fixup_alt_jump = 0;
- laststart = 0;
- begalt = b;
- /* If we've reached MAX_REGNUM groups, then this open
- won't actually generate any code, so we'll have to
- clear pending_exact explicitly. */
- pending_exact = 0;
- break;
+ /* These are the values to restore when we hit end of this
+ group. They are all relative offsets, so that if the
+ whole pattern moves because of realloc, they will still
+ be valid. */
+ COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
+ COMPILE_STACK_TOP.fixup_alt_jump
+ = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
+ COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
+ COMPILE_STACK_TOP.regnum = shy ? -regnum : regnum;
+
+ /* Do not push a
+ start_memory for groups beyond the last one we can
+ represent in the compiled pattern. */
+ if (regnum <= MAX_REGNUM && !shy)
+ BUF_PUSH_2 (start_memory, regnum);
+
+ compile_stack.avail++;
+
+ fixup_alt_jump = 0;
+ laststart = 0;
+ begalt = b;
+ /* If we've reached MAX_REGNUM groups, then this open
+ won't actually generate any code, so we'll have to
+ clear pending_exact explicitly. */
+ pending_exact = 0;
+ break;
}
case ')':
if (!(syntax & RE_INTERVALS)
/* If we're at `\{' and it's not the open-interval
operator. */
- || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
- || (p - 2 == pattern && p == pend))
+ || (syntax & RE_NO_BK_BRACES)
+ /* What is that? -sm */
+ /* || (p - 2 == pattern && p == pend) */)
goto normal_backslash;
handle_interval:
/* If got here, then the syntax allows intervals. */
/* At least (most) this many matches must be made. */
- int lower_bound = -1, upper_bound = -1;
+ int lower_bound = 0, upper_bound = -1;
- beg_interval = p - 1;
+ beg_interval = p;
if (p == pend)
{
GET_UNSIGNED_NUMBER (lower_bound);
if (c == ',')
- {
- GET_UNSIGNED_NUMBER (upper_bound);
- if (upper_bound < 0) upper_bound = RE_DUP_MAX;
- }
+ GET_UNSIGNED_NUMBER (upper_bound);
else
/* Interval such as `{1}' => match exactly once. */
upper_bound = lower_bound;
if (lower_bound < 0 || upper_bound > RE_DUP_MAX
- || lower_bound > upper_bound)
+ || (upper_bound >= 0 && lower_bound > upper_bound))
{
if (syntax & RE_NO_BK_BRACES)
goto unfetch_interval;
goto unfetch_interval;
}
- /* If the 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 we insert the jump. */
if (upper_bound == 0)
- {
- GET_BUFFER_SPACE (3);
- INSERT_JUMP (jump, laststart, b + 3);
- b += 3;
- }
+ /* If the upper bound is zero, just drop the sub pattern
+ altogether. */
+ b = laststart;
+ else if (lower_bound == 1 && upper_bound == 1)
+ /* Just match it once: nothing to do here. */
+ ;
/* Otherwise, we have a nontrivial interval. When
we're all done, the pattern will look like:
else
{ /* If the upper bound is > 1, we need to insert
more at the end of the loop. */
- unsigned nbytes = 10 + (upper_bound > 1) * 10;
-
- GET_BUFFER_SPACE (nbytes);
-
- /* Initialize lower bound of the `succeed_n', even
- though it will be set during matching by its
- attendant `set_number_at' (inserted next),
- because `re_compile_fastmap' needs to know.
- Jump to the `jump_n' we might insert below. */
- INSERT_JUMP2 (succeed_n, laststart,
- b + 5 + (upper_bound > 1) * 5,
- lower_bound);
- b += 5;
-
- /* Code to initialize the lower bound. Insert
- before the `succeed_n'. The `5' is the last two
- bytes of this `set_number_at', plus 3 bytes of
- the following `succeed_n'. */
- insert_op2 (set_number_at, laststart, 5, lower_bound, b);
- b += 5;
-
- if (upper_bound > 1)
+ unsigned int nbytes = (upper_bound < 0 ? 3
+ : upper_bound > 1 ? 5 : 0);
+ unsigned int startoffset = 0;
+
+ GET_BUFFER_SPACE (20); /* We might use less. */
+
+ if (lower_bound == 0)
+ {
+ /* A succeed_n that starts with 0 is really a
+ a simple on_failure_jump_loop. */
+ INSERT_JUMP (on_failure_jump_loop, laststart,
+ b + 3 + nbytes);
+ b += 3;
+ }
+ else
+ {
+ /* Initialize lower bound of the `succeed_n', even
+ though it will be set during matching by its
+ attendant `set_number_at' (inserted next),
+ because `re_compile_fastmap' needs to know.
+ Jump to the `jump_n' we might insert below. */
+ INSERT_JUMP2 (succeed_n, laststart,
+ b + 5 + nbytes,
+ lower_bound);
+ b += 5;
+
+ /* Code to initialize the lower bound. Insert
+ before the `succeed_n'. The `5' is the last two
+ bytes of this `set_number_at', plus 3 bytes of
+ the following `succeed_n'. */
+ insert_op2 (set_number_at, laststart, 5, lower_bound, b);
+ b += 5;
+ startoffset += 5;
+ }
+
+ if (upper_bound < 0)
+ {
+ /* A negative upper bound stands for infinity,
+ in which case it degenerates to a plain jump. */
+ STORE_JUMP (jump, b, laststart + startoffset);
+ b += 3;
+ }
+ else if (upper_bound > 1)
{ /* More than one repetition is allowed, so
append a backward jump to the `succeed_n'
that starts this interval.
When we've reached this during matching,
we'll have matched the interval once, so
jump back only `upper_bound - 1' times. */
- STORE_JUMP2 (jump_n, b, laststart + 5,
+ STORE_JUMP2 (jump_n, b, laststart + startoffset,
upper_bound - 1);
b += 5;
beg_interval = NULL;
/* normal_char and normal_backslash need `c'. */
- PATFETCH (c);
+ c = '{';
if (!(syntax & RE_NO_BK_BRACES))
{
- if (p > pattern && p[-1] == '\\')
- goto normal_backslash;
+ assert (p > pattern && p[-1] == '\\');
+ goto normal_backslash;
}
- goto normal_char;
+ else
+ goto normal_char;
#ifdef emacs
/* There is no way to specify the before_dot and after_dot
case 'w':
laststart = b;
- BUF_PUSH (wordchar);
+ BUF_PUSH_2 (syntaxspec, Sword);
break;
case 'W':
laststart = b;
- BUF_PUSH (notwordchar);
+ BUF_PUSH_2 (notsyntaxspec, Sword);
break;
default:
/* Expects the character in `c'. */
normal_char:
- p1 = p - 1; /* P1 points the head of C. */
-#ifdef emacs
- if (bufp->multibyte)
- {
- c = STRING_CHAR (p1, pend - p1);
- c = TRANSLATE (c);
- /* Set P to the next character boundary. */
- p += MULTIBYTE_FORM_LENGTH (p1, pend - p1) - 1;
- }
-#endif
/* If no exactn currently being built. */
if (!pending_exact
|| pending_exact + *pending_exact + 1 != b
/* We have only one byte following the exactn for the count. */
- || *pending_exact >= (1 << BYTEWIDTH) - (p - p1)
+ || *pending_exact >= (1 << BYTEWIDTH) - MAX_MULTIBYTE_LENGTH
/* If followed by a repetition operator. */
|| (p != pend && (*p == '*' || *p == '^'))
pending_exact = b - 1;
}
-#ifdef emacs
- if (! SINGLE_BYTE_CHAR_P (c))
- {
- unsigned char str[MAX_MULTIBYTE_LENGTH];
- int i = CHAR_STRING (c, str);
- int j;
- for (j = 0; j < i; j++)
- {
- BUF_PUSH (str[j]);
- (*pending_exact)++;
- }
- }
- else
-#endif
- {
- BUF_PUSH (c);
- (*pending_exact)++;
- }
+ GET_BUFFER_SPACE (MAX_MULTIBYTE_LENGTH);
+ {
+ int len = CHAR_STRING (c, b);
+ b += len;
+ (*pending_exact) += len;
+ }
+
break;
} /* switch (c) */
} /* while p != pend */
bufp->used = b - bufp->buffer;
#ifdef DEBUG
- if (debug)
+ if (debug > 0)
{
re_compile_fastmap (bufp);
DEBUG_PRINT1 ("\nCompiled pattern: \n");
print_compiled_pattern (bufp);
- /* debug = 0; */
}
+ debug--;
#endif /* DEBUG */
#ifndef MATCH_MAY_ALLOCATE
static boolean
at_begline_loc_p (pattern, p, syntax)
- re_char *pattern, *p;
+ const unsigned char *pattern, *p;
reg_syntax_t syntax;
{
- re_char *prev = p - 2;
+ const unsigned char *prev = p - 2;
boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
return
/* After a subexpression? */
(*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
/* After an alternative? */
- || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
+ || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash))
+ /* After a shy subexpression? */
+ || ((syntax & RE_SHY_GROUPS) && prev - 2 >= pattern
+ && prev[-1] == '?' && prev[-2] == '('
+ && (syntax & RE_NO_BK_PARENS
+ || (prev - 3 >= pattern && prev[-3] == '\\')));
}
static boolean
at_endline_loc_p (p, pend, syntax)
- re_char *p, *pend;
- int syntax;
+ const unsigned char *p, *pend;
+ reg_syntax_t syntax;
{
- re_char *next = p;
+ const unsigned char *next = p;
boolean next_backslash = *next == '\\';
- re_char *next_next = p + 1 < pend ? p + 1 : 0;
+ const unsigned char *next_next = p + 1 < pend ? p + 1 : 0;
return
/* Before a subexpression? */
return false;
}
\f
-/* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
- BUFP. A 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 impossible starting points.
-
- Character codes above (1 << BYTEWIDTH) are not represented in the
- fastmap, but the leading codes are represented. Thus, the fastmap
- indicates which character sets could start a match.
-
- The caller must supply the address of a (1 << BYTEWIDTH)-byte data
- area as BUFP->fastmap.
-
- We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
- the pattern buffer.
-
- Returns 0 if we succeed, -2 if an internal error. */
+/* analyse_first.
+ If fastmap is non-NULL, go through the pattern and fill fastmap
+ with all the possible leading chars. If fastmap is NULL, don't
+ bother filling it up (obviously) and only return whether the
+ pattern could potentially match the empty string.
+
+ Return 1 if p..pend might match the empty string.
+ Return 0 if p..pend matches at least one char.
+ Return -1 if p..pend matches at least one char, but fastmap was not
+ updated accurately.
+ Return -2 if an error occurred. */
-int
-re_compile_fastmap (bufp)
- struct re_pattern_buffer *bufp;
+static int
+analyse_first (p, pend, fastmap, multibyte)
+ unsigned char *p, *pend;
+ char *fastmap;
+ const int multibyte;
{
int j, k;
+ boolean not;
#ifdef MATCH_MAY_ALLOCATE
fail_stack_type fail_stack;
#endif
char *destination;
#endif
- register char *fastmap = bufp->fastmap;
- unsigned char *pattern = bufp->buffer;
- unsigned long size = bufp->used;
- unsigned char *p = pattern;
- register unsigned char *pend = pattern + size;
-
+#if defined (REL_ALLOC) && defined (REGEX_MALLOC)
/* This holds the pointer to the failure stack, when
it is allocated relocatably. */
fail_stack_elt_t *failure_stack_ptr;
+#endif
/* Assume that each path through the pattern can be null until
proven otherwise. We set this false at the bottom of switch
match the empty string. */
boolean path_can_be_null = true;
- /* We aren't doing a `succeed_n' to begin with. */
- boolean succeed_n_p = false;
-
/* If all elements for base leading-codes in fastmap is set, this
flag is set true. */
boolean match_any_multibyte_characters = false;
- /* Maximum code of simple (single byte) character. */
- int simple_char_max;
-
- assert (fastmap != NULL && p != NULL);
+ assert (p);
INIT_FAIL_STACK ();
- bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
- bufp->fastmap_accurate = 1; /* It will be when we're done. */
- bufp->can_be_null = 0;
/* The loop below works as follows:
- It has a working-list kept in the PATTERN_STACK and which basically
never set `p' (or push) anything `<= p1'. */
/* If can_be_null is set, then the fastmap will not be used anyway. */
- while (!bufp->can_be_null)
+ while (1)
{
/* `p1' is used as a marker of how far back a `on_failure_jump'
can go without being ignored. It is normally equal to `p'
as used for the *? operator. */
unsigned char *p1 = p;
- if (p == pend || *p == succeed)
+ if (p >= pend)
{
- /* We have reached the (effective) end of pattern. */
- if (!PATTERN_STACK_EMPTY ())
- {
- bufp->can_be_null |= path_can_be_null;
-
- /* Reset for next path. */
- path_can_be_null = true;
+ if (path_can_be_null)
+ return (RESET_FAIL_STACK (), 1);
- p = (unsigned char*) POP_PATTERN_OP ();
+ /* We have reached the (effective) end of pattern. */
+ if (PATTERN_STACK_EMPTY ())
+ return (RESET_FAIL_STACK (), 0);
- continue;
- }
- else
- break;
+ p = (unsigned char*) POP_PATTERN_OP ();
+ path_can_be_null = true;
+ continue;
}
/* We should never be about to go beyond the end of the pattern. */
switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
{
+ case succeed:
+ p = pend;
+ continue;
case duplicate:
/* If the first character has to match a backreference, that means
with `break'. */
case exactn:
- fastmap[p[1]] = 1;
+ if (fastmap) fastmap[p[1]] = 1;
break;
-#ifndef emacs
- case charset:
- {
- int length = (*p & 0x7f);;
- p++;
+ case anychar:
+ /* We could put all the chars except for \n (and maybe \0)
+ but we don't bother since it is generally not worth it. */
+ if (!fastmap) break;
+ return (RESET_FAIL_STACK (), -1);
- for (j = length * BYTEWIDTH - 1; j >= 0; j--)
- if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
- fastmap[j] = 1;
- }
- break;
case charset_not:
- /* Chars beyond end of map must be allowed. */
- {
- int length = (*p & 0x7f);;
- p++;
-
- for (j = length * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
- fastmap[j] = 1;
-
- for (j = length * BYTEWIDTH - 1; j >= 0; j--)
- if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
- fastmap[j] = 1;
- }
- 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;
-#else /* emacs */
+ /* Chars beyond end of bitmap are possible matches.
+ All the single-byte codes can occur in multibyte buffers.
+ So any that are not listed in the charset
+ are possible matches, even in multibyte buffers. */
+ if (!fastmap) break;
+ for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH;
+ j < (1 << BYTEWIDTH); j++)
+ fastmap[j] = 1;
+ /* Fallthrough */
case charset:
+ if (!fastmap) break;
+ not = (re_opcode_t) *(p - 1) == charset_not;
for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++;
j >= 0; j--)
- if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
+ if (!!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) ^ not)
fastmap[j] = 1;
- /* If we can match a character class, we can match
- any character set. */
- if (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
- && CHARSET_RANGE_TABLE_BITS (&p[-2]) != 0)
- goto set_fastmap_for_multibyte_characters;
+ if ((not && multibyte)
+ /* Any character set can possibly contain a character
+ which doesn't match the specified set of characters. */
+ || (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
+ && CHARSET_RANGE_TABLE_BITS (&p[-2]) != 0))
+ /* If we can match a character class, we can match
+ any character set. */
+ {
+ set_fastmap_for_multibyte_characters:
+ if (match_any_multibyte_characters == false)
+ {
+ for (j = 0x80; j < 0xA0; j++) /* XXX */
+ if (BASE_LEADING_CODE_P (j))
+ fastmap[j] = 1;
+ match_any_multibyte_characters = true;
+ }
+ }
- if (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
- && match_any_multibyte_characters == false)
+ else if (!not && CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
+ && match_any_multibyte_characters == false)
{
/* Set fastmap[I] 1 where I is a base leading code of each
multibyte character in the range table. */
int c, count;
- /* Make P points the range table. */
- p += CHARSET_BITMAP_SIZE (&p[-2]);
+ /* Make P points the range table. `+ 2' is to skip flag
+ bits for a character class. */
+ p += CHARSET_BITMAP_SIZE (&p[-2]) + 2;
/* Extract the number of ranges in range table into COUNT. */
EXTRACT_NUMBER_AND_INCR (count, p);
}
break;
-
- case charset_not:
- /* Chars beyond end of bitmap are possible matches.
- All the single-byte codes can occur in multibyte buffers.
- So any that are not listed in the charset
- are possible matches, even in multibyte buffers. */
- simple_char_max = (1 << BYTEWIDTH);
- for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH;
- j < simple_char_max; j++)
- fastmap[j] = 1;
-
- for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++;
- j >= 0; j--)
- if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- which doesn't match the specified set of characters. */
- {
- set_fastmap_for_multibyte_characters:
- if (match_any_multibyte_characters == false)
- {
- for (j = 0x80; j < 0xA0; j++) /* XXX */
- if (BASE_LEADING_CODE_P (j))
- fastmap[j] = 1;
- match_any_multibyte_characters = true;
- }
- }
- break;
-
-
- case wordchar:
- /* All the single-byte codes can occur in multibyte buffers,
- and they may have word syntax. So do consider them. */
- simple_char_max = (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (SYNTAX (j) == Sword)
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- whose syntax is `Sword'. */
- goto set_fastmap_for_multibyte_characters;
- break;
-
-
- case notwordchar:
- /* All the single-byte codes can occur in multibyte buffers,
- and they may not have word syntax. So do consider them. */
- simple_char_max = (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (SYNTAX (j) != Sword)
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- whose syntax is not `Sword'. */
- goto set_fastmap_for_multibyte_characters;
- break;
-#endif
-
- case anychar:
- {
- int fastmap_newline = fastmap['\n'];
-
- /* `.' matches anything, except perhaps newline.
- Even in a multibyte buffer, it should match any
- conceivable byte value for the fastmap. */
- if (bufp->multibyte)
- match_any_multibyte_characters = true;
-
- simple_char_max = (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- fastmap[j] = 1;
-
- /* ... except perhaps newline. */
- if (!(bufp->syntax & RE_DOT_NEWLINE))
- fastmap['\n'] = fastmap_newline;
-
- /* Otherwise, have to check alternative paths. */
- break;
- }
-
-#ifdef emacs
- case wordbound:
- case notwordbound:
- case wordbeg:
- case wordend:
- case notsyntaxspec:
- case syntaxspec:
- /* This match depends on text properties. These end with
- aborting optimizations. */
- bufp->can_be_null = 1;
- continue;
-#if 0
- k = *p++;
- simple_char_max = bufp->multibyte ? 0x80 : (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (SYNTAX (j) == (enum syntaxcode) k)
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- whose syntax is K. */
- goto set_fastmap_for_multibyte_characters;
- break;
-
- case notsyntaxspec:
- k = *p++;
- simple_char_max = bufp->multibyte ? 0x80 : (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (SYNTAX (j) != (enum syntaxcode) k)
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- whose syntax is not K. */
- goto set_fastmap_for_multibyte_characters;
- break;
-#endif
-
+ case syntaxspec:
+ case notsyntaxspec:
+ if (!fastmap) break;
+#ifndef emacs
+ not = (re_opcode_t)p[-1] == notsyntaxspec;
+ k = *p++;
+ for (j = 0; j < (1 << BYTEWIDTH); j++)
+ if ((SYNTAX (j) == (enum syntaxcode) k) ^ not)
+ fastmap[j] = 1;
+ break;
+#else /* emacs */
+ /* This match depends on text properties. These end with
+ aborting optimizations. */
+ return (RESET_FAIL_STACK (), -1);
case categoryspec:
- k = *p++;
- simple_char_max = (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (CHAR_HAS_CATEGORY (j, k))
- fastmap[j] = 1;
-
- if (bufp->multibyte)
- /* Any character set can possibly contain a character
- whose category is K. */
- goto set_fastmap_for_multibyte_characters;
- break;
-
-
case notcategoryspec:
+ if (!fastmap) break;
+ not = (re_opcode_t)p[-1] == notcategoryspec;
k = *p++;
- simple_char_max = (1 << BYTEWIDTH);
- for (j = 0; j < simple_char_max; j++)
- if (!CHAR_HAS_CATEGORY (j, k))
+ for (j = 0; j < (1 << BYTEWIDTH); j++)
+ if ((CHAR_HAS_CATEGORY (j, k)) ^ not)
fastmap[j] = 1;
- if (bufp->multibyte)
+ if (multibyte)
/* Any character set can possibly contain a character
- whose category is not K. */
+ whose category is K (or not). */
goto set_fastmap_for_multibyte_characters;
break;
/* All cases after this match the empty string. These end with
`continue'. */
-
case before_dot:
case at_dot:
case after_dot:
- continue;
-#endif /* emacs */
-
-
+#endif /* !emacs */
case no_op:
case begline:
case endline:
case begbuf:
case endbuf:
-#ifndef emacs
case wordbound:
case notwordbound:
case wordbeg:
case wordend:
-#endif
continue;
- case jump_n:
case jump:
EXTRACT_NUMBER_AND_INCR (j, p);
if (j < 0)
{
case on_failure_jump:
case on_failure_keep_string_jump:
- case on_failure_jump_exclusive:
case on_failure_jump_loop:
+ case on_failure_jump_nastyloop:
case on_failure_jump_smart:
p++;
break;
case on_failure_jump:
case on_failure_keep_string_jump:
- case on_failure_jump_exclusive:
+ case on_failure_jump_nastyloop:
case on_failure_jump_loop:
case on_failure_jump_smart:
- handle_on_failure_jump:
EXTRACT_NUMBER_AND_INCR (j, p);
-
- /* For some patterns, e.g., `(a?)?', `p+j' here points to the
- end of the pattern. We don't want to push such a point,
- since when we restore it above, entering the switch will
- increment `p' past the end of the pattern. We don't need
- to push such a point since we obviously won't find any more
- fastmap entries beyond `pend'. Such a pattern can match
- the null string, though. */
if (p + j <= p1)
- /* Backward jump to be ignored. */
- ;
- else if (p + j < pend)
- {
- if (!PUSH_PATTERN_OP (p + j, fail_stack))
- {
- RESET_FAIL_STACK ();
- return -2;
- }
- }
- else
- bufp->can_be_null = 1;
-
- if (succeed_n_p)
- {
- EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */
- succeed_n_p = false;
- }
-
+ ; /* Backward jump to be ignored. */
+ else if (!PUSH_PATTERN_OP (p + j, fail_stack))
+ return (RESET_FAIL_STACK (), -2);
continue;
+ case jump_n:
+ /* This code simply does not properly handle forward jump_n. */
+ DEBUG_STATEMENT (EXTRACT_NUMBER (j, p); assert (j < 0));
+ p += 4;
+ /* jump_n can either jump or fall through. The (backward) jump
+ case has already been handled, so we only need to look at the
+ fallthrough case. */
+ continue;
+
case succeed_n:
- /* 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;
- succeed_n_p = true; /* Spaghetti code alert. */
- goto handle_on_failure_jump;
- }
+ /* If N == 0, it should be an on_failure_jump_loop instead. */
+ DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); assert (j > 0));
+ p += 4;
+ /* We only care about one iteration of the loop, so we don't
+ need to consider the case where this behaves like an
+ on_failure_jump. */
continue;
p = pend;
} /* while p */
- /* Set `can_be_null' for the last path (also the first path, if the
- pattern is empty). */
- bufp->can_be_null |= path_can_be_null;
- RESET_FAIL_STACK ();
+ return (RESET_FAIL_STACK (), 0);
+} /* analyse_first */
+\f
+/* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
+ BUFP. A 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 impossible starting points.
+
+ Character codes above (1 << BYTEWIDTH) are not represented in the
+ fastmap, but the leading codes are represented. Thus, the fastmap
+ indicates which character sets could start a match.
+
+ The caller must supply the address of a (1 << BYTEWIDTH)-byte data
+ area as BUFP->fastmap.
+
+ We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
+ the pattern buffer.
+
+ Returns 0 if we succeed, -2 if an internal error. */
+
+int
+re_compile_fastmap (bufp)
+ struct re_pattern_buffer *bufp;
+{
+ char *fastmap = bufp->fastmap;
+ int analysis;
+
+ assert (fastmap && bufp->buffer);
+
+ bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
+ bufp->fastmap_accurate = 1; /* It will be when we're done. */
+
+ analysis = analyse_first (bufp->buffer, bufp->buffer + bufp->used,
+ fastmap, RE_MULTIBYTE_P (bufp));
+ if (analysis < -1)
+ return analysis;
+ bufp->can_be_null = (analysis != 0);
return 0;
} /* re_compile_fastmap */
\f
int anchored_start = 0;
/* Nonzero if we have to concern multibyte character. */
- int multibyte = bufp->multibyte;
+ const boolean multibyte = RE_MULTIBYTE_P (bufp);
/* Check for out-of-range STARTPOS. */
if (startpos < 0 || startpos > total_size)
#ifdef emacs
gl_state.object = re_match_object;
{
- int adjpos = NILP (re_match_object) || BUFFERP (re_match_object);
- int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (startpos + adjpos);
+ int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (startpos));
SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
}
}
else /* Searching backwards. */
{
- int room = (size1 == 0 || startpos >= size1
+ int room = (startpos >= size1
? size2 + size1 - startpos
: size1 - startpos);
-
- buf_ch = STRING_CHAR (d, room);
- if (RE_TRANSLATE_P (translate))
- buf_ch = RE_TRANSLATE (translate, buf_ch);
+ buf_ch = RE_STRING_CHAR (d, room);
+ buf_ch = TRANSLATE (buf_ch);
if (! (buf_ch >= 0400
|| fastmap[buf_ch]))
\f
/* Declarations and macros for re_match_2. */
-static int bcmp_translate ();
+static int bcmp_translate _RE_ARGS((re_char *s1, re_char *s2,
+ register int len,
+ RE_TRANSLATE_TYPE translate,
+ const int multibyte));
/* This converts PTR, a pointer into one of the search strings `string1'
and `string2' into an offset from the beginning of that string. */
? ((regoff_t) ((ptr) - string1)) \
: ((regoff_t) ((ptr) - string2 + size1)))
-/* Macros for dealing with the split strings in re_match_2. */
-
-#define MATCHING_IN_FIRST_STRING (dend == end_match_1)
-
/* Call before fetching a character with *d. This switches over to
- string2 if necessary. */
+ string2 if necessary.
+ Check re_match_2_internal for a discussion of why end_match_2 might
+ not be within string2 (but be equal to end_match_1 instead). */
#define PREFETCH() \
while (d == dend) \
{ \
dend = end_match_2; \
}
+/* Call before fetching a char with *d if you already checked other limits.
+ This is meant for use in lookahead operations like wordend, etc..
+ where we might need to look at parts of the string that might be
+ outside of the LIMITs (i.e past `stop'). */
+#define PREFETCH_NOLIMIT() \
+ if (d == end1) \
+ { \
+ d = string2; \
+ dend = end_match_2; \
+ } \
/* Test if at very beginning or at very end of the virtual concatenation
of `string1' and `string2'. If only one string, it's `string2'. */
\f
/* Optimization routines. */
+/* If the operation is a match against one or more chars,
+ return a pointer to the next operation, else return NULL. */
+static unsigned char *
+skip_one_char (p)
+ unsigned char *p;
+{
+ switch (SWITCH_ENUM_CAST (*p++))
+ {
+ case anychar:
+ break;
+
+ case exactn:
+ p += *p + 1;
+ break;
+
+ case charset_not:
+ case charset:
+ if (CHARSET_RANGE_TABLE_EXISTS_P (p - 1))
+ {
+ int mcnt;
+ p = CHARSET_RANGE_TABLE (p - 1);
+ EXTRACT_NUMBER_AND_INCR (mcnt, p);
+ p = CHARSET_RANGE_TABLE_END (p, mcnt);
+ }
+ else
+ p += 1 + CHARSET_BITMAP_SIZE (p - 1);
+ break;
+
+ case syntaxspec:
+ case notsyntaxspec:
+#ifdef emacs
+ case categoryspec:
+ case notcategoryspec:
+#endif /* emacs */
+ p++;
+ break;
+
+ default:
+ p = NULL;
+ }
+ return p;
+}
+
+
/* Jump over non-matching operations. */
static unsigned char *
-skip_noops (p, pend, memory)
+skip_noops (p, pend)
unsigned char *p, *pend;
- int memory;
{
int mcnt;
while (p < pend)
switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
{
case start_memory:
- if (!memory)
- return p;
case stop_memory:
p += 2; break;
case no_op:
struct re_pattern_buffer *bufp;
unsigned char *p1, *p2;
{
- int multibyte = bufp->multibyte;
+ re_opcode_t op2;
+ const boolean multibyte = RE_MULTIBYTE_P (bufp);
unsigned char *pend = bufp->buffer + bufp->used;
- assert (p1 >= bufp->buffer && p1 <= pend
+ assert (p1 >= bufp->buffer && p1 < pend
&& p2 >= bufp->buffer && p2 <= pend);
/* Skip over open/close-group commands.
If what follows this loop is a ...+ construct,
look at what begins its body, since we will have to
match at least one of that. */
- p2 = skip_noops (p2, pend, 1);
- /* The same skip can be done for p1, except that skipping over
- start_memory is not a good idea (if there's a group inside
- the loop delimited by on_failure_jump_exclusive, then it
- can't optimize the push away (it still works properly, but
- slightly slower rather than faster)). */
- p1 = skip_noops (p1, pend, 0);
-
- /* If we're at the end of the pattern, we can change. */
- if (p2 == pend)
+ p2 = skip_noops (p2, pend);
+ /* The same skip can be done for p1, except that this function
+ is only used in the case where p1 is a simple match operator. */
+ /* p1 = skip_noops (p1, pend); */
+
+ assert (p1 >= bufp->buffer && p1 < pend
+ && p2 >= bufp->buffer && p2 <= pend);
+
+ op2 = p2 == pend ? succeed : *p2;
+
+ switch (SWITCH_ENUM_CAST (op2))
{
- switch (SWITCH_ENUM_CAST ((re_opcode_t) *p1))
+ case succeed:
+ case endbuf:
+ /* If we're at the end of the pattern, we can change. */
+ if (skip_one_char (p1))
{
- case anychar:
- case charset_not:
- case charset:
- case exactn:
DEBUG_PRINT1 (" End of pattern: fast loop.\n");
return 1;
- default:
- return 0;
}
- }
-
- else if ((re_opcode_t) *p2 == exactn
- || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
- {
- register unsigned int c
- = *p2 == (unsigned char) endline ? '\n' : p2[2];
+ break;
+
+ case endline:
+ if (!bufp->newline_anchor)
+ break;
+ /* Fallthrough */
+ case exactn:
+ {
+ register unsigned int c
+ = (re_opcode_t) *p2 == endline ? '\n'
+ : RE_STRING_CHAR(p2 + 2, pend - p2 - 2);
- if ((re_opcode_t) *p1 == exactn)
- {
- if (!(multibyte /* && (c != '\n') */
- && BASE_LEADING_CODE_P (c))
- ? c != p1[2]
- : (STRING_CHAR (&p2[2], pend - &p2[2])
- != STRING_CHAR (&p1[2], pend - &p1[2])))
- {
- DEBUG_PRINT3 (" '%c' != '%c' => fast loop.\n", c, p1[2]);
- return 1;
- }
- }
+ if ((re_opcode_t) *p1 == exactn)
+ {
+ if (c != RE_STRING_CHAR (p1 + 2, pend - p1 - 2))
+ {
+ DEBUG_PRINT3 (" '%c' != '%c' => fast loop.\n", c, p1[2]);
+ return 1;
+ }
+ }
- else if ((re_opcode_t) *p1 == charset
- || (re_opcode_t) *p1 == charset_not)
- {
- int not = (re_opcode_t) *p1 == charset_not;
+ else if ((re_opcode_t) *p1 == charset
+ || (re_opcode_t) *p1 == charset_not)
+ {
+ int not = (re_opcode_t) *p1 == charset_not;
- if (multibyte /* && (c != '\n') */
- && BASE_LEADING_CODE_P (c))
- c = STRING_CHAR (&p2[2], pend - &p2[2]);
+ /* Test if C is listed in charset (or charset_not)
+ at `p1'. */
+ if (SINGLE_BYTE_CHAR_P (c))
+ {
+ if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
+ && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
+ not = !not;
+ }
+ else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
+ CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
- /* Test if C is listed in charset (or charset_not)
- at `p1'. */
- if (SINGLE_BYTE_CHAR_P (c))
- {
- if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
- && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
- not = !not;
- }
- else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
- CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
+ /* `not' is equal to 1 if c would match, which means
+ that we can't change to pop_failure_jump. */
+ if (!not)
+ {
+ DEBUG_PRINT1 (" No match => fast loop.\n");
+ return 1;
+ }
+ }
+ else if ((re_opcode_t) *p1 == anychar
+ && c == '\n')
+ {
+ DEBUG_PRINT1 (" . != \\n => fast loop.\n");
+ return 1;
+ }
+ }
+ break;
- /* `not' is equal to 1 if c would match, which means
- that we can't change to pop_failure_jump. */
- if (!not)
- {
- DEBUG_PRINT1 (" No match => fast loop.\n");
- return 1;
- }
- }
- else if ((re_opcode_t) *p1 == anychar
- && c == '\n')
- {
- DEBUG_PRINT1 (" . != \\n => fast loop.\n");
- return 1;
- }
- }
- else if ((re_opcode_t) *p2 == charset
- || (re_opcode_t) *p2 == charset_not)
- {
- if ((re_opcode_t) *p1 == exactn)
- /* Reuse the code above. */
- return mutually_exclusive_p (bufp, p2, p1);
+ case charset:
+ case charset_not:
+ {
+ if ((re_opcode_t) *p1 == exactn)
+ /* Reuse the code above. */
+ return mutually_exclusive_p (bufp, p2, p1);
/* It is hard to list up all the character in charset
&& ((p2[2 + idx] & ~ p1[2 + idx]) == 0))))
break;
- if (idx == p2[1])
- {
- DEBUG_PRINT1 (" No match => fast loop.\n");
- return 1;
- }
- }
- }
+ if (idx == p2[1])
+ {
+ DEBUG_PRINT1 (" No match => fast loop.\n");
+ return 1;
+ }
+ }
+ }
+ }
+
+ case wordend:
+ case notsyntaxspec:
+ return ((re_opcode_t) *p1 == syntaxspec
+ && p1[1] == (op2 == wordend ? Sword : p2[1]));
+
+ case wordbeg:
+ case syntaxspec:
+ return ((re_opcode_t) *p1 == notsyntaxspec
+ && p1[1] == (op2 == wordend ? Sword : p2[1]));
+
+ case wordbound:
+ return (((re_opcode_t) *p1 == notsyntaxspec
+ || (re_opcode_t) *p1 == syntaxspec)
+ && p1[1] == Sword);
+
+#ifdef emacs
+ case categoryspec:
+ return ((re_opcode_t) *p1 == notcategoryspec && p1[1] == p2[1]);
+ case notcategoryspec:
+ return ((re_opcode_t) *p1 == categoryspec && p1[1] == p2[1]);
+#endif /* emacs */
+
+ default:
+ ;
}
/* Safe default. */
{
int result = re_match_2_internal (bufp, NULL, 0, string, size,
pos, regs, size);
+#if defined (C_ALLOCA) && !defined (REGEX_MALLOC)
alloca (0);
+#endif
return result;
}
#endif /* not emacs */
#ifdef emacs
int charpos;
- int adjpos = NILP (re_match_object) || BUFFERP (re_match_object);
gl_state.object = re_match_object;
- charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos + adjpos);
+ charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (pos));
SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
#endif
result = re_match_2_internal (bufp, string1, size1, string2, size2,
pos, regs, stop);
+#if defined (C_ALLOCA) && !defined (REGEX_MALLOC)
alloca (0);
+#endif
return result;
}
/* Where we are in the data, and the end of the current string. */
re_char *d, *dend;
+ /* Used sometimes to remember where we were before starting matching
+ an operator so that we can go back in case of failure. This "atomic"
+ behavior of matching opcodes is indispensable to the correctness
+ of the on_failure_keep_string_jump optimization. */
+ re_char *dfail;
+
/* Where we are in the pattern, and the end of the pattern. */
unsigned char *p = bufp->buffer;
register unsigned char *pend = p + bufp->used;
RE_TRANSLATE_TYPE translate = bufp->translate;
/* Nonzero if we have to concern multibyte character. */
- int multibyte = bufp->multibyte;
+ const boolean multibyte = RE_MULTIBYTE_P (bufp);
/* Failure point stack. Each place that can handle a failure further
down the line pushes a failure point on this stack. It consists of
unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
#endif
+#if defined (REL_ALLOC) && defined (REGEX_MALLOC)
/* This holds the pointer to the failure stack, when
it is allocated relocatably. */
fail_stack_elt_t *failure_stack_ptr;
+#endif
/* We fill all the registers internally, independent of what we
return, for use in backreferences. The number here includes
start_memory/stop_memory has been seen for. Also initialize the
register information struct. */
for (mcnt = 1; mcnt < num_regs; mcnt++)
- {
- regstart[mcnt] = regend[mcnt] = REG_UNSET_VALUE;
- }
+ regstart[mcnt] = regend[mcnt] = REG_UNSET_VALUE;
/* We move `string1' into `string2' if the latter's empty -- but not if
`string1' is null. */
end1 = string1 + size1;
end2 = string2 + size2;
- /* Compute where to stop matching, within the two strings. */
- if (stop <= size1)
- {
- end_match_1 = string1 + stop;
- end_match_2 = string2;
- }
- else
- {
- end_match_1 = end1;
- end_match_2 = string2 + stop - 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)
+ if (pos >= size1)
{
- d = string1 + pos;
- dend = end_match_1;
+ /* Only match within string2. */
+ d = string2 + pos - size1;
+ dend = end_match_2 = string2 + stop - size1;
+ end_match_1 = end1; /* Just to give it a value. */
}
else
{
- d = string2 + pos - size1;
- dend = end_match_2;
+ if (stop < size1)
+ {
+ /* Only match within string1. */
+ end_match_1 = string1 + stop;
+ /* BEWARE!
+ When we reach end_match_1, PREFETCH normally switches to string2.
+ But in the present case, this means that just doing a PREFETCH
+ makes us jump from `stop' to `gap' within the string.
+ What we really want here is for the search to stop as
+ soon as we hit end_match_1. That's why we set end_match_2
+ to end_match_1 (since PREFETCH fails as soon as we hit
+ end_match_2). */
+ end_match_2 = end_match_1;
+ }
+ else
+ { /* It's important to use this code when stop == size so that
+ moving `d' from end1 to string2 will not prevent the d == dend
+ check from catching the end of string. */
+ end_match_1 = end1;
+ end_match_2 = string2 + stop - size1;
+ }
+ d = string1 + pos;
+ dend = end_match_1;
}
DEBUG_PRINT1 ("The compiled pattern is: ");
/* 1 if this match ends in the same string (string1 or string2)
as the best previous match. */
boolean same_str_p = (FIRST_STRING_P (match_end)
- == MATCHING_IN_FIRST_STRING);
+ == FIRST_STRING_P (d));
/* 1 if this match is the best seen so far. */
boolean best_match_p;
if (same_str_p)
best_match_p = d > match_end;
else
- best_match_p = !MATCHING_IN_FIRST_STRING;
+ best_match_p = !FIRST_STRING_P (d);
DEBUG_PRINT1 ("backtracking.\n");
if (regs->num_regs > 0)
{
regs->start[0] = pos;
- regs->end[0] = (MATCHING_IN_FIRST_STRING
- ? ((regoff_t) (d - string1))
- : ((regoff_t) (d - string2 + size1)));
+ regs->end[0] = POINTER_TO_OFFSET (d);
}
/* Go through the first `min (num_regs, regs->num_regs)'
nfailure_points_pushed - nfailure_points_popped);
DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
- mcnt = d - pos - (MATCHING_IN_FIRST_STRING
- ? string1
- : string2 - size1);
+ mcnt = POINTER_TO_OFFSET (d) - pos;
DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
mcnt = *p++;
DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
+ /* Remember the start point to rollback upon failure. */
+ dfail = d;
+
/* This is written out as an if-else so we don't waste time
testing `translate' inside the loop. */
if (RE_TRANSLATE_P (translate))
{
-#ifdef emacs
if (multibyte)
do
{
if (RE_TRANSLATE (translate, buf_ch)
!= pat_ch)
- goto fail;
+ {
+ d = dfail;
+ goto fail;
+ }
p += pat_charlen;
d += buf_charlen;
}
while (mcnt > 0);
else
-#endif /* not emacs */
do
{
PREFETCH ();
if (RE_TRANSLATE (translate, *d) != *p++)
- goto fail;
+ {
+ d = dfail;
+ goto fail;
+ }
d++;
}
while (--mcnt);
do
{
PREFETCH ();
- if (*d++ != *p++) goto fail;
+ if (*d++ != *p++)
+ {
+ d = dfail;
+ goto fail;
+ }
}
while (--mcnt);
}
DEBUG_PRINT1 ("EXECUTING anychar.\n");
PREFETCH ();
-
-#ifdef emacs
- if (multibyte)
- buf_ch = STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen);
- else
-#endif /* not emacs */
- {
- buf_ch = *d;
- buf_charlen = 1;
- }
-
+ buf_ch = RE_STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen);
buf_ch = TRANSLATE (buf_ch);
if ((!(bufp->syntax & RE_DOT_NEWLINE)
DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
- PREFETCH ();
- c = *d;
-
range_table_exists = CHARSET_RANGE_TABLE_EXISTS_P (&p[-1]);
-#ifdef emacs
if (range_table_exists)
{
range_table = CHARSET_RANGE_TABLE (&p[-1]); /* Past the bitmap. */
EXTRACT_NUMBER_AND_INCR (count, range_table);
}
- if (multibyte && BASE_LEADING_CODE_P (c))
- c = STRING_CHAR_AND_LENGTH (d, dend - d, len);
-#endif /* emacs */
+ PREFETCH ();
+ c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
+ c = TRANSLATE (c); /* The character to match. */
if (SINGLE_BYTE_CHAR_P (c))
{ /* Lookup bitmap. */
- c = TRANSLATE (c); /* The character to match. */
- len = 1;
-
/* Cast to `unsigned' instead of `unsigned char' in
case the bit list is a full 32 bytes long. */
if (c < (unsigned) (CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH)
/* Where in input to try to start matching. */
d2 = regstart[regno];
+ /* Remember the start point to rollback upon failure. */
+ dfail = d;
+
/* 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
/* Compare that many; failure if mismatch, else move
past them. */
if (RE_TRANSLATE_P (translate)
- ? bcmp_translate (d, d2, mcnt, translate)
+ ? bcmp_translate (d, d2, mcnt, translate, multibyte)
: bcmp (d, d2, mcnt))
- goto fail;
+ {
+ d = dfail;
+ goto fail;
+ }
d += mcnt, d2 += mcnt;
}
}
{
if (!bufp->not_bol) break;
}
- else if (d[-1] == '\n' && bufp->newline_anchor)
+ else
{
- break;
+ unsigned char c;
+ GET_CHAR_BEFORE_2 (c, d, string1, end1, string2, end2);
+ if (c == '\n' && bufp->newline_anchor)
+ break;
}
/* In all other cases, we fail. */
goto fail;
{
if (!bufp->not_eol) break;
}
-
- /* We have to ``prefetch'' the next character. */
- else if ((d == end1 ? *string2 : *d) == '\n'
- && bufp->newline_anchor)
+ else
{
- break;
+ PREFETCH_NOLIMIT ();
+ if (*d == '\n' && bufp->newline_anchor)
+ break;
}
goto fail;
PUSH_FAILURE_POINT (p - 3, NULL);
break;
- case on_failure_jump_exclusive:
+ /* A nasty loop is introduced by the non-greedy *? and +?.
+ With such loops, the stack only ever contains one failure point
+ at a time, so that a plain on_failure_jump_loop kind of
+ cycle detection cannot work. Worse yet, such a detection
+ can not only fail to detect a cycle, but it can also wrongly
+ detect a cycle (between different instantiations of the same
+ loop.
+ So the method used for those nasty loops is a little different:
+ We use a special cycle-detection-stack-frame which is pushed
+ when the on_failure_jump_nastyloop failure-point is *popped*.
+ This special frame thus marks the beginning of one iteration
+ through the loop and we can hence easily check right here
+ whether something matched between the beginning and the end of
+ the loop. */
+ case on_failure_jump_nastyloop:
EXTRACT_NUMBER_AND_INCR (mcnt, p);
- DEBUG_PRINT3 ("EXECUTING on_failure_jump_exclusive %d (to %p):\n",
+ DEBUG_PRINT3 ("EXECUTING on_failure_jump_nastyloop %d (to %p):\n",
mcnt, p + mcnt);
- if (! FAIL_STACK_EMPTY ()
- && FAILURE_PAT (TOP_FAILURE_HANDLE ()) == (p - 3)
- && fail_stack.avail == fail_stack.frame)
- {
- /* We are trying to push failure F2 onto the stack but there
- is already a failure F1 pushed from the same instruction.
- Between F1 and now, something has matched (else this is an
- improper use of on_failure_jump_exclusive), so that we know
- that the fail-destination of F1 cannot match, hence we can
- pop F1 before pushing F2. Instead of doing this pop/push,
- we manually turn F1 into F2.
- `fail_stack.avail == fail_stack.frame' makes sure
- that popping F1 doesn't involve registers, else
- this optimization cannot be done so trivially. */
- assert (FAILURE_STR (TOP_FAILURE_HANDLE ()) != d);
- FAILURE_STR (TOP_FAILURE_HANDLE ()) = d;
- }
- else
- PUSH_FAILURE_POINT (p - 3, d);
+ assert ((re_opcode_t)p[-4] == no_op);
+ CHECK_INFINITE_LOOP (p - 4, d);
+ PUSH_FAILURE_POINT (p - 3, d);
break;
+
+ /* Simple loop detecting on_failure_jump: just check on the
+ failure stack if the same spot was already hit earlier. */
case on_failure_jump_loop:
on_failure:
EXTRACT_NUMBER_AND_INCR (mcnt, p);
the repetition text and either the following jump or
pop_failure_jump back to this on_failure_jump. */
case on_failure_jump:
-
-#if defined (WINDOWSNT) && defined (emacs)
QUIT;
-#endif
-
EXTRACT_NUMBER_AND_INCR (mcnt, p);
DEBUG_PRINT3 ("EXECUTING on_failure_jump %d (to %p):\n",
mcnt, p + mcnt);
PUSH_FAILURE_POINT (p -3, d);
break;
- /* This operation is used for greedy * and +.
+ /* This operation is used for greedy *.
Compare the beginning of the repeat with what in the
pattern follows its end. If we can establish that there
is nothing that they would both match, i.e., that we
would have to backtrack because of (as in, e.g., `a*a')
then we can use a non-backtracking loop based on
- on_failure_jump_exclusive instead of on_failure_jump_loop. */
+ on_failure_keep_string_jump instead of on_failure_jump. */
case on_failure_jump_smart:
-#if defined (WINDOWSNT) && defined (emacs)
QUIT;
-#endif
EXTRACT_NUMBER_AND_INCR (mcnt, p);
DEBUG_PRINT3 ("EXECUTING on_failure_jump_smart %d (to %p).\n",
mcnt, p + mcnt);
p -= 3; /* Reset so that we will re-execute the
instruction once it's been changed. */
- /* DEBUG_STATEMENT (debug = 1); */
+ EXTRACT_NUMBER (mcnt, p2 - 2);
+
+ /* Ensure this is a indeed the trivial kind of loop
+ we are expecting. */
+ assert (skip_one_char (p1) == p2 - 3);
+ assert ((re_opcode_t) p2[-3] == jump && p2 + mcnt == p);
+ DEBUG_STATEMENT (debug += 2);
if (mutually_exclusive_p (bufp, p1, p2))
{
/* Use a fast `on_failure_keep_string_jump' loop. */
- *p = (unsigned char) on_failure_jump_exclusive;
- /* STORE_NUMBER (p2 - 2, mcnt + 3); */
+ DEBUG_PRINT1 (" smart exclusive => fast loop.\n");
+ *p = (unsigned char) on_failure_keep_string_jump;
+ STORE_NUMBER (p2 - 2, mcnt + 3);
}
else
{
/* Default to a safe `on_failure_jump' loop. */
DEBUG_PRINT1 (" smart default => slow loop.\n");
- *p = (unsigned char) on_failure_jump_loop;
+ *p = (unsigned char) on_failure_jump;
}
- /* DEBUG_STATEMENT (debug = 0); */
+ DEBUG_STATEMENT (debug -= 2);
}
break;
/* Unconditionally jump (without popping any failure points). */
case jump:
unconditional_jump:
-#if defined (WINDOWSNT) && defined (emacs)
QUIT;
-#endif
EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
p += mcnt; /* Do the jump. */
not = (re_opcode_t) *(p - 1) == notwordbound;
DEBUG_PRINT2 ("EXECUTING %swordbound.\n", not?"not":"");
- /* We SUCCEED in one of the following cases: */
+ /* We SUCCEED (or FAIL) in one of the following cases: */
/* Case 1: D is at the beginning or the end of string. */
if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
is the character at D, and S2 is the syntax of C2. */
int c1, c2, s1, s2;
#ifdef emacs
- int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (PTR_TO_OFFSET (d - 1));
+ int offset = PTR_TO_OFFSET (d - 1);
+ int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
UPDATE_SYNTAX_TABLE (charpos);
#endif
- /* FIXME: This does a STRING_CHAR even for unibyte buffers. */
GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
s1 = SYNTAX (c1);
#ifdef emacs
UPDATE_SYNTAX_TABLE_FORWARD (charpos + 1);
#endif
- PREFETCH ();
- /* FIXME: This does a STRING_CHAR even for unibyte buffers. */
- c2 = STRING_CHAR (d, dend - d);
+ PREFETCH_NOLIMIT ();
+ c2 = RE_STRING_CHAR (d, dend - d);
s2 = SYNTAX (c2);
if (/* Case 2: Only one of S1 and S2 is Sword. */
/* Case 1: D is at the end of string. */
if (AT_STRINGS_END (d))
- goto fail;
+ goto fail;
else
{
/* C1 is the character before D, S1 is the syntax of C1, C2
is the character at D, and S2 is the syntax of C2. */
int c1, c2, s1, s2;
- int pos1 = PTR_TO_OFFSET (d);
- int charpos;
-
- PREFETCH ();
- c2 = STRING_CHAR (d, dend - d);
#ifdef emacs
- charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1);
+ int offset = PTR_TO_OFFSET (d);
+ int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
UPDATE_SYNTAX_TABLE (charpos);
#endif
+ PREFETCH ();
+ c2 = RE_STRING_CHAR (d, dend - d);
s2 = SYNTAX (c2);
/* Case 2: S2 is not Sword. */
/* C1 is the character before D, S1 is the syntax of C1, C2
is the character at D, and S2 is the syntax of C2. */
int c1, c2, s1, s2;
- int pos1 = PTR_TO_OFFSET (d);
- int charpos;
-
- GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
#ifdef emacs
- charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1 - 1);
+ int offset = PTR_TO_OFFSET (d) - 1;
+ int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
UPDATE_SYNTAX_TABLE (charpos);
#endif
+ GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
s1 = SYNTAX (c1);
/* Case 2: S1 is not Sword. */
/* Case 3: D is not at the end of string ... */
if (!AT_STRINGS_END (d))
{
- PREFETCH ();
- c2 = STRING_CHAR (d, dend - d);
+ PREFETCH_NOLIMIT ();
+ c2 = RE_STRING_CHAR (d, dend - d);
#ifdef emacs
UPDATE_SYNTAX_TABLE_FORWARD (charpos);
#endif
}
break;
-#ifdef emacs
- case before_dot:
- DEBUG_PRINT1 ("EXECUTING before_dot.\n");
- if (PTR_BYTE_POS (d) >= PT_BYTE)
- goto fail;
- break;
-
- case at_dot:
- DEBUG_PRINT1 ("EXECUTING at_dot.\n");
- if (PTR_BYTE_POS (d) != PT_BYTE)
- goto fail;
- break;
-
- case after_dot:
- DEBUG_PRINT1 ("EXECUTING after_dot.\n");
- if (PTR_BYTE_POS (d) <= PT_BYTE)
- goto fail;
- break;
-
case syntaxspec:
- DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
+ case notsyntaxspec:
+ not = (re_opcode_t) *(p - 1) == notsyntaxspec;
mcnt = *p++;
- goto matchsyntax;
-
- case wordchar:
- DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
- mcnt = (int) Sword;
- matchsyntax:
+ DEBUG_PRINT3 ("EXECUTING %ssyntaxspec %d.\n", not?"not":"", mcnt);
PREFETCH ();
#ifdef emacs
{
- int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (PTR_TO_OFFSET (d));
+ int offset = PTR_TO_OFFSET (d);
+ int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
UPDATE_SYNTAX_TABLE (pos1);
}
#endif
{
int c, len;
- if (multibyte)
- /* we must concern about multibyte form, ... */
- c = STRING_CHAR_AND_LENGTH (d, dend - d, len);
- else
- /* everything should be handled as ASCII, even though it
- looks like multibyte form. */
- c = *d, len = 1;
+ c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
- if (SYNTAX (c) != (enum syntaxcode) mcnt)
- goto fail;
+ if ((SYNTAX (c) != (enum syntaxcode) mcnt) ^ not)
+ goto fail;
d += len;
}
break;
- case notsyntaxspec:
- DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
- mcnt = *p++;
- goto matchnotsyntax;
-
- case notwordchar:
- DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
- mcnt = (int) Sword;
- matchnotsyntax:
- PREFETCH ();
#ifdef emacs
- {
- int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (PTR_TO_OFFSET (d));
- UPDATE_SYNTAX_TABLE (pos1);
- }
-#endif
- {
- int c, len;
-
- if (multibyte)
- c = STRING_CHAR_AND_LENGTH (d, dend - d, len);
- else
- c = *d, len = 1;
-
- if (SYNTAX (c) == (enum syntaxcode) mcnt)
+ case before_dot:
+ DEBUG_PRINT1 ("EXECUTING before_dot.\n");
+ if (PTR_BYTE_POS (d) >= PT_BYTE)
goto fail;
- d += len;
- }
break;
- case categoryspec:
- DEBUG_PRINT2 ("EXECUTING categoryspec %d.\n", *p);
- mcnt = *p++;
- PREFETCH ();
- {
- int c, len;
-
- if (multibyte)
- c = STRING_CHAR_AND_LENGTH (d, dend - d, len);
- else
- c = *d, len = 1;
+ case at_dot:
+ DEBUG_PRINT1 ("EXECUTING at_dot.\n");
+ if (PTR_BYTE_POS (d) != PT_BYTE)
+ goto fail;
+ break;
- if (!CHAR_HAS_CATEGORY (c, mcnt))
- goto fail;
- d += len;
- }
+ case after_dot:
+ DEBUG_PRINT1 ("EXECUTING after_dot.\n");
+ if (PTR_BYTE_POS (d) <= PT_BYTE)
+ goto fail;
break;
+ case categoryspec:
case notcategoryspec:
- DEBUG_PRINT2 ("EXECUTING notcategoryspec %d.\n", *p);
+ not = (re_opcode_t) *(p - 1) == notcategoryspec;
mcnt = *p++;
+ DEBUG_PRINT3 ("EXECUTING %scategoryspec %d.\n", not?"not":"", mcnt);
PREFETCH ();
{
int c, len;
+ c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
- if (multibyte)
- c = STRING_CHAR_AND_LENGTH (d, dend - d, len);
- else
- c = *d, len = 1;
-
- if (CHAR_HAS_CATEGORY (c, mcnt))
+ if ((!CHAR_HAS_CATEGORY (c, mcnt)) ^ not)
goto fail;
d += len;
}
- break;
-
-#else /* not emacs */
- case wordchar:
- DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
- PREFETCH ();
- if (!WORDCHAR_P (d))
- goto fail;
- d++;
break;
- case notwordchar:
- DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
- PREFETCH ();
- if (WORDCHAR_P (d))
- goto fail;
- d++;
- break;
-#endif /* not emacs */
+#endif /* emacs */
default:
abort ();
/* We goto here if a matching operation fails. */
fail:
-#if defined (WINDOWSNT) && defined (emacs)
QUIT;
-#endif
if (!FAIL_STACK_EMPTY ())
{
re_char *str;
assert (str == NULL);
goto continue_failure_jump;
- case on_failure_jump_exclusive:
- /* If something has matched, the alternative will not match,
- so we might as well keep popping right away. */
- if (0 /* d != str && d != string2 */) /* Don't bother. -sm */
- /* (d == string2 && str == end1) => (d =~ str) */
- goto fail;
+ case on_failure_jump_nastyloop:
+ assert ((re_opcode_t)pat[-2] == no_op);
+ PUSH_FAILURE_POINT (pat - 2, str);
/* Fallthrough */
case on_failure_jump_loop:
p = pat + mcnt;
break;
+ case no_op:
+ /* A special frame used for nastyloops. */
+ goto fail;
+
default:
abort();
}
bytes; nonzero otherwise. */
static int
-bcmp_translate (s1, s2, len, translate)
- unsigned char *s1, *s2;
+bcmp_translate (s1, s2, len, translate, multibyte)
+ re_char *s1, *s2;
register int len;
RE_TRANSLATE_TYPE translate;
+ const int multibyte;
{
- register unsigned char *p1 = s1, *p2 = s2;
- unsigned char *p1_end = s1 + len;
- unsigned char *p2_end = s2 + len;
+ register re_char *p1 = s1, *p2 = s2;
+ re_char *p1_end = s1 + len;
+ re_char *p2_end = s2 + len;
while (p1 != p1_end && p2 != p2_end)
{
int p1_charlen, p2_charlen;
int p1_ch, p2_ch;
- p1_ch = STRING_CHAR_AND_LENGTH (p1, p1_end - p1, p1_charlen);
- p2_ch = STRING_CHAR_AND_LENGTH (p2, p2_end - p2, p2_charlen);
+ p1_ch = RE_STRING_CHAR_AND_LENGTH (p1, p1_end - p1, p1_charlen);
+ p2_ch = RE_STRING_CHAR_AND_LENGTH (p2, p2_end - p2, p2_charlen);
if (RE_TRANSLATE (translate, p1_ch)
!= RE_TRANSLATE (translate, p2_ch))
if (!s)
{
if (!re_comp_buf.buffer)
- return gettext ("No previous regular expression");
+ /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
+ return (char *) gettext ("No previous regular expression");
return 0;
}
{
re_comp_buf.buffer = (unsigned char *) malloc (200);
if (re_comp_buf.buffer == NULL)
- return gettext (re_error_msgid[(int) REG_ESPACE]);
+ /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
+ return (char *) gettext (re_error_msgid[(int) REG_ESPACE]);
re_comp_buf.allocated = 200;
re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
if (re_comp_buf.fastmap == NULL)
- return gettext (re_error_msgid[(int) REG_ESPACE]);
+ /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
+ return (char *) gettext (re_error_msgid[(int) REG_ESPACE]);
}
/* Since `re_exec' always passes NULL for the `regs' argument, we
projects / gnulib.git / blobdiff