Skip to main content
aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java1
-rw-r--r--org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java19
-rw-r--r--org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java175
-rw-r--r--org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java510
-rw-r--r--org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java11
5 files changed, 612 insertions, 104 deletions
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
index dd134b94dd..41bd69c710 100644
--- a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
@@ -542,6 +542,7 @@ public class BuilderTests extends TestCase {
GetResourcesTests.class,
FriendDependencyTests.class,
ReferenceCollectionTest.class,
+ StateTest.class,
TestAttributeBuilderTests.class,
Bug530366Test.class,
Bug531382Test.class,
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
index 2cfbb371fb..c60d73f6b7 100644
--- a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
@@ -1,5 +1,5 @@
/*******************************************************************************
- * Copyright (c) 2000, 2015 IBM Corporation and others.
+ * Copyright (c) 2019 Sebastian Zarnekow and others.
*
* This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
@@ -9,7 +9,7 @@
* SPDX-License-Identifier: EPL-2.0
*
* Contributors:
- * IBM Corporation - initial API and implementation
+ * Sebastian Zarnekow - initial API and implementation
*******************************************************************************/
package org.eclipse.jdt.core.tests.builder;
@@ -77,8 +77,7 @@ public class ReferenceCollectionTest extends BuilderTests {
}
}
- // Disabled due bug 545491 comment 15
- public void XtestInternQualifiedNamesSorts_01() {
+ public void testInternQualifiedNamesSorts_01() {
char[][][] qualifiedNames = new char[][][] {
CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -97,8 +96,7 @@ public class ReferenceCollectionTest extends BuilderTests {
toStringArray(internQualifiedNames));
}
- // Disabled due bug 545491 comment 15
- public void XtestInternQualifiedNamesSorts_02() {
+ public void testInternQualifiedNamesSorts_02() {
char[][][] qualifiedNames = new char[][][] {
CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -124,8 +122,7 @@ public class ReferenceCollectionTest extends BuilderTests {
toStringArray(internQualifiedNames));
}
- // Disabled due bug 545491 comment 15
- public void XtestInternSimpleNamesSorts_01() {
+ public void testInternSimpleNamesSorts_01() {
char[][] simpleNames = new char[][] {
"Throwable".toCharArray(),
"aaa".toCharArray(),
@@ -142,8 +139,7 @@ public class ReferenceCollectionTest extends BuilderTests {
toStringArray(internSimpleNames));
}
- // Disabled due bug 545491 comment 15
- public void XtestInternSimpleNamesSorts_02() {
+ public void testInternSimpleNamesSorts_02() {
char[][] simpleNames = new char[][] {
"aaa".toCharArray(),
"bbb".toCharArray(),
@@ -291,8 +287,7 @@ public class ReferenceCollectionTest extends BuilderTests {
assertFalse(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
}
- // Disabled due bug 545491 comment 15
- public void XtestAddDependencies() {
+ public void testAddDependencies() {
TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
String[] array = new String[] {"a.b.c.D"};
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java
new file mode 100644
index 0000000000..e33bc200fd
--- /dev/null
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java
@@ -0,0 +1,175 @@
+/*******************************************************************************
+ * Copyright (c) 2019 Sebastian Zarnekow and others.
+ *
+ * This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License 2.0
+ * which accompanies this distribution, and is available at
+ * https://www.eclipse.org/legal/epl-2.0/
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *
+ * Contributors:
+ * Sebastian Zarnekow - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.jdt.core.tests.builder;
+
+import static org.junit.Assert.assertArrayEquals;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Field;
+import java.util.Arrays;
+
+import org.eclipse.core.resources.IProject;
+import org.eclipse.core.runtime.CoreException;
+import org.eclipse.core.runtime.IPath;
+import org.eclipse.jdt.core.JavaModelException;
+import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.core.tests.util.Util;
+import org.eclipse.jdt.internal.compiler.util.SimpleLookupTable;
+import org.eclipse.jdt.internal.core.JavaModelManager;
+import org.eclipse.jdt.internal.core.JavaModelManager.PerProjectInfo;
+import org.eclipse.jdt.internal.core.builder.JavaBuilder;
+import org.eclipse.jdt.internal.core.builder.ReferenceCollection;
+import org.eclipse.jdt.internal.core.builder.State;
+
+import junit.framework.Test;
+
+public class StateTest extends BuilderTests {
+
+ public StateTest(String name) {
+ super(name);
+ }
+
+ public static Test suite() {
+ return buildTestSuite(StateTest.class);
+ }
+
+ public void testWriteAndReadState() throws JavaModelException, Exception {
+ IPath interfaceProjectPath = env.addProject("Interface"); //$NON-NLS-1$
+ env.addExternalJars(interfaceProjectPath, Util.getJavaClassLibs());
+
+ IPath implementationProjectPath = env.addProject("Implementation"); //$NON-NLS-1$
+ env.addExternalJars(implementationProjectPath, Util.getJavaClassLibs());
+ env.addClassFolder(implementationProjectPath, interfaceProjectPath, false);
+
+ env.addClass(interfaceProjectPath, "a", "Interfaze", //$NON-NLS-1$ //$NON-NLS-2$
+ "package a;\n" +
+ "public interface Interfaze {\n" +
+ " void callMe();\n" +
+ "}" //$NON-NLS-1$
+ );
+
+ env.addClass(interfaceProjectPath, "c", "Impl1", //$NON-NLS-1$ //$NON-NLS-2$
+ "package c;\n" +
+ "import a.Interfaze;\n" +
+ "public class Impl1 implements Interfaze {\n" +
+ " @Override\n" +
+ " public void callMe() {\n" +
+ " }\n" +
+ "}"
+ );
+
+ env.addClass(implementationProjectPath, "b", "Impl2", //$NON-NLS-1$ //$NON-NLS-2$
+ "package b;\n" +
+ "import a.Interfaze;\n" +
+ "public class Impl2 implements Interfaze {\n" +
+ " @Override\n" +
+ " public void callMe() {\n" +
+ " }\n" +
+ "}" //$NON-NLS-1$
+ );
+ fullBuild();
+
+ writeReadAndCompareReferences(interfaceProjectPath);
+ writeReadAndCompareReferences(implementationProjectPath);
+ }
+
+ private void writeReadAndCompareReferences(IPath projectPath)
+ throws JavaModelException, IOException, CoreException {
+ JavaModelManager javaModelManager = JavaModelManager.getJavaModelManager();
+ IProject project = env.getProject(projectPath);
+ PerProjectInfo info = javaModelManager.getPerProjectInfoCheckExistence(project);
+ ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
+ State savedState = (State) info.savedState;
+ JavaBuilder.writeState(savedState, new DataOutputStream(outputStream));
+ byte[] bytes = outputStream.toByteArray();
+ State readState = JavaBuilder.readState(project, new DataInputStream(new ByteArrayInputStream(bytes)));
+ SimpleLookupTable readReferences = readState.getReferences();
+ assertEqualLookupTables(savedState.getReferences(), readReferences);
+ }
+
+ private void assertEqualLookupTables(SimpleLookupTable expectation, SimpleLookupTable actual) {
+ assertEquals(expectation.elementSize, actual.elementSize);
+ Object[] expectedKeys = expectation.keyTable;
+ for(int i = 0; i < expectedKeys.length; i++) {
+ Object key = expectedKeys[i];
+ if (key != null) {
+ ReferenceCollection actualReferenceCollection = (ReferenceCollection) actual.get(key);
+ ReferenceCollection expectedReferenceCollection = (ReferenceCollection) expectation.valueTable[i];
+ assertEqualReferenceCollections(expectedReferenceCollection, actualReferenceCollection);
+ }
+ }
+ }
+
+ private void assertEqualReferenceCollections(ReferenceCollection expectedReferenceCollection,
+ ReferenceCollection actualReferenceCollection) {
+ {
+ char[][] expected = getSimpleNameReferences(expectedReferenceCollection);
+ char[][] actual = getSimpleNameReferences(actualReferenceCollection);
+ assertArrayEquals(toStringArray(expected), toStringArray(actual));
+ }
+ {
+ char[][] expected = getRootReferences(expectedReferenceCollection);
+ char[][] actual = getRootReferences(actualReferenceCollection);
+ assertArrayEquals(toStringArray(expected), toStringArray(actual));
+ }
+ {
+ char[][][] expected = getQualifiedNameReferences(expectedReferenceCollection);
+ char[][][] actual = getQualifiedNameReferences(actualReferenceCollection);
+ assertArrayEquals(toStringArray(expected), toStringArray(actual));
+ }
+ }
+
+ private static String[] toStringArray(char[][][] qualifiedNameReferences) {
+ return Arrays.stream(qualifiedNameReferences).map(a -> CharOperation.toString(a)).toArray(String[]::new);
+ }
+
+ private static String[] toStringArray(char[][] qualifiedNameReferences) {
+ return Arrays.stream(qualifiedNameReferences).map(a -> CharOperation.charToString(a)).toArray(String[]::new);
+ }
+
+ char[][][] getQualifiedNameReferences(ReferenceCollection collection) {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("qualifiedNameReferences");
+ fld.setAccessible(true);
+ return (char[][][]) fld.get(collection);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ char[][] getSimpleNameReferences(ReferenceCollection collection) {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("simpleNameReferences");
+ fld.setAccessible(true);
+ return (char[][]) fld.get(collection);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ char[][] getRootReferences(ReferenceCollection collection) {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("rootReferences");
+ fld.setAccessible(true);
+ return (char[][]) fld.get(collection);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+}
diff --git a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
index 8b5e24646e..0b47eda2bc 100644
--- a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
+++ b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
@@ -11,17 +11,25 @@
* Contributors:
* IBM Corporation - initial API and implementation
* Tim Hanson <thanson@bea.com> - fix for https://bugs.eclipse.org/bugs/show_bug.cgi?id=137634
+ * Sebastian Zarnekow - Contribution for
+ * Bug 545491 - Poor performance of ReferenceCollection with many source files
*******************************************************************************/
package org.eclipse.jdt.internal.core.builder;
+import java.util.Arrays;
+import java.util.Comparator;
import java.util.Set;
+import java.util.stream.Collectors;
import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.internal.compiler.lookup.CompilationUnitScope;
import org.eclipse.jdt.internal.compiler.lookup.TypeConstants;
public class ReferenceCollection {
-char[][][] qualifiedNameReferences; // contains no simple names as in just 'a' which is kept in simpleNameReferences instead
+// contains no simple names as in just 'a' which is kept in simpleNameReferences instead
+// TODO after #addDependencies, it will contain simple names, though. See ReferenceCollectionTest
+char[][][] qualifiedNameReferences;
char[][] simpleNameReferences;
char[][] rootReferences;
@@ -31,51 +39,64 @@ protected ReferenceCollection(char[][][] qualifiedNameReferences, char[][] simpl
this.rootReferences = internSimpleNames(rootReferences, false);
}
+/**
+ * Add the given fully qualified names to this reference collection.
+ * Subsequent queries of {@link #includes(char[][][], char[][], char[][])} will report true
+ * if the given names intersect with one of the added type name dependencies.
+ *
+ * @see CompilationUnitScope#recordQualifiedReference
+ */
public void addDependencies(String[] typeNameDependencies) {
// if each qualified type name is already known then all of its subNames can be skipped
// and its expected that very few qualified names in typeNameDependencies need to be added
// but could always take 'p1.p2.p3.X' and make all qualified names 'p1' 'p1.p2' 'p1.p2.p3' 'p1.p2.p3.X', then intern
- char[][][] qNames = new char[typeNameDependencies.length][][];
- for (int i = typeNameDependencies.length; --i >= 0;)
- qNames[i] = CharOperation.splitOn('.', typeNameDependencies[i].toCharArray());
- qNames = internQualifiedNames(qNames, false);
-
- next : for (int i = qNames.length; --i >= 0;) {
- char[][] qualifiedTypeName = qNames[i];
- while (!includes(qualifiedTypeName)) {
- if (!includes(qualifiedTypeName[qualifiedTypeName.length - 1])) {
- int length = this.simpleNameReferences.length;
- System.arraycopy(this.simpleNameReferences, 0, this.simpleNameReferences = new char[length + 1][], 0, length);
- this.simpleNameReferences[length] = qualifiedTypeName[qualifiedTypeName.length - 1];
- }
- if (!insideRoot(qualifiedTypeName[0])) {
- int length = this.rootReferences.length;
- System.arraycopy(this.rootReferences, 0, this.rootReferences = new char[length + 1][], 0, length);
- this.rootReferences[length] = qualifiedTypeName[0];
+ next: for(String typeNameDependency: typeNameDependencies) {
+ char[][] qualifiedTypeName = CharOperation.splitOn('.', typeNameDependency.toCharArray());
+ if (!isWellKnownQualifiedName(qualifiedTypeName)) {
+ int qLength = qualifiedTypeName.length;
+ QualifiedNameSet internedNames = InternedQualifiedNames[qLength <= MaxQualifiedNames ? qLength - 1 : 0];
+ qualifiedTypeName = internSimpleNames(qualifiedTypeName, false, false);
+ qualifiedTypeName = internedNames.add(qualifiedTypeName);
+ int idx;
+ while ((idx = Arrays.binarySearch(this.qualifiedNameReferences, qualifiedTypeName, CHAR_CHAR_ARR_COMPARATOR)) < 0) {
+ this.simpleNameReferences = ensureContainedInSortedOrder(this.simpleNameReferences, qualifiedTypeName[qualifiedTypeName.length - 1]);
+ this.rootReferences = ensureContainedInSortedOrder(this.rootReferences, qualifiedTypeName[0]);
+
+ int length = this.qualifiedNameReferences.length;
+ idx = -(idx+1);
+ char[][][] newArray = new char[length + 1][][];
+ insertIntoArray(this.qualifiedNameReferences, this.qualifiedNameReferences = newArray, qualifiedTypeName, idx);
+
+ qualifiedTypeName = CharOperation.subarray(qualifiedTypeName, 0, qualifiedTypeName.length - 1);
+ char[][][] temp = internQualifiedNames(new char[][][] {qualifiedTypeName}, false);
+ if (temp == EmptyQualifiedNames)
+ continue next; // qualifiedTypeName is a well known name
+ qualifiedTypeName = temp[0];
}
- int length = this.qualifiedNameReferences.length;
- System.arraycopy(this.qualifiedNameReferences, 0, this.qualifiedNameReferences = new char[length + 1][][], 0, length);
- this.qualifiedNameReferences[length] = qualifiedTypeName;
-
- qualifiedTypeName = CharOperation.subarray(qualifiedTypeName, 0, qualifiedTypeName.length - 1);
- char[][][] temp = internQualifiedNames(new char[][][] {qualifiedTypeName}, false);
- if (temp == EmptyQualifiedNames)
- continue next; // qualifiedTypeName is a well known name
- qualifiedTypeName = temp[0];
}
}
}
public boolean includes(char[] simpleName) {
- for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
- if (simpleName == this.simpleNameReferences[i]) return true;
- return false;
+ boolean result = sortedArrayContains(this.simpleNameReferences, simpleName, CHAR_ARR_COMPARATOR);
+ if (REFERENCE_COLLECTION_DEBUG) {
+ assertIncludes(result, simpleName);
+ }
+ return result;
}
public boolean includes(char[][] qualifiedName) {
- for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
- if (qualifiedName == this.qualifiedNameReferences[i]) return true;
- return false;
+ boolean result = sortedArrayContains(this.qualifiedNameReferences, qualifiedName, CHAR_CHAR_ARR_COMPARATOR);
+ if (REFERENCE_COLLECTION_DEBUG) {
+ assertIncludes(result, qualifiedName);
+ }
+ return result;
+}
+
+private static String qualifiedNamesToString(char[][][] qualifiedNames) {
+ if (qualifiedNames == null)
+ return "null"; //$NON-NLS-1$
+ return Arrays.stream(qualifiedNames).map(CharOperation::toString).collect(Collectors.joining(",")); //$NON-NLS-1$
}
/**
@@ -86,82 +107,157 @@ public boolean includes(char[][][] qualifiedNames, char[][] simpleNames) {
}
public boolean includes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
- // if either collection of names is null, it means it contained a well known name so we know it already has a match
+ boolean result = doIncludes(qualifiedNames, simpleNames, rootNames);
+ if (REFERENCE_COLLECTION_DEBUG) {
+ assertIncludes(result, qualifiedNames, simpleNames, rootNames);
+ }
+ return result;
+}
+
+private boolean doIncludes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
if (rootNames != null) {
- boolean foundRoot = false;
- for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
- foundRoot = insideRoot(rootNames[i]);
- if (!foundRoot)
+ if (!includesRootName(rootNames))
return false;
}
+ // if either collection of names is null, it means it contained a well known name so we know it already has a match
if (simpleNames == null || qualifiedNames == null) {
if (simpleNames == null && qualifiedNames == null) {
if (JavaBuilder.DEBUG)
System.out.println("Found well known match"); //$NON-NLS-1$
return true;
} else if (qualifiedNames == null) {
- for (int i = 0, l = simpleNames.length; i < l; i++) {
- if (includes(simpleNames[i])) {
- if (JavaBuilder.DEBUG)
- System.out.println("Found match in well known package to " + new String(simpleNames[i])); //$NON-NLS-1$
- return true;
- }
- }
- } else {
- for (int i = 0, l = qualifiedNames.length; i < l; i++) {
- char[][] qualifiedName = qualifiedNames[i];
- if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
- if (JavaBuilder.DEBUG)
- System.out.println("Found well known match in " + CharOperation.toString(qualifiedName)); //$NON-NLS-1$
- return true;
- }
- }
+ return includesSimpleName(simpleNames);
+ }
+ return includesQualifiedName(qualifiedNames);
+ }
+
+ if (simpleNames.length <= qualifiedNames.length) {
+ return includesSimpleName(simpleNames) && includesQualifiedName(qualifiedNames);
+ } else {
+ return includesQualifiedName(qualifiedNames) && includesSimpleName(simpleNames);
+ }
+}
+
+public boolean insideRoot(char[] rootName) {
+ boolean result = sortedArrayContains(this.rootReferences, rootName, CHAR_ARR_COMPARATOR);
+ if (REFERENCE_COLLECTION_DEBUG) {
+ if (result != debugIncludes(rootName)) {
+ String message = "Mismatch: " + String.valueOf(rootName) + (result ? " should not " : " should ") + " be included in " //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+ + Arrays.asList(CharOperation.toStrings(this.rootReferences));
+ throw new IllegalStateException(message);
}
+ }
+ return result;
+}
+
+private static <T> boolean sortedArrayContains(T[] array, T element, Comparator<? super T> comparator) {
+ int l = array.length;
+ if (l < BINARY_SEARCH_THRESHOLD) {
+ for (int i = 0; i < l; i++)
+ if (element == array[i]) return true;
return false;
}
+ return Arrays.binarySearch(array, element, comparator) >= 0;
+}
- int sLength = simpleNames.length;
- int qLength = qualifiedNames.length;
- if (sLength <= qLength) {
- for (int i = 0; i < sLength; i++) {
- if (includes(simpleNames[i])) {
- for (int j = 0; j < qLength; j++) {
- char[][] qualifiedName = qualifiedNames[j];
- if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
- if (JavaBuilder.DEBUG)
- System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
- + " to " + new String(simpleNames[i])); //$NON-NLS-1$
- return true;
- }
+private boolean includesSimpleName(char[][] simpleNames) {
+ return intersects(simpleNames, this.simpleNameReferences, CHAR_ARR_COMPARATOR);
+}
+
+private boolean includesQualifiedName(char[][][] qualifiedNames) {
+ if (intersects(qualifiedNames, this.qualifiedNameReferences, CHAR_CHAR_ARR_COMPARATOR)) {
+ return true;
+ }
+ char[][] maybeSimpleName;
+ for(int i = qualifiedNames.length - 1; i >= 0 && (maybeSimpleName = qualifiedNames[i]).length == 1; i--) {
+ if (includes(maybeSimpleName[0])) {
+ return true;
+ }
+ }
+ return false;
+}
+
+private boolean includesRootName(char[][] rootNames) {
+ return intersects(rootNames, this.rootReferences, CHAR_ARR_COMPARATOR);
+}
+
+// TODO there may be better thresholds available for different scenarios
+private static final int BINARY_SEARCH_THRESHOLD = 16;
+private static <T> boolean intersects(T[] firstSortedArr, T[] secondSortedArr, Comparator<? super T> comparator) {
+ /*
+ * Both arrays are sorted, so we can walk them in pairs.
+ * Using binary search for the remaining array elements to figure the next
+ * interesting index can greatly reduce the runtime cost for arrays that do
+ * have more than a few elements.
+ */
+ for(int i = 0, l = firstSortedArr.length, j = 0, k = secondSortedArr.length; i < l && j < k;) {
+ T firstElement = firstSortedArr[i];
+ T secondElement = secondSortedArr[j];
+ int compare = comparator.compare(firstElement, secondElement);
+ if (compare == 0) {
+ return true;
+ } else if (compare < 0) {
+ /*
+ * left side is smaller than the right side, but not exactly the right side.
+ * Take the next element from the left and proceed.
+ *
+ * If the number of remaining elements in the first array is sufficiently big,
+ * attempt a binary search for the second element to possibly skip a few elements.
+ */
+ i++;
+ if (l - i > BINARY_SEARCH_THRESHOLD) {
+ i = Arrays.binarySearch(firstSortedArr, i, l, secondElement, comparator);
+ if (i >= 0) {
+ return true;
}
- return false;
+ i = -(i + 1);
}
- }
- } else {
- for (int i = 0; i < qLength; i++) {
- char[][] qualifiedName = qualifiedNames[i];
- if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
- for (int j = 0; j < sLength; j++) {
- if (includes(simpleNames[j])) {
- if (JavaBuilder.DEBUG)
- System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
- + " to " + new String(simpleNames[j])); //$NON-NLS-1$
- return true;
- }
+ } else {
+ /*
+ * the inverse logic is applied here
+ */
+ j++;
+ if (k - j > BINARY_SEARCH_THRESHOLD) {
+ j = Arrays.binarySearch(secondSortedArr, j, k, firstElement, comparator);
+ if (j >= 0) {
+ return true;
}
- return false;
+ j = -(j + 1);
}
}
}
return false;
}
-public boolean insideRoot(char[] rootName) {
- for (int i = 0, l = this.rootReferences.length; i < l; i++)
- if (rootName == this.rootReferences[i]) return true;
- return false;
+// Generifying this appears to be pointless since arracopy takes an Object array anyways.
+private static void insertIntoArray(Object[] src, Object[] target, Object entry, int idx) {
+ System.arraycopy(src, 0, target, 0, idx);
+ target[idx] = entry;
+ System.arraycopy(src, idx, target, idx+1, src.length - idx);
+}
+
+private static char[][] ensureContainedInSortedOrder(char[][] sortedArray, char[] entry) {
+ int idx = Arrays.binarySearch(sortedArray, entry, CHAR_ARR_COMPARATOR);
+ if (idx < 0) {
+ idx = -(idx + 1);
+ char[][] result = new char[sortedArray.length + 1][];
+ insertIntoArray(sortedArray, result, entry, idx);
+ return result;
+ }
+ return sortedArray;
}
+private static boolean isWellKnownQualifiedName(char[][] qualifiedName) {
+ for (int i = 0, m = WellKnownQualifiedNames.length, qLength = qualifiedName.length; i < m; i++) {
+ char[][] wellKnownName = WellKnownQualifiedNames[i];
+ if (qLength > wellKnownName.length)
+ break; // all remaining well known names are shorter
+ if (CharOperation.equals(qualifiedName, wellKnownName)) {
+ return true;
+ }
+ }
+ return false;
+}
// When any type is compiled, its methods are verified for certain problems
// the MethodVerifier requests 3 well known types which end up in the reference collection
@@ -228,17 +324,38 @@ public static char[][][] internQualifiedNames(StringSet qualifiedStrings) {
return internQualifiedNames(result, false);
}
+/**
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ */
public static char[][][] internQualifiedNames(char[][][] qualifiedNames) {
return internQualifiedNames(qualifiedNames, false);
}
+/**
+ * Use a flyweight cache for the char arrays to avoid duplicated arrays with the same contents.
+ * After calling this method, identity comparison on the array contents of the resulting array
+ * will work for arrays with equal content.
+ * <p>
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ * <p>
+ * Optionally drops very common qualified names from the array to spare some bytes.
+ *
+ * @return a new array with interned elements.
+ */
public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWellKnown) {
+ return internQualifiedNames(qualifiedNames, keepWellKnown, true);
+}
+
+static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWellKnown, boolean doSort) {
if (qualifiedNames == null) return EmptyQualifiedNames;
int length = qualifiedNames.length;
if (length == 0) return EmptyQualifiedNames;
char[][][] keepers = new char[length][][];
+ char[][] prev = null;
+ boolean isSorted = true;
int index = 0;
+
next : for (int i = 0; i < length; i++) {
char[][] qualifiedName = qualifiedNames[i];
int qLength = qualifiedName.length;
@@ -248,6 +365,13 @@ public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean
break; // all remaining well known names are shorter
if (CharOperation.equals(qualifiedName, wellKnownName)) {
if (keepWellKnown) {
+ // This code is duplicated to encourage the JIT to inline more stuff
+ if (doSort && isSorted) {
+ if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) {
+ isSorted = false;
+ }
+ prev = qualifiedName;
+ }
keepers[index++] = wellKnownName;
}
continue next;
@@ -258,17 +382,69 @@ public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean
// InternedQualifiedNames[1] is for size 2...
// InternedQualifiedNames[6] is for size 7
QualifiedNameSet internedNames = InternedQualifiedNames[qLength <= MaxQualifiedNames ? qLength - 1 : 0];
- qualifiedName = internSimpleNames(qualifiedName, false);
+ qualifiedName = internSimpleNames(qualifiedName, false, false);
+ // This code is duplicated to encourage the JIT to inline more stuff
+ if (doSort && isSorted) {
+ if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) {
+ isSorted = false;
+ }
+ prev = qualifiedName;
+ }
keepers[index++] = internedNames.add(qualifiedName);
}
if (length > index) {
if (index == 0) return EmptyQualifiedNames;
System.arraycopy(keepers, 0, keepers = new char[index][][], 0, index);
}
+ if (doSort && !isSorted) {
+ Arrays.sort(keepers, CHAR_CHAR_ARR_COMPARATOR);
+ }
return keepers;
}
/**
+ * Compares the two char arrays.
+ * Longer arrays are considered to be smaller than shorter arrays.
+ * Arrays with the same length are compared char by char lexicographically.
+ *
+ * @see Character#compare(char, char)
+ */
+private static int compareCharArray(char[] left, char[] right){
+ if (left == right) {
+ return 0;
+ }
+ int l = left.length;
+ int diff = right.length - l;
+ if (diff == 0) {
+ for(int i = 0; i < l && (diff = left[i] - right[i]) == 0; i++) {
+ // all logic is in the loop header
+ }
+ }
+ return diff;
+}
+private static final Comparator<char[]> CHAR_ARR_COMPARATOR = ReferenceCollection::compareCharArray;
+
+/**
+ * Compares the two char-char arrays.
+ * Longer arrays are considered to be smaller than shorter arrays.
+ * Arrays with the same length are compared according to the logic in {@link #compareCharArray(char[], char[])}.
+ */
+static int compareCharCharArray(char[][] left, char[][]right) {
+ if (left == right) {
+ return 0;
+ }
+ int l = left.length;
+ int diff = right.length - l;
+ if (diff == 0) {
+ for(int i = 0; i < l && (diff = compareCharArray(left[i], right[i])) == 0; i++) {
+ // all logic is in the loop header
+ }
+ }
+ return diff;
+}
+private static final Comparator<char[][]> CHAR_CHAR_ARR_COMPARATOR = ReferenceCollection::compareCharCharArray;
+
+/**
* @deprecated
*/
public static char[][] internSimpleNames(Set<String> simpleStrings) {
@@ -301,13 +477,28 @@ public static char[][] internSimpleNames(StringSet simpleStrings, boolean remove
result[--length] = strings[i].toCharArray();
return internSimpleNames(result, removeWellKnown);
}
-
+/**
+ * Use a flyweight cache for the char arrays to avoid duplicated arrays with the same contents.
+ * After calling this method, identity comparison on the array contents of the resulting array
+ * will work for arrays with equal content.
+ * <p>
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ * <p>
+ * Optionally drops very common qualified names from the array to spare some bytes.
+ *
+ * @return a new array with interned elements.
+ */
public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown) {
+ return internSimpleNames(simpleNames, removeWellKnown, true);
+}
+static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown, boolean doSort) {
if (simpleNames == null) return EmptySimpleNames;
int length = simpleNames.length;
if (length == 0) return EmptySimpleNames;
char[][] keepers = new char[length][];
+ char[] prev = null;
+ boolean isSorted = true;
int index = 0;
next : for (int i = 0; i < length; i++) {
char[] name = simpleNames[i];
@@ -317,8 +508,16 @@ public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWel
if (sLength > wellKnownName.length)
break; // all remaining well known names are shorter
if (CharOperation.equals(name, wellKnownName)) {
- if (!removeWellKnown)
- keepers[index++] = WellKnownSimpleNames[j];
+ if (!removeWellKnown) {
+ keepers[index++] = wellKnownName;
+ // This code is duplicated to encourage the JIT to inline more stuff
+ if (doSort && isSorted) {
+ if (prev != null && compareCharArray(prev, name) > 0) {
+ isSorted = false;
+ }
+ prev = name;
+ }
+ }
continue next;
}
}
@@ -328,11 +527,144 @@ public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWel
// InternedSimpleNames[29] is for size 29
NameSet internedNames = InternedSimpleNames[sLength < MaxSimpleNames ? sLength : 0];
keepers[index++] = internedNames.add(name);
+ // This code is duplicated to encourage the JIT to inline more stuff
+ if (doSort && isSorted) {
+ if (prev != null && compareCharArray(prev, name) > 0) {
+ isSorted = false;
+ }
+ prev = name;
+ }
}
if (length > index) {
if (index == 0) return EmptySimpleNames;
System.arraycopy(keepers, 0, keepers = new char[index][], 0, index);
}
+ if (doSort && !isSorted) {
+ Arrays.sort(keepers, CHAR_ARR_COMPARATOR);
+ }
return keepers;
}
+
+// DEBUG code below
+public static boolean REFERENCE_COLLECTION_DEBUG = false;
+
+private void assertIncludes(boolean expectation, char[] simpleName) {
+ if (expectation != debugIncludes(simpleName)) {
+ String message = "Mismatch: " + String.valueOf(simpleName) + (expectation ? " should not " : " should ") + " be included in " //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+ + Arrays.asList(CharOperation.toStrings(this.simpleNameReferences));
+ throw new IllegalStateException(message);
+ }
+}
+
+private void assertIncludes(boolean expectation, char[][] qualifiedName) {
+ if (expectation != debugIncludes(qualifiedName)) {
+ String message = "Mismatch: " + CharOperation.toString(qualifiedName) + (expectation ? " should not " : " should ") + " be included in " //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+ + qualifiedNamesToString(this.qualifiedNameReferences);
+ throw new IllegalStateException(message);
+ }
+}
+
+private void assertIncludes(boolean expectation, char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
+ if (expectation != debugIncludes(qualifiedNames, simpleNames, rootNames)) {
+ String message = String.format("Mismatched includes(..): ReferenceCollection([%s], %s, %s).includes([%s], %s, %s)", //$NON-NLS-1$
+ qualifiedNamesToString(this.qualifiedNameReferences),
+ Arrays.toString(CharOperation.toStrings(this.simpleNameReferences)),
+ Arrays.toString(CharOperation.toStrings(this.rootReferences)),
+ qualifiedNamesToString(qualifiedNames),
+ Arrays.toString(CharOperation.toStrings(simpleNames)),
+ Arrays.toString(CharOperation.toStrings(rootNames))
+ );
+ throw new IllegalStateException(message);
+ }
+}
+
+private boolean debugIncludes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
+ // if either collection of names is null, it means it contained a well known name so we know it already has a match
+ if (rootNames != null) {
+ boolean foundRoot = false;
+ for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
+ foundRoot = debugInsideRoot(rootNames[i]);
+ if (!foundRoot)
+ return false;
+ }
+ if (simpleNames == null || qualifiedNames == null) {
+ if (simpleNames == null && qualifiedNames == null) {
+ if (JavaBuilder.DEBUG)
+ System.out.println("Found well known match"); //$NON-NLS-1$
+ return true;
+ } else if (qualifiedNames == null) {
+ for (int i = 0, l = simpleNames.length; i < l; i++) {
+ if (debugIncludes(simpleNames[i])) {
+ if (JavaBuilder.DEBUG)
+ System.out.println("Found match in well known package to " + new String(simpleNames[i])); //$NON-NLS-1$
+ return true;
+ }
+ }
+ } else {
+ for (int i = 0, l = qualifiedNames.length; i < l; i++) {
+ char[][] qualifiedName = qualifiedNames[i];
+ if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+ if (JavaBuilder.DEBUG)
+ System.out.println("Found well known match in " + CharOperation.toString(qualifiedName)); //$NON-NLS-1$
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ int sLength = simpleNames.length;
+ int qLength = qualifiedNames.length;
+ if (sLength <= qLength) {
+ for (int i = 0; i < sLength; i++) {
+ if (debugIncludes(simpleNames[i])) {
+ for (int j = 0; j < qLength; j++) {
+ char[][] qualifiedName = qualifiedNames[j];
+ if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+ if (JavaBuilder.DEBUG)
+ System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
+ + " to " + new String(simpleNames[i])); //$NON-NLS-1$
+ return true;
+ }
+ }
+ return false;
+ }
+ }
+ } else {
+ for (int i = 0; i < qLength; i++) {
+ char[][] qualifiedName = qualifiedNames[i];
+ if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+ for (int j = 0; j < sLength; j++) {
+ if (debugIncludes(simpleNames[j])) {
+ if (JavaBuilder.DEBUG)
+ System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
+ + " to " + new String(simpleNames[j])); //$NON-NLS-1$
+ return true;
+ }
+ }
+ return false;
+ }
+ }
+ }
+ return false;
+}
+
+private boolean debugInsideRoot(char[] rootName) {
+ for (int i = 0, l = this.rootReferences.length; i < l; i++)
+ if (rootName == this.rootReferences[i]) return true;
+ return false;
+}
+
+private boolean debugIncludes(char[] simpleName) {
+ for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
+ if (simpleName == this.simpleNameReferences[i]) return true;
+ return false;
+}
+
+private boolean debugIncludes(char[][] qualifiedName) {
+ for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
+ if (qualifiedName == this.qualifiedNameReferences[i]) return true;
+ return false;
+}
+
}
diff --git a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
index a57cc107e6..7afd3dc085 100644
--- a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
+++ b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
@@ -13,6 +13,8 @@
* Stephan Herrmann - Contribution for
* Bug 440477 - [null] Infrastructure for feeding external annotations into compilation
* Karsten Thoms - Bug 532505
+ * Sebastian Zarnekow - Contribution for
+ * Bug 545491 - Poor performance of ReferenceCollection with many source files
*******************************************************************************/
package org.eclipse.jdt.internal.core.builder;
@@ -387,8 +389,11 @@ static State read(IProject project, DataInputStream in) throws IOException, Core
for (int i = 0; i < length; i++)
newState.recordLocatorForType(in.readUTF(), internedTypeLocators[in.readInt()]);
- char[][] internedRootNames = ReferenceCollection.internSimpleNames(readNames(in), false);
- char[][] internedSimpleNames = ReferenceCollection.internSimpleNames(readNames(in), false);
+ /*
+ * Here we read global arrays of names for the entire project - do not mess up the ordering while interning
+ */
+ char[][] internedRootNames = ReferenceCollection.internSimpleNames(readNames(in), false /* keep well known */, false /* do not sort */);
+ char[][] internedSimpleNames = ReferenceCollection.internSimpleNames(readNames(in), false /* keep well known */, false /* do not sort */);
char[][][] internedQualifiedNames = new char[length = in.readInt()][][];
for (int i = 0; i < length; i++) {
int qLength = in.readInt();
@@ -397,7 +402,7 @@ static State read(IProject project, DataInputStream in) throws IOException, Core
qName[j] = internedSimpleNames[in.readInt()];
internedQualifiedNames[i] = qName;
}
- internedQualifiedNames = ReferenceCollection.internQualifiedNames(internedQualifiedNames, false);
+ internedQualifiedNames = ReferenceCollection.internQualifiedNames(internedQualifiedNames, false /* drop well known */, false /* do not sort */);
newState.references = new SimpleLookupTable(length = in.readInt());
for (int i = 0; i < length; i++) {

Back to the top