diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/Implicits.scala | 519 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/util/HashSet.scala | 3 |
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 |