[413520] Fixes IndexOutOfBoundsException on merging opposite references

The IndexOutOfBoundsExceptions occurred when a one-to-many reference has
been changed, whereas the original object on the single-valued side of
the one-to-many reference has been deleted. During the check for the
ordering of the target values affected by equivalent changes (in this
case, changes of opposite references) in
ReferenceChangeMerger.internalCheckOrdering(ReferenceChange, boolean),
the source and target container and, in the next step, their values at
the feature constituting the multi-valued side of a one-to-many
reference are obtained and their LCS is computed to finally move the
respective value. However, when the original object on the source side
has been deleted, the source container is null, and the values at the
respective feature are empty. DiffUtil.findInsertionIndex will still
return 0, so that EList.move(index, value) is called, whereas value is
not available in the list, which ultimately causes the exception.

This commit prevents the call of
ReferenceChangeMerger.internalCheckOrdering(ReferenceChange, boolean)
for any difference that is not an addition to a multi-valued feature in
the current merge (thus, not a move or a delete), since only for such
differences a check of the resulting order should be necessary.

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

5 files changed, 173 insertions, 19 deletions

diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/TwoWayBatchMergingTest.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/TwoWayBatchMergingTest.java
index 5a1279b54..7fe62cf0a 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/TwoWayBatchMergingTest.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/TwoWayBatchMergingTest.java
@@ -15,18 +15,24 @@ import static org.junit.Assert.assertEquals;
 import java.io.IOException;
 
 import org.eclipse.emf.common.util.BasicMonitor;
+import org.eclipse.emf.common.util.EList;
 import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.Diff;
 import org.eclipse.emf.compare.EMFCompare;
+import org.eclipse.emf.compare.ReferenceChange;
 import org.eclipse.emf.compare.internal.utils.DiffUtil;
 import org.eclipse.emf.compare.merge.BatchMerger;
 import org.eclipse.emf.compare.merge.IBatchMerger;
 import org.eclipse.emf.compare.merge.IMerger;
+import org.eclipse.emf.compare.merge.ReferenceChangeMerger;
 import org.eclipse.emf.compare.scope.DefaultComparisonScope;
 import org.eclipse.emf.compare.scope.IComparisonScope;
 import org.eclipse.emf.compare.tests.merge.data.TwoWayMergeInputData;
 import org.eclipse.emf.compare.tests.nodes.Node;
 import org.eclipse.emf.compare.tests.nodes.NodeMultipleContainment;
+import org.eclipse.emf.compare.tests.nodes.NodeOppositeRefOneToMany;
 import org.eclipse.emf.compare.tests.nodes.NodesPackage;
+import org.eclipse.emf.ecore.EObject;
 import org.eclipse.emf.ecore.resource.Resource;
 import org.junit.Test;
 
@@ -38,6 +44,10 @@ import org.junit.Test;
  */
 public class TwoWayBatchMergingTest {
 
+	private enum Direction {
+		LEFT_TO_RIGHT, RIGHT_TO_LEFT;
+	}
+
 	private TwoWayMergeInputData input = new TwoWayMergeInputData();
 
 	private IMerger.Registry mergerRegistry = IMerger.RegistryImpl.createStandaloneInstance();
@@ -46,11 +56,14 @@ public class TwoWayBatchMergingTest {
 	 * Tests a scenario in which an element is moved from one container to another, whereas the containment
 	 * reference in the original container (left) is not available in the target container (right). This lead
 	 * to a NPE in {@link DiffUtil#findInsertionIndex(Comparison, org.eclipse.emf.compare.Diff, boolean)} (cf.
-	 * Bug #440679). In particular, we have two differences: (1) Deletion of {@link NodeMultipleContainment}
-	 * "A" and (2) Move of {@link Node} "B" from {@link NodeMultipleContainment} "A" (reference
-	 * "containmentRef2") to {@link Node} "Root" into reference "containmentRef1". As a result, we move node
-	 * "B" originally contained through "containmentRef2" into a {@link Node}, which does not have the feature
+	 * Bug #440679).
+	 * <p>
+	 * In this test case we have two differences: (1) Deletion of {@link NodeMultipleContainment} "A" and (2)
+	 * Move of {@link Node} "B" from {@link NodeMultipleContainment} "A" (reference "containmentRef2") to
+	 * {@link Node} "Root" into reference "containmentRef1". As a result, we move node "B" originally
+	 * contained through "containmentRef2" into a {@link Node}, which does not have the feature
 	 * "containmentRef2".
+	 * </p>
 	 * 
 	 * @throws IOException
 	 *             if {@link TwoWayMergeInputData} fails to load the test models.
@@ -59,18 +72,7 @@ public class TwoWayBatchMergingTest {
 	public void mergingMoveToDifferentContainmentFeatureR2L() throws IOException {
 		final Resource left = input.getMoveToDifferentContainmentFeatureRTLLeft();
 		final Resource right = input.getMoveToDifferentContainmentFeatureRTLRight();
-
-		// perform comparison
-		final IComparisonScope scope = new DefaultComparisonScope(left, right, null);
-		Comparison comparison = EMFCompare.builder().build().compare(scope);
-
-		// batch merging of all detected differences:
-		final IBatchMerger merger = new BatchMerger(mergerRegistry);
-		merger.copyAllRightToLeft(comparison.getDifferences(), new BasicMonitor());
-
-		// check that models are equal after batch merging
-		Comparison assertionComparison = EMFCompare.builder().build().compare(scope);
-		assertEquals(0, assertionComparison.getDifferences().size());
+		batchMergeAndAssertEquality(left, right, Direction.RIGHT_TO_LEFT);
 	}
 
 	/**
@@ -84,14 +86,59 @@ public class TwoWayBatchMergingTest {
 	public void mergingMoveToDifferentContainmentFeatureL2R() throws IOException {
 		final Resource left = input.getMoveToDifferentContainmentFeatureL2RLeft();
 		final Resource right = input.getMoveToDifferentContainmentFeatureL2RRight();
+		batchMergeAndAssertEquality(left, right, Direction.LEFT_TO_RIGHT);
+	}
+
+	/**
+	 * Tests a scenario in which an opposite one-to-many reference is changed, whereas the original object on
+	 * the single-valued side of the one-to-many reference has no match. This lead to an
+	 * {@link IndexOutOfBoundsException} (cf. Bug #413520), because in the
+	 * {@link ReferenceChangeMerger#internalCheckOrdering(ReferenceChange, boolean) ordering check of the
+	 * equivalent changes}, the source container is <code>null</code> leading to an empty source list. This
+	 * leads to an invocation of {@link EList#move(int, EObject)} on an empty list.
+	 * <p>
+	 * In this test case, we have the following differences: (1) the deletion of {@link Node} "C" (only
+	 * available on the right-hand side), as a result, (2) the deletion of the reference to {@link Node} "C"
+	 * from {@link NodeOppositeRefOneToMany} "A" at its feature
+	 * {@link NodeOppositeRefOneToMany#getDestination() destination}, and (3 & 4) the change of the opposite
+	 * references {@link NodeOppositeRefOneToMany#getSource() source} and
+	 * {@link NodeOppositeRefOneToMany#getDestination() destination} between {@link NodeOppositeRefOneToMany
+	 * nodes} "A" and "B" (both have a match in the left and right model version).
+	 * </p>
+	 * 
+	 * @throws IOException
+	 *             if {@link TwoWayMergeInputData} fails to load the test models.
+	 */
+	@Test
+	public void mergingOppositeReferenceChangeWithoutMatchingOriginalL2R() throws IOException {
+		final Resource left = input.getOppositeReferenceChangeWithoutMatchingOrignalContainerL2RLeft();
+		final Resource right = input.getOppositeReferenceChangeWithoutMatchingOrignalContainerL2RRight();
+		batchMergeAndAssertEquality(left, right, Direction.LEFT_TO_RIGHT);
+	}
 
+	/**
+	 * Merges the given resources {@code left} and {@code right} using the {@link BatchMerger} in the
+	 * specified {@code direction}, re-compares left and right, and assert their equality in the end.
+	 * 
+	 * @param left
+	 *            left resource.
+	 * @param right
+	 *            right resource.
+	 */
+	private void batchMergeAndAssertEquality(Resource left, Resource right, Direction direction) {
 		// perform comparison
 		final IComparisonScope scope = new DefaultComparisonScope(left, right, null);
 		Comparison comparison = EMFCompare.builder().build().compare(scope);
+		final EList<Diff> differences = comparison.getDifferences();
 
 		// batch merging of all detected differences:
 		final IBatchMerger merger = new BatchMerger(mergerRegistry);
-		merger.copyAllLeftToRight(comparison.getDifferences(), new BasicMonitor());
+		switch (direction) {
+			case LEFT_TO_RIGHT:
+				merger.copyAllLeftToRight(differences, new BasicMonitor());
+			case RIGHT_TO_LEFT:
+				merger.copyAllRightToLeft(differences, new BasicMonitor());
+		}
 
 		// check that models are equal after batch merging
 		Comparison assertionComparison = EMFCompare.builder().build().compare(scope);
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/TwoWayMergeInputData.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/TwoWayMergeInputData.java
index b56de0640..fee806db6 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/TwoWayMergeInputData.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/TwoWayMergeInputData.java
@@ -32,4 +32,12 @@ public class TwoWayMergeInputData extends AbstractInputData {
 	public Resource getMoveToDifferentContainmentFeatureL2RRight() throws IOException {
 		return loadFromClassLoader("twoway/movedifferentcontainmentfeature/ltr/right.nodes");
 	}
+
+	public Resource getOppositeReferenceChangeWithoutMatchingOrignalContainerL2RLeft() throws IOException {
+		return loadFromClassLoader("twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/left.nodes");
+	}
+
+	public Resource getOppositeReferenceChangeWithoutMatchingOrignalContainerL2RRight() throws IOException {
+		return loadFromClassLoader("twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/right.nodes");
+	}
 }
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/left.nodes b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/left.nodes
new file mode 100644
index 000000000..0a5bfb13a
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/left.nodes
@@ -0,0 +1,19 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<nodes:Node
+    xmi:version="2.0"
+    xmlns:xmi="http://www.omg.org/XMI"
+    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+    xmlns:nodes="http://www.eclipse.org/emf/compare/tests/nodes"
+    xmi:id="_root"
+    name="Root">
+  <containmentRef1
+      xsi:type="nodes:NodeOppositeRefOneToMany"
+      xmi:id="_A"
+      name="A"
+      source="B"/>
+  <containmentRef1
+      xsi:type="nodes:NodeOppositeRefOneToMany"
+      xmi:id="_B"
+      name="B"
+      destination="A"/>
+</nodes:Node>
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/right.nodes b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/right.nodes
new file mode 100644
index 000000000..336b9b93c
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/merge/data/twoway/oppositereferencechangewithoutmatchingorignalcontainer/ltr/right.nodes
@@ -0,0 +1,23 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<nodes:Node
+    xmi:version="2.0"
+    xmlns:xmi="http://www.omg.org/XMI"
+    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+    xmlns:nodes="http://www.eclipse.org/emf/compare/tests/nodes"
+    xmi:id="_root"
+    name="Root">
+  <containmentRef1
+      xsi:type="nodes:NodeOppositeRefOneToMany"
+      xmi:id="_A"
+      name="A"
+      source="C"/>
+  <containmentRef1
+      xsi:type="nodes:NodeOppositeRefOneToMany"
+      xmi:id="_B"
+      name="B"/>
+  <containmentRef1
+      xsi:type="nodes:NodeOppositeRefOneToMany"
+      xmi:id="_C"
+      name="C"
+      destination="A"/>
+</nodes:Node>
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/ReferenceChangeMerger.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/ReferenceChangeMerger.java
index c13044c70..874a42b4e 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/ReferenceChangeMerger.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/merge/ReferenceChangeMerger.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2012, 2014 Obeo.
+ * Copyright (c) 2012, 2014 Obeo 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
@@ -7,6 +7,7 @@
  * 
  * Contributors:
  *     Obeo - initial API and implementation
+ *     Philip Langer - fixes for bug 413520
  *******************************************************************************/
 package org.eclipse.emf.compare.merge;
 
@@ -617,7 +618,7 @@ public class ReferenceChangeMerger extends AbstractMerger {
 		while (impliedReferenceChanges.hasNext()) {
 			final ReferenceChange implied = impliedReferenceChanges.next();
 			if (implied != diff && implied.getState() == DifferenceState.MERGED) {
-				if (implied.getReference().isMany() && implied.getKind() != DifferenceKind.MOVE) {
+				if (implied.getReference().isMany() && isAdd(implied, rightToLeft)) {
 					internalCheckOrdering(implied, rightToLeft);
 				}
 			}
@@ -625,6 +626,62 @@ public class ReferenceChangeMerger extends AbstractMerger {
 	}
 
 	/**
+	 * Specifies whether the given {@code diff} will add a value in the target model for the current merging.
+	 * <p>
+	 * To check whether the {@code diff} is an addition, we have to check the direction of the merge,
+	 * specified in {@code rightToLeft} and the {@link Diff#getSource() source of the diff}. Therefore, this
+	 * method delegates to {@link #isLeftAddOrRightDelete(ReferenceChange)} and
+	 * {@link #isLeftDeleteOrRightAdd(ReferenceChange)}.
+	 * </p>
+	 * 
+	 * @param diff
+	 *            The difference to check.
+	 * @param rightToLeft
+	 *            Direction of the merge.
+	 * @return <code>true</code> if {@code diff} will add a value with this merge, <code>false</code>
+	 *         otherwise.
+	 */
+	private boolean isAdd(ReferenceChange diff, boolean rightToLeft) {
+		if (rightToLeft) {
+			return isLeftDeleteOrRightAdd(diff);
+		} else {
+			return isLeftAddOrRightDelete(diff);
+		}
+	}
+
+	/**
+	 * Specifies whether the given {@code diff} is either an addition on the left-hand side or a deletion on
+	 * the right-hand side.
+	 * 
+	 * @param diff
+	 *            The difference to check.
+	 * @return <code>true</code> if it is a left addition or a right deletion.
+	 */
+	private boolean isLeftAddOrRightDelete(ReferenceChange diff) {
+		if (diff.getSource() == DifferenceSource.LEFT) {
+			return diff.getKind() == DifferenceKind.ADD;
+		} else {
+			return diff.getKind() == DifferenceKind.DELETE;
+		}
+	}
+
+	/**
+	 * Specifies whether the given {@code diff} is either a deletion on the left-hand side or an addition on
+	 * the right-hand side.
+	 * 
+	 * @param diff
+	 *            The difference to check.
+	 * @return <code>true</code> if it is a left deletion or a right addition.
+	 */
+	private boolean isLeftDeleteOrRightAdd(ReferenceChange diff) {
+		if (diff.getSource() == DifferenceSource.LEFT) {
+			return diff.getKind() == DifferenceKind.DELETE;
+		} else {
+			return diff.getKind() == DifferenceKind.ADD;
+		}
+	}
+
+	/**
 	 * Checks a particular difference for the ordering of its target values. This will be used to double-check
 	 * that equivalent differences haven't been "broken" by EMF by not preserving their value order.
 	 * <p>