regex.c

linux平台中

#define true 1

static int re_match_2_internal PARAMS ((struct re_pattern_buffer *bufp,
					const char *string1, int size1,
					const char *string2, int size2,
					int pos,
					struct re_registers *regs,
					int stop));

/* These are the command codes that appear in compiled regular
   expressions.  Some opcodes are followed by argument bytes.  A
   command code can specify any interpretation whatsoever for its
   arguments.  Zero bytes may appear in the compiled regular expression.  */

typedef enum
{
  no_op = 0,

  /* Succeed right away--no more backtracking.  */
  succeed,

        /* Followed by one byte giving n, then by n literal bytes.  */
  exactn,

#ifdef MBS_SUPPORT
	/* Same as exactn, but contains binary data.  */
  exactn_bin,
#endif

        /* Matches any (more or less) character.  */
  anychar,

        /* Matches any one char belonging to specified set.  First
           following byte is number of bitmap bytes.  Then come bytes
           for a bitmap saying which chars are in.  Bits in each byte
           are ordered low-bit-first.  A character is in the set if its
           bit is 1.  A character too large to have a bit in the map is
           automatically not in the set.  */
        /* ifdef MBS_SUPPORT, following element is length of character
	   classes, length of collating symbols, length of equivalence
	   classes, length of character ranges, and length of characters.
	   Next, character class element, collating symbols elements,
	   equivalence class elements, range elements, and character
	   elements follow.
	   See regex_compile function.  */
  charset,

        /* Same parameters as charset, but match any character that is
           not one of those specified.  */
  charset_not,

        /* Start remembering the text that is matched, for storing in a
           register.  Followed by one byte with the register number, in
           the range 0 to one less than the pattern buffer's re_nsub
           field.  Then followed by one byte with the number of groups
           inner to this one.  (This last has to be part of the
           start_memory only because we need it in the on_failure_jump
           of re_match_2.)  */
  start_memory,

        /* Stop remembering the text that is matched and store it in a
           memory register.  Followed by one byte with the register
           number, in the range 0 to one less than `re_nsub' in the
           pattern buffer, and one byte with the number of inner groups,
           just like `start_memory'.  (We need the number of inner
           groups here because we don't have any easy way of finding the
           corresponding start_memory when we're at a stop_memory.)  */
  stop_memory,

        /* Match a duplicate of something remembered. Followed by one
           byte containing the register number.  */
  duplicate,

        /* Fail unless at beginning of line.  */
  begline,

        /* Fail unless at end of line.  */
  endline,

        /* Succeeds if at beginning of buffer (if emacs) or at beginning
           of string to be matched (if not).  */
  begbuf,

        /* Analogously, for end of buffer/string.  */
  endbuf,

        /* Followed by two byte relative address to which to jump.  */
  jump,

	/* Same as jump, but marks the end of an alternative.  */
  jump_past_alt,

        /* Followed by two-byte relative address of place to resume at
           in case of failure.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  on_failure_jump,

        /* Like on_failure_jump, but pushes a placeholder instead of the
           current string position when executed.  */
  on_failure_keep_string_jump,

        /* Throw away latest failure point and then jump to following
           two-byte relative address.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  pop_failure_jump,

        /* Change to pop_failure_jump if know won't have to backtrack to
           match; otherwise change to jump.  This is used to jump
           back to the beginning of a repeat.  If what follows this jump
           clearly won't match what the repeat does, such that we can be
           sure that there is no use backtracking out of repetitions
           already matched, then we change it to a pop_failure_jump.
           Followed by two-byte address.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  maybe_pop_jump,

        /* Jump to following two-byte address, and push a dummy failure
           point. This failure point will be thrown away if an attempt
           is made to use it for a failure.  A `+' construct makes this
           before the first repeat.  Also used as an intermediary kind
           of jump when compiling an alternative.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  dummy_failure_jump,

	/* Push a dummy failure point and continue.  Used at the end of
	   alternatives.  */
  push_dummy_failure,

        /* Followed by two-byte relative address and two-byte number n.
           After matching N times, jump to the address upon failure.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  succeed_n,

        /* Followed by two-byte relative address, and two-byte number n.
           Jump to the address N times, then fail.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  jump_n,

        /* Set the following two-byte relative address to the
           subsequent two-byte number.  The address *includes* the two
           bytes of number.  */
        /* ifdef MBS_SUPPORT, the size of address is 1.  */
  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.  */

	/* 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
#endif /* emacs */
} re_opcode_t;

/* Common operations on the compiled pattern.  */

/* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
/* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */

#ifdef MBS_SUPPORT
# define STORE_NUMBER(destination, number)				\
  do {									\
    *(destination) = (US_CHAR_TYPE)(number);				\
  } while (0)
#else
# define STORE_NUMBER(destination, number)				\
  do {									\
    (destination)[0] = (number) & 0377;					\
    (destination)[1] = (number) >> 8;					\
  } while (0)
#endif /* MBS_SUPPORT */

/* Same as STORE_NUMBER, except increment DESTINATION to
   the byte after where the number is stored.  Therefore, DESTINATION
   must be an lvalue.  */
/* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */

#define STORE_NUMBER_AND_INCR(destination, number)			\
  do {									\
    STORE_NUMBER (destination, number);					\
    (destination) += OFFSET_ADDRESS_SIZE;				\
  } while (0)

/* Put into DESTINATION a number stored in two contiguous bytes starting
   at SOURCE.  */
/* ifdef MBS_SUPPORT, we store NUMBER in 1 element.  */

#ifdef MBS_SUPPORT
# define EXTRACT_NUMBER(destination, source)				\
  do {									\
    (destination) = *(source);						\
  } while (0)
#else
# define EXTRACT_NUMBER(destination, source)				\
  do {									\
    (destination) = *(source) & 0377;					\
    (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;		\
  } while (0)
#endif

#ifdef DEBUG
static void extract_number _RE_ARGS ((int *dest, US_CHAR_TYPE *source));
static void
extract_number (dest, source)
    int *dest;
    US_CHAR_TYPE *source;
{
#ifdef MBS_SUPPORT
  *dest = *source;
#else
  int temp = SIGN_EXTEND_CHAR (*(source + 1));
  *dest = *source & 0377;
  *dest += temp << 8;
#endif
}

# ifndef EXTRACT_MACROS /* To debug the macros.  */
#  undef EXTRACT_NUMBER
#  define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
# endif /* not EXTRACT_MACROS */

#endif /* DEBUG */

/* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
   SOURCE must be an lvalue.  */

#define EXTRACT_NUMBER_AND_INCR(destination, source)			\
  do {									\
    EXTRACT_NUMBER (destination, source);				\
    (source) += OFFSET_ADDRESS_SIZE; 					\
  } while (0)

#ifdef DEBUG
static void extract_number_and_incr _RE_ARGS ((int *destination,
					       US_CHAR_TYPE **source));
static void
extract_number_and_incr (destination, source)
    int *destination;
    US_CHAR_TYPE **source;
{
  extract_number (destination, *source);
  *source += OFFSET_ADDRESS_SIZE;
}

# ifndef EXTRACT_MACROS
#  undef EXTRACT_NUMBER_AND_INCR
#  define EXTRACT_NUMBER_AND_INCR(dest, src) \
  extract_number_and_incr (&dest, &src)
# endif /* not EXTRACT_MACROS */

#endif /* DEBUG */

/* If DEBUG is defined, Regex prints many voluminous messages about what
   it is doing (if the variable `debug' is nonzero).  If linked with the
   main program in `iregex.c', you can enter patterns and strings
   interactively.  And if linked with the main program in `main.c' and
   the other test files, you can run the already-written tests.  */

#ifdef DEBUG

/* We use standard I/O for debugging.  */
# include <stdio.h>

/* It is useful to test things that ``must'' be true when debugging.  */
# include <assert.h>

static int debug;

# 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_PRINT_COMPILED_PATTERN(p, s, e) 				\
  if (debug) 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)


/* Print the fastmap in human-readable form.  */

void
print_fastmap (fastmap)
    char *fastmap;
{
  unsigned was_a_range = 0;
  unsigned i = 0;

  while (i < (1 << BYTEWIDTH))
    {
      if (fastmap[i++])
	{
	  was_a_range = 0;
          putchar (i - 1);
          while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
            {
              was_a_range = 1;
              i++;
            }
	  if (was_a_range)
            {
              printf ("-");
              putchar (i - 1);
            }
        }
    }
  putchar ('\n');
}


/* Print a compiled pattern string in human-readable form, starting at
   the START pointer into it and ending just before the pointer END.  */

void
print_partial_compiled_pattern (start, end)
    US_CHAR_TYPE *start;
    US_CHAR_TYPE *end;
{
  int mcnt, mcnt2;
  US_CHAR_TYPE *p1;
  US_CHAR_TYPE *p = start;
  US_CHAR_TYPE *pend = end;

  if (start == NULL)
    {
      printf ("(null)\n");
      return;
    }

  /* Loop over pattern commands.  */
  while (p < pend)
    {
#ifdef _LIBC
      printf ("%td:\t", p - start);
#else
      printf ("%ld:\t", (long int) (p - start));
#endif

      switch ((re_opcode_t) *p++)
	{
        case no_op:
          printf ("/no_op");
          break;

	case exactn:
	  mcnt = *p++;
          printf ("/exactn/%d", mcnt);
          do
	    {
              putchar ('/');
	      PUT_CHAR (*p++);
            }
          while (--mcnt);
          break;

#ifdef MBS_SUPPORT
	case exactn_bin:
	  mcnt = *p++;
	  printf ("/exactn_bin/%d", mcnt);
          do
	    {
	      printf("/%lx", (long int) *p++);
            }
          while (--mcnt);
          break;
#endif /* MBS_SUPPORT */

	case start_memory:
          mcnt = *p++;
          printf ("/start_memory/%d/%ld", mcnt, (long int) *p++);
          break;

	case stop_memory:
          mcnt = *p++;
	  printf ("/stop_memory/%d/%ld", mcnt, (long int) *p++);
          break;

	case duplicate:
	  printf ("/duplicate/%ld", (long int) *p++);
	  break;

	case anychar:
	  printf ("/anychar");
	  break;

	case charset:
        case charset_not:
          {
#ifdef MBS_SUPPORT
	    int i, length;
	    wchar_t *workp = p;
	    printf ("/charset [%s",
	            (re_opcode_t) *(workp - 1) == charset_not ? "^" : "");
	    p += 5;
	    length = *workp++; /* the length of char_classes */
	    for (i=0 ; i<length ; i++)
	      printf("[:%lx:]", (long int) *p++);
	    length = *workp++; /* the length of collating_symbol */
	    for (i=0 ; i<length ;)
	      {
		printf("[.");
		while(*p != 0)
		  PUT_CHAR((i++,*p++));
		i++,p++;
		printf(".]");
	      }