/*
* Copyright (c) 1999, 2011, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package com.sun.tools.javac.code;
import com.sun.tools.javac.util.*;
import java.util.Iterator;
/** A scope represents an area of visibility in a Java program. The
* Scope class is a container for symbols which provides
* efficient access to symbols given their names. Scopes are implemented
* as hash tables with "open addressing" and "double hashing".
* Scopes can be nested; the next field of a scope points
* to its next outer scope. Nested scopes can share their hash tables.
*
* <p><b>This is NOT part of any supported API.
* If you write code that depends on this, you do so at your own risk.
* This code and its internal interfaces are subject to change or
* deletion without notice.</b>
*/
public class Scope {
/** The number of scopes that share this scope's hash table.
*/
private int shared;
/** Next enclosing scope (with whom this scope may share a hashtable)
*/
public Scope next;
/** The scope's owner.
*/
public Symbol owner;
/** A hash table for the scope's entries.
*/
Entry[] table;
/** Mask for hash codes, always equal to (table.length - 1).
*/
int hashMask;
/** A linear list that also contains all entries in
* reverse order of appearance (i.e later entries are pushed on top).
*/
public Entry elems;
/** The number of elements in this scope.
* This includes deleted elements, whose value is the sentinel.
*/
int nelems = 0;
/** A list of scopes to be notified if items are to be removed from this scope.
*/
List<ScopeListener> listeners = List.nil();
/** Use as a "not-found" result for lookup.
* Also used to mark deleted entries in the table.
*/
private static final Entry sentinel = new Entry(null, null, null, null);
/** The hash table's initial size.
*/
private static final int INITIAL_SIZE = 0x10;
/** A value for the empty scope.
*/
public static final Scope emptyScope = new Scope(null, null, new Entry[]{});
/** Construct a new scope, within scope next, with given owner, using
* given table. The table's length must be an exponent of 2.
*/
private Scope(Scope next, Symbol owner, Entry[] table) {
this.next = next;
Assert.check(emptyScope == null || owner != null);
this.owner = owner;
this.table = table;
this.hashMask = table.length - 1;
}
/** Convenience constructor used for dup and dupUnshared. */
private Scope(Scope next, Symbol owner, Entry[] table, int nelems) {
this(next, owner, table);
this.nelems = nelems;
}
/** Construct a new scope, within scope next, with given owner,
* using a fresh table of length INITIAL_SIZE.
*/
public Scope(Symbol owner) {
this(null, owner, new Entry[INITIAL_SIZE]);
}
/** Construct a fresh scope within this scope, with same owner,
* which shares its table with the outer scope. Used in connection with
* method leave if scope access is stack-like in order to avoid allocation
* of fresh tables.
*/
public Scope dup() {
return dup(this.owner);
}
/** Construct a fresh scope within this scope, with new owner,
* which shares its table with the outer scope. Used in connection with
* method leave if scope access is stack-like in order to avoid allocation
* of fresh tables.
*/
public Scope dup(Symbol newOwner) {
Scope result = new Scope(this, newOwner, this.table, this.nelems);
shared++;
// System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode());
// new Error().printStackTrace(System.out);
return result;
}
/** Construct a fresh scope within this scope, with same owner,
* with a new hash table, whose contents initially are those of
* the table of its outer scope.
*/
public Scope dupUnshared() {
return new Scope(this, this.owner, this.table.clone(), this.nelems);
}
/** Remove all entries of this scope from its table, if shared
* with next.
*/
public Scope leave() {
Assert.check(shared == 0);
if (table != next.table) return next;
while (elems != null) {
int hash = getIndex(elems.sym.name);
Entry e = table[hash];
Assert.check(e == elems, elems.sym);
table[hash] = elems.shadowed;
elems = elems.sibling;
}
Assert.check(next.shared > 0);
next.shared--;
next.nelems = nelems;
// System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode());
// new Error().printStackTrace(System.out);
return next;
}
/** Double size of hash table.
*/
private void dble() {
Assert.check(shared == 0);
Entry[] oldtable = table;
Entry[] newtable = new Entry[oldtable.length * 2];
for (Scope s = this; s != null; s = s.next) {
if (s.table == oldtable) {
Assert.check(s == this || s.shared != 0);
s.table = newtable;
s.hashMask = newtable.length - 1;
}
}
int n = 0;
for (int i = oldtable.length; --i >= 0; ) {
Entry e = oldtable[i];
if (e != null && e != sentinel) {
table[getIndex(e.sym.name)] = e;
n++;
}
}
// We don't need to update nelems for shared inherited scopes,
// since that gets handled by leave().
nelems = n;
}
/** Enter symbol sym in this scope.
*/
public void enter(Symbol sym) {
Assert.check(shared == 0);
enter(sym, this);
}
public void enter(Symbol sym, Scope s) {
enter(sym, s, s);
}
/**
* Enter symbol sym in this scope, but mark that it comes from
* given scope `s' accessed through `origin'. The last two
* arguments are only used in import scopes.
*/
public void enter(Symbol sym, Scope s, Scope origin) {
Assert.check(shared == 0);
if (nelems * 3 >= hashMask * 2)
dble();
int hash = getIndex(sym.name);
Entry old = table[hash];
if (old == null) {
old = sentinel;
nelems++;
}
Entry e = makeEntry(sym, old, elems, s, origin);
table[hash] = e;
elems = e;
//notify listeners
for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
l.head.symbolAdded(sym, this);
}
}
Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
return new Entry(sym, shadowed, sibling, scope);
}
public interface ScopeListener {
public void symbolAdded(Symbol sym, Scope s);
public void symbolRemoved(Symbol sym, Scope s);
}
public void addScopeListener(ScopeListener sl) {
listeners = listeners.prepend(sl);
}
/** Remove symbol from this scope. Used when an inner class
* attribute tells us that the class isn't a package member.
*/
public void remove(Symbol sym) {
Assert.check(shared == 0);
Entry e = lookup(sym.name);
if (e.scope == null) return;
// remove e from table and shadowed list;
int i = getIndex(sym.name);
Entry te = table[i];
if (te == e)
table[i] = e.shadowed;
else while (true) {
if (te.shadowed == e) {
te.shadowed = e.shadowed;
break;
}
te = te.shadowed;
}
// 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;
}
//notify listeners
for (List<ScopeListener> l = listeners; l.nonEmpty(); l = l.tail) {
l.head.symbolRemoved(sym, this);
}
}
/** Enter symbol sym in this scope if not already there.
*/
public void enterIfAbsent(Symbol sym) {
Assert.check(shared == 0);
Entry e = lookup(sym.name);
while (e.scope == this && e.sym.kind != sym.kind) e = e.next();
if (e.scope != this) enter(sym);
}
/** Given a class, is there already a class with same fully
* qualified name in this (import) scope?
*/
public boolean includes(Symbol c) {
for (Scope.Entry e = lookup(c.name);
e.scope == this;
e = e.next()) {
if (e.sym == c) return true;
}
return false;
}
static final Filter<Symbol> noFilter = new Filter<Symbol>() {
public boolean accepts(Symbol s) {
return true;
}
};
/** Return the entry associated with given name, starting in
* this scope and proceeding outwards. If no entry was found,
* return the sentinel, which is characterized by having a null in
* both its scope and sym fields, whereas both fields are non-null
* for regular entries.
*/
public Entry lookup(Name name) {
return lookup(name, noFilter);
}
public Entry lookup(Name name, Filter<Symbol> sf) {
Entry e = table[getIndex(name)];
if (e == null || e == sentinel)
return sentinel;
while (e.scope != null && (e.sym.name != name || !sf.accepts(e.sym)))
e = e.shadowed;
return e;
}
/*void dump (java.io.PrintStream out) {
out.println(this);
for (int l=0; l < table.length; l++) {
Entry le = table[l];
out.print("#"+l+": ");
if (le==sentinel) out.println("sentinel");
else if(le == null) out.println("null");
else out.println(""+le+" s:"+le.sym);
}
}*/
/** Look for slot in the table.
* We use open addressing with double hashing.
*/
int getIndex (Name name) {
int h = name.hashCode();
int i = h & hashMask;
// The expression below is always odd, so it is guaranteed
// to be mutually prime with table.length, a power of 2.
int x = hashMask - ((h + (h >> 16)) << 1);
int d = -1; // Index of a deleted item.
for (;;) {
Entry e = table[i];
if (e == null)
return d >= 0 ? d : i;
if (e == sentinel) {
// We have to keep searching even if we see a deleted item.
// However, remember the index in case we fail to find the name.
if (d < 0)
d = i;
} else if (e.sym.name == name)
return i;
i = (i + x) & hashMask;
}
}
public Iterable<Symbol> getElements() {
return getElements(noFilter);
}
public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
return new Iterable<Symbol>() {
public Iterator<Symbol> iterator() {
return new Iterator<Symbol>() {
private Scope currScope = Scope.this;
private Scope.Entry currEntry = elems;
{
update();
}
public boolean hasNext() {
return currEntry != null;
}
public Symbol next() {
Symbol sym = (currEntry == null ? null : currEntry.sym);
if (currEntry != null) {
currEntry = currEntry.sibling;
}
update();
return sym;
}
public void remove() {
throw new UnsupportedOperationException();
}
private void update() {
skipToNextMatchingEntry();
while (currEntry == null && currScope.next != null) {
currScope = currScope.next;
currEntry = currScope.elems;
skipToNextMatchingEntry();
}
}
void skipToNextMatchingEntry() {
while (currEntry != null && !sf.accepts(currEntry.sym)) {
currEntry = currEntry.sibling;
}
}
};
}
};
}
public Iterable<Symbol> getElementsByName(Name name) {
return getElementsByName(name, noFilter);
}
public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) {
return new Iterable<Symbol>() {
public Iterator<Symbol> iterator() {
return new Iterator<Symbol>() {
Scope.Entry currentEntry = lookup(name, sf);
public boolean hasNext() {
return currentEntry.scope != null;
}
public Symbol next() {
Scope.Entry prevEntry = currentEntry;
currentEntry = currentEntry.next(sf);
return prevEntry.sym;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
};
}
public String toString() {
StringBuilder result = new StringBuilder();
result.append("Scope[");
for (Scope s = this; s != null ; s = s.next) {
if (s != this) result.append(" | ");
for (Entry e = s.elems; e != null; e = e.sibling) {
if (e != s.elems) result.append(", ");
result.append(e.sym);
}
}
result.append("]");
return result.toString();
}
/** A class for scope entries.
*/
public static class Entry {
/** The referenced symbol.
* sym == null iff this == sentinel
*/
public Symbol sym;
/** An entry with the same hash code, or sentinel.
*/
private Entry shadowed;
/** Next entry in same scope.
*/
public Entry sibling;
/** The entry's scope.
* scope == null iff this == sentinel
* for an entry in an import scope, this is the scope
* where the entry came from (i.e. was imported from).
*/
public Scope scope;
public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) {
this.sym = sym;
this.shadowed = shadowed;
this.sibling = sibling;
this.scope = scope;
}
/** Return next entry with the same name as this entry, proceeding
* outwards if not found in this scope.
*/
public Entry next() {
return shadowed;
}
public Entry next(Filter<Symbol> sf) {
if (shadowed.sym == null || sf.accepts(shadowed.sym)) return shadowed;
else return shadowed.next(sf);
}
public Scope getOrigin() {
// The origin is only recorded for import scopes. For all
// other scope entries, the "enclosing" type is available
// from other sources. See Attr.visitSelect and
// Attr.visitIdent. Rather than throwing an assertion
// error, we return scope which will be the same as origin
// in many cases.
return scope;
}
}
public static class ImportScope extends Scope {
public ImportScope(Symbol owner) {
super(owner);
}
@Override
Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
return new ImportEntry(sym, shadowed, sibling, scope, origin);
}
static class ImportEntry extends Entry {
private Scope origin;
ImportEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) {
super(sym, shadowed, sibling, scope);
this.origin = origin;
}
@Override
public Scope getOrigin() { return origin; }
}
}
public static class StarImportScope extends ImportScope implements ScopeListener {
public StarImportScope(Symbol owner) {
super(owner);
}
public void importAll (Scope fromScope) {
for (Scope.Entry e = fromScope.elems; e != null; e = e.sibling) {
if (e.sym.kind == Kinds.TYP && !includes(e.sym))
enter(e.sym, fromScope);
}
// Register to be notified when imported items are removed
fromScope.addScopeListener(this);
}
public void symbolRemoved(Symbol sym, Scope s) {
remove(sym);
}
public void symbolAdded(Symbol sym, Scope s) { }
}
/** An empty scope, into which you can't place anything. Used for
* the scope for a variable initializer.
*/
public static class DelegatedScope extends Scope {
Scope delegatee;
public static final Entry[] emptyTable = new Entry[0];
public DelegatedScope(Scope outer) {
super(outer, outer.owner, emptyTable);
delegatee = outer;
}
public Scope dup() {
return new DelegatedScope(next);
}
public Scope dupUnshared() {
return new DelegatedScope(next);
}
public Scope leave() {
return next;
}
public void enter(Symbol sym) {
// only anonymous classes could be put here
}
public void enter(Symbol sym, Scope s) {
// only anonymous classes could be put here
}
public void remove(Symbol sym) {
throw new AssertionError(sym);
}
public Entry lookup(Name name) {
return delegatee.lookup(name);
}
}
/** A class scope adds capabilities to keep track of changes in related
* class scopes - this allows client to realize whether a class scope
* has changed, either directly (because a new member has been added/removed
* to this scope) or indirectly (i.e. because a new member has been
* added/removed into a supertype scope)
*/
public static class CompoundScope extends Scope implements ScopeListener {
public static final Entry[] emptyTable = new Entry[0];
private List<Scope> subScopes = List.nil();
private int mark = 0;
public CompoundScope(Symbol owner) {
super(null, owner, emptyTable);
}
public void addSubScope(Scope that) {
if (that != null) {
subScopes = subScopes.prepend(that);
that.addScopeListener(this);
mark++;
for (ScopeListener sl : listeners) {
sl.symbolAdded(null, this); //propagate upwards in case of nested CompoundScopes
}
}
}
public void symbolAdded(Symbol sym, Scope s) {
mark++;
for (ScopeListener sl : listeners) {
sl.symbolAdded(sym, s);
}
}
public void symbolRemoved(Symbol sym, Scope s) {
mark++;
for (ScopeListener sl : listeners) {
sl.symbolRemoved(sym, s);
}
}
public int getMark() {
return mark;
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("CompoundScope{");
String sep = "";
for (Scope s : subScopes) {
buf.append(sep);
buf.append(s);
sep = ",";
}
buf.append("}");
return buf.toString();
}
@Override
public Iterable<Symbol> getElements(final Filter<Symbol> sf) {
return new Iterable<Symbol>() {
public Iterator<Symbol> iterator() {
return new CompoundScopeIterator(subScopes) {
Iterator<Symbol> nextIterator(Scope s) {
return s.getElements(sf).iterator();
}
};
}
};
}
@Override
public Iterable<Symbol> getElementsByName(final Name name, final Filter<Symbol> sf) {
return new Iterable<Symbol>() {
public Iterator<Symbol> iterator() {
return new CompoundScopeIterator(subScopes) {
Iterator<Symbol> nextIterator(Scope s) {
return s.getElementsByName(name, sf).iterator();
}
};
}
};
}
abstract class CompoundScopeIterator implements Iterator<Symbol> {
private Iterator<Symbol> currentIterator;
private List<Scope> scopesToScan;
public CompoundScopeIterator(List<Scope> scopesToScan) {
this.scopesToScan = scopesToScan;
update();
}
abstract Iterator<Symbol> nextIterator(Scope s);
public boolean hasNext() {
return currentIterator != null;
}
public Symbol next() {
Symbol sym = currentIterator.next();
if (!currentIterator.hasNext()) {
update();
}
return sym;
}
public void remove() {
throw new UnsupportedOperationException();
}
private void update() {
while (scopesToScan.nonEmpty()) {
currentIterator = nextIterator(scopesToScan.head);
scopesToScan = scopesToScan.tail;
if (currentIterator.hasNext()) return;
}
currentIterator = null;
}
}
@Override
public Entry lookup(Name name, Filter<Symbol> sf) {
throw new UnsupportedOperationException();
}
@Override
public Scope dup(Symbol newOwner) {
throw new UnsupportedOperationException();
}
@Override
public void enter(Symbol sym, Scope s, Scope origin) {
throw new UnsupportedOperationException();
}
@Override
public void remove(Symbol sym) {
throw new UnsupportedOperationException();
}
}
/** An error scope, for which the owner should be an error symbol. */
public static class ErrorScope extends Scope {
ErrorScope(Scope next, Symbol errSymbol, Entry[] table) {
super(next, /*owner=*/errSymbol, table);
}
public ErrorScope(Symbol errSymbol) {
super(errSymbol);
}
public Scope dup() {
return new ErrorScope(this, owner, table);
}
public Scope dupUnshared() {
return new ErrorScope(this, owner, table.clone());
}
public Entry lookup(Name name) {
Entry e = super.lookup(name);
if (e.scope == null)
return new Entry(owner, null, null, null);
else
return e;
}
}
}