From a7511dd43d9afe8025a6d7bd2fcccf8f594a6f2b Mon Sep 17 00:00:00 2001
From: Russ Cox <rsc@swtch.com>
Date: Fri, 7 Dec 2007 15:32:45 -0500
Subject: libregexp: fix ambiguous match selection

	echo SYSSYSR1 | sed 's/SYS.+/sysr1/'

was producing SYSsysr1 instead of sysr1.
Bug was introduced during overflow cleanup earlier this year.

Also bring regexec.c and rregexec.c into sync again.
Also allocate large enough lists in the regexec2/rregexec2 case.
---
 src/libregexp/regaux.c | 105 ++++++++++++++++++++++++-------------------------
 1 file changed, 52 insertions(+), 53 deletions(-)

(limited to 'src/libregexp/regaux.c')

diff --git a/src/libregexp/regaux.c b/src/libregexp/regaux.c
index b854b5ac..39e67725 100644
--- a/src/libregexp/regaux.c
+++ b/src/libregexp/regaux.c
@@ -23,90 +23,89 @@ _renewmatch(Resub *mp, int ms, Resublist *sp)
 }
 
 /*
- * Note optimization in _renewthread:
- * 	*lp must be pending when _renewthread called; if *l has been looked
- *		at already, the optimization is a bug.
+ * Add ip to the list [lp, elp], but only if it is not there already.
+ * These work lists are stored and processed in increasing
+ * order of sp[0], so if the ip is there already, the one that's
+ * there already is a more left match and takes priority.
  */
-extern Relist*
-_renewthread(Relist *lp,	/* _relist to add to */
+static Relist*
+_renewthread1(Relist *lp,	/* Relist to add to */
+	Relist *elp,		/* limit pointer for Relist */
 	Reinst *ip,		/* instruction to add */
 	int ms,
 	Resublist *sep)		/* pointers to subexpressions */
 {
 	Relist *p;
 
-	for(p=lp; p->inst; p++){
-		if(p->inst == ip){
-			if(sep->m[0].s.sp < p->se.m[0].s.sp){
-				if(ms > 1)
-					p->se = *sep;
-				else
-					p->se.m[0] = sep->m[0];
-			}
+	for(p=lp; p->inst; p++)
+		if(p->inst == ip)
 			return 0;
-		}
-	}
+	
+	if(p == elp)	/* refuse to overflow buffer */
+		return elp;
+
 	p->inst = ip;
 	if(ms > 1)
 		p->se = *sep;
 	else
 		p->se.m[0] = sep->m[0];
-	(++p)->inst = 0;
+	(p+1)->inst = 0;
 	return p;
 }
 
+extern int
+_renewthread(Relist *lp, Relist *elp, Reinst *ip, int ms, Resublist *sep)
+{
+	Relist *ap;
+
+	ap = _renewthread1(lp, elp, ip, ms, sep);
+	if(ap == 0)
+		return 0;
+	if(ap == elp)
+		return -1;
+
+	/*
+	 * Added ip to list at ap.  
+	 * Expand any ORs right now, so that entire
+	 * work list ends up being sorted by increasing m[0].sp.
+	 */
+	for(; ap->inst; ap++){
+		if(ap->inst->type == OR){
+			if(_renewthread1(lp, elp, ap->inst->u1.right, ms, &ap->se) == elp)
+				return -1;
+			if(_renewthread1(lp, elp, ap->inst->u2.next, ms, &ap->se) == elp)
+				return -1;
+		}
+	}
+	return 0;
+}
+
 /*
  * same as renewthread, but called with
  * initial empty start pointer.
  */
-extern Relist*
+extern int
 _renewemptythread(Relist *lp,	/* _relist to add to */
+	Relist *elp,
 	Reinst *ip,		/* instruction to add */
 	int ms,
 	char *sp)		/* pointers to subexpressions */
 {
-	Relist *p;
-
-	for(p=lp; p->inst; p++){
-		if(p->inst == ip){
-			if(sp < p->se.m[0].s.sp) {
-				if(ms > 1)
-					memset(&p->se, 0, sizeof(p->se));
-				p->se.m[0].s.sp = sp;
-			}
-			return 0;
-		}
-	}
-	p->inst = ip;
+	Resublist sep;
+	
 	if(ms > 1)
-		memset(&p->se, 0, sizeof(p->se));
-	p->se.m[0].s.sp = sp;
-	(++p)->inst = 0;
-	return p;
+		memset(&sep, 0, sizeof sep);
+	sep.m[0].s.sp = sp;
+	sep.m[0].e.ep = 0;
+	return _renewthread(lp, elp, ip, ms, &sep);
 }
 
-extern Relist*
+extern int
 _rrenewemptythread(Relist *lp,	/* _relist to add to */
+	Relist *elp,
 	Reinst *ip,		/* instruction to add */
 	int ms,
 	Rune *rsp)		/* pointers to subexpressions */
 {
-	Relist *p;
-
-	for(p=lp; p->inst; p++){
-		if(p->inst == ip){
-			if(rsp < p->se.m[0].s.rsp) {
-				if(ms > 1)
-					memset(&p->se, 0, sizeof(p->se));
-				p->se.m[0].s.rsp = rsp;
-			}
-			return 0;
-		}
-	}
-	p->inst = ip;
-	if(ms > 1)
-		memset(&p->se, 0, sizeof(p->se));
-	p->se.m[0].s.rsp = rsp;
-	(++p)->inst = 0;
-	return p;
+	return _renewemptythread(lp, elp, ip, ms, (char*)rsp);
 }
-- 
cgit v1.2.3