fgrep

[Geoff Whale]

The following bug can be found in many releases, notably Level 7
and system V (fgrep version 1.2).
Try matching the patterns "roar" and "arrow"
against the subject "arroar".
It will fail to match due to a problem in setting
fail links in cfail() - this was probably never noticed because
of the highly obscure and unstructured nature of the implementation,
which looks more like Fortran than C.
The expedient fix (and the poor quality of the original code)
is evident from the diff listing below:
317c317
< 		*rear++ = s->nst;
---
> 		*rear++ = s;
339,346c339,351
< 		floop:	if (state == 0) state = w;
< 			if (state->inp == c) {
< 			qloop:	q->fail = state->nst;
< 				if ((state->nst)->out == 1) q->out = 1;
< 				if ((q = q->link) != 0) goto qloop;
< 			}
< 			else if ((state = state->link) != 0)
< 				goto floop;
---
> 			while (state != NULL && state->inp != c)
> 				if (state->link != NULL)
> 					state = state->link;
> 				else	/* no more alternatives at this level */
> 					state = state->fail;
> 			if (state == NULL)
> 				state = w;	/* first level node */
> 			else
> 				state = state->nst;	/* success link */
> 			do {
> 				q->fail = state;
> 				q->out |= state->out;
> 			} while ((q = q->link) != NULL);

The program has been completely rewritten at UNSW to use malloc()
to obtain tree nodes when needed (the original version declares
an incredible 96076 bytes of data!), to avoid useless leaf
nodes in the tree, and to accept the other grep options -s and -y.

					-- Geoff Whale (geoffw:elecvax)