regex.c

linux平台中

/* We actually push this many items.  */
#define NUM_FAILURE_ITEMS				\
  (((0							\
     ? 0 : highest_active_reg - lowest_active_reg + 1)	\
    * NUM_REG_ITEMS)					\
   + NUM_NONREG_ITEMS)

/* 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.
     LOW_REG, HIGH_REG -- the highest and lowest active registers.
     REGSTART, REGEND -- arrays of string positions.
     REG_INFO -- array of information about each subexpression.

   Also assumes the variables `fail_stack' and (if debugging), `bufp',
   `pend', `string1', `size1', `string2', and `size2'.  */
#define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
{									\
  DEBUG_STATEMENT (unsigned failure_id;)				\
  active_reg_t this_reg;						\
  const US_CHAR_TYPE *string_temp;					\
									\
  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);	\
									\
  assert (fail_stack.avail >= NUM_NONREG_ITEMS);			\
									\
  DEBUG_POP (&failure_id);						\
  DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);		\
									\
  /* 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.  */	\
  string_temp = POP_FAILURE_POINTER ();					\
  if (string_temp != NULL)						\
    str = (const CHAR_TYPE *) string_temp;				\
									\
  DEBUG_PRINT2 ("  Popping string %p: `", str);				\
  DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);	\
  DEBUG_PRINT1 ("'\n");							\
									\
  pat = (US_CHAR_TYPE *) POP_FAILURE_POINTER ();			\
  DEBUG_PRINT2 ("  Popping pattern %p:\n", pat);			\
  DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);			\
									\
  /* Restore register info.  */						\
  high_reg = (active_reg_t) POP_FAILURE_INT ();				\
  DEBUG_PRINT2 ("  Popping high active reg: %ld\n", high_reg);		\
									\
  low_reg = (active_reg_t) POP_FAILURE_INT ();				\
  DEBUG_PRINT2 ("  Popping  low active reg: %ld\n", low_reg);		\
									\
  if (1)								\
    for (this_reg = high_reg; this_reg >= low_reg; this_reg--)		\
      {									\
	DEBUG_PRINT2 ("    Popping reg: %ld\n", this_reg);		\
									\
	reg_info[this_reg].word = POP_FAILURE_ELT ();			\
	DEBUG_PRINT2 ("      info: %p\n",				\
		      reg_info[this_reg].word.pointer);			\
									\
	regend[this_reg] = (const CHAR_TYPE *) POP_FAILURE_POINTER ();	\
	DEBUG_PRINT2 ("      end: %p\n", regend[this_reg]);		\
									\
	regstart[this_reg] = (const CHAR_TYPE *) POP_FAILURE_POINTER ();\
	DEBUG_PRINT2 ("      start: %p\n", regstart[this_reg]);		\
      }									\
  else									\
    {									\
      for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
	{								\
	  reg_info[this_reg].word.integer = 0;				\
	  regend[this_reg] = 0;						\
	  regstart[this_reg] = 0;					\
	}								\
      highest_active_reg = high_reg;					\
    }									\
									\
  set_regs_matched_done = 0;						\
  DEBUG_STATEMENT (nfailure_points_popped++);				\
} /* POP_FAILURE_POINT */


/* Structure for per-register (a.k.a. per-group) information.
   Other register information, such as the
   starting and ending positions (which are addresses), and the list of
   inner groups (which is a bits list) are maintained in separate
   variables.

   We are making a (strictly speaking) nonportable assumption here: that
   the compiler will pack our bit fields into something that fits into
   the type of `word', i.e., is something that fits into one item on the
   failure stack.  */


/* Declarations and macros for re_match_2.  */

typedef union
{
  fail_stack_elt_t word;
  struct
  {
      /* This field is one if this group can match the empty string,
         zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
#define MATCH_NULL_UNSET_VALUE 3
    unsigned match_null_string_p : 2;
    unsigned is_active : 1;
    unsigned matched_something : 1;
    unsigned ever_matched_something : 1;
  } bits;
} register_info_type;

#define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
#define IS_ACTIVE(R)  ((R).bits.is_active)
#define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
#define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)


/* Call this when have matched a real character; it sets `matched' flags
   for the subexpressions which we are currently inside.  Also records
   that those subexprs have matched.  */
#define SET_REGS_MATCHED()						\
  do									\
    {									\
      if (!set_regs_matched_done)					\
	{								\
	  active_reg_t r;						\
	  set_regs_matched_done = 1;					\
	  for (r = lowest_active_reg; r <= highest_active_reg; r++)	\
	    {								\
	      MATCHED_SOMETHING (reg_info[r])				\
		= EVER_MATCHED_SOMETHING (reg_info[r])			\
		= 1;							\
	    }								\
	}								\
    }									\
  while (0)

/* Registers are set to a sentinel when they haven't yet matched.  */
static CHAR_TYPE reg_unset_dummy;
#define REG_UNSET_VALUE (&reg_unset_dummy)
#define REG_UNSET(e) ((e) == REG_UNSET_VALUE)

/* Subroutine declarations and macros for regex_compile.  */

static reg_errcode_t regex_compile _RE_ARGS ((const char *pattern, size_t size,
					      reg_syntax_t syntax,
					      struct re_pattern_buffer *bufp));
static void store_op1 _RE_ARGS ((re_opcode_t op, US_CHAR_TYPE *loc, int arg));
static void store_op2 _RE_ARGS ((re_opcode_t op, US_CHAR_TYPE *loc,
				 int arg1, int arg2));
static void insert_op1 _RE_ARGS ((re_opcode_t op, US_CHAR_TYPE *loc,
				  int arg, US_CHAR_TYPE *end));
static void insert_op2 _RE_ARGS ((re_opcode_t op, US_CHAR_TYPE *loc,
				  int arg1, int arg2, US_CHAR_TYPE *end));
static boolean at_begline_loc_p _RE_ARGS ((const CHAR_TYPE *pattern,
					   const CHAR_TYPE *p,
					   reg_syntax_t syntax));
static boolean at_endline_loc_p _RE_ARGS ((const CHAR_TYPE *p,
					   const CHAR_TYPE *pend,
					   reg_syntax_t syntax));
#ifdef MBS_SUPPORT
static reg_errcode_t compile_range _RE_ARGS ((CHAR_TYPE range_start,
					      const CHAR_TYPE **p_ptr,
					      const CHAR_TYPE *pend,
					      char *translate,
					      reg_syntax_t syntax,
					      US_CHAR_TYPE *b,
					      CHAR_TYPE *char_set));
static void insert_space _RE_ARGS ((int num, CHAR_TYPE *loc, CHAR_TYPE *end));
#else
static reg_errcode_t compile_range _RE_ARGS ((unsigned int range_start,
					      const CHAR_TYPE **p_ptr,
					      const CHAR_TYPE *pend,
					      char *translate,
					      reg_syntax_t syntax,
					      US_CHAR_TYPE *b));
#endif /* MBS_SUPPORT */

/* 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').  */
/* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
   because it is impossible to allocate 4GB array for some encodings
   which have 4 byte character_set like UCS4.  */
#ifndef PATFETCH
# ifdef MBS_SUPPORT
#  define PATFETCH(c)							\
  do {if (p == pend) return REG_EEND;					\
    c = (US_CHAR_TYPE) *p++;						\
    if (translate && (c <= 0xff)) c = (US_CHAR_TYPE) translate[c];	\
  } while (0)
# else
#  define PATFETCH(c)							\
  do {if (p == pend) return REG_EEND;					\
    c = (unsigned char) *p++;						\
    if (translate) c = (unsigned char) translate[c];			\
  } while (0)
# endif /* MBS_SUPPORT */
#endif

/* Fetch the next character in the uncompiled pattern, with no
   translation.  */
#define PATFETCH_RAW(c)							\
  do {if (p == pend) return REG_EEND;					\
    c = (US_CHAR_TYPE) *p++; 						\
  } 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
   `char *', to avoid warnings when a string constant is passed.  But
   when we use a character as a subscript we must make it unsigned.  */
/* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
   because it is impossible to allocate 4GB array for some encodings
   which have 4 byte character_set like UCS4.  */
#ifndef TRANSLATE
# ifdef MBS_SUPPORT
#  define TRANSLATE(d) \
  ((translate && ((US_CHAR_TYPE) (d)) <= 0xff) \
   ? (char) translate[(unsigned char) (d)] : (d))
#else
#  define TRANSLATE(d) \
  (translate ? (char) translate[(unsigned char) (d)] : (d))
# endif /* MBS_SUPPORT */
#endif


/* Macros for outputting the compiled pattern into `buffer'.  */

/* If the buffer isn't allocated when it comes in, use this.  */
#define INIT_BUF_SIZE  (32 * sizeof(US_CHAR_TYPE))

/* Make sure we have at least N more bytes of space in buffer.  */
#ifdef MBS_SUPPORT
# define GET_BUFFER_SPACE(n)						\
    while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR	\
            + (n)*sizeof(CHAR_TYPE)) > bufp->allocated)			\
      EXTEND_BUFFER ()
#else
# define GET_BUFFER_SPACE(n)						\
    while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)	\
      EXTEND_BUFFER ()
#endif /* MBS_SUPPORT */

/* Make sure we have one more byte of buffer space and then add C to it.  */
#define BUF_PUSH(c)							\
  do {									\
    GET_BUFFER_SPACE (1);						\
    *b++ = (US_CHAR_TYPE) (c);						\
  } while (0)


/* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
#define BUF_PUSH_2(c1, c2)						\
  do {									\
    GET_BUFFER_SPACE (2);						\
    *b++ = (US_CHAR_TYPE) (c1);					\
    *b++ = (US_CHAR_TYPE) (c2);					\
  } while (0)


/* As with BUF_PUSH_2, except for three bytes.  */
#define BUF_PUSH_3(c1, c2, c3)						\
  do {									\
    GET_BUFFER_SPACE (3);						\
    *b++ = (US_CHAR_TYPE) (c1);					\
    *b++ = (US_CHAR_TYPE) (c2);					\
    *b++ = (US_CHAR_TYPE) (c3);					\
  } while (0)

/* Store a jump with opcode OP at LOC to location TO.  We store a
   relative address offset by the three bytes the jump itself occupies.  */
#define STORE_JUMP(op, loc, to) \
  store_op1 (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))

/* Likewise, for a two-argument jump.  */
#define STORE_JUMP2(op, loc, to, arg) \
  store_op2 (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)

/* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
#define INSERT_JUMP(op, loc, to) \
  insert_op1 (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)

/* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
#define INSERT_JUMP2(op, loc, to, arg) \
  insert_op2 (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
	      arg, b)


/* This is not an arbitrary limit: the arguments which represent offsets
   into the pattern are two bytes long.  So if 2^16 bytes turns out to
   be too small, many things would have to change.  */
/* Any other compiler which, like MSC, has allocation limit below 2^16
   bytes will have to use approach similar to what was done below for
   MSC and drop MAX_BUF_SIZE a bit.  Otherwise you may end up
   reallocating to 0 bytes.  Such thing is not going to work too well.
   You have been warned!!  */
#if defined _MSC_VER  && !defined WIN32
/* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
   The REALLOC define eliminates a flurry of conversion warnings,
   but is not required. */
# define MAX_BUF_SIZE  65500L
# define REALLOC(p,s) realloc ((p), (size_t) (s))
#else
# define MAX_BUF_SIZE (1L << 16)
# define REALLOC(p,s) realloc ((p), (s))
#endif

/* Extend the buffer by twice its current size via realloc and
   reset the pointers that pointed into the old block to point to the
   correct places in the new one.  If extending the buffer results in it
   being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
#if __BOUNDED_POINTERS__
# define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
# define MOVE_BUFFER_POINTER(P) \
  (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
# define ELSE_EXTEND_BUFFER_HIGH_BOUND		\
  else						\
    {						\
      SET_HIGH_BOUND (b);			\
      SET_HIGH_BOUND (begalt);			\
      if (fixup_alt_jump)			\
	SET_HIGH_BOUND (fixup_alt_jump);	\
      if (laststart)				\
	SET_HIGH_BOUND (laststart);		\
      if (pending_exact)			\
	SET_HIGH_BOUND (pending_exact);		\
    }
#else
# define MOVE_BUFFER_POINTER(P) (P) += incr
# define ELSE_EXTEND_BUFFER_HIGH_BOUND
#endif

#ifdef MBS_SUPPORT
# define EXTEND_BUFFER()						\
  do {									\
    US_CHAR_TYPE *old_buffer = COMPILED_BUFFER_VAR;			\
    int wchar_count;							\
    if (bufp->allocated + sizeof(US_CHAR_TYPE) > MAX_BUF_SIZE)		\
      return REG_ESIZE;							\
    bufp->allocated <<= 1;						\
    if (bufp->allocated > MAX_BUF_SIZE)					\
      bufp->allocated = MAX_BUF_SIZE;					\
    /* How many characters the new buffer can have?  */			\
    wchar_count = bufp->allocated / sizeof(US_CHAR_TYPE);		\
    if (wchar_count == 0) wchar_count = 1;				\
    /* Truncate the buffer to CHAR_TYPE align.  */			\
    bufp->allocated = wchar_count * sizeof(US_CHAR_TYPE);		\
    RETALLOC (COMPILED_BUFFER_VAR, wchar_count, US_CHAR_TYPE);		\
    bufp->buffer = (char*)COMPILED_BUFFER_VAR;				\
    if (COMPILED_BUFFER_VAR == NULL)					\
      return REG_ESPACE;						\
    /* If the buffer moved, move all the pointers into it.  */		\
    if (old_buffer != COMPILED_BUFFER_VAR)				\
      {									\
	int incr = COMPILED_BUFFER_VAR - old_buffer;			\
	MOVE_BUFFER_POINTER (b);					\
	MOVE_BUFFER_POINTER (begalt);					\
	if (fixup_alt_jump)						\
	  MOVE_BUFFER_POINTER (fixup_alt_jump);				\
	if (laststart)							\
	  MOVE_BUFFER_POINTER (laststart);				\
	if (pending_exact)						\
	  MOVE_BUFFER_POINTER (pending_exact);				\
      }									\
    ELSE_EXTEND_BUFFER_HIGH_BOUND					\
  } while (0)
#else
# define EXTEND_BUFFER()						\
  do {									\
    US_CHAR_TYPE *old_buffer = COMPILED_BUFFER_VAR;			\
    if (bufp->allocated == MAX_BUF_SIZE)				\
      return REG_ESIZE;							\
    bufp->allocated <<= 1;						\
    if (bufp->allocated > MAX_BUF_SIZE)					\
      bufp->allocated = MAX_BUF_SIZE;					\
    bufp->buffer = (US_CHAR_TYPE *) REALLOC (COMPILED_BUFFER_VAR,	\
						bufp->allocated);	\
    if (COMPILED_BUFFER_VAR == NULL)					\
      return REG_ESPACE;						\
    /* If the buffer moved, move all the pointers into it.  */		\
    if (old_buffer != COMPILED_BUFFER_VAR)				\
      {									\
	int incr = COMPILED_BUFFER_VAR - old_buffer;			\
	MOVE_BUFFER_POINTER (b);					\
	MOVE_BUFFER_POINTER (begalt);					\
	if (fixup_alt_jump)						\
	  MOVE_BUFFER_POINTER (fixup_alt_jump);				\
	if (laststart)							\
	  MOVE_BUFFER_POINTER (laststart);				\
	if (pending_exact)						\
	  MOVE_BUFFER_POINTER (pending_exact);				\
      }									\
    ELSE_EXTEND_BUFFER_HIGH_BOUND					\
  } while (0)
#endif /* MBS_SUPPORT */

/* Since we have one byte reserved for the register number argument to
   {start,stop}_memory, the maximum number of groups we can report
   things about