diff options
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; +} + } |