regex.cc

早期freebsd实现

{
  unsigned is_active : 1;
  unsigned matched_something : 1;
};

#define IS_ACTIVE(R)  ((R).is_active)
#define MATCHED_SOMETHING(R)  ((R).matched_something)


/* Macros used by re_match_2:  */


/* I.e., regstart, regend, and reg_info.  */

#define NUM_REG_ITEMS  3

/* We push at most this many things on the stack whenever we
   fail.  The `+ 2' refers to PATTERN_PLACE and STRING_PLACE, which are
   arguments to the PUSH_FAILURE_POINT macro.  */

#define MAX_NUM_FAILURE_ITEMS   (RE_NREGS * NUM_REG_ITEMS + 2)


/* We push this many things on the stack whenever we fail.  */

#define NUM_FAILURE_ITEMS  (last_used_reg * NUM_REG_ITEMS + 2)


/* This pushes most of the information about the current state we will want
   if we ever fail back to it.  */

#define PUSH_FAILURE_POINT(pattern_place, string_place)			\
  {									\
    short last_used_reg, this_reg;					\
									\
    /* Find out how many registers are active or have been matched.	\
       (Aside from register zero, which is only set at the end.)  */	\
    for (last_used_reg = RE_NREGS - 1; last_used_reg > 0; last_used_reg--)\
      if (regstart[last_used_reg] != (unsigned char *) -1)		\
        break;								\
									\
    if (stacke - stackp < NUM_FAILURE_ITEMS)				\
      {									\
	unsigned char **stackx;						\
	int len = stacke - stackb;				\
	if (len > re_max_failures * MAX_NUM_FAILURE_ITEMS)		\
	  return -2;							\
									\
        /* Roughly double the size of the stack.  */			\
        stackx = (unsigned char **) alloca (2 * len			\
                                            * sizeof (unsigned char *));\
	/* Only copy what is in use.  */				\
        memcpy (stackx, stackb, len * sizeof (char *));			\
	stackp = stackx + (stackp - stackb);				\
	stackb = stackx;						\
	stacke = stackb + 2 * len;					\
      }									\
									\
    /* Now push the info for each of those registers.  */		\
    for (this_reg = 1; this_reg <= last_used_reg; this_reg++)		\
      {									\
        *stackp++ = regstart[this_reg];					\
        *stackp++ = regend[this_reg];					\
        *stackp++ = (unsigned char *) &reg_info[this_reg];		\
      }									\
									\
    /* Push how many registers we saved.  */				\
    *stackp++ = (unsigned char *) last_used_reg;			\
									\
    *stackp++ = pattern_place;                                          \
    *stackp++ = string_place;                                           \
  }
  

/* This pops what PUSH_FAILURE_POINT pushes.  */

#define POP_FAILURE_POINT()						\
  {									\
    int temp;								\
    stackp -= 2;		/* Remove failure points.  */		\
    temp = (int) *--stackp;	/* How many regs pushed.  */	        \
    temp *= NUM_REG_ITEMS;	/* How much to take off the stack.  */	\
    stackp -= temp; 		/* Remove the register info.  */	\
  }


#define MATCHING_IN_FIRST_STRING  (dend == end_match_1)

/* Is true if there is a first string and if PTR is pointing anywhere
   inside it or just past the end.  */
   
#define IS_IN_FIRST_STRING(ptr) 					\
	(size1 && string1 <= (ptr) && (ptr) <= string1 + size1)

/* Call before fetching a character with *d.  This switches over to
   string2 if necessary.  */

#define PREFETCH							\
 while (d == dend)						    	\
  {									\
    /* end of string2 => fail.  */					\
    if (dend == end_match_2) 						\
      goto fail;							\
    /* end of string1 => advance to string2.  */ 			\
    d = string2;						        \
    dend = end_match_2;							\
  }


/* Call this when have matched something; it sets `matched' flags for the
   registers corresponding to the subexpressions of which we currently
   are inside.  */
#define SET_REGS_MATCHED 						\
  { unsigned this_reg; 							\
    for (this_reg = 0; this_reg < RE_NREGS; this_reg++) 		\
      { 								\
        if (IS_ACTIVE(reg_info[this_reg]))				\
          MATCHED_SOMETHING(reg_info[this_reg]) = 1;			\
        else								\
          MATCHED_SOMETHING(reg_info[this_reg]) = 0;			\
      } 								\
  }

/* Test if at very beginning or at very end of the virtual concatenation
   of string1 and string2.  If there is only one string, we've put it in
   string2.  */

#define AT_STRINGS_BEG  (d == (size1 ? string1 : string2)  ||  !size2)
#define AT_STRINGS_END  (d == end2)	

#define AT_WORD_BOUNDARY						\
  (AT_STRINGS_BEG || AT_STRINGS_END || IS_A_LETTER (d - 1) != IS_A_LETTER (d))

/* We have two special cases to check for: 
     1) if we're past the end of string1, we have to look at the first
        character in string2;
     2) if we're before the beginning of string2, we have to look at the
        last character in string1; we assume there is a string1, so use
        this in conjunction with AT_STRINGS_BEG.  */
#define IS_A_LETTER(d)							\
  (SYNTAX ((d) == end1 ? *string2 : (d) == string2 - 1 ? *(end1 - 1) : *(d))\
   == Sword)


/* Match the pattern described by PBUFP against the virtual
   concatenation of STRING1 and STRING2, which are of SIZE1 and SIZE2,
   respectively.  Start the match at index POS in the virtual
   concatenation of STRING1 and STRING2.  In REGS, return the indices of
   the virtual concatenation of STRING1 and STRING2 that matched the
   entire PBUFP->buffer and its contained subexpressions.  Do not
   consider matching one past the index MSTOP in the virtual
   concatenation of STRING1 and STRING2.

   If pbufp->fastmap is nonzero, then it had better be up to date.

   The reason that the data to match are specified as two components
   which are to be regarded as concatenated is so this function can be
   used directly on the contents of an Emacs buffer.

   -1 is returned if there is no match.  -2 is returned if there is an
   error (such as match stack overflow).  Otherwise the value is the
   length of the substring which was matched.  */

int
re_match_2 (struct re_pattern_buffer *pbufp,
	    char *string1_arg, int size1,
	    char *string2_arg, int size2,
	    int pos,
	    struct re_registers *regs,
	    int mstop)
{
  register unsigned char *p = (unsigned char *) pbufp->buffer;

  /* Pointer to beyond end of buffer.  */
  register unsigned char *pend = p + pbufp->used;

  unsigned char *string1 = (unsigned char *) string1_arg;
  unsigned char *string2 = (unsigned char *) string2_arg;
  unsigned char *end1;		/* Just past end of first string.  */
  unsigned char *end2;		/* Just past end of second string.  */

  /* Pointers into string1 and string2, just past the last characters in
     each to consider matching.  */
  unsigned char *end_match_1, *end_match_2;

  register unsigned char *d, *dend;
  register int mcnt;			/* Multipurpose.  */
  unsigned char *translate = (unsigned char *) pbufp->translate;
  unsigned is_a_jump_n = 0;

 /* Failure point stack.  Each place that can handle a failure further
    down the line pushes a failure point on this stack.  It consists of
    restart, regend, and reg_info for all registers corresponding to the
    subexpressions we're currently inside, plus the number of such
    registers, and, finally, two char *'s.  The first char * is where to
    resume scanning the pattern; the second one is where to resume
    scanning the strings.  If the latter is zero, the failure point is a
    ``dummy''; if a failure happens and the failure point is a dummy, it
    gets discarded and the next next one is tried.  */

  unsigned char *initial_stack[MAX_NUM_FAILURE_ITEMS * NFAILURES];
  unsigned char **stackb = initial_stack;
  unsigned char **stackp = stackb;
  unsigned char **stacke = &stackb[MAX_NUM_FAILURE_ITEMS * NFAILURES];


  /* Information on the contents of registers. These are pointers into
     the input strings; they record just what was matched (on this
     attempt) by a subexpression part of the pattern, that is, the
     regnum-th regstart pointer points to where in the pattern we began
     matching and the regnum-th regend points to right after where we
     stopped matching the regnum-th subexpression.  (The zeroth register
     keeps track of what the whole pattern matches.)  */
     
  unsigned char *regstart[RE_NREGS];
  unsigned char *regend[RE_NREGS];

  /* The is_active field of reg_info helps us keep track of which (possibly
     nested) subexpressions we are currently in. The matched_something
     field of reg_info[reg_num] helps us tell whether or not we have
     matched any of the pattern so far this time through the reg_num-th
     subexpression.  These two fields get reset each time through any
     loop their register is in.  */

  struct register_info reg_info[RE_NREGS];


  /* The following record the register info as found in the above
     variables when we find a match better than any we've seen before. 
     This happens as we backtrack through the failure points, which in
     turn happens only if we have not yet matched the entire string.  */

  unsigned best_regs_set = 0;
  unsigned char *best_regstart[RE_NREGS];
  unsigned char *best_regend[RE_NREGS];

  /* Initialize subexpression text positions to -1 to mark ones that no
     \( or ( and \) or ) has been seen for. Also set all registers to
     inactive and mark them as not having matched anything or ever
     failed.  */
  for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
    {
      regstart[mcnt] = regend[mcnt] = (unsigned char *) -1;
      IS_ACTIVE (reg_info[mcnt]) = 0;
      MATCHED_SOMETHING (reg_info[mcnt]) = 0;
    }
  
  if (regs)
    for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
      regs->start[mcnt] = regs->end[mcnt] = -1;

  /* Set up pointers to ends of strings.
     Don't allow the second string to be empty unless both are empty.  */
  if (size2 == 0)
    {
      string2 = string1;
      size2 = size1;
      string1 = 0;
      size1 = 0;
    }
  end1 = string1 + size1;
  end2 = string2 + size2;

  /* Compute where to stop matching, within the two strings.  */
  if (mstop <= size1)
    {
      end_match_1 = string1 + mstop;
      end_match_2 = string2;
    }
  else
    {
      end_match_1 = end1;
      end_match_2 = string2 + mstop - 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)
    d = string1 + pos, dend = end_match_1;
  else
    d = string2 + pos - size1, dend = end_match_2;


  /* This loops over pattern commands.  It exits by returning from the
     function if match is complete, or it drops through if match fails
     at this starting point in the input data.  */

  while (1)
    {
      is_a_jump_n = 0;
      /* End of pattern means we might have succeeded.  */
      if (p == pend)
	{
	  /* If not end of string, try backtracking.  Otherwise done.  */
          if (d != end_match_2)
	    {
              if (stackp != stackb)
                {
                  /* More failure points to try.  */

                  unsigned in_same_string = 
        	          	IS_IN_FIRST_STRING (best_regend[0]) 
	        	        == MATCHING_IN_FIRST_STRING;

                  /* If exceeds best match so far, save it.  */
                  if (! best_regs_set
                      || (in_same_string && d > best_regend[0])
                      || (! in_same_string && ! MATCHING_IN_FIRST_STRING))
                    {
                      best_regs_set = 1;
                      best_regend[0] = d;	/* Never use regstart[0].  */
                      
                      for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
                        {
                          best_regstart[mcnt] = regstart[mcnt];
                          best_regend[mcnt] = regend[mcnt];
                        }
                    }
                  goto fail;	       
                }
              /* If no failure points, don't restore garbage.  */
              else if (best_regs_set)   
                {
	      restore_best_regs:
                  /* Restore best match.  */
                  d = best_regend[0];
                  
		  for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
		    {
		      regstart[mcnt] = best_regstart[mcnt];
		      regend[mcnt] = best_regend[mcnt];
		    }
                }
            }

	  /* If caller wants register contents data back, convert it 
	     to indices.  */
	  if (regs)
	    {
	      regs->start[0] = pos;
	      if (MATCHING_IN_FIRST_STRING)
		regs->end[0] = d - string1;
	      else
		regs->end[0] = d - string2 + size1;
	      for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
		{
		  if (regend[mcnt] == (unsigned char *) -1)
		    {
		      regs->start[mcnt] = -1;
		      regs->end[mcnt] = -1;
		      continue;
		    }
		  if (IS_IN_FIRST_STRING (regstart[mcnt]))
		    regs->start[mcnt] = regstart[mcnt] - string1;
		  else
		    regs->start[mcnt] = regstart[mcnt] - string2 + size1;
                    
		  if (IS_IN_FIRST_STRING (regend[mcnt]))
		    regs->end[mcnt] = regend[mcnt] - string1;
		  else
		    regs->end[mcnt] = regend[mcnt] - string2 + size1;
		}
	    }
	  return d - pos - (MATCHING_IN_FIRST_STRING 
			    ? string1 
			    : string2 - size1);
        }

      /* Otherwise match next pattern command.  */
#ifdef SWITCH_ENUM_BUG
      switch ((int) ((enum regexpcode) *p++))
#else
      switch ((enum regexpcode) *p++)
#endif
	{

	/* \( [or `(', as appropriate] is represented by start_memory,
           \) by stop_memory.  Both of those commands are followed by
           a register number in the next byte.  The text matched
           within the \( and \) is recorded under that number.  */
	case start_memory:
          regstart[*p] = d;
          IS_ACTIVE (reg_info[*p]) = 1;
          MATCHED_SOMETHING (reg_info[*p]) = 0;
          p++;
          break;

	case stop_memory:
          regend[*p] = d;
          IS_ACTIVE (reg_info[*p]) = 0;

          /* If just failed to match something this time around with a sub-
	     expression that's in a loop, try to force exit from the loop.  */
          if ((! MATCHED_SOMETHING (reg_info[*p])
	       || (enum regexpcode) p[-3] == start_memory)
	      && (p + 1) != pend)              
            {
	      register unsigned char *p2 = p + 1;
              mcnt = 0;
              switch (*p2++)
                {
                  case jump_n:
		    is_a_jump_n = 1;
                  case finalize_jump:
		  case maybe_finalize_jump:
		  case jump:
		  case dummy_failure_jump:
                    EXTRACT_NUMBER_AND_INCR (mcnt, p2);
		    if (is_a_jump_n)
		      p2 += 2;