bdiff: do not use recursion / avoid stackoverflow (issue1940) stable
authorAlistair Bell <alistair@bellsonline.com>
Thu, 18 Feb 2010 10:32:51 +0100
branchstable
changeset 10500 e96597c8d0ea
parent 10499 4401b0dfee88
child 10501 a27af7229850
bdiff: do not use recursion / avoid stackoverflow (issue1940)
mercurial/bdiff.c
--- a/mercurial/bdiff.c	Thu Feb 18 05:55:05 2010 +0100
+++ b/mercurial/bdiff.c	Thu Feb 18 10:32:51 2010 +0100
@@ -226,19 +226,23 @@
 {
 	int i, j, k;
 
-	/* find the longest match in this chunk */
-	k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j);
-	if (!k)
-		return;
+	while (1) {
+		/* find the longest match in this chunk */
+		k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j);
+		if (!k)
+			return;
 
-	/* and recurse on the remaining chunks on either side */
-	recurse(a, b, pos, a1, i, b1, j, l);
-	l->head->a1 = i;
-	l->head->a2 = i + k;
-	l->head->b1 = j;
-	l->head->b2 = j + k;
-	l->head++;
-	recurse(a, b, pos, i + k, a2, j + k, b2, l);
+		/* and recurse on the remaining chunks on either side */
+		recurse(a, b, pos, a1, i, b1, j, l);
+		l->head->a1 = i;
+		l->head->a2 = i + k;
+		l->head->b1 = j;
+		l->head->b2 = j + k;
+		l->head++;
+		/* tail-recursion didn't happen, so doing equivalent iteration */
+		a1 = i + k;
+		b1 = j + k;
+	}
 }
 
 static struct hunklist diff(struct line *a, int an, struct line *b, int bn)