Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
USA. */
-/* BUGS:
- - (x?)*y\1z should match both xxxxyxz and xxxyz.
- TODO:
+/* TODO:
- structure the opcode space into opcode+flag.
- merge with glibc's regex.[ch].
- replace (succeed_n + jump_n + set_number_at) with something that doesn't
#pragma alloca
#endif
-#undef _GNU_SOURCE
-#define _GNU_SOURCE
-
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
{ \
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); \
+ re_char *d0 = dtemp; \
+ PREV_CHAR_BOUNDARY (d0, dlimit); \
+ c = STRING_CHAR (d0, dtemp - d0); \
} \
else \
(c = ((p) == (str2) ? (end1) : (p))[-1]); \
# define SINGLE_BYTE_CHAR_P(c) (1)
# define SAME_CHARSET_P(c1, c2) (1)
# define MULTIBYTE_FORM_LENGTH(p, s) (1)
+# define PREV_CHAR_BOUNDARY(p, limit) ((p)--)
# define STRING_CHAR(p, s) (*(p))
# define RE_STRING_CHAR STRING_CHAR
# define CHAR_STRING(c, s) (*(s) = (c), 1)
if (start == NULL)
{
- printf ("(null)\n");
+ fprintf (stderr, "(null)\n");
return;
}
/* Loop over pattern commands. */
while (p < pend)
{
- printf ("%d:\t", p - start);
+ fprintf (stderr, "%d:\t", p - start);
switch ((re_opcode_t) *p++)
{
case no_op:
- printf ("/no_op");
+ fprintf (stderr, "/no_op");
break;
case succeed:
- printf ("/succeed");
+ fprintf (stderr, "/succeed");
break;
case exactn:
mcnt = *p++;
- printf ("/exactn/%d", mcnt);
+ fprintf (stderr, "/exactn/%d", mcnt);
do
{
- putchar ('/');
- putchar (*p++);
+ fprintf (stderr, "/%c", *p++);
}
while (--mcnt);
break;
case start_memory:
- printf ("/start_memory/%d", *p++);
+ fprintf (stderr, "/start_memory/%d", *p++);
break;
case stop_memory:
- printf ("/stop_memory/%d", *p++);
+ fprintf (stderr, "/stop_memory/%d", *p++);
break;
case duplicate:
- printf ("/duplicate/%d", *p++);
+ fprintf (stderr, "/duplicate/%d", *p++);
break;
case anychar:
- printf ("/anychar");
+ fprintf (stderr, "/anychar");
break;
case charset:
int length = CHARSET_BITMAP_SIZE (p - 1);
int has_range_table = CHARSET_RANGE_TABLE_EXISTS_P (p - 1);
- printf ("/charset [%s",
+ fprintf (stderr, "/charset [%s",
(re_opcode_t) *(p - 1) == charset_not ? "^" : "");
assert (p + *p < pend);
/* Are we starting a range? */
if (last + 1 == c && ! in_range)
{
- putchar ('-');
+ fprintf (stderr, "-");
in_range = 1;
}
/* Have we broken a range? */
else if (last + 1 != c && in_range)
{
- putchar (last);
+ fprintf (stderr, "%c", last);
in_range = 0;
}
if (! in_range)
- putchar (c);
+ fprintf (stderr, "%c", c);
last = c;
}
if (in_range)
- putchar (last);
+ fprintf (stderr, "%c", last);
- putchar (']');
+ fprintf (stderr, "]");
p += 1 + length;
if (has_range_table)
{
int count;
- printf ("has-range-table");
+ fprintf (stderr, "has-range-table");
/* ??? Should print the range table; for now, just skip it. */
p += 2; /* skip range table bits */
break;
case begline:
- printf ("/begline");
+ fprintf (stderr, "/begline");
break;
case endline:
- printf ("/endline");
+ fprintf (stderr, "/endline");
break;
case on_failure_jump:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_jump to %d", p + mcnt - start);
+ fprintf (stderr, "/on_failure_jump to %d", p + mcnt - start);
break;
case on_failure_keep_string_jump:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
+ fprintf (stderr, "/on_failure_keep_string_jump to %d", p + mcnt - start);
break;
case on_failure_jump_nastyloop:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_jump_nastyloop to %d", p + mcnt - start);
+ fprintf (stderr, "/on_failure_jump_nastyloop to %d", p + mcnt - start);
break;
case on_failure_jump_loop:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_jump_loop to %d", p + mcnt - start);
+ fprintf (stderr, "/on_failure_jump_loop to %d", p + mcnt - start);
break;
case on_failure_jump_smart:
extract_number_and_incr (&mcnt, &p);
- printf ("/on_failure_jump_smart to %d", p + mcnt - start);
+ fprintf (stderr, "/on_failure_jump_smart to %d", p + mcnt - start);
break;
case jump:
extract_number_and_incr (&mcnt, &p);
- printf ("/jump to %d", p + mcnt - start);
+ fprintf (stderr, "/jump to %d", p + mcnt - start);
break;
case succeed_n:
extract_number_and_incr (&mcnt, &p);
extract_number_and_incr (&mcnt2, &p);
- printf ("/succeed_n to %d, %d times", p - 2 + mcnt - start, mcnt2);
+ fprintf (stderr, "/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 - 2 + mcnt - start, mcnt2);
+ fprintf (stderr, "/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 - 2 + mcnt - start, mcnt2);
+ fprintf (stderr, "/set_number_at location %d to %d", p - 2 + mcnt - start, mcnt2);
break;
case wordbound:
- printf ("/wordbound");
+ fprintf (stderr, "/wordbound");
break;
case notwordbound:
- printf ("/notwordbound");
+ fprintf (stderr, "/notwordbound");
break;
case wordbeg:
- printf ("/wordbeg");
+ fprintf (stderr, "/wordbeg");
break;
case wordend:
- printf ("/wordend");
+ fprintf (stderr, "/wordend");
case syntaxspec:
- printf ("/syntaxspec");
+ fprintf (stderr, "/syntaxspec");
mcnt = *p++;
- printf ("/%d", mcnt);
+ fprintf (stderr, "/%d", mcnt);
break;
case notsyntaxspec:
- printf ("/notsyntaxspec");
+ fprintf (stderr, "/notsyntaxspec");
mcnt = *p++;
- printf ("/%d", mcnt);
+ fprintf (stderr, "/%d", mcnt);
break;
# ifdef emacs
case before_dot:
- printf ("/before_dot");
+ fprintf (stderr, "/before_dot");
break;
case at_dot:
- printf ("/at_dot");
+ fprintf (stderr, "/at_dot");
break;
case after_dot:
- printf ("/after_dot");
+ fprintf (stderr, "/after_dot");
break;
case categoryspec:
- printf ("/categoryspec");
+ fprintf (stderr, "/categoryspec");
mcnt = *p++;
- printf ("/%d", mcnt);
+ fprintf (stderr, "/%d", mcnt);
break;
case notcategoryspec:
- printf ("/notcategoryspec");
+ fprintf (stderr, "/notcategoryspec");
mcnt = *p++;
- printf ("/%d", mcnt);
+ fprintf (stderr, "/%d", mcnt);
break;
# endif /* emacs */
case begbuf:
- printf ("/begbuf");
+ fprintf (stderr, "/begbuf");
break;
case endbuf:
- printf ("/endbuf");
+ fprintf (stderr, "/endbuf");
break;
default:
- printf ("?%d", *(p-1));
+ fprintf (stderr, "?%d", *(p-1));
}
- putchar ('\n');
+ fprintf (stderr, "\n");
}
- printf ("%d:\tend of pattern.\n", p - start);
+ fprintf (stderr, "%d:\tend of pattern.\n", p - start);
}
} \
} while (0)
-/* Discard a saved register off the stack. */
-#define DISCARD_FAILURE_REG_OR_COUNT() \
-do { \
- int reg = POP_FAILURE_INT (); \
- if (reg == -1) \
- { \
- /* It's a counter. */ \
- POP_FAILURE_POINTER (); \
- reg = POP_FAILURE_INT (); \
- DEBUG_PRINT3 (" Discard counter %p = %d\n", ptr, reg); \
- } \
- else \
- { \
- POP_FAILURE_POINTER (); \
- POP_FAILURE_POINTER (); \
- DEBUG_PRINT4 (" Discard reg %d (spanning %p -> %p)\n", \
- reg, regstart[reg], regend[reg]); \
- } \
-} while (0)
-
/* Check that we are not stuck in an infinite loop. */
#define CHECK_INFINITE_LOOP(pat_cur, string_place) \
do { \
&& FAILURE_PAT (failure) <= bufp->buffer + bufp->used); \
if (FAILURE_PAT (failure) == pat_cur) \
{ \
- while (fail_stack.frame < fail_stack.avail) \
- DISCARD_FAILURE_REG_OR_COUNT (); \
- goto fail; \
+ cycle = 1; \
+ break; \
} \
DEBUG_PRINT2 (" Other pattern: %p\n", FAILURE_PAT (failure)); \
failure = NEXT_FAILURE_HANDLE(failure); \
} \
DEBUG_PRINT2 (" Other string: %p\n", FAILURE_STR (failure)); \
} while (0)
-
+
/* Push the information about the state we will need
if we ever fail back to it.
/* But patterns can have more than `MAX_REGNUM' registers. We just
ignore the excess. */
-typedef unsigned regnum_t;
+typedef int regnum_t;
/* Macros for the compile stack. */
static void
extend_range_table_work_area (work_area)
struct range_table_work_area *work_area;
-{
+{
work_area->allocated += 16 * sizeof (int);
if (work_area->table)
work_area->table
`strange' indicates a character that has more than one
case-equivalent. */
-
+
enum case_type {one_case, two_case, strange};
/* Describe the run that is in progress,
}
run_type = strange;
}
-
+
if (this_type == strange)
{
/* For a strange character, add each of its equivalents, one
unsigned int startoffset = 0;
re_opcode_t ofj =
/* Check if the loop can match the empty string. */
- (simple || !analyse_first (laststart, b, NULL, 0)) ?
- on_failure_jump : on_failure_jump_loop;
+ (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+
{
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 */
+ /* The non-greedy multiple match looks like
+ a repeat..until: we only need a conditional jump
+ at the end of the loop. */
if (emptyp) BUF_PUSH (no_op);
STORE_JUMP (emptyp ? on_failure_jump_nastyloop
: on_failure_jump, b, laststart);
{
/* 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). */
+ the end of the loop (its conditional jump). */
INSERT_JUMP (jump, laststart, b);
b += 3;
}
goto unfetch_interval;
}
- if (upper_bound == 0)
- /* 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:
- set_number_at <jump count> <upper bound>
- set_number_at <succeed_n count> <lower bound>
- succeed_n <after jump addr> <succeed_n count>
- <body of loop>
- jump_n <succeed_n addr> <jump count>
- (The upper bound and `jump_n' are omitted if
- `upper_bound' is 1, though.) */
- else
- { /* If the upper bound is > 1, we need to insert
- more at the end of the loop. */
- 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 + startoffset,
- upper_bound - 1);
- b += 5;
-
- /* The location we want to set is the second
- parameter of the `jump_n'; that is `b-2' as
- an absolute address. `laststart' will be
- the `set_number_at' we're about to insert;
- `laststart+3' the number to set, the source
- for the relative address. But we are
- inserting into the middle of the pattern --
- so everything is getting moved up by 5.
- Conclusion: (b - 2) - (laststart + 3) + 5,
- i.e., b - laststart.
-
- We insert this at the beginning of the loop
- so that if we fail during matching, we'll
- reinitialize the bounds. */
- insert_op2 (set_number_at, laststart, b - laststart,
- upper_bound - 1, b);
- b += 5;
- }
- }
+ if (upper_bound == 0)
+ /* 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:
+ set_number_at <jump count> <upper bound>
+ set_number_at <succeed_n count> <lower bound>
+ succeed_n <after jump addr> <succeed_n count>
+ <body of loop>
+ jump_n <succeed_n addr> <jump count>
+ (The upper bound and `jump_n' are omitted if
+ `upper_bound' is 1, though.) */
+ else
+ { /* If the upper bound is > 1, we need to insert
+ more at the end of the loop. */
+ 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 + startoffset,
+ upper_bound - 1);
+ b += 5;
+
+ /* The location we want to set is the second
+ parameter of the `jump_n'; that is `b-2' as
+ an absolute address. `laststart' will be
+ the `set_number_at' we're about to insert;
+ `laststart+3' the number to set, the source
+ for the relative address. But we are
+ inserting into the middle of the pattern --
+ so everything is getting moved up by 5.
+ Conclusion: (b - 2) - (laststart + 3) + 5,
+ i.e., b - laststart.
+
+ We insert this at the beginning of the loop
+ so that if we fail during matching, we'll
+ reinitialize the bounds. */
+ insert_op2 (set_number_at, laststart, b - laststart,
+ upper_bound - 1, b);
+ b += 5;
+ }
+ }
pending_exact = 0;
beg_interval = NULL;
}
case has already been handled, so we only need to look at the
fallthrough case. */
continue;
-
+
case succeed_n:
/* If N == 0, it should be an on_failure_jump_loop instead. */
DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); assert (j > 0));
}
WEAK_ALIAS (__re_search, re_search)
+/* Head address of virtual concatenation of string. */
+#define HEAD_ADDR_VSTRING(P) \
+ (((P) >= size1 ? string2 : string1))
+
/* End address of virtual concatenation of string. */
#define STOP_ADDR_VSTRING(P) \
(((P) >= size1 ? string2 + size2 : string1 + size1))
/* Update STARTPOS to the previous character boundary. */
if (multibyte)
{
- re_char *p = POS_ADDR_VSTRING (startpos);
- int len = 0;
+ re_char *p = POS_ADDR_VSTRING (startpos) + 1;
+ re_char *p0 = p;
+ re_char *phead = HEAD_ADDR_VSTRING (startpos);
/* Find the head of multibyte form. */
- while (!CHAR_HEAD_P (*p))
- p--, len++;
-
- /* Adjust it. */
-#if 0 /* XXX */
- if (MULTIBYTE_FORM_LENGTH (p, len + 1) != (len + 1))
- ;
- else
-#endif
- {
- range += len;
- if (range > 0)
- break;
+ PREV_CHAR_BOUNDARY (p, phead);
+ range += p0 - 1 - p;
+ if (range > 0)
+ break;
- startpos -= len;
- }
+ startpos -= p0 - 1 - p;
}
}
}
{
case anychar:
break;
-
+
case exactn:
p += *p + 1;
break;
else
p += 1 + CHARSET_BITMAP_SIZE (p - 1);
break;
-
+
case syntaxspec:
case notsyntaxspec:
#ifdef emacs
return 1;
}
break;
-
+
case endline:
case exactn:
{
}
}
break;
-
+
case charset_not:
switch (SWITCH_ENUM_CAST (*p1))
{
assert (!REG_UNSET (regstart[*p]));
/* Strictly speaking, there should be code such as:
-
+
assert (REG_UNSET (regend[*p]));
PUSH_FAILURE_REGSTOP ((unsigned int)*p);
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.
+ 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*.
mcnt, p + mcnt);
assert ((re_opcode_t)p[-4] == no_op);
- CHECK_INFINITE_LOOP (p - 4, d);
- PUSH_FAILURE_POINT (p - 3, d);
+ {
+ int cycle = 0;
+ CHECK_INFINITE_LOOP (p - 4, d);
+ if (!cycle)
+ /* If there's a cycle, just continue without pushing
+ this failure point. The failure point is the "try again"
+ option, which shouldn't be tried.
+ We want (x?)*?y\1z to match both xxyz and xxyxz. */
+ 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:
EXTRACT_NUMBER_AND_INCR (mcnt, p);
DEBUG_PRINT3 ("EXECUTING on_failure_jump_loop %d (to %p):\n",
mcnt, p + mcnt);
-
- CHECK_INFINITE_LOOP (p - 3, d);
- PUSH_FAILURE_POINT (p - 3, d);
+ {
+ int cycle = 0;
+ CHECK_INFINITE_LOOP (p - 3, d);
+ if (cycle)
+ /* If there's a cycle, get out of the loop, as if the matching
+ had failed. We used to just `goto fail' here, but that was
+ aborting the search a bit too early: we want to keep the
+ empty-loop-match and keep matching after the loop.
+ We want (x?)*y\1z to match both xxyz and xxyxz. */
+ p += mcnt;
+ else
+ PUSH_FAILURE_POINT (p - 3, d);
+ }
break;
PREFETCH ();
c2 = RE_STRING_CHAR (d, dend - d);
s2 = SYNTAX (c2);
-
+
/* Case 2: S2 is not Sword. */
if (s2 != Sword)
goto fail;
const regex_t *__restrict preg;
const char *__restrict string;
size_t nmatch;
- regmatch_t pmatch[];
+ regmatch_t pmatch[__restrict_arr];
int eflags;
{
int ret;
WEAK_ALIAS (__regfree, regfree)
#endif /* not emacs */
+
+/* arch-tag: 4ffd68ba-2a9e-435b-a21a-018990f9eeb2
+ (do not change this comment) */