aboutsummaryrefslogtreecommitdiffstats
path: root/org.eclipse.jgit
diff options
context:
space:
mode:
authorShawn Pearce <spearce@spearce.org>2014-07-25 08:17:27 -0700
committerShawn Pearce <spearce@spearce.org>2014-07-25 10:04:23 -0700
commitd11ca1b0845987f1e17c284ea86a264b45bf52d7 (patch)
tree6ad60d8442969868f0a8dbbcc9c6ca77550406e2 /org.eclipse.jgit
parentf3fc3797579ac0bf55648bad560e7daa5e6df9b5 (diff)
downloadjgit-d11ca1b0845987f1e17c284ea86a264b45bf52d7.tar.gz
jgit-d11ca1b0845987f1e17c284ea86a264b45bf52d7.zip
HistogramDiff: Convert stack recursion to heap managed queue
Each time the longest common substring is found the diff algorithm recurses to reprocess the regions before and after the common string. Large files with many edits can trigger StackOverflowError as the algorithm attempts to process a deeply split tree of regions. This is especially prone to happen in servers where the Java stack size may have been limited to 1M or even 256K. To keep edits produced in order a queue is used to process edits in a depth-first strategy. Change-Id: Iae7260c6934efdffac7c7bee4d3633a8208924f7
Diffstat (limited to 'org.eclipse.jgit')
-rw-r--r--org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java20
1 files changed, 14 insertions, 6 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java
index 0979db1e78..e57faaf858 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java
@@ -43,6 +43,9 @@
package org.eclipse.jgit.diff;
+import java.util.ArrayList;
+import java.util.List;
+
/**
* An extended form of Bram Cohen's patience diff algorithm.
* <p>
@@ -130,15 +133,14 @@ public class HistogramDiff extends LowLevelDiffAlgorithm {
public <S extends Sequence> void diffNonCommon(EditList edits,
HashedSequenceComparator<S> cmp, HashedSequence<S> a,
HashedSequence<S> b, Edit region) {
- new State<S>(edits, cmp, a, b).diffReplace(region);
+ new State<S>(edits, cmp, a, b).diffRegion(region);
}
private class State<S extends Sequence> {
private final HashedSequenceComparator<S> cmp;
-
private final HashedSequence<S> a;
-
private final HashedSequence<S> b;
+ private final List<Edit> queue = new ArrayList<Edit>();
/** Result edits we have determined that must be made to convert a to b. */
final EditList edits;
@@ -151,7 +153,13 @@ public class HistogramDiff extends LowLevelDiffAlgorithm {
this.edits = edits;
}
- void diffReplace(Edit r) {
+ void diffRegion(Edit r) {
+ diffReplace(r);
+ while (!queue.isEmpty())
+ diff(queue.remove(queue.size() - 1));
+ }
+
+ private void diffReplace(Edit r) {
Edit lcs = new HistogramDiffIndex<S>(maxChainLength, cmp, a, b, r)
.findLongestCommonSequence();
if (lcs != null) {
@@ -163,8 +171,8 @@ public class HistogramDiff extends LowLevelDiffAlgorithm {
//
edits.add(r);
} else {
- diff(r.before(lcs));
- diff(r.after(lcs));
+ queue.add(r.after(lcs));
+ queue.add(r.before(lcs));
}
} else if (fallback instanceof LowLevelDiffAlgorithm) {