+\f
+/* Failure stack declarations and macros; both re_compile_fastmap and
+ re_match_2 use a failure stack. These have to be macros because of
+ REGEX_ALLOCATE_STACK. */
+
+
+/* Approximate number of failure points for which to initially allocate space
+ when matching. If this number is exceeded, we allocate more
+ space, so it is not a hard limit. */
+#ifndef INIT_FAILURE_ALLOC
+# define INIT_FAILURE_ALLOC 20
+#endif
+
+/* Roughly the maximum number of failure points on the stack. Would be
+ exactly that if always used TYPICAL_FAILURE_SIZE items each time we failed.
+ This is a variable only so users of regex can assign to it; we never
+ change it ourselves. */
+# if defined MATCH_MAY_ALLOCATE
+/* Note that 4400 was enough to cause a crash on Alpha OSF/1,
+ whose default stack limit is 2mb. In order for a larger
+ value to work reliably, you have to try to make it accord
+ with the process stack limit. */
+size_t re_max_failures = 40000;
+# else
+size_t re_max_failures = 4000;
+# endif
+
+union fail_stack_elt
+{
+ re_char *pointer;
+ /* This should be the biggest `int' that's no bigger than a pointer. */
+ long integer;
+};
+
+typedef union fail_stack_elt fail_stack_elt_t;
+
+typedef struct
+{
+ fail_stack_elt_t *stack;
+ size_t size;
+ size_t avail; /* Offset of next open position. */
+ size_t frame; /* Offset of the cur constructed frame. */
+} fail_stack_type;
+
+#define FAIL_STACK_EMPTY() (fail_stack.frame == 0)
+#define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
+
+
+/* Define macros to initialize and free the failure stack.
+ Do `return -2' if the alloc fails. */
+
+#ifdef MATCH_MAY_ALLOCATE
+# define INIT_FAIL_STACK() \
+ do { \
+ fail_stack.stack = (fail_stack_elt_t *) \
+ REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * TYPICAL_FAILURE_SIZE \
+ * sizeof (fail_stack_elt_t)); \
+ \
+ if (fail_stack.stack == NULL) \
+ return -2; \
+ \
+ fail_stack.size = INIT_FAILURE_ALLOC; \
+ fail_stack.avail = 0; \
+ fail_stack.frame = 0; \
+ } while (0)
+
+# define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack)
+#else
+# define INIT_FAIL_STACK() \
+ do { \
+ fail_stack.avail = 0; \
+ fail_stack.frame = 0; \
+ } while (0)
+
+# define RESET_FAIL_STACK() ((void)0)
+#endif
+
+
+/* Double the size of FAIL_STACK, up to a limit
+ which allows approximately `re_max_failures' items.
+
+ Return 1 if succeeds, and 0 if either ran out of memory
+ allocating space for it or it was already too large.
+
+ REGEX_REALLOCATE_STACK requires `destination' be declared. */
+
+/* Factor to increase the failure stack size by
+ when we increase it.
+ This used to be 2, but 2 was too wasteful
+ because the old discarded stacks added up to as much space
+ were as ultimate, maximum-size stack. */
+#define FAIL_STACK_GROWTH_FACTOR 4
+
+#define GROW_FAIL_STACK(fail_stack) \
+ (((fail_stack).size * sizeof (fail_stack_elt_t) \
+ >= re_max_failures * TYPICAL_FAILURE_SIZE) \
+ ? 0 \
+ : ((fail_stack).stack \
+ = (fail_stack_elt_t *) \
+ REGEX_REALLOCATE_STACK ((fail_stack).stack, \
+ (fail_stack).size * sizeof (fail_stack_elt_t), \
+ MIN (re_max_failures * TYPICAL_FAILURE_SIZE, \
+ ((fail_stack).size * sizeof (fail_stack_elt_t) \
+ * FAIL_STACK_GROWTH_FACTOR))), \
+ \
+ (fail_stack).stack == NULL \
+ ? 0 \
+ : ((fail_stack).size \
+ = (MIN (re_max_failures * TYPICAL_FAILURE_SIZE, \
+ ((fail_stack).size * sizeof (fail_stack_elt_t) \
+ * FAIL_STACK_GROWTH_FACTOR)) \
+ / sizeof (fail_stack_elt_t)), \
+ 1)))
+
+
+/* Push a pointer value onto the failure stack.
+ Assumes the variable `fail_stack'. Probably should only
+ be called from within `PUSH_FAILURE_POINT'. */
+#define PUSH_FAILURE_POINTER(item) \
+ fail_stack.stack[fail_stack.avail++].pointer = (item)
+
+/* This pushes an integer-valued item onto the failure stack.
+ Assumes the variable `fail_stack'. Probably should only
+ be called from within `PUSH_FAILURE_POINT'. */
+#define PUSH_FAILURE_INT(item) \
+ fail_stack.stack[fail_stack.avail++].integer = (item)
+
+/* Push a fail_stack_elt_t value onto the failure stack.
+ Assumes the variable `fail_stack'. Probably should only
+ be called from within `PUSH_FAILURE_POINT'. */
+#define PUSH_FAILURE_ELT(item) \
+ fail_stack.stack[fail_stack.avail++] = (item)
+
+/* These three POP... operations complement the three PUSH... operations.
+ All assume that `fail_stack' is nonempty. */
+#define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
+#define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
+#define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
+
+/* Individual items aside from the registers. */
+#define NUM_NONREG_ITEMS 3
+
+/* Used to examine the stack (to detect infinite loops). */
+#define FAILURE_PAT(h) fail_stack.stack[(h) - 1].pointer
+#define FAILURE_STR(h) (fail_stack.stack[(h) - 2].pointer)
+#define NEXT_FAILURE_HANDLE(h) fail_stack.stack[(h) - 3].integer
+#define TOP_FAILURE_HANDLE() fail_stack.frame
+
+
+#define ENSURE_FAIL_STACK(space) \
+while (REMAINING_AVAIL_SLOTS <= space) { \
+ if (!GROW_FAIL_STACK (fail_stack)) \
+ return -2; \
+ DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", (fail_stack).size);\
+ DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
+}
+
+/* Push register NUM onto the stack. */
+#define PUSH_FAILURE_REG(num) \
+do { \
+ char *destination; \
+ ENSURE_FAIL_STACK(3); \
+ DEBUG_PRINT4 (" Push reg %d (spanning %p -> %p)\n", \
+ num, regstart[num], regend[num]); \
+ PUSH_FAILURE_POINTER (regstart[num]); \
+ PUSH_FAILURE_POINTER (regend[num]); \
+ PUSH_FAILURE_INT (num); \
+} while (0)
+
+/* Change the counter's value to VAL, but make sure that it will
+ be reset when backtracking. */
+#define PUSH_NUMBER(ptr,val) \
+do { \
+ char *destination; \
+ int c; \
+ ENSURE_FAIL_STACK(3); \
+ EXTRACT_NUMBER (c, ptr); \
+ DEBUG_PRINT4 (" Push number %p = %d -> %d\n", ptr, c, val); \
+ PUSH_FAILURE_INT (c); \
+ PUSH_FAILURE_POINTER (ptr); \
+ PUSH_FAILURE_INT (-1); \
+ STORE_NUMBER (ptr, val); \
+} while (0)
+
+/* Pop a saved register off the stack. */
+#define POP_FAILURE_REG_OR_COUNT() \
+do { \
+ int reg = POP_FAILURE_INT (); \
+ if (reg == -1) \
+ { \
+ /* It's a counter. */ \
+ /* Here, we discard `const', making re_match non-reentrant. */ \
+ unsigned char *ptr = (unsigned char*) POP_FAILURE_POINTER (); \
+ reg = POP_FAILURE_INT (); \
+ STORE_NUMBER (ptr, reg); \
+ DEBUG_PRINT3 (" Pop counter %p = %d\n", ptr, reg); \
+ } \
+ else \
+ { \
+ regend[reg] = POP_FAILURE_POINTER (); \
+ regstart[reg] = POP_FAILURE_POINTER (); \
+ DEBUG_PRINT4 (" Pop 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 { \
+ int failure = TOP_FAILURE_HANDLE(); \
+ /* Check for infinite matching loops */ \
+ while (failure > 0 && \
+ (FAILURE_STR (failure) == string_place \
+ || FAILURE_STR (failure) == NULL)) \
+ { \
+ assert (FAILURE_PAT (failure) >= bufp->buffer \
+ && FAILURE_PAT (failure) <= bufp->buffer + bufp->used); \
+ if (FAILURE_PAT (failure) == pat_cur) \
+ goto fail; \
+ 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.
+
+ Requires variables fail_stack, regstart, regend and
+ num_regs be declared. GROW_FAIL_STACK requires `destination' be
+ declared.
+
+ Does `return FAILURE_CODE' if runs out of memory. */
+
+#define PUSH_FAILURE_POINT(pattern, string_place) \
+do { \
+ char *destination; \
+ /* Must be int, so when we don't save any registers, the arithmetic \
+ of 0 + -1 isn't done as unsigned. */ \
+ \
+ DEBUG_STATEMENT (nfailure_points_pushed++); \
+ DEBUG_PRINT1 ("\nPUSH_FAILURE_POINT:\n"); \
+ DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail); \
+ DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
+ \
+ ENSURE_FAIL_STACK (NUM_NONREG_ITEMS); \
+ \
+ DEBUG_PRINT1 ("\n"); \
+ \
+ DEBUG_PRINT2 (" Push frame index: %d\n", fail_stack.frame); \
+ PUSH_FAILURE_INT (fail_stack.frame); \
+ \
+ DEBUG_PRINT2 (" Push string %p: `", string_place); \
+ DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, size2);\
+ DEBUG_PRINT1 ("'\n"); \
+ PUSH_FAILURE_POINTER (string_place); \
+ \
+ DEBUG_PRINT2 (" Push pattern %p: ", pattern); \
+ DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern, pend); \
+ PUSH_FAILURE_POINTER (pattern); \
+ \
+ /* Close the frame by moving the frame pointer past it. */ \
+ fail_stack.frame = fail_stack.avail; \
+} while (0)
+
+/* Estimate the size of data pushed by a typical failure stack entry.
+ An estimate is all we need, because all we use this for
+ is to choose a limit for how big to make the failure stack. */
+
+#define TYPICAL_FAILURE_SIZE 20
+
+/* How many items can still be added to the stack without overflowing it. */
+#define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
+
+
+/* Pops what PUSH_FAIL_STACK pushes.
+
+ We restore into the parameters, all of which should be lvalues:
+ STR -- the saved data position.
+ PAT -- the saved pattern position.
+ REGSTART, REGEND -- arrays of string positions.
+
+ Also assumes the variables `fail_stack' and (if debugging), `bufp',
+ `pend', `string1', `size1', `string2', and `size2'. */
+
+#define POP_FAILURE_POINT(str, pat) \
+do { \
+ assert (!FAIL_STACK_EMPTY ()); \
+ \
+ /* Remove failure points and point to how many regs pushed. */ \
+ DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
+ DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
+ DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
+ \
+ /* Pop the saved registers. */ \
+ while (fail_stack.frame < fail_stack.avail) \
+ POP_FAILURE_REG_OR_COUNT (); \
+ \
+ pat = POP_FAILURE_POINTER (); \
+ DEBUG_PRINT2 (" Popping pattern %p: ", pat); \
+ DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
+ \
+ /* If the saved string location is NULL, it came from an \
+ on_failure_keep_string_jump opcode, and we want to throw away the \
+ saved NULL, thus retaining our current position in the string. */ \
+ str = POP_FAILURE_POINTER (); \
+ DEBUG_PRINT2 (" Popping string %p: `", str); \
+ DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
+ DEBUG_PRINT1 ("'\n"); \
+ \
+ fail_stack.frame = POP_FAILURE_INT (); \
+ DEBUG_PRINT2 (" Popping frame index: %d\n", fail_stack.frame); \
+ \
+ assert (fail_stack.avail >= 0); \
+ assert (fail_stack.frame <= fail_stack.avail); \
+ \
+ DEBUG_STATEMENT (nfailure_points_popped++); \
+} while (0) /* POP_FAILURE_POINT */
+
+
+\f
+/* Registers are set to a sentinel when they haven't yet matched. */
+#define REG_UNSET(e) ((e) == NULL)
+\f
+/* Subroutine declarations and macros for regex_compile. */
+
+static reg_errcode_t regex_compile _RE_ARGS ((re_char *pattern, size_t size,
+ reg_syntax_t syntax,
+ struct re_pattern_buffer *bufp));
+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 ((re_char *pattern,
+ re_char *p,
+ reg_syntax_t syntax));
+static boolean at_endline_loc_p _RE_ARGS ((re_char *p,
+ re_char *pend,
+ reg_syntax_t syntax));
+static re_char *skip_one_char _RE_ARGS ((re_char *p));
+static int analyse_first _RE_ARGS ((re_char *p, re_char *pend,
+ char *fastmap, const int multibyte));
+
+/* Fetch the next character in the uncompiled pattern---translating it
+ if necessary. */
+#define PATFETCH(c) \
+ do { \
+ PATFETCH_RAW (c); \
+ c = TRANSLATE (c); \
+ } while (0)