dfa.c

早期freebsd实现

	break;

      case _OR:
	/* The firstpos is the union of the firstpos of each argument. */
	nfirstpos[-2] += nfirstpos[-1];
	--nfirstpos;

	/* The lastpos is the union of the lastpos of each argument. */
	nlastpos[-2] += nlastpos[-1];
	--nlastpos;

	/* An _OR node is nullable if either argument is nullable. */
	nullable[-2] = nullable[-1] || nullable[-2];
	--nullable;
	break;

      default:
	/* Anything else is a nonempty position.  (Note that special
	   constructs like \< are treated as nonempty strings here;
	   an "epsilon closure" effectively makes them nullable later.
	   Backreferences have to get a real position so we can detect
	   transitions on them later.  But they are nullable. */
	*nullable++ = r->tokens[i] == _BACKREF;

	/* This position is in its own firstpos and lastpos. */
	*nfirstpos++ = *nlastpos++ = 1;
	--firstpos, --lastpos;
	firstpos->index = lastpos->index = i;
	firstpos->constraint = lastpos->constraint = _NO_CONSTRAINT;

	/* Allocate the follow set for this position. */
	nalloc[i] = 1;
	MALLOC(r->follows[i].elems, _position, nalloc[i]);
	break;
      }

  /* For each follow set that is the follow set of a real position, replace
     it with its epsilon closure. */
  for (i = 0; i < r->tindex; ++i)
    if (r->tokens[i] < _NOTCHAR || r->tokens[i] == _BACKREF
	|| r->tokens[i] >= _SET)
      {
	copy(&r->follows[i], &merged);
	epsclosure(&merged, r);
	if (r->follows[i].nelem < merged.nelem)
	  REALLOC(r->follows[i].elems, _position, merged.nelem);
	copy(&merged, &r->follows[i]);
      }

  /* Get the epsilon closure of the firstpos of the regexp.  The result will
     be the set of positions of state 0. */
  merged.nelem = 0;
  for (i = 0; i < nfirstpos[-1]; ++i)
    insert(firstpos[i], &merged);
  epsclosure(&merged, r);

  /* Check if any of the positions of state 0 will want newline context. */
  wants_newline = 0;
  for (i = 0; i < merged.nelem; ++i)
    if (_PREV_NEWLINE_DEPENDENT(merged.elems[i].constraint))
      wants_newline = 1;

  /* Build the initial state. */
  r->salloc = 1;
  r->sindex = 0;
  MALLOC(r->states, _dfa_state, r->salloc);
  state_index(r, &merged, wants_newline, 0);

  free(o_nullable);
  free(o_nfirst);
  free(o_firstpos);
  free(o_nlast);
  free(o_lastpos);
  free(nalloc);
  free(merged.elems);
}

/* Find, for each character, the transition out of state s of r, and store
   it in the appropriate slot of trans.

   We divide the positions of s into groups (positions can appear in more
   than one group).  Each group is labeled with a set of characters that
   every position in the group matches (taking into account, if necessary,
   preceding context information of s).  For each group, find the union
   of the its elements' follows.  This set is the set of positions of the
   new state.  For each character in the group's label, set the transition
   on this character to be to a state corresponding to the set's positions,
   and its associated backward context information, if necessary.

   If we are building a searching matcher, we include the positions of state
   0 in every state.

   The collection of groups is constructed by building an equivalence-class
   partition of the positions of s.

   For each position, find the set of characters C that it matches.  Eliminate
   any characters from C that fail on grounds of backward context.

   Search through the groups, looking for a group whose label L has nonempty
   intersection with C.  If L - C is nonempty, create a new group labeled
   L - C and having the same positions as the current group, and set L to
   the intersection of L and C.  Insert the position in this group, set
   C = C - L, and resume scanning.

   If after comparing with every group there are characters remaining in C,
   create a new group labeled with the characters of C and insert this
   position in that group. */
void
regstate(s, r, trans)
     int s;
     struct regexp *r;
     int trans[];
{
  _position_set grps[_NOTCHAR];	/* As many as will ever be needed. */
  _charset labels[_NOTCHAR];	/* Labels corresponding to the groups. */
  int ngrps = 0;		/* Number of groups actually used. */
  _position pos;		/* Current position being considered. */
  _charset matches;		/* Set of matching characters. */
  int matchesf;			/* True if matches is nonempty. */
  _charset intersect;		/* Intersection with some label set. */
  int intersectf;		/* True if intersect is nonempty. */
  _charset leftovers;		/* Stuff in the label that didn't match. */
  int leftoversf;		/* True if leftovers is nonempty. */
  static _charset letters;	/* Set of characters considered letters. */
  static _charset newline;	/* Set of characters that aren't newline. */
  _position_set follows;	/* Union of the follows of some group. */
  _position_set tmp;		/* Temporary space for merging sets. */
  int state;			/* New state. */
  int wants_newline;		/* New state wants to know newline context. */
  int state_newline;		/* New state on a newline transition. */
  int wants_letter;		/* New state wants to know letter context. */
  int state_letter;		/* New state on a letter transition. */
  static initialized;		/* Flag for static initialization. */
  int i, j, k;

  /* Initialize the set of letters, if necessary. */
  if (! initialized)
    {
      initialized = 1;
      for (i = 0; i < _NOTCHAR; ++i)
	if (ISALNUM(i))
	  setbit(i, letters);
      setbit('\n', newline);
    }

  zeroset(matches);

  for (i = 0; i < r->states[s].elems.nelem; ++i)
    {
      pos = r->states[s].elems.elems[i];
      if (r->tokens[pos.index] >= 0 && r->tokens[pos.index] < _NOTCHAR)
	setbit(r->tokens[pos.index], matches);
      else if (r->tokens[pos.index] >= _SET)
	copyset(r->charsets[r->tokens[pos.index] - _SET], matches);
      else
	continue;

      /* Some characters may need to be climinated from matches because
	 they fail in the current context. */
      if (pos.constraint != 0xff)
	{
	  if (! _MATCHES_NEWLINE_CONTEXT(pos.constraint,
					 r->states[s].newline, 1))
	    clrbit('\n', matches);
	  if (! _MATCHES_NEWLINE_CONTEXT(pos.constraint,
					 r->states[s].newline, 0))
	    for (j = 0; j < _CHARSET_INTS; ++j)
	      matches[j] &= newline[j];
	  if (! _MATCHES_LETTER_CONTEXT(pos.constraint,
					r->states[s].letter, 1))
	    for (j = 0; j < _CHARSET_INTS; ++j)
	      matches[j] &= ~letters[j];
	  if (! _MATCHES_LETTER_CONTEXT(pos.constraint,
					r->states[s].letter, 0))
	    for (j = 0; j < _CHARSET_INTS; ++j)
	      matches[j] &= letters[j];

	  /* If there are no characters left, there's no point in going on. */
	  for (j = 0; j < _CHARSET_INTS && !matches[j]; ++j)
	    ;
	  if (j == _CHARSET_INTS)
	    continue;
	}

      for (j = 0; j < ngrps; ++j)
	{
	  /* If matches contains a single character only, and the current
	     group's label doesn't contain that character, go on to the
	     next group. */
	  if (r->tokens[pos.index] >= 0 && r->tokens[pos.index] < _NOTCHAR
	      && !tstbit(r->tokens[pos.index], labels[j]))
	    continue;

	  /* Check if this group's label has a nonempty intersection with
	     matches. */
	  intersectf = 0;
	  for (k = 0; k < _CHARSET_INTS; ++k)
	    (intersect[k] = matches[k] & labels[j][k]) ? intersectf = 1 : 0;
	  if (! intersectf)
	    continue;

	  /* It does; now find the set differences both ways. */
	  leftoversf = matchesf = 0;
	  for (k = 0; k < _CHARSET_INTS; ++k)
	    {
	      /* Even an optimizing compiler can't know this for sure. */
	      int match = matches[k], label = labels[j][k];

	      (leftovers[k] = ~match & label) ? leftoversf = 1 : 0;
	      (matches[k] = match & ~label) ? matchesf = 1 : 0;
	    }

	  /* If there were leftovers, create a new group labeled with them. */
	  if (leftoversf)
	    {
	      copyset(leftovers, labels[ngrps]);
	      copyset(intersect, labels[j]);
	      MALLOC(grps[ngrps].elems, _position, r->nleaves);
	      copy(&grps[j], &grps[ngrps]);
	      ++ngrps;
	    }

	  /* Put the position in the current group.  Note that there is no
	     reason to call insert() here. */
	  grps[j].elems[grps[j].nelem++] = pos;

	  /* If every character matching the current position has been
	     accounted for, we're done. */
	  if (! matchesf)
	    break;
	}

      /* If we've passed the last group, and there are still characters
	 unaccounted for, then we'll have to create a new group. */
      if (j == ngrps)
	{
	  copyset(matches, labels[ngrps]);
	  zeroset(matches);
	  MALLOC(grps[ngrps].elems, _position, r->nleaves);
	  grps[ngrps].nelem = 1;
	  grps[ngrps].elems[0] = pos;
	  ++ngrps;
	}
    }

  MALLOC(follows.elems, _position, r->nleaves);
  MALLOC(tmp.elems, _position, r->nleaves);

  /* If we are a searching matcher, the default transition is to a state
     containing the positions of state 0, otherwise the default transition
     is to fail miserably. */
  if (r->searchflag)
    {
      wants_newline = 0;
      wants_letter = 0;
      for (i = 0; i < r->states[0].elems.nelem; ++i)
	{
	  if (_PREV_NEWLINE_DEPENDENT(r->states[0].elems.elems[i].constraint))
	    wants_newline = 1;
	  if (_PREV_LETTER_DEPENDENT(r->states[0].elems.elems[i].constraint))
	    wants_letter = 1;
	}
      copy(&r->states[0].elems, &follows);
      state = state_index(r, &follows, 0, 0);
      if (wants_newline)
	state_newline = state_index(r, &follows, 1, 0);
      else
	state_newline = state;
      if (wants_letter)
	state_letter = state_index(r, &follows, 0, 1);
      else
	state_letter = state;
      for (i = 0; i < _NOTCHAR; ++i)
	trans[i] = (ISALNUM(i)) ? state_letter : state ;
      trans['\n'] = state_newline;
    }
  else
    for (i = 0; i < _NOTCHAR; ++i)
      trans[i] = -1;

  for (i = 0; i < ngrps; ++i)
    {
      follows.nelem = 0;

      /* Find the union of the follows of the positions of the group.
	 This is a hideously inefficient loop.  Fix it someday. */
      for (j = 0; j < grps[i].nelem; ++j)
	for (k = 0; k < r->follows[grps[i].elems[j].index].nelem; ++k)
	  insert(r->follows[grps[i].elems[j].index].elems[k], &follows);

      /* If we are building a searching matcher, throw in the positions
	 of state 0 as well. */
      if (r->searchflag)
	for (j = 0; j < r->states[0].elems.nelem; ++j)
	  insert(r->states[0].elems.elems[j], &follows);

      /* Find out if the new state will want any context information. */
      wants_newline = 0;
      if (tstbit('\n', labels[i]))
	for (j = 0; j < follows.nelem; ++j)
	  if (_PREV_NEWLINE_DEPENDENT(follows.elems[j].constraint))
	    wants_newline = 1;

      wants_letter = 0;
      for (j = 0; j < _CHARSET_INTS; ++j)
	if (labels[i][j] & letters[j])
	  break;
      if (j < _CHARSET_INTS)
	for (j = 0; j < follows.nelem; ++j)
	  if (_PREV_LETTER_DEPENDENT(follows.elems[j].constraint))
	    wants_letter = 1;

      /* Find the state(s) corresponding to the union of the follows. */
      state = state_index(r, &follows, 0, 0);
      if (wants_newline)
	state_newline = state_index(r, &follows, 1, 0);
      else
	state_newline = state;
      if (wants_letter)
	state_letter = state_index(r, &follows, 0, 1);
      else
	state_letter = state;

      /* Set the transitions for each character in the current label. */
      for (j = 0; j < _CHARSET_INTS; ++j)
	for (k = 0; k < INTBITS; ++k)
	  if (labels[i][j] & 1 << k)
	    {
	      int c = j * INTBITS + k;

	      if (c == '\n')
		trans[c] = state_newline;
	      else if (ISALNUM(c))
		trans[c] = state_letter;
	      else if (c < _NOTCHAR)
		trans[c] = state;
	    }
    }

  for (i = 0; i < ngrps; ++i)
    free(grps[i].elems);
  free(follows.elems);
  free(tmp.elems);
}

/* Some routines for manipulating a compiled regexp's transition tables.
   Each state may or may not have a transition table; if it does, and it
   is a non-accepting state, then r->trans[state] points to its table.
   If it is an accepting state then r->fails[state] points to its table.
   If it has no table at all, then r->trans[state] is NULL.
   TODO: Improve this comment, get rid of the unnecessary redundancy. */

static void
build_state(s, r)
     int s;
     struct regexp *r;
{
  int *trans;			/* The new transition table. */
  int i;

  /* Set an upper limit on the number of transition tables that will ever
     exist at once.  1024 is arbitrary.  The idea is that the frequently
     used transition tables will be quickly rebuilt, whereas the ones that
     were only needed once or twice will be cleared away. */
  if (r->trcount >= 1024)
    {
      for (i = 0; i < r->tralloc; ++i)
	if (r->trans[i])
	  {
	    free((ptr_t) r->trans[i]);
	    r->trans[i] = NULL;
	  }
	else if (r->fails[i])
	  {
	    free((ptr_t) r->fails[i]);
	    r->fails[i] = NULL;
	  }
      r->trcount = 0;
    }

  ++r->trcount;

  /* Set up the success bits for this state. */
  r->success[s] = 0;
  if (ACCEPTS_IN_CONTEXT(r->states[s].newline, 1, r->states[s].letter, 0,
      s, *r))
    r->success[s] |= 4;
  if (ACCEPTS_IN_CONTEXT(r->states[s].newline, 0, r->states[s].letter, 1,
      s, *r))
    r->success[s] |= 2;
  if (ACCEPTS_IN_CONTEXT(r->states[s].newline, 0, r->states[s].letter, 0,
      s, *r))
    r->success[s] |= 1;

  MALLOC(trans, int, _NOTCHAR);
  regstate(s, r, trans);

  /* Now go through the new transition table, and make sure that the trans
     and fail arrays are allocated large enough to hold a pointer for the
     largest state mentioned in the table. */
  for (i = 0; i < _NOTCHAR; ++i)
    if (trans[i] >= r->tralloc)
      {
	int oldalloc = r->tralloc;

	while (trans[i] >= r->tralloc)
	  r->tralloc *= 2;
	REALLOC(r->realtrans, int *, r->tralloc + 1);
	r->trans = r->realtrans + 1;
	REALLOC(r->fails, int *, r->tralloc);
	REALLOC(r->success, int, r->tralloc);
	REALLOC(r->newlines, int, r->tralloc);
	while (oldalloc < r->tralloc)
	  {
	    r->trans[oldalloc] = NULL;
	    r->fails[oldalloc++] = NULL;
	  }
      }

  /* Keep the newline transition in a special place so we can use it as
     a sentinel. */
  r->newlines[s] = trans['\n'];
  trans['\n'] = -1;

  if (ACCEPTING(s, *r))
    r->fails[s] = trans;
  else
    r->trans[s] = trans;
}

static void
build_state_zero(r)
     struct regexp *r;
{
  r->tralloc = 1;
  r->trcount = 0;
  CALLOC(r->realtrans, int *, r->tralloc + 1);
  r->trans = r->realtrans + 1;
  CALLOC(r->fails, int *, r->tralloc);
  MALLOC(r->success, int, r->tralloc);
  MALLOC(r->newlines, int, r->tralloc);
  build_state(0, r);
}

/* Search through a buffer looking for a match to the given struct regexp.
   Find the first occurrence of a string matching the regexp in the buffer,
   and the shortest possible version thereof.  Return a pointer to the first
   character after the match, or NULL if none is found.  Begin points to
   the beginning of the buffer, and end points to the first character after
   its end.  We store a newline in *end to act as a sentinel, so end had
   better point somewhere valid.  Newline is a flag indicating whether to
   allow newlines to be in the matching string.  If count is non-
   NULL it points to a place we're supposed to increment every time we
   see a newline.  Finally, if backref is non-NULL it points to a place
   where we're supposed to store a 1 if backreferencing happened and the
   match needs to be verified by a backtracking matcher.  Otherwise
   we store a 0 in *backref. */
char *
regexecute(r, begin, end, newline, count, backref)
     struct regexp *r;
     char *begin;
     char *end;
     int newline;
     int *count;
     int *backref;
{
  register s, s1, tmp;		/* Current state. */
  register unsigned char *p;	/* Current input character. */
  register **trans, *t;		/* Copy of r->trans so it can be optimized
				   into a register. */
  static sbit[_NOTCHAR];	/* Table for anding with r->success. */
  static sbit_init;

  if (! sbit_init)
    {
      int i;

      sbit_init = 1;
      for (i = 0; i < _NOTCHAR; ++i)
	sbit[i] = (ISALNUM(i)) ? 2 : 1;
      sbit['\n'] = 4;
    }

  if (! r->tralloc)
    build_state_zero(r);

  s = s1 = 0;
  p = (unsigned char *) begin;
  trans = r->trans;
  *end = '\n';

  for (;;)
    {
      while ((t = trans[s]) != 0) { /* hand-optimized loop */
	s1 = t[*p++];
        if ((t = trans[s1]) == 0) {
           tmp = s ; s = s1 ; s1 = tmp ; /* swap */
           break;
        }
	s = t[*p++];
      }

      if (s >= 0 && p <= (unsigned char *) end && r->fails[s])
	{
	  if (r->success[s] & sbit[*p])
	    {
	      if (backref)
		*backref = (r->states[s].backref != 0);
	      return (char *) p;
	    }

	  s1 = s;
	  s = r->fails[s][*p++];
	  continue;
	}

      /* If the previous character was a newline, count it. */
      if (count && (char *) p <= end && p[-1] == '\n')
	++*count;

      /* Check if we've run off the end of the buffer. */
      if ((char *) p >= end)
	return NULL;

      if (s >= 0)
	{
	  build_state(s, r);
	  trans = r->trans;
	  continue;
	}

      if (p[-1] == '\n' && newline)
	{
	  s = r->newlines[s1];
	  continue;
	}

      s = 0;
    }
}

/* Initialize the components of a regexp that the other routines don't
   initialize for themselves. */
void
reginit(r)
     struct regexp *r;
{
  r->calloc = 1;
  MALLOC(r->charsets, _charset, r->calloc);
  r->cindex = 0;

  r->talloc = 1;
  MALLOC(r->tokens, _token, r->talloc);
  r->tindex = r->depth = r->nleaves = r->nregexps = 0;

  r->searchflag = 0;
  r->tralloc = 0;
}

/* Parse and analyze a single string of the given length. */
void
regcompile(s, len, r, searchflag)
     const char *s;
     size_t len;
     struct regexp *r;
     int searchflag;
{
  if (case_fold)	/* dummy folding in service of regmust() */
    {
      char *regcopy;
      int i;

      regcopy = malloc(len);