Bug 511845 - FactoryPath.internalAdd takes O(n) timeI20170208-0700I20170207-2000

Change-Id: I8e1b34234195f8b2ad1dc26d6244a75fdfc68b18
Signed-off-by: Stefan Xenos <sxenos@gmail.com>

3 files changed, 140 insertions, 17 deletions

diff --git a/org.eclipse.jdt.apt.core/src/org/eclipse/jdt/apt/core/internal/util/FactoryPath.java b/org.eclipse.jdt.apt.core/src/org/eclipse/jdt/apt/core/internal/util/FactoryPath.java
index fafa72053c..617a976582 100644
--- a/org.eclipse.jdt.apt.core/src/org/eclipse/jdt/apt/core/internal/util/FactoryPath.java
+++ b/org.eclipse.jdt.apt.core/src/org/eclipse/jdt/apt/core/internal/util/FactoryPath.java
@@ -13,9 +13,13 @@
 package org.eclipse.jdt.apt.core.internal.util;
 
 import java.io.File;
+import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.LinkedHashMap;
+import java.util.List;
 import java.util.Map;
+import java.util.Map.Entry;
 
 import org.eclipse.core.runtime.CoreException;
 import org.eclipse.core.runtime.IPath;
@@ -89,7 +93,7 @@ public class FactoryPath implements IFactoryPath {
 	}
 	
 	/**
-	 * The factory path.  
+	 * The factory path. Stored in reverse order.
 	 */
 	private final Map<FactoryContainer, Attributes> _path = Collections.synchronizedMap(
 			new LinkedHashMap<FactoryContainer, Attributes>());
@@ -183,7 +187,7 @@ public class FactoryPath implements IFactoryPath {
 		Attributes a = new Attributes(enabled, runInBatchMode);
 		internalAdd(fc, a);
 	}
-	
+
 	/**
 	 * Set the factory path based on the contents of an ordered map.
 	 * @param map should be an ordered map, such as LinkedHashMap; should contain no
@@ -192,10 +196,12 @@ public class FactoryPath implements IFactoryPath {
 	public void setContainers(Map<FactoryContainer, Attributes> map) {
 		synchronized(_path) {
 			_path.clear();
-			_path.putAll(map);
+			for (Entry<FactoryContainer, Attributes> entry : getReversed(_path.entrySet())) {
+				_path.put(entry.getKey(), entry.getValue());
+			}
 		}
 	}
-	
+
 	/**
 	 * Add a factory container, and attributes, to the head of the list.
 	 * If it already existed in the list, remove the old instance before
@@ -207,22 +213,14 @@ public class FactoryPath implements IFactoryPath {
 	private void internalAdd(FactoryContainer fc, Attributes a) {
 		synchronized(_path) {
 			_path.remove(fc);
-			// LinkedHashMap doesn't have any way to add to the head,
-			// so we're forced to do two copies.  Make the new map
-			// large enough that we don't have to rehash midway through the putAll().
-			Map<FactoryContainer, Attributes> newPath = 
-				new LinkedHashMap<>(1 + 4*(_path.size() + 1)/3);
-			newPath.put(fc, a);
-			newPath.putAll(_path);
-			_path.clear();
-			_path.putAll(newPath);
+			_path.put(fc, a);
 		}
 	}
 
 	public Map<FactoryContainer, Attributes> getEnabledContainers() {
 		Map<FactoryContainer, Attributes> map = new LinkedHashMap<>();
 		synchronized(_path) {
-			for (Map.Entry<FactoryContainer, Attributes> entry : _path.entrySet()) {
+			for (Map.Entry<FactoryContainer, Attributes> entry : getReversed(_path.entrySet())) {
 				Attributes attr = entry.getValue();
 				if (attr.isEnabled()) {
 					Attributes attrClone = new Attributes(attr);
@@ -233,14 +231,21 @@ public class FactoryPath implements IFactoryPath {
 		return map;
 	}
 
+	private static <T> List<T> getReversed(Collection<T> collection) {
+		ArrayList<T> result = new ArrayList<>();
+		result.addAll(collection);
+		Collections.reverse(result);
+		return result;
+	}
+
 	/**
 	 * @return a copy of the path
 	 */
 	public Map<FactoryContainer, Attributes> getAllContainers() {
 		Map<FactoryContainer, Attributes> map = new LinkedHashMap<>(_path.size());
-		synchronized(_path) {
-			for( Map.Entry<FactoryContainer, Attributes> entry : _path.entrySet() ){
-				map.put( entry.getKey(), new Attributes(entry.getValue()) );
+		synchronized (_path) {
+			for (Map.Entry<FactoryContainer, Attributes> entry : getReversed(_path.entrySet())) {
+				map.put(entry.getKey(), new Attributes(entry.getValue()));
 			}
 		}
 		return map;
diff --git a/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/FactoryPathTests.java b/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/FactoryPathTests.java
new file mode 100644
index 0000000000..0a29b34a2a
--- /dev/null
+++ b/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/FactoryPathTests.java
@@ -0,0 +1,117 @@
+package org.eclipse.jdt.apt.tests;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+import org.eclipse.core.runtime.IPath;
+import org.eclipse.core.runtime.Path;
+import org.eclipse.jdt.apt.core.internal.VarJarFactoryContainer;
+import org.eclipse.jdt.apt.core.internal.WkspJarFactoryContainer;
+import org.eclipse.jdt.apt.core.internal.util.FactoryContainer;
+import org.eclipse.jdt.apt.core.internal.util.FactoryPath;
+import org.eclipse.jdt.apt.core.internal.util.FactoryPathUtil;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+public class FactoryPathTests extends TestCase {
+	private FactoryPath path; 
+
+	private final String[] filesInPath = { "all/your.jar", "base.jar", "are.jar", "belong/to/us.jar",
+			"you/have/no/chance.jar", "to.jar", "survive.jar" };
+
+	public FactoryPathTests(String name) {
+		super(name);
+	}
+
+	public static Test suite() {
+		return new TestSuite( FactoryPathTests.class );
+	}
+
+	@Override
+	protected void setUp() throws Exception {
+		path = new FactoryPath();
+		for (String next : filesInPath) {
+			path.addExternalJar(new File(next));
+		}
+		super.setUp();
+	}
+
+	public void testGetAllContainers() throws Exception {
+		int index = 0;
+		List<FactoryContainer> toIterate = new ArrayList<>();
+		toIterate.addAll(path.getAllContainers().keySet());
+		Collections.reverse(toIterate);
+		for (FactoryContainer container : toIterate) {
+			FactoryContainer fc = FactoryPathUtil.newExtJarFactoryContainer(new File(filesInPath[index++]));
+			assertEquals("Unexpected jar file", fc, container);
+		}
+	}
+
+	public void testGetEnabledContainersOrder() throws Exception {
+		int index = 0;
+		List<FactoryContainer> toIterate = new ArrayList<>();
+		toIterate.addAll(path.getEnabledContainers().keySet());
+		Collections.reverse(toIterate);
+		for (FactoryContainer container : toIterate) {
+			FactoryContainer fc = FactoryPathUtil.newExtJarFactoryContainer(new File(filesInPath[index++]));
+			assertEquals("Unexpected jar file", fc, container);
+		}
+	}
+
+	public void testRemoveExternalJar() throws Exception {
+		File toRemove = new File(filesInPath[3]);
+		FactoryContainer fc = FactoryPathUtil.newExtJarFactoryContainer(toRemove);
+
+		assertTrue("Initial classpath should have contained jar", path.getAllContainers().containsKey(fc));
+
+		path.removeExternalJar(toRemove);
+
+		assertFalse("Final classpath should not have contained jar", path.getAllContainers().containsKey(fc));
+	}
+
+	public void testAddRemoveVarJar() throws Exception {
+		IPath toAdd = new Path("/foo/bar/baz.jar");
+
+		path.addVarJar(toAdd);
+
+		// Will throw an exception if the newly added jar isn't first
+		VarJarFactoryContainer fc = (VarJarFactoryContainer)path.getAllContainers().keySet().iterator().next();
+		assertEquals(toAdd.toString(), fc.getId());
+
+		path.removeVarJar(toAdd);
+
+		assertFalse("Factory path should not contain the removed jar", path.getAllContainers().containsKey(fc));
+	}
+
+	public void testAddRemoveWorkspaceJar() throws Exception {
+		IPath toAdd = new Path("/foo/bar/baz.jar");
+
+		path.addWkspJar(toAdd);
+
+		// Will throw an exception if the newly added jar isn't first
+		WkspJarFactoryContainer fc = (WkspJarFactoryContainer)path.getAllContainers().keySet().iterator().next();
+		assertTrue(fc.getJarFile().toString().endsWith(toAdd.toString()));
+
+		path.removeWkspJar(toAdd);
+
+		assertFalse("Factory path should not contain the removed jar", path.getAllContainers().containsKey(fc));
+	}
+
+	public void testSetContainers() throws Exception {
+		FactoryPath newPath = new FactoryPath();
+		newPath.setContainers(path.getAllContainers());
+	
+		List<FactoryContainer> toIterate = new ArrayList<>();
+		toIterate.addAll(newPath.getAllContainers().keySet());
+		Collections.reverse(toIterate);
+		int index = 0;
+		for (FactoryContainer container : toIterate) {
+			FactoryContainer fc = FactoryPathUtil.newExtJarFactoryContainer(new File(filesInPath[index++]));
+			assertEquals("Unexpected jar file", fc, container);
+		}
+	}
+}
diff --git a/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/TestAll.java b/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/TestAll.java
index 0487245648..3587f3ff08 100644
--- a/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/TestAll.java
+++ b/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/TestAll.java
@@ -42,6 +42,7 @@ public class TestAll extends TestCase {
 		suite.addTest(ReadAnnotationTests.suite());
 		suite.addTest(PreferencesTests.suite());
 		suite.addTest(FactoryLoaderTests.suite());
+		suite.addTest(FactoryPathTests.suite());
 		suite.addTest(ListenerTests.suite());
 		suite.addTest(MirrorDeclarationTests.suite());
 		suite.addTest(MirrorUtilTests.suite());