Scope.java revision 2833:f683944ffa42
133965Sjdp/* 278828Sobrien * Copyright (c) 1999, 2014, Oracle and/or its affiliates. All rights reserved. 333965Sjdp * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 433965Sjdp * 533965Sjdp * This code is free software; you can redistribute it and/or modify it 633965Sjdp * under the terms of the GNU General Public License version 2 only, as 733965Sjdp * published by the Free Software Foundation. Oracle designates this 833965Sjdp * particular file as subject to the "Classpath" exception as provided 933965Sjdp * by Oracle in the LICENSE file that accompanied this code. 1033965Sjdp * 1133965Sjdp * This code is distributed in the hope that it will be useful, but WITHOUT 1233965Sjdp * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1333965Sjdp * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1433965Sjdp * version 2 for more details (a copy is included in the LICENSE file that 1533965Sjdp * accompanied this code). 1633965Sjdp * 1733965Sjdp * You should have received a copy of the GNU General Public License version 1833965Sjdp * 2 along with this work; if not, write to the Free Software Foundation, 1933965Sjdp * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2033965Sjdp * 2133965Sjdp * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2233965Sjdp * or visit www.oracle.com if you need additional information or have any 2333965Sjdp * questions. 2433965Sjdp */ 2533965Sjdp 2633965Sjdppackage com.sun.tools.javac.code; 2733965Sjdp 2833965Sjdpimport com.sun.tools.javac.code.Kinds.Kind; 2933965Sjdpimport java.util.*; 3033965Sjdp 3133965Sjdpimport com.sun.tools.javac.code.Symbol.TypeSymbol; 3233965Sjdpimport com.sun.tools.javac.tree.JCTree.JCImport; 3333965Sjdpimport com.sun.tools.javac.util.*; 3433965Sjdpimport com.sun.tools.javac.util.List; 3533965Sjdp 3633965Sjdpimport static com.sun.tools.javac.code.Scope.LookupKind.NON_RECURSIVE; 3733965Sjdpimport static com.sun.tools.javac.code.Scope.LookupKind.RECURSIVE; 3833965Sjdpimport java.util.stream.Stream; 3933965Sjdpimport java.util.stream.StreamSupport; 4033965Sjdp 4133965Sjdp/** A scope represents an area of visibility in a Java program. The 4233965Sjdp * Scope class is a container for symbols which provides 4333965Sjdp * efficient access to symbols given their names. Scopes are implemented 4433965Sjdp * as hash tables with "open addressing" and "double hashing". 4533965Sjdp * Scopes can be nested. Nested scopes can share their hash tables. 4633965Sjdp * 4733965Sjdp * <p><b>This is NOT part of any supported API. 4833965Sjdp * If you write code that depends on this, you do so at your own risk. 4933965Sjdp * This code and its internal interfaces are subject to change or 5033965Sjdp * deletion without notice.</b> 5133965Sjdp */ 5233965Sjdppublic abstract class Scope { 5333965Sjdp 5433965Sjdp /** The scope's owner. 5533965Sjdp */ 5633965Sjdp public final Symbol owner; 5733965Sjdp 5833965Sjdp protected Scope(Symbol owner) { 5933965Sjdp this.owner = owner; 6033965Sjdp } 6133965Sjdp 6233965Sjdp /**Returns all Symbols in this Scope. Symbols from outward Scopes are included. 6333965Sjdp */ 6433965Sjdp public final Iterable<Symbol> getSymbols() { 6533965Sjdp return getSymbols(noFilter); 6633965Sjdp } 6733965Sjdp 6833965Sjdp /**Returns Symbols that match the given filter. Symbols from outward Scopes are included. 6933965Sjdp */ 7033965Sjdp public final Iterable<Symbol> getSymbols(Filter<Symbol> sf) { 7133965Sjdp return getSymbols(sf, RECURSIVE); 7233965Sjdp } 7333965Sjdp 7433965Sjdp /**Returns all Symbols in this Scope. Symbols from outward Scopes are included 7533965Sjdp * iff lookupKind == RECURSIVE. 7633965Sjdp */ 7733965Sjdp public final Iterable<Symbol> getSymbols(LookupKind lookupKind) { 7833965Sjdp return getSymbols(noFilter, lookupKind); 7933965Sjdp } 8033965Sjdp 8133965Sjdp /**Returns Symbols that match the given filter. Symbols from outward Scopes are included 8233965Sjdp * iff lookupKind == RECURSIVE. 8333965Sjdp */ 8433965Sjdp public abstract Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind); 8533965Sjdp 8633965Sjdp /**Returns Symbols with the given name. Symbols from outward Scopes are included. 8760484Sobrien */ 8860484Sobrien public final Iterable<Symbol> getSymbolsByName(Name name) { 8933965Sjdp return getSymbolsByName(name, RECURSIVE); 9033965Sjdp } 9133965Sjdp 9233965Sjdp /**Returns Symbols with the given name that match the given filter. 9333965Sjdp * Symbols from outward Scopes are included. 9433965Sjdp */ 9533965Sjdp public final Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf) { 9633965Sjdp return getSymbolsByName(name, sf, RECURSIVE); 9733965Sjdp } 9833965Sjdp 9933965Sjdp /**Returns Symbols with the given name. Symbols from outward Scopes are included 10033965Sjdp * iff lookupKind == RECURSIVE. 10133965Sjdp */ 10233965Sjdp public final Iterable<Symbol> getSymbolsByName(Name name, LookupKind lookupKind) { 10333965Sjdp return getSymbolsByName(name, noFilter, lookupKind); 10433965Sjdp } 10533965Sjdp 10633965Sjdp /**Returns Symbols with the given name that match the given filter. 10733965Sjdp * Symbols from outward Scopes are included iff lookupKind == RECURSIVE. 10833965Sjdp */ 10933965Sjdp public abstract Iterable<Symbol> getSymbolsByName(final Name name, final Filter<Symbol> sf, 11033965Sjdp final LookupKind lookupKind); 11133965Sjdp 11233965Sjdp /** Return the first Symbol from this or outward scopes with the given name. 11333965Sjdp * Returns null if none. 11433965Sjdp */ 11533965Sjdp public final Symbol findFirst(Name name) { 11633965Sjdp return findFirst(name, noFilter); 11733965Sjdp } 11833965Sjdp 11933965Sjdp /** Return the first Symbol from this or outward scopes with the given name that matches the 12033965Sjdp * given filter. Returns null if none. 12133965Sjdp */ 12233965Sjdp public Symbol findFirst(Name name, Filter<Symbol> sf) { 12333965Sjdp Iterator<Symbol> it = getSymbolsByName(name, sf).iterator(); 12433965Sjdp return it.hasNext() ? it.next() : null; 12533965Sjdp } 12633965Sjdp 12733965Sjdp /** Returns true iff there are is at least one Symbol in this scope matching the given filter. 12833965Sjdp * Does not inspect outward scopes. 12933965Sjdp */ 13033965Sjdp public boolean anyMatch(Filter<Symbol> filter) { 13133965Sjdp return getSymbols(filter, NON_RECURSIVE).iterator().hasNext(); 13233965Sjdp } 13333965Sjdp 13433965Sjdp /** Returns true iff the given Symbol is in this scope or any outward scope. 13533965Sjdp */ 13633965Sjdp public boolean includes(final Symbol sym) { 13733965Sjdp return getSymbolsByName(sym.name, new Filter<Symbol>() { 13833965Sjdp @Override 13933965Sjdp public boolean accepts(Symbol t) { 14033965Sjdp return t == sym; 14133965Sjdp } 14233965Sjdp }).iterator().hasNext(); 14333965Sjdp } 14433965Sjdp 14533965Sjdp /** Returns true iff this scope does not contain any Symbol. Does not inspect outward scopes. 14633965Sjdp */ 14733965Sjdp public boolean isEmpty() { 14833965Sjdp return !getSymbols(NON_RECURSIVE).iterator().hasNext(); 14933965Sjdp } 15033965Sjdp 15133965Sjdp /** Returns the Scope from which the givins Symbol originates in this scope. 15233965Sjdp */ 15333965Sjdp public abstract Scope getOrigin(Symbol byName); 15433965Sjdp 15533965Sjdp /** Returns true iff the given Symbol is part of this scope due to a static import. 15633965Sjdp */ 15733965Sjdp public abstract boolean isStaticallyImported(Symbol byName); 15833965Sjdp 15933965Sjdp private static final Filter<Symbol> noFilter = null; 16033965Sjdp 16133965Sjdp /** A list of scopes to be notified if items are to be removed from this scope. 16260484Sobrien */ 16333965Sjdp List<ScopeListener> listeners = List.nil(); 16433965Sjdp 16533965Sjdp public void addScopeListener(ScopeListener sl) { 16633965Sjdp listeners = listeners.prepend(sl); 16733965Sjdp } 16833965Sjdp 16933965Sjdp public interface ScopeListener { 17033965Sjdp public void symbolAdded(Symbol sym, Scope s); 17133965Sjdp public void symbolRemoved(Symbol sym, Scope s); 17233965Sjdp } 17333965Sjdp 17433965Sjdp public enum LookupKind { 17533965Sjdp RECURSIVE, 17633965Sjdp NON_RECURSIVE; 17733965Sjdp } 17833965Sjdp 17933965Sjdp /**A scope into which Symbols can be added.*/ 18033965Sjdp public abstract static class WriteableScope extends Scope { 18133965Sjdp 18233965Sjdp public WriteableScope(Symbol owner) { 18333965Sjdp super(owner); 18433965Sjdp } 18533965Sjdp 18633965Sjdp /** Enter the given Symbol into this scope. 18733965Sjdp */ 188104834Sobrien public abstract void enter(Symbol c); 18960484Sobrien /** Enter symbol sym in this scope if not already there. 19060484Sobrien */ 19160484Sobrien public abstract void enterIfAbsent(Symbol c); 19260484Sobrien 19360484Sobrien public abstract void remove(Symbol c); 19460484Sobrien 19560484Sobrien /** Construct a fresh scope within this scope, with same owner. The new scope may 196104834Sobrien * shares internal structures with the this scope. Used in connection with 19733965Sjdp * method leave if scope access is stack-like in order to avoid allocation 198104834Sobrien * of fresh tables. 19933965Sjdp */ 20033965Sjdp public final WriteableScope dup() { 20133965Sjdp return dup(this.owner); 20233965Sjdp } 20333965Sjdp 20433965Sjdp /** Construct a fresh scope within this scope, with new owner. The new scope may 20533965Sjdp * shares internal structures with the this scope. Used in connection with 20633965Sjdp * method leave if scope access is stack-like in order to avoid allocation 20733965Sjdp * of fresh tables. 20833965Sjdp */ 20933965Sjdp public abstract WriteableScope dup(Symbol newOwner); 21033965Sjdp 21133965Sjdp /** Must be called on dup-ed scopes to be able to work with the outward scope again. 21233965Sjdp */ 21333965Sjdp public abstract WriteableScope leave(); 21433965Sjdp 21533965Sjdp /** Construct a fresh scope within this scope, with same owner. The new scope 21633965Sjdp * will not share internal structures with this scope. 21733965Sjdp */ 21833965Sjdp public final WriteableScope dupUnshared() { 21933965Sjdp return dupUnshared(owner); 22033965Sjdp } 22133965Sjdp 22233965Sjdp /** Construct a fresh scope within this scope, with new owner. The new scope 22333965Sjdp * will not share internal structures with this scope. 22433965Sjdp */ 22533965Sjdp public abstract WriteableScope dupUnshared(Symbol newOwner); 22633965Sjdp 22733965Sjdp /** Create a new WriteableScope. 22833965Sjdp */ 22933965Sjdp public static WriteableScope create(Symbol owner) { 23033965Sjdp return new ScopeImpl(owner); 23133965Sjdp } 23233965Sjdp 23333965Sjdp } 23433965Sjdp 23533965Sjdp private static class ScopeImpl extends WriteableScope { 23633965Sjdp /** The number of scopes that share this scope's hash table. 23733965Sjdp */ 23833965Sjdp private int shared; 23933965Sjdp 24033965Sjdp /** Next enclosing scope (with whom this scope may share a hashtable) 24133965Sjdp */ 24233965Sjdp public ScopeImpl next; 24333965Sjdp 24433965Sjdp /** A hash table for the scope's entries. 24533965Sjdp */ 24633965Sjdp Entry[] table; 24733965Sjdp 24833965Sjdp /** Mask for hash codes, always equal to (table.length - 1). 24933965Sjdp */ 25033965Sjdp int hashMask; 25133965Sjdp 25233965Sjdp /** A linear list that also contains all entries in 25333965Sjdp * reverse order of appearance (i.e later entries are pushed on top). 25433965Sjdp */ 25533965Sjdp public Entry elems; 25633965Sjdp 25733965Sjdp /** The number of elements in this scope. 25833965Sjdp * This includes deleted elements, whose value is the sentinel. 25933965Sjdp */ 26033965Sjdp int nelems = 0; 26133965Sjdp 26233965Sjdp /** Use as a "not-found" result for lookup. 26333965Sjdp * Also used to mark deleted entries in the table. 26433965Sjdp */ 26533965Sjdp private static final Entry sentinel = new Entry(null, null, null, null); 26633965Sjdp 26733965Sjdp /** The hash table's initial size. 26833965Sjdp */ 26933965Sjdp private static final int INITIAL_SIZE = 0x10; 27033965Sjdp 27133965Sjdp /** Construct a new scope, within scope next, with given owner, using 27233965Sjdp * given table. The table's length must be an exponent of 2. 27333965Sjdp */ 27433965Sjdp private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table) { 27533965Sjdp super(owner); 27633965Sjdp this.next = next; 27733965Sjdp Assert.check(owner != null); 27833965Sjdp this.table = table; 27933965Sjdp this.hashMask = table.length - 1; 28033965Sjdp } 28133965Sjdp 28233965Sjdp /** Convenience constructor used for dup and dupUnshared. */ 28333965Sjdp private ScopeImpl(ScopeImpl next, Symbol owner, Entry[] table, int nelems) { 28433965Sjdp this(next, owner, table); 28533965Sjdp this.nelems = nelems; 28633965Sjdp } 28733965Sjdp 28833965Sjdp /** Construct a new scope, within scope next, with given owner, 28933965Sjdp * using a fresh table of length INITIAL_SIZE. 29033965Sjdp */ 29133965Sjdp public ScopeImpl(Symbol owner) { 29233965Sjdp this(null, owner, new Entry[INITIAL_SIZE]); 29333965Sjdp } 29433965Sjdp 29533965Sjdp /** Construct a fresh scope within this scope, with new owner, 29633965Sjdp * which shares its table with the outer scope. Used in connection with 29733965Sjdp * method leave if scope access is stack-like in order to avoid allocation 29833965Sjdp * of fresh tables. 29933965Sjdp */ 30033965Sjdp public WriteableScope dup(Symbol newOwner) { 30133965Sjdp ScopeImpl result = new ScopeImpl(this, newOwner, this.table, this.nelems); 30233965Sjdp shared++; 30333965Sjdp // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode()); 30433965Sjdp // new Error().printStackTrace(System.out); 30533965Sjdp return result; 30633965Sjdp } 30733965Sjdp 30833965Sjdp /** Construct a fresh scope within this scope, with new owner, 30933965Sjdp * with a new hash table, whose contents initially are those of 31033965Sjdp * the table of its outer scope. 31133965Sjdp */ 31233965Sjdp public WriteableScope dupUnshared(Symbol newOwner) { 31333965Sjdp if (shared > 0) { 31433965Sjdp //The nested Scopes might have already added something to the table, so all items 31533965Sjdp //that don't originate in this Scope or any of its outer Scopes need to be cleared: 31633965Sjdp Set<Scope> acceptScopes = Collections.newSetFromMap(new IdentityHashMap<>()); 31733965Sjdp ScopeImpl c = this; 31833965Sjdp while (c != null) { 31933965Sjdp acceptScopes.add(c); 32033965Sjdp c = c.next; 32133965Sjdp } 32233965Sjdp int n = 0; 32333965Sjdp Entry[] oldTable = this.table; 32433965Sjdp Entry[] newTable = new Entry[this.table.length]; 32533965Sjdp for (int i = 0; i < oldTable.length; i++) { 32633965Sjdp Entry e = oldTable[i]; 32733965Sjdp while (e != null && e != sentinel && !acceptScopes.contains(e.scope)) { 32833965Sjdp e = e.shadowed; 32933965Sjdp } 33033965Sjdp if (e != null) { 33133965Sjdp n++; 33233965Sjdp newTable[i] = e; 33333965Sjdp } 33433965Sjdp } 33533965Sjdp return new ScopeImpl(this, newOwner, newTable, n); 33633965Sjdp } else { 33733965Sjdp return new ScopeImpl(this, newOwner, this.table.clone(), this.nelems); 33833965Sjdp } 33933965Sjdp } 34033965Sjdp 34133965Sjdp /** Remove all entries of this scope from its table, if shared 34233965Sjdp * with next. 34333965Sjdp */ 34433965Sjdp public WriteableScope leave() { 34533965Sjdp Assert.check(shared == 0); 34633965Sjdp if (table != next.table) return next; 34733965Sjdp while (elems != null) { 34833965Sjdp int hash = getIndex(elems.sym.name); 34933965Sjdp Entry e = table[hash]; 35033965Sjdp Assert.check(e == elems, elems.sym); 35133965Sjdp table[hash] = elems.shadowed; 35233965Sjdp elems = elems.sibling; 35333965Sjdp } 35433965Sjdp Assert.check(next.shared > 0); 35533965Sjdp next.shared--; 35633965Sjdp next.nelems = nelems; 35733965Sjdp // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode()); 35833965Sjdp // new Error().printStackTrace(System.out); 35933965Sjdp return next; 36033965Sjdp } 36133965Sjdp 36233965Sjdp /** Double size of hash table. 36333965Sjdp */ 36433965Sjdp private void dble() { 36533965Sjdp Assert.check(shared == 0); 36633965Sjdp Entry[] oldtable = table; 36733965Sjdp Entry[] newtable = new Entry[oldtable.length * 2]; 36833965Sjdp for (ScopeImpl s = this; s != null; s = s.next) { 36933965Sjdp if (s.table == oldtable) { 37033965Sjdp Assert.check(s == this || s.shared != 0); 37133965Sjdp s.table = newtable; 37233965Sjdp s.hashMask = newtable.length - 1; 37333965Sjdp } 37433965Sjdp } 37533965Sjdp int n = 0; 37633965Sjdp for (int i = oldtable.length; --i >= 0; ) { 37733965Sjdp Entry e = oldtable[i]; 37833965Sjdp if (e != null && e != sentinel) { 37933965Sjdp table[getIndex(e.sym.name)] = e; 38033965Sjdp n++; 38133965Sjdp } 38233965Sjdp } 38333965Sjdp // We don't need to update nelems for shared inherited scopes, 38433965Sjdp // since that gets handled by leave(). 38533965Sjdp nelems = n; 38633965Sjdp } 38733965Sjdp 38833965Sjdp /** Enter symbol sym in this scope. 38933965Sjdp */ 39033965Sjdp public void enter(Symbol sym) { 39133965Sjdp Assert.check(shared == 0); 39233965Sjdp if (nelems * 3 >= hashMask * 2) 39333965Sjdp dble(); 39433965Sjdp int hash = getIndex(sym.name); 39533965Sjdp Entry old = table[hash]; 39633965Sjdp if (old == null) { 39733965Sjdp old = sentinel; 39833965Sjdp nelems++; 39933965Sjdp } 40033965Sjdp Entry e = new Entry(sym, old, elems, this); 40133965Sjdp table[hash] = e; 40233965Sjdp elems = e; 40333965Sjdp 40433965Sjdp //notify listeners 40533965Sjdp for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) { 40633965Sjdp l.head.symbolAdded(sym, this); 40733965Sjdp } 40833965Sjdp } 40933965Sjdp 41060484Sobrien /** Remove symbol from this scope. Used when an inner class 41133965Sjdp * attribute tells us that the class isn't a package member. 41233965Sjdp */ 41333965Sjdp public void remove(Symbol sym) { 41433965Sjdp Assert.check(shared == 0); 41533965Sjdp Entry e = lookup(sym.name); 41633965Sjdp if (e.scope == null) return; 41733965Sjdp 41833965Sjdp // remove e from table and shadowed list; 41933965Sjdp int i = getIndex(sym.name); 42033965Sjdp Entry te = table[i]; 42133965Sjdp if (te == e) 42233965Sjdp table[i] = e.shadowed; 42333965Sjdp else while (true) { 42433965Sjdp if (te.shadowed == e) { 42533965Sjdp te.shadowed = e.shadowed; 42633965Sjdp break; 42733965Sjdp } 42833965Sjdp te = te.shadowed; 42933965Sjdp } 43033965Sjdp 43133965Sjdp // remove e from elems and sibling list 43233965Sjdp te = elems; 43333965Sjdp if (te == e) 43433965Sjdp elems = e.sibling; 43533965Sjdp else while (true) { 43633965Sjdp if (te.sibling == e) { 43733965Sjdp te.sibling = e.sibling; 43833965Sjdp break; 43933965Sjdp } 44033965Sjdp te = te.sibling; 44133965Sjdp } 44233965Sjdp 44333965Sjdp //notify listeners 44433965Sjdp for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) { 44533965Sjdp l.head.symbolRemoved(sym, this); 44633965Sjdp } 44733965Sjdp } 44833965Sjdp 44933965Sjdp /** Enter symbol sym in this scope if not already there. 45033965Sjdp */ 45133965Sjdp public void enterIfAbsent(Symbol sym) { 45233965Sjdp Assert.check(shared == 0); 45333965Sjdp Entry e = lookup(sym.name); 45433965Sjdp while (e.scope == this && e.sym.kind != sym.kind) e = e.next(); 45533965Sjdp if (e.scope != this) enter(sym); 45633965Sjdp } 45733965Sjdp 45833965Sjdp /** Given a class, is there already a class with same fully 459 * qualified name in this (import) scope? 460 */ 461 public boolean includes(Symbol c) { 462 for (Scope.Entry e = lookup(c.name); 463 e.scope == this; 464 e = e.next()) { 465 if (e.sym == c) return true; 466 } 467 return false; 468 } 469 470 /** Return the entry associated with given name, starting in 471 * this scope and proceeding outwards. If no entry was found, 472 * return the sentinel, which is characterized by having a null in 473 * both its scope and sym fields, whereas both fields are non-null 474 * for regular entries. 475 */ 476 protected Entry lookup(Name name) { 477 return lookup(name, noFilter); 478 } 479 480 protected Entry lookup(Name name, Filter<Symbol> sf) { 481 Entry e = table[getIndex(name)]; 482 if (e == null || e == sentinel) 483 return sentinel; 484 while (e.scope != null && (e.sym.name != name || (sf != null && !sf.accepts(e.sym)))) 485 e = e.shadowed; 486 return e; 487 } 488 489 public Symbol findFirst(Name name, Filter<Symbol> sf) { 490 return lookup(name, sf).sym; 491 } 492 493 /*void dump (java.io.PrintStream out) { 494 out.println(this); 495 for (int l=0; l < table.length; l++) { 496 Entry le = table[l]; 497 out.print("#"+l+": "); 498 if (le==sentinel) out.println("sentinel"); 499 else if(le == null) out.println("null"); 500 else out.println(""+le+" s:"+le.sym); 501 } 502 }*/ 503 504 /** Look for slot in the table. 505 * We use open addressing with double hashing. 506 */ 507 int getIndex (Name name) { 508 int h = name.hashCode(); 509 int i = h & hashMask; 510 // The expression below is always odd, so it is guaranteed 511 // to be mutually prime with table.length, a power of 2. 512 int x = hashMask - ((h + (h >> 16)) << 1); 513 int d = -1; // Index of a deleted item. 514 for (;;) { 515 Entry e = table[i]; 516 if (e == null) 517 return d >= 0 ? d : i; 518 if (e == sentinel) { 519 // We have to keep searching even if we see a deleted item. 520 // However, remember the index in case we fail to find the name. 521 if (d < 0) 522 d = i; 523 } else if (e.sym.name == name) 524 return i; 525 i = (i + x) & hashMask; 526 } 527 } 528 529 public boolean anyMatch(Filter<Symbol> sf) { 530 return getSymbols(sf, NON_RECURSIVE).iterator().hasNext(); 531 } 532 533 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, 534 final LookupKind lookupKind) { 535 return new Iterable<Symbol>() { 536 public Iterator<Symbol> iterator() { 537 return new Iterator<Symbol>() { 538 private ScopeImpl currScope = ScopeImpl.this; 539 private Scope.Entry currEntry = elems; 540 { 541 update(); 542 } 543 544 public boolean hasNext() { 545 return currEntry != null; 546 } 547 548 public Symbol next() { 549 Symbol sym = (currEntry == null ? null : currEntry.sym); 550 if (currEntry != null) { 551 currEntry = currEntry.sibling; 552 } 553 update(); 554 return sym; 555 } 556 557 public void remove() { 558 throw new UnsupportedOperationException(); 559 } 560 561 private void update() { 562 skipToNextMatchingEntry(); 563 if (lookupKind == RECURSIVE) { 564 while (currEntry == null && currScope.next != null) { 565 currScope = currScope.next; 566 currEntry = currScope.elems; 567 skipToNextMatchingEntry(); 568 } 569 } 570 } 571 572 void skipToNextMatchingEntry() { 573 while (currEntry != null && sf != null && !sf.accepts(currEntry.sym)) { 574 currEntry = currEntry.sibling; 575 } 576 } 577 }; 578 } 579 }; 580 } 581 582 public Iterable<Symbol> getSymbolsByName(final Name name, 583 final Filter<Symbol> sf, 584 final LookupKind lookupKind) { 585 return new Iterable<Symbol>() { 586 public Iterator<Symbol> iterator() { 587 return new Iterator<Symbol>() { 588 Scope.Entry currentEntry = lookup(name, sf); 589 590 public boolean hasNext() { 591 return currentEntry.scope != null && 592 (lookupKind == RECURSIVE || 593 currentEntry.scope == ScopeImpl.this); 594 } 595 public Symbol next() { 596 Scope.Entry prevEntry = currentEntry; 597 currentEntry = currentEntry.next(sf); 598 return prevEntry.sym; 599 } 600 public void remove() { 601 throw new UnsupportedOperationException(); 602 } 603 }; 604 } 605 }; 606 } 607 608 public Scope getOrigin(Symbol s) { 609 for (Scope.Entry e = lookup(s.name); e.scope != null ; e = e.next()) { 610 if (e.sym == s) { 611 return this; 612 } 613 } 614 return null; 615 } 616 617 @Override 618 public boolean isStaticallyImported(Symbol s) { 619 return false; 620 } 621 622 public String toString() { 623 StringBuilder result = new StringBuilder(); 624 result.append("Scope["); 625 for (ScopeImpl s = this; s != null ; s = s.next) { 626 if (s != this) result.append(" | "); 627 for (Entry e = s.elems; e != null; e = e.sibling) { 628 if (e != s.elems) result.append(", "); 629 result.append(e.sym); 630 } 631 } 632 result.append("]"); 633 return result.toString(); 634 } 635 } 636 637 /** A class for scope entries. 638 */ 639 private static class Entry { 640 641 /** The referenced symbol. 642 * sym == null iff this == sentinel 643 */ 644 public Symbol sym; 645 646 /** An entry with the same hash code, or sentinel. 647 */ 648 private Entry shadowed; 649 650 /** Next entry in same scope. 651 */ 652 public Entry sibling; 653 654 /** The entry's scope. 655 * scope == null iff this == sentinel 656 */ 657 public Scope scope; 658 659 public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) { 660 this.sym = sym; 661 this.shadowed = shadowed; 662 this.sibling = sibling; 663 this.scope = scope; 664 } 665 666 /** Return next entry with the same name as this entry, proceeding 667 * outwards if not found in this scope. 668 */ 669 public Entry next() { 670 return shadowed; 671 } 672 673 public Entry next(Filter<Symbol> sf) { 674 if (shadowed.sym == null || sf == null || sf.accepts(shadowed.sym)) return shadowed; 675 else return shadowed.next(sf); 676 } 677 678 } 679 680 public static class ImportScope extends CompoundScope { 681 682 public ImportScope(Symbol owner) { 683 super(owner); 684 } 685 686 /**Finalize the content of the ImportScope to speed-up future lookups. 687 * No further changes to class hierarchy or class content will be reflected. 688 */ 689 public void finalizeScope() { 690 for (List<Scope> scopes = this.subScopes; scopes.nonEmpty(); scopes = scopes.tail) { 691 Scope impScope = scopes.head; 692 693 if (impScope instanceof FilterImportScope && impScope.owner.kind == Kind.TYP) { 694 WriteableScope finalized = WriteableScope.create(impScope.owner); 695 696 for (Symbol sym : impScope.getSymbols()) { 697 finalized.enter(sym); 698 } 699 700 finalized.addScopeListener(new ScopeListener() { 701 @Override 702 public void symbolAdded(Symbol sym, Scope s) { 703 Assert.error("The scope is sealed."); 704 } 705 @Override 706 public void symbolRemoved(Symbol sym, Scope s) { 707 Assert.error("The scope is sealed."); 708 } 709 }); 710 711 scopes.head = finalized; 712 } 713 } 714 } 715 716 } 717 718 public static class NamedImportScope extends ImportScope { 719 720 public NamedImportScope(Symbol owner, Scope currentFileScope) { 721 super(owner); 722 prependSubScope(currentFileScope); 723 } 724 725 public Scope importByName(Types types, Scope origin, Name name, ImportFilter filter) { 726 return appendScope(new FilterImportScope(types, origin, name, filter, true)); 727 } 728 729 public Scope importType(Scope delegate, Scope origin, Symbol sym) { 730 return appendScope(new SingleEntryScope(delegate.owner, sym, origin)); 731 } 732 733 private Scope appendScope(Scope newScope) { 734 List<Scope> existingScopes = this.subScopes.reverse(); 735 subScopes = List.of(existingScopes.head); 736 subScopes = subScopes.prepend(newScope); 737 for (Scope s : existingScopes.tail) { 738 subScopes = subScopes.prepend(s); 739 } 740 return newScope; 741 } 742 743 private static class SingleEntryScope extends Scope { 744 745 private final Symbol sym; 746 private final List<Symbol> content; 747 private final Scope origin; 748 749 public SingleEntryScope(Symbol owner, Symbol sym, Scope origin) { 750 super(owner); 751 this.sym = sym; 752 this.content = List.of(sym); 753 this.origin = origin; 754 } 755 756 @Override 757 public Iterable<Symbol> getSymbols(Filter<Symbol> sf, LookupKind lookupKind) { 758 return sf == null || sf.accepts(sym) ? content : Collections.<Symbol>emptyList(); 759 } 760 761 @Override 762 public Iterable<Symbol> getSymbolsByName(Name name, 763 Filter<Symbol> sf, 764 LookupKind lookupKind) { 765 return sym.name == name && 766 (sf == null || sf.accepts(sym)) ? content : Collections.<Symbol>emptyList(); 767 } 768 769 @Override 770 public Scope getOrigin(Symbol byName) { 771 return sym == byName ? origin : null; 772 } 773 774 @Override 775 public boolean isStaticallyImported(Symbol byName) { 776 return false; 777 } 778 779 } 780 } 781 782 public static class StarImportScope extends ImportScope { 783 784 public StarImportScope(Symbol owner) { 785 super(owner); 786 } 787 788 public void importAll(Types types, Scope origin, 789 ImportFilter filter, 790 boolean staticImport) { 791 for (Scope existing : subScopes) { 792 Assert.check(existing instanceof FilterImportScope); 793 FilterImportScope fis = (FilterImportScope) existing; 794 if (fis.origin == origin && fis.filter == filter && 795 fis.staticImport == staticImport) 796 return ; //avoid entering the same scope twice 797 } 798 prependSubScope(new FilterImportScope(types, origin, null, filter, staticImport)); 799 } 800 801 public boolean isFilled() { 802 return subScopes.nonEmpty(); 803 } 804 805 } 806 807 public interface ImportFilter { 808 public boolean accepts(Scope origin, Symbol sym); 809 } 810 811 private static class FilterImportScope extends Scope { 812 813 private final Types types; 814 private final Scope origin; 815 private final Name filterName; 816 private final ImportFilter filter; 817 private final boolean staticImport; 818 819 public FilterImportScope(Types types, 820 Scope origin, 821 Name filterName, 822 ImportFilter filter, 823 boolean staticImport) { 824 super(origin.owner); 825 this.types = types; 826 this.origin = origin; 827 this.filterName = filterName; 828 this.filter = filter; 829 this.staticImport = staticImport; 830 } 831 832 @Override 833 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, final LookupKind lookupKind) { 834 if (filterName != null) 835 return getSymbolsByName(filterName, sf, lookupKind); 836 SymbolImporter si = new SymbolImporter(staticImport) { 837 @Override 838 Iterable<Symbol> doLookup(TypeSymbol tsym) { 839 return tsym.members().getSymbols(sf, lookupKind); 840 } 841 }; 842 return si.importFrom((TypeSymbol) origin.owner) :: iterator; 843 } 844 845 @Override 846 public Iterable<Symbol> getSymbolsByName(final Name name, 847 final Filter<Symbol> sf, 848 final LookupKind lookupKind) { 849 if (filterName != null && filterName != name) 850 return Collections.emptyList(); 851 SymbolImporter si = new SymbolImporter(staticImport) { 852 @Override 853 Iterable<Symbol> doLookup(TypeSymbol tsym) { 854 return tsym.members().getSymbolsByName(name, sf, lookupKind); 855 } 856 }; 857 return si.importFrom((TypeSymbol) origin.owner) :: iterator; 858 } 859 860 @Override 861 public Scope getOrigin(Symbol byName) { 862 return origin; 863 } 864 865 @Override 866 public boolean isStaticallyImported(Symbol byName) { 867 return staticImport; 868 } 869 870 abstract class SymbolImporter { 871 Set<Symbol> processed = new HashSet<>(); 872 List<Iterable<Symbol>> delegates = List.nil(); 873 final boolean inspectSuperTypes; 874 public SymbolImporter(boolean inspectSuperTypes) { 875 this.inspectSuperTypes = inspectSuperTypes; 876 } 877 Stream<Symbol> importFrom(TypeSymbol tsym) { 878 if (tsym == null || !processed.add(tsym)) 879 return Stream.empty(); 880 881 Stream<Symbol> result = Stream.empty(); 882 883 if (inspectSuperTypes) { 884 // also import inherited names 885 result = importFrom(types.supertype(tsym.type).tsym); 886 for (Type t : types.interfaces(tsym.type)) 887 result = Stream.concat(importFrom(t.tsym), result); 888 } 889 890 return Stream.concat(StreamSupport.stream(doLookup(tsym).spliterator(), false) 891 .filter(s -> filter.accepts(origin, s)), 892 result); 893 } 894 abstract Iterable<Symbol> doLookup(TypeSymbol tsym); 895 } 896 897 } 898 899 /** A class scope adds capabilities to keep track of changes in related 900 * class scopes - this allows client to realize whether a class scope 901 * has changed, either directly (because a new member has been added/removed 902 * to this scope) or indirectly (i.e. because a new member has been 903 * added/removed into a supertype scope) 904 */ 905 public static class CompoundScope extends Scope implements ScopeListener { 906 907 List<Scope> subScopes = List.nil(); 908 private int mark = 0; 909 910 public CompoundScope(Symbol owner) { 911 super(owner); 912 } 913 914 public void prependSubScope(Scope that) { 915 if (that != null) { 916 subScopes = subScopes.prepend(that); 917 that.addScopeListener(this); 918 mark++; 919 for (ScopeListener sl : listeners) { 920 sl.symbolAdded(null, this); //propagate upwards in case of nested CompoundScopes 921 } 922 } 923 } 924 925 public void symbolAdded(Symbol sym, Scope s) { 926 mark++; 927 for (ScopeListener sl : listeners) { 928 sl.symbolAdded(sym, s); 929 } 930 } 931 932 public void symbolRemoved(Symbol sym, Scope s) { 933 mark++; 934 for (ScopeListener sl : listeners) { 935 sl.symbolRemoved(sym, s); 936 } 937 } 938 939 public int getMark() { 940 return mark; 941 } 942 943 @Override 944 public String toString() { 945 StringBuilder buf = new StringBuilder(); 946 buf.append("CompoundScope{"); 947 String sep = ""; 948 for (Scope s : subScopes) { 949 buf.append(sep); 950 buf.append(s); 951 sep = ","; 952 } 953 buf.append("}"); 954 return buf.toString(); 955 } 956 957 @Override 958 public Iterable<Symbol> getSymbols(final Filter<Symbol> sf, 959 final LookupKind lookupKind) { 960 return new Iterable<Symbol>() { 961 public Iterator<Symbol> iterator() { 962 return new CompoundScopeIterator(subScopes) { 963 Iterator<Symbol> nextIterator(Scope s) { 964 return s.getSymbols(sf, lookupKind).iterator(); 965 } 966 }; 967 } 968 }; 969 } 970 971 @Override 972 public Iterable<Symbol> getSymbolsByName(final Name name, 973 final Filter<Symbol> sf, 974 final LookupKind lookupKind) { 975 return new Iterable<Symbol>() { 976 public Iterator<Symbol> iterator() { 977 return new CompoundScopeIterator(subScopes) { 978 Iterator<Symbol> nextIterator(Scope s) { 979 return s.getSymbolsByName(name, sf, lookupKind).iterator(); 980 } 981 }; 982 } 983 }; 984 } 985 986 @Override 987 public Scope getOrigin(Symbol sym) { 988 for (Scope delegate : subScopes) { 989 if (delegate.includes(sym)) 990 return delegate.getOrigin(sym); 991 } 992 993 return null; 994 } 995 996 @Override 997 public boolean isStaticallyImported(Symbol sym) { 998 for (Scope delegate : subScopes) { 999 if (delegate.includes(sym)) 1000 return delegate.isStaticallyImported(sym); 1001 } 1002 1003 return false; 1004 } 1005 1006 abstract class CompoundScopeIterator implements Iterator<Symbol> { 1007 1008 private Iterator<Symbol> currentIterator; 1009 private List<Scope> scopesToScan; 1010 1011 public CompoundScopeIterator(List<Scope> scopesToScan) { 1012 this.scopesToScan = scopesToScan; 1013 update(); 1014 } 1015 1016 abstract Iterator<Symbol> nextIterator(Scope s); 1017 1018 public boolean hasNext() { 1019 return currentIterator != null; 1020 } 1021 1022 public Symbol next() { 1023 Symbol sym = currentIterator.next(); 1024 if (!currentIterator.hasNext()) { 1025 update(); 1026 } 1027 return sym; 1028 } 1029 1030 public void remove() { 1031 throw new UnsupportedOperationException(); 1032 } 1033 1034 private void update() { 1035 while (scopesToScan.nonEmpty()) { 1036 currentIterator = nextIterator(scopesToScan.head); 1037 scopesToScan = scopesToScan.tail; 1038 if (currentIterator.hasNext()) return; 1039 } 1040 currentIterator = null; 1041 } 1042 } 1043 } 1044 1045 /** An error scope, for which the owner should be an error symbol. */ 1046 public static class ErrorScope extends ScopeImpl { 1047 ErrorScope(ScopeImpl next, Symbol errSymbol, Entry[] table) { 1048 super(next, /*owner=*/errSymbol, table); 1049 } 1050 public ErrorScope(Symbol errSymbol) { 1051 super(errSymbol); 1052 } 1053 public WriteableScope dup(Symbol newOwner) { 1054 return new ErrorScope(this, newOwner, table); 1055 } 1056 public WriteableScope dupUnshared(Symbol newOwner) { 1057 return new ErrorScope(this, newOwner, table.clone()); 1058 } 1059 public Entry lookup(Name name) { 1060 Entry e = super.lookup(name); 1061 if (e.scope == null) 1062 return new Entry(owner, null, null, null); 1063 else 1064 return e; 1065 } 1066 } 1067} 1068