Bug 545491 - revert ReferenceCollection fixS4_12_0_M1I20190412-1800I20190412-0520I20190411-0625I20190410-1800

The fix caused build state to be persisted or restored in a wrong way,
so that ReferenceCollection was not properly read form a previous state,
so that types referenced by that collection were not found by Java
search anymore till next build of the project.

This change also decrements State.VERSION counter to trigger a rebuild
and a new state creation.

Tests aren't reverted, only those depending on the sorted state are
commented out.

Change-Id: I945dd6ef42eacfe34f06361b41697c7b8e7b6725
Signed-off-by: Andrey Loskutov <loskutov@gmx.de>

3 files changed, 100 insertions, 414 deletions

diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
index 481fe69afd..2cfbb371fb 100644
--- a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
@@ -77,7 +77,8 @@ public class ReferenceCollectionTest extends BuilderTests {
 		}
 	}
 
-	public void testInternQualifiedNamesSorts_01() {
+	// Disabled due bug 545491 comment 15
+	public void XtestInternQualifiedNamesSorts_01() {
 		char[][][] qualifiedNames = new char[][][] {
 			CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
 			CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -96,7 +97,8 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internQualifiedNames));
 	}
 
-	public void testInternQualifiedNamesSorts_02() {
+	// Disabled due bug 545491 comment 15
+	public void XtestInternQualifiedNamesSorts_02() {
 		char[][][] qualifiedNames = new char[][][] {
 			CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
 			CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -122,7 +124,8 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internQualifiedNames));
 	}
 
-	public void testInternSimpleNamesSorts_01() {
+	// Disabled due bug 545491 comment 15
+	public void XtestInternSimpleNamesSorts_01() {
 		char[][] simpleNames = new char[][] {
 			"Throwable".toCharArray(),
 			"aaa".toCharArray(),
@@ -139,7 +142,8 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internSimpleNames));
 	}
 
-	public void testInternSimpleNamesSorts_02() {
+	// Disabled due bug 545491 comment 15
+	public void XtestInternSimpleNamesSorts_02() {
 		char[][] simpleNames = new char[][] {
 			"aaa".toCharArray(),
 			"bbb".toCharArray(),
@@ -287,7 +291,8 @@ public class ReferenceCollectionTest extends BuilderTests {
 		assertFalse(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
 	}
 
-	public void testAddDependencies() {
+	// Disabled due bug 545491 comment 15
+	public void XtestAddDependencies() {
 		TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
 
 		String[] array = new String[] {"a.b.c.D"};
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 12b2bc54e4..8b5e24646e 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,20 +14,14 @@
  *******************************************************************************/
 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 {
 
-// 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[][][] qualifiedNameReferences; // contains no simple names as in just 'a' which is kept in simpleNameReferences instead
 char[][] simpleNameReferences;
 char[][] rootReferences;
 
@@ -37,64 +31,51 @@ 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
-	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];
+	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];
 			}
+			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) {
-	boolean result = sortedArrayContains(this.simpleNameReferences, simpleName, CHAR_ARR_COMPARATOR);
-	if (REFERENCE_COLLECTION_DEBUG) {
-		assertIncludes(result, simpleName);
-	}
-	return result;
+	for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
+		if (simpleName == this.simpleNameReferences[i]) return true;
+	return false;
 }
 
 public boolean includes(char[][] qualifiedName) {
-	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$
+	for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
+		if (qualifiedName == this.qualifiedNameReferences[i]) return true;
+	return false;
 }
 
 /**
@@ -105,158 +86,83 @@ public boolean includes(char[][][] qualifiedNames, char[][] simpleNames) {
 }
 
 public boolean includes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
-	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 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) {
-		if (!includesRootName(rootNames))
+		boolean foundRoot = false;
+		for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
+			foundRoot = insideRoot(rootNames[i]);
+		if (!foundRoot)
 			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) {
-			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;
-}
-
-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) {
+			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;
 				}
-				i = -(i + 1);
 			}
 		} 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) {
+			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;
 				}
-				j = -(j + 1);
 			}
 		}
+		return false;
 	}
-	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;
+	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;
+					}
+				}
+				return false;
+			}
+		}
+	} 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;
+					}
+				}
+				return false;
+			}
+		}
 	}
-	return sortedArray;
+	return false;
 }
 
-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;
-		}
-	}
+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;
 }
 
+
 // 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
 // having WellKnownQualifiedNames & WellKnownSimpleNames, saves every type 40 bytes
@@ -326,25 +232,13 @@ 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;
@@ -354,13 +248,6 @@ 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;
@@ -371,69 +258,17 @@ 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, 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;
-		}
+		qualifiedName = internSimpleNames(qualifiedName, false);
 		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) {
@@ -466,26 +301,13 @@ 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];
@@ -495,16 +317,8 @@ private static char[][] internSimpleNames(char[][] simpleNames, boolean removeWe
 			if (sLength > wellKnownName.length)
 				break; // all remaining well known names are shorter
 			if (CharOperation.equals(name, wellKnownName)) {
-				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;
-					}
-				}
+				if (!removeWellKnown)
+					keepers[index++] = WellKnownSimpleNames[j];
 				continue next;
 			}
 		}
@@ -514,144 +328,11 @@ private static char[][] internSimpleNames(char[][] simpleNames, boolean removeWe
 		// InternedSimpleNames[29] is for size 29
 		NameSet internedNames = InternedSimpleNames[sLength < MaxSimpleNames ? sLength : 0];
 		keepers[index++] = internedNames.add(name);
-		// This code is duplicated to encourage the JIT to inline more stuff
-		if (doSort && isSorted) {
-			if (prev != null && compareCharArray(prev, name) > 0) {
-				isSorted = false;
-			}
-			prev = name;
-		}
 	}
 	if (length > index) {
 		if (index == 0) return EmptySimpleNames;
 		System.arraycopy(keepers, 0, keepers = new char[index][], 0, index);
 	}
-	if (doSort && !isSorted) {
-		Arrays.sort(keepers, CHAR_ARR_COMPARATOR);
-	}
 	return keepers;
 }
-
-// DEBUG code below
-public static boolean REFERENCE_COLLECTION_DEBUG = false;
-
-private void assertIncludes(boolean expectation, char[] simpleName) {
-	if (expectation != debugIncludes(simpleName)) {
-		String message = "Mismatch: " + String.valueOf(simpleName) + (expectation ? " should not " : " should ") + " be included in "  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
-				+ Arrays.asList(CharOperation.toStrings(this.simpleNameReferences));
-		throw new IllegalStateException(message);
-	}
-}
-
-private void assertIncludes(boolean expectation, char[][] qualifiedName) {
-	if (expectation != debugIncludes(qualifiedName)) {
-		String message = "Mismatch: " + CharOperation.toString(qualifiedName) + (expectation ? " should not " : " should ") + " be included in "  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
-				+ qualifiedNamesToString(this.qualifiedNameReferences);
-		throw new IllegalStateException(message);
-	}
-}
-
-private void assertIncludes(boolean expectation, char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
-	if (expectation != debugIncludes(qualifiedNames, simpleNames, rootNames)) {
-		String message = String.format("Mismatched includes(..): ReferenceCollection([%s], %s, %s).includes([%s], %s, %s)", //$NON-NLS-1$
-				qualifiedNamesToString(this.qualifiedNameReferences),
-				Arrays.toString(CharOperation.toStrings(this.simpleNameReferences)),
-				Arrays.toString(CharOperation.toStrings(this.rootReferences)),
-				qualifiedNamesToString(qualifiedNames),
-				Arrays.toString(CharOperation.toStrings(simpleNames)),
-				Arrays.toString(CharOperation.toStrings(rootNames))
-		);
-		throw new IllegalStateException(message);
-	}
-}
-
-private boolean debugIncludes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
-	// if either collection of names is null, it means it contained a well known name so we know it already has a match
-	if (rootNames != null) {
-		boolean foundRoot = false;
-		for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
-			foundRoot = debugInsideRoot(rootNames[i]);
-		if (!foundRoot)
-			return false;
-	}
-	if (simpleNames == null || qualifiedNames == null) {
-		if (simpleNames == null && qualifiedNames == null) {
-			if (JavaBuilder.DEBUG)
-				System.out.println("Found well known match"); //$NON-NLS-1$
-			return true;
-		} else if (qualifiedNames == null) {
-			for (int i = 0, l = simpleNames.length; i < l; i++) {
-				if (debugIncludes(simpleNames[i])) {
-					if (JavaBuilder.DEBUG)
-						System.out.println("Found match in well known package to " + new String(simpleNames[i])); //$NON-NLS-1$
-					return true;
-				}
-			}
-		} else {
-			for (int i = 0, l = qualifiedNames.length; i < l; i++) {
-				char[][] qualifiedName = qualifiedNames[i];
-				if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
-					if (JavaBuilder.DEBUG)
-						System.out.println("Found well known match in " + CharOperation.toString(qualifiedName)); //$NON-NLS-1$
-					return true;
-				}
-			}
-		}
-		return false;
-	}
-
-	int sLength = simpleNames.length;
-	int qLength = qualifiedNames.length;
-	if (sLength <= qLength) {
-		for (int i = 0; i < sLength; i++) {
-			if (debugIncludes(simpleNames[i])) {
-				for (int j = 0; j < qLength; j++) {
-					char[][] qualifiedName = qualifiedNames[j];
-					if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
-						if (JavaBuilder.DEBUG)
-							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
-								+ " to " + new String(simpleNames[i])); //$NON-NLS-1$
-						return true;
-					}
-				}
-				return false;
-			}
-		}
-	} else {
-		for (int i = 0; i < qLength; i++) {
-			char[][] qualifiedName = qualifiedNames[i];
-			if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
-				for (int j = 0; j < sLength; j++) {
-					if (debugIncludes(simpleNames[j])) {
-						if (JavaBuilder.DEBUG)
-							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
-								+ " to " + new String(simpleNames[j])); //$NON-NLS-1$
-						return true;
-					}
-				}
-				return false;
-			}
-		}
-	}
-	return false;
-}
-
-private boolean debugInsideRoot(char[] rootName) {
-	for (int i = 0, l = this.rootReferences.length; i < l; i++)
-		if (rootName == this.rootReferences[i]) return true;
-	return false;
-}
-
-private boolean debugIncludes(char[] simpleName) {
-	for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
-		if (simpleName == this.simpleNameReferences[i]) return true;
-	return false;
-}
-
-private boolean debugIncludes(char[][] qualifiedName) {
-	for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
-		if (qualifiedName == this.qualifiedNameReferences[i]) return true;
-	return false;
-}
-
 }
diff --git a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
index 65a640f66e..a57cc107e6 100644
--- a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
+++ b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
@@ -56,7 +56,7 @@ private long previousStructuralBuildTime;
 private StringSet structurallyChangedTypes;
 public static int MaxStructurallyChangedTypes = 100; // keep track of ? structurally changed types, otherwise consider all to be changed
 
-public static final byte VERSION = 0x0023;
+public static final byte VERSION = 0x0022;
 
 static final byte SOURCE_FOLDER = 1;
 static final byte BINARY_FOLDER = 2;