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.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