[478620] Cherry pick operation hangs

Updated the graph tree iterator, so that, in case the graph has cycles,
the same node isn't returned twice. Changed name of Graph#treeIterator(E
root) method to depthFirstIterator, in order to better reflect its new
behavior. 

Bug: 478620
Change-Id: Ic5096d5060fccb9c6f4ed449225a9d9230c4b57b
Signed-off-by: Alexandra Buzila <abuzila@eclipsesource.com>

3 files changed, 156 insertions, 88 deletions

diff --git a/plugins/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/logical/EMFResourceMappingMerger.java b/plugins/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/logical/EMFResourceMappingMerger.java
index 12b5d94e5..a5617418d 100644
--- a/plugins/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/logical/EMFResourceMappingMerger.java
+++ b/plugins/org.eclipse.emf.compare.ide.ui/src/org/eclipse/emf/compare/ide/ui/internal/logical/EMFResourceMappingMerger.java
@@ -8,7 +8,7 @@
  * Contributors:
  *     Obeo - initial API and implementation
  *     Philip Langer - bugs 461713, 465331, 470268, 476363, 476417, refactorings
- *     Alexandra Buzila - bug 470332
+ *     Alexandra Buzila - bugs 470332, 478620
  *******************************************************************************/
 package org.eclipse.emf.compare.ide.ui.internal.logical;
 
@@ -322,7 +322,7 @@ public class EMFResourceMappingMerger implements IResourceMappingMerger {
 			final Diff next = iterator.next();
 			if (hasConflict(ConflictKind.REAL).apply(next)) {
 				iterator.prune();
-				conflictingURIs.addAll(collectConflictingResources(differencesGraph.treeIterator(next)));
+				conflictingURIs.addAll(collectConflictingResources(differencesGraph.depthFirstIterator(next)));
 			} else if (next.getState() != DifferenceState.MERGED) {
 				final IMerger merger = MERGER_REGISTRY.getHighestRankingMerger(next);
 				merger.copyRightToLeft(next, emfMonitor);
diff --git a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
index 4cd8dab63..a9e77cd43 100644
--- a/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
+++ b/plugins/org.eclipse.emf.compare.tests/src/org/eclipse/emf/compare/tests/utils/GraphTest.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2015 Obeo.
+ * Copyright (c) 2015 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
+ *     Alexandra Buzila - bug 478620
  *******************************************************************************/
 package org.eclipse.emf.compare.tests.utils;
 
@@ -140,27 +141,9 @@ public class GraphTest {
 
 	@Test
 	public void testTreeIteration_1() {
-		Graph<String> graph = new Graph<String>();
-		//@formatter:off
-		/*
-		 * With the following Graph:
-		 *
-		 *     A       I    J
-		 *    / \     /    / \
-		 *   B   C   G    K   L
-		 *  /   / \ / \      / \
-		 * D   E   F   H    M   N
-		 */
-		//@formatter:on
-		graph.addChildren("A", ImmutableSet.of("B", "C"));
-		graph.addChildren("B", ImmutableSet.of("D"));
-		graph.addChildren("C", ImmutableSet.of("E", "F"));
-		graph.addChildren("I", ImmutableSet.of("G"));
-		graph.addChildren("G", ImmutableSet.of("F", "H"));
-		graph.addChildren("J", ImmutableSet.of("K", "L"));
-		graph.addChildren("L", ImmutableSet.of("M", "N"));
+		Graph<String> graph = getAcyclicGraph();
 
-		Iterator<String> iteratorOnA = graph.treeIterator("A");
+		Iterator<String> iteratorOnA = graph.depthFirstIterator("A");
 		assertEquals("A", iteratorOnA.next());
 		assertEquals("B", iteratorOnA.next());
 		assertEquals("D", iteratorOnA.next());
@@ -172,27 +155,9 @@ public class GraphTest {
 
 	@Test
 	public void testTreeIteration_2() {
-		Graph<String> graph = new Graph<String>();
-		//@formatter:off
-		/*
-		 * With the following Graph:
-		 *
-		 *     A       I    J
-		 *    / \     /    / \
-		 *   B   C   G    K   L
-		 *  /   / \ / \      / \
-		 * D   E   F   H    M   N
-		 */
-		//@formatter:on
-		graph.addChildren("A", ImmutableSet.of("B", "C"));
-		graph.addChildren("B", ImmutableSet.of("D"));
-		graph.addChildren("C", ImmutableSet.of("E", "F"));
-		graph.addChildren("I", ImmutableSet.of("G"));
-		graph.addChildren("G", ImmutableSet.of("F", "H"));
-		graph.addChildren("J", ImmutableSet.of("K", "L"));
-		graph.addChildren("L", ImmutableSet.of("M", "N"));
+		Graph<String> graph = getAcyclicGraph();
 
-		Iterator<String> iteratorOnC = graph.treeIterator("C");
+		Iterator<String> iteratorOnC = graph.depthFirstIterator("C");
 		assertEquals("C", iteratorOnC.next());
 		assertEquals("E", iteratorOnC.next());
 		assertEquals("F", iteratorOnC.next());
@@ -201,27 +166,9 @@ public class GraphTest {
 
 	@Test
 	public void testTreeIteration_3() {
-		Graph<String> graph = new Graph<String>();
-		//@formatter:off
-		/*
-		 * With the following Graph:
-		 *
-		 *     A       I    J
-		 *    / \     /    / \
-		 *   B   C   G    K   L
-		 *  /   / \ / \      / \
-		 * D   E   F   H    M   N
-		 */
-		//@formatter:on
-		graph.addChildren("A", ImmutableSet.of("B", "C"));
-		graph.addChildren("B", ImmutableSet.of("D"));
-		graph.addChildren("C", ImmutableSet.of("E", "F"));
-		graph.addChildren("I", ImmutableSet.of("G"));
-		graph.addChildren("G", ImmutableSet.of("F", "H"));
-		graph.addChildren("J", ImmutableSet.of("K", "L"));
-		graph.addChildren("L", ImmutableSet.of("M", "N"));
+		Graph<String> graph = getAcyclicGraph();
 
-		Iterator<String> iteratorOnI = graph.treeIterator("I");
+		Iterator<String> iteratorOnI = graph.depthFirstIterator("I");
 		assertEquals("I", iteratorOnI.next());
 		assertEquals("G", iteratorOnI.next());
 		assertEquals("F", iteratorOnI.next());
@@ -231,18 +178,90 @@ public class GraphTest {
 
 	@Test
 	public void testTreeIteration_4() {
+		Graph<String> graph = getAcyclicGraph();
+
+		Iterator<String> iteratorOnJ = graph.depthFirstIterator("J");
+		assertEquals("J", iteratorOnJ.next());
+		assertEquals("K", iteratorOnJ.next());
+		assertEquals("L", iteratorOnJ.next());
+		assertEquals("M", iteratorOnJ.next());
+		assertEquals("N", iteratorOnJ.next());
+		assertFalse(iteratorOnJ.hasNext());
+	}
+
+	@Test
+	public void testDepthIterationWithCycles_1() {
+		Graph<String> graph = getGraphWithCycles();
+
+		Iterator<String> iteratorOnA = graph.depthFirstIterator("A");
+		assertEquals("A", iteratorOnA.next());
+		assertEquals("B", iteratorOnA.next());
+		assertEquals("D", iteratorOnA.next());
+		assertEquals("E", iteratorOnA.next());
+		assertEquals("C", iteratorOnA.next());
+		assertEquals("F", iteratorOnA.next());
+		assertEquals("H", iteratorOnA.next());
+
+		assertFalse(iteratorOnA.hasNext());
+	}
+
+	@Test
+	public void testDepthIterationWithCycles_2() {
+		Graph<String> graph = getGraphWithCycles();
+
+		Iterator<String> iteratorOnC = graph.depthFirstIterator("C");
+		assertEquals("C", iteratorOnC.next());
+		assertEquals("A", iteratorOnC.next());
+		assertEquals("B", iteratorOnC.next());
+		assertEquals("D", iteratorOnC.next());
+		assertEquals("E", iteratorOnC.next());
+		assertEquals("F", iteratorOnC.next());
+		assertEquals("H", iteratorOnC.next());
+
+		assertFalse(iteratorOnC.hasNext());
+	}
+
+	@Test
+	public void testDepthIterationWithCycles_3() {
+		Graph<String> graph = getGraphWithCycles();
+
+		Iterator<String> iteratorOnI = graph.depthFirstIterator("I");
+		assertEquals("I", iteratorOnI.next());
+		assertEquals("G", iteratorOnI.next());
+		assertEquals("F", iteratorOnI.next());
+		assertEquals("H", iteratorOnI.next());
+
+		assertFalse(iteratorOnI.hasNext());
+	}
+
+	@Test
+	public void testDepthIterationWithCycles_4() {
+		Graph<String> graph = getGraphWithCycles();
+
+		Iterator<String> iteratorOnJ = graph.depthFirstIterator("J");
+		assertEquals("J", iteratorOnJ.next());
+		assertEquals("K", iteratorOnJ.next());
+		assertEquals("M", iteratorOnJ.next());
+		assertEquals("L", iteratorOnJ.next());
+		assertEquals("N", iteratorOnJ.next());
+
+		assertFalse(iteratorOnJ.hasNext());
+	}
+
+	/**
+	 * @return The following acyclic graph:
+	 * 
+	 *         <pre>
+	 *     A       I    J
+	 *    / \     /    / \
+	 *   B   C   G    K   L
+	 *  /   / \ / \      / \
+	 * D   E   F   H    M   N
+	 * </pre>
+	 */
+	private Graph<String> getAcyclicGraph() {
 		Graph<String> graph = new Graph<String>();
-		//@formatter:off
-		/*
-		 * With the following Graph:
-		 *
-		 *     A       I    J
-		 *    / \     /    / \
-		 *   B   C   G    K   L
-		 *  /   / \ / \      / \
-		 * D   E   F   H    M   N
-		 */
-		//@formatter:on
+
 		graph.addChildren("A", ImmutableSet.of("B", "C"));
 		graph.addChildren("B", ImmutableSet.of("D"));
 		graph.addChildren("C", ImmutableSet.of("E", "F"));
@@ -251,12 +270,37 @@ public class GraphTest {
 		graph.addChildren("J", ImmutableSet.of("K", "L"));
 		graph.addChildren("L", ImmutableSet.of("M", "N"));
 
-		Iterator<String> iteratorOnJ = graph.treeIterator("J");
-		assertEquals("J", iteratorOnJ.next());
-		assertEquals("K", iteratorOnJ.next());
-		assertEquals("L", iteratorOnJ.next());
-		assertEquals("M", iteratorOnJ.next());
-		assertEquals("N", iteratorOnJ.next());
-		assertFalse(iteratorOnJ.hasNext());
+		return graph;
 	}
+
+	/**
+	 * @return The following cyclic graph:
+	 * 
+	 *         <pre>
+	 *     A       I    J
+	 *    / \\    /    /  \
+	 *   B   C   G    K    L
+	 *  /   / \ / \    \ // \
+	 * D - E   F = H    M    N
+	 * </pre>
+	 */
+	private Graph<String> getGraphWithCycles() {
+		Graph<String> graph = new Graph<String>();
+
+		graph.addChildren("A", ImmutableSet.of("B", "C"));
+		graph.addChildren("B", ImmutableSet.of("D"));
+		graph.addChildren("D", ImmutableSet.of("E"));
+		graph.addChildren("C", ImmutableSet.of("A", "E", "F"));
+		graph.addChildren("I", ImmutableSet.of("G"));
+		graph.addChildren("G", ImmutableSet.of("F", "H"));
+		graph.addChildren("J", ImmutableSet.of("K", "L"));
+		graph.addChildren("K", ImmutableSet.of("M"));
+		graph.addChildren("M", ImmutableSet.of("L"));
+		graph.addChildren("L", ImmutableSet.of("M", "N"));
+		graph.addChildren("F", ImmutableSet.of("H"));
+		graph.addChildren("H", ImmutableSet.of("F"));
+
+		return graph;
+	}
+
 }
diff --git a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
index 9e888813d..d77484c7e 100644
--- a/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
+++ b/plugins/org.eclipse.emf.compare/src/org/eclipse/emf/compare/internal/utils/Graph.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2013, 2015 Obeo.
+ * Copyright (c) 2013, 2015 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
+ *     Alexandra Buzila - bug 478620
  *******************************************************************************/
 package org.eclipse.emf.compare.internal.utils;
 
@@ -22,6 +23,7 @@ import com.google.common.collect.Iterators;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.ConcurrentModificationException;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
@@ -394,7 +396,8 @@ public class Graph<E> {
 	}
 
 	/**
-	 * Returns a tree iterator created with the given element as root.
+	 * Returns a depth first iterator created with the given element as root. If the graph contains cycles,
+	 * the same node won't be returned twice.
 	 * <p>
 	 * The root will be returned first, then the left-most child of that root, then the left-most child of
 	 * that child if any, or the closest sibling to the right of the current element. For example, with the
@@ -419,7 +422,7 @@ public class Graph<E> {
 	 *            The root of the tree over which we need to iterate.
 	 * @return An iterator over the tree starting from the given root.
 	 */
-	public Iterator<E> treeIterator(E root) {
+	public Iterator<E> depthFirstIterator(E root) {
 		return new ChildrenIterator(root);
 	}
 
@@ -850,7 +853,7 @@ public class Graph<E> {
 	 * 
 	 * @author <a href="mailto:laurent.goubet@obeo.fr">Laurent Goubet</a>
 	 */
-	private class ChildrenIterator implements Iterator<E> {
+	private class ChildrenIterator implements Iterator<E>, Predicate<Node<E>> {
 		/**
 		 * The expected {@link Graph#modcount} for this iterator. Any attempt at calling {@link #next()} after
 		 * the underlying graph has been modified will fail in {@link ConcurrentModificationException}.
@@ -858,7 +861,14 @@ public class Graph<E> {
 		private final int expectedModCount;
 
 		/** The current stack of iterators. */
-		private LinkedList<Iterator<Node<E>>> iteratorStack;
+		private final LinkedList<Iterator<Node<E>>> iteratorStack;
+
+		/**
+		 * The set of all nodes from the underlying graph we've already iterated over. This will prevent us
+		 * from cycling over nodes if there are cycles in our graph, and will also prevent us from iterating
+		 * twice over the same node (when a node has multiple parents).
+		 */
+		private final Set<Node<E>> consumedNodes;
 
 		/**
 		 * Creates an iterator over the tree starting from the given root element.
@@ -870,6 +880,7 @@ public class Graph<E> {
 			this.expectedModCount = Graph.this.modcount;
 			this.iteratorStack = new LinkedList<Iterator<Node<E>>>();
 			iteratorStack.add(Iterators.singletonIterator(Graph.this.nodes.get(root)));
+			consumedNodes = new HashSet<Node<E>>();
 		}
 
 		/** {@inheritDoc} */
@@ -886,8 +897,10 @@ public class Graph<E> {
 				throw new NoSuchElementException();
 			}
 			Node<E> resultNode = iteratorStack.getLast().next();
-			// no check for emptiness, would be redundant with the following loop
-			iteratorStack.add(resultNode.getChildren().iterator());
+			if (consumedNodes.add(resultNode)) {
+				// no check for emptiness, would be redundant with the following loop
+				iteratorStack.add(Iterators.filter(resultNode.getChildren().iterator(), this));
+			}
 
 			// remove the iterators we've consumed entirely from the stack.
 			ListIterator<Iterator<Node<E>>> reverseStackIterator = iteratorStack.listIterator(iteratorStack
@@ -907,6 +920,17 @@ public class Graph<E> {
 		public void remove() {
 			throw new UnsupportedOperationException();
 		}
+
+		/**
+		 * Predicate implementation, only nodes that are not consumed will be accepted.
+		 * 
+		 * @param input
+		 *            The node to filter
+		 * @return true If and only if the given node is not in comsumedNodes.
+		 */
+		public boolean apply(Node<E> input) {
+			return !consumedNodes.contains(input);
+		}
 	}
 
 	/**