[456860] Improve handling of equivalent three-way text changes

Three-way diffing and patching is not supported by google diff match
patch (dmp) and simply applying the patch computed by dmp to the
opposite side, as we did before, would cause the equivalent changes to
be applied twice. Therefore, we had to re-implement the detection and
merging ourselves to support the handling of equivalent changes.

We also adapted the test cases and the implementation of the three-way
diff and merge to correspond to the behavior of the org.eclipse.compare
line differencing and introduced a determination of the currently used
line separator in the text, which is now also used when building the
merged version.

Bug: 456860
Change-Id: I12be9c68eda663e0206c9f230a9faf9631be3275
Signed-off-by: Philip Langer <planger@eclipsesource.com>

1 files changed, 303 insertions, 13 deletions

diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/diff/ThreeWayTextDiffTest.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/diff/ThreeWayTextDiffTest.java
index 0b4dae8f7..9d0434cee 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/diff/ThreeWayTextDiffTest.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/diff/ThreeWayTextDiffTest.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2014 EclipseSource Muenchen GmbH and others.
+ * Copyright (c) 2014, 2015 EclipseSource Muenchen GmbH and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
@@ -307,16 +307,29 @@ public class ThreeWayTextDiffTest {
 		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
 				+ "Nah, they got the metric system, they wouldn't know what a Quarter Pounder is." + NL //
 				+ "What do they call it?" + NL //
-				+ "I asked, what do they call it?" + NL //
-				+ "Do you hear me?" + NL //
+				+ "I asked, what do they call it?" + NL // changed
+				+ "Do you hear me?" + NL // added
 				+ "They call it a Royale with Cheese." + NL //
-				+ "Alright." + NL //
+				+ "Alright." + NL // added
 				+ "Royale with Cheese." + NL //
 				+ "That's right." + NL //
 				+ "What do they call a Big Mac?" + NL //
 				+ "A Big Mac's a Big Mac, but they call it Le Big Mac.";
 
-		assertConflictingBidirectional(origin, left, right);
+		final String merged = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "Nah, they got the metric system, they wouldn't know what a Quarter Pounder is." + NL //
+				+ "What do they call it?" + NL //
+				+ "I asked, what do they call it?" + NL // changed right
+				+ "Do you hear me?" + NL // added right
+				+ "They call it a \"Royale with Cheese\"." + NL // changed left
+				+ "Alright." + NL // added right
+				+ "Royale with Cheese." + NL //
+				+ "That's right." + NL //
+				+ "What do they call a Big Mac?" + NL //
+				+ "A Big Mac's a Big Mac, but they call it Le Big Mac.";
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
 	}
 
 	@Test
@@ -342,25 +355,202 @@ public class ThreeWayTextDiffTest {
 	}
 
 	@Test
-	public void addDifferentLinesIndirectlyAtSameLineInMultiLineText() throws IOException {
+	public void addDifferentLineAtTheBeginningInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?" + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Who's Zed?" + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		assertConflictingBidirectional(origin, left, right);
+	}
+
+	@Test
+	public void addDifferentLineAtTheEndOfMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Whose chopper is this?" + NL; // added
+
+		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Who's Zed?" + NL; // added
+
+		assertConflictingBidirectional(origin, left, right);
+	}
+
+	@Test
+	public void addDifferentMultipleLinesAtTheBeginningInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?" + NL // added same as right
+				+ "It's Zed's!" + NL // added same as right
+				+ "Who is Zed?" + NL // added different from right
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Whose chopper is this?" + NL // added same as left
+				+ "It's Zed's!" + NL // added same as left
+				+ "Who's Zed?" + NL // added different from left
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		assertConflictingBidirectional(origin, left, right);
+	}
+
+	@Test
+	public void addSameMultipleLinesAtTheBeginningOfFirstLineInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?" + NL // added same as right
+				+ "It's Zed's!" + NL // added same as right
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Whose chopper is this?" + NL // added same as left
+				+ "It's Zed's!" + NL // added same as left
+				+ "Who's Zed?" + NL // added additionally to left
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		// The merge result should be the right side, since right inserts an additional line and the rest are
+		// equal insertions
+		final String merged = right;
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void addSameMultipleLinesAtTheBeginningAndChangeOfFirstLineInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?" + NL // added same as right
+				+ "It's Zed's!" + NL // added same as right
+				+ "They do not call it a Quarter Pounder with Cheese?" + NL // changed
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Whose chopper is this?" + NL // added same as left
+				+ "It's Zed's!" + NL // added same as left
+				+ "Who's Zed?" + NL // added additionally to left
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String merged = "Whose chopper is this?" + NL // added
+				+ "It's Zed's!" + NL // added
+				+ "Who's Zed?" + NL // added additionally to left
+				+ "They do not call it a Quarter Pounder with Cheese?" + NL // changed left
+				+ "They call it a Royale with Cheese.";
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void addSameMultipleLinesAtTheBeginningAndChangeOfFirstLine2InMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?"
+				+ NL // added same as right
+				+ "It's Zed's!"
+				+ NL // added same as right
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Whose chopper is this?" + NL // added same as left
+				+ "It's Zed's!" + NL // added same as left
+				+ "Who's Zed?" + NL // added additionally to left
+				+ "They do not call it a Quarter Pounder with Cheese?" + NL // changed
+				+ "They call it a Royale with Cheese.";
+
+		final String merged = "Whose chopper is this?" + NL // added
+				+ "It's Zed's!" + NL // added
+				+ "Who's Zed?" + NL // added additionally to left
+				+ "They do not call it a Quarter Pounder with Cheese?" + NL // changed left
+				+ "They call it a Royale with Cheese.";
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void addDifferentLinesAtTheBeginningInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Whose chopper is this?" + NL // added
+				+ "Whose chopper is this?" + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Who's Zed?" + NL // added
+				+ "It's Zed's." + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		assertConflictingBidirectional(origin, left, right);
+	}
+
+	@Test
+	public void addSameLineAtTheBeginningInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String left = "Who's Zed?" + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String right = "Who's Zed?" + NL // added
+				+ "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese.";
+
+		final String merged = right;
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void changeAndAddDifferentLinesOnBothSides() throws IOException {
 		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
 				+ "They call it a Royale with Cheese." + NL //
 				+ "Royale with Cheese." + NL //
 				+ "That's right.";
 
 		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
-				+ "Nah, they got the metric system, they wouldn't know what a Quarter Pounder is." + NL // added
+				+ "Nah, they got the metric system.1" + NL // added
+				+ "Nah, they got the metric system.2" + NL // added
+				+ "Nah, they got the metric system.3" + NL // added
 				+ "They call it a \"Royale\" with Cheese." + NL // changed
 				+ "Royale with Cheese." + NL //
 				+ "That's right.";
 
-		final String right = "" // removed
-				+ "What do they call it?" + NL // added
-				+ "They call it a Royale with Cheese." + NL //
+		final String right = "What do they call it?" + NL // changed
+				+ "They call it a Royale with Cheese." + NL//
 				+ "Royale with Cheese." + NL //
-				+ "That's right.";
+				+ "That's right!"; // changed
 
-		assertConflictingBidirectional(origin, left, right);
+		final String merged = "What do they call it?" + NL // changed line 1 from right
+				+ "Nah, they got the metric system.1" + NL // added left
+				+ "Nah, they got the metric system.2" + NL // added left
+				+ "Nah, they got the metric system.3" + NL // added left
+				+ "They call it a \"Royale\" with Cheese." + NL// changed line 3 from left
+				+ "Royale with Cheese." + NL // unchanged on both sides
+				+ "That's right!"; // changed right
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
 	}
 
 	@Test
@@ -395,6 +585,97 @@ public class ThreeWayTextDiffTest {
 	}
 
 	@Test
+	public void addSameLineAtSameLineOnBothSidesInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL // added
+				+ "Royale with Cheese." + NL //
+				+ "That's right!!!"; // changed
+
+		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL // added
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String merged = left; // right didn't contribute a unique change
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void changeSameLineToSameContentOnBothSidesInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese!!!" + NL // changed
+				+ "Royale with Cheese." + NL //
+				+ "That's right!!!" + NL // changed
+				+ "They call it a Royale with Cheese!!!"; // added
+
+		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese!!!" + NL // changed
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String merged = left; // right didn't contribute a unique change
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void removeAndChangeVersusSameChangeInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right!"; // changed
+
+		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right!"; // changed
+
+		final String merged = left; // right didn't contribute a unique change
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
+	public void removeSameLineOnBothSidesInMultiLineText() throws IOException {
+		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "They call it a Royale with Cheese." + NL //
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String left = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "" // removed
+				+ "Royale with Cheese." + NL //
+				+ "That's right!!!"; // changed
+
+		final String right = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "" // removed
+				+ "Royale with Cheese." + NL //
+				+ "That's right.";
+
+		final String merged = left; // right didn't contribute a unique change
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
+	}
+
+	@Test
 	public void removeLineAndAddLineAtSameLineInMultiLineText() throws IOException {
 		final String origin = "They don't call it a Quarter Pounder with Cheese?" + NL //
 				+ "They call it a Royale with Cheese." + NL //
@@ -413,7 +694,16 @@ public class ThreeWayTextDiffTest {
 				+ "That's right." + NL //
 				+ "What do they call a Big Mac?"; // added
 
-		assertConflictingBidirectional(origin, left, right);
+		final String merged = "They don't call it a Quarter Pounder with Cheese?" + NL //
+				+ "Nah, they got the metric system, they wouldn't know what a Quarter Pounder is." + NL // added
+																										// left
+				+ "" // removed right
+				+ "Royale with Cheese." + NL //
+				+ "That's right." + NL //
+				+ "What do they call a Big Mac?"; // added right
+
+		assertNonConflictingBidirectional(origin, left, right);
+		assertMergedBidirectional(origin, left, right, merged);
 	}
 
 	private void assertNonConflictingBidirectional(String origin, String left, String right) {