8230162: ScopeImpl.remove() has O(N) performance
Reviewed-by: jlahoda
Contributed-by: bcorso@google.com
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java Tue Oct 08 15:48:36 2019 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Scope.java Tue Oct 08 15:43:38 2019 +0200
@@ -389,7 +389,7 @@
Entry e = table[hash];
Assert.check(e == elems, elems.sym);
table[hash] = elems.shadowed;
- elems = elems.sibling;
+ elems = elems.nextSibling;
}
Assert.check(next.shared > 0);
next.shared--;
@@ -466,15 +466,15 @@
}
// remove e from elems and sibling list
- te = elems;
- if (te == e)
- elems = e.sibling;
- else while (true) {
- if (te.sibling == e) {
- te.sibling = e.sibling;
- break;
- }
- te = te.sibling;
+ if (elems == e) {
+ elems = e.nextSibling;
+ if (elems != null)
+ elems.prevSibling = null;
+ } else {
+ Assert.check(e.prevSibling != null, e.sym);
+ e.prevSibling.nextSibling = e.nextSibling;
+ if (e.nextSibling != null)
+ e.nextSibling.prevSibling = e.prevSibling;
}
removeCount++;
@@ -597,7 +597,7 @@
private Symbol doNext() {
Symbol sym = (currEntry == null ? null : currEntry.sym);
if (currEntry != null) {
- currEntry = currEntry.sibling;
+ currEntry = currEntry.nextSibling;
}
update();
return sym;
@@ -617,7 +617,7 @@
void skipToNextMatchingEntry() {
while (currEntry != null && sf != null && !sf.accepts(currEntry.sym)) {
- currEntry = currEntry.sibling;
+ currEntry = currEntry.nextSibling;
}
}
};
@@ -677,7 +677,7 @@
result.append("Scope[");
for (ScopeImpl s = this; s != null ; s = s.next) {
if (s != this) result.append(" | ");
- for (Entry e = s.elems; e != null; e = e.sibling) {
+ for (Entry e = s.elems; e != null; e = e.nextSibling) {
if (e != s.elems) result.append(", ");
result.append(e.sym);
}
@@ -702,18 +702,24 @@
/** Next entry in same scope.
*/
- public Entry sibling;
+ public Entry nextSibling;
+
+ /** Prev entry in same scope.
+ */
+ public Entry prevSibling;
/** The entry's scope.
* scope == null iff this == sentinel
*/
public ScopeImpl scope;
- public Entry(Symbol sym, Entry shadowed, Entry sibling, ScopeImpl scope) {
+ public Entry(Symbol sym, Entry shadowed, Entry nextSibling, ScopeImpl scope) {
this.sym = sym;
this.shadowed = shadowed;
- this.sibling = sibling;
+ this.nextSibling = nextSibling;
this.scope = scope;
+ if (nextSibling != null)
+ nextSibling.prevSibling = this;
}
/** Return next entry with the same name as this entry, proceeding
--- a/test/langtools/tools/javac/lib/DPrinter.java Tue Oct 08 15:48:36 2019 +0200
+++ b/test/langtools/tools/javac/lib/DPrinter.java Tue Oct 08 15:43:38 2019 +0200
@@ -437,7 +437,8 @@
Scope scope = (Scope) getField(e, e.getClass(), "scope");
return "(" + sym.name + ":" + sym
+ ",shdw:" + entryToString(callMethod(e, e.getClass(), "next"), table, true)
- + ",sibl:" + entryToString(getField(e, e.getClass(), "sibling"), table, true)
+ + ",nextSibling:" + entryToString(getField(e, e.getClass(), "nextSibling"), table, true)
+ + ",prevSibling:" + entryToString(getField(e, e.getClass(), "prevSibling"), table, true)
+ ((sym.owner != scope.owner)
? (",BOGUS[" + sym.owner + "," + scope.owner + "]")
: "")
--- a/test/langtools/tools/javac/scope/RemoveSymbolUnitTest.java Tue Oct 08 15:48:36 2019 +0200
+++ b/test/langtools/tools/javac/scope/RemoveSymbolUnitTest.java Tue Oct 08 15:43:38 2019 +0200
@@ -33,8 +33,13 @@
import com.sun.tools.javac.util.*;
import com.sun.tools.javac.code.*;
import com.sun.tools.javac.code.Scope.*;
+import com.sun.tools.javac.code.Symbol;
import com.sun.tools.javac.code.Symbol.*;
import com.sun.tools.javac.file.JavacFileManager;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
public class RemoveSymbolUnitTest {
@@ -63,36 +68,66 @@
// Try enter and remove in different shuffled combinations.
// working with fresh scope each time.
- WriteableScope cs = WriteableScope.create(clazz);
- cs.enter(v);
- cs.enter(m);
+ WriteableScope cs = writeableScope(clazz, v, m);
cs.remove(v);
Symbol s = cs.findFirst(hasNext);
if (s != m)
throw new AssertionError("Wrong symbol");
- cs = WriteableScope.create(clazz);
- cs.enter(m);
- cs.enter(v);
+ cs = writeableScope(clazz, m, v);
cs.remove(v);
s = cs.findFirst(hasNext);
if (s != m)
throw new AssertionError("Wrong symbol");
- cs = WriteableScope.create(clazz);
- cs.enter(v);
- cs.enter(m);
+ cs = writeableScope(clazz, v, m);
cs.remove(m);
s = cs.findFirst(hasNext);
if (s != v)
throw new AssertionError("Wrong symbol");
- cs = WriteableScope.create(clazz);
+ cs = writeableScope(clazz);
cs.enter(m);
cs.enter(v);
cs.remove(m);
s = cs.findFirst(hasNext);
if (s != v)
throw new AssertionError("Wrong symbol");
+
+ // Test multiple removals in the same scope.
+ VarSymbol v1 = new VarSymbol(0, names.fromString("name1"), Type.noType, clazz);
+ VarSymbol v2 = new VarSymbol(0, names.fromString("name2"), Type.noType, clazz);
+ VarSymbol v3 = new VarSymbol(0, names.fromString("name3"), Type.noType, clazz);
+ VarSymbol v4 = new VarSymbol(0, names.fromString("name4"), Type.noType, clazz);
+
+ cs = writeableScope(clazz, v1, v2, v3, v4);
+ cs.remove(v2);
+ assertRemainingSymbols(cs, v1, v3, v4);
+ cs.remove(v3);
+ assertRemainingSymbols(cs, v1, v4);
+ cs.remove(v1);
+ assertRemainingSymbols(cs, v4);
+ cs.remove(v4);
+ assertRemainingSymbols(cs);
+ }
+
+ private WriteableScope writeableScope(ClassSymbol classSymbol, Symbol... symbols) {
+ WriteableScope cs = WriteableScope.create(classSymbol);
+ for (Symbol symbol : symbols) {
+ cs.enter(symbol);
+ }
+ return cs;
+ }
+
+ private void assertRemainingSymbols(WriteableScope cs, Symbol... symbols) {
+ List<Symbol> expectedSymbols = Arrays.asList(symbols);
+ List<Symbol> actualSymbols = new ArrayList<>();
+ cs.getSymbols().forEach(symbol -> actualSymbols.add(symbol));
+ // The symbols are stored in reverse order
+ Collections.reverse(actualSymbols);
+ if (!actualSymbols.equals(expectedSymbols)) {
+ throw new AssertionError(
+ String.format("Wrong symbols: %s. Expected %s", actualSymbols, expectedSymbols));
+ }
}
}