diff options
author | Paul Phillips <paulp@improving.org> | 2013-04-04 13:29:18 -0700 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2013-04-05 10:34:58 -0700 |
commit | ca2a09d2934672b16ca9a729ec57bf9211a0a01a (patch) | |
tree | 5a1d2ee649542143b0a887816172b2d6f730f855 /src/reflect | |
parent | d301a86488f944ae3a1a14ba578ac8c87e64f01d (diff) | |
download | scala-ca2a09d2934672b16ca9a729ec57bf9211a0a01a.tar.gz scala-ca2a09d2934672b16ca9a729ec57bf9211a0a01a.tar.bz2 scala-ca2a09d2934672b16ca9a729ec57bf9211a0a01a.zip |
Optimization/logic improvement in Scopes.
I rescued "isSubScope" from the innards of isSameType
and placed it on Scope.
To write a more efficient "isSameScope", I needed a size
method which wasn't O(n). I now cache the size whenever the
elemsCache is regenerated.
Diffstat (limited to 'src/reflect')
-rw-r--r-- | src/reflect/scala/reflect/internal/Scopes.scala | 48 |
1 files changed, 44 insertions, 4 deletions
diff --git a/src/reflect/scala/reflect/internal/Scopes.scala b/src/reflect/scala/reflect/internal/Scopes.scala index 850c497d4b..371eddbc4f 100644 --- a/src/reflect/scala/reflect/internal/Scopes.scala +++ b/src/reflect/scala/reflect/internal/Scopes.scala @@ -6,6 +6,8 @@ package scala.reflect package internal +import scala.annotation.tailrec + trait Scopes extends api.Scopes { self: SymbolTable => /** An ADT to represent the results of symbol name lookups. @@ -65,6 +67,11 @@ trait Scopes extends api.Scopes { self: SymbolTable => /** a cache for all elements, to be used by symbol iterator. */ private var elemsCache: List[Symbol] = null + private var cachedSize = -1 + private def flushElemsCache() { + elemsCache = null + cachedSize = -1 + } /** size and mask of hash tables * todo: make hashtables grow? @@ -86,6 +93,12 @@ trait Scopes extends api.Scopes { self: SymbolTable => /** the number of entries in this scope */ override def size: Int = { + if (cachedSize < 0) + cachedSize = directSize + + cachedSize + } + private def directSize: Int = { var s = 0 var e = elems while (e ne null) { @@ -98,7 +111,7 @@ trait Scopes extends api.Scopes { self: SymbolTable => /** enter a scope entry */ protected def enterEntry(e: ScopeEntry) { - elemsCache = null + flushElemsCache() if (hashtable ne null) enterInHash(e) else if (size >= MIN_HASH) @@ -192,7 +205,7 @@ trait Scopes extends api.Scopes { self: SymbolTable => e1.tail = e.tail } } - elemsCache = null + flushElemsCache() } /** remove symbol */ @@ -304,16 +317,43 @@ trait Scopes extends api.Scopes { self: SymbolTable => e } + /** TODO - we can test this more efficiently than checking isSubScope + * in both directions. However the size test might be enough to quickly + * rule out most failures. + */ + def isSameScope(other: Scope) = ( + (size == other.size) // optimization - size is cached + && (this isSubScope other) + && (other isSubScope this) + ) + + def isSubScope(other: Scope) = { + def scopeContainsSym(sym: Symbol): Boolean = { + @tailrec def entryContainsSym(e: ScopeEntry): Boolean = e match { + case null => false + case _ => + val comparableInfo = sym.info.substThis(sym.owner, e.sym.owner) + (e.sym.info =:= comparableInfo) || entryContainsSym(lookupNextEntry(e)) + } + entryContainsSym(this lookupEntry sym.name) + } + other.toList forall scopeContainsSym + } + /** 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 symbols: List[Symbol] = Nil + var count = 0 var e = elems while ((e ne null) && e.owner == this) { - elemsCache = e.sym :: elemsCache + count += 1 + symbols ::= e.sym e = e.next } + elemsCache = symbols + cachedSize = count } elemsCache } |