Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 beta 3/9/83; site microsoft.UUCP
Path: utzoo!linus!philabs!cmcl2!seismo!harvard!talcott!panda!genrad!decvax!tektronix!uw-beaver!fluke!microsoft!gordonl
From: gordonl@microsoft.UUCP (Gordon Letwin)
Newsgroups: net.unix-wizards,net.bugs
Subject: Universal FGREP bug
Message-ID: <8770@microsoft.UUCP>
Date: Sun, 28-Jul-85 21:20:56 EDT
Article-I.D.: microsof.8770
Posted: Sun Jul 28 21:20:56 1985
Date-Received: Thu, 1-Aug-85 20:12:59 EDT
Organization: Microsoft Corporation
Lines: 47
Xref: linus net.unix-wizards:11279 net.bugs:600

I've just discovered what appears to be a "day 1" bug in fgrep.  Its
present in our V7, SYS III, and SYS 5 sources, so its probably present
in all fgrep sources out there.

The bug is in fgrep's handling of -y for multiple search strings.
Fgrep works by building a binary decision tree from its multiple
search strings.  It starts at the root of the tree, comparing the
character therin to the text character.  If there is a match it
follows the "success pointer" and reads another character.  If there
is a miss it follows the "fail pointer"

Thus, for a pattern space of

	DEVBANG
	DevTyp

If D fails we read another character and start over.  If D succeeds
we check for E, if E fails we check for e, and if that fails we
read another and start over, etc.

The problem is, fgrep only looks at the -y switch when its doing the
compares, not when it builds this tree.  Thus, with -y set the tree
should be

   |->  "D"?    ->   "E"   ->    "V"   ->  etc.
   |     |            |           |
   ---<---------<-----------<------

but instead the tables show

   |->  "D"?    ->   "E"   ->    "V"   ->  etc.
   |     |            |
   ---<---           "e"

			etc.

This means that if our text file has a "DevTyp" in it fgrep matches
the DEV in DEVBANG.  When it gets to the B, however, the tables say
"give up" instead of trying for "T".


Has anyone seen and fixed this bug?  It shouldn't be too hard to fix....
if someone doesn't post a fix we'll fix it and post.


	gordon letwin
	microsoft