[PATCH] grep: fix infinite loop in -o

[Colin Watson]

On Mon, Aug 23, 2010 at 02:39:10AM +0200, Denys Vlasenko wrote:
> On Thursday 19 August 2010 15:50, Colin Watson wrote:
> > --- a/findutils/grep.c
> > +++ b/findutils/grep.c
> > @@ -463,13 +463,19 @@ static int grep_file(FILE *file)
> >  					} else while (1) {
> >  						unsigned end = gl->matched_range.rm_eo;
> >  						char old = line[end];
> > -						line[end] = '\0';
> > -						print_line(line + gl->matched_range.rm_so,
> > -								end - gl->matched_range.rm_so,
> > -								linenum, ':');
> > -						if (old == '\0')
> > -							break;
> > -						line[end] = old;
> > +						if (gl->matched_range.rm_so == gl->matched_range.rm_eo) {
> > +							end++;
> 
> Why do you think end++ does not run off the end of the line?

Fair point, thanks.  Updated version follows.

From: Colin Watson <cjwatson at ubuntu.com>
Date: Thu, 19 Aug 2010 14:46:48 +0100
Subject: [PATCH] grep: fix infinite loop in -o

If the supplied pattern matches the empty string at the start of a line,
then 'grep -o' would loop forever.

Originally reported as
https://bugs.launchpad.net/ubuntu/+source/busybox/+bug/619817.

Signed-off-by: Colin Watson <cjwatson at ubuntu.com>
---
 findutils/grep.c     |   23 ++++++++++++++++-------
 testsuite/grep.tests |    4 ++++
 2 files changed, 20 insertions(+), 7 deletions(-)

diff --git a/findutils/grep.c b/findutils/grep.c
index 688ea6a..1b53d83 100644
--- a/findutils/grep.c
+++ b/findutils/grep.c
@@ -463,13 +463,22 @@ static int grep_file(FILE *file)
 					} else while (1) {
 						unsigned end = gl->matched_range.rm_eo;
 						char old = line[end];
-						line[end] = '\0';
-						print_line(line + gl->matched_range.rm_so,
-								end - gl->matched_range.rm_so,
-								linenum, ':');
-						if (old == '\0')
-							break;
-						line[end] = old;
+						if (gl->matched_range.rm_so == gl->matched_range.rm_eo) {
+							/* Already at end of line? */
+							if (line[end] == '\0')
+								break;
+							/* Otherwise make sure we make some progress. */
+							if (line[++end] == '\0')
+								break;
+						} else {
+							line[end] = '\0';
+							print_line(line + gl->matched_range.rm_so,
+									end - gl->matched_range.rm_so,
+									linenum, ':');
+							if (old == '\0')
+								break;
+							line[end] = old;
+						}
 #if !ENABLE_EXTRA_COMPAT
 						if (regexec(&gl->compiled_regex, line + end,
 								1, &gl->matched_range, REG_NOTBOL) != 0)
diff --git a/testsuite/grep.tests b/testsuite/grep.tests
index 520a184..ad99257 100755
--- a/testsuite/grep.tests
+++ b/testsuite/grep.tests
@@ -98,5 +98,9 @@ testing "grep -o does not loop forever" \
 	'grep -o "[^/]*$"' \
 	"test\n" \
 	"" "/var/test\n"
+testing "grep -o does not loop forever on zero-length match at ^" \
+	'grep -o "" | head -n1' \
+	"" \
+	"" "test\n"
 
 exit $FAILCOUNT
-- 
1.7.1