From:	MERC::"uunet!WKUVX1.BITNET!FILESERV-Mgr" 12-JUN-1992 15:01:42.19
To:	galaxy::gleeve
CC:	
Subj:	GREP.03_OF_12

-+-+-+-+-+-+-+-+ START OF PART 3 -+-+-+-+-+-+-+-+
X  if (i < s->nelem && p.index == s->elems`5Bi`5D.index)
X    s->elems`5Bi`5D.constraint `7C= p.constraint;
X  else
X    `7B
X      t1 = p;
X      ++s->nelem;
X      while (i < s->nelem)
X`09`7B
X`09  t2 = s->elems`5Bi`5D;
X`09  s->elems`5Bi++`5D = t1;
X`09  t1 = t2;
X`09`7D
X    `7D
X`7D
X
X/* Merge two sets of positions into a third.  The result is exactly as if
X   the positions of both sets were inserted into an initially empty set. */
Xstatic void
Xmerge(s1, s2, m)
X     _position_set *s1;
X     _position_set *s2;
X     _position_set *m;
X`7B
X  int i = 0, j = 0;
X
X  m->nelem = 0;
X  while (i < s1->nelem && j < s2->nelem)
X    if (s1->elems`5Bi`5D.index > s2->elems`5Bj`5D.index)
X      m->elems`5Bm->nelem++`5D = s1->elems`5Bi++`5D;
X    else if (s1->elems`5Bi`5D.index < s2->elems`5Bj`5D.index)
X      m->elems`5Bm->nelem++`5D = s2->elems`5Bj++`5D;
X    else
X      `7B
X`09m->elems`5Bm->nelem`5D = s1->elems`5Bi++`5D;
X`09m->elems`5Bm->nelem++`5D.constraint `7C= s2->elems`5Bj++`5D.constraint;
X      `7D
X  while (i < s1->nelem)
X    m->elems`5Bm->nelem++`5D = s1->elems`5Bi++`5D;
X  while (j < s2->nelem)
X    m->elems`5Bm->nelem++`5D = s2->elems`5Bj++`5D;
X`7D
X
X/* Delete a position from a set. */
Xstatic void
Xdelete(p, s)
X     _position p;
X     _position_set *s;
X`7B
X  int i;
X
X  for (i = 0; i < s->nelem; ++i)
X    if (p.index == s->elems`5Bi`5D.index)
X      break;
X  if (i < s->nelem)
X    for (--s->nelem; i < s->nelem; ++i)
X      s->elems`5Bi`5D = s->elems`5Bi + 1`5D;
X`7D
X`0C
X/* Find the index of the state corresponding to the given position set with
X   the given preceding context, or create a new state if there is no such
X   state.  Newline and letter tell whether we got here on a newline or
X   letter, respectively. */
Xstatic int
Xstate_index(r, s, newline, letter)
X     struct regexp *r;
X     _position_set *s;
X     int newline;
X     int letter;
X`7B
X  int hash = 0;
X  int constraint;
X  int i, j;
X
X  newline = newline ? 1 : 0;
X  letter = letter ? 1 : 0;
X
X  for (i = 0; i < s->nelem; ++i)
X    hash `5E= s->elems`5Bi`5D.index + s->elems`5Bi`5D.constraint;
X
X  /* Try to find a state that exactly matches the proposed one. */
X  for (i = 0; i < r->sindex; ++i)
X    `7B
X      if (hash != r->states`5Bi`5D.hash `7C`7C s->nelem != r->states`5Bi`5D.
Velems.nelem
X`09  `7C`7C newline != r->states`5Bi`5D.newline `7C`7C letter != r->states`5
VBi`5D.letter)
X`09continue;
X      for (j = 0; j < s->nelem; ++j)
X`09if (s->elems`5Bj`5D.constraint
X`09    != r->states`5Bi`5D.elems.elems`5Bj`5D.constraint
X`09    `7C`7C s->elems`5Bj`5D.index != r->states`5Bi`5D.elems.elems`5Bj`5D.i
Vndex)
X`09  break;
X      if (j == s->nelem)
X`09return i;
X    `7D
X
X  /* We'll have to create a new state. */
X  REALLOC_IF_NECESSARY(r->states, _dfa_state, r->salloc, r->sindex);
X  r->states`5Bi`5D.hash = hash;
X  MALLOC(r->states`5Bi`5D.elems.elems, _position, s->nelem);
X  copy(s, &r->states`5Bi`5D.elems);
X  r->states`5Bi`5D.newline = newline;
X  r->states`5Bi`5D.letter = letter;
X  r->states`5Bi`5D.backref = 0;
X  r->states`5Bi`5D.constraint = 0;
X  r->states`5Bi`5D.first_end = 0;
X  for (j = 0; j < s->nelem; ++j)
X    if (r->tokens`5Bs->elems`5Bj`5D.index`5D < 0)
X      `7B
X`09constraint = s->elems`5Bj`5D.constraint;
X`09if (_SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 0)
X`09    `7C`7C _SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 1)
X`09    `7C`7C _SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 0)
X`09    `7C`7C _SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 1))
X`09  r->states`5Bi`5D.constraint `7C= constraint;
X`09if (! r->states`5Bi`5D.first_end)
X`09  r->states`5Bi`5D.first_end = r->tokens`5Bs->elems`5Bj`5D.index`5D;
X      `7D
X    else if (r->tokens`5Bs->elems`5Bj`5D.index`5D == _BACKREF)
X      `7B
X`09r->states`5Bi`5D.constraint = _NO_CONSTRAINT;
X`09r->states`5Bi`5D.backref = 1;
X      `7D
X
X  ++r->sindex;
X
X  return i;
X`7D
X`0C
X/* Find the epsilon closure of a set of positions.  If any position of the s
Vet
X   contains a symbol that matches the empty string in some context, replace
X   that position with the elements of its follow labeled with an appropriate
X   constraint.  Repeat exhaustively until no funny positions are left.
X   S->elems must be large enough to hold the result. */
Xvoid
Xepsclosure(s, r)
X     _position_set *s;
X     struct regexp *r;
X`7B
X  int i, j;
X  int *visited;
X  _position p, old;
X
X  MALLOC(visited, int, r->tindex);
X  for (i = 0; i < r->tindex; ++i)
X    visited`5Bi`5D = 0;
X
X  for (i = 0; i < s->nelem; ++i)
X    if (r->tokens`5Bs->elems`5Bi`5D.index`5D >= _NOTCHAR
X`09&& r->tokens`5Bs->elems`5Bi`5D.index`5D != _BACKREF
X`09&& r->tokens`5Bs->elems`5Bi`5D.index`5D < _SET)
X      `7B
X`09old = s->elems`5Bi`5D;
X`09p.constraint = old.constraint;
X`09delete(s->elems`5Bi`5D, s);
X`09if (visited`5Bold.index`5D)
X`09  `7B
X`09    --i;
X`09    continue;
X`09  `7D
X`09visited`5Bold.index`5D = 1;
X`09switch (r->tokens`5Bold.index`5D)
X`09  `7B
X`09  case _BEGLINE:
X`09    p.constraint &= _BEGLINE_CONSTRAINT;
X`09    break;
X`09  case _ENDLINE:
X`09    p.constraint &= _ENDLINE_CONSTRAINT;
X`09    break;
X`09  case _BEGWORD:
X`09    p.constraint &= _BEGWORD_CONSTRAINT;
X`09    break;
X`09  case _ENDWORD:
X`09    p.constraint &= _ENDWORD_CONSTRAINT;
X`09    break;
X`09  case _LIMWORD:
X`09    p.constraint &= _LIMWORD_CONSTRAINT;
X`09    break;
X`09  case _NOTLIMWORD:
X`09    p.constraint &= _NOTLIMWORD_CONSTRAINT;
X`09    break;
X`09  default:
X`09    break;
X`09  `7D
X`09for (j = 0; j < r->follows`5Bold.index`5D.nelem; ++j)
X`09  `7B
X`09    p.index = r->follows`5Bold.index`5D.elems`5Bj`5D.index;
X`09    insert(p, s);
X`09  `7D
X`09/* Force rescan to start at the beginning. */
X`09i = -1;
X      `7D
X
X  free(visited);
X`7D
X`0C
X/* Perform bottom-up analysis on the parse tree, computing various functions
V.
X   Note that at this point, we're pretending constructs like \< are real
X   characters rather than constraints on what can follow them.
X
X   Nullable:  A node is nullable if it is at the root of a regexp that can
X   match the empty string.
X   *  _EMPTY leaves are nullable.
X   * No other leaf is nullable.
X   * A _QMARK or _STAR node is nullable.
X   * A _PLUS node is nullable if its argument is nullable.
X   * A _CAT node is nullable if both its arguments are nullable.
X   * An _OR node is nullable if either argument is nullable.
X
X   Firstpos:  The firstpos of a node is the set of positions (nonempty leave
Vs)
X   that could correspond to the first character of a string matching the
X   regexp rooted at the given node.
X   * _EMPTY leaves have empty firstpos.
X   * The firstpos of a nonempty leaf is that leaf itself.
X   * The firstpos of a _QMARK, _STAR, or _PLUS node is the firstpos of its
X     argument.
X   * The firstpos of a _CAT node is the firstpos of the left argument, union
X     the firstpos of the right if the left argument is nullable.
X   * The firstpos of an _OR node is the union of firstpos of each argument.
X
X   Lastpos:  The lastpos of a node is the set of positions that could
X   correspond to the last character of a string matching the regexp at
X   the given node.
X   * _EMPTY leaves have empty lastpos.
X   * The lastpos of a nonempty leaf is that leaf itself.
X   * The lastpos of a _QMARK, _STAR, or _PLUS node is the lastpos of its
X     argument.
X   * The lastpos of a _CAT node is the lastpos of its right argument, union
X     the lastpos of the left if the right argument is nullable.
X   * The lastpos of an _OR node is the union of the lastpos of each argument
V.
X
X   Follow:  The follow of a position is the set of positions that could
X   correspond to the character following a character matching the node in
X   a string matching the regexp.  At this point we consider special symbols
X   that match the empty string in some context to be just normal characters.
X   Later, if we find that a special symbol is in a follow set, we will
X   replace it with the elements of its follow, labeled with an appropriate
X   constraint.
X   * Every node in the firstpos of the argument of a _STAR or _PLUS node is
V in
X     the follow of every node in the lastpos.
X   * Every node in the firstpos of the second argument of a _CAT node is in
X     the follow of every node in the lastpos of the first argument.
X
X   Because of the postfix representation of the parse tree, the depth-first
X   analysis is conveniently done by a linear scan with the aid of a stack.
X   Sets are stored as arrays of the elements, obeying a stack-like allocatio
Vn
X   scheme; the number of elements in each set deeper in the stack can be
X   used to determine the address of a particular set's array. */
Xvoid
Xreganalyze(r, searchflag)
X     struct regexp *r;
X     int searchflag;
X`7B
X  int *nullable;`09`09/* Nullable stack. */
X  int *nfirstpos;`09`09/* Element count stack for firstpos sets. */
X  _position *firstpos;`09`09/* Array where firstpos elements are stored. */
X  int *nlastpos;`09`09/* Element count stack for lastpos sets. */
X  _position *lastpos;`09`09/* Array where lastpos elements are stored. */
X  int *nalloc;`09`09`09/* Sizes of arrays allocated to follow sets. */
X  _position_set tmp;`09`09/* Temporary set for merging sets. */
X  _position_set merged;`09`09/* Result of merging sets. */
X  int wants_newline;`09`09/* True if some position wants newline info. */
X  int *o_nullable;
X  int *o_nfirst, *o_nlast;
X  _position *o_firstpos, *o_lastpos;
X  int i, j;
X  _position *pos;
X
X#ifdef DEBUG
X  fprintf(stderr, "reganalyze:\n");
X  for (i = 0; i < r->tindex; ++i)
X    `7B
X      fprintf(stderr, " %d:", i);
X      prtok(r->tokens`5Bi`5D);
X    `7D
X  putc('\n', stderr);
X#endif
X
X  r->searchflag = searchflag;
X
X  MALLOC(nullable, int, r->depth);
X  o_nullable = nullable;
X  MALLOC(nfirstpos, int, r->depth);
X  o_nfirst = nfirstpos;
X  MALLOC(firstpos, _position, r->nleaves);
X  o_firstpos = firstpos, firstpos += r->nleaves;
X  MALLOC(nlastpos, int, r->depth);
X  o_nlast = nlastpos;
X  MALLOC(lastpos, _position, r->nleaves);
X  o_lastpos = lastpos, lastpos += r->nleaves;
X  MALLOC(nalloc, int, r->tindex);
X  for (i = 0; i < r->tindex; ++i)
X    nalloc`5Bi`5D = 0;
X  MALLOC(merged.elems, _position, r->nleaves);
X
X  CALLOC(r->follows, _position_set, r->tindex);
X
X  for (i = 0; i < r->tindex; ++i)
X#ifdef DEBUG
X    `7B`09`09`09`09/* Nonsyntactic #ifdef goo... */
X#endif
X    switch (r->tokens`5Bi`5D)
X      `7B
X      case _EMPTY:
X`09/* The empty set is nullable. */
X`09*nullable++ = 1;
X
X`09/* The firstpos and lastpos of the empty leaf are both empty. */
X`09*nfirstpos++ = *nlastpos++ = 0;
X`09break;
X
X      case _STAR:
X      case _PLUS:
X`09/* Every element in the firstpos of the argument is in the follow
X`09   of every element in the lastpos. */
X`09tmp.nelem = nfirstpos`5B-1`5D;
X`09tmp.elems = firstpos;
X`09pos = lastpos;
X`09for (j = 0; j < nlastpos`5B-1`5D; ++j)
X`09  `7B
X`09    merge(&tmp, &r->follows`5Bpos`5Bj`5D.index`5D, &merged);
X`09    REALLOC_IF_NECESSARY(r->follows`5Bpos`5Bj`5D.index`5D.elems, _positio
Vn,
X`09`09`09`09 nalloc`5Bpos`5Bj`5D.index`5D, merged.nelem - 1);
X`09    copy(&merged, &r->follows`5Bpos`5Bj`5D.index`5D);
X`09  `7D
X
X      case _QMARK:
X`09/* A _QMARK or _STAR node is automatically nullable. */
X`09if (r->tokens`5Bi`5D != _PLUS)
X`09  nullable`5B-1`5D = 1;
X`09break;
X
X      case _CAT:
X`09/* Every element in the firstpos of the second argument is in the
X`09   follow of every element in the lastpos of the first argument. */
X`09tmp.nelem = nfirstpos`5B-1`5D;
X`09tmp.elems = firstpos;
X`09pos = lastpos + nlastpos`5B-1`5D;
X`09for (j = 0; j < nlastpos`5B-2`5D; ++j)
X`09  `7B
X`09    merge(&tmp, &r->follows`5Bpos`5Bj`5D.index`5D, &merged);
X`09    REALLOC_IF_NECESSARY(r->follows`5Bpos`5Bj`5D.index`5D.elems, _positio
Vn,
X`09`09`09`09 nalloc`5Bpos`5Bj`5D.index`5D, merged.nelem - 1);
X`09    copy(&merged, &r->follows`5Bpos`5Bj`5D.index`5D);
X`09  `7D
X
X`09/* The firstpos of a _CAT node is the firstpos of the first argument,
X`09   union that of the second argument if the first is nullable. */
X`09if (nullable`5B-2`5D)
X`09  nfirstpos`5B-2`5D += nfirstpos`5B-1`5D;
X`09else
X`09  firstpos += nfirstpos`5B-1`5D;
X`09--nfirstpos;
X
X`09/* The lastpos of a _CAT node is the lastpos of the second argument,
X`09   union that of the first argument if the second is nullable. */
X`09if (nullable`5B-1`5D)
X`09  nlastpos`5B-2`5D += nlastpos`5B-1`5D;
X`09else
X`09  `7B
X`09    pos = lastpos + nlastpos`5B-2`5D;
X`09    for (j = nlastpos`5B-1`5D - 1; j >= 0; --j)
X`09      pos`5Bj`5D = lastpos`5Bj`5D;
X`09    lastpos += nlastpos`5B-2`5D;
X`09    nlastpos`5B-2`5D = nlastpos`5B-1`5D;
X`09  `7D
X`09--nlastpos;
X
X`09/* A _CAT node is nullable if both arguments are nullable. */
X`09nullable`5B-2`5D = nullable`5B-1`5D && nullable`5B-2`5D;
X`09--nullable;
X`09break;
X
X      case _OR:
X`09/* The firstpos is the union of the firstpos of each argument. */
X`09nfirstpos`5B-2`5D += nfirstpos`5B-1`5D;
X`09--nfirstpos;
X
X`09/* The lastpos is the union of the lastpos of each argument. */
X`09nlastpos`5B-2`5D += nlastpos`5B-1`5D;
X`09--nlastpos;
X
X`09/* An _OR node is nullable if either argument is nullable. */
X`09nullable`5B-2`5D = nullable`5B-1`5D `7C`7C nullable`5B-2`5D;
X`09--nullable;
X`09break;
X
X      default:
X`09/* Anything else is a nonempty position.  (Note that special
X`09   constructs like \< are treated as nonempty strings here;
X`09   an "epsilon closure" effectively makes them nullable later.
X`09   Backreferences have to get a real position so we can detect
X`09   transitions on them later.  But they are nullable. */
X`09*nullable++ = r->tokens`5Bi`5D == _BACKREF;
X
X`09/* This position is in its own firstpos and lastpos. */
X`09*nfirstpos++ = *nlastpos++ = 1;
X`09--firstpos, --lastpos;
X`09firstpos->index = lastpos->index = i;
X`09firstpos->constraint = lastpos->constraint = _NO_CONSTRAINT;
X
X`09/* Allocate the follow set for this position. */
X`09nalloc`5Bi`5D = 1;
X`09MALLOC(r->follows`5Bi`5D.elems, _position, nalloc`5Bi`5D);
X`09break;
X      `7D
X#ifdef DEBUG
X    /* ... balance the above nonsyntactic #ifdef goo... */
X      fprintf(stderr, "node %d:", i);
X      prtok(r->tokens`5Bi`5D);
X      putc('\n', stderr);
X      fprintf(stderr, nullable`5B-1`5D ? " nullable: yes\n" : " nullable: no
V\n");
X      fprintf(stderr, " firstpos:");
X      for (j = nfirstpos`5B-1`5D - 1; j >= 0; --j)
X`09`7B
X`09  fprintf(stderr, " %d:", firstpos`5Bj`5D.index);
X`09  prtok(r->tokens`5Bfirstpos`5Bj`5D.index`5D);
X`09`7D
X      fprintf(stderr, "\n lastpos:");
X      for (j = nlastpos`5B-1`5D - 1; j >= 0; --j)
X`09`7B
X`09  fprintf(stderr, " %d:", lastpos`5Bj`5D.index);
X`09  prtok(r->tokens`5Blastpos`5Bj`5D.index`5D);
X`09`7D
X      putc('\n', stderr);
X    `7D
X#endif
X
X  /* For each follow set that is the follow set of a real position, replace
X     it with its epsilon closure. */
X  for (i = 0; i < r->tindex; ++i)
X    if (r->tokens`5Bi`5D < _NOTCHAR `7C`7C r->tokens`5Bi`5D == _BACKREF
X`09`7C`7C r->tokens`5Bi`5D >= _SET)
X      `7B
X#ifdef DEBUG
X`09fprintf(stderr, "follows(%d:", i);
X`09prtok(r->tokens`5Bi`5D);
X`09fprintf(stderr, "):");
X`09for (j = r->follows`5Bi`5D.nelem - 1; j >= 0; --j)
X`09  `7B
X`09    fprintf(stderr, " %d:", r->follows`5Bi`5D.elems`5Bj`5D.index);
X`09    prtok(r->tokens`5Br->follows`5Bi`5D.elems`5Bj`5D.index`5D);
X`09  `7D
X`09putc('\n', stderr);
X#endif
X`09copy(&r->follows`5Bi`5D, &merged);
X`09epsclosure(&merged, r);
X`09if (r->follows`5Bi`5D.nelem < merged.nelem)
X`09  REALLOC(r->follows`5Bi`5D.elems, _position, merged.nelem);
X`09copy(&merged, &r->follows`5Bi`5D);
X      `7D
X
X  /* Get the epsilon closure of the firstpos of the regexp.  The result will
X     be the set of positions of state 0. */
X  merged.nelem = 0;
X  for (i = 0; i < nfirstpos`5B-1`5D; ++i)
X    insert(firstpos`5Bi`5D, &merged);
X  epsclosure(&merged, r);
X
X  /* Check if any of the positions of state 0 will want newline context. */
X  wants_newline = 0;
X  for (i = 0; i < merged.nelem; ++i)
X    if (_PREV_NEWLINE_DEPENDENT(merged.elems`5Bi`5D.constraint))
X      wants_newline = 1;
X
X  /* Build the initial state. */
X  r->salloc = 1;
X  r->sindex = 0;
X  MALLOC(r->states, _dfa_state, r->salloc);
X  state_index(r, &merged, wants_newline, 0);
X
X  free(o_nullable);
X  free(o_nfirst);
X  free(o_firstpos);
X  free(o_nlast);
X  free(o_lastpos);
X  free(nalloc);
X  free(merged.elems);
X`7D
X`0C
X/* Find, for each character, the transition out of state s of r, and store
X   it in the appropriate slot of trans.
X
X   We divide the positions of s into groups (positions can appear in more
X   than one group).  Each group is labeled with a set of characters that
X   every position in the group matches (taking into account, if necessary,
X   preceding context information of s).  For each group, find the union
X   of the its elements' follows.  This set is the set of positions of the
X   new state.  For each character in the group's label, set the transition
X   on this character to be to a state corresponding to the set's positions,
X   and its associated backward context information, if necessary.
X
X   If we are building a searching matcher, we include the positions of state
X   0 in every state.
X
X   The collection of groups is constructed by building an equivalence-class
X   partition of the positions of s.
X
X   For each position, find the set of characters C that it matches.  Elimina
Vte
X   any characters from C that fail on grounds of backward context.
X
X   Search through the groups, looking for a group whose label L has nonempty
X   intersection with C.  If L - C is nonempty, create a new group labeled
X   L - C and having the same positions as the current group, and set L to
X   the intersection of L and C.  Insert the position in this group, set
X   C = C - L, and resume scanning.
X
X   If after comparing with every group there are characters remaining in C,
X   create a new group labeled with the characters of C and insert this
X   position in that group. */
Xvoid
Xregstate(s, r, trans)
X     int s;
X     struct regexp *r;
X     int trans`5B`5D;
X`7B
X  _position_set grps`5B_NOTCHAR`5D;`09/* As many as will ever be needed. */
X  _charset labels`5B_NOTCHAR`5D;`09/* Labels corresponding to the groups. */
X  int ngrps = 0;`09`09/* Number of groups actually used. */
X  _position pos;`09`09/* Current position being considered. */
X  _charset matches;`09`09/* Set of matching characters. */
X  int matchesf;`09`09`09/* True if matches is nonempty. */
X  _charset intersect;`09`09/* Intersection with some label set. */
X  int intersectf;`09`09/* True if intersect is nonempty. */
X  _charset leftovers;`09`09/* Stuff in the label that didn't match. */
X  int leftoversf;`09`09/* True if leftovers is nonempty. */
X  static _charset letters;`09/* Set of characters considered letters. */
X  static _charset newline;`09/* Set of characters that aren't newline. */
X  _position_set follows;`09/* Union of the follows of some group. */
X  _position_set tmp;`09`09/* Temporary space for merging sets. */
X  int state;`09`09`09/* New state. */
X  int wants_newline;`09`09/* New state wants to know newline context. */
X  int state_newline;`09`09/* New state on a newline transition. */
X  int wants_letter;`09`09/* New state wants to know letter context. */
X  int state_letter;`09`09/* New state on a letter transition. */
X  static initialized;`09`09/* Flag for static initialization. */
X  int i, j, k;
X
X  /* Initialize the set of letters, if necessary. */
X  if (! initialized)
X    `7B
X      initialized = 1;
X      for (i = 0; i < _NOTCHAR; ++i)
X`09if (ISALNUM(i))
X`09  setbit(i, letters);
X      setbit('\n', newline);
X    `7D
X
X  zeroset(matches);
X
X  for (i = 0; i < r->states`5Bs`5D.elems.nelem; ++i)
X    `7B
X      pos = r->states`5Bs`5D.elems.elems`5Bi`5D;
X      if (r->tokens`5Bpos.index`5D >= 0 && r->tokens`5Bpos.index`5D < _NOTCH
VAR)
X`09setbit(r->tokens`5Bpos.index`5D, matches);
X      else if (r->tokens`5Bpos.index`5D >= _SET)
X`09copyset(r->charsets`5Br->tokens`5Bpos.index`5D - _SET`5D, matches);
X      else
X`09continue;
X
X      /* Some characters may need to be eliminated from matches because
X`09 they fail in the current context. */
X      if (pos.constraint != 0xFF)
X`09`7B
X`09  if (! _MATCHES_NEWLINE_CONTEXT(pos.constraint,
X`09`09`09`09`09 r->states`5Bs`5D.newline, 1))
X`09    clrbit('\n', matches);
X`09  if (! _MATCHES_NEWLINE_CONTEXT(pos.constraint,
X`09`09`09`09`09 r->states`5Bs`5D.newline, 0))
X`09    for (j = 0; j < _CHARSET_INTS; ++j)
X`09      matches`5Bj`5D &= newline`5Bj`5D;
X`09  if (! _MATCHES_LETTER_CONTEXT(pos.constraint,
X`09`09`09`09`09r->states`5Bs`5D.letter, 1))
X`09    for (j = 0; j < _CHARSET_INTS; ++j)
X`09      matches`5Bj`5D &= `7Eletters`5Bj`5D;
X`09  if (! _MATCHES_LETTER_CONTEXT(pos.constraint,
X`09`09`09`09`09r->states`5Bs`5D.letter, 0))
X`09    for (j = 0; j < _CHARSET_INTS; ++j)
X`09      matches`5Bj`5D &= letters`5Bj`5D;
X
X`09  /* If there are no characters left, there's no point in going on. */
X`09  for (j = 0; j < _CHARSET_INTS && !matches`5Bj`5D; ++j)
X`09    ;
X`09  if (j == _CHARSET_INTS)
X`09    continue;
X`09`7D
X
X      for (j = 0; j < ngrps; ++j)
X`09`7B
X`09  /* If matches contains a single character only, and the current
X`09     group's label doesn't contain that character, go on to the
X`09     next group. */
X`09  if (r->tokens`5Bpos.index`5D >= 0 && r->tokens`5Bpos.index`5D < _NOTCHA
VR
X`09      && !tstbit(r->tokens`5Bpos.index`5D, labels`5Bj`5D))
X`09    continue;
X
X`09  /* Check if this group's label has a nonempty intersection with
X`09     matches. */
X`09  intersectf = 0;
X`09  for (k = 0; k < _CHARSET_INTS; ++k)
X`09    (intersect`5Bk`5D = matches`5Bk`5D & labels`5Bj`5D`5Bk`5D) ? intersec
Vtf = 1 : 0;
X`09  if (! intersectf)
X`09    continue;
X
X`09  /* It does; now find the set differences both ways. */
X`09  leftoversf = matchesf = 0;
X`09  for (k = 0; k < _CHARSET_INTS; ++k)
X`09    `7B
X`09      /* Even an optimizing compiler can't know this for sure. */
X`09      int match = matches`5Bk`5D, label = labels`5Bj`5D`5Bk`5D;
X
X`09      (leftovers`5Bk`5D = `7Ematch & label) ? leftoversf = 1 : 0;
X`09      (matches`5Bk`5D = match & `7Elabel) ? matchesf = 1 : 0;
X`09    `7D
X
X`09  /* If there were leftovers, create a new group labeled with them. */
X`09  if (leftoversf)
X`09    `7B
X`09      copyset(leftovers, labels`5Bngrps`5D);
X`09      copyset(intersect, labels`5Bj`5D);
X`09      MALLOC(grps`5Bngrps`5D.elems, _position, r->nleaves);
X`09      copy(&grps`5Bj`5D, &grps`5Bngrps`5D);
X`09      ++ngrps;
X`09    `7D
X
X`09  /* Put the position in the current group.  Note that there is no
X`09     reason to call insert() here. */
X`09  grps`5Bj`5D.elems`5Bgrps`5Bj`5D.nelem++`5D = pos;
X
X`09  /* If every character matching the current position has been
X`09     accounted for, we're done. */
X`09  if (! matchesf)
X`09    break;
X`09`7D
X
X      /* If we've passed the last group, and there are still characters
X`09 unaccounted for, then we'll have to create a new group. */
X      if (j == ngrps)
X`09`7B
X`09  copyset(matches, labels`5Bngrps`5D);
X`09  zeroset(matches);
X`09  MALLOC(grps`5Bngrps`5D.elems, _position, r->nleaves);
X`09  grps`5Bngrps`5D.nelem = 1;
X`09  grps`5Bngrps`5D.elems`5B0`5D = pos;
X`09  ++ngrps;
X`09`7D
X    `7D
X
X  MALLOC(follows.elems, _position, r->nleaves);
X  MALLOC(tmp.elems, _position, r->nleaves);
X
X  /* If we are a searching matcher, the default transition is to a state
X     containing the positions of state 0, otherwise the default transition
X     is to fail miserably. */
X  if (r->searchflag)
X    `7B
X      wants_newline = 0;
X      wants_letter = 0;
X      for (i = 0; i < r->states`5B0`5D.elems.nelem; ++i)
X`09`7B
X`09  if (_PREV_NEWLINE_DEPENDENT(r->states`5B0`5D.elems.elems`5Bi`5D.constra
Vint))
X`09    wants_newline = 1;
X`09  if (_PREV_LETTER_DEPENDENT(r->states`5B0`5D.elems.elems`5Bi`5D.constrai
Vnt))
X`09    wants_letter = 1;
X`09`7D
X      copy(&r->states`5B0`5D.elems, &follows);
X      state = state_index(r, &follows, 0, 0);
X      if (wants_newline)
X`09state_newline = state_index(r, &follows, 1, 0);
X      else
X`09state_newline = state;
X      if (wants_letter)
X`09state_letter = state_index(r, &follows, 0, 1);
X      else
X`09state_letter = state;
X      for (i = 0; i < _NOTCHAR; ++i)
X`09if (i == '\n')
X`09  trans`5Bi`5D = state_newline;
X`09else if (ISALNUM(i))
X`09  trans`5Bi`5D = state_letter;
X`09else
X`09  trans`5Bi`5D = state;
X    `7D
X  else
X    for (i = 0; i < _NOTCHAR; ++i)
X      trans`5Bi`5D = -1;
X
X  for (i = 0; i < ngrps; ++i)
X    `7B
X      follows.nelem = 0;
X
X      /* Find the union of the follows of the positions of the group.
X`09 This is a hideously inefficient loop.  Fix it someday. */
X      for (j = 0; j < grps`5Bi`5D.nelem; ++j)
X`09for (k = 0; k < r->follows`5Bgrps`5Bi`5D.elems`5Bj`5D.index`5D.nelem; ++k
V)
X`09  insert(r->follows`5Bgrps`5Bi`5D.elems`5Bj`5D.index`5D.elems`5Bk`5D, &fo
Vllows);
X
X      /* If we are building a searching matcher, throw in the positions
X`09 of state 0 as well. */
X      if (r->searchflag)
X`09for (j = 0; j < r->states`5B0`5D.elems.nelem; ++j)
X`09  insert(r->states`5B0`5D.elems.elems`5Bj`5D, &follows);
X
X      /* Find out if the new state will want any context information. */
X      wants_newline = 0;
X      if (tstbit('\n', labels`5Bi`5D))
X`09for (j = 0; j < follows.nelem; ++j)
X`09  if (_PREV_NEWLINE_DEPENDENT(follows.elems`5Bj`5D.constraint))
X`09    wants_newline = 1;
X
X      wants_letter = 0;
X      for (j = 0; j < _CHARSET_INTS; ++j)
X`09if (labels`5Bi`5D`5Bj`5D & letters`5Bj`5D)
X`09  break;
X      if (j < _CHARSET_INTS)
X`09for (j = 0; j < follows.nelem; ++j)
X`09  if (_PREV_LETTER_DEPENDENT(follows.elems`5Bj`5D.constraint))
X`09    wants_letter = 1;
X
X      /* Find the state(s) corresponding to the union of the follows. */
X      state = state_index(r, &follows, 0, 0);
X      if (wants_newline)
X`09state_newline = state_index(r, &follows, 1, 0);
X      else
X`09state_newline = state;
X      if (wants_letter)
X`09state_letter = state_index(r, &follows, 0, 1);
X      else
X`09state_letter = state;
X
X      /* Set the transitions for each character in the current label. */
X      for (j = 0; j < _CHARSET_INTS; ++j)
X`09for (k = 0; k < INTBITS; ++k)
X`09  if (labels`5Bi`5D`5Bj`5D & 1 << k)
X`09    `7B
X`09      int c = j * INTBITS + k;
X
X`09      if (c == '\n')
X`09`09trans`5Bc`5D = state_newline;
X`09      else if (ISALNUM(c))
X`09`09trans`5Bc`5D = state_letter;
X`09      else if (c < _NOTCHAR)
X`09`09trans`5Bc`5D = state;
X`09    `7D
X    `7D
X
X  for (i = 0; i < ngrps; ++i)
X    free(grps`5Bi`5D.elems);
X  free(follows.elems);
X  free(tmp.elems);
X`7D
X`0C
X/* Some routines for manipulating a compiled regexp's transition tables.
X   Each state may or may not have a transition table; if it does, and it
X   is a non-accepting state, then r->trans`5Bstate`5D points to its table.
X   If it is an accepting state then r->fails`5Bstate`5D points to its table.
X   If it has no table at all, then r->trans`5Bstate`5D is NULL.
X   TODO: Improve this comment, get rid of the unnecessary redundancy. */
X
Xstatic void
Xbuild_state(s, r)
X     int s;
X     struct regexp *r;
X`7B
X  int *trans;`09`09`09/* The new transition table. */
X  int i;
X
X  /* Set an upper limit on the number of transition tables that will ever
X     exist at once.  1024 is arbitrary.  The idea is that the frequently
X     used transition tables will be quickly rebuilt, whereas the ones that
X     were only needed once or twice will be cleared away. */
X  if (r->trcount >= 1024)
X    `7B
X      for (i = 0; i < r->tralloc; ++i)
X`09if (r->trans`5Bi`5D)
X`09  `7B
X`09    free((ptr_t) r->trans`5Bi`5D);
X`09    r->trans`5Bi`5D = NULL;
X`09  `7D
X`09else if (r->fails`5Bi`5D)
X`09  `7B
X`09    free((ptr_t) r->fails`5Bi`5D);
X`09    r->fails`5Bi`5D = NULL;
X`09  `7D
X      r->trcount = 0;
X    `7D
X
X  ++r->trcount;
X
X  /* Set up the success bits for this state. */
X  r->success`5Bs`5D = 0;
X  if (ACCEPTS_IN_CONTEXT(r->states`5Bs`5D.newline, 1, r->states`5Bs`5D.lette
Vr, 0,
X      s, *r))
X    r->success`5Bs`5D `7C= 4;
X  if (ACCEPTS_IN_CONTEXT(r->states`5Bs`5D.newline, 0, r->states`5Bs`5D.lette
Vr, 1,
X      s, *r))
X    r->success`5Bs`5D `7C= 2;
X  if (ACCEPTS_IN_CONTEXT(r->states`5Bs`5D.newline, 0, r->states`5Bs`5D.lette
Vr, 0,
X      s, *r))
X    r->success`5Bs`5D `7C= 1;
X
X  MALLOC(trans, int, _NOTCHAR);
X  regstate(s, r, trans);
X
X  /* Now go through the new transition table, and make sure that the trans
X     and fail arrays are allocated large enough to hold a pointer for the
X     largest state mentioned in the table. */
X  for (i = 0; i < _NOTCHAR; ++i)
X    if (trans`5Bi`5D >= r->tralloc)
X      `7B
+-+-+-+-+-+-+-+-  END  OF PART 3 +-+-+-+-+-+-+-+-
