Skip to main content
aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSebastian Zarnekow2019-03-30 13:01:37 -0400
committerAndrey Loskutov2019-04-04 10:31:30 -0400
commitdb34b6c6d93872a5055adf9f939b44095582de53 (patch)
treeffd2683f93cd5bd88e4b3752044b01f32f8f5c73
parentea6dff04b6decdc2a1f54bc692022a63221a6a0a (diff)
downloadeclipse.jdt.core-db34b6c6d93872a5055adf9f939b44095582de53.tar.gz
eclipse.jdt.core-db34b6c6d93872a5055adf9f939b44095582de53.tar.xz
eclipse.jdt.core-db34b6c6d93872a5055adf9f939b44095582de53.zip
Bug 545491 - Improved performance of ReferenceCollectionI20190404-1800
The implementation of reference collection suffered from a couple of quadratic lookup operations in its logic to determine, whether the collection includes certain names. Instead of doing a simple nested loop scanning of the given arrays, we apply an algorithm based on the reduced runtime complexity of binary searches. The reference collections are long living objects that are far more often queried than modified. Now we use a simple comparator to sort the arrays by length and content. When the collection is asked whether it contains another list of names, these names have to be interned. In addition to the interning, we also sort the argument arrays. Now we do have a total of three pairs of arrays, each of the paired arrays is sorted by the same criteria. That allows to walk both arrays pairways so even if the worst case, we do no longer need O(n*m) with n=first.length and m = second.length, but only O(2*(n+m)) comparisons. For longer arrays, we even use binary search logic to skip more than one array index when we advance the iteration. In our scenario, this reduced the accumulated time for invocations of include from 90s to less than one second. Change-Id: I815a43e41ecb5ecaf874fc731d63bffbe7081ea9 Signed-off-by: Sebastian Zarnekow <sebastian.zarnekow@gmail.com> Signed-off-by: Andrey Loskutov <loskutov@gmx.de>
-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.java372
-rw-r--r--org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java497
3 files changed, 781 insertions, 89 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 ec9718a8e5..dd134b94dd 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
@@ -541,6 +541,7 @@ public class BuilderTests extends TestCase {
StaticFinalTests.class,
GetResourcesTests.class,
FriendDependencyTests.class,
+ ReferenceCollectionTest.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
new file mode 100644
index 0000000000..481fe69afd
--- /dev/null
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
@@ -0,0 +1,372 @@
+/*******************************************************************************
+ * Copyright (c) 2000, 2015 IBM Corporation 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:
+ * IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.jdt.core.tests.builder;
+
+import static org.junit.Assert.assertArrayEquals;
+
+import java.lang.reflect.Field;
+import java.util.Arrays;
+import java.util.Collections;
+
+import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.internal.core.builder.ReferenceCollection;
+
+import junit.framework.Test;
+
+public class ReferenceCollectionTest extends BuilderTests {
+
+ public ReferenceCollectionTest(String name) {
+ super(name);
+ }
+
+ public static Test suite() {
+ return buildTestSuite(ReferenceCollectionTest.class);
+ }
+
+ private static class TestableReferenceCollection extends ReferenceCollection {
+ /*
+ Make the package visible fields reflectively available for testing
+ char[][][] qualifiedNameReferences;
+ char[][] simpleNameReferences;
+ char[][] rootReferences;
+ */
+ protected TestableReferenceCollection(char[][][] qualifiedNameReferences, char[][] simpleNameReferences,
+ char[][] rootReferences) {
+ super(qualifiedNameReferences, simpleNameReferences, rootReferences);
+ }
+
+ char[][][] getQualifiedNameReferences() {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("qualifiedNameReferences");
+ fld.setAccessible(true);
+ return (char[][][]) fld.get(this);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ char[][] getSimpleNameReferences() {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("simpleNameReferences");
+ fld.setAccessible(true);
+ return (char[][]) fld.get(this);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+
+ char[][] getRootReferences() {
+ try {
+ Field fld = ReferenceCollection.class.getDeclaredField("rootReferences");
+ fld.setAccessible(true);
+ return (char[][]) fld.get(this);
+ } catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+ throw new RuntimeException(e);
+ }
+ }
+ }
+
+ public void testInternQualifiedNamesSorts_01() {
+ char[][][] qualifiedNames = new char[][][] {
+ CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
+ CharOperation.splitOn('.', "a.a.a".toCharArray()),
+ CharOperation.splitOn('.', "b.b.b".toCharArray()),
+ CharOperation.splitOn('.', "a.a".toCharArray()),
+ CharOperation.splitOn('.', "a.b".toCharArray()),
+ CharOperation.splitOn('.', "com".toCharArray()),
+ CharOperation.splitOn('.', "a".toCharArray()),
+ CharOperation.splitOn('.', "b".toCharArray())
+ };
+ char[][][] expectation = qualifiedNames.clone();
+ Collections.shuffle(Arrays.asList(qualifiedNames));
+ char[][][] internQualifiedNames = ReferenceCollection.internQualifiedNames(qualifiedNames, true);
+ assertArrayEquals("Should be sorted, longest first, alphanumeric later",
+ toStringArray(expectation),
+ toStringArray(internQualifiedNames));
+ }
+
+ public void testInternQualifiedNamesSorts_02() {
+ char[][][] qualifiedNames = new char[][][] {
+ CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
+ CharOperation.splitOn('.', "a.a.a".toCharArray()),
+ CharOperation.splitOn('.', "b.b.b".toCharArray()),
+ CharOperation.splitOn('.', "a.a".toCharArray()),
+ CharOperation.splitOn('.', "a.b".toCharArray()),
+ CharOperation.splitOn('.', "com".toCharArray()),
+ CharOperation.splitOn('.', "a".toCharArray()),
+ CharOperation.splitOn('.', "b".toCharArray())
+ };
+ char[][][] expectation = new char[][][] {
+ CharOperation.splitOn('.', "a.a.a".toCharArray()),
+ CharOperation.splitOn('.', "b.b.b".toCharArray()),
+ CharOperation.splitOn('.', "a.a".toCharArray()),
+ CharOperation.splitOn('.', "a.b".toCharArray()),
+ CharOperation.splitOn('.', "a".toCharArray()),
+ CharOperation.splitOn('.', "b".toCharArray())
+ };
+ Collections.shuffle(Arrays.asList(qualifiedNames));
+ char[][][] internQualifiedNames = ReferenceCollection.internQualifiedNames(qualifiedNames, false);
+ assertArrayEquals("Should be sorted, longest first, alphanumeric later",
+ toStringArray(expectation),
+ toStringArray(internQualifiedNames));
+ }
+
+ public void testInternSimpleNamesSorts_01() {
+ char[][] simpleNames = new char[][] {
+ "Throwable".toCharArray(),
+ "aaa".toCharArray(),
+ "bbb".toCharArray(),
+ "ccc".toCharArray(),
+ "aa".toCharArray(),
+ "a".toCharArray()
+ };
+ char[][] expectation = simpleNames.clone();
+ Collections.shuffle(Arrays.asList(simpleNames));
+ char[][] internSimpleNames = ReferenceCollection.internSimpleNames(simpleNames, false);
+ assertArrayEquals("Should be sorted, longest first, alphanumeric later",
+ toStringArray(expectation),
+ toStringArray(internSimpleNames));
+ }
+
+ public void testInternSimpleNamesSorts_02() {
+ char[][] simpleNames = new char[][] {
+ "aaa".toCharArray(),
+ "bbb".toCharArray(),
+ "Throwable".toCharArray(),
+ "ccc".toCharArray(),
+ "java".toCharArray(),
+ "aa".toCharArray(),
+ "a".toCharArray()
+ };
+ char[][] expectation = new char[][] {
+ "aaa".toCharArray(),
+ "bbb".toCharArray(),
+ "ccc".toCharArray(),
+ "aa".toCharArray(),
+ "a".toCharArray()
+ };
+ Collections.shuffle(Arrays.asList(simpleNames));
+ char[][] internSimpleNames = ReferenceCollection.internSimpleNames(simpleNames, true);
+ assertArrayEquals("Should be sorted, longest first, alphanumeric later",
+ toStringArray(expectation),
+ toStringArray(internSimpleNames));
+ }
+
+ public void testIncludesWithBinarySearch() {
+ char[][] simpleNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "a".toCharArray(),
+ "b".toCharArray(),
+ "c".toCharArray(),
+ "d".toCharArray(),
+ "e".toCharArray(),
+ "f".toCharArray(),
+ "g".toCharArray(),
+ "h".toCharArray(),
+ "i".toCharArray(),
+ "j".toCharArray(),
+ "k".toCharArray(),
+ "l".toCharArray(),
+ "m".toCharArray(),
+ "n".toCharArray(),
+ "o".toCharArray(),
+ "p".toCharArray(),
+ "q".toCharArray(),
+ "r".toCharArray(),
+ "s".toCharArray(),
+ "t".toCharArray(),
+ "u".toCharArray(),
+ "v".toCharArray(),
+ "w".toCharArray(),
+ "x".toCharArray(),
+ "y".toCharArray(),
+ "z".toCharArray()
+ }, false);
+ ReferenceCollection collection = new TestableReferenceCollection(null, simpleNames, null);
+ for(char[] simpleName: simpleNames) {
+ assertTrue("Should include " + simpleName[0], collection.includes(simpleName));
+ assertFalse("Should not include " + CharOperation.toUpperCase(simpleName)[0], collection.includes(CharOperation.toUpperCase(simpleName)));
+ }
+ }
+
+ public void testIncludesWithLinearSearch() {
+ char[][] simpleNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "a".toCharArray(),
+ "b".toCharArray(),
+ "c".toCharArray(),
+ "d".toCharArray(),
+ "e".toCharArray(),
+ "f".toCharArray(),
+ "g".toCharArray(),
+ "h".toCharArray()
+ }, false);
+ ReferenceCollection collection = new TestableReferenceCollection(null, simpleNames, null);
+ for(char[] simpleName: simpleNames) {
+ assertTrue("Should include " + simpleName[0], collection.includes(simpleName));
+ assertFalse("Should not include " + CharOperation.toUpperCase(simpleName)[0], collection.includes(CharOperation.toUpperCase(simpleName)));
+ }
+ }
+
+ public void testIncludes01() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] { "a.a", "b.a", "b.b" };
+ refColl.addDependencies(array);
+
+ TestableReferenceCollection other = new TestableReferenceCollection(null, null, null);
+ String[] array2 = new String[] { "a.a", "B.A", "b.b" };
+ other.addDependencies(array2);
+
+ assertTrue(refColl.includes(other.getQualifiedNameReferences(), other.getSimpleNameReferences(), other.getRootReferences()));
+ assertTrue(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
+ }
+
+ public void testIncludes02() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] { "a.x", "b.y" };
+ refColl.addDependencies(array);
+
+ TestableReferenceCollection other = new TestableReferenceCollection(null, null, null);
+ String[] array2 = new String[] { "a.y", "b.x" };
+ other.addDependencies(array2);
+
+ assertTrue(refColl.includes(other.getQualifiedNameReferences(), other.getSimpleNameReferences(), other.getRootReferences()));
+ assertTrue(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
+ }
+
+ public void testIncludes03() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] { "a.d.y", "c.x" };
+ refColl.addDependencies(array);
+
+ TestableReferenceCollection other = new TestableReferenceCollection(null, null, null);
+ String[] array2 = new String[] { "c.y" };
+ other.addDependencies(array2);
+
+ assertTrue(refColl.includes(other.getQualifiedNameReferences(), other.getSimpleNameReferences(), other.getRootReferences()));
+ assertTrue(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
+ }
+
+ public void testIncludes04() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] { "a.d.y" };
+ refColl.addDependencies(array);
+
+ TestableReferenceCollection other = new TestableReferenceCollection(null, null, null);
+ String[] array2 = new String[] { "a.d" };
+ other.addDependencies(array2);
+
+ assertTrue(refColl.includes(other.getQualifiedNameReferences(), other.getSimpleNameReferences(), other.getRootReferences()));
+ assertTrue(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
+ }
+
+ public void testIncludesNot() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] {"b.a"};
+ refColl.addDependencies(array);
+
+ TestableReferenceCollection other = new TestableReferenceCollection(null, null, null);
+ String[] array2 = new String[] {"B.A"};
+ other.addDependencies(array2);
+
+ assertFalse(refColl.includes(other.getQualifiedNameReferences(), other.getSimpleNameReferences(), other.getRootReferences()));
+ assertFalse(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
+ }
+
+ public void testAddDependencies() {
+ TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
+
+ String[] array = new String[] {"a.b.c.D"};
+ refColl.addDependencies(array);
+
+ char[][][] qualifiedNameReferences = refColl.getQualifiedNameReferences();
+ String [] strings = toStringArray(qualifiedNameReferences);
+ assertArrayEquals(new String[] {
+ "a.b.c.D",
+ "a.b.c",
+ "a.b",
+ "a"
+ }, strings);
+
+ char[][] simpleNameReferences = refColl.getSimpleNameReferences();
+ assertArrayEquals(new String[] {
+ "D",
+ "a",
+ "b",
+ "c"
+ }, CharOperation.toStrings(simpleNameReferences));
+
+ char[][] rootReferences = refColl.getRootReferences();
+ assertArrayEquals(new String[] {
+ "a"
+ }, CharOperation.toStrings(rootReferences));
+ }
+
+ 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);
+ }
+
+ public void testRegression01() {
+ char[][][] qualifiedNames = new char[][][] {
+ CharOperation.splitOn('.', "p1.IX".toCharArray()),
+ CharOperation.splitOn('.', "p2.X".toCharArray())
+ };
+ char[][] simpleNames = new char[][] {
+ "I__X".toCharArray(), "IX".toCharArray(), "p1".toCharArray(), "p2".toCharArray(), "X".toCharArray()
+ };
+ char[][] rootNames = new char[][] {
+ "java".toCharArray(), "IX".toCharArray(), "p1".toCharArray(), "p2".toCharArray()
+ };
+ ReferenceCollection collection = new TestableReferenceCollection(qualifiedNames, simpleNames, rootNames);
+ qualifiedNames = ReferenceCollection.internQualifiedNames(new char[][][] {
+ CharOperation.splitOn('.', "p2".toCharArray())
+ });
+ simpleNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "X".toCharArray()
+ }, true);
+ rootNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "p2".toCharArray()
+ }, false);
+
+ assertTrue("Should include", collection.includes(qualifiedNames, simpleNames, rootNames));
+ }
+
+ public void testRegression02() {
+ char[][][] qualifiedNames = new char[][][] {};
+ char[][] simpleNames = new char[][] {
+ "GeneratedAnnotation".toCharArray(), "Test".toCharArray()
+ };
+ char[][] rootNames = new char[][] {
+ "java".toCharArray(), "GeneratedAnnotation".toCharArray()
+ };
+ ReferenceCollection collection = new TestableReferenceCollection(qualifiedNames, simpleNames, rootNames);
+
+ qualifiedNames = null;
+ simpleNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "GeneratedAnnotation".toCharArray()
+ }, true);
+ rootNames = ReferenceCollection.internSimpleNames(new char[][] {
+ "GeneratedAnnotation".toCharArray()
+ }, false);
+
+ assertTrue("Should include", collection.includes(qualifiedNames, simpleNames, rootNames));
+ }
+}
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..12b2bc54e4 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
@@ -14,14 +14,20 @@
*******************************************************************************/
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 +37,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 +105,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
@@ -232,13 +326,25 @@ 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.
+ *
+ * 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) {
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 +354,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 (isSorted) {
+ if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) {
+ isSorted = false;
+ }
+ prev = qualifiedName;
+ }
keepers[index++] = wellKnownName;
}
continue next;
@@ -258,17 +371,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 (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 (!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 +466,26 @@ 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.
+ *
+ * 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);
+}
+private 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 +495,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 +514,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;
+}
+
}

Back to the top