Skip to main content
aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorStefan Xenos2017-02-08 15:43:08 +0000
committerStefan Xenos2017-02-08 18:06:52 +0000
commit0fc4de15a335d3d8006d7db585d17d3576096101 (patch)
treedef2d8c401326e3632a5c2a1bc32215c9e23ff79
parent3691b5b11f799faea2f0ffcbe121c5e6eb0aed06 (diff)
downloadeclipse.jdt.core-0fc4de15a335d3d8006d7db585d17d3576096101.tar.gz
eclipse.jdt.core-0fc4de15a335d3d8006d7db585d17d3576096101.tar.xz
eclipse.jdt.core-0fc4de15a335d3d8006d7db585d17d3576096101.zip
Bug 511845 - FactoryPath.internalAdd takes O(n) timeI20170208-2000
Resubmitting the original fix for bug 511845, but with an additional fix and regression test for the regression it introduced. Change-Id: I98a6660f81bcad95aec1cd1a4ca9159d5d89da41 Signed-off-by: Stefan Xenos <sxenos@gmail.com>
-rw-r--r--org.eclipse.jdt.apt.core/src/org/eclipse/jdt/apt/core/internal/util/FactoryPath.java38
-rw-r--r--org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/FactoryPathTests.java124
-rw-r--r--org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/TestAll.java1
3 files changed, 146 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..b7870d188d 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(map.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,20 @@ public class FactoryPath implements IFactoryPath {
return map;
}
+ private static <T> List<T> getReversed(Collection<T> collection) {
+ ArrayList<T> result = new ArrayList<>(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..b92a4feca1
--- /dev/null
+++ b/org.eclipse.jdt.apt.tests/src/org/eclipse/jdt/apt/tests/FactoryPathTests.java
@@ -0,0 +1,124 @@
+/*******************************************************************************
+ * Copyright (c) 2017 Google, 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:
+ * Stefan Xenos (Google) - Initial implementation
+ *******************************************************************************/
+package org.eclipse.jdt.apt.tests;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+
+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 org.eclipse.jdt.apt.core.internal.util.FactoryPath.Attributes;
+
+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);
+ }
+
+ private static void assertExtJars(List<String> expected, Map<FactoryContainer, Attributes> actual) {
+ List<FactoryContainer> toIterate = new ArrayList<>();
+ toIterate.addAll(actual.keySet());
+ Collections.reverse(toIterate);
+ assertEquals("The size of the path list should match up", expected.size(), toIterate.size());
+ int index = 0;
+ for (FactoryContainer container : toIterate) {
+ FactoryContainer fc = FactoryPathUtil.newExtJarFactoryContainer(new File(expected.get(index++)));
+ assertEquals("Unexpected jar file", fc, container);
+ }
+ }
+
+ @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 {
+ assertExtJars(Arrays.asList(filesInPath), path.getAllContainers());
+ }
+
+ public void testGetEnabledContainersOrder() throws Exception {
+ assertExtJars(Arrays.asList(filesInPath), path.getEnabledContainers());
+ }
+
+ 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));
+ final String[] expectedResult = { "all/your.jar", "base.jar", "are.jar", "you/have/no/chance.jar", "to.jar",
+ "survive.jar" };
+ assertExtJars(Arrays.asList(expectedResult), path.getAllContainers());
+ }
+
+ 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());
+
+ assertExtJars(Arrays.asList(filesInPath), newPath.getAllContainers());
+ }
+}
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());

Back to the top