duke@1: /* ohair@554: * Copyright (c) 1999, 2008, Oracle and/or its affiliates. All rights reserved. duke@1: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@1: * duke@1: * This code is free software; you can redistribute it and/or modify it duke@1: * under the terms of the GNU General Public License version 2 only, as ohair@554: * published by the Free Software Foundation. Oracle designates this duke@1: * particular file as subject to the "Classpath" exception as provided ohair@554: * by Oracle in the LICENSE file that accompanied this code. duke@1: * duke@1: * This code is distributed in the hope that it will be useful, but WITHOUT duke@1: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@1: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@1: * version 2 for more details (a copy is included in the LICENSE file that duke@1: * accompanied this code). duke@1: * duke@1: * You should have received a copy of the GNU General Public License version duke@1: * 2 along with this work; if not, write to the Free Software Foundation, duke@1: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@1: * ohair@554: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA ohair@554: * or visit www.oracle.com if you need additional information or have any ohair@554: * questions. duke@1: */ duke@1: duke@1: package com.sun.tools.javac.code; duke@1: duke@1: import com.sun.tools.javac.util.*; duke@1: import java.util.Iterator; duke@1: duke@1: /** A scope represents an area of visibility in a Java program. The duke@1: * Scope class is a container for symbols which provides duke@1: * efficient access to symbols given their names. Scopes are implemented duke@1: * as hash tables. Scopes can be nested; the next field of a scope points duke@1: * to its next outer scope. Nested scopes can share their hash tables. duke@1: * duke@1: *

This is NOT part of any API supported by Sun Microsystems. If duke@1: * you write code that depends on this, you do so at your own risk. duke@1: * This code and its internal interfaces are subject to change or duke@1: * deletion without notice. duke@1: */ duke@1: public class Scope { duke@1: duke@1: /** The number of scopes that share this scope's hash table. duke@1: */ duke@1: private int shared; duke@1: duke@1: /** Next enclosing scope (with whom this scope may share a hashtable) duke@1: */ duke@1: public Scope next; duke@1: duke@1: /** The scope's owner. duke@1: */ duke@1: public Symbol owner; duke@1: duke@1: /** A hash table for the scope's entries. duke@1: */ duke@1: public Entry[] table; duke@1: duke@1: /** Mask for hash codes, always equal to (table.length - 1). duke@1: */ duke@1: int hashMask; duke@1: duke@1: /** A linear list that also contains all entries in duke@1: * reverse order of appearance (i.e later entries are pushed on top). duke@1: */ duke@1: public Entry elems; duke@1: duke@1: /** The number of elements in this scope. duke@1: */ duke@1: public int nelems = 0; duke@1: duke@1: /** Every hash bucket is a list of Entry's which ends in sentinel. duke@1: */ duke@1: private static final Entry sentinel = new Entry(null, null, null, null); duke@1: duke@1: /** The hash table's initial size. duke@1: */ duke@1: private static final int INITIAL_SIZE = 0x10; duke@1: duke@1: /** A value for the empty scope. duke@1: */ duke@1: public static final Scope emptyScope = new Scope(null, null, new Entry[]{}); duke@1: duke@1: /** Construct a new scope, within scope next, with given owner, using duke@1: * given table. The table's length must be an exponent of 2. duke@1: */ duke@1: Scope(Scope next, Symbol owner, Entry[] table) { duke@1: this.next = next; duke@1: assert emptyScope == null || owner != null; duke@1: this.owner = owner; duke@1: this.table = table; duke@1: this.hashMask = table.length - 1; duke@1: this.elems = null; duke@1: this.nelems = 0; duke@1: this.shared = 0; duke@1: } duke@1: duke@1: /** Construct a new scope, within scope next, with given owner, duke@1: * using a fresh table of length INITIAL_SIZE. duke@1: */ duke@1: public Scope(Symbol owner) { duke@1: this(null, owner, new Entry[INITIAL_SIZE]); duke@1: for (int i = 0; i < INITIAL_SIZE; i++) table[i] = sentinel; duke@1: } duke@1: duke@1: /** Construct a fresh scope within this scope, with same owner, duke@1: * which shares its table with the outer scope. Used in connection with duke@1: * method leave if scope access is stack-like in order to avoid allocation duke@1: * of fresh tables. duke@1: */ duke@1: public Scope dup() { duke@1: Scope result = new Scope(this, this.owner, this.table); duke@1: shared++; duke@1: // System.out.println("====> duping scope " + this.hashCode() + " owned by " + this.owner + " to " + result.hashCode()); duke@1: // new Error().printStackTrace(System.out); duke@1: return result; duke@1: } duke@1: duke@1: /** Construct a fresh scope within this scope, with new owner, duke@1: * which shares its table with the outer scope. Used in connection with duke@1: * method leave if scope access is stack-like in order to avoid allocation duke@1: * of fresh tables. duke@1: */ duke@1: public Scope dup(Symbol newOwner) { duke@1: Scope result = new Scope(this, newOwner, this.table); duke@1: shared++; duke@1: // System.out.println("====> duping scope " + this.hashCode() + " owned by " + newOwner + " to " + result.hashCode()); duke@1: // new Error().printStackTrace(System.out); duke@1: return result; duke@1: } duke@1: duke@1: /** Construct a fresh scope within this scope, with same owner, duke@1: * with a new hash table, whose contents initially are those of duke@1: * the table of its outer scope. duke@1: */ duke@1: public Scope dupUnshared() { duke@1: return new Scope(this, this.owner, this.table.clone()); duke@1: } duke@1: duke@1: /** Remove all entries of this scope from its table, if shared duke@1: * with next. duke@1: */ duke@1: public Scope leave() { duke@1: assert shared == 0; duke@1: if (table != next.table) return next; duke@1: while (elems != null) { jjg@113: int hash = elems.sym.name.hashCode() & hashMask; duke@1: Entry e = table[hash]; duke@1: assert e == elems : elems.sym; duke@1: table[hash] = elems.shadowed; duke@1: elems = elems.sibling; duke@1: } duke@1: assert next.shared > 0; duke@1: next.shared--; duke@1: // System.out.println("====> leaving scope " + this.hashCode() + " owned by " + this.owner + " to " + next.hashCode()); duke@1: // new Error().printStackTrace(System.out); duke@1: return next; duke@1: } duke@1: duke@1: /** Double size of hash table. duke@1: */ duke@1: private void dble() { duke@1: assert shared == 0; duke@1: Entry[] oldtable = table; duke@1: Entry[] newtable = new Entry[oldtable.length * 2]; duke@1: for (Scope s = this; s != null; s = s.next) { duke@1: if (s.table == oldtable) { duke@1: assert s == this || s.shared != 0; duke@1: s.table = newtable; duke@1: s.hashMask = newtable.length - 1; duke@1: } duke@1: } duke@1: for (int i = 0; i < newtable.length; i++) newtable[i] = sentinel; duke@1: for (int i = 0; i < oldtable.length; i++) copy(oldtable[i]); duke@1: } duke@1: duke@1: /** Copy the given entry and all entries shadowed by it to table duke@1: */ duke@1: private void copy(Entry e) { duke@1: if (e.sym != null) { duke@1: copy(e.shadowed); jjg@113: int hash = e.sym.name.hashCode() & hashMask; duke@1: e.shadowed = table[hash]; duke@1: table[hash] = e; duke@1: } duke@1: } duke@1: duke@1: /** Enter symbol sym in this scope. duke@1: */ duke@1: public void enter(Symbol sym) { duke@1: assert shared == 0; duke@1: enter(sym, this); duke@1: } duke@1: duke@1: public void enter(Symbol sym, Scope s) { duke@1: enter(sym, s, s); duke@1: } duke@1: duke@1: /** duke@1: * Enter symbol sym in this scope, but mark that it comes from duke@1: * given scope `s' accessed through `origin'. The last two duke@1: * arguments are only used in import scopes. duke@1: */ duke@1: public void enter(Symbol sym, Scope s, Scope origin) { duke@1: assert shared == 0; duke@1: // Temporarily disabled (bug 6460352): duke@1: // if (nelems * 3 >= hashMask * 2) dble(); jjg@113: int hash = sym.name.hashCode() & hashMask; duke@1: Entry e = makeEntry(sym, table[hash], elems, s, origin); duke@1: table[hash] = e; duke@1: elems = e; duke@1: nelems++; duke@1: } duke@1: duke@1: Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { duke@1: return new Entry(sym, shadowed, sibling, scope); duke@1: } duke@1: duke@1: /** Remove symbol from this scope. Used when an inner class duke@1: * attribute tells us that the class isn't a package member. duke@1: */ duke@1: public void remove(Symbol sym) { duke@1: assert shared == 0; duke@1: Entry e = lookup(sym.name); duke@1: while (e.scope == this && e.sym != sym) e = e.next(); duke@1: if (e.scope == null) return; duke@1: duke@1: // remove e from table and shadowed list; jjg@113: Entry te = table[sym.name.hashCode() & hashMask]; duke@1: if (te == e) jjg@113: table[sym.name.hashCode() & hashMask] = e.shadowed; duke@1: else while (true) { duke@1: if (te.shadowed == e) { duke@1: te.shadowed = e.shadowed; duke@1: break; duke@1: } duke@1: te = te.shadowed; duke@1: } duke@1: duke@1: // remove e from elems and sibling list duke@1: te = elems; duke@1: if (te == e) duke@1: elems = e.sibling; duke@1: else while (true) { duke@1: if (te.sibling == e) { duke@1: te.sibling = e.sibling; duke@1: break; duke@1: } duke@1: te = te.sibling; duke@1: } duke@1: } duke@1: duke@1: /** Enter symbol sym in this scope if not already there. duke@1: */ duke@1: public void enterIfAbsent(Symbol sym) { duke@1: assert shared == 0; duke@1: Entry e = lookup(sym.name); duke@1: while (e.scope == this && e.sym.kind != sym.kind) e = e.next(); duke@1: if (e.scope != this) enter(sym); duke@1: } duke@1: duke@1: /** Given a class, is there already a class with same fully duke@1: * qualified name in this (import) scope? duke@1: */ duke@1: public boolean includes(Symbol c) { duke@1: for (Scope.Entry e = lookup(c.name); duke@1: e.scope == this; duke@1: e = e.next()) { duke@1: if (e.sym == c) return true; duke@1: } duke@1: return false; duke@1: } duke@1: duke@1: /** Return the entry associated with given name, starting in duke@1: * this scope and proceeding outwards. If no entry was found, duke@1: * return the sentinel, which is characterized by having a null in duke@1: * both its scope and sym fields, whereas both fields are non-null duke@1: * for regular entries. duke@1: */ duke@1: public Entry lookup(Name name) { jjg@113: Entry e = table[name.hashCode() & hashMask]; duke@1: while (e.scope != null && e.sym.name != name) duke@1: e = e.shadowed; duke@1: return e; duke@1: } duke@1: duke@1: public Iterable getElements() { duke@1: return new Iterable() { duke@1: public Iterator iterator() { duke@1: return new Iterator() { duke@1: private Scope currScope = Scope.this; duke@1: private Scope.Entry currEntry = elems; duke@1: { duke@1: update(); duke@1: } duke@1: duke@1: public boolean hasNext() { duke@1: return currEntry != null; duke@1: } duke@1: duke@1: public Symbol next() { duke@1: Symbol sym = (currEntry == null ? null : currEntry.sym); duke@1: currEntry = currEntry.sibling; duke@1: update(); duke@1: return sym; duke@1: } duke@1: duke@1: public void remove() { duke@1: throw new UnsupportedOperationException(); duke@1: } duke@1: duke@1: private void update() { duke@1: while (currEntry == null && currScope.next != null) { duke@1: currScope = currScope.next; duke@1: currEntry = currScope.elems; duke@1: } duke@1: } duke@1: }; duke@1: } duke@1: }; duke@1: duke@1: } duke@1: duke@1: public String toString() { duke@1: StringBuilder result = new StringBuilder(); duke@1: result.append("Scope["); duke@1: for (Scope s = this; s != null ; s = s.next) { duke@1: if (s != this) result.append(" | "); duke@1: for (Entry e = s.elems; e != null; e = e.sibling) { duke@1: if (e != s.elems) result.append(", "); duke@1: result.append(e.sym); duke@1: } duke@1: } duke@1: result.append("]"); duke@1: return result.toString(); duke@1: } duke@1: duke@1: /** A class for scope entries. duke@1: */ duke@1: public static class Entry { duke@1: duke@1: /** The referenced symbol. duke@1: * sym == null iff this == sentinel duke@1: */ duke@1: public Symbol sym; duke@1: duke@1: /** An entry with the same hash code, or sentinel. duke@1: */ duke@1: private Entry shadowed; duke@1: duke@1: /** Next entry in same scope. duke@1: */ duke@1: public Entry sibling; duke@1: duke@1: /** The entry's scope. duke@1: * scope == null iff this == sentinel duke@1: * for an entry in an import scope, this is the scope duke@1: * where the entry came from (i.e. was imported from). duke@1: */ duke@1: public Scope scope; duke@1: duke@1: public Entry(Symbol sym, Entry shadowed, Entry sibling, Scope scope) { duke@1: this.sym = sym; duke@1: this.shadowed = shadowed; duke@1: this.sibling = sibling; duke@1: this.scope = scope; duke@1: } duke@1: duke@1: /** Return next entry with the same name as this entry, proceeding duke@1: * outwards if not found in this scope. duke@1: */ duke@1: public Entry next() { duke@1: Entry e = shadowed; duke@1: while (e.scope != null && e.sym.name != sym.name) duke@1: e = e.shadowed; duke@1: return e; duke@1: } duke@1: duke@1: public Scope getOrigin() { duke@1: // The origin is only recorded for import scopes. For all duke@1: // other scope entries, the "enclosing" type is available duke@1: // from other sources. See Attr.visitSelect and duke@1: // Attr.visitIdent. Rather than throwing an assertion duke@1: // error, we return scope which will be the same as origin duke@1: // in many cases. duke@1: return scope; duke@1: } duke@1: } duke@1: duke@1: public static class ImportScope extends Scope { duke@1: duke@1: public ImportScope(Symbol owner) { duke@1: super(owner); duke@1: } duke@1: duke@1: @Override duke@1: Entry makeEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { duke@1: return new ImportEntry(sym, shadowed, sibling, scope, origin); duke@1: } duke@1: duke@1: public Entry lookup(Name name) { jjg@113: Entry e = table[name.hashCode() & hashMask]; duke@1: while (e.scope != null && duke@1: (e.sym.name != name || duke@1: /* Since an inner class will show up in package and duke@1: * import scopes until its inner class attribute has duke@1: * been processed, we have to weed it out here. This duke@1: * is done by comparing the owners of the entry's duke@1: * scope and symbol fields. The scope field's owner duke@1: * points to where the class originally was imported duke@1: * from. The symbol field's owner points to where the duke@1: * class is situated now. This can change when an duke@1: * inner class is read (see ClassReader.enterClass). duke@1: * By comparing the two fields we make sure that we do duke@1: * not accidentally import an inner class that started duke@1: * life as a flat class in a package. */ duke@1: e.sym.owner != e.scope.owner)) duke@1: e = e.shadowed; duke@1: return e; duke@1: } duke@1: duke@1: static class ImportEntry extends Entry { duke@1: private Scope origin; duke@1: duke@1: ImportEntry(Symbol sym, Entry shadowed, Entry sibling, Scope scope, Scope origin) { duke@1: super(sym, shadowed, sibling, scope); duke@1: this.origin = origin; duke@1: } duke@1: public Entry next() { duke@1: Entry e = super.shadowed; duke@1: while (e.scope != null && duke@1: (e.sym.name != sym.name || duke@1: e.sym.owner != e.scope.owner)) // see lookup() duke@1: e = e.shadowed; duke@1: return e; duke@1: } duke@1: duke@1: @Override duke@1: public Scope getOrigin() { return origin; } duke@1: } duke@1: } duke@1: duke@1: /** An empty scope, into which you can't place anything. Used for duke@1: * the scope for a variable initializer. duke@1: */ duke@1: public static class DelegatedScope extends Scope { duke@1: Scope delegatee; duke@1: public static final Entry[] emptyTable = new Entry[0]; duke@1: duke@1: public DelegatedScope(Scope outer) { duke@1: super(outer, outer.owner, emptyTable); duke@1: delegatee = outer; duke@1: } duke@1: public Scope dup() { duke@1: return new DelegatedScope(next); duke@1: } duke@1: public Scope dupUnshared() { duke@1: return new DelegatedScope(next); duke@1: } duke@1: public Scope leave() { duke@1: return next; duke@1: } duke@1: public void enter(Symbol sym) { duke@1: // only anonymous classes could be put here duke@1: } duke@1: public void enter(Symbol sym, Scope s) { duke@1: // only anonymous classes could be put here duke@1: } duke@1: public void remove(Symbol sym) { duke@1: throw new AssertionError(sym); duke@1: } duke@1: public Entry lookup(Name name) { duke@1: return delegatee.lookup(name); duke@1: } duke@1: } duke@1: duke@1: /** An error scope, for which the owner should be an error symbol. */ duke@1: public static class ErrorScope extends Scope { duke@1: ErrorScope(Scope next, Symbol errSymbol, Entry[] table) { duke@1: super(next, /*owner=*/errSymbol, table); duke@1: } duke@1: public ErrorScope(Symbol errSymbol) { duke@1: super(errSymbol); duke@1: } duke@1: public Scope dup() { duke@1: return new ErrorScope(this, owner, table); duke@1: } duke@1: public Scope dupUnshared() { duke@1: return new ErrorScope(this, owner, table.clone()); duke@1: } duke@1: public Entry lookup(Name name) { duke@1: Entry e = super.lookup(name); duke@1: if (e.scope == null) duke@1: return new Entry(owner, null, null, null); duke@1: else duke@1: return e; duke@1: } duke@1: } duke@1: }