diff options
14 files changed, 854 insertions, 294 deletions
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/Bug544921Test.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/Bug544921Test.java new file mode 100644 index 0000000000..1740794da4 --- /dev/null +++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/Bug544921Test.java @@ -0,0 +1,379 @@ +/******************************************************************************* + * Copyright (c) 2019 Sebastian Zarnekow and others. + * + * This program and the accompanying materials + * are made available under the terms of the Eclipse Public License 2.0 + * which accompanies this distribution, and is available at + * https://www.eclipse.org/legal/epl-2.0/ + * + * SPDX-License-Identifier: EPL-2.0 + * + * Contributors: + * Sebastian Zarnekow - initial API and implementation + *******************************************************************************/ +package org.eclipse.jdt.core.tests.builder; + +import org.eclipse.core.runtime.IPath; +import org.eclipse.jdt.core.JavaModelException; +import org.eclipse.jdt.core.tests.util.Util; +import junit.framework.Test; + +public class Bug544921Test extends BuilderTests { + public Bug544921Test(String name) { + super(name); + } + + public static Test suite() { + return buildTestSuite(Bug544921Test.class); + } + + public void testBuildLargeFile_01() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 1, 10, 64); + fullBuild(); + expectingNoProblems(); + } + + public void testBuildLargeFile_02() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 2, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + public void testBuildLargeFile_03() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 3, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + public void testBuildLargeFile_04() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 4, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + public void testBuildLargeFile_05() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 5, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + public void testBuildLargeFile_08() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 8, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + public void _testBuildLargeFile_10() throws JavaModelException, Exception { + IPath projectPath = env.addProject("Bug544921Test", "1.8"); //$NON-NLS-1$ + scaffoldProject(projectPath, 10, 500, 64); + fullBuild(); + expectingNoProblems(); + } + + private void scaffoldProject(IPath projectPath, int maxPeripheral, int maxRegister, int maxFields) throws JavaModelException { + env.addExternalJars(projectPath, Util.getJavaClassLibs()); + + env.addClass(projectPath, "reg", "Field", //$NON-NLS-1$ //$NON-NLS-2$ + "package reg;\n" + + "\n" + + "import reg.Register.AccessType;\n" + + "\n" + + "public class Field {\n" + + " String name;\n" + + " String description;\n" + + " long bitRange;\n" + + " AccessType accessType;\n" + + "\n" + + " public Field(String name, String description, long bitRange, AccessType accessType) {\n" + + " super();\n" + + " this.name = name;\n" + + " this.description = description;\n" + + " this.bitRange = bitRange;\n" + + " this.accessType = accessType;\n" + + " }\n" + + "\n" + + " @Override\n" + + " public String toString() {\n" + + " return \"Field [name=\" + name + \", description=\" + description + \", bitRange=\" + bitRange + \", accessType=\"\n" + + " + accessType + \"]\";\n" + + " }\n" + + " \n" + + "}" //$NON-NLS-1$ + ); + + env.addClass(projectPath, "reg", "Peripheral", //$NON-NLS-1$ //$NON-NLS-2$ + "package reg;\n" + + "\n" + + "import java.util.Collection;\n" + + "import java.util.Map;\n" + + "import java.util.TreeMap;\n" + + "\n" + + "public class Peripheral {\n" + + "\n" + + " String name;\n" + + " String version;\n" + + " String description;\n" + + " String groupName;\n" + + " long baseAddress;\n" + + " long size;\n" + + "\n" + + " Map<String, Register> registersMap;\n" + + "\n" + + " public Peripheral(String name, String version, String description, String groupName,\n" + + " long baseAddress, long size) {\n" + + " super();\n" + + " this.name = name;\n" + + " this.version = version;\n" + + " this.description = description;\n" + + " this.groupName = groupName;\n" + + " this.baseAddress = baseAddress;\n" + + " this.size = size;\n" + + " }\n" + + "\n" + + " private void initRegistersMap(){\n" + + " if (registersMap != null) {\n" + + " return;\n" + + " }\n" + + " registersMap = new TreeMap<>();\n" + + " for (java.lang.reflect.Field field : this.getClass().getDeclaredFields()) {\n" + + " if (!Register.class.isAssignableFrom(field.getType())){\n" + + " continue;\n" + + " }\n" + + " try {\n" + + " registersMap.put(field.getName(), (Register) field.get(this));\n" + + " } catch (Exception e) {\n" + + " e.printStackTrace();\n" + + " }\n" + + " }\n" + + " }\n" + + "\n" + + " public Register getRegister(String name) {\n" + + " return registersMap.get(name);\n" + + " }\n" + + " public Collection<Register> getRegisters(){\n" + + " initRegistersMap();\n" + + " return registersMap.values();\n" + + " }\n" + + "}\n" //$NON-NLS-1$ + ); + + env.addClass(projectPath, "reg", "Reg", //$NON-NLS-1$ //$NON-NLS-2$ + "package reg;\n" + + "\n" + + "public final class Reg {\n" + + "\n" + + " Peripheral_TIMER0 peripheral_Timer0 = new Peripheral_TIMER0();\n" + + "\n" + + " public static final class Peripheral_TIMER0 extends Peripheral {\n" + + "\n" + + " public Peripheral_TIMER0() {\n" + + " super(\"TIMER0\", \"1.0\", \"desc\", \"groupName\", 0, 32);\n" + + " }\n" + + "\n" + + " public Reg_CR regCR = new Reg_CR();\n" + + "\n" + + " public static final class Reg_CR extends Register {\n" + + " public Reg_CR() {\n" + + " super(\"CR\", \"\", 0, 32, AccessType.readWrite, 0xf, 0x0);\n" + + " }\n" + + "\n" + + " // fields of CR\n" + + " public Field_EN fieldEn = new Field_EN();\n" + + "\n" + + " public static final class Field_EN extends Field {\n" + + " public Field_EN() {\n" + + " super(\"EN\", \"description\", 0, AccessType.readWrite);\n" + + " }\n" + + " }\n" + + "\n" + + " public Field_RST fieldRST = new Field_RST();\n" + + "\n" + + " public static final class Field_RST extends Field {\n" + + " public Field_RST() {\n" + + " super(\"RST\", \"description\", 1, AccessType.readWrite);\n" + + " }\n" + + " }\n" + + " }\n" + + " }\n" + + "\n" + + " public static void main(String[] args) {\n" + + " Reg reg = new Reg();\n" + + "\n" + + " System.out.println(reg.peripheral_Timer0.regCR.name + \": \" + reg.peripheral_Timer0.regCR.resetValue);\n" + + " System.out.println(reg.peripheral_Timer0.regCR.fieldEn.name + \": \" + reg.peripheral_Timer0.regCR.fieldEn.bitRange);\n" + + " }\n" + + "}\n" //$NON-NLS-1$ + ); + + env.addClass(projectPath, "reg", "Register", //$NON-NLS-1$ //$NON-NLS-2$ + "package reg;\n" + + "\n" + + "import java.util.Collection;\n" + + "import java.util.Map;\n" + + "import java.util.TreeMap;\n" + + "\n" + + "public class Register {\n" + + "\n" + + " public enum AccessType {\n" + + " readOnly, readWrite;\n" + + " }\n" + + "\n" + + " String name;\n" + + " String description;\n" + + " long addressOffset;\n" + + " long size;\n" + + " AccessType accessType;\n" + + " long resetValue;\n" + + " long resetMask;\n" + + " long value;\n" + + "\n" + + " Map<String, Field> fieldsMap;\n" + + "\n" + + " public Register(String name, String description, long addressOffset, long size,\n" + + " AccessType accessType, long resetValue, long resetMask) {\n" + + " this.name = name;\n" + + " this.description = description;\n" + + " this.addressOffset = addressOffset;\n" + + " this.size = size;\n" + + " this.accessType = accessType;\n" + + " this.resetValue = resetValue;\n" + + " this.resetMask = resetMask;\n" + + "\n" + + " }\n" + + "\n" + + " private void initFieldsMap(){\n" + + " if (fieldsMap != null) {\n" + + " return;\n" + + " }\n" + + " fieldsMap = new TreeMap<>();\n" + + " for (java.lang.reflect.Field field : this.getClass().getDeclaredFields()) {\n" + + " if (!Field.class.isAssignableFrom(field.getType())){\n" + + " continue;\n" + + " }\n" + + " try {\n" + + " fieldsMap.put(field.getName(), (Field) field.get(this));\n" + + " } catch (Exception e) {\n" + + " e.printStackTrace();\n" + + " }\n" + + " }\n" + + " }\n" + + "\n" + + " public void setValue(long value){\n" + + " this.value = value;\n" + + " }\n" + + "\n" + + " public long getValue(){\n" + + " return this.value;\n" + + " }\n" + + "\n" + + " public Collection<Field> getFields(){\n" + + " initFieldsMap();\n" + + " return fieldsMap.values();\n" + + " }\n" + + "\n" + + " @Override\n" + + " public String toString() {\n" + + " return \"Register [name=\" + name + \", description=\" + description + \", addressOffset=\" + addressOffset\n" + + " + \", size=\" + size + \", accessType=\" + accessType + \", resetValue=\" + resetValue + \", resetMask=\"\n" + + " + resetMask + \"]\";\n" + + " }\n" + + "\n" + + "\n" + + "}\n" //$NON-NLS-1$ + ); + + env.addClass(projectPath, "reg.generate", "DeviceXY", genSource(maxPeripheral, maxRegister, maxFields)); + } + + public static String genSource(int maxPeripheral, int maxRegister, int maxFields) { + /* + * + * The example that took 25 minutes was generated with: int maxPeripheral = 10; + * int maxRegister = 500; int maxFields = 64; + * + * Still performs ok (less than a minute): int maxPeripheral = 2; int + * maxRegister = 500; int maxFields = 64; + * + * With this (8 MB) it gets already slow (few minutes): int maxPeripheral = 3; + * int maxRegister = 500; int maxFields = 64; + * + * This takes 5 minutes (14MB file-size): int maxPeripheral = 5; int maxRegister + * = 500; int maxFields = 64; + */ + + StringBuilder source = new StringBuilder(); + + source.append("package reg.generate;").append(System.lineSeparator()); + source.append("public class DeviceXY {").append(System.lineSeparator()); + source.append("private static DeviceXY instance;").append(System.lineSeparator()); + source.append("private DeviceXY() {}").append(System.lineSeparator()); + source.append("public static DeviceXY getInstance() {").append(System.lineSeparator()); + source.append(" if (instance == null) { instance = new DeviceXY(); }").append(System.lineSeparator()); + source.append(" return instance;").append(System.lineSeparator()); + source.append("}").append(System.lineSeparator()); + + for (int peripheral = 0; peripheral < maxPeripheral; peripheral++) { + String peripheralName = "peri_" + peripheral; + String peripheralClassName = String.valueOf(Character.toUpperCase(peripheralName.charAt(0))) + + peripheralName.substring(1); + + source.append("public ").append(peripheralClassName).append(" ").append(peripheralName) + .append(" = new ").append(peripheralClassName).append("();").append(System.lineSeparator()); + source.append("public static final class ").append(peripheralClassName) + .append(" extends reg.Peripheral {").append(System.lineSeparator()); + // constructor start + source.append("public ").append(peripheralClassName).append("() {").append(System.lineSeparator()); + source.append(" super(\"").append(peripheralName).append("\",") + .append("\"1.0\",\"desc\", \"groupName\", 0, 32);").append(System.lineSeparator()); + source.append("}").append(System.lineSeparator()); + // constructor end + + for (int register = 0; register < maxRegister; register++) { + String registerName = "reg_" + register; + String registerClassName = String.valueOf(Character.toUpperCase(registerName.charAt(0))) + + registerName.substring(1); + + source.append("public ").append(registerClassName).append(" ").append(registerName) + .append(" = new ").append(registerClassName).append("();").append(System.lineSeparator()); + + source.append("/**").append(System.lineSeparator()); + source.append("* Register ").append(registerName).append(System.lineSeparator()); + source.append("*/").append(System.lineSeparator()); + source.append("public static final class ").append(registerClassName) + .append(" extends reg.Register {").append(System.lineSeparator()); + // constructor start + source.append("public ").append(registerClassName).append("() {") + .append(System.lineSeparator()); + source.append(" super(\"").append(registerName).append("\",") + .append("\"desc\", 0, 32, AccessType.readWrite, 0xf, 0x0);").append(System.lineSeparator()); + source.append("}").append(System.lineSeparator()); + // constructor end + + source.append("//fields").append(System.lineSeparator()); + + for (int field = 0; field < maxFields; field++) { + String fieldName = "field_" + field; + source.append("public ").append("reg.Field").append(" ").append(fieldName) + .append(" = new ").append("reg.Field").append("(\"").append(fieldName).append("\",") + .append("\"desc\", 0, AccessType.readWrite);").append(System.lineSeparator()); + + } + + source.append("}").append(System.lineSeparator()); + } + source.append("}").append(System.lineSeparator()); + } + + + source.append("}").append(System.lineSeparator()); + + return source.toString(); + + } +} 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 41bd69c710..834f554042 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 @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2000, 2015 IBM Corporation and others. + * Copyright (c) 2000, 2019 IBM Corporation and others. * * This program and the accompanying materials * are made available under the terms of the Eclipse Public License 2.0 @@ -555,6 +555,9 @@ public class BuilderTests extends TestCase { list.add(ParticipantBuildTests.class); list.add(AnnotationDependencyTests.class); } + if (matchesCompliance(F_1_8)) { + list.add(Bug544921Test.class); + } if (matchesCompliance(F_9)) { list.add(LeakTestsAfter9.class); } diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/BinaryTypeBinding.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/BinaryTypeBinding.java index b1364c66d7..50a3633828 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/BinaryTypeBinding.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/BinaryTypeBinding.java @@ -42,10 +42,13 @@ * Jesper Steen Moller - Contributions for * Bug 412150 [1.8] [compiler] Enable reflected parameter names during annotation processing * Bug 412153 - [1.8][compiler] Check validity of annotations which may be repeatable + * Sebastian Zarnekow - Contributions for + * bug 544921 - [performance] Poor performance with large source files *******************************************************************************/ package org.eclipse.jdt.internal.compiler.lookup; import java.util.ArrayList; +import java.util.Arrays; import org.eclipse.jdt.core.compiler.CharOperation; import org.eclipse.jdt.internal.compiler.ast.Annotation; @@ -100,6 +103,7 @@ public class BinaryTypeBinding extends ReferenceBinding { private ReferenceBinding containerAnnotationType; int defaultNullness = 0; + boolean memberTypesSorted = false; public enum ExternalAnnotationStatus { FROM_SOURCE, NOT_EEA_CONFIGURED, @@ -1283,20 +1287,39 @@ public ReferenceBinding getMemberType(char[] typeName) { return memberType == null ? null : this.environment.createMemberType(memberType, this); } - for (int i = this.memberTypes.length; --i >= 0;) { - ReferenceBinding memberType = this.memberTypes[i]; - if (memberType instanceof UnresolvedReferenceBinding) { - char[] name = memberType.sourceName; // source name is qualified with enclosing type name - int prefixLength = this.compoundName[this.compoundName.length - 1].length + 1; // enclosing$ - if (name.length == (prefixLength + typeName.length)) // enclosing $ typeName - if (CharOperation.fragmentEquals(typeName, name, prefixLength, true)) // only check trailing portion - return this.memberTypes[i] = (ReferenceBinding) resolveType(memberType, this.environment, false /* no raw conversion for now */); - } else if (CharOperation.equals(typeName, memberType.sourceName)) { - return memberType; - } + ReferenceBinding[] members = sortedMemberTypes(); + int memberTypeIndex = unresolvedTypesAwareBinarySearch(typeName, members); + if (memberTypeIndex >= 0) { + ReferenceBinding memberType = members[memberTypeIndex]; + if (memberType instanceof UnresolvedReferenceBinding) { + return members[memberTypeIndex] = (ReferenceBinding) resolveType(memberType, this.environment, false /* no raw conversion for now */); + } + return memberType; } return null; } +private int unresolvedTypesAwareBinarySearch(char[] name, ReferenceBinding[] sortedMemberTypes) { + if (sortedMemberTypes == null) + return -1; + int max = sortedMemberTypes.length; + if (max == 0) + return -1; + int left = 0, right = max - 1, nameLength = name.length; + int mid = 0; + char[] midName; + while (left <= right) { + mid = left + (right - left) /2; + int compare = compare(name, midName = getSourceName(sortedMemberTypes[mid]), nameLength, midName.length); + if (compare < 0) { + right = mid-1; + } else if (compare > 0) { + left = mid+1; + } else { + return mid; + } + } + return -1; +} // NOTE: the return type, arg & exception types of each method of a binary type are resolved when needed @Override public MethodBinding[] getMethods(char[] selector) { @@ -1522,6 +1545,11 @@ public ReferenceBinding[] memberTypes() { if (!isPrototype()) { if ((this.tagBits & TagBits.HasUnresolvedMemberTypes) == 0) return this.memberTypes; + /* + * The members obtained from the prototype are already sorted + * thus we can safely assume that our local copy of the member types + * is sorted, too. + */ ReferenceBinding [] members = this.prototype.memberTypes(); int memberTypesLength = members == null ? 0 : members.length; if (memberTypesLength > 0) { @@ -1530,17 +1558,49 @@ public ReferenceBinding[] memberTypes() { this.memberTypes[i] = this.environment.createMemberType(members[i], this); } this.tagBits &= ~TagBits.HasUnresolvedMemberTypes; - return this.memberTypes; + this.memberTypesSorted = true; + return this.memberTypes; } - if ((this.tagBits & TagBits.HasUnresolvedMemberTypes) == 0) - return this.memberTypes; - + if ((this.tagBits & TagBits.HasUnresolvedMemberTypes) == 0) { + return sortedMemberTypes(); + } for (int i = this.memberTypes.length; --i >= 0;) this.memberTypes[i] = (ReferenceBinding) resolveType(this.memberTypes[i], this.environment, false /* no raw conversion for now */); this.tagBits &= ~TagBits.HasUnresolvedMemberTypes; + return sortedMemberTypes(); +} + +private ReferenceBinding[] sortedMemberTypes() { + if (!this.memberTypesSorted) { + // lazily sort member types + int length = this.memberTypes.length; + if (length > 1) + unresolvedAwareSortMemberTypes(this.memberTypes, 0, length); + this.memberTypesSorted = true; + } return this.memberTypes; } + +private void unresolvedAwareSortMemberTypes(ReferenceBinding[] sortedMemberTypes, int left, int right) { + Arrays.sort(sortedMemberTypes, left, right, this::unresolvedAwareCompare); +} + +private int unresolvedAwareCompare(ReferenceBinding o1, ReferenceBinding o2) { + char[] n1 = getSourceName(o1); + char[] n2 = getSourceName(o2); + return ReferenceBinding.compare(n1, n2, n1.length, n2.length); +} + +private char[] getSourceName(ReferenceBinding memberType) { + if (memberType instanceof UnresolvedReferenceBinding) { + char[] name = memberType.sourceName; // source name is qualified with enclosing type name + int prefixLength = this.compoundName[this.compoundName.length - 1].length + 1; // enclosing$ + return CharOperation.subarray(name, prefixLength, name.length); + } + return memberType.sourceName; +} + // NOTE: the return type, arg & exception types of each method of a binary type are resolved when needed @Override public MethodBinding[] methods() { diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/CompilationUnitScope.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/CompilationUnitScope.java index c5f9f3700c..b42355e16d 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/CompilationUnitScope.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/CompilationUnitScope.java @@ -14,12 +14,17 @@ * Stephan Herrmann - Contribution for * Bug 429958 - [1.8][null] evaluate new DefaultLocation attribute of @NonNullByDefault * Bug 434570 - Generic type mismatch for parametrized class annotation attribute with inner class + * Sebastian Zarnekow - Contribution for + * Bug 544921 - [performance] Poor performance with large source files *******************************************************************************/ package org.eclipse.jdt.internal.compiler.lookup; import java.util.ArrayList; import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedHashSet; import java.util.Map; +import java.util.Set; import org.eclipse.jdt.core.compiler.CharOperation; import org.eclipse.jdt.internal.compiler.ast.*; @@ -41,10 +46,11 @@ public class CompilationUnitScope extends Scope { public SourceTypeBinding[] topLevelTypes; - private CompoundNameVector qualifiedReferences; - private SimpleNameVector simpleNameReferences; - private SimpleNameVector rootReferences; - private ObjectVector referencedTypes; + private SortedCompoundNameVector qualifiedReferences; + private SortedSimpleNameVector simpleNameReferences; + private SortedSimpleNameVector rootReferences; + private LinkedHashSet<ReferenceBindingSetWrapper> referencedTypes; + private Set<ReferenceBindingSetWrapper> referencedSuperTypesSet; private ObjectVector referencedSuperTypes; HashtableOfType constantPoolNameUsage; @@ -75,16 +81,18 @@ public CompilationUnitScope(CompilationUnitDeclaration unit, CompilerOptions com this.currentPackageName = unit.currentPackage == null ? CharOperation.NO_CHAR_CHAR : unit.currentPackage.tokens; if (compilerOptions.produceReferenceInfo) { - this.qualifiedReferences = new CompoundNameVector(); - this.simpleNameReferences = new SimpleNameVector(); - this.rootReferences = new SimpleNameVector(); - this.referencedTypes = new ObjectVector(); + this.qualifiedReferences = new SortedCompoundNameVector(); + this.simpleNameReferences = new SortedSimpleNameVector(); + this.rootReferences = new SortedSimpleNameVector(); + this.referencedTypes = new LinkedHashSet<>(); + this.referencedSuperTypesSet = new HashSet<>(); this.referencedSuperTypes = new ObjectVector(); } else { this.qualifiedReferences = null; // used to test if dependencies should be recorded this.simpleNameReferences = null; this.rootReferences = null; this.referencedTypes = null; + this.referencedSuperTypesSet = null; this.referencedSuperTypes = null; } // client still needs to assign #environment @@ -756,8 +764,7 @@ void recordQualifiedReference(char[][] qualifiedName) { int length = qualifiedName.length; if (length > 1) { recordRootReference(qualifiedName[0]); - while (!this.qualifiedReferences.contains(qualifiedName)) { - this.qualifiedReferences.add(qualifiedName); + while (this.qualifiedReferences.add(qualifiedName)) { if (length == 2) { recordSimpleReference(qualifiedName[0]); recordSimpleReference(qualifiedName[1]); @@ -786,20 +793,18 @@ void recordReference(ReferenceBinding type, char[] simpleName) { void recordRootReference(char[] simpleName) { if (this.rootReferences == null) return; // not recording dependencies - if (!this.rootReferences.contains(simpleName)) - this.rootReferences.add(simpleName); + this.rootReferences.add(simpleName); } void recordSimpleReference(char[] simpleName) { if (this.simpleNameReferences == null) return; // not recording dependencies - if (!this.simpleNameReferences.contains(simpleName)) - this.simpleNameReferences.add(simpleName); + this.simpleNameReferences.add(simpleName); } void recordSuperTypeReference(TypeBinding type) { if (this.referencedSuperTypes == null) return; // not recording dependencies ReferenceBinding actualType = typeToRecord(type); - if (actualType != null && !this.referencedSuperTypes.containsIdentical(actualType)) + if (actualType != null && this.referencedSuperTypesSet.add(new ReferenceBindingSetWrapper(actualType))) this.referencedSuperTypes.add(actualType); } public void recordTypeConversion(TypeBinding superType, TypeBinding subType) { @@ -809,8 +814,8 @@ void recordTypeReference(TypeBinding type) { if (this.referencedTypes == null) return; // not recording dependencies ReferenceBinding actualType = typeToRecord(type); - if (actualType != null && !this.referencedTypes.containsIdentical(actualType)) - this.referencedTypes.add(actualType); + if (actualType != null) + this.referencedTypes.add(new ReferenceBindingSetWrapper(actualType)); } void recordTypeReferences(TypeBinding[] types) { if (this.referencedTypes == null) return; // not recording dependencies @@ -820,8 +825,8 @@ void recordTypeReferences(TypeBinding[] types) { // No need to record supertypes of method arguments & thrown exceptions, just the compoundName // If a field/method is retrieved from such a type then a separate call does the job ReferenceBinding actualType = typeToRecord(types[i]); - if (actualType != null && !this.referencedTypes.containsIdentical(actualType)) - this.referencedTypes.add(actualType); + if (actualType != null) + this.referencedTypes.add(new ReferenceBindingSetWrapper(actualType)); } } Binding resolveSingleImport(ImportBinding importBinding, int mask) { @@ -847,8 +852,7 @@ public void storeDependencyInfo() { // cannot do early since the hierarchy may not be fully resolved for (int i = 0; i < this.referencedSuperTypes.size; i++) { // grows as more types are added ReferenceBinding type = (ReferenceBinding) this.referencedSuperTypes.elementAt(i); - if (!this.referencedTypes.containsIdentical(type)) - this.referencedTypes.add(type); + this.referencedTypes.add(new ReferenceBindingSetWrapper(type)); if (!type.isLocalType()) { ReferenceBinding enclosing = type.enclosingType(); @@ -864,8 +868,8 @@ public void storeDependencyInfo() { recordSuperTypeReference(interfaces[j]); } - for (int i = 0, l = this.referencedTypes.size; i < l; i++) { - ReferenceBinding type = (ReferenceBinding) this.referencedTypes.elementAt(i); + for (ReferenceBindingSetWrapper wrapper : this.referencedTypes) { + ReferenceBinding type = wrapper.referenceBinding; if (!type.isLocalType()) recordQualifiedReference(type.isMemberType() ? CharOperation.splitOn('.', type.readableName()) diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ParameterizedTypeBinding.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ParameterizedTypeBinding.java index 9c91e09abe..6fba803083 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ParameterizedTypeBinding.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ParameterizedTypeBinding.java @@ -1062,6 +1062,8 @@ public class ParameterizedTypeBinding extends ReferenceBinding implements Substi public ReferenceBinding[] memberTypes() { if (this.memberTypes == null) { try { + // the originalMemberTypes are already sorted by name so there + // is no need to sort again in our copy - names are not affected by type parameters ReferenceBinding[] originalMemberTypes = this.type.memberTypes(); int length = originalMemberTypes.length; ReferenceBinding[] parameterizedMemberTypes = new ReferenceBinding[length]; diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBinding.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBinding.java index 48f8cbeef5..241874b753 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBinding.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBinding.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2000, 2018 IBM Corporation and others. + * Copyright (c) 2000, 2019 IBM Corporation and others. * * This program and the accompanying materials * are made available under the terms of the Eclipse Public License 2.0 @@ -47,6 +47,8 @@ * bug 386692 - Missing "unused" warning on "autowired" fields * Pierre-Yves B. <pyvesdev@gmail.com> - Contribution for * bug 542520 - [JUnit 5] Warning The method xxx from the type X is never used locally is shown when using MethodSource + * Sebastian Zarnekow - Contributions for + * bug 544921 - [performance] Poor performance with large source files *******************************************************************************/ package org.eclipse.jdt.internal.compiler.lookup; @@ -105,9 +107,7 @@ abstract public class ReferenceBinding extends TypeBinding { }; private static final Comparator<MethodBinding> METHOD_COMPARATOR = new Comparator<MethodBinding>() { @Override - public int compare(MethodBinding o1, MethodBinding o2) { - MethodBinding m1 = o1; - MethodBinding m2 = o2; + public int compare(MethodBinding m1, MethodBinding m2) { char[] s1 = m1.selector; char[] s2 = m2.selector; int c = ReferenceBinding.compare(s1, s2, s1.length, s2.length); @@ -1049,14 +1049,42 @@ public char[] getFileName() { return this.fileName; } +/** + * Find the member type with the given simple typeName. Benefits from the fact that + * the array of {@link #memberTypes()} is sorted. + */ public ReferenceBinding getMemberType(char[] typeName) { ReferenceBinding[] memberTypes = memberTypes(); - for (int i = memberTypes.length; --i >= 0;) - if (CharOperation.equals(memberTypes[i].sourceName, typeName)) - return memberTypes[i]; + int memberTypeIndex = ReferenceBinding.binarySearch(typeName, memberTypes); + if (memberTypeIndex >= 0) { + return memberTypes[memberTypeIndex]; + } return null; } +private static int binarySearch(char[] name, ReferenceBinding[] sortedMemberTypes) { + if (sortedMemberTypes == null) + return -1; + int max = sortedMemberTypes.length; + if (max == 0) + return -1; + int left = 0, right = max - 1, nameLength = name.length; + int mid = 0; + char[] midName; + while (left <= right) { + mid = left + (right - left) /2; + int compare = compare(name, midName = sortedMemberTypes[mid].sourceName, nameLength, midName.length); + if (compare < 0) { + right = mid-1; + } else if (compare > 0) { + left = mid+1; + } else { + return mid; + } + } + return -1; +} + @Override public MethodBinding[] getMethods(char[] selector) { return Binding.NO_METHODS; @@ -1097,6 +1125,10 @@ public int hashCode() { : CharOperation.hashCode(this.compoundName[this.compoundName.length - 1]); } +final int identityHashCode() { + return super.hashCode(); +} + /** * Returns true if the two types have an incompatible common supertype, * e.g. List<String> and List<Integer> @@ -1673,6 +1705,9 @@ public final boolean isViewedAsDeprecated() { return false; } +/** + * Returns the member types of this type sorted by simple name. + */ public ReferenceBinding[] memberTypes() { return Binding.NO_MEMBER_TYPES; } diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBindingSetWrapper.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBindingSetWrapper.java new file mode 100644 index 0000000000..e411ed14ad --- /dev/null +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/ReferenceBindingSetWrapper.java @@ -0,0 +1,58 @@ +/******************************************************************************* + * Copyright (c) 2019 Simeon Andreev 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: + * Simeon Andreev - initial API and implementation + *******************************************************************************/ +package org.eclipse.jdt.internal.compiler.lookup; + +/** + * Defines a wrapper type for {@link ReferenceBinding} and provides proper hashCode() and equals() based on the wrapped + * {@link ReferenceBinding} object identity comparison. + * <p> + * Note: {@link ReferenceBinding} defines a hashCode() which is not consistent with the respective equals() + * implementation). + */ +final class ReferenceBindingSetWrapper { + + final ReferenceBinding referenceBinding; + private int hashCode; + + ReferenceBindingSetWrapper(ReferenceBinding referenceBinding) { + this.referenceBinding = referenceBinding; + this.hashCode = referenceBinding.identityHashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj == this) { + return true; + } + if (obj instanceof ReferenceBindingSetWrapper) { + ReferenceBindingSetWrapper other = (ReferenceBindingSetWrapper) obj; + return identityEqual(this.referenceBinding, other.referenceBinding); + } + return false; + } + + private static boolean identityEqual(Object o1, Object o2) { + return o1 == o2; + } + + @Override + public int hashCode() { + return this.hashCode; + } + + @Override + public String toString() { + return this.referenceBinding.toString(); + } +} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedCompoundNameVector.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedCompoundNameVector.java new file mode 100644 index 0000000000..f6d2a7d4b8 --- /dev/null +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedCompoundNameVector.java @@ -0,0 +1,63 @@ +/******************************************************************************* + * Copyright (c) 2019 Sebastian Zarnekow and others. + * + * This program and the accompanying materials + * are made available under the terms of the Eclipse Public License 2.0 + * which accompanies this distribution, and is available at + * https://www.eclipse.org/legal/epl-2.0/ + * + * SPDX-License-Identifier: EPL-2.0 + * + * Contributors: + * Sebastian Zarnekow - initial API and implementation + *******************************************************************************/ +package org.eclipse.jdt.internal.compiler.lookup; + +import java.util.Arrays; + +import org.eclipse.jdt.core.compiler.CharOperation; +import org.eclipse.jdt.internal.compiler.util.SortedCharArrays; + +/** + * Sorted and simplified version of previously existed CompoundNameVector + */ +final class SortedCompoundNameVector { + + static int INITIAL_SIZE = 10; + + int size; + char[][][] elements; + + public SortedCompoundNameVector() { + this.size = 0; + this.elements = new char[INITIAL_SIZE][][]; + } + + public boolean add(char[][] newElement) { + int idx = Arrays.binarySearch(this.elements, 0, this.size, newElement, SortedCharArrays.CHAR_CHAR_ARR_COMPARATOR); + if (idx < 0) { + this.elements = SortedCharArrays.insertIntoArray( + this.elements, + this.size < this.elements.length ? this.elements : new char[this.elements.length * 2][][], + newElement, + -(idx + 1), + this.size++); + return true; + } + return false; + } + + public char[][] elementAt(int index) { + return this.elements[index]; + } + + @Override + public String toString() { + StringBuilder buffer = new StringBuilder(); + for (int i = 0; i < this.size; i++) { + buffer.append(CharOperation.toString(this.elements[i])).append("\n"); //$NON-NLS-1$ + } + return buffer.toString(); + } + +} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedSimpleNameVector.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedSimpleNameVector.java new file mode 100644 index 0000000000..2cd0179488 --- /dev/null +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SortedSimpleNameVector.java @@ -0,0 +1,62 @@ +/******************************************************************************* + * Copyright (c) 2019 Sebastian Zarnekow and others. + * + * This program and the accompanying materials + * are made available under the terms of the Eclipse Public License 2.0 + * which accompanies this distribution, and is available at + * https://www.eclipse.org/legal/epl-2.0/ + * + * SPDX-License-Identifier: EPL-2.0 + * + * Contributors: + * Sebastian Zarnekow - initial API and implementation + *******************************************************************************/ +package org.eclipse.jdt.internal.compiler.lookup; + +import java.util.Arrays; + +import org.eclipse.jdt.internal.compiler.util.SortedCharArrays; + +/** + * Sorted and simplified version of previously existed SimpleNameVector + */ +final class SortedSimpleNameVector { + + static int INITIAL_SIZE = 10; + + int size; + char[][] elements; + + public SortedSimpleNameVector() { + this.size = 0; + this.elements = new char[INITIAL_SIZE][]; + } + + public boolean add(char[] newElement) { + int idx = Arrays.binarySearch(this.elements, 0, this.size, newElement, SortedCharArrays.CHAR_ARR_COMPARATOR); + if (idx < 0) { + this.elements = SortedCharArrays.insertIntoArray( + this.elements, + this.size < this.elements.length ? this.elements : new char[this.elements.length * 2][], + newElement, + -(idx + 1), + this.size++); + return true; + } + return false; + } + + public char[] elementAt(int index) { + return this.elements[index]; + } + + @Override + public String toString() { + StringBuilder buffer = new StringBuilder(); + for (int i = 0; i < this.size; i++) { + buffer.append(this.elements[i]).append("\n"); //$NON-NLS-1$ + } + return buffer.toString(); + } + +} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SourceTypeBinding.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SourceTypeBinding.java index d2c525fb07..5158fb90ab 100644 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SourceTypeBinding.java +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/lookup/SourceTypeBinding.java @@ -48,10 +48,14 @@ * bug 415269 - NonNullByDefault is not always inherited to nested classes * Andy Clement (GoPivotal, Inc) aclement@gopivotal.com - Contributions for * Bug 405104 - [1.8][compiler][codegen] Implement support for serializeable lambdas + * Sebastian Zarnekow - Contributions for + * bug 544921 - [performance] Poor performance with large source files *******************************************************************************/ package org.eclipse.jdt.internal.compiler.lookup; +import java.util.Arrays; import java.util.Collection; +import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; @@ -112,6 +116,7 @@ public class SourceTypeBinding extends ReferenceBinding { private SimpleLookupTable storedAnnotations = null; // keys are this ReferenceBinding & its fields and methods, value is an AnnotationHolder public int defaultNullness; + boolean memberTypesSorted = false; private int nullnessDefaultInitialized = 0; // 0: nothing; 1: type; 2: package private ReferenceBinding containerAnnotationType = null; @@ -1514,7 +1519,9 @@ public boolean canBeSeenBy(Scope sco) { public ReferenceBinding[] memberTypes() { if (!isPrototype()) { if ((this.tagBits & TagBits.HasUnresolvedMemberTypes) == 0) - return this.memberTypes; + return sortedMemberTypes(); + // members obtained from the prototype are already sorted so it is safe + // to set the sorted flag here immediately. ReferenceBinding [] members = this.memberTypes = this.prototype.memberTypes(); int membersLength = members == null ? 0 : members.length; this.memberTypes = new ReferenceBinding[membersLength]; @@ -1522,10 +1529,35 @@ public ReferenceBinding[] memberTypes() { this.memberTypes[i] = this.environment.createMemberType(members[i], this); } this.tagBits &= ~TagBits.HasUnresolvedMemberTypes; + this.memberTypesSorted = true; + } + return sortedMemberTypes(); +} + +private ReferenceBinding[] sortedMemberTypes() { + if (!this.memberTypesSorted) { + // lazily sort member types + int length = this.memberTypes.length; + if (length > 1) + sortMemberTypes(this.memberTypes, 0, length); + this.memberTypesSorted = true; } return this.memberTypes; } +/** + * Sort the member types using a quicksort + */ +private static void sortMemberTypes(ReferenceBinding[] sortedMemberTypes, int left, int right) { + Arrays.sort(sortedMemberTypes, left, right, BASIC_MEMBER_TYPES_COMPARATOR); +} + +private static final Comparator<ReferenceBinding> BASIC_MEMBER_TYPES_COMPARATOR = (ReferenceBinding o1, ReferenceBinding o2) -> { + char[] n1 = o1.sourceName; + char[] n2 = o2.sourceName; + return ReferenceBinding.compare(n1, n2, n1.length, n2.length); +}; + @Override public boolean hasMemberTypes() { if (!isPrototype()) @@ -2301,6 +2333,7 @@ public ReferenceBinding [] setMemberTypes(ReferenceBinding[] memberTypes) { annotatedType.memberTypes(); // recompute. } } + sortedMemberTypes(); return this.memberTypes; } diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/CompoundNameVector.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/CompoundNameVector.java deleted file mode 100644 index ea9f98863b..0000000000 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/CompoundNameVector.java +++ /dev/null @@ -1,75 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2000, 2009 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.internal.compiler.util; - -import org.eclipse.jdt.core.compiler.CharOperation; - -public final class CompoundNameVector { - static int INITIAL_SIZE = 10; - - public int size; - int maxSize; - char[][][] elements; -public CompoundNameVector() { - this.maxSize = INITIAL_SIZE; - this.size = 0; - this.elements = new char[this.maxSize][][]; -} -public void add(char[][] newElement) { - if (this.size == this.maxSize) // knows that size starts <= maxSize - System.arraycopy(this.elements, 0, (this.elements = new char[this.maxSize *= 2][][]), 0, this.size); - this.elements[this.size++] = newElement; -} -public void addAll(char[][][] newElements) { - if (this.size + newElements.length >= this.maxSize) { - this.maxSize = this.size + newElements.length; // assume no more elements will be added - System.arraycopy(this.elements, 0, (this.elements = new char[this.maxSize][][]), 0, this.size); - } - System.arraycopy(newElements, 0, this.elements, this.size, newElements.length); - this.size += newElements.length; -} -public boolean contains(char[][] element) { - for (int i = this.size; --i >= 0;) - if (CharOperation.equals(element, this.elements[i])) - return true; - return false; -} -public char[][] elementAt(int index) { - return this.elements[index]; -} -public char[][] remove(char[][] element) { - // assumes only one occurrence of the element exists - for (int i = this.size; --i >= 0;) - if (element == this.elements[i]) { - // shift the remaining elements down one spot - System.arraycopy(this.elements, i + 1, this.elements, i, --this.size - i); - this.elements[this.size] = null; - return element; - } - return null; -} -public void removeAll() { - for (int i = this.size; --i >= 0;) - this.elements[i] = null; - this.size = 0; -} -@Override -public String toString() { - StringBuffer buffer = new StringBuffer(); - for (int i = 0; i < this.size; i++) { - buffer.append(CharOperation.toString(this.elements[i])).append("\n"); //$NON-NLS-1$ - } - return buffer.toString(); -} -} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SimpleNameVector.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SimpleNameVector.java deleted file mode 100644 index 1d35b1205b..0000000000 --- a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SimpleNameVector.java +++ /dev/null @@ -1,100 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2000, 2009 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.internal.compiler.util; - -import org.eclipse.jdt.core.compiler.CharOperation; - -public final class SimpleNameVector { - - static int INITIAL_SIZE = 10; - - public int size; - int maxSize; - char[][] elements; - - public SimpleNameVector() { - - this.maxSize = INITIAL_SIZE; - this.size = 0; - this.elements = new char[this.maxSize][]; - } - - public void add(char[] newElement) { - - if (this.size == this.maxSize) // knows that size starts <= maxSize - System.arraycopy(this.elements, 0, (this.elements = new char[this.maxSize *= 2][]), 0, this.size); - this.elements[this.size++] = newElement; - } - - public void addAll(char[][] newElements) { - - if (this.size + newElements.length >= this.maxSize) { - this.maxSize = this.size + newElements.length; // assume no more elements will be added - System.arraycopy(this.elements, 0, (this.elements = new char[this.maxSize][]), 0, this.size); - } - System.arraycopy(newElements, 0, this.elements, this.size, newElements.length); - this.size += newElements.length; - } - - public void copyInto(Object[] targetArray){ - - System.arraycopy(this.elements, 0, targetArray, 0, this.size); - } - - public boolean contains(char[] element) { - - for (int i = this.size; --i >= 0;) - if (CharOperation.equals(element, this.elements[i])) - return true; - return false; - } - - public char[] elementAt(int index) { - return this.elements[index]; - } - - public char[] remove(char[] element) { - - // assumes only one occurrence of the element exists - for (int i = this.size; --i >= 0;) - if (element == this.elements[i]) { - // shift the remaining elements down one spot - System.arraycopy(this.elements, i + 1, this.elements, i, --this.size - i); - this.elements[this.size] = null; - return element; - } - return null; - } - - public void removeAll() { - - for (int i = this.size; --i >= 0;) - this.elements[i] = null; - this.size = 0; - } - - public int size(){ - - return this.size; - } - - @Override - public String toString() { - StringBuffer buffer = new StringBuffer(); - for (int i = 0; i < this.size; i++) { - buffer.append(this.elements[i]).append("\n"); //$NON-NLS-1$ - } - return buffer.toString(); - } -} diff --git a/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SortedCharArrays.java b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SortedCharArrays.java new file mode 100644 index 0000000000..0178dc4cb3 --- /dev/null +++ b/org.eclipse.jdt.core/compiler/org/eclipse/jdt/internal/compiler/util/SortedCharArrays.java @@ -0,0 +1,88 @@ +/******************************************************************************* + * Copyright (c) 2019 Sebastian Zarnekow and others. + * + * This program and the accompanying materials + * are made available under the terms of the Eclipse Public License 2.0 + * which accompanies this distribution, and is available at + * https://www.eclipse.org/legal/epl-2.0/ + * + * SPDX-License-Identifier: EPL-2.0 + * + * Contributors: + * Sebastian Zarnekow - initial API and implementation + *******************************************************************************/ +package org.eclipse.jdt.internal.compiler.util; + +import java.util.Comparator; + +/** + * @since 3.18 + */ +public class SortedCharArrays { + + // there may be better thresholds available for different scenarios + public static final int BINARY_SEARCH_THRESHOLD = 16; + + /** + * @param target same as source array or new array with higher capacity + * @param idx position for new element + * @param currentCount the current number of elements in the source array + * @return given target array + */ + public static <T> T[] insertIntoArray(T[] src, T[] target, T entry, int idx, int currentCount) { + if (src != target) { + // src and target point to different instances + // -> we need to copy the elements into the new result + System.arraycopy(src, 0, target, 0, idx); + System.arraycopy(src, idx, target, idx+1, currentCount - idx); + } else if (idx != currentCount) { + // src and target point to the same instance + // -> we need to shift the elements one slot to the right + System.arraycopy(src, idx, target, idx+1, currentCount - idx); + } + target[idx] = entry; + return target; + } + + /** + * 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) + */ + public 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; + } + public static final Comparator<char[]> CHAR_ARR_COMPARATOR = SortedCharArrays::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[])}. + */ + public 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; + } + public static final Comparator<char[][]> CHAR_CHAR_ARR_COMPARATOR = SortedCharArrays::compareCharCharArray; +} 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 0b47eda2bc..01cf9c8f79 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 @@ -24,6 +24,7 @@ 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; +import org.eclipse.jdt.internal.compiler.util.SortedCharArrays; public class ReferenceCollection { @@ -58,14 +59,13 @@ public void addDependencies(String[] typeNameDependencies) { qualifiedTypeName = internSimpleNames(qualifiedTypeName, false, false); qualifiedTypeName = internedNames.add(qualifiedTypeName); int idx; - while ((idx = Arrays.binarySearch(this.qualifiedNameReferences, qualifiedTypeName, CHAR_CHAR_ARR_COMPARATOR)) < 0) { + while ((idx = Arrays.binarySearch(this.qualifiedNameReferences, qualifiedTypeName, SortedCharArrays.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); + this.qualifiedNameReferences = SortedCharArrays.insertIntoArray(this.qualifiedNameReferences, new char[length + 1][][], qualifiedTypeName, idx, this.qualifiedNameReferences.length); qualifiedTypeName = CharOperation.subarray(qualifiedTypeName, 0, qualifiedTypeName.length - 1); char[][][] temp = internQualifiedNames(new char[][][] {qualifiedTypeName}, false); @@ -78,7 +78,7 @@ public void addDependencies(String[] typeNameDependencies) { } public boolean includes(char[] simpleName) { - boolean result = sortedArrayContains(this.simpleNameReferences, simpleName, CHAR_ARR_COMPARATOR); + boolean result = sortedArrayContains(this.simpleNameReferences, simpleName, SortedCharArrays.CHAR_ARR_COMPARATOR); if (REFERENCE_COLLECTION_DEBUG) { assertIncludes(result, simpleName); } @@ -86,7 +86,7 @@ public boolean includes(char[] simpleName) { } public boolean includes(char[][] qualifiedName) { - boolean result = sortedArrayContains(this.qualifiedNameReferences, qualifiedName, CHAR_CHAR_ARR_COMPARATOR); + boolean result = sortedArrayContains(this.qualifiedNameReferences, qualifiedName, SortedCharArrays.CHAR_CHAR_ARR_COMPARATOR); if (REFERENCE_COLLECTION_DEBUG) { assertIncludes(result, qualifiedName); } @@ -139,7 +139,7 @@ private boolean doIncludes(char[][][] qualifiedNames, char[][] simpleNames, char } public boolean insideRoot(char[] rootName) { - boolean result = sortedArrayContains(this.rootReferences, rootName, CHAR_ARR_COMPARATOR); + boolean result = sortedArrayContains(this.rootReferences, rootName, SortedCharArrays.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$ @@ -152,7 +152,7 @@ public boolean insideRoot(char[] rootName) { private static <T> boolean sortedArrayContains(T[] array, T element, Comparator<? super T> comparator) { int l = array.length; - if (l < BINARY_SEARCH_THRESHOLD) { + if (l < SortedCharArrays.BINARY_SEARCH_THRESHOLD) { for (int i = 0; i < l; i++) if (element == array[i]) return true; return false; @@ -161,11 +161,11 @@ private static <T> boolean sortedArrayContains(T[] array, T element, Comparator< } private boolean includesSimpleName(char[][] simpleNames) { - return intersects(simpleNames, this.simpleNameReferences, CHAR_ARR_COMPARATOR); + return intersects(simpleNames, this.simpleNameReferences, SortedCharArrays.CHAR_ARR_COMPARATOR); } private boolean includesQualifiedName(char[][][] qualifiedNames) { - if (intersects(qualifiedNames, this.qualifiedNameReferences, CHAR_CHAR_ARR_COMPARATOR)) { + if (intersects(qualifiedNames, this.qualifiedNameReferences, SortedCharArrays.CHAR_CHAR_ARR_COMPARATOR)) { return true; } char[][] maybeSimpleName; @@ -178,11 +178,9 @@ private boolean includesQualifiedName(char[][][] qualifiedNames) { } private boolean includesRootName(char[][] rootNames) { - return intersects(rootNames, this.rootReferences, CHAR_ARR_COMPARATOR); + return intersects(rootNames, this.rootReferences, SortedCharArrays.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. @@ -205,7 +203,7 @@ private static <T> boolean intersects(T[] firstSortedArr, T[] secondSortedArr, C * attempt a binary search for the second element to possibly skip a few elements. */ i++; - if (l - i > BINARY_SEARCH_THRESHOLD) { + if (l - i > SortedCharArrays.BINARY_SEARCH_THRESHOLD) { i = Arrays.binarySearch(firstSortedArr, i, l, secondElement, comparator); if (i >= 0) { return true; @@ -217,7 +215,7 @@ private static <T> boolean intersects(T[] firstSortedArr, T[] secondSortedArr, C * the inverse logic is applied here */ j++; - if (k - j > BINARY_SEARCH_THRESHOLD) { + if (k - j > SortedCharArrays.BINARY_SEARCH_THRESHOLD) { j = Arrays.binarySearch(secondSortedArr, j, k, firstElement, comparator); if (j >= 0) { return true; @@ -229,19 +227,11 @@ private static <T> boolean intersects(T[] firstSortedArr, T[] secondSortedArr, C 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); + int idx = Arrays.binarySearch(sortedArray, entry, SortedCharArrays.CHAR_ARR_COMPARATOR); if (idx < 0) { idx = -(idx + 1); - char[][] result = new char[sortedArray.length + 1][]; - insertIntoArray(sortedArray, result, entry, idx); + char[][] result = SortedCharArrays.insertIntoArray(sortedArray, new char[sortedArray.length + 1][], entry, idx, sortedArray.length); return result; } return sortedArray; @@ -367,7 +357,7 @@ static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWe if (keepWellKnown) { // This code is duplicated to encourage the JIT to inline more stuff if (doSort && isSorted) { - if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) { + if (prev != null && SortedCharArrays.compareCharCharArray(prev, qualifiedName) > 0) { isSorted = false; } prev = qualifiedName; @@ -385,7 +375,7 @@ static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWe qualifiedName = internSimpleNames(qualifiedName, false, false); // This code is duplicated to encourage the JIT to inline more stuff if (doSort && isSorted) { - if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) { + if (prev != null && SortedCharArrays.compareCharCharArray(prev, qualifiedName) > 0) { isSorted = false; } prev = qualifiedName; @@ -397,54 +387,12 @@ static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWe System.arraycopy(keepers, 0, keepers = new char[index][][], 0, index); } if (doSort && !isSorted) { - Arrays.sort(keepers, CHAR_CHAR_ARR_COMPARATOR); + Arrays.sort(keepers, SortedCharArrays.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) { @@ -512,7 +460,7 @@ static char[][] internSimpleNames(char[][] simpleNames, boolean 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) { + if (prev != null && SortedCharArrays.compareCharArray(prev, name) > 0) { isSorted = false; } prev = name; @@ -529,7 +477,7 @@ static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown, 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) { + if (prev != null && SortedCharArrays.compareCharArray(prev, name) > 0) { isSorted = false; } prev = name; @@ -540,7 +488,7 @@ static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown, System.arraycopy(keepers, 0, keepers = new char[index][], 0, index); } if (doSort && !isSorted) { - Arrays.sort(keepers, CHAR_ARR_COMPARATOR); + Arrays.sort(keepers, SortedCharArrays.CHAR_ARR_COMPARATOR); } return keepers; } |