Remove recursive call in DiffUtils.calcUnifiedDiff to avoid StackOverflowError
Java's default stack size is limited to 1MB, which is far smaller than the memory we could use. Luckily, calcUnifiedDiff can be implemented without recursion and still preserve the readability.
RELNOTES=n/a
GOOGLE:
@@ -19,6 +19,7 @@ import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
@@ -116,6 +117,7 @@ final class DiffUtils {
}
private void calcUnifiedDiff(int i, int j) {
+ while (i > 0 || j > 0) {
if (i > 0
&& j > 0
&& original[i] == revised[j]
@@ -123,19 +125,23 @@ final class DiffUtils {
// multiple solutions.
&& lcs[i - 1][j - 1] + 1 > lcs[i - 1][j]
&& lcs[i - 1][j - 1] + 1 > lcs[i][j - 1]) {
- calcUnifiedDiff(i - 1, j - 1);
unifiedDiffType.add(' ');
unifiedDiffContentId.add(original[i]);
+ i--;
+ j--;
} else if (j > 0 && (i == 0 || lcs[i][j - 1] >= lcs[i - 1][j])) {
- calcUnifiedDiff(i, j - 1);
unifiedDiffType.add('+');
unifiedDiffContentId.add(revised[j]);
+ j--;
} else if (i > 0 && (j == 0 || lcs[i][j - 1] < lcs[i - 1][j])) {
- calcUnifiedDiff(i - 1, j);
unifiedDiffType.add('-');
unifiedDiffContentId.add(original[i]);
+ i--;
}
}
+ Collections.reverse(unifiedDiffType);
+ Collections.reverse(unifiedDiffContentId);
+ }
/**
* Generate the unified diff with a given context size
