diff options
author | Paul Phillips <paulp@improving.org> | 2011-05-16 21:11:17 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2011-05-16 21:11:17 +0000 |
commit | fff93cd0497916708e6a9a9207660623ed2e50ee (patch) | |
tree | 22ade6ccc3605c91c2f227ace6536fd94db13bf9 /src/compiler/scala/reflect/common/Scopes.scala | |
parent | 1e5194b41cdc5563237381b80a9f948abbf96e6e (diff) | |
download | scala-fff93cd0497916708e6a9a9207660623ed2e50ee.tar.gz scala-fff93cd0497916708e6a9a9207660623ed2e50ee.tar.bz2 scala-fff93cd0497916708e6a9a9207660623ed2e50ee.zip |
And the remainder of the scala.reflect refactor...
And the remainder of the scala.reflect refactoring (think of it like a
"balloon payment") no review.
Diffstat (limited to 'src/compiler/scala/reflect/common/Scopes.scala')
-rw-r--r-- | src/compiler/scala/reflect/common/Scopes.scala | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/src/compiler/scala/reflect/common/Scopes.scala b/src/compiler/scala/reflect/common/Scopes.scala new file mode 100644 index 0000000000..4fbfa1760e --- /dev/null +++ b/src/compiler/scala/reflect/common/Scopes.scala @@ -0,0 +1,326 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2011 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.reflect +package common + +trait Scopes { self: SymbolTable => + + class ScopeEntry(val sym: Symbol, val owner: Scope) { + /** the next entry in the hash bucket + */ + var tail: ScopeEntry = null + + /** the next entry in this scope + */ + var next: ScopeEntry = null + + override def hashCode(): Int = sym.name.start + override def toString(): String = sym.toString() + } + + /** + * @param sym ... + * @param owner ... + * @return ... + */ + private def newScopeEntry(sym: Symbol, owner: Scope): ScopeEntry = { + val e = new ScopeEntry(sym, owner) + e.next = owner.elems + owner.elems = e + e + } + + class Scope(initElems: ScopeEntry) extends Iterable[Symbol] { + + var elems: ScopeEntry = initElems + + /** The number of times this scope is nested in another + */ + private var nestinglevel = 0 + + /** the hash table + */ + private var hashtable: Array[ScopeEntry] = null + + /** a cache for all elements, to be used by symbol iterator. + */ + private var elemsCache: List[Symbol] = null + + /** size and mask of hash tables + * todo: make hashtables grow? + */ + private val HASHSIZE = 0x80 + private val HASHMASK = 0x7f + + /** the threshold number of entries from which a hashtable is constructed. + */ + private val MIN_HASH = 8 + + if (size >= MIN_HASH) createHash() + + def this() = this(null: ScopeEntry) + + def this(base: Scope) = { + this(base.elems) + nestinglevel = base.nestinglevel + 1 + } + + def this(decls: List[Symbol]) = { + this() + decls foreach enter + } + + /** Returns a new scope with the same content as this one. */ + def cloneScope: Scope = { + val clone = new Scope() + this.toList foreach (clone enter _) + clone + } + + /** is the scope empty? */ + override def isEmpty: Boolean = elems eq null + + /** the number of entries in this scope */ + override def size: Int = { + var s = 0 + var e = elems + while (e ne null) { + s += 1 + e = e.next + } + s + } + + /** enter a scope entry + * + * @param e ... + */ + def enter(e: ScopeEntry) { + elemsCache = null + if (hashtable ne null) { + val i = e.sym.name.start & HASHMASK + elems.tail = hashtable(i) + hashtable(i) = elems + } else if (size >= MIN_HASH) { + createHash() + } + } + + /** enter a symbol + * + * @param sym ... + */ + def enter(sym: Symbol): Symbol = { enter(newScopeEntry(sym, this)); sym } + + /** enter a symbol, asserting that no symbol with same name exists in scope + * + * @param sym ... + */ + def enterUnique(sym: Symbol) { + assert(lookup(sym.name) == NoSymbol) + enter(sym) + } + + private def createHash() { + hashtable = new Array[ScopeEntry](HASHSIZE) + enterInHash(elems) + } + + private def enterInHash(e: ScopeEntry) { + if (e ne null) { + enterInHash(e.next) + val i = e.sym.name.start & HASHMASK + e.tail = hashtable(i) + hashtable(i) = e + } + } + + def rehash(sym: Symbol, newname: Name) { + if (hashtable ne null) { + val index = sym.name.start & HASHMASK + var e1 = hashtable(index) + var e: ScopeEntry = null + if (e1 != null) { + if (e1.sym == sym) { + hashtable(index) = e1.tail + e = e1 + } else { + while (e1.tail != null && e1.tail.sym != sym) e1 = e1.tail + if (e1.tail != null) { + e = e1.tail + e1.tail = e.tail + } + } + } + if (e != null) { + val newindex = newname.start & HASHMASK + e.tail = hashtable(newindex) + hashtable(newindex) = e + } + } + } + + /** remove entry + * + * @param e ... + */ + def unlink(e: ScopeEntry) { + if (elems == e) { + elems = e.next + } else { + var e1 = elems + while (e1.next != e) e1 = e1.next + e1.next = e.next + } + if (hashtable ne null) { + val index = e.sym.name.start & HASHMASK + var e1 = hashtable(index) + if (e1 == e) { + hashtable(index) = e.tail + } else { + while (e1.tail != e) e1 = e1.tail; + e1.tail = e.tail + } + } + elemsCache = null + } + + /** remove symbol */ + def unlink(sym: Symbol) { + var e = lookupEntry(sym.name) + while (e ne null) { + if (e.sym == sym) unlink(e); + e = lookupNextEntry(e) + } + } + + /** lookup a symbol + * + * @param name ... + * @return ... + */ + def lookup(name: Name): Symbol = { + val e = lookupEntry(name) + if (e eq null) NoSymbol else e.sym + } + + /** Returns an iterator yielding every symbol with given name in this scope. + */ + def lookupAll(name: Name): Iterator[Symbol] = new Iterator[Symbol] { + var e = lookupEntry(name) + def hasNext: Boolean = e ne null + def next: Symbol = { val r = e.sym; e = lookupNextEntry(e); r } + } + + /** lookup a symbol entry matching given name. + * @note from Martin: I believe this is a hotspot or will be one + * in future versions of the type system. I have reverted the previous + * change to use iterators as too costly. + */ + def lookupEntry(name: Name): ScopeEntry = { + var e: ScopeEntry = null + if (hashtable ne null) { + e = hashtable(name.start & HASHMASK) + while ((e ne null) && e.sym.name != name) { + e = e.tail + } + } else { + e = elems + while ((e ne null) && e.sym.name != name) { + e = e.next + } + } + e + } + + /** lookup next entry with same name as this one + * @note from Martin: I believe this is a hotspot or will be one + * in future versions of the type system. I have reverted the previous + * change to use iterators as too costly. + */ + def lookupNextEntry(entry: ScopeEntry): ScopeEntry = { + var e = entry + if (hashtable ne null) + do { e = e.tail } while ((e ne null) && e.sym.name != entry.sym.name) + else + do { e = e.next } while ((e ne null) && e.sym.name != entry.sym.name); + e + } + + /** Return all symbols as a list in the order they were entered in this scope. + */ + override def toList: List[Symbol] = { + if (elemsCache eq null) { + elemsCache = Nil + var e = elems + while ((e ne null) && e.owner == this) { + elemsCache = e.sym :: elemsCache + e = e.next + } + } + elemsCache + } + + /** Return the nesting level of this scope, i.e. the number of times this scope + * was nested in another */ + def nestingLevel = nestinglevel + + /** Return all symbols as an iterator in the order they were entered in this scope. + */ + def iterator: Iterator[Symbol] = toList.iterator + +/* + /** Does this scope contain an entry for `sym`? + */ + def contains(sym: Symbol): Boolean = lookupAll(sym.name) contains sym + + /** A scope that contains all symbols of this scope and that also contains `sym`. + */ + def +(sym: Symbol): Scope = + if (contains(sym)) this + else { + val result = cloneScope + result enter sym + result + } + + /** A scope that contains all symbols of this scope except `sym`. + */ + def -(sym: Symbol): Scope = + if (!contains(sym)) this + else { + val result = cloneScope + result unlink sym + result + } +*/ + override def foreach[U](p: Symbol => U): Unit = toList foreach p + + override def filter(p: Symbol => Boolean): Scope = + if (!(toList forall p)) new Scope(toList filter p) else this + + override def mkString(start: String, sep: String, end: String) = + toList.map(_.defString).mkString(start, sep, end) + + override def toString(): String = mkString("Scope{\n ", ";\n ", "\n}") + + } + + def newScope: Scope = new Scope + + /** The empty scope (immutable). + */ + object EmptyScope extends Scope { + override def enter(e: ScopeEntry) { + abort("EmptyScope.enter") + } + } + + /** The error scope. + */ + class ErrorScope(owner: Symbol) extends Scope(null: ScopeEntry) +} + |