[486923,488941] Fix Stack Overflow in ThreeWayComparisonGroupProvider

When conflicts contain diffs which are refined by containment reference
changes located in a match above a Stackoverflow exception can occur.
This is now avoided.

Bug: 486923
Bug: 488941
Change-Id: I1e6e4b465450baf07c8141d1580cf854bcd02783
Signed-off-by: Simon Delisle <simon.delisle@ericsson.com>
Signed-off-by: Edgar Mueller <emueller@eclipsesource.com>
Signed-off-by: Stefan Dirix <sdirix@eclipsesource.com>
Signed-off-by: Alexandra Buzila <abuzila@eclipsesource.com>
Signed-off-by: Philip Langer <planger@eclipsesource.com>
Also-by: Alexandra Buzila <abuzila@eclipsesource.com>
Also-by: Simon Delisle <simon.delisle@ericsson.com>

7 files changed, 146 insertions, 20 deletions

diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/ThreeWayComparisonGroupProviderTest.java b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/ThreeWayComparisonGroupProviderTest.java
new file mode 100644
index 000000000..ec7a3265a
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/ThreeWayComparisonGroupProviderTest.java
@@ -0,0 +1,48 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Ericsson 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
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * Contributors:
+ *     Simon Delisle - bug 486923
+ *******************************************************************************/
+package org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider;
+
+import java.io.IOException;
+
+import org.eclipse.emf.compare.Comparison;
+import org.eclipse.emf.compare.rcp.ui.internal.structuremergeviewer.groups.impl.ThreeWayComparisonGroupProvider;
+import org.eclipse.emf.compare.rcp.ui.internal.structuremergeviewer.groups.provider.TreeNodeItemProviderSpec;
+import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.data.ecore.bug486923.Bug486923InputData;
+import org.eclipse.emf.edit.tree.TreeFactory;
+import org.eclipse.emf.edit.tree.TreeNode;
+import org.junit.Before;
+import org.junit.Test;
+
+@SuppressWarnings("restriction")
+public class ThreeWayComparisonGroupProviderTest extends AbstractTestTreeNodeItemProviderAdapter {
+
+	private TreeNodeItemProviderSpec itemProvider;
+
+	@Override
+	@Before
+	public void before() throws IOException {
+		super.before();
+		itemProvider = (TreeNodeItemProviderSpec) treeItemProviderAdapterFactory.createTreeNodeAdapter();
+	}
+
+	@Test
+	public void testBug486923() throws IOException {
+		Comparison comparison = getComparison(new Bug486923InputData());
+
+		TreeNode treeNode = TreeFactory.eINSTANCE.createTreeNode();
+		treeNode.setData(comparison);
+		treeNode.eAdapters().add(new ThreeWayComparisonGroupProvider());
+
+		// we don't expect a stack overflow when obtaining the children
+		itemProvider.getChildren(treeNode);
+	}
+
+}
diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/Bug486923InputData.java b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/Bug486923InputData.java
new file mode 100644
index 000000000..2e28d3d3b
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/Bug486923InputData.java
@@ -0,0 +1,33 @@
+/*******************************************************************************
+ * Copyright (c) 2016 Ericsson 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
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * Contributors:
+ *     Simon Delisle - bug 486923
+ *******************************************************************************/
+package org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.data.ecore.bug486923;
+
+import java.io.IOException;
+
+import org.eclipse.emf.compare.tests.edit.data.ResourceScopeProvider;
+import org.eclipse.emf.compare.tests.framework.AbstractInputData;
+import org.eclipse.emf.ecore.resource.Resource;
+
+public class Bug486923InputData extends AbstractInputData implements ResourceScopeProvider {
+
+	public Resource getLeft() throws IOException {
+		return loadFromClassLoader("left.ecore");
+	}
+
+	public Resource getRight() throws IOException {
+		return loadFromClassLoader("right.ecore");
+	}
+
+	public Resource getOrigin() throws IOException {
+		return loadFromClassLoader("ancestor.ecore");
+	}
+
+}
diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/ancestor.ecore b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/ancestor.ecore
new file mode 100644
index 000000000..f9dc4fdf5
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/ancestor.ecore
@@ -0,0 +1,12 @@
+<?xml version="1.0" encoding="UTF-8"?>

+<ecore:EPackage xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:ecore="http://www.eclipse.org/emf/2002/Ecore"

+    xmi:id="_root" name="root" nsURI="http://www.eclipse.org/emf/compare/conflicts/move/delete"

+    nsPrefix="r">

+  <eSubpackages xmi:id="_packageA" name="packageA">

+    <eSubpackages xmi:id="_shouldNotBePresentAfterMerge" name="shouldNotBePresentAfterMerge">

+      <eSubpackages xmi:id="_containerPackage" name="containerPackage">

+        <eSubpackages xmi:id="_childPackage" name="childPackage"/>

+      </eSubpackages>

+    </eSubpackages>

+  </eSubpackages>

+</ecore:EPackage>

diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/left.ecore b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/left.ecore
new file mode 100644
index 000000000..46bb331ac
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/left.ecore
@@ -0,0 +1,6 @@
+<?xml version="1.0" encoding="UTF-8"?>

+<ecore:EPackage xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:ecore="http://www.eclipse.org/emf/2002/Ecore"

+    xmi:id="_root" name="root" nsURI="http://www.eclipse.org/emf/compare/conflicts/move/delete"

+    nsPrefix="r">

+  <eSubpackages xmi:id="_packageA" name="packageA"/>

+</ecore:EPackage>

diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/right.ecore b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/right.ecore
new file mode 100644
index 000000000..5544a7d77
--- /dev/null
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/structuremergeviewer/groups/provider/data/ecore/bug486923/right.ecore
@@ -0,0 +1,10 @@
+<?xml version="1.0" encoding="UTF-8"?>

+<ecore:EPackage xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:ecore="http://www.eclipse.org/emf/2002/Ecore"

+    xmi:id="_root" name="root" nsURI="http://www.eclipse.org/emf/compare/conflicts/move/delete"

+    nsPrefix="r">

+  <eSubpackages xmi:id="_packageA" name="packageA">

+    <eSubpackages xmi:id="_childPackage" name="childPackage">

+      <eSubpackages xmi:id="_containerPackage" name="containerPackage"/>

+    </eSubpackages>

+  </eSubpackages>

+</ecore:EPackage>

diff --git a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/suite/AllTests.java b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/suite/AllTests.java
index f7f7d24a8..b803ee7ec 100644
--- a/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/suite/AllTests.java
+++ b/plugins/org.eclipse.emf.compare.rcp.ui.tests/src/org/eclipse/emf/compare/rcp/ui/tests/suite/AllTests.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2013, 2015 Obeo.
+ * Copyright (c) 2013, 2016 Obeo.
  * 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 - bug 486923
  *******************************************************************************/
 package org.eclipse.emf.compare.rcp.ui.tests.suite;
 
@@ -24,6 +25,7 @@ import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.TestBasi
 import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.TestComparisonTreeNodeItemProviderSpec;
 import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.TestMatchTreeNodeItemProviderSpec;
 import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.TestReferenceChangeTreeNodeItemProviderSpec;
+import org.eclipse.emf.compare.rcp.ui.tests.structuremergeviewer.groups.provider.ThreeWayComparisonGroupProviderTest;
 import org.eclipse.emf.compare.tests.nodes.NodesPackage;
 import org.eclipse.emf.compare.tests.nodes.util.NodesResourceFactoryImpl;
 import org.eclipse.emf.ecore.EPackage;
@@ -34,13 +36,11 @@ import org.junit.runners.Suite;
 import org.junit.runners.Suite.SuiteClasses;
 
 @RunWith(Suite.class)
-@SuiteClasses({TestComparisonTreeNodeItemProviderSpec.class, 
-			   TestMatchTreeNodeItemProviderSpec.class, 
-			   TestReferenceChangeTreeNodeItemProviderSpec.class,
-			   MergeViewerItemTest.class, MergeViewerItemPseudoConflictTest.class, MergeViewerItemFeatureMapsTest.class,
-			   TestBasicDifferenceGroupImpl.class, BugsTestSuite.class,
-			   TestFeatureMapDifferencesFilter.class,
-			   RCPMatchEngineFactoryRegistryTest.class})
+@SuiteClasses({ TestComparisonTreeNodeItemProviderSpec.class, TestMatchTreeNodeItemProviderSpec.class,
+		TestReferenceChangeTreeNodeItemProviderSpec.class, MergeViewerItemTest.class,
+		MergeViewerItemPseudoConflictTest.class, MergeViewerItemFeatureMapsTest.class,
+		TestBasicDifferenceGroupImpl.class, BugsTestSuite.class, TestFeatureMapDifferencesFilter.class,
+		RCPMatchEngineFactoryRegistryTest.class, ThreeWayComparisonGroupProviderTest.class, })
 public class AllTests {
 	/**
 	 * Launches the test with the given arguments.
@@ -60,7 +60,7 @@ public class AllTests {
 	public static Test suite() {
 		return new JUnit4TestAdapter(AllTests.class);
 	}
-	
+
 	@BeforeClass
 	public static void fillEMFRegistries() {
 		EPackage.Registry.INSTANCE.put(ComparePackage.eNS_URI, ComparePackage.eINSTANCE);
diff --git a/plugins/org.eclipse.emf.compare.rcp.ui/src/org/eclipse/emf/compare/rcp/ui/internal/structuremergeviewer/groups/impl/ThreeWayComparisonGroupProvider.java b/plugins/org.eclipse.emf.compare.rcp.ui/src/org/eclipse/emf/compare/rcp/ui/internal/structuremergeviewer/groups/impl/ThreeWayComparisonGroupProvider.java
index 3ef345ec3..3a7fffbae 100644
--- a/plugins/org.eclipse.emf.compare.rcp.ui/src/org/eclipse/emf/compare/rcp/ui/internal/structuremergeviewer/groups/impl/ThreeWayComparisonGroupProvider.java
+++ b/plugins/org.eclipse.emf.compare.rcp.ui/src/org/eclipse/emf/compare/rcp/ui/internal/structuremergeviewer/groups/impl/ThreeWayComparisonGroupProvider.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2013, 2015 Obeo.
+ * Copyright (c) 2013, 2016 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,8 @@
  * 
  * Contributors:
  *     Obeo - initial API and implementation
+ *     Stefan Dirix - bug 488941
+ *     Simon Delisle, Edgar Mueller - bug 486923
  *******************************************************************************/
 package org.eclipse.emf.compare.rcp.ui.internal.structuremergeviewer.groups.impl;
 
@@ -30,6 +32,7 @@ import com.google.common.collect.UnmodifiableIterator;
 
 import java.util.Collection;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 
 import org.eclipse.emf.common.notify.Adapter;
 import org.eclipse.emf.compare.Comparison;
@@ -147,7 +150,7 @@ public class ThreeWayComparisonGroupProvider extends AbstractDifferenceGroupProv
 			TreeNode ret = wrap(conflict);
 
 			for (Match match : getComparison().getMatches()) {
-				buildSubTree(ret, conflict, match);
+				buildSubTree(ret, conflict, match, Sets.<Match> newLinkedHashSet());
 			}
 
 			return ret;
@@ -163,9 +166,13 @@ public class ThreeWayComparisonGroupProvider extends AbstractDifferenceGroupProv
 		 *            the conflict of the tree.
 		 * @param match
 		 *            the given match.
+		 * @param alreadyProcessedContainedMatches
+		 *            already processed matches that are contained in the given <code>match</code>.
 		 */
-		protected void buildSubTree(TreeNode parentNode, Conflict conflict, Match match) {
-			buildSubTree(parentNode, conflict, match, Sets.<Match> newHashSet());
+		protected void buildSubTree(TreeNode parentNode, Conflict conflict, Match match,
+				Collection<Match> alreadyProcessedContainedMatches) {
+			buildSubTree(parentNode, conflict, match, alreadyProcessedContainedMatches, Sets
+					.<Match> newHashSet());
 		}
 
 		/**
@@ -177,31 +184,39 @@ public class ThreeWayComparisonGroupProvider extends AbstractDifferenceGroupProv
 		 *            the conflict of the tree.
 		 * @param match
 		 *            the given match.
+		 * @param alreadyProcessedContainedMatches
+		 *            already processed matches that are contained in the given <code>match</code>.
 		 * @param alreadyProcessedMatches
 		 *            already processed matches.
 		 */
 		private void buildSubTree(TreeNode parentNode, Conflict conflict, Match match,
-				Collection<Match> alreadyProcessedMatches) {
+				Collection<Match> alreadyProcessedContainedMatches, Collection<Match> alreadyProcessedMatches) {
 			// Use a LinkedHashSet for the first argument of Sets.intersection, in order to keep the order of
 			// differences.
 			SetView<Diff> setView = Sets.intersection(Sets.newLinkedHashSet(match.getDifferences()), Sets
 					.newHashSet(conflict.getDifferences()));
 			for (Diff diff : setView) {
 				if (!isParentPseudoConflictFromOtherSide(diff, parentNode.getData())) {
-					TreeNode wrap = wrap(diff);
-					parentNode.getChildren().add(wrap);
+					TreeNode diffNode = wrap(diff);
+					parentNode.getChildren().add(diffNode);
 					if (isContainment(diff)) {
 						final Match diffMatch = ComparisonUtil.getComparison(diff).getMatch(
 								((ReferenceChange)diff).getValue());
-						if (diffMatch != null) {
-							buildSubTree(wrap, conflict, diffMatch);
+						if (diffMatch != null && !alreadyProcessedContainedMatches.contains(diffMatch)) {
+							// we don't want callers deeper in the tree to modify the sets of already
+							// processed contained matches
+							LinkedHashSet<Match> updatedProcessedContainedMatches = Sets
+									.newLinkedHashSet(alreadyProcessedContainedMatches);
+							updatedProcessedContainedMatches.add(diffMatch);
+							buildSubTree(diffNode, conflict, diffMatch, updatedProcessedContainedMatches);
 						}
 					} else {
 						alreadyProcessedMatches.add(match);
 						for (Diff refinedBy : diff.getRefinedBy()) {
 							Match refinedByMatch = refinedBy.getMatch();
 							if (alreadyProcessedMatches.add(refinedByMatch)) {
-								buildSubTree(wrap, conflict, refinedByMatch, alreadyProcessedMatches);
+								buildSubTree(diffNode, conflict, refinedByMatch,
+										alreadyProcessedContainedMatches, alreadyProcessedMatches);
 							}
 						}
 					}
@@ -209,7 +224,9 @@ public class ThreeWayComparisonGroupProvider extends AbstractDifferenceGroupProv
 			}
 			for (Match subMatch : match.getSubmatches()) {
 				if (!isMatchOfConflictContainmentDiff(conflict, subMatch)) {
-					buildSubTree(parentNode, conflict, subMatch, alreadyProcessedMatches);
+					buildSubTree(parentNode, conflict, subMatch, alreadyProcessedContainedMatches,
+							alreadyProcessedMatches);
+					alreadyProcessedMatches.add(subMatch);
 				}
 			}
 		}