duke@1: /* xdono@117: * Copyright 1999-2008 Sun Microsystems, Inc. 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 duke@1: * published by the Free Software Foundation. Sun designates this duke@1: * particular file as subject to the "Classpath" exception as provided duke@1: * by Sun 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: * duke@1: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, duke@1: * CA 95054 USA or visit www.sun.com if you need additional information or duke@1: * have any 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