[458971] Fix infinite loop in Graph.BreadthFirstIterator#prune()

Bug: 458971
Change-Id: I1134d05a996d1f1a80cac27829250e6e9b732d02
Signed-off-by: Axel Richard <axel.richard@obeo.fr>

2 files changed, 30 insertions, 2 deletions

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 01cf4ddd8..b8ab011ee 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
@@ -19,6 +19,7 @@ import com.google.common.collect.Lists;
 import java.util.Set;
 
 import org.eclipse.emf.compare.internal.utils.Graph;
+import org.eclipse.emf.compare.internal.utils.PruningIterator;
 import org.junit.Test;
 
 /**
@@ -53,4 +54,30 @@ public class GraphTest {
 		assertEquals(4, subgraph.size());
 		assertTrue(subgraph.containsAll(Lists.newArrayList("a", "b", "d", "f")));
 	}
+
+	/*
+	 * Just to avoid infinite loop in prune.
+	 */
+	@Test
+	public void testPrune() {
+		Graph<String> graph = new Graph<String>();
+		//@formatter:off
+		/*
+		 * Add the following graph:
+		 *          c-\
+		 *          |  |
+		 *          b-/
+		 *          |
+		 *          a
+		 */
+		//@formatter:on
+		graph.addChildren("a", ImmutableSet.of("b"));
+		graph.addChildren("b", ImmutableSet.of("c"));
+		graph.addChildren("c", ImmutableSet.of("b"));
+		PruningIterator<String> iterator = graph.breadthFirstIterator();
+		while (iterator.hasNext()) {
+			iterator.next();
+			iterator.prune();
+		}
+	}
 }
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 e3083c7ea..03b8c349e 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
@@ -898,11 +898,12 @@ public final class Graph<E> {
 			Set<Node<E>> children = lastReturned.getChildren();
 			lastReturned = null;
 			while (!children.isEmpty()) {
-				consumedNodes.addAll(children);
 				final Set<Node<E>> copy = children;
 				children = new LinkedHashSet<Node<E>>();
 				for (Node<E> child : copy) {
-					children.addAll(child.getChildren());
+					if (consumedNodes.add(child)) {
+						children.addAll(child.getChildren());
+					}
 				}
 			}
 		}