From 79cb2ebb92c18af11edf5eea238425d86eef173d Mon Sep 17 00:00:00 2001
From: Stefan Beller <sbeller@google.com>
Date: Thu, 19 Jul 2018 15:19:42 -0700
Subject: xdiff/histogram: remove tail recursion

When running the same reproduction script as the previous patch,
it turns out the stack is too small, which can be easily avoided.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
index fc2d3cd..ec85f59 100644
--- a/xdiff/xhistogram.c
+++ b/xdiff/xhistogram.c
@@ -318,7 +318,9 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
 {
 	struct region lcs;
 	int lcs_found;
-	int result = -1;
+	int result;
+redo:
+	result = -1;
 
 	if (count1 <= 0 && count2 <= 0)
 		return 0;
@@ -355,11 +357,17 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
 						line2, lcs.begin2 - line2);
 			if (result)
 				goto out;
-			result = histogram_diff(xpp, env,
-						lcs.end1 + 1, LINE_END(1) - lcs.end1,
-						lcs.end2 + 1, LINE_END(2) - lcs.end2);
-			if (result)
-				goto out;
+			/*
+			 * result = histogram_diff(xpp, env,
+			 *            lcs.end1 + 1, LINE_END(1) - lcs.end1,
+			 *            lcs.end2 + 1, LINE_END(2) - lcs.end2);
+			 * but let's optimize tail recursion ourself:
+			*/
+			count1 = LINE_END(1) - lcs.end1;
+			line1 = lcs.end1 + 1;
+			count2 = LINE_END(2) - lcs.end2;
+			line2 = lcs.end2 + 1;
+			goto redo;
 		}
 	}
 out:
-- 
cgit v0.10.2-6-g49f6