Optimize MergeAlgorithm if ours or theirs is empty

Previously when merging two contents with a non-empty base and one of
the contents was empty (size == 0) and the other was modified there
was a potentially expensive calculation until we finally always come
to the same result -> the complete non-deleted content should collide
with the empty content.

This proposal adds an optimization to detect empty input content and
to produce the appropriate result immediatly.

Change-Id: Ie6a837260c19d808f0e99173f570ff96dd22acd3
Signed-off-by: Christian Halstrick <christian.halstrick@sap.com>

1 files changed, 31 insertions, 0 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
index e6688f5bc9..112550a1de 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
@@ -103,6 +103,37 @@ public final class MergeAlgorithm {
 		sequences.add(ours);
 		sequences.add(theirs);
 		MergeResult<S> result = new MergeResult<S>(sequences);
+
+		if (ours.size() == 0) {
+			if (theirs.size() != 0) {
+				EditList theirsEdits = diffAlg.diff(cmp, base, theirs);
+				if (!theirsEdits.isEmpty()) {
+					// we deleted, they modified -> Let their complete content
+					// conflict with empty text
+					result.add(1, 0, 0, ConflictState.FIRST_CONFLICTING_RANGE);
+					result.add(2, 0, theirs.size(),
+							ConflictState.NEXT_CONFLICTING_RANGE);
+				} else
+					// we deleted, they didn't modify -> Let our deletion win
+					result.add(1, 0, 0, ConflictState.NO_CONFLICT);
+			} else
+				// we and they deleted -> return a single chunk of nothing
+				result.add(1, 0, 0, ConflictState.NO_CONFLICT);
+			return result;
+		} else if (theirs.size() == 0) {
+			EditList oursEdits = diffAlg.diff(cmp, base, ours);
+			if (!oursEdits.isEmpty()) {
+				// we modified, they deleted -> Let our complete content
+				// conflict with empty text
+				result.add(1, 0, ours.size(),
+						ConflictState.FIRST_CONFLICTING_RANGE);
+				result.add(2, 0, 0, ConflictState.NEXT_CONFLICTING_RANGE);
+			} else
+				// they deleted, we didn't modify -> Let their deletion win
+				result.add(2, 0, 0, ConflictState.NO_CONFLICT);
+			return result;
+		}
+
 		EditList oursEdits = diffAlg.diff(cmp, base, ours);
 		Iterator<Edit> baseToOurs = oursEdits.iterator();
 		EditList theirsEdits = diffAlg.diff(cmp, base, theirs);