/* NSC -- new Scala compiler
* Copyright 2005-2009 LAMP/EPFL
* @author Martin Odersky
*/
// $Id$
//todo: rewrite or disllow new T where T is a mixin (currently: <init> not a member of T)
//todo: use inherited type info also for vars and values
//todo: disallow C#D in superclass
//todo: treat :::= correctly
package scala.tools.nsc
package typechecker
import scala.collection.mutable.{LinkedHashMap, ListBuffer}
import scala.tools.nsc.util.{ HashSet, Position, Set, NoPosition, SourceFile }
import symtab.Flags._
/** This trait provides methods to find various kinds of implicits.
*
* @author Martin Odersky
* @version 1.0
*/
trait Implicits {
self: Analyzer =>
import global._
import definitions._
def traceImplicits = printTypings
var implicitTime = 0L
var inscopeSucceed = 0L
var inscopeFail = 0L
var oftypeSucceed = 0L
var oftypeFail = 0L
var manifSucceed = 0L
var manifFail = 0L
var hits = 0
var misses = 0
/** Search for an implicit value. See the comment on `result` at the end of class `ImplicitSearch`
* for more info how the search is conducted.
* @param tree The tree for which the implicit needs to be inserted.
* (the inference might instantiate some of the undetermined
* type parameters of that tree.
* @param pt The expected type of the implicit.
* @param reportAmbiguous Should ambiguous implicit errors be reported?
* False iff we search for a view to find out
* whether one type is coercible to another.
* @param isView We are looking for a view
* @param context The current context
* @return A search result
*/
def inferImplicit(tree: Tree, pt: Type, reportAmbiguous: Boolean, isView: Boolean, context: Context): SearchResult = {
if (traceImplicits && !tree.isEmpty && !context.undetparams.isEmpty)
println("typing implicit with undetermined type params: "+context.undetparams+"\n"+tree)
val result = new ImplicitSearch(tree, pt, isView, context.makeImplicit(reportAmbiguous)).bestImplicit
context.undetparams = context.undetparams filterNot (result.subst.from contains _)
result
}
final val sizeLimit = 50000
val implicitsCache = new LinkedHashMap[Type, List[List[ImplicitInfo]]]
def resetImplicits() { implicitsCache.clear() }
/** If type `pt` an instance of Manifest or OptManifest, or an abstract type lower-bounded
* by such an instance?
*/
def isManifest(pt: Type): Boolean = pt.dealias match {
case TypeRef(_, PartialManifestClass, List(_)) |
TypeRef(_, FullManifestClass, List(_)) |
TypeRef(_, OptManifestClass, List(_)) => true
case TypeRef(_, tsym, _) => tsym.isAbstractType && isManifest(pt.bounds.lo)
case _ => false
}
/** The result of an implicit search
* @param tree The tree representing the implicit
* @param subst A substituter that represents the undetermined type parameters
* that were instantiated by the winning implicit.
*/
class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter) {
override def toString = "SearchResult("+tree+", "+subst+")"
}
lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter)
/** A class that records an available implicit
* @param name The name of the implicit
* @param pre The prefix type of the implicit
* @param sym The symbol of the implicit
*/
class ImplicitInfo(val name: Name, val pre: Type, val sym: Symbol) {
private var tpeCache: Type = null
/** Computes member type of implicit from prefix `pre` (cached). */
def tpe: Type = {
if (tpeCache eq null) tpeCache = pre.memberType(sym)
tpeCache
}
/** Does type `tp` contain an Error type as parameter or result?
*/
private def containsError(tp: Type): Boolean = tp match {
case PolyType(tparams, restpe) => containsError(restpe)
case MethodType(params, restpe) => (params map (_.tpe) exists (_.isError)) || containsError(restpe)
case _ => tp.isError
}
def isCyclicOrErroneous = try {
containsError(tpe)
} catch {
case ex: CyclicReference =>
true
}
override def equals(other: Any) = other match {
case that: ImplicitInfo =>
this.name == that.name &&
this.pre =:= that.pre &&
this.sym == that.sym
case _ => false
}
override def hashCode =
name.hashCode + pre.hashCode + sym.hashCode
override def toString = "ImplicitInfo(" + name + "," + pre + "," + sym + ")"
}
/** A sentinel indicating no implicit was found */
val NoImplicitInfo = new ImplicitInfo(null, NoType, NoSymbol) {
// equals used to be implemented in ImplicitInfo with an `if(this eq NoImplicitInfo)`
// overriding the equals here seems cleaner and benchmarks show no difference in performance
override def equals(other: Any) = other match { case that: AnyRef => that eq this case _ => false }
override def hashCode = 1
}
/** A constructor for types ?{ name: tp }, used in infer view to member
* searches.
*/
def memberWildcardType(name: Name, tp: Type) = {
val result = refinedType(List(WildcardType), NoSymbol)
var psym = if (name.isTypeName) result.typeSymbol.newAbstractType(NoPosition, name)
else result.typeSymbol.newValue(NoPosition, name)
psym setInfo tp
result.decls enter psym
result
}
/** An extractor for types of the form ? { name: ? }
*/
object HasMember {
def apply(name: Name): Type = 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 _ => None
}
case _ =>
None
}
}
/** An extractor for types of the form ? { name: (? >: argtpe <: Any*)restp }
*/
object HasMethodMatching {
def apply(name: Name, argtpes: List[Type], restpe: Type): Type = {
def templateArgType(argtpe: Type) =
new BoundedWildcardType(mkTypeBounds(argtpe, AnyClass.tpe))
val dummyMethod = new TermSymbol(NoSymbol, NoPosition, "typer$dummy")
val mtpe = MethodType(dummyMethod.newSyntheticValueParams(argtpes map templateArgType), restpe)
memberWildcardType(name, mtpe)
}
def unapply(pt: Type): Option[(Name, List[Type], Type)] = pt match {
case RefinedType(List(WildcardType), decls) =>
decls.toList match {
case List(sym) =>
sym.tpe match {
case MethodType(params, restpe)
if (params forall (_.tpe.isInstanceOf[BoundedWildcardType])) =>
Some((sym.name, params map (_.tpe.bounds.lo), restpe))
case _ => None
}
case _ => None
}
case _ => None
}
}
/** An extractor for unary function types arg => res
*/
object Function1 {
def unapply(tp: Type) = tp match {
case TypeRef(_, sym, List(arg, res)) if (sym == FunctionClass(1)) => Some(arg, res)
case _ => None
}
}
/** A class that sets up an implicit search. For more info, see comments for `inferImplicit`.
* @param tree The tree for which the implicit needs to be inserted.
* @param pt The original expected type of the implicit.
* @param isView We are looking for a view
* @param context0 The context used for the implicit search
*/
class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context)
extends Typer(context0) {
// assert(tree.isEmpty || tree.pos.isDefined, tree)
import infer._
/** Is implicit info `info1` better than implicit info `info2`?
*/
def improves(info1: ImplicitInfo, info2: ImplicitInfo) =
(info2 == NoImplicitInfo) ||
(info1 != NoImplicitInfo) &&
isStrictlyMoreSpecific(info1.tpe, info2.tpe, info1.sym, info2.sym)
/** Map all type params in given list to WildcardType
* @param tp The type in which to do the mapping
* @param tparams The list of type parameters to map
*/
private def tparamsToWildcards(tp: Type, tparams: List[Symbol]) =
tp.instantiateTypeParams(tparams, tparams map (t => WildcardType))
/* Map a polytype to one in which all type parameters are replaced by wildcards.
*/
private def depoly(tp: Type): Type = tp match {
case PolyType(tparams, restpe) => tparamsToWildcards(restpe, tparams)
case _ => tp
}
/** Does type `dtor` dominate type `dted`?
* This is the case if the stripped cores `dtor1` and `dted1` of both types are
* the same wrt `=:=`, or if they overlap and the complexity of `dtor1` is higher
* than the complexity of `dted1`.
* The _stripped core_ of a type is the type where
* - all refinements and annotations are dropped,
* - all universal and existential quantification is eliminated
* by replacing variables by their upper bounds,
* - all remaining free type parameters in the type are replaced by WildcardType.
* The _complexity_ of a stripped core type corresponds roughly to the number of
* nodes in its ast, except that singleton types are widened befoe taking the complexity.
* Two types overlap if they have the same type symbol, or
* if one or both are intersection types with a pair of overlapiing parent types.
*/
private def dominates(dtor: Type, dted: Type): Boolean = {
def core(tp: Type): Type = tp.normalize match {
case RefinedType(parents, defs) => intersectionType(parents map core, tp.typeSymbol.owner)
case AnnotatedType(annots, tp, selfsym) => core(tp)
case ExistentialType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi)))
case PolyType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi)))
case _ => tp
}
def stripped(tp: Type): Type = {
val tparams = freeTypeParametersNoSkolems.collect(tp)
tp.subst(tparams, tparams map (t => WildcardType))
}
def sum(xs: List[Int]) = (0 /: xs)(_ + _)
def complexity(tp: Type): Int = tp.normalize match {
case NoPrefix =>
0
case SingleType(pre, sym) =>
if (sym.isPackage) 0 else complexity(tp.widen)
case TypeRef(pre, sym, args) =>
complexity(pre) + sum(args map complexity) + 1
case RefinedType(parents, _) =>
sum(parents map complexity) + 1
case _ =>
1
}
def overlaps(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match {
case (RefinedType(parents, _), _) => parents exists (overlaps(_, tp2))
case (_, RefinedType(parents, _)) => parents exists (overlaps(tp1, _))
case _ => tp1.typeSymbol == tp2.typeSymbol
}
val dtor1 = stripped(core(dtor))
val dted1 = stripped(core(dted))
overlaps(dtor1, dted1) && (dtor1 =:= dted1 || complexity(dtor1) > complexity(dted1))
}
if (util.Statistics.enabled) implcnt += 1
/** Issues an error signalling ambiguous implicits */
private def ambiguousImplicitError(info1: ImplicitInfo, info2: ImplicitInfo,
pre1: String, pre2: String, trailer: String) =
if (!info1.tpe.isErroneous && !info2.tpe.isErroneous) {
val coreMsg =
pre1+" "+info1.sym+info1.sym.locationString+" of type "+info1.tpe+"\n "+
pre2+" "+info2.sym+info2.sym.locationString+" of type "+info2.tpe+"\n "+
trailer
error(tree.pos,
if (isView) {
val found = pt.typeArgs(0)
val req = pt.typeArgs(1)
typeErrorMsg(found, req)+
"\nNote that implicit conversions are not applicable because they are ambiguous:\n "+
coreMsg+"are possible conversion functions from "+ found+" to "+req
} else {
"ambiguous implicit values:\n "+coreMsg + "match expected type "+pt
})
}
/** The type parameters to instantiate */
val undetParams = if (isView) List() else context.outer.undetparams
/** Try to construct a typed tree from given implicit info with given
* expected type.
* Detect infinite search trees for implicits.
*
* @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 =
context.openImplicits find (dominates(pt, _)) match {
case Some(pending) =>
// println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
throw DivergentImplicit
SearchFailure
case None =>
try {
context.openImplicits = pt :: context.openImplicits
// println(" "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
typedImplicit0(info)
} catch {
case DivergentImplicit =>
// println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
if (context.openImplicits.tail.isEmpty) {
if (!(pt.isErroneous))
context.unit.error(
tree.pos, "diverging implicit expansion for type "+pt+"\nstarting with "+
info.sym+info.sym.locationString)
SearchFailure
} else {
throw DivergentImplicit
}
} finally {
context.openImplicits = context.openImplicits.tail
}
}
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
}
/** Replace undetParams in type `tp` by Any/Nothing, according to variance */
def approximate(tp: Type) =
tp.instantiateTypeParams(undetParams, undetParams map (_ => WildcardType))
/** Instantiated `pt' so that undetermined type parameters are replaced by wildcards
*/
val wildPt = approximate(pt)
/** 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'.
*/
def matchesPt(tp: Type, pt: Type, undet: List[Symbol]) =
isCompatible(tp, pt) || {
pt match {
case Function1(arg, HasMethodMatching(name, argtpes, restpe)) =>
normalize(tp) match {
case Function1(arg1, res1) =>
(arg <:< arg1) &&
(res1.member(name) filter (m => isApplicableSafe(undet, m.tpe, argtpes, restpe))) != NoSymbol
case _ =>
false
}
case _ =>
false
}
}
//if (traceImplicits) println("typed impl for "+wildPt+"? "+info.name+":"+depoly(info.tpe)+"/"+undetParams+"/"+isPlausiblyCompatible(info.tpe, wildPt)+"/"+matchesPt(depoly(info.tpe), wildPt, List()))
if (isPlausiblyCompatible(info.tpe, wildPt) &&
matchesPt(depoly(info.tpe), wildPt, List()) &&
isStable(info.pre)) {
val itree = atPos(tree.pos.focus) {
if (info.pre == NoPrefix) Ident(info.name)
else Select(gen.mkAttributedQualifier(info.pre), info.name)
}
if (traceImplicits) println("typed impl?? "+info.name+":"+info.tpe+" ==> "+itree+" with pt = "+pt+", wildpt = "+wildPt)
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)
if (traceImplicits) println("typed implicit "+itree1+":"+itree1.tpe+", pt = "+wildPt)
val itree2 = if (isView) (itree1: @unchecked) match { case Apply(fun, _) => fun }
else adapt(itree1, EXPRmode, wildPt)
if (traceImplicits) println("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, name) => name == 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)) {
if (traceImplicits) println("tvars = "+tvars+"/"+(tvars map (_.constr)))
val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt),
false, lubDepth(List(itree2.tpe, pt)))
checkBounds(itree2.pos, NoPrefix, NoSymbol, undetParams, targs, "inferred ") // #2421
val subst = new TreeTypeSubstituter(undetParams, targs)
subst traverse itree2
// todo: remove type params that have been instantiated to Nothing, similar
// to methTypeArgs
val result = new SearchResult(itree2, subst)
if (traceImplicits) println("RESULT = "+result)
// println("RESULT = "+itree+"///"+itree1+"///"+itree2)//DEBUG
result
} else {
if (traceImplicits) println("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())
}
} else {
SearchFailure
}
}
/** 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
* - the symbol comes from a classfile
* - the symbol comes from a different sourcefile than the current one
* - the symbol's definition comes before, and does not contain the closest enclosing definition,
* - the symbol's definition is a val, var, or def with an explicit result type
* The aim of this method is to prevent premature cyclic reference errors
* by computing the types of only those implicitis for which one of these
* conditions is true.
*/
def isValid(sym: Symbol) = {
def hasExplicitResultType(sym: Symbol) = {
def hasExplicitRT(tree: Tree) = tree match {
case ValDef(_, _, tpt, _) => !tpt.isEmpty
case DefDef(_, _, _, _, tpt, _) => !tpt.isEmpty
case _ => false
}
sym.rawInfo match {
case tc: TypeCompleter => hasExplicitRT(tc.tree)
case PolyType(_, tc: TypeCompleter) => hasExplicitRT(tc.tree)
case _ => true
}
}
def comesBefore(sym: Symbol, owner: Symbol) =
sym.pos.pointOrElse(0) < owner.pos.pointOrElse(Integer.MAX_VALUE) &&
!(owner.ownerChain contains sym)
sym.isInitialized ||
sym.sourceFile == null ||
(sym.sourceFile ne context.unit.source.file) ||
hasExplicitResultType(sym) ||
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).
* @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.
*/
def applicableInfos(iss: List[List[ImplicitInfo]],
isLocal: Boolean,
invalidImplicits: ListBuffer[Symbol]): Map[ImplicitInfo, SearchResult] = {
/** A set containing names that are shadowed by implicit infos */
lazy val shadowed = new HashSet[Name]("shadowed", 512)
/** 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.
*/
def tryImplicit(info: ImplicitInfo): SearchResult =
if (info.isCyclicOrErroneous ||
(isLocal && shadowed.contains(info.name)) ||
(isView && (info.sym == Predef_identity || info.sym == Predef_conforms)) //@M this condition prevents no-op conversions, which are a problem (besides efficiency),
// TODO: remove `info.sym == Predef_identity` once we have a new STARR that only has conforms as an implicit
// one example is removeNames in NamesDefaults, which relies on the type checker failing in case of ambiguity between an assignment/named arg
) SearchFailure
else typedImplicit(info)
def appInfos(is: List[ImplicitInfo]): Map[ImplicitInfo, SearchResult] = {
var applicable = Map[ImplicitInfo, SearchResult]()
for (i <- is)
if (!isValid(i.sym)) invalidImplicits += i.sym
else {
val result = tryImplicit(i)
if (result != SearchFailure) applicable += (i -> result)
}
if (isLocal)
for (i <- is) shadowed addEntry i.name
applicable
}
(Map[ImplicitInfo, SearchResult]() /: (iss map appInfos))(_ ++ _)
}
/** 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.
*
* @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: 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.
*/
val invalidImplicits = new ListBuffer[Symbol]
/** A map which takes applicable infos to their attributed trees. */
val applicable = applicableInfos(implicitInfoss, isLocal, invalidImplicits)
if (applicable.isEmpty && !invalidImplicits.isEmpty) {
infer.setAddendum(tree.pos, () =>
"\n Note: implicit "+invalidImplicits.head+" is not applicable here"+
"\n because it comes after the application point and it lacks an explicit result type")
}
/** 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 dropWhile (alt => best == alt || improves(best, alt))
if (!competing.isEmpty) ambiguousImplicitError(best, competing.head, "both", "and", "")
// Also check that applicable infos that did not get selected are not
// in (a companion object of) a subclass of (a companion object of) the class
// containing the winning info.
// (no longer needed; rules have changed)
/*
for (alt <- applicable.keySet) {
if (isProperSubClassOrObject(alt.sym.owner, best.sym.owner)) {
ambiguousImplicitError(best, alt,
"most specific definition is:",
"yet alternative definition ",
"is defined in a subclass.\n Both definitions ")
}
}
*/
applicable(best)
}
} // end searchImplicit
/** The implicits made available directly by class type `tp`.
* If `tp` refers to class C, these are all implicit members of the companion object of C.
*/
private def implicitsOfClass(tp: Type): List[ImplicitInfo] = tp match {
case TypeRef(pre, clazz, _) =>
clazz.initialize.linkedClassOfClass.info.members.toList.filter(_.hasFlag(IMPLICIT)) map
(sym => new ImplicitInfo(sym.name, pre.memberType(clazz.linkedModuleOfClass), sym))
case _ =>
List()
}
/** The parts of a type is the smallest set of types that contains
* - the type itself
* - the parts of its immediate components (prefix and argument)
* - the parts of its base types
*/
private def parts(tp: Type): List[Type] = {
val partMap = new collection.mutable.LinkedHashMap[Symbol, List[Type]]
/** Add a new type to partMap, unless a subtype of it with the same
* type symbol exists already.
*/
def addType(newtp: Type): Boolean = {
val tsym = newtp.typeSymbol
partMap.get(tsym) match {
case Some(ts) =>
if (ts exists (_ <:< newtp)) false
else { partMap.put(tsym, newtp :: ts); true }
case None =>
partMap.put(tsym, List(newtp)); true
}
}
/** Enter all parts of `tp` into `partMap`
*/
def getParts(tp: Type) {
tp match {
case TypeRef(pre, sym, args) if (!sym.isPackageClass) =>
if (sym.isClass && !sym.isRefinementClass && !sym.isAnonymousClass) {
if (addType(tp)) {
for (bc <- sym.ancestors)
getParts(tp.baseType(bc))
getParts(pre)
args foreach getParts
}
} else if (sym.isAliasType) {
getParts(tp.normalize)
} else if (sym.isAbstractType) {
getParts(tp.bounds.hi)
}
case ThisType(_) =>
getParts(tp.widen)
case _: SingletonType =>
getParts(tp.widen)
case RefinedType(ps, _) =>
for (p <- ps) getParts(p)
case AnnotatedType(_, t, _) =>
getParts(t)
case ExistentialType(tparams, t) =>
getParts(t)
case _ =>
}
}
/** Gives a list of typerefs with the same type symbol,
* remove all those that have a prefix which is a supertype
* of some other elements's prefix.
*/
def compactify(ts: List[Type]): List[Type] = ts match {
case List() => ts
case (t @ TypeRef(pre, _, _)) :: ts1 =>
if (ts1 exists (_.prefix <:< pre)) compactify(ts1)
else t :: compactify(ts1 filterNot (pre <:< _.prefix))
}
getParts(tp)
for ((k, ts) <- partMap.iterator.toList; t <- compactify(ts)) yield t
}
/** The implicits made available by type `pt`.
* 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 {
case Some(implicitInfoss) => hits += 1; implicitInfoss
case None => {
misses += 1
val implicitInfoss = parts(pt).iterator.map(implicitsOfClass).toList
implicitsCache(pt) = implicitInfoss
if (implicitsCache.size >= sizeLimit)
implicitsCache -= implicitsCache.keysIterator.next
implicitInfoss
}
}
/** The manifest corresponding to type `pt`, provided `pt` is an instance of Manifest.
*/
private def implicitManifest(pt: Type): Tree = pt.dealias match {
case TypeRef(_, FullManifestClass, List(arg)) =>
manifestOfType(arg, true)
case TypeRef(_, PartialManifestClass, List(arg)) =>
manifestOfType(arg, false)
case TypeRef(_, OptManifestClass, List(arg)) =>
val itree = manifestOfType(arg, false)
if (itree == EmptyTree) gen.mkAttributedRef(NoManifest) else itree
case TypeRef(_, tsym, _) if (tsym.isAbstractType) =>
implicitManifest(pt.bounds.lo)
case _ =>
EmptyTree
}
/** Creates a tree that calls the relevant factory method in object
* reflect.Manifest for type 'tp'. An EmptyTree is returned if
* no manifest is found. todo: make this instantiate take type params as well?
*/
private def manifestOfType(tp: Type, full: Boolean): Tree = {
/** Creates a tree that calls the factory method called constructor in object reflect.Manifest */
def manifestFactoryCall(constructor: String, tparg: Type, args: Tree*): Tree =
if (args contains EmptyTree) EmptyTree
else
typed { atPos(tree.pos.focus) {
Apply(
TypeApply(
Select(gen.mkAttributedRef(if (full) FullManifestModule else PartialManifestModule), constructor),
List(TypeTree(tparg))
),
args.toList
)
}}
/** Re-wraps a type in a manifest before calling inferImplicit on the result */
def findManifest(tp: Type, manifestClass: Symbol = if (full) FullManifestClass else PartialManifestClass) =
inferImplicit(tree, appliedType(manifestClass.typeConstructor, List(tp)), true, false, context).tree
def findSubManifest(tp: Type) = findManifest(tp, if (full) FullManifestClass else OptManifestClass)
def mot(tp0: Type): Tree = tp0.normalize match {
case ThisType(_) | SingleType(_, _) =>
manifestFactoryCall("singleType", tp, gen.mkAttributedQualifier(tp0))
case ConstantType(value) =>
manifestOfType(tp0.deconst, full)
case TypeRef(pre, sym, args) =>
if (isValueClass(sym) || isPhantomClass(sym)) {
typed { atPos(tree.pos.focus) {
Select(gen.mkAttributedRef(FullManifestModule), sym.name.toString)
}}
} else if (sym == ArrayClass && args.length == 1) {
manifestFactoryCall("arrayType", args.head, findSubManifest(args.head))
} else if (sym.isClass) {
val suffix = gen.mkClassOf(tp0) :: (args map findSubManifest)
manifestFactoryCall(
"classType", tp,
(if ((pre eq NoPrefix) || pre.typeSymbol.isStaticOwner) suffix
else findSubManifest(pre) :: suffix): _*)
} else if (sym.isAbstractType) {
if (sym.isExistential)
EmptyTree // todo: change to existential parameter manifest
else if (sym.isTypeParameterOrSkolem)
EmptyTree // a manifest should have been found by normal searchImplicit
else
manifestFactoryCall(
"abstractType", tp,
findSubManifest(pre) :: Literal(sym.name.toString) :: findManifest(tp0.bounds.hi) :: (args map findSubManifest): _*)
} else {
EmptyTree // a manifest should have been found by normal searchImplicit
}
case RefinedType(parents, decls) =>
// refinement is not generated yet
if (parents.length == 1) findManifest(parents.head)
else manifestFactoryCall("intersectionType", tp, parents map (findSubManifest(_)): _*)
case ExistentialType(tparams, result) =>
existentialAbstraction(tparams, result) match {
case ExistentialType(_, _) => mot(result)
case t => mot(t)
}
case _ =>
EmptyTree
}
mot(tp)
}
/** The result of the implicit search:
* First search implicits visible in current context.
* If that fails, search implicits in expected type `pt`.
* If that fails, and `pt` is an instance of Manifest, try to construct a manifest.
* If all fails return SearchFailure
*/
def bestImplicit: SearchResult = {
val start = System.nanoTime()
var result = searchImplicit(context.implicitss, true)
val timer1 = System.nanoTime()
if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start
if (result == SearchFailure)
result = searchImplicit(implicitsOfExpectedType, false)
val timer2 = System.nanoTime()
if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1
if (result == SearchFailure) {
val resultTree = implicitManifest(pt)
if (resultTree != EmptyTree) result = new SearchResult(resultTree, EmptyTreeTypeSubstituter)
}
val timer3 = System.nanoTime()
if (result == SearchFailure) manifFail += timer3 - timer2 else manifSucceed += timer3 - timer2
if (result == SearchFailure && settings.debug.value)
log("no implicits found for "+pt+" "+pt.typeSymbol.info.baseClasses+" "+parts(pt)+implicitsOfExpectedType)
implicitTime += System.nanoTime() - start
result
}
def allImplicits: List[SearchResult] = {
val invalidImplicits = new ListBuffer[Symbol]
def search(iss: List[List[ImplicitInfo]], isLocal: Boolean) =
applicableInfos(iss, isLocal, invalidImplicits).valuesIterator.toList
search(context.implicitss, true) ::: search(implicitsOfExpectedType, false)
}
}
private val DivergentImplicit = new Exception()
}