diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2014-01-31 13:23:33 +0100 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@typesafe.com> | 2014-02-10 14:34:35 -0800 |
commit | db9fd559ec70f033b475b0d91c6049b68955e095 (patch) | |
tree | 45d7fcaf69c92b5cd16c9e7b6f52a6162db4b819 /src/reflect | |
parent | 59fc37ade773f66eb05c7b2cfebe03abaf767c51 (diff) | |
download | scala-db9fd559ec70f033b475b0d91c6049b68955e095.tar.gz scala-db9fd559ec70f033b475b0d91c6049b68955e095.tar.bz2 scala-db9fd559ec70f033b475b0d91c6049b68955e095.zip |
SI-7475 Refactor findMember computation into a class
This affords us:
- a better chance to share code with `findMembers` again
- the ability to break up the logic into smaller methods for
scrutability and JIT-tability.
The cost is the use of the heap rather than the stack for the
working area of the computation. But I didn't notice a difference
between `locker.lib` and `quick.lib` after this change.
I've left the old implementation in place with an assertion to
verify identical results. In the next commit, this stepping stone
will be removed, and we'll update `findMembers` to share the code.
Some problem areas have been highlighted and will be addressed
after the refactoring phase is complete.
Diffstat (limited to 'src/reflect')
-rw-r--r-- | src/reflect/scala/reflect/internal/Types.scala | 21 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/tpe/FindMembers.scala | 223 |
2 files changed, 240 insertions, 4 deletions
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 17a58d79f6..b7cf8d2197 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -82,6 +82,7 @@ trait Types with tpe.GlbLubs with tpe.TypeMaps with tpe.TypeConstraints + with tpe.FindMembers with util.Collections { self: SymbolTable => import definitions._ @@ -248,7 +249,7 @@ trait Types * type instead of the proxy. This gives buried existentials a * chance to make peace with the other types. See SI-5330. */ - private def narrowForFindMember(tp: Type): Type = { + private[internal] def narrowForFindMember(tp: Type): Type = { val w = tp.widen // Only narrow on widened type when we have to -- narrow is expensive unless the target is a singleton type. if ((tp ne w) && containsExistential(w)) w.narrow @@ -989,6 +990,7 @@ trait Types * */ def findMembers(excludedFlags: Long, requiredFlags: Long): Scope = { + // TODO refactor to use `FindMemberBase` def findMembersInternal: Scope = { var members: Scope = null if (Statistics.canEnable) Statistics.incCounter(findMembersCount) @@ -1055,14 +1057,25 @@ trait Types * Find member(s) in this type. If several members matching criteria are found, they are * returned in an OverloadedSymbol * - * @param name The member's name, where nme.ANYNAME means `unspecified` + * @param name The member's name * @param excludedFlags Returned members do not have these flags * @param requiredFlags Returned members do have these flags * @param stableOnly If set, return only members that are types or stable values */ - //TODO: use narrow only for modules? (correct? efficiency gain?) def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = { - def findMemberInternal: Symbol = { + def findMemberInternal = { + // TODO delete `findMemberInternalOld` + val resultOld = findMemberInternalOld + val resultNew = findMemberInternalNew + if (resultOld.alternatives != resultNew.alternatives) { + findMemberInternalOld + findMemberInternalNew + } + assert(resultOld.alternatives == resultNew.alternatives, s"\nOLD:${resultOld.alternatives}\nNEW${resultNew.alternatives}") + resultNew + } + def findMemberInternalNew = new FindMember(this, name, excludedFlags, requiredFlags, stableOnly).apply() + def findMemberInternalOld: Symbol = { var member: Symbol = NoSymbol var members: List[Symbol] = null var lastM: ::[Symbol] = null diff --git a/src/reflect/scala/reflect/internal/tpe/FindMembers.scala b/src/reflect/scala/reflect/internal/tpe/FindMembers.scala new file mode 100644 index 0000000000..380e11e0d7 --- /dev/null +++ b/src/reflect/scala/reflect/internal/tpe/FindMembers.scala @@ -0,0 +1,223 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2014 LAMP/EPFL + * @author Jason Zaugg + */ +package scala.reflect.internal +package tpe + +import Flags._ +import util.Statistics +import TypesStats._ + +trait FindMembers { + this: SymbolTable => + + /** Implementatation of `Type#{findMember, findMembers}` */ + private[internal] abstract class FindMemberBase[T](tpe: Type, name: Name, excludedFlags: Long, requiredFlags: Long) { + protected val initBaseClasses: List[Symbol] = tpe.baseClasses + + // The first base class, or the symbol of the ThisType + private[this] var _selectorClass: Symbol = null + private def selectorClass: Symbol = { + if (_selectorClass eq null) { + _selectorClass = tpe match { + case tt: ThisType => tt.sym // SI-7507 the first base class is not necessarily the selector class. + case _ => initBaseClasses.head + } + } + _selectorClass + } + + // Cache for the narrowed type of `tp` (in `tp.findMember`). + // This is needed to avoid mismatched existential types are reported in SI-5330. + private[this] var _self: Type = null + protected def self: Type = { + // TODO: use narrow only for modules? (correct? efficiency gain?) (<-- Note: this comment predates SI-5330) + if (_self eq null) _self = narrowForFindMember(tpe) + _self + } + + // Main entry point + def apply(): T = { + if (Statistics.canEnable) Statistics.incCounter(findMemberCount) + val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMemberNanos) else null + try searchConcreteThenDeferred + finally if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + } + + protected def result: T + + // SLS 5.1.3 First, a concrete definition always overrides an abstract definition + private def searchConcreteThenDeferred: T = { + val deferredSeen = walkBaseClasses(requiredFlags, excludedFlags | DEFERRED) + if (deferredSeen) // OPT: the `if` avoids a second pass if the first pass didn't spot any candidates. + walkBaseClasses(requiredFlags | DEFERRED, excludedFlags & ~(DEFERRED.toLong)) + result + } + + /* + * Walk up through the decls of each base class. + * + * Called in two passes: first excluding deferred, then mandating it. + * + * @return true, if a potential deferred member was seen on the first pass that calls for a second pass. + */ + private def walkBaseClasses(required: Long, excluded: Long): Boolean = { + var bcs = initBaseClasses + + // Has we seen a candidate deferred member? + var deferredSeen = false + + while (!bcs.isEmpty) { + val currentBaseClass = bcs.head + val decls = currentBaseClass.info.decls + val findAll = name == nme.ANYname + var entry = if (findAll) decls.elems else decls.lookupEntry(name) + while (entry ne null) { + val sym = entry.sym + val flags = sym.flags + val meetsRequirements = (flags & required) == required + if (meetsRequirements) { + val excl: Long = flags & excluded + val isExcluded: Boolean = excl != 0L + if (!isExcluded && isPotentialMember(sym, flags, currentBaseClass)) { + if (shortCircuit(sym)) return false + else addMemberIfNew(sym) + } else if (excl == DEFERRED) { + deferredSeen = true + } + } + entry = if (findAll) entry.next else decls lookupNextEntry entry + } + + bcs = bcs.tail + } + deferredSeen + } + + /* Should this symbol be returned immediately as the sole result? */ + protected def shortCircuit(sym: Symbol): Boolean + + /* Add this member to the final result, unless an already-found member matches it. */ + protected def addMemberIfNew(sym: Symbol): Unit + + // Is `sym` a potentially member of `baseClass`? + // + // Q. When does a potential member fail to be a an actual member? + // A. if it is subsumed by an member in a subclass. + private def isPotentialMember(sym: Symbol, flags: Long, owner: Symbol): Boolean = { + // conservatively (performance wise) doing this with flags masks rather than `sym.isPrivate` + // to avoid multiple calls to `Symbol#flags`. + val isPrivateLocal = (flags & PrivateLocal) == PrivateLocal + + def admitPrivateLocal(sym: Symbol): Boolean = + ( + (selectorClass == owner) + || !isPrivateLocal + || selectorClass.hasTransOwner(owner) // private[this] only a member from within the class (incorrect!) + ) + + // TODO first condition incorrect wrt self types! In neg/t7507, bippy should not be a member! + // The condition, or a close variant thereof, will still be needed to prevent inheritance of constructors. + owner == initBaseClasses.head || admitPrivateLocal(sym) && sym.name != nme.CONSTRUCTOR + } + + // True unless the already-found member of type `memberType` matches the candidate symbol `other`. + protected def isNewMember(member: Symbol, other: Symbol): Boolean = + ( (other ne member) + && ( (member.owner eq other.owner) + || (other.flags & PRIVATE) != 0 + || !(memberTypeLow(member) matches memberTypeHi(other)) + ) + ) + + // Cache for the member type of a candidate member when comparing against multiple, already-found existing members + // + // TODO this cache is probably unnecessary, `tp.memberType(sym: MethodSymbol)` is already cached internally. + private[this] var _memberTypeHiCache: Type = null + private[this] var _memberTypeHiCacheSym: Symbol = null + + protected def memberTypeHi(sym: Symbol): Type = { + if (_memberTypeHiCacheSym ne sym) { + _memberTypeHiCache = self.memberType(sym) + _memberTypeHiCacheSym = sym + } + _memberTypeHiCache + } + + // member type of the LHS of `matches` call. This is an extension point to enable a cache in + // FindMember. + protected def memberTypeLow(sym: Symbol): Type = self.memberType(sym) + } + + private[reflect] final class FindMember(tpe: Type, name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean) + extends FindMemberBase[Symbol](tpe, name, excludedFlags, requiredFlags) { + // Gathering the results into a hand rolled ListBuffer + // TODO Try just using a ListBuffer to see if this low-level-ness is worth it. + private[this] var member0: Symbol = NoSymbol + private[this] var members: List[Symbol] = null + private[this] var lastM: ::[Symbol] = null + + private def clearAndAddResult(sym: Symbol): Unit = { + member0 = sym + members = null + lastM = null + } + + protected def shortCircuit(sym: Symbol): Boolean = (name.isTypeName || (stableOnly && sym.isStable && !sym.hasVolatileType)) && { + clearAndAddResult(sym) + true + } + + protected def addMemberIfNew(sym: Symbol): Unit = + if (member0 eq NoSymbol) { + member0 = sym // The first found member + } else if (members eq null) { + // We've found exactly one member so far... + if (isNewMember(member0, sym)) { + // ... make that two. + lastM = new ::(sym, null) + members = member0 :: lastM + } + } else { + // Already found 2 or more members + var ms: List[Symbol] = members + + var isNew = true + while ((ms ne null) && isNew) { + val member = ms.head + if (!isNewMember(member, sym)) + isNew = false + ms = ms.tail + } + if (isNew) { + val lastM1 = new ::(sym, null) + lastM.tl = lastM1 + lastM = lastM1 + } + } + + // Cache for the member type of the first member we find. + private[this] var _member0Tpe: Type = null + private[this] def member0Tpe: Type = { + assert(member0 != null) + if (_member0Tpe eq null) _member0Tpe = self.memberType(member0) + _member0Tpe + } + + override protected def memberTypeLow(sym: Symbol): Type = + if (sym eq member0) member0Tpe else super.memberTypeLow(sym) + + // Assemble the result from the hand-rolled ListBuffer + protected def result: Symbol = if (members eq null) { + if (member0 == NoSymbol) { + if (Statistics.canEnable) Statistics.incCounter(noMemberCount) + NoSymbol + } else member0 + } else { + if (Statistics.canEnable) Statistics.incCounter(multMemberCount) + lastM.tl = Nil + initBaseClasses.head.newOverloaded(tpe, members) + } + } +} |