summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/compiler/scala/tools/nsc/typechecker/Implicits.scala519
-rw-r--r--src/compiler/scala/tools/nsc/util/HashSet.scala3
2 files changed, 280 insertions, 242 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 4fc248b574..3a84bdc9e4 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -11,6 +11,7 @@
package scala.tools.nsc
package typechecker
+import annotation.tailrec
import scala.collection.{ mutable, immutable }
import mutable.{ LinkedHashMap, ListBuffer }
import scala.util.matching.Regex
@@ -23,7 +24,7 @@ import util.Statistics._
* @version 1.0
*/
trait Implicits {
-self: Analyzer =>
+ self: Analyzer =>
import global._
import definitions._
@@ -65,7 +66,9 @@ self: Analyzer =>
}
final val sizeLimit = 50000
- val implicitsCache = new LinkedHashMap[Type, List[List[ImplicitInfo]]]
+ private type Infos = List[ImplicitInfo]
+ private type Infoss = List[List[ImplicitInfo]]
+ val implicitsCache = new LinkedHashMap[Type, Infoss]
def resetImplicits() { implicitsCache.clear() }
private val ManifestSymbols = Set(PartialManifestClass, FullManifestClass, OptManifestClass)
@@ -103,6 +106,9 @@ self: Analyzer =>
tpeCache
}
+ var useCountArg: Int = 0
+ var useCountView: Int = 0
+
/** Does type `tp` contain an Error type as parameter or result?
*/
private def containsError(tp: Type): Boolean = tp match {
@@ -128,9 +134,7 @@ self: Analyzer =>
this.sym == that.sym
case _ => false
}
-
override def hashCode = name.## + pre.## + sym.##
-
override def toString = "ImplicitInfo(" + name + "," + pre + "," + sym + ")"
}
@@ -159,11 +163,12 @@ self: Analyzer =>
/** An extractor for types of the form ? { name: ? }
*/
object HasMember {
- def apply(name: Name): Type = memberWildcardType(name, WildcardType)
+ private val hasMemberCache = new mutable.HashMap[Name, Type]
+ def apply(name: Name): Type = hasMemberCache.getOrElseUpdate(name, memberWildcardType(name, WildcardType))
def unapply(pt: Type): Option[Name] = pt match {
case RefinedType(List(WildcardType), decls) =>
decls.toList match {
- case List(sym) if (sym.tpe == WildcardType) => Some(sym.name)
+ case List(sym) if sym.tpe == WildcardType => Some(sym.name)
case _ => None
}
case _ =>
@@ -202,8 +207,8 @@ self: Analyzer =>
object Function1 {
val Sym = FunctionClass(1)
def unapply(tp: Type) = tp match {
- case TypeRef(_, Sym, args) => Some((args.head, args.tail.head))
- case _ => None
+ case TypeRef(_, Sym, arg1 :: arg2 :: _) => Some(arg1, arg2)
+ case _ => None
}
}
@@ -336,7 +341,8 @@ self: Analyzer =>
/** Replace undetParams in type `tp` by Any/Nothing, according to variance */
def approximate(tp: Type) =
- tp.instantiateTypeParams(undetParams, undetParams map (_ => WildcardType))
+ if (undetParams.isEmpty) tp
+ else tp.instantiateTypeParams(undetParams, undetParams map (_ => WildcardType))
val wildPt = approximate(pt)
@@ -347,7 +353,7 @@ self: Analyzer =>
* @param info The given implicit info describing the implicit definition
* @pre <code>info.tpe</code> does not contain an error
*/
- private def typedImplicit(info: ImplicitInfo): SearchResult =
+ private def typedImplicit(info: ImplicitInfo, ptChecked: Boolean): SearchResult =
(context.openImplicits find { case (tp, sym) => sym == tree.symbol && dominates(pt, tp)}) match {
case Some(pending) =>
// println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
@@ -356,7 +362,7 @@ self: Analyzer =>
try {
context.openImplicits = (pt, tree.symbol) :: context.openImplicits
// println(" "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
- typedImplicit0(info)
+ typedImplicit0(info, ptChecked)
} catch {
case DivergentImplicit =>
// println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
@@ -374,150 +380,176 @@ self: Analyzer =>
}
}
- private def typedImplicit0(info: ImplicitInfo): SearchResult = {
-
- /** Todo reconcile with definition of stability given in Types.scala */
- def isStable(tp: Type): Boolean = tp match {
- case TypeRef(pre, sym, _) =>
- sym.isPackageClass ||
- sym.isModuleClass && isStable(pre) /*||
- sym.isAliasType && isStable(tp.normalize)*/
- case _ => tp.isStable
- }
+ /** Todo reconcile with definition of stability given in Types.scala */
+ private def isStable(tp: Type): Boolean = tp match {
+ case TypeRef(pre, sym, _) =>
+ sym.isPackageClass ||
+ sym.isModuleClass && isStable(pre) /*||
+ sym.isAliasType && isStable(tp.normalize)*/
+ case _ => tp.isStable
+ }
- /** Does type `tp' match expected type `pt'
- * This is the case if either `pt' is a unary function type with a
- * HasMethodMatching type as result, and `tp' is a unary function
- * or method type whose result type has a method whose name and type
- * correspond to the HasMethodMatching type,
- * or otherwise if `tp' is compatible with `pt'.
- * This method is performance critical: 5-8% of typechecking time.
- */
- def matchesPt(tp: Type, pt: Type, undet: List[Symbol]) = {
- val start = startTimer(matchesPtNanos)
- val result = normSubType(tp, pt) || isView && {
- pt match {
- case TypeRef(_, Function1.Sym, args) =>
- matchesPtView(tp, args.head, args.tail.head, undet)
- case _ =>
- false
- }
+ /** Does type `tp' match expected type `pt'
+ * This is the case if either `pt' is a unary function type with a
+ * HasMethodMatching type as result, and `tp' is a unary function
+ * or method type whose result type has a method whose name and type
+ * correspond to the HasMethodMatching type,
+ * or otherwise if `tp' is compatible with `pt'.
+ * This method is performance critical: 5-8% of typechecking time.
+ */
+ private def matchesPt(tp: Type, pt: Type, undet: List[Symbol]) = {
+ val start = startTimer(matchesPtNanos)
+ val result = normSubType(tp, pt) || isView && {
+ pt match {
+ case TypeRef(_, Function1.Sym, args) =>
+ matchesPtView(tp, args.head, args.tail.head, undet)
+ case _ =>
+ false
}
- stopTimer(matchesPtNanos, start)
- result
}
+ stopTimer(matchesPtNanos, start)
+ result
+ }
- def matchesPtView(tp: Type, ptarg: Type, ptres: Type, undet: List[Symbol]): Boolean = tp match {
- case MethodType(p :: _, restpe) if p.isImplicit => matchesPtView(restpe, ptarg, ptres, undet)
- case MethodType(p :: Nil, restpe) => matchesArgRes(p.tpe, restpe, ptarg, ptres, undet)
- case ExistentialType(_, qtpe) => matchesPtView(normalize(qtpe), ptarg, ptres, undet)
- case Function1(arg1, res1) => matchesArgRes(arg1, res1, ptarg, ptres, undet)
- case _ => false
- }
+ private def matchesPtView(tp: Type, ptarg: Type, ptres: Type, undet: List[Symbol]): Boolean = tp match {
+ case MethodType(p :: _, restpe) if p.isImplicit => matchesPtView(restpe, ptarg, ptres, undet)
+ case MethodType(p :: Nil, restpe) => matchesArgRes(p.tpe, restpe, ptarg, ptres, undet)
+ case ExistentialType(_, qtpe) => matchesPtView(normalize(qtpe), ptarg, ptres, undet)
+ case Function1(arg1, res1) => matchesArgRes(arg1, res1, ptarg, ptres, undet)
+ case _ => false
+ }
- def matchesArgRes(tparg: Type, tpres: Type, ptarg: Type, ptres: Type, undet: List[Symbol]): Boolean =
- (ptarg weak_<:< tparg) && {
- ptres match {
- case HasMethodMatching(name, argtpes, restpe) =>
- (tpres.member(name) filter (m =>
- isApplicableSafe(undet, m.tpe, argtpes, restpe))) != NoSymbol
- case _ =>
- tpres <:< ptres
- }
- }
+ private def matchesArgRes(tparg: Type, tpres: Type, ptarg: Type, ptres: Type, undet: List[Symbol]): Boolean =
+ (ptarg weak_<:< tparg) && {
+ ptres match {
+ case HasMethodMatching(name, argtpes, restpe) =>
+ (tpres.member(name) filter (m =>
+ isApplicableSafe(undet, m.tpe, argtpes, restpe))) != NoSymbol
+ case _ =>
+ tpres <:< ptres
+ }
+ }
+ private def typedImplicit0(info: ImplicitInfo, ptChecked: Boolean): SearchResult = {
incCounter(plausiblyCompatibleImplicits)
printTyping("typed impl for "+wildPt+"? "+info.name +":"+ depoly(info.tpe)+ " orig info= "+ info.tpe +"/"+undetParams+"/"+isPlausiblyCompatible(info.tpe, wildPt)+"/"+matchesPt(depoly(info.tpe), wildPt, List())+"/"+info.pre+"/"+isStable(info.pre))
- if (matchesPt(depoly(info.tpe), wildPt, List()) && isStable(info.pre)) {
+ if (ptChecked || matchesPt(depoly(info.tpe), wildPt, List()) && isStable(info.pre))
+ typedImplicit1(info)
+ else
+ SearchFailure
+ }
- incCounter(matchingImplicits)
+ private def typedImplicit1(info: ImplicitInfo): SearchResult = {
+ incCounter(matchingImplicits)
- val itree = atPos(tree.pos.focus) {
- if (info.pre == NoPrefix) Ident(info.name)
- else Select(gen.mkAttributedQualifier(info.pre), info.name)
- }
- printTyping("typedImplicit0 typing"+ itree +" with wildpt = "+ wildPt +" from implicit "+ info.name+":"+info.tpe)
- def fail(reason: String): SearchResult = {
- if (settings.XlogImplicits.value)
- inform(itree+" is not a valid implicit value for "+pt+" because:\n"+reason)
- SearchFailure
- }
- try {
- val itree1 =
- if (isView)
- typed1 (
- atPos(itree.pos) (
- Apply(itree, List(Ident("<argument>").setType(approximate(pt.typeArgs.head))))),
- EXPRmode, approximate(pt.typeArgs.tail.head)
- )
- else
- typed1(itree, EXPRmode, wildPt)
-
- incCounter(typedImplicits)
-
- printTyping("typed implicit "+itree1+":"+itree1.tpe+", pt = "+wildPt)
- val itree2 = if (isView) (itree1: @unchecked) match { case Apply(fun, _) => fun }
- else adapt(itree1, EXPRmode, wildPt)
- printTyping("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+wildPt)
- def hasMatchingSymbol(tree: Tree): Boolean = (tree.symbol == info.sym) || {
- tree match {
- case Apply(fun, _) => hasMatchingSymbol(fun)
- case TypeApply(fun, _) => hasMatchingSymbol(fun)
- case Select(pre, nme.apply) => pre.symbol == info.sym
- case _ => false
- }
+ val itree = atPos(tree.pos.focus) {
+ if (info.pre == NoPrefix) Ident(info.name)
+ else Select(gen.mkAttributedQualifier(info.pre), info.name)
+ }
+ printTyping("typedImplicit0 typing"+ itree +" with wildpt = "+ wildPt +" from implicit "+ info.name+":"+info.tpe)
+ def fail(reason: String): SearchResult = {
+ if (settings.XlogImplicits.value)
+ inform(itree+" is not a valid implicit value for "+pt+" because:\n"+reason)
+ SearchFailure
+ }
+ try {
+ val itree1 =
+ if (isView) {
+ val arg1 :: arg2 :: _ = pt.typeArgs
+ typed1(
+ atPos(itree.pos)(Apply(itree, List(Ident("<argument>") setType approximate(arg1)))),
+ EXPRmode,
+ approximate(arg2)
+ )
}
+ else
+ typed1(itree, EXPRmode, wildPt)
+
+ incCounter(typedImplicits)
+
+ printTyping("typed implicit "+itree1+":"+itree1.tpe+", pt = "+wildPt)
+ val itree2 = if (isView) (itree1: @unchecked) match { case Apply(fun, _) => fun }
+ else adapt(itree1, EXPRmode, wildPt)
+ printTyping("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+wildPt)
+ def hasMatchingSymbol(tree: Tree): Boolean = (tree.symbol == info.sym) || {
+ tree match {
+ case Apply(fun, _) => hasMatchingSymbol(fun)
+ case TypeApply(fun, _) => hasMatchingSymbol(fun)
+ case Select(pre, nme.apply) => pre.symbol == info.sym
+ case _ => false
+ }
+ }
- if (itree2.tpe.isError) SearchFailure
- else if (hasMatchingSymbol(itree1)) {
- val tvars = undetParams map freshVar
- if (matchesPt(itree2.tpe, pt.instantiateTypeParams(undetParams, tvars), undetParams)) {
- printTyping("tvars = "+tvars+"/"+(tvars map (_.constr)))
- val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt),
- false, lubDepth(List(itree2.tpe, pt)))
-
- // #2421: check that we correctly instantiated type parameters outside of the implicit tree:
- checkBounds(itree2.pos, NoPrefix, NoSymbol, undetParams, targs, "inferred ")
-
- // filter out failures from type inference, don't want to remove them from undetParams!
- // we must be conservative in leaving type params in undetparams
- val AdjustedTypeArgs(okParams, okArgs) = adjustTypeArgs(undetParams, targs) // prototype == WildcardType: want to remove all inferred Nothing's
- val subst = new TreeTypeSubstituter(okParams, okArgs)
+ if (itree2.tpe.isError) SearchFailure
+ else if (hasMatchingSymbol(itree1)) {
+ val tvars = undetParams map freshVar
+ if (matchesPt(itree2.tpe, pt.instantiateTypeParams(undetParams, tvars), undetParams)) {
+ printTyping("tvars = "+tvars+"/"+(tvars map (_.constr)))
+ val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt),
+ false, lubDepth(List(itree2.tpe, pt)))
+
+ // #2421: check that we correctly instantiated type parameters outside of the implicit tree:
+ checkBounds(itree2.pos, NoPrefix, NoSymbol, undetParams, targs, "inferred ")
+
+ // filter out failures from type inference, don't want to remove them from undetParams!
+ // we must be conservative in leaving type params in undetparams
+ val AdjustedTypeArgs(okParams, okArgs) = adjustTypeArgs(undetParams, targs) // prototype == WildcardType: want to remove all inferred Nothing's
+ var subst = EmptyTreeTypeSubstituter
+ if (okParams.nonEmpty) {
+ subst = new TreeTypeSubstituter(okParams, okArgs)
subst traverse itree2
+ }
- // #2421b: since type inference (which may have been performed during implicit search)
- // does not check whether inferred arguments meet the bounds of the corresponding parameter (see note in solvedTypes),
- // must check again here:
- // TODO: I would prefer to just call typed instead of duplicating the code here, but this is probably a hotspot (and you can't just call typed, need to force re-typecheck)
- itree2 match {
- case TypeApply(fun, args) => typedTypeApply(itree2, EXPRmode, fun, args)
- case Apply(TypeApply(fun, args), _) => typedTypeApply(itree2, EXPRmode, fun, args) // t2421c
- case _ =>
- }
+ // #2421b: since type inference (which may have been performed during implicit search)
+ // does not check whether inferred arguments meet the bounds of the corresponding parameter (see note in solvedTypes),
+ // must check again here:
+ // TODO: I would prefer to just call typed instead of duplicating the code here, but this is probably a hotspot (and you can't just call typed, need to force re-typecheck)
+ itree2 match {
+ case TypeApply(fun, args) => typedTypeApply(itree2, EXPRmode, fun, args)
+ case Apply(TypeApply(fun, args), _) => typedTypeApply(itree2, EXPRmode, fun, args) // t2421c
+ case _ =>
+ }
- val result = new SearchResult(itree2, subst)
- incCounter(foundImplicits)
- if (traceImplicits) println("RESULT = "+result)
- // println("RESULT = "+itree+"///"+itree1+"///"+itree2)//DEBUG
- result
- } else {
- printTyping("incompatible: "+itree2.tpe+" does not match "+pt.instantiateTypeParams(undetParams, tvars))
+ val result = new SearchResult(itree2, subst)
+ incCounter(foundImplicits)
+ if (traceImplicits) println("RESULT = "+result)
+ // println("RESULT = "+itree+"///"+itree1+"///"+itree2)//DEBUG
+ result
+ } else {
+ printTyping("incompatible: "+itree2.tpe+" does not match "+pt.instantiateTypeParams(undetParams, tvars))
- SearchFailure
- }
- } else if (settings.XlogImplicits.value)
- fail("candidate implicit "+info.sym+info.sym.locationString+
- " is shadowed by other implicit: "+itree1.symbol+itree1.symbol.locationString)
- else SearchFailure
- } catch {
- case ex: TypeError => fail(ex.getMessage())
+ SearchFailure
+ }
}
- } else {
- SearchFailure
+ else if (settings.XlogImplicits.value)
+ fail("candidate implicit "+info.sym+info.sym.locationString+
+ " is shadowed by other implicit: "+itree1.symbol+itree1.symbol.locationString)
+ else SearchFailure
+ } catch {
+ case ex: TypeError => fail(ex.getMessage())
}
}
+ // #3453: in addition to the implicit symbols that may shadow the implicit with
+ // name `name`, this method tests whether there's a non-implicit symbol with name
+ // `name` in scope. Inspired by logic in typedIdent.
+ private def nonImplicitSynonymInScope(name: Name) = {
+ // the implicit ones are handled by the `shadowed` set above
+ context.scope.lookupEntry(name) match {
+ case x: ScopeEntry => reallyExists(x.sym) && !x.sym.isImplicit
+ case _ => false
+ }
+ }
+
+ /** Is `sym' the standard conforms method in Predef?
+ * Note: DON't replace this by sym == Predef_conforms, as Predef_conforms is a `def'
+ * which does a member lookup (it can't be a lazy val because we might reload Predef
+ * during resident compilations).
+ */
+ private def isConformsMethod(sym: Symbol) =
+ sym.name == nme.conforms && sym.owner == PredefModule.moduleClass
+
/** Should implicit definition symbol `sym' be considered for applicability testing?
* This is the case if one of the following holds:
* - the symbol's type is initialized
@@ -544,7 +576,7 @@ self: Analyzer =>
def comesBefore(sym: Symbol, owner: Symbol) = {
val ownerPos = owner.pos.pointOrElse(Int.MaxValue)
sym.pos.pointOrElse(0) < ownerPos && (
- if(sym hasAccessorFlag) {
+ if (sym hasAccessorFlag) {
val symAcc = sym.accessed // #3373
symAcc.pos.pointOrElse(0) < ownerPos &&
!(owner.ownerChain exists (o => (o eq sym) || (o eq symAcc))) // probably faster to iterate only once, don't feel like duplicating hasTransOwner for this case
@@ -558,131 +590,133 @@ self: Analyzer =>
comesBefore(sym, context.owner)
}
- /** Computes from a list of lists of implicit infos a map which takes
- * infos which are applicable for given expected type `pt` to their attributed trees.
- * Computes invalid implicits as a side effect (used for better error message).
- * Returns both the above in a tuple.
+ /** Prune ImplicitInfos down to either all the eligible ones or the best one.
*
- * @param iss The given list of lists of implicit infos
- * @param isLocal Is implicit definition visible without prefix?
- * If this is the case then symbols in preceding lists shadow
- * symbols of the same name in succeeding lists.
- * @return (invalidImplicits, map from infos to search results)
+ * @param iss list of list of infos
+ * @param shadowed set in which to record names that are shadowed by implicit infos
+ * If it is null, no shadowing.
*/
- def applicableInfos(iss: List[List[ImplicitInfo]], isLocal: Boolean): (List[Symbol], Map[ImplicitInfo, SearchResult]) = {
-
- val start = startCounter(subtypeAppInfos)
-
- /** A set containing names that are shadowed by implicit infos */
- lazy val shadowed = new util.HashSet[Name]("shadowed", 512)
-
- // #3453
- // in addition to the implicit symbols that may shadow the implicit with name `name`,
- // this method tests whether there's a non-implicit symbol with name `name` in scope
- // inspired by logic in typedIdent
- def nonImplicitSynonymInScope(name: Name) = {
- val defEntry = context.scope.lookupEntry(name)
- (defEntry ne null) &&
- reallyExists(defEntry.sym) &&
- !defEntry.sym.isImplicit // the implicit ones are handled by the `shadowed` set above
- // also, subsumes the test that defEntry.sym ne info.sym
- // (the `info` that's in scope at the call to nonImplicitSynonymInScope in tryImplicit)
+ class ImplicitComputation(iss: Infoss, shadowed: util.HashSet[Name]) {
+ private var _best: SearchResult = SearchFailure
+
+ /** True if a given ImplicitInfo (already known isValid) is eligible.
+ */
+ def survives(info: ImplicitInfo): Boolean = {
+ !info.isCyclicOrErroneous &&
+ !(isView && isConformsMethod(info.sym)) &&
+ isPlausiblyCompatible(info.tpe, wildPt) && // <--- cheaper than matchesPt
+ matchesPt(depoly(info.tpe), wildPt, Nil) &&
+ isStable(info.pre) &&
+ (shadowed == null || (!shadowed(info.name) && !nonImplicitSynonymInScope(info.name)))
}
+ /** The implicits that are not valid because they come later in the source and
+ * lack an explicit result type. Used for error diagnostics only.
+ */
+ val invalidImplicits = new ListBuffer[Symbol]
- /** Is `sym' the standard conforms method in Predef?
- * Note: DON't replace this by sym == Predef_conforms, as Predef_conforms is a `def'
- * which does a member lookup (it can't be a lazy val because we might reload Predef
- * during resident compilations).
+ /** Tests for validity and updates invalidImplicits by side effect when false.
*/
- def isConformsMethod(sym: Symbol) =
- sym.name == nme.conforms && sym.owner == PredefModule.moduleClass
-
- /** Try implicit `info` to see whether it is applicable for expected type `pt`.
- * This is the case if all of the following holds:
- * - the info's type is not erroneous,
- * - the info is not shadowed by another info with the same name,
- * - we're not trying to infer a view that amounts to the identity function (specifically, Predef.identity or Predef.conforms)
- * - the result of typedImplicit is non-empty.
- * @return A search result with an attributed tree containing the implicit if succeeded,
- * SearchFailure if not.
- * @note Extreme hotspot!
+ private def checkValid(sym: Symbol) = isValid(sym) || { invalidImplicits += sym ; false }
+
+ /** Sorted list of eligible implicits.
*/
- def tryImplicit(info: ImplicitInfo): SearchResult = {
- incCounter(triedImplicits)
- if (info.isCyclicOrErroneous ||
- (isLocal && (shadowed(info.name) || nonImplicitSynonymInScope(info.name))) ||
- (isView && isConformsMethod(info.sym)) ||
- //@M this condition prevents no-op conversions, which are a problem (besides efficiency),
- // one example is removeNames in NamesDefaults, which relies on the type checker failing in case of ambiguity between an assignment/named arg
- !isPlausiblyCompatible(info.tpe, wildPt))
- SearchFailure
- else
- typedImplicit(info)
+ val eligible = {
+ val matches = iss flatMap { is =>
+ val result = is filter (info => checkValid(info.sym) && survives(info))
+ if (shadowed ne null)
+ shadowed addEntries (is map (_.name))
+
+ result
+ }
+
+ // most frequent one first
+ matches sortBy (x => if (isView) -x.useCountView else -x.useCountArg)
}
- val invalidImplicits = new ListBuffer[Symbol]
- val applicable = immutable.Map.newBuilder[ImplicitInfo, SearchResult]
- def addAppInfos(is: List[ImplicitInfo]): Unit = {
- for (i <- is)
- if (!isValid(i.sym)) invalidImplicits += i.sym
- else tryImplicit(i) match {
- case SearchFailure => ()
- case result => applicable += ((i, result))
+ /** Faster implicit search. Overall idea:
+ * - prune aggressively
+ * - find the most likely one
+ * - if it matches, forget about all others it improves upon
+ */
+ @tailrec private def rankImplicits(pending: Infos, acc: Infos): Infos = pending match {
+ case Nil => acc
+ case i :: is =>
+ typedImplicit(i, true) match {
+ case SearchFailure => rankImplicits(is, acc)
+ case newBest =>
+ _best = newBest
+ val newPending = undoLog undo {
+ is filterNot (alt => alt == i || {
+ try improves(i, alt)
+ catch { case e: CyclicReference => true }
+ })
+ }
+ rankImplicits(newPending, i :: acc)
}
- if (isLocal)
- for (i <- is) shadowed addEntry i.name
}
- // #3453 -- alternative fix, seems not to be faster than encoding the set as the boolean predicate nonImplicitSynonymInScope
- // in addition to the *implicit* symbols that may shadow the implicit with name `name` (added to shadowed by addAppInfos)
- // add names of non-implicit symbols that are in scope (accessible without prefix)
- // for(sym <- context.scope; if !sym.isImplicit) shadowed addEntry sym.name
+ /** Returns all eligible ImplicitInfos and their SearchResults in a map.
+ */
+ def findAll() = eligible map (info => (info, typedImplicit(info, false))) toMap
- iss foreach addAppInfos
- stopCounter(subtypeAppInfos, start)
+ /** Returns the SearchResult of the best match.
+ */
+ def findBest(): SearchResult = {
+ // After calling rankImplicits, the least frequent matching one is first and
+ // earlier elems may improve on later ones, but not the other way.
+ // So if there is any element not improved upon by the first it is an error.
+ rankImplicits(eligible, Nil) match {
+ case Nil => ()
+ case chosen :: rest =>
+ rest find (alt => !improves(chosen, alt)) match {
+ case Some(competing) =>
+ ambiguousImplicitError(chosen, competing, "both", "and", "")
+ case _ =>
+ if (isView) chosen.useCountView += 1
+ else chosen.useCountArg += 1
+ }
+ }
- (invalidImplicits.toList, applicable.result)
+ if (_best == SearchFailure && invalidImplicits.nonEmpty) {
+ setAddendum(tree.pos, () =>
+ "\n Note: implicit "+invalidImplicits.head+" is not applicable here"+
+ " because it comes after the application point and it lacks an explicit result type")
+ }
+
+ _best
+ }
}
- /** Search list of implicit info lists for one matching prototype
- * <code>pt</code>. If found return a search result with a tree from found implicit info
- * which is typed with expected type <code>pt</code>.
- * Otherwise return SearchFailure.
+ /** Computes from a list of lists of implicit infos a map which takes
+ * infos which are applicable for given expected type `pt` to their attributed trees.
*
- * @param implicitInfoss The given list of lists of implicit infos
+ * @param iss The given list of lists of implicit infos
* @param isLocal Is implicit definition visible without prefix?
* If this is the case then symbols in preceding lists shadow
* symbols of the same name in succeeding lists.
+ * @return map from infos to search results
*/
- def searchImplicit(implicitInfoss: List[List[ImplicitInfo]], isLocal: Boolean): SearchResult = {
- /** The implicits that are not valid because they come later in the source
- * and lack an explicit result type. Used for error diagnostics only.
- *
- * A map which takes applicable infos to their attributed trees.
- */
- val (invalidImplicits, applicable) = applicableInfos(implicitInfoss, isLocal)
-
- if (applicable.isEmpty && invalidImplicits.nonEmpty) {
- setAddendum(tree.pos, () =>
- "\n Note: implicit "+invalidImplicits.head+" is not applicable here"+
- " because it comes after the application point and it lacks an explicit result type")
- }
-
- val start = startCounter(subtypeImprovCount)
+ def applicableInfos(iss: Infoss, isLocal: Boolean): Map[ImplicitInfo, SearchResult] = {
+ val start = startCounter(subtypeAppInfos)
+ val computation = new ImplicitComputation(iss, if (isLocal) new util.HashSet[Name](512) else null) { }
+ val applicable = computation.findAll()
- /** A candidate for best applicable info wrt `improves` */
- val best = (NoImplicitInfo /: applicable.keysIterator) (
- (best, alt) => if (improves(alt, best)) alt else best)
- if (best == NoImplicitInfo) SearchFailure
- else {
- /** The list of all applicable infos which are not improved upon by `best`. */
- val competing = applicable.keySet filterNot (alt => best == alt || improves(best, alt))
- if (!competing.isEmpty) ambiguousImplicitError(best, competing.head, "both", "and", "")
+ stopCounter(subtypeAppInfos, start)
+ applicable
+ }
- stopCounter(subtypeImprovCount, start)
- applicable(best)
- }
- } // end searchImplicit
+ /** Search list of implicit info lists for one matching prototype `pt`.
+ * If found return a search result with a tree from found implicit info
+ * which is typed with expected type `pt`. Otherwise return SearchFailure.
+ *
+ * @param implicitInfoss The given list of lists of implicit infos
+ * @param isLocal Is implicit definition visible without prefix?
+ * If this is the case then symbols in preceding lists shadow
+ * symbols of the same name in succeeding lists.
+ */
+ def searchImplicit(implicitInfoss: Infoss, isLocal: Boolean): SearchResult =
+ if (implicitInfoss.forall(_.isEmpty)) SearchFailure
+ else new ImplicitComputation(implicitInfoss, if (isLocal) new util.HashSet[Name](512) else null) findBest()
/** The parts of a type is the smallest set of types that contains
* - the type itself
@@ -694,7 +728,7 @@ self: Analyzer =>
* can be accessed with unambiguous stable prefixes, the implicits infos
* which are members of these companion objects.
*/
- private def companionImplicits(tp: Type): List[List[ImplicitInfo]] = {
+ private def companionImplicits(tp: Type): Infoss = {
val partMap = new LinkedHashMap[Symbol, Type]
/** Enter all parts of `tp` into `parts` set.
@@ -743,7 +777,8 @@ self: Analyzer =>
}
getParts(tp)
- val buf = new ListBuffer[List[ImplicitInfo]]
+
+ val buf = new ListBuffer[Infos]
for ((clazz, pre) <- partMap) {
if (pre != NoType) {
val companion = clazz.companionModule
@@ -763,7 +798,7 @@ self: Analyzer =>
* These are all implicits found in companion objects of classes C
* such that some part of `tp` has C as one of its superclasses.
*/
- private def implicitsOfExpectedType: List[List[ImplicitInfo]] = implicitsCache get pt match {
+ private def implicitsOfExpectedType: Infoss = implicitsCache get pt match {
case Some(implicitInfoss) =>
incCounter(implicitCacheHits)
implicitInfoss
@@ -921,7 +956,7 @@ self: Analyzer =>
}
def allImplicits: List[SearchResult] = {
- def search(iss: List[List[ImplicitInfo]], isLocal: Boolean) = applicableInfos(iss, isLocal)._2.values
+ def search(iss: Infoss, isLocal: Boolean) = applicableInfos(iss, isLocal).values
search(context.implicitss, true) ++ search(implicitsOfExpectedType, false) toList
}
}
diff --git a/src/compiler/scala/tools/nsc/util/HashSet.scala b/src/compiler/scala/tools/nsc/util/HashSet.scala
index 8e0c2e2e59..72d51343e2 100644
--- a/src/compiler/scala/tools/nsc/util/HashSet.scala
+++ b/src/compiler/scala/tools/nsc/util/HashSet.scala
@@ -61,6 +61,9 @@ class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) exte
used += 1
if (used > (table.length >> 2)) growTable()
}
+ def addEntries(xs: TraversableOnce[T]) {
+ xs foreach addEntry
+ }
def iterator = new Iterator[T] {
private var i = 0
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-20 08:57:57 +0000