Bug 530649 - Reduce instantiations to avoid OOMI20180219-2000I20180218-2000I20180217-1500I20180216-2000I20180216-0415I20180215-2000

Change-Id: I95aa8f2c157bfd148a30aee5029fd63ca9f03023
Signed-off-by: Mickael Istria <mistria@redhat.com>

3 files changed, 120 insertions, 3 deletions

diff --git a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
index 3fabcffa6..9f33a666f 100644
--- a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
+++ b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/ComputeProjectOrder.java
@@ -16,7 +16,6 @@ package org.eclipse.core.internal.resources;
 import java.lang.reflect.Array;
 import java.util.*;
 import java.util.function.Predicate;
-import java.util.stream.Collectors;
 import org.eclipse.core.internal.resources.ComputeProjectOrder.Digraph.Edge;
 import org.eclipse.core.internal.resources.ComputeProjectOrder.Digraph.Vertex;
 import org.eclipse.core.runtime.Assert;
@@ -121,6 +120,20 @@ public class ComputeProjectOrder {
 				this.from = from;
 				this.to = to;
 			}
+
+			@Override
+			public boolean equals(Object obj) {
+				if (!(obj instanceof Edge)) {
+					return false;
+				}
+				Edge<?> other = (Edge<?>) obj;
+				return Objects.equals(this.from, other.from) && Objects.equals(this.to, other.to);
+			}
+
+			@Override
+			public int hashCode() {
+				return Objects.hash(this.from, this.to);
+			}
 		}
 
 		/**
@@ -674,8 +687,15 @@ public class ComputeProjectOrder {
 		}
 		Set<Edge<T>> edges = new LinkedHashSet<>(initialGraph.getEdges());
 		for (Vertex<T> vertexToRemove : toRemove) {
-			Set<Edge<T>> incoming = edges.stream().filter(edge -> edge.to == vertexToRemove.id).collect(Collectors.toCollection(LinkedHashSet::new));
-			Set<Edge<T>> outgoing = edges.stream().filter(edge -> edge.from == vertexToRemove.id).collect(Collectors.toCollection(LinkedHashSet::new));
+			Set<Edge<T>> incoming = new LinkedHashSet<>();
+			Set<Edge<T>> outgoing = new LinkedHashSet<>();
+			for (Edge<T> edge : edges) {
+				if (edge.from == vertexToRemove.id) {
+					outgoing.add(edge);
+				} else if (edge.to == vertexToRemove.id) {
+					incoming.add(edge);
+				}
+			}
 			edges.removeAll(incoming);
 			edges.removeAll(outgoing);
 			incoming.forEach(incomingEdge -> outgoing.forEach(outgoingEdge -> edges.add(new Edge<>(incomingEdge.from, outgoingEdge.to))));
diff --git a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/AllTests.java b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/AllTests.java
index 959ec6910..36985d321 100644
--- a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/AllTests.java
+++ b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/AllTests.java
@@ -36,6 +36,7 @@ public class AllTests extends TestCase {
 		suite.addTest(BuildConfigurationsTest.suite());
 		suite.addTest(BuildContextTest.suite());
 		suite.addTest(ParallelBuildChainTest.suite());
+		suite.addTest(ComputeProjectOrderTest.suite());
 		return suite;
 	}
 }
diff --git a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java
new file mode 100644
index 000000000..f8646fb09
--- /dev/null
+++ b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/builders/ComputeProjectOrderTest.java
@@ -0,0 +1,96 @@
+/*******************************************************************************
+ * Copyright (c) 2018 Red Hat Inc. 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:
+ *     Mickael Istria (Red Hat Inc.) - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.core.tests.internal.builders;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.*;
+import java.util.function.Predicate;
+import junit.framework.JUnit4TestAdapter;
+import org.eclipse.core.internal.resources.ComputeProjectOrder;
+import org.eclipse.core.internal.resources.ComputeProjectOrder.Digraph;
+import org.eclipse.core.internal.resources.ComputeProjectOrder.Digraph.Edge;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/**
+ *
+ */
+@RunWith(JUnit4.class)
+public class ComputeProjectOrderTest {
+	public static junit.framework.Test suite() {
+		return new JUnit4TestAdapter(ComputeProjectOrderTest.class);
+	}
+
+	@Test
+	public void testComputeVertexOrderDuration() {
+		final Digraph<Object> digraph = new Digraph<>(Object.class);
+		for (int i = 0; i < 320; i++) {
+			Collection<Object> existingVertexes = new HashSet<>(digraph.vertexMap.keySet());
+			Object newVertex = new Object();
+			digraph.addVertex(newVertex);
+			existingVertexes.forEach(existingVertex -> digraph.addEdge(existingVertex, newVertex));
+		}
+		long timestamp = System.currentTimeMillis();
+		digraph.freeze();
+		ComputeProjectOrder.computeVertexOrder(digraph, Object.class);
+		long duration = System.currentTimeMillis() - timestamp;
+		assertTrue(duration < 1000);
+	}
+
+	@Test
+	public void testFilterDigraphDuration() {
+		final Digraph<Object> digraph = new Digraph<>(Object.class);
+		Object initialVertex = new Object();
+		digraph.addVertex(initialVertex);
+		for (int i = 0; i < 320; i++) {
+			Collection<Object> existingVertexes = new HashSet<>(digraph.vertexMap.keySet());
+			Object newVertex = new Object();
+			digraph.addVertex(newVertex);
+			existingVertexes.forEach(existingVertex -> digraph.addEdge(existingVertex, newVertex));
+		}
+		// keep everything
+		long timestamp = System.currentTimeMillis();
+		Digraph<Object> filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, o -> false, Object.class);
+		assertEquals(digraph.vertexMap.keySet(), filtered.vertexMap.keySet());
+		long duration = System.currentTimeMillis() - timestamp;
+		assertTrue(duration < 1000);
+		// keep only 1 element
+		timestamp = System.currentTimeMillis();
+		filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, o -> o != initialVertex, Object.class);
+		assertEquals(Collections.singleton(initialVertex), filtered.vertexMap.keySet());
+		duration = System.currentTimeMillis() - timestamp;
+		assertTrue(duration < 1000);
+	}
+
+	@Test
+	public void testFilterDigraphBasic() {
+		final Digraph<Object> digraph = new Digraph<>(Object.class);
+		Object a = new Object();
+		Object b = new Object();
+		Object c = new Object();
+		digraph.addVertex(a);
+		digraph.addVertex(b);
+		digraph.addEdge(a, b);
+		digraph.addVertex(c);
+		digraph.addEdge(b, c);
+		//
+		Digraph<Object> filtered = ComputeProjectOrder.buildFilteredDigraph(digraph, Predicate.isEqual(b), Object.class);
+		Set<Object> filteredVertexes = new HashSet<>(2, (float) 1.);
+		filteredVertexes.add(a);
+		filteredVertexes.add(c);
+		assertEquals(filteredVertexes, filtered.vertexMap.keySet());
+		Collection<Edge<Object>> filteredEdges = filtered.getEdges();
+		assertEquals(Collections.singleton(new Edge<>(a, c)), filteredEdges);
+	}
+}