diff options
author | Martin Odersky <odersky@gmail.com> | 2003-02-13 14:41:36 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2003-02-13 14:41:36 +0000 |
commit | 4177daab2f54bdb20c71f623296a8bb32616fd12 (patch) | |
tree | 23f08b43f3758e825d5965b336030603a65bbcf7 /sources/scalac/symtab/Scope.java | |
parent | 33d6e170c97ca7b2f991896a0729941a7240b6d6 (diff) | |
download | scala-4177daab2f54bdb20c71f623296a8bb32616fd12.tar.gz scala-4177daab2f54bdb20c71f623296a8bb32616fd12.tar.bz2 scala-4177daab2f54bdb20c71f623296a8bb32616fd12.zip |
Initial version.
Diffstat (limited to 'sources/scalac/symtab/Scope.java')
-rw-r--r-- | sources/scalac/symtab/Scope.java | 306 |
1 files changed, 306 insertions, 0 deletions
diff --git a/sources/scalac/symtab/Scope.java b/sources/scalac/symtab/Scope.java new file mode 100644 index 0000000000..3bd22f51ed --- /dev/null +++ b/sources/scalac/symtab/Scope.java @@ -0,0 +1,306 @@ + /* ____ ____ ____ ____ ______ *\ +** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala ** +** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL ** +** /_____/\____/\___/\____/____/ ** +** ** +** $Id$ +\* */ + +package scalac.symtab; + +import scalac.util.*; +import scalac.ApplicationError; + +public class Scope { + + public static abstract class SymbolIterator { + public abstract boolean hasNext(); + public abstract Symbol next(); + } + + /** A symbol iterator that returns all alternatives of an overloaded symbol + * instead of the overloaded symbol itself. + */ + public static class UnloadIterator extends SymbolIterator { + private SymbolIterator iterator; + private Symbol[] alternatives; + private int index; + + public UnloadIterator(SymbolIterator iterator) { + this.iterator = iterator; + this.alternatives = null; + this.index = -1; + } + + public boolean hasNext() { + return index >= 0 || iterator.hasNext(); + } + public Symbol next() { + if (index >= 0) { + Symbol symbol = alternatives[index++]; + if (index == alternatives.length) { + alternatives = null; + index = -1; + } + return symbol; + } else { + Symbol symbol = iterator.next(); + switch (symbol.type()) { + case OverloadedType(Symbol[] alts, _): + alternatives = alts; + index = 0; + return next(); + default: + return symbol; + } + } + } + } + + public static class Entry { + + /** the absent entry + */ + public static final Entry NONE = new Entry(); + + /** the symbol of the entry (this is the symbol containing the name) + */ + public Symbol sym; + + /** the next entry in the hash bucket + */ + Entry tail; + + /** the next entry in this scope + */ + public Entry next; + + /** The owner of the entry; + */ + public Scope owner; + + Entry(Symbol sym, Scope owner) { + if (sym == null) throw new ApplicationError(); + this.sym = sym; + this.owner = owner; + this.next = owner.elems; + owner.elems = this; + } + + private Entry() { + this.sym = Symbol.NONE; + } + + public Entry setSymbol(Symbol sym) { + this.sym = sym; + owner.elemsCache = null; + return this; + } + + public int hashCode() { + return sym.name.index; + } + + public String toString() { + return sym.toString(); + } + } + + /** all elements of this scope + */ + public Entry elems; + + /** the hash table + */ + private Entry[] hashtable; + + /** a cache for all elements, to be used by symbol iterator. + */ + private Symbol[] elemsCache = null; + + /** size and mask of hash tables + * todo: make hashtables grow? + */ + private final int HASHSIZE = 0x80; + private final int HASHMASK = 0x7f; + + /** the threshold number of entries from which a hashtable is constructed. + */ + private final int MIN_HASH = 6; + + /** construct a new name space + */ + public Scope() { + this.elems = Entry.NONE; + } + + public Scope(Entry elems) { + this.elems = elems; + if (size() >= MIN_HASH) createHash(); + } + + public Scope(Scope base) { + this.elems = base.elems; + if (base.hashtable != null) { + this.hashtable = new Entry[HASHSIZE]; + for (int i = 0; i < HASHSIZE; i++) + hashtable[i] = base.hashtable[i]; + } + } + + public Scope(Symbol[] members) { + this(); + for (int i = 0; i < members.length; i++) + enter(members[i]); + } + + /** the number of entries in this scope + */ + int size() { + int s = 0; + for (Entry e = elems; e != Entry.NONE; e = e.next) s++; + return s; + } + + private Scope enter(Entry e) { + elems = e; + elemsCache = null; + if (hashtable != null) { + int i = e.sym.name.index & HASHMASK; + elems.tail = hashtable[i]; + hashtable[i] = elems; + } else if (size() >= MIN_HASH) { + createHash(); + } + return this; + } + + /** enter a symbol + */ + public Scope enter(Symbol sym) { + return enter(new Entry(sym, this)); + } + + public Scope enterOrOverload(Symbol sym) { + Entry e = lookupEntry(sym.name); + if (e.owner == this && (sym.flags & Modifiers.PRIVATE) == 0) { + e.setSymbol(e.sym.overloadWith(sym)); + return this; + } else { + return enter(sym); + } + } + + private void createHash() { + hashtable = new Entry[HASHSIZE]; + for (int i = 0; i < HASHSIZE; i++) + hashtable[i] = Entry.NONE; + enterInHash(elems); + } + + private void enterInHash(Entry e) { + if (e != Entry.NONE) { + enterInHash(e.next); + int i = e.sym.name.index & HASHMASK; + e.tail = hashtable[i]; + hashtable[i] = e; + } + } + + /** remove entry + */ + public void unlink(Entry e) { + Entry e1 = hashtable[e.sym.name.index & HASHMASK]; + if (e1 == e) { + hashtable[e.sym.name.index & HASHMASK] = e.tail; + } else { + while (e1.tail != e) e1 = e1.tail; + } + if (elems == e) { + elems = e.next; + } else { + e1 = elems; + while (e1.next != e) e1 = e1.next; + e1.next = e.next; + } + elemsCache = null; + } + + /** lookup a symbol + */ + public Symbol lookup(Name name) { + return lookupEntry(name).sym; + } + + /** lookup a symbol entry. + */ + public Entry lookupEntry(Name name) { + Entry e; + if (hashtable != null) { + e = hashtable[name.index & HASHMASK]; + while (e != Entry.NONE && e.sym.name != name) e = e.tail; + } else { + e = elems; + while (e != Entry.NONE && e.sym.name != name) e = e.next; + } + return e; + } + + /** return all symbols as an array, + * in the order they were entered in this scope. + */ + public Symbol[] elements() { + if (elemsCache == null) { + int s = size(); + elemsCache = new Symbol[s]; + for (Entry e = elems; e != Entry.NONE; e = e.next) + elemsCache[--s] = e.sym; + } + return elemsCache; + } + + /** return all symbols as an iterator, + * in the order they were entered in this scope. + */ + public SymbolIterator iterator() { return new MySymbols(); } + + class MySymbols extends SymbolIterator { + + private int index; + MySymbols() { + elements(); + index = 0; + } + + public boolean hasNext() { + return index < elemsCache.length; + } + + public Symbol next() { + return elemsCache[index++]; + } + } + + public String toString() { + StringBuffer str = new StringBuffer("{"); + SymbolIterator it = iterator(); + while (it.hasNext()) { + str.append("\n " + it.next().defString()); + } + str.append("}"); + return str.toString(); + } + + public String simpleToString() { + StringBuffer str = new StringBuffer("{"); + SymbolIterator it = iterator(); + while (it.hasNext()) { + str.append("\n " + it.next().name); + } + str.append("}"); + return str.toString(); + } + + public static Scope EMPTY = new Scope(); +} + |