NetBSD Problem Report #28126

From andrew@untraceable.net  Tue Nov  9 02:36:13 2004
Return-Path: <andrew@untraceable.net>
Received: from noc.untraceable.net (noc.untraceable.net [166.84.189.65])
	by narn.netbsd.org (Postfix) with ESMTP id 59BAF2521DB
	for <gnats-bugs@gnats.netbsd.org>; Tue,  9 Nov 2004 02:36:13 +0000 (UTC)
Message-Id: <200411090236.iA92aAk0019567@noc.untraceable.net>
Date: Mon, 8 Nov 2004 21:36:10 -0500 (EST)
From: Andrew Brown <atatat@atatdot.net>
Reply-To: Andrew Brown <atatat@atatdot.net>
To: gnats-bugs@gnats.netbsd.org
Subject: sed fails to match empty back-reference
X-Send-Pr-Version: 3.95

>Number:         28126
>Category:       bin
>Synopsis:       sed fails to match empty back-reference
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Nov 09 02:37:00 +0000 2004
>Closed-Date:    
>Last-Modified:  Sun Mar 18 10:15:02 +0000 2012
>Originator:     TheMan
>Release:        2.99.10
>Organization:
none
>Environment:

System: NetBSD this 2.99.10 NetBSD 2.99.10 (THAT) #346: Mon Nov  8 07:58:51 EST 2004  andrew@this:/usr/src/sys/arch/i386/compile/THAT i386


>Description:

	sed fails to match an empty back-reference.  i discovered this
after i partially zorched my cvs tree and my Root and Repository files
mostly ended up containing garbage.  finding improper Repository files
should have been as simple as:

	% cd /usr/src
	% find ./bin -path \*/CVS/Repository | \
		xargs grep -H . | \
		sed -n '/^\.\(.*\)\/CVS\/Repository:src\1$/d;p'

yet the first line out is 

	./CVS/Repository:src

which is clearly fine.

>How-To-Repeat:

on netbsd current

	% echo foobar | sed -ne '/foo\(.*\)bar\1/p'
	% echo foo1bar1 | sed -ne '/foo\(.*\)bar\1/p'
	foo1bar1

compared to solaris:

	% echo foobar | sed -ne '/foo\(.*\)bar\1/p'
	foobar

linux:

	% echo foobar | sed -ne '/foo\(.*\)bar\1/p'
	foobar

netbsd 2.0_RC4:

	% echo foobar | sed -ne '/foo\(.*\)bar\1/p'
	foobar

netbsd 1.6ZL:

	% echo foobar | sed -ne '/foo\(.*\)bar\1/p'
	foobar

etc.

>Fix:

not sure.  repeatedly updating my sed tree to something older (and
older and older) didn't yield any good results, so i suppose it might
be a recent change to regex stuff in libc?
>Release-Note:
>Audit-Trail:
From: dieter roelants <dieter.NetBSD@pandora.be>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: bin/28126 (sed fails to match empty back-reference)
Date: Sat, 17 May 2008 17:00:41 +0200

 I've been looking into this. The change that caused it is:

 http://cvsweb.be.netbsd.org/cgi-bin/cvsweb.cgi/src/lib/libc/regex/engine.c.diff?r2=1.18&r1=1.17&f=H
 "Avoid infinite recursion on:

     echo "foo foo bar bar bar baz" | sed 's/\([^ ]*\)\( *\1\)*/\1/g'

 From OpenBSD."

 Wondering whether OpenBSD people had perhaps detected and fixed the
 problem, I noticed that they did, in response to this very same PR.

 The patch, adapted to NetBSD, follows. I have verified with a small C
 program (included after the patch) that it works (and returns the same
 results as PCRE).

 I should also note that the foo bar baz sed thing above returns the
 wrong result with the current libc:

 echo "foo foo bar bar bar baz" | sed 's/\([^ ]*\)\( *\1\)*/\1/g'
 foo bar baz
 echo "foo foo bar bar bar baz" | LD_PRELOAD=/usr/src/lib/libc/libc.so.12 sed 's/\([^ ]*\)\( *\1\)*/\1/g'
 foobarbaz

 Index: regex/engine.c
 ===================================================================
 RCS file: /cvsroot/src/lib/libc/regex/engine.c,v
 retrieving revision 1.21
 diff -u -r1.21 engine.c
 --- regex/engine.c	8 Feb 2007 05:44:18 -0000	1.21
 +++ regex/engine.c	17 May 2008 14:47:45 -0000
 @@ -128,10 +128,11 @@
  /* === engine.c === */
  static int matcher(struct re_guts *g, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
  static const char *dissect(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
 -static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev);
 +static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst, sopno lev, int rec);
  static const char *fast(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
  static const char *slow(struct match *m, const char *start, const char *stop, sopno startst, sopno stopst);
  static states step(struct re_guts *g, sopno start, sopno stop, states bef, int ch, states aft);
 +#define MAX_RECURSION	100
  #define	BOL	(OUT+1)
  #define	EOL	(BOL+1)
  #define	BOLEOL	(BOL+2)
 @@ -279,7 +280,7 @@
  				goto done;
  			}
  			NOTE("backref dissect");
 -			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
 +			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
  		}
  		if (dp != NULL)
  			break;
 @@ -302,7 +303,7 @@
  			}
  #endif
  			NOTE("backoff dissect");
 -			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
 +			dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
  		}
  		assert(dp == NULL || dp == endp);
  		if (dp != NULL)		/* found a shorter one */
 @@ -565,7 +566,8 @@
      const char *stop,
      sopno startst,
      sopno stopst,
 -    sopno lev)			/* PLUS nesting level */
 +    sopno lev,			/* PLUS nesting level */
 +    int rec)
  {
  	int i;
  	sopno ss;	/* start sop of current subRE */
 @@ -675,7 +677,7 @@
  			return(NULL);
  		assert(m->pmatch[i].rm_so != (regoff_t)-1);
  		len = (size_t)(m->pmatch[i].rm_eo - m->pmatch[i].rm_so);
 -		if (len == 0)
 +		if (len == 0 && rec++ > MAX_RECURSION)
  			return(NULL);
  		assert(stop - m->beginp >= len);
  		if (sp > stop - len)
 @@ -685,28 +687,28 @@
  			return(NULL);
  		while (m->g->strip[ss] != SOP(O_BACK, i))
  			ss++;
 -		return(backref(m, sp+len, stop, ss+1, stopst, lev));
 +		return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));

  	case OQUEST_:		/* to null or not */
 -		dp = backref(m, sp, stop, ss+1, stopst, lev);
 +		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
  		if (dp != NULL)
  			return(dp);	/* not */
 -		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
 +		return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));

  	case OPLUS_:
  		assert(m->lastpos != NULL);
  		assert(lev+1 <= m->g->nplus);
  		m->lastpos[lev+1] = sp;
 -		return(backref(m, sp, stop, ss+1, stopst, lev+1));
 +		return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));

  	case O_PLUS:
  		if (sp == m->lastpos[lev])	/* last pass matched null */
 -			return(backref(m, sp, stop, ss+1, stopst, lev-1));
 +			return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
  		/* try another pass */
  		m->lastpos[lev] = sp;
 -		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
 +		dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
  		if (dp == NULL)
 -			dp = backref(m, sp, stop, ss+1, stopst, lev-1);
 +			dp = backref(m, sp, stop, ss+1, stopst, lev-1, rec);
  		return(dp);

  	case OCH_:		/* find the right one, if any */
 @@ -714,7 +716,7 @@
  		esub = ss + OPND(s) - 1;
  		assert(OP(m->g->strip[esub]) == OOR1);
  		for (;;) {	/* find first matching branch */
 -			dp = backref(m, sp, stop, ssub, esub, lev);
 +			dp = backref(m, sp, stop, ssub, esub, lev, rec);
  			if (dp != NULL)
  				return(dp);
  			/* that one missed, try next one */
 @@ -735,7 +737,7 @@
  		assert(0 < i && i <= m->g->nsub);
  		offsave = m->pmatch[i].rm_so;
  		m->pmatch[i].rm_so = sp - m->offp;
 -		dp = backref(m, sp, stop, ss+1, stopst, lev);
 +		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
  		if (dp != NULL)
  			return(dp);
  		m->pmatch[i].rm_so = offsave;
 @@ -746,7 +748,7 @@
  		assert(0 < i && i <= m->g->nsub);
  		offsave = m->pmatch[i].rm_eo;
  		m->pmatch[i].rm_eo = sp - m->offp;
 -		dp = backref(m, sp, stop, ss+1, stopst, lev);
 +		dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
  		if (dp != NULL)
  			return(dp);
  		m->pmatch[i].rm_eo = offsave;


 ======================================
 #include <inttypes.h>
 #ifdef _USE_PCRE
 #include <pcreposix.h>
 #else
 #include <regex.h>
 #endif
 #include <stdio.h>

 void
 testreg(regex_t *r, const char *s)
 {
 	regmatch_t m[2];
 	printf("%s: %d\t", s, regexec(r, s, 2, m, 0));
 	printf("%jd - %jd\t", (intmax_t)(m[0].rm_so), (intmax_t)(m[0].rm_eo));
 	printf("%jd - %jd\n", (intmax_t)(m[1].rm_so), (intmax_t)(m[1].rm_eo));
 }

 int
 main()
 {
 	regex_t r;
 	int ret;
 	char err[1024];
 #ifdef _USE_PCRE
 #define TESTRE "foo(.*)bar\\1"
 #else
 #define TESTRE "foo\\(.*\\)bar\\1"
 #endif

 	if ((ret = regcomp(&r, TESTRE, 0)) != 0) {
 		regerror(ret, &r, err, 1024);
 		fprintf(stderr, "RE error: %s\n", err);
 		return 1;
 	}
 	testreg(&r, "foobar");
 	testreg(&r, "foo_bar_");
 	testreg(&r, "foobar_");
 	testreg(&r, "foolbar_");
 	return 0;
 }

 /*
 output:

 current libc:
 ./t_libc
 foobar: 1	0 - 0	0 - 577757282805521148
 foo_bar_: 0	0 - 8	3 - 4
 foobar_: 1	0 - 8	3 - 4
 foolbar_: 1	0 - 8	3 - 4

 patched libc:
 LD_PRELOAD=/usr/src/lib/libc/libc.so.12 ./t_libc
 foobar: 0	0 - 6	3 - 3
 foo_bar_: 0	0 - 8	3 - 4
 foobar_: 0	0 - 6	3 - 3
 foolbar_: 1	0 - 6	3 - 3

 pcre:
 LD_PRELOAD=/usr/pkg/lib/libpcreposix.so ./t_pcre
 foobar: 0	0 - 6	3 - 3
 foo_bar_: 0	0 - 8	3 - 4
 foobar_: 0	0 - 6	3 - 3
 foolbar_: 17	0 - 6	3 - 3
 */

 dieter

From: "Jukka Ruohonen" <jruoho@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/28126 CVS commit: src
Date: Sun, 18 Mar 2012 10:12:31 +0000

 Module Name:	src
 Committed By:	jruoho
 Date:		Sun Mar 18 10:12:31 UTC 2012

 Modified Files:
 	src/distrib/sets/lists/tests: mi
 	src/etc/mtree: NetBSD.dist.tests
 	src/tests/usr.bin: Makefile
 Added Files:
 	src/tests/usr.bin/sed: Makefile t_sed.sh

 Log Message:
 Add a test case for PR bin/28126. Does not fail with GNU sed.


 To generate a diff of this commit:
 cvs rdiff -u -r1.447 -r1.448 src/distrib/sets/lists/tests/mi
 cvs rdiff -u -r1.64 -r1.65 src/etc/mtree/NetBSD.dist.tests
 cvs rdiff -u -r1.9 -r1.10 src/tests/usr.bin/Makefile
 cvs rdiff -u -r0 -r1.1 src/tests/usr.bin/sed/Makefile \
     src/tests/usr.bin/sed/t_sed.sh

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

>Unformatted:
 >Quarter:
 >Keywords:
 >Date-Required:

NetBSD Home
NetBSD PR Database Search

(Contact us) $NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2007 The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.