Improve MergeAlgorithm to produce smaller conflicts

The merge algorithm was reporting conflicts which where to big.

Example: The common base was "ABC", the "ours" version contained
"AB1C" (the addition of "1" after pos 2) and the "theirs" version also
contained "AB1C". We have two potentially conflicting edits in the
same region which happen to bring in exactly the same content. This
should not be a conflict - but was previously reported as
"AB<<<1===1>>>C".

This is fixed by checking every conflicting chunk whether the
conflicting regions have a common prefix or suffix and by removing
this regions from the conflict.

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

1 files changed, 35 insertions, 4 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 deae82e762..2c8386b8c2 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
@@ -195,11 +195,42 @@ public final class MergeAlgorithm {
 					theirsEndB += oursEdit.getEndA() - theirsEdit.getEndA();
 				}
 
+				// A conflicting region is found. Strip off common lines in
+				// in the beginning and the end of the conflicting region
+				int conflictLen = Math.min(oursEndB - oursBeginB, theirsEndB
+						- theirsBeginB);
+				int commonPrefix = 0;
+				while (commonPrefix < conflictLen
+						&& ours.equals(oursBeginB + commonPrefix, theirs,
+								theirsBeginB + commonPrefix))
+					commonPrefix++;
+				conflictLen -= commonPrefix;
+				int commonSuffix = 0;
+				while (commonSuffix < conflictLen
+						&& ours.equals(oursEndB - commonSuffix - 1, theirs,
+								theirsEndB - commonSuffix - 1))
+					commonSuffix++;
+				conflictLen -= commonSuffix;
+
+				// Add the common lines at start of conflict
+				if (commonPrefix > 0)
+					result.add(1, oursBeginB, oursBeginB + commonPrefix,
+							ConflictState.NO_CONFLICT);
+
 				// Add the conflict
-				result.add(1, oursBeginB, oursEndB,
-						ConflictState.FIRST_CONFLICTING_RANGE);
-				result.add(2, theirsBeginB, theirsEndB,
-						ConflictState.NEXT_CONFLICTING_RANGE);
+				if (conflictLen > 0) {
+					result.add(1, oursBeginB + commonPrefix, oursEndB
+							- commonSuffix,
+							ConflictState.FIRST_CONFLICTING_RANGE);
+					result.add(2, theirsBeginB + commonPrefix, theirsEndB
+							- commonSuffix,
+							ConflictState.NEXT_CONFLICTING_RANGE);
+				}
+
+				// Add the common lines at end of conflict
+				if (commonSuffix > 0)
+					result.add(1, oursEndB - commonSuffix, oursEndB,
+							ConflictState.NO_CONFLICT);
 
 				current = Math.max(oursEdit.getEndA(), theirsEdit.getEndA());
 				oursEdit = nextOursEdit;