Scala example source code file (Implicits.scala)
The Implicits.scala Scala example source code/* NSC -- new Scala compiler
* Copyright 2005-2013 LAMP/EPFL
* @author Martin Odersky
*/
//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
package tools.nsc
package typechecker
import scala.annotation.tailrec
import scala.collection.{ mutable, immutable }
import mutable.{ LinkedHashMap, ListBuffer }
import scala.util.matching.Regex
import symtab.Flags._
import scala.reflect.internal.util.{TriState, Statistics}
import scala.language.implicitConversions
/** This trait provides methods to find various kinds of implicits.
*
* @author Martin Odersky
* @version 1.0
*/
trait Implicits {
self: Analyzer =>
import global._
import definitions._
import ImplicitsStats._
import typingStack.{ printTyping }
import typeDebug._
def inferImplicit(tree: Tree, pt: Type, reportAmbiguous: Boolean, isView: Boolean, context: Context): SearchResult =
inferImplicit(tree, pt, reportAmbiguous, isView, context, saveAmbiguousDivergent = true, tree.pos)
def inferImplicit(tree: Tree, pt: Type, reportAmbiguous: Boolean, isView: Boolean, context: Context, saveAmbiguousDivergent: Boolean): SearchResult =
inferImplicit(tree, pt, reportAmbiguous, isView, context, saveAmbiguousDivergent, tree.pos)
/** 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
* @param saveAmbiguousDivergent False if any divergent/ambiguous errors should be ignored after
* implicits search,
* true if they should be reported (used in further typechecking).
* @param pos Position that is should be used for tracing and error reporting
* (useful when we infer synthetic stuff and pass EmptyTree in the `tree` argument)
* If it's set NoPosition, then position-based services will use `tree.pos`
* @return A search result
*/
def inferImplicit(tree: Tree, pt: Type, reportAmbiguous: Boolean, isView: Boolean, context: Context, saveAmbiguousDivergent: Boolean, pos: Position): SearchResult = {
// Note that the isInvalidConversionTarget seems to make a lot more sense right here, before all the
// work is performed, than at the point where it presently exists.
val shouldPrint = printTypings && !context.undetparams.isEmpty
val rawTypeStart = if (Statistics.canEnable) Statistics.startCounter(rawTypeImpl) else null
val findMemberStart = if (Statistics.canEnable) Statistics.startCounter(findMemberImpl) else null
val subtypeStart = if (Statistics.canEnable) Statistics.startCounter(subtypeImpl) else null
val start = if (Statistics.canEnable) Statistics.startTimer(implicitNanos) else null
if (shouldPrint)
typingStack.printTyping(tree, "typing implicit: %s %s".format(tree, context.undetparamsString))
val implicitSearchContext = context.makeImplicit(reportAmbiguous)
val result = new ImplicitSearch(tree, pt, isView, implicitSearchContext, pos).bestImplicit
if (result.isFailure && saveAmbiguousDivergent && implicitSearchContext.hasErrors) {
context.updateBuffer(implicitSearchContext.reportBuffer.errors.collect {
case dte: DivergentImplicitTypeError => dte
case ate: AmbiguousImplicitTypeError => ate
})
debuglog("update buffer: " + implicitSearchContext.reportBuffer.errors)
}
// SI-7944 undetermined type parameters that result from inference within typedImplicit land in
// `implicitSearchContext.undetparams`, *not* in `context.undetparams`
// Here, we copy them up to parent context (analogously to the way the errors are copied above),
// and then filter out any which *were* inferred and are part of the substitutor in the implicit search result.
context.undetparams = ((context.undetparams ++ result.undetparams) filterNot result.subst.from.contains).distinct
if (Statistics.canEnable) Statistics.stopTimer(implicitNanos, start)
if (Statistics.canEnable) Statistics.stopCounter(rawTypeImpl, rawTypeStart)
if (Statistics.canEnable) Statistics.stopCounter(findMemberImpl, findMemberStart)
if (Statistics.canEnable) Statistics.stopCounter(subtypeImpl, subtypeStart)
result
}
/** A friendly wrapper over inferImplicit to be used in macro contexts and toolboxes.
*/
def inferImplicit(tree: Tree, pt: Type, isView: Boolean, context: Context, silent: Boolean, withMacrosDisabled: Boolean, pos: Position, onError: (Position, String) => Unit): Tree = {
val wrapper1 = if (!withMacrosDisabled) (context.withMacrosEnabled[SearchResult] _) else (context.withMacrosDisabled[SearchResult] _)
def wrapper(inference: => SearchResult) = wrapper1(inference)
val result = wrapper(inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos))
if (result.isFailure && !silent) {
val err = context.firstError
val errPos = err.map(_.errPos).getOrElse(pos)
val errMsg = err.map(_.errMsg).getOrElse("implicit search has failed. to find out the reason, turn on -Xlog-implicits")
onError(errPos, errMsg)
}
result.tree
}
/** Find all views from type `tp` (in which `tpars` are free)
*
* Note that the trees in the search results in the returned list share the same type variables.
* Ignore their constr field! The list of type constraints returned along with each tree specifies the constraints that
* must be met by the corresponding type parameter in `tpars` (for the returned implicit view to be valid).
*
* @arg tp from-type for the implicit conversion
* @arg context search implicits here
* @arg tpars symbols that should be considered free type variables
* (implicit search should not try to solve them, just track their constraints)
*/
def allViewsFrom(tp: Type, context: Context, tpars: List[Symbol]): List[(SearchResult, List[TypeConstraint])] = {
// my untouchable typevars are better than yours (they can't be constrained by them)
val tvars = tpars map (TypeVar untouchable _)
val tpSubsted = tp.subst(tpars, tvars)
val search = new ImplicitSearch(EmptyTree, functionType(List(tpSubsted), AnyTpe), true, context.makeImplicit(reportAmbiguousErrors = false))
search.allImplicitsPoly(tvars)
}
private final val sizeLimit = 50000
private type Infos = List[ImplicitInfo]
private type Infoss = List[List[ImplicitInfo]]
private type InfoMap = LinkedHashMap[Symbol, List[ImplicitInfo]] // A map from class symbols to their associated implicits
private val implicitsCache = new LinkedHashMap[Type, Infoss]
private val infoMapCache = new LinkedHashMap[Symbol, InfoMap]
private val improvesCache = perRunCaches.newMap[(ImplicitInfo, ImplicitInfo), Boolean]()
private val implicitSearchId = { var id = 1 ; () => try id finally id += 1 }
private def isInvalidConversionSource(tpe: Type): Boolean = tpe match {
case Function1(in, _) => in <:< NullClass.tpe
case _ => false
}
def resetImplicits() {
implicitsCache.clear()
infoMapCache.clear()
improvesCache.clear()
}
/* Map a polytype to one in which all type parameters and argument-dependent types are replaced by wildcards.
* Consider `implicit def b(implicit x: A): x.T = error("")`. We need to approximate debruijn index types
* when checking whether `b` is a valid implicit, as we haven't even searched a value for the implicit arg `x`,
* so we have to approximate (otherwise it is excluded a priori).
*/
private def depoly(tp: Type): Type = tp match {
case PolyType(tparams, restpe) => deriveTypeWithWildcards(tparams)(ApproximateDependentMap(restpe))
case _ => ApproximateDependentMap(tp)
}
/** 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.
* @param undetparams undeterminted type parameters
*/
class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter, val undetparams: List[Symbol]) {
override def toString = "SearchResult(%s, %s)".format(tree,
if (subst.isEmpty) "" else subst)
def isFailure = false
def isAmbiguousFailure = false
def isDivergent = false
final def isSuccess = !isFailure
}
lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
override def isFailure = true
}
lazy val DivergentSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
override def isFailure = true
override def isDivergent = true
}
lazy val AmbiguousSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
override def isFailure = true
override def isAmbiguousFailure = true
}
/** 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
private var isCyclicOrErroneousCache: TriState = TriState.Unknown
/** Computes member type of implicit from prefix `pre` (cached). */
def tpe: Type = {
if (tpeCache eq null) tpeCache = pre.memberType(sym)
tpeCache
}
def isCyclicOrErroneous: Boolean = {
if (!isCyclicOrErroneousCache.isKnown) isCyclicOrErroneousCache = computeIsCyclicOrErroneous
isCyclicOrErroneousCache.booleanValue
}
private[this] final def computeIsCyclicOrErroneous =
try sym.hasFlag(LOCKED) || containsError(tpe)
catch { case _: CyclicReference => true }
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 {
case PolyType(tparams, restpe) =>
containsError(restpe)
case NullaryMethodType(restpe) =>
containsError(restpe)
case mt @ MethodType(_, restpe) =>
// OPT avoiding calling `mt.paramTypes` which creates a new list.
(mt.params exists symTypeIsError) || containsError(restpe)
case _ =>
tp.isError
}
def isStablePrefix = pre.isStable
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.## + pre.## + sym.##
override def toString = (
if (tpeCache eq null) name + ": ?"
else name + ": " + tpe
)
}
/** A class which is used to track pending implicits to prevent infinite implicit searches.
*/
case class OpenImplicit(info: ImplicitInfo, pt: Type, tree: Tree)
/** 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 ?{ def/type name: tp }, used in infer view to member
* searches.
*/
def memberWildcardType(name: Name, tp: Type) = {
val result = refinedType(List(WildcardType), NoSymbol)
name match {
case x: TermName => result.typeSymbol.newMethod(x) setInfoAndEnter tp
case x: TypeName => result.typeSymbol.newAbstractType(x) setInfoAndEnter tp
}
result
}
/** An extractor for types of the form ? { name: ? }
*/
object HasMember {
private val hasMemberCache = perRunCaches.newMap[Name, Type]()
def apply(name: Name): Type = hasMemberCache.getOrElseUpdate(name, memberWildcardType(name, WildcardType))
}
/** An extractor for types of the form ? { name: (? >: argtpe <: Any*)restp }
*/
object HasMethodMatching {
val dummyMethod = NoSymbol.newTermSymbol("typer$dummy") setInfo NullaryMethodType(AnyTpe)
def templateArgType(argtpe: Type) = new BoundedWildcardType(TypeBounds.lower(argtpe))
def apply(name: Name, argtpes: List[Type], restpe: Type): Type = {
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 {
val Sym = FunctionClass(1)
// It is tempting to think that this should be inspecting "tp baseType Sym"
// rather than tp. See test case run/t8280 and the commit message which
// accompanies it for explanation why that isn't done.
def unapply(tp: Type) = tp match {
case TypeRef(_, Sym, arg1 :: arg2 :: _) => Some((arg1, arg2))
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
* @param pos0 Position that is preferable for use in tracing and error reporting
* (useful when we infer synthetic stuff and pass EmptyTree in the `tree` argument)
* If it's set to NoPosition, then position-based services will use `tree.pos`
*/
class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context, pos0: Position = NoPosition) extends Typer(context0) with ImplicitsContextErrors {
val searchId = implicitSearchId()
private def typingLog(what: String, msg: => String) =
typingStack.printTyping(tree, f"[search #$searchId] $what $msg")
import infer._
if (Statistics.canEnable) Statistics.incCounter(implicitSearchCount)
/** The type parameters to instantiate */
val undetParams = if (isView) Nil else context.outer.undetparams
val wildPt = approximate(pt)
private val runDefintions = currentRun.runDefinitions
import runDefintions._
def undet_s = if (undetParams.isEmpty) "" else undetParams.mkString(" inferring ", ", ", "")
def tree_s = typeDebug ptTree tree
def ctx_s = fullSiteString(context)
typingLog("start", s"`$tree_s`$undet_s, searching for adaptation to pt=$pt $ctx_s")
def pos = if (pos0 != NoPosition) pos0 else tree.pos
def failure(what: Any, reason: String, pos: Position = this.pos): SearchResult = {
if (settings.XlogImplicits)
reporter.echo(pos, what+" is not a valid implicit value for "+pt+" because:\n"+reason)
SearchFailure
}
/** Is implicit info `info1` better than implicit info `info2`?
*/
def improves(info1: ImplicitInfo, info2: ImplicitInfo) = {
if (Statistics.canEnable) Statistics.incCounter(improvesCount)
(info2 == NoImplicitInfo) ||
(info1 != NoImplicitInfo) && {
if (info1.sym.isStatic && info2.sym.isStatic) {
improvesCache get ((info1, info2)) match {
case Some(b) => if (Statistics.canEnable) Statistics.incCounter(improvesCachedCount); b
case None =>
val result = isStrictlyMoreSpecific(info1.tpe, info2.tpe, info1.sym, info2.sym)
improvesCache((info1, info2)) = result
result
}
} else isStrictlyMoreSpecific(info1.tpe, info2.tpe, info1.sym, info2.sym)
}
}
def isPlausiblyCompatible(tp: Type, pt: Type) = checkCompatibility(fast = true, tp, pt)
def normSubType(tp: Type, pt: Type) = checkCompatibility(fast = false, tp, pt)
/** 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 before 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 overlapping parent types.
*/
private def dominates(dtor: Type, dted: Type): Boolean = {
def core(tp: Type): Type = tp.dealiasWiden match {
case RefinedType(parents, defs) => intersectionType(parents map core, tp.typeSymbol.owner)
case AnnotatedType(annots, tp) => 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 = {
// `t.typeSymbol` returns the symbol of the normalized type. If that normalized type
// is a `PolyType`, the symbol of the result type is collected. This is precisely
// what we require for SI-5318.
val syms = for (t <- tp; if t.typeSymbol.isTypeParameter) yield t.typeSymbol
deriveTypeWithWildcards(syms.distinct)(tp)
}
def complexity(tp: Type): Int = tp.dealias match {
case NoPrefix => 0
case SingleType(pre, sym) => if (sym.hasPackageFlag) 0 else complexity(tp.dealiasWiden)
case ThisType(sym) => if (sym.hasPackageFlag) 0 else 1
case TypeRef(pre, sym, args) => complexity(pre) + (args map complexity).sum + 1
case RefinedType(parents, _) => (parents map complexity).sum + 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))
}
/** The expected type with all undetermined type parameters replaced with wildcards. */
def approximate(tp: Type) = deriveTypeWithWildcards(undetParams)(tp)
/** 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
* @param isLocalToCallsite Is the implicit in the local scope of the call site?
* @pre `info.tpe` does not contain an error
*/
private def typedImplicit(info: ImplicitInfo, ptChecked: Boolean, isLocalToCallsite: Boolean): SearchResult = {
// SI-7167 let implicit macros decide what amounts for a divergent implicit search
// imagine a macro writer which wants to synthesize a complex implicit Complex[T] by making recursive calls to Complex[U] for its parts
// e.g. we have `class Foo(val bar: Bar)` and `class Bar(val x: Int)`
// then it's quite reasonable for the macro writer to synthesize Complex[Foo] by calling `inferImplicitValue(typeOf[Complex[Bar])`
// however if we didn't insert the `info.sym.isMacro` check here, then under some circumstances
// (e.g. as described here http://groups.google.com/group/scala-internals/browse_thread/thread/545462b377b0ac0a)
// `dominates` might decide that `Bar` dominates `Foo` and therefore a recursive implicit search should be prohibited
// now when we yield control of divergent expansions to the macro writer, what happens next?
// in the worst case, if the macro writer is careless, we'll get a StackOverflowException from repeated macro calls
// otherwise, the macro writer could check `c.openMacros` and `c.openImplicits` and do `c.abort` when expansions are deemed to be divergent
// upon receiving `c.abort` the typechecker will decide that the corresponding implicit search has failed
// which will fail the entire stack of implicit searches, producing a nice error message provided by the programmer
(context.openImplicits find { case OpenImplicit(info, tp, tree1) => !info.sym.isMacro && tree1.symbol == tree.symbol && dominates(pt, tp)}) match {
case Some(pending) =>
//println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
DivergentSearchFailure
case None =>
try {
context.openImplicits = OpenImplicit(info, pt, tree) :: context.openImplicits
// println(" "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
val result = typedImplicit0(info, ptChecked, isLocalToCallsite)
if (result.isDivergent) {
//println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
if (context.openImplicits.tail.isEmpty && !pt.isErroneous)
DivergingImplicitExpansionError(tree, pt, info.sym)(context)
}
result
} finally {
context.openImplicits = context.openImplicits.tail
}
}
}
/** 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]): Boolean = {
val start = if (Statistics.canEnable) Statistics.startTimer(matchesPtNanos) else null
val result = normSubType(tp, pt) || isView && {
pt match {
case Function1(arg1, arg2) => matchesPtView(tp, arg1, arg2, undet)
case _ => false
}
}
if (Statistics.canEnable) Statistics.stopTimer(matchesPtNanos, start)
result
}
private def matchesPt(info: ImplicitInfo): Boolean = (
info.isStablePrefix && matchesPt(depoly(info.tpe), wildPt, Nil)
)
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
}
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
}
}
/** Capturing the overlap between isPlausiblyCompatible and normSubType.
* This is a faithful translation of the code which was there, but it
* seems likely the methods are intended to be even more similar than
* they are: perhaps someone more familiar with the intentional distinctions
* can examine the now much smaller concrete implementations below.
*/
private def checkCompatibility(fast: Boolean, tp0: Type, pt0: Type): Boolean = {
@tailrec def loop(tp: Type, pt: Type): Boolean = tp match {
case mt @ MethodType(params, restpe) =>
if (mt.isImplicit)
loop(restpe, pt)
else pt match {
case tr @ TypeRef(pre, sym, args) =>
if (sym.isAliasType) loop(tp, pt.dealias)
else if (sym.isAbstractType) loop(tp, pt.bounds.lo)
else {
val len = args.length - 1
hasLength(params, len) &&
sym == FunctionClass(len) && {
var ps = params
var as = args
if (fast) {
while (ps.nonEmpty && as.nonEmpty) {
if (!isPlausiblySubType(as.head, ps.head.tpe))
return false
ps = ps.tail
as = as.tail
}
} else {
while (ps.nonEmpty && as.nonEmpty) {
if (!(as.head <:< ps.head.tpe))
return false
ps = ps.tail
as = as.tail
}
}
ps.isEmpty && as.nonEmpty && {
val lastArg = as.head
as.tail.isEmpty && loop(restpe, lastArg)
}
}
}
case _ => if (fast) false else tp <:< pt
}
case NullaryMethodType(restpe) => loop(restpe, pt)
case PolyType(_, restpe) => loop(restpe, pt)
case ExistentialType(_, qtpe) => if (fast) loop(qtpe, pt) else normalize(tp) <:< pt // is !fast case needed??
case _ => if (fast) isPlausiblySubType(tp, pt) else tp <:< pt
}
loop(tp0, pt0)
}
/** This expresses more cleanly in the negative: there's a linear path
* to a final true or false.
*/
private def isPlausiblySubType(tp1: Type, tp2: Type) = !isImpossibleSubType(tp1, tp2)
private def isImpossibleSubType(tp1: Type, tp2: Type) = tp1.dealiasWiden match {
// We can only rule out a subtype relationship if the left hand
// side is a class, else we may not know enough.
case tr1 @ TypeRef(_, sym1, _) if sym1.isClass =>
tp2.dealiasWiden match {
case TypeRef(_, sym2, _) => ((sym1 eq ByNameParamClass) != (sym2 eq ByNameParamClass)) || (sym2.isClass && !(sym1 isWeakSubClass sym2))
case RefinedType(parents, decls) => decls.nonEmpty && tr1.member(decls.head.name) == NoSymbol
case _ => false
}
case _ => false
}
private def typedImplicit0(info: ImplicitInfo, ptChecked: Boolean, isLocalToCallsite: Boolean): SearchResult = {
if (Statistics.canEnable) Statistics.incCounter(plausiblyCompatibleImplicits)
val ok = ptChecked || matchesPt(info) && {
def word = if (isLocalToCallsite) "local " else ""
typingLog("match", s"$word$info")
true
}
if (ok) typedImplicit1(info, isLocalToCallsite) else SearchFailure
}
private def typedImplicit1(info: ImplicitInfo, isLocalToCallsite: Boolean): SearchResult = {
if (Statistics.canEnable) Statistics.incCounter(matchingImplicits)
// workaround for deficient context provided by ModelFactoryImplicitSupport#makeImplicitConstraints
val isScalaDoc = context.tree == EmptyTree
val itree0 = atPos(pos.focus) {
if (isLocalToCallsite && !isScalaDoc) {
// SI-4270 SI-5376 Always use an unattributed Ident for implicits in the local scope,
// rather than an attributed Select, to detect shadowing.
Ident(info.name)
} else {
assert(info.pre != NoPrefix, info)
// SI-2405 Not info.name, which might be an aliased import
val implicitMemberName = info.sym.name
Select(gen.mkAttributedQualifier(info.pre), implicitMemberName)
}
}
val itree1 = if (isBlackbox(info.sym)) suppressMacroExpansion(itree0) else itree0
typingLog("considering", typeDebug.ptTree(itree1))
def fail(reason: String): SearchResult = failure(itree0, reason)
def fallback = typed1(itree1, EXPRmode, wildPt)
try {
val itree2 = if (!isView) fallback else pt match {
case Function1(arg1, arg2) =>
typed1(
atPos(itree0.pos)(Apply(itree1, List(Ident("<argument>") setType approximate(arg1)))),
EXPRmode,
approximate(arg2)
) match {
// try to infer implicit parameters immediately in order to:
// 1) guide type inference for implicit views
// 2) discard ineligible views right away instead of risking spurious ambiguous implicits
//
// this is an improvement of the state of the art that brings consistency to implicit resolution rules
// (and also helps fundep materialization to be applicable to implicit views)
//
// there's one caveat though. we need to turn this behavior off for scaladoc
// because scaladoc usually doesn't know the entire story
// and is just interested in views that are potentially applicable
// for instance, if we have `class C[T]` and `implicit def conv[T: Numeric](c: C[T]) = ???`
// then Scaladoc will give us something of type `C[T]`, and it would like to know
// that `conv` is potentially available under such and such conditions
case tree if isImplicitMethodType(tree.tpe) && !isScalaDoc =>
applyImplicitArgs(tree)
case tree => tree
}
case _ => fallback
}
context.firstError match { // using match rather than foreach to avoid non local return.
case Some(err) =>
log("implicit adapt failed: " + err.errMsg)
return fail(err.errMsg)
case None =>
}
if (Statistics.canEnable) Statistics.incCounter(typedImplicits)
val itree3 = if (isView) treeInfo.dissectApplied(itree2).callee
else adapt(itree2, EXPRmode, wildPt)
typingStack.showAdapt(itree0, itree3, pt, context)
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 (context.hasErrors)
fail("hasMatchingSymbol reported error: " + context.firstError.get.errMsg)
else if (itree3.isErroneous)
fail("error typechecking implicit candidate")
else if (isLocalToCallsite && !hasMatchingSymbol(itree2))
fail("candidate implicit %s is shadowed by %s".format(
info.sym.fullLocationString, itree2.symbol.fullLocationString))
else {
val tvars = undetParams map freshVar
def ptInstantiated = pt.instantiateTypeParams(undetParams, tvars)
if (matchesPt(itree3.tpe, ptInstantiated, undetParams)) {
if (tvars.nonEmpty)
typingLog("solve", ptLine("tvars" -> tvars, "tvars.constr" -> tvars.map(_.constr)))
val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt), upper = false, lubDepth(itree3.tpe :: pt :: Nil))
// #2421: check that we correctly instantiated type parameters outside of the implicit tree:
checkBounds(itree3, NoPrefix, NoSymbol, undetParams, targs, "inferred ")
context.firstError match {
case Some(err) =>
return fail("type parameters weren't correctly instantiated outside of the implicit tree: " + err.errMsg)
case None =>
}
// filter out failures from type inference, don't want to remove them from undetParams!
// we must be conservative in leaving type params in undetparams
// prototype == WildcardType: want to remove all inferred Nothings
val AdjustedTypeArgs(okParams, okArgs) = adjustTypeArgs(undetParams, tvars, targs)
val subst: TreeTypeSubstituter =
if (okParams.isEmpty) EmptyTreeTypeSubstituter
else {
val subst = new TreeTypeSubstituter(okParams, okArgs)
subst traverse itree3
notifyUndetparamsInferred(okParams, okArgs)
subst
}
// #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)
//
// This is just called for the side effect of error detection,
// see SI-6966 to see what goes wrong if we use the result of this
// as the SearchResult.
itree3 match {
case TypeApply(fun, args) => typedTypeApply(itree3, EXPRmode, fun, args)
case Apply(TypeApply(fun, args), _) => typedTypeApply(itree3, EXPRmode, fun, args) // t2421c
case t => t
}
context.firstError match {
case Some(err) =>
fail("typing TypeApply reported errors for the implicit tree: " + err.errMsg)
case None =>
val result = new SearchResult(unsuppressMacroExpansion(itree3), subst, context.undetparams)
if (Statistics.canEnable) Statistics.incCounter(foundImplicits)
typingLog("success", s"inferred value of type $ptInstantiated is $result")
result
}
}
else fail("incompatible: %s does not match expected type %s".format(itree3.tpe, ptInstantiated))
}
}
catch {
case ex: TypeError =>
fail(ex.getMessage())
}
}
/** 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 and the accessed symbol's definitions come before, and do not contain the closest enclosing definition, // see #3373
* - 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 implicits for which one of these
* conditions is true.
*/
def isValid(sym: Symbol) = {
def hasExplicitResultType(sym: Symbol) = {
def hasExplicitRT(tree: Tree) = tree match {
case x: ValOrDefDef => !x.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) = {
val ownerPos = owner.pos.pointOrElse(Int.MaxValue)
sym.pos.pointOrElse(0) < ownerPos && (
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
} else !(owner hasTransOwner sym)) // faster than owner.ownerChain contains sym
}
sym.isInitialized ||
sym.sourceFile == null ||
(sym.sourceFile ne context.unit.source.file) ||
hasExplicitResultType(sym) ||
comesBefore(sym, context.owner)
}
/** Prune ImplicitInfos down to either all the eligible ones or the best one.
*
* @param iss list of list of infos
* @param isLocalToCallsite if true, `iss` represents in-scope implicits, which must respect the normal rules of
* shadowing. The head of the list `iss` must represent implicits from the closest
* enclosing scope, and so on.
*/
class ImplicitComputation(iss: Infoss, isLocalToCallsite: Boolean) {
abstract class Shadower {
def addInfos(infos: Infos)
def isShadowed(name: Name): Boolean
}
private val shadower: Shadower = {
/** Used for exclude implicits from outer scopes that are shadowed by same-named implicits */
final class LocalShadower extends Shadower {
val shadowed = util.HashSet[Name](512)
def addInfos(infos: Infos) {
infos.foreach(i => shadowed.addEntry(i.name))
}
def isShadowed(name: Name) = shadowed(name)
}
/** Used for the implicits of expected type, when no shadowing checks are needed. */
object NoShadower extends Shadower {
def addInfos(infos: Infos) {}
def isShadowed(name: Name) = false
}
if (isLocalToCallsite) new LocalShadower else NoShadower
}
private var best: SearchResult = SearchFailure
private def isIneligible(info: ImplicitInfo) = (
info.isCyclicOrErroneous
|| isView && (info.sym eq Predef_conforms) // as an implicit conversion, Predef.$conforms is a no-op, so exclude it
|| (!context.macrosEnabled && info.sym.isTermMacro)
)
/** True if a given ImplicitInfo (already known isValid) is eligible.
*/
def survives(info: ImplicitInfo) = (
!isIneligible(info) // cyclic, erroneous, shadowed, or specially excluded
&& isPlausiblyCompatible(info.tpe, wildPt) // optimization to avoid matchesPt
&& !shadower.isShadowed(info.name) // OPT rare, only check for plausible candidates
&& matchesPt(info) // stable and matches expected type
)
/** 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]
/** Tests for validity and updates invalidImplicits by side effect when false.
*/
private def checkValid(sym: Symbol) = isValid(sym) || { invalidImplicits += sym ; false }
/** Preventing a divergent implicit from terminating implicit search,
* so that if there is a best candidate it can still be selected.
*/
object DivergentImplicitRecovery {
private var divergentError: Option[DivergentImplicitTypeError] = None
private def saveDivergent(err: DivergentImplicitTypeError) {
if (divergentError.isEmpty) divergentError = Some(err)
}
def issueSavedDivergentError() {
divergentError foreach (err => context.issue(err))
}
def apply(search: SearchResult, i: ImplicitInfo, errors: Seq[AbsTypeError]): SearchResult = {
// A divergent error from a nested implicit search will be found in `errors`. Stash that
// aside to be re-issued if this implicit search fails.
errors.collectFirst { case err: DivergentImplicitTypeError => err } foreach saveDivergent
if (search.isDivergent && divergentError.isEmpty) {
// Divergence triggered by `i` at this level of the implicit serach. We haven't
// seen divergence so far, we won't issue this error just yet, and instead temporarily
// treat `i` as a failed candidate.
saveDivergent(DivergentImplicitTypeError(tree, pt, i.sym))
log(s"discarding divergent implicit ${i.sym} during implicit search")
SearchFailure
} else {
if (search.isFailure) {
// We don't want errors that occur during checking implicit info
// to influence the check of further infos, but we should retain divergent implicit errors
// (except for the one we already squirreled away)
val saved = divergentError.getOrElse(null)
context.reportBuffer.retainErrors {
case err: DivergentImplicitTypeError => err ne saved
}
}
search
}
}
}
/** Sorted list of eligible implicits.
*/
val eligible = {
val matches = iss flatMap { is =>
val result = is filter (info => checkValid(info.sym) && survives(info))
shadower addInfos is
result
}
// most frequent one first
matches sortBy (x => if (isView) -x.useCountView else -x.useCountArg)
}
if (eligible.nonEmpty)
printTyping(tree, eligible.size + s" eligible for pt=$pt at ${fullSiteString(context)}")
/** 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 firstPending :: otherPending =>
def firstPendingImproves(alt: ImplicitInfo) =
firstPending == alt || (
try improves(firstPending, alt)
catch {
case e: CyclicReference =>
debugwarn(s"Discarding $firstPending during implicit search due to cyclic reference.")
true
}
)
val typedFirstPending = typedImplicit(firstPending, ptChecked = true, isLocalToCallsite)
// Pass the errors to `DivergentImplicitRecovery` so that it can note
// the first `DivergentImplicitTypeError` that is being propagated
// from a nested implicit search; this one will be
// re-issued if this level of the search fails.
DivergentImplicitRecovery(typedFirstPending, firstPending, context.errors) match {
case sr if sr.isDivergent => Nil
case sr if sr.isFailure => rankImplicits(otherPending, acc)
case newBest =>
best = newBest // firstPending is our new best, since we already pruned last time around:
val pendingImprovingBest = undoLog undo {
otherPending filterNot firstPendingImproves
}
rankImplicits(pendingImprovingBest, firstPending :: acc)
}
}
/** Returns all eligible ImplicitInfos and their SearchResults in a map.
*/
def findAll() = mapFrom(eligible)(typedImplicit(_, ptChecked = false, isLocalToCallsite))
/** 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", "")(isView, pt, tree)(context)
return AmbiguousSearchFailure // Stop the search once ambiguity is encountered, see t4457_2.scala
case _ =>
if (isView) chosen.useCountView += 1
else chosen.useCountArg += 1
}
}
if (best.isFailure) {
// If there is no winner, and we witnessed and recorded a divergence error,
// our recovery attempt has failed, so we must now issue it.
DivergentImplicitRecovery.issueSavedDivergentError()
if (invalidImplicits.nonEmpty)
setAddendum(pos, () =>
s"\n Note: implicit ${invalidImplicits.head} is not applicable here because it comes after the application point and it lacks an explicit result type"
)
}
best
}
}
/** 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 iss The given list of lists of implicit infos
* @param isLocalToCallsite 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 applicableInfos(iss: Infoss, isLocalToCallsite: Boolean): Map[ImplicitInfo, SearchResult] = {
val start = if (Statistics.canEnable) Statistics.startCounter(subtypeAppInfos) else null
val computation = new ImplicitComputation(iss, isLocalToCallsite) { }
val applicable = computation.findAll()
if (Statistics.canEnable) Statistics.stopCounter(subtypeAppInfos, start)
applicable
}
/** 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 isLocalToCallsite 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, isLocalToCallsite: Boolean): SearchResult =
if (implicitInfoss.forall(_.isEmpty)) SearchFailure
else new ImplicitComputation(implicitInfoss, isLocalToCallsite) findBest()
/** Produce an implicict info map, i.e. a map from the class symbols C of all parts of this type to
* the implicit infos in the companion objects of these class symbols C.
* 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
* - for alias types and abstract types, we take instead the parts
* - of their upper bounds.
* @return For those parts that refer to classes with companion objects that
* can be accessed with unambiguous stable prefixes that are not existentially
* bound, the implicits infos which are members of these companion objects.
*/
private def companionImplicitMap(tp: Type): InfoMap = {
/* Populate implicit info map by traversing all parts of type `tp`.
* Parameters as for `getParts`.
*/
def getClassParts(tp: Type)(implicit infoMap: InfoMap, seen: mutable.Set[Type], pending: Set[Symbol]) = tp match {
case TypeRef(pre, sym, args) =>
infoMap get sym match {
case Some(infos1) =>
if (infos1.nonEmpty && !(pre =:= infos1.head.pre.prefix)) {
log(s"Ignoring implicit members of $pre#$sym as it is also visible via another prefix: ${infos1.head.pre.prefix}")
infoMap(sym) = List() // ambiguous prefix - ignore implicit members
}
case None =>
if (pre.isStable && !pre.typeSymbol.isExistentiallyBound) {
val companion = companionSymbolOf(sym, context)
companion.moduleClass match {
case mc: ModuleClassSymbol =>
val infos =
for (im <- mc.implicitMembers.toList) yield new ImplicitInfo(im.name, singleType(pre, companion), im)
if (infos.nonEmpty)
infoMap += (sym -> infos)
case _ =>
}
}
val bts = tp.baseTypeSeq
var i = 1
while (i < bts.length) {
getParts(bts(i))
i += 1
}
getParts(pre)
}
}
/* Populate implicit info map by traversing all parts of type `tp`.
* This method is performance critical.
* @param tp The type for which we want to traverse parts
* @param infoMap The infoMap in which implicit infos corresponding to parts are stored
* @param seen The types that were already visited previously when collecting parts for the given infoMap
* @param pending The set of static symbols for which we are currently trying to collect their parts
* in order to cache them in infoMapCache
*/
def getParts(tp: Type)(implicit infoMap: InfoMap, seen: mutable.Set[Type], pending: Set[Symbol]) {
if (seen(tp))
return
seen += tp
tp match {
case TypeRef(pre, sym, args) =>
if (sym.isClass) {
if (!sym.isAnonOrRefinementClass && !sym.isRoot) {
if (sym.isStatic && !(pending contains sym))
infoMap ++= {
infoMapCache get sym match {
case Some(imap) => imap
case None =>
val result = new InfoMap
getClassParts(sym.tpeHK)(result, new mutable.HashSet(), pending + sym)
infoMapCache(sym) = result
result
}
}
else
getClassParts(tp)
args foreach getParts
}
} else if (sym.isAliasType) {
getParts(tp.normalize) // SI-7180 Normalize needed to expand HK type refs
} else if (sym.isAbstractType) {
getParts(tp.bounds.hi)
}
case ThisType(_) =>
getParts(tp.widen)
case _: SingletonType =>
getParts(tp.widen)
case HasMethodMatching(_, argtpes, restpe) =>
for (tp <- argtpes) getParts(tp)
getParts(restpe)
case RefinedType(ps, _) =>
for (p <- ps) getParts(p)
case AnnotatedType(_, t) =>
getParts(t)
case ExistentialType(_, t) =>
getParts(t)
case PolyType(_, t) =>
getParts(t)
case _ =>
}
}
val infoMap = new InfoMap
getParts(tp)(infoMap, new mutable.HashSet(), Set())
if (infoMap.nonEmpty)
printTyping(tree, infoMap.size + " implicits in companion scope")
infoMap
}
/** 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: Infoss = {
if (Statistics.canEnable) Statistics.incCounter(implicitCacheAccs)
implicitsCache get pt match {
case Some(implicitInfoss) =>
if (Statistics.canEnable) Statistics.incCounter(implicitCacheHits)
implicitInfoss
case None =>
val start = if (Statistics.canEnable) Statistics.startTimer(subtypeETNanos) else null
// val implicitInfoss = companionImplicits(pt)
val implicitInfoss1 = companionImplicitMap(pt).valuesIterator.toList
// val is1 = implicitInfoss.flatten.toSet
// val is2 = implicitInfoss1.flatten.toSet
// for (i <- is1)
// if (!(is2 contains i)) println("!!! implicit infos of "+pt+" differ, new does not contain "+i+",\nold: "+implicitInfoss+",\nnew: "+implicitInfoss1)
// for (i <- is2)
// if (!(is1 contains i)) println("!!! implicit infos of "+pt+" differ, old does not contain "+i+",\nold: "+implicitInfoss+",\nnew: "+implicitInfoss1)
if (Statistics.canEnable) Statistics.stopTimer(subtypeETNanos, start)
implicitsCache(pt) = implicitInfoss1
if (implicitsCache.size >= sizeLimit)
implicitsCache -= implicitsCache.keysIterator.next
implicitInfoss1
}
}
/** Creates a tree will produce a tag of the requested flavor.
* An EmptyTree is returned if materialization fails.
*/
private def tagOfType(pre: Type, tp: Type, tagClass: Symbol): SearchResult = {
def success(arg: Tree) = {
def isMacroException(msg: String): Boolean =
// [Eugene] very unreliable, ask Hubert about a better way
msg contains "exception during macro expansion"
def processMacroExpansionError(pos: Position, msg: String): SearchResult = {
// giving up and reporting all macro exceptions regardless of their source
// this might lead to an avalanche of errors if one of your implicit macros misbehaves
if (isMacroException(msg)) context.error(pos, msg)
failure(arg, "failed to typecheck the materialized tag: %n%s".format(msg), pos)
}
try {
val tree1 = typedPos(pos.focus)(arg)
context.firstError match {
case Some(err) => processMacroExpansionError(err.errPos, err.errMsg)
case None => new SearchResult(tree1, EmptyTreeTypeSubstituter, Nil)
}
} catch {
case ex: TypeError =>
processMacroExpansionError(ex.pos, ex.msg)
}
}
val prefix = (
// ClassTags are not path-dependent, so their materializer doesn't care about prefixes
if (tagClass eq ClassTagClass) EmptyTree
else pre match {
case SingleType(prePre, preSym) =>
gen.mkAttributedRef(prePre, preSym) setType pre
// necessary only to compile typetags used inside the Universe cake
case ThisType(thisSym) =>
gen.mkAttributedThis(thisSym)
case _ =>
// if `pre` is not a PDT, e.g. if someone wrote
// implicitly[scala.reflect.macros.blackbox.Context#TypeTag[Int]]
// then we need to fail, because we don't know the prefix to use during type reification
// upd. we also need to fail silently, because this is a very common situation
// e.g. quite often we're searching for BaseUniverse#TypeTag, e.g. for a type tag in any universe
// so that if we find one, we could convert it to whatever universe we need by the means of the `in` method
// if no tag is found in scope, we end up here, where we ask someone to materialize the tag for us
// however, since the original search was about a tag with no particular prefix, we cannot proceed
// this situation happens very often, so emitting an error message here (even if only for -Xlog-implicits) would be too much
//return failure(tp, "tag error: unsupported prefix type %s (%s)".format(pre, pre.kind))
return SearchFailure
}
)
// todo. migrate hardcoded materialization in Implicits to corresponding implicit macros
val materializer = atPos(pos.focus)(gen.mkMethodCall(TagMaterializers(tagClass), List(tp), if (prefix != EmptyTree) List(prefix) else List()))
if (settings.XlogImplicits) reporter.echo(pos, "materializing requested %s.%s[%s] using %s".format(pre, tagClass.name, tp, materializer))
if (context.macrosEnabled) success(materializer)
// don't call `failure` here. if macros are disabled, we just fail silently
// otherwise -Xlog-implicits will spam the long with zillions of "macros are disabled"
// this is ugly but temporary, since all this code will be removed once I fix implicit macros
else SearchFailure
}
/** Creates a tree that calls the relevant factory method in object
* scala.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, flavor: Symbol): SearchResult = {
val full = flavor == FullManifestClass
val opt = flavor == OptManifestClass
/* Creates a tree that calls the factory method called constructor in object scala.reflect.Manifest */
def manifestFactoryCall(constructor: String, tparg: Type, args: Tree*): Tree =
if (args contains EmptyTree) EmptyTree
else typedPos(tree.pos.focus) {
val mani = gen.mkManifestFactoryCall(full, constructor, tparg, args.toList)
if (settings.debug) println("generated manifest: "+mani) // DEBUG
mani
}
/* Creates a tree representing one of the singleton manifests.*/
def findSingletonManifest(name: String) = typedPos(tree.pos.focus) {
Select(gen.mkAttributedRef(FullManifestModule), name)
}
/* 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, tp), reportAmbiguous = true, isView = false, context).tree
def findSubManifest(tp: Type) = findManifest(tp, if (full) FullManifestClass else OptManifestClass)
def mot(tp0: Type, from: List[Symbol], to: List[Type]): SearchResult = {
implicit def wrapResult(tree: Tree): SearchResult =
if (tree == EmptyTree) SearchFailure else new SearchResult(tree, if (from.isEmpty) EmptyTreeTypeSubstituter else new TreeTypeSubstituter(from, to), Nil)
val tp1 = tp0.dealias
tp1 match {
case ThisType(_) | SingleType(_, _) =>
// can't generate a reference to a value that's abstracted over by an existential
if (containsExistential(tp1)) EmptyTree
else manifestFactoryCall("singleType", tp, gen.mkAttributedQualifier(tp1))
case ConstantType(value) =>
manifestOfType(tp1.deconst, FullManifestClass)
case TypeRef(pre, sym, args) =>
if (isPrimitiveValueClass(sym) || isPhantomClass(sym)) {
findSingletonManifest(sym.name.toString)
} else if (sym == ObjectClass || sym == AnyRefClass) {
findSingletonManifest("Object")
} else if (sym == RepeatedParamClass || sym == ByNameParamClass) {
EmptyTree
} else if (sym == ArrayClass && args.length == 1) {
manifestFactoryCall("arrayType", args.head, findManifest(args.head))
} else if (sym.isClass) {
val classarg0 = gen.mkClassOf(tp1)
val classarg = tp match {
case _: ExistentialType => gen.mkCast(classarg0, ClassType(tp))
case _ => classarg0
}
val suffix = classarg :: (args map findSubManifest)
manifestFactoryCall(
"classType", tp,
(if ((pre eq NoPrefix) || pre.typeSymbol.isStaticOwner) suffix
else findSubManifest(pre) :: suffix): _*)
} else if (sym.isExistentiallyBound && full) {
manifestFactoryCall("wildcardType", tp,
findManifest(tp.bounds.lo), findManifest(tp.bounds.hi))
}
// looking for a manifest of a type parameter that hasn't been inferred by now,
// can't do much, but let's not fail
else if (undetParams contains sym) {
// #3859: need to include the mapping from sym -> NothingTpe in the SearchResult
mot(NothingTpe, sym :: from, NothingTpe :: to)
} else {
// a manifest should have been found by normal searchImplicit
EmptyTree
}
case RefinedType(parents, decls) => // !!! not yet: if !full || decls.isEmpty =>
// refinement is not generated yet
if (hasLength(parents, 1)) findManifest(parents.head)
else if (full) manifestFactoryCall("intersectionType", tp, parents map findSubManifest: _*)
else mot(erasure.intersectionDominator(parents), from, to)
case ExistentialType(tparams, result) =>
mot(tp1.skolemizeExistential, from, to)
case _ =>
EmptyTree
}
}
if (full) {
val tagInScope = resolveTypeTag(pos, NoType, tp, concrete = true, allowMaterialization = false)
if (tagInScope.isEmpty) mot(tp, Nil, Nil)
else {
if (ReflectRuntimeUniverse == NoSymbol) {
// todo. write a test for this
context.error(pos,
sm"""to create a manifest here, it is necessary to interoperate with the type tag `$tagInScope` in scope.
|however typetag -> manifest conversion requires Scala reflection, which is not present on the classpath.
|to proceed put scala-reflect.jar on your compilation classpath and recompile.""")
return SearchFailure
}
if (resolveClassTag(pos, tp, allowMaterialization = true) == EmptyTree) {
context.error(pos,
sm"""to create a manifest here, it is necessary to interoperate with the type tag `$tagInScope` in scope.
|however typetag -> manifest conversion requires a class tag for the corresponding type to be present.
|to proceed add a class tag to the type `$tp` (e.g. by introducing a context bound) and recompile.""")
return SearchFailure
}
val cm = typed(Ident(ReflectRuntimeCurrentMirror))
val internal = gen.mkAttributedSelect(gen.mkAttributedRef(ReflectRuntimeUniverse), UniverseInternal)
val interop = gen.mkMethodCall(Select(internal, nme.typeTagToManifest), List(tp), List(cm, tagInScope))
wrapResult(interop)
}
} else {
mot(tp, Nil, Nil) match {
case SearchFailure if opt => wrapResult(gen.mkAttributedRef(NoManifest))
case result => result
}
}
}
def wrapResult(tree: Tree): SearchResult =
if (tree == EmptyTree) SearchFailure else new SearchResult(tree, EmptyTreeTypeSubstituter, Nil)
/** Materializes implicits of predefined types (currently, manifests and tags).
* Will be replaced by implicit macros once we fix them.
*/
private def materializeImplicit(pt: Type): SearchResult =
pt match {
case TypeRef(_, sym, _) if sym.isAbstractType =>
materializeImplicit(pt.dealias.bounds.lo) // #3977: use pt.dealias, not pt (if pt is a type alias, pt.bounds.lo == pt)
case pt @ TypeRef(pre, sym, arg :: Nil) =>
sym match {
case sym if ManifestSymbols(sym) => manifestOfType(arg, sym)
case sym if TagSymbols(sym) => tagOfType(pre, arg, sym)
// as of late ClassManifest is an alias of ClassTag
// hence we need to take extra care when performing dealiasing
// because it might destroy the flavor of the manifest requested by the user
// when the user wants ClassManifest[T], we should invoke `manifestOfType` not `tagOfType`
// hence we don't do `pt.dealias` as we did before, but rather do `pt.betaReduce`
// unlike `dealias`, `betaReduce` performs at most one step of dealiasing
// while dealias pops all aliases in a single invocation
case sym if sym.isAliasType => materializeImplicit(pt.betaReduce)
case _ => SearchFailure
}
case _ =>
SearchFailure
}
/** The result of the implicit search:
* First search implicits visible in current context.
* If that fails, search implicits in expected type `pt`.
*
* todo. the following lines should be deleted after we migrate delegate tag materialization to implicit macros
* If that fails, and `pt` is an instance of a ClassTag, try to construct a class tag.
* If that fails, and `pt` is an instance of a TypeTag, try to construct a type tag.
* If that fails, and `pt` is an instance of a ClassManifest, try to construct a class manifest.
* If that fails, and `pt` is an instance of a Manifest, try to construct a manifest.
* If that fails, and `pt` is an instance of a OptManifest, try to construct a class manifest and return NoManifest if construction fails.
* If all fails return SearchFailure
*/
def bestImplicit: SearchResult = {
val failstart = if (Statistics.canEnable) Statistics.startTimer(inscopeFailNanos) else null
val succstart = if (Statistics.canEnable) Statistics.startTimer(inscopeSucceedNanos) else null
var result = searchImplicit(context.implicitss, isLocalToCallsite = true)
if (result.isFailure) {
if (Statistics.canEnable) Statistics.stopTimer(inscopeFailNanos, failstart)
} else {
if (Statistics.canEnable) Statistics.stopTimer(inscopeSucceedNanos, succstart)
if (Statistics.canEnable) Statistics.incCounter(inscopeImplicitHits)
}
if (result.isFailure) {
val previousErrs = context.flushAndReturnBuffer()
val failstart = if (Statistics.canEnable) Statistics.startTimer(oftypeFailNanos) else null
val succstart = if (Statistics.canEnable) Statistics.startTimer(oftypeSucceedNanos) else null
val wasAmbigious = result.isAmbiguousFailure // SI-6667, never search companions after an ambiguous error in in-scope implicits
result = materializeImplicit(pt)
// `materializeImplicit` does some preprocessing for `pt`
// is it only meant for manifests/tags or we need to do the same for `implicitsOfExpectedType`?
if (result.isFailure && !wasAmbigious)
result = searchImplicit(implicitsOfExpectedType, isLocalToCallsite = false)
if (result.isFailure) {
context.updateBuffer(previousErrs)
if (Statistics.canEnable) Statistics.stopTimer(oftypeFailNanos, failstart)
} else {
if (Statistics.canEnable) Statistics.stopTimer(oftypeSucceedNanos, succstart)
if (Statistics.canEnable) Statistics.incCounter(oftypeImplicitHits)
}
}
if (result.isSuccess && isView) {
def maybeInvalidConversionError(msg: String) {
// We have to check context.ambiguousErrors even though we are calling "issueAmbiguousError"
// which ostensibly does exactly that before issuing the error. Why? I have no idea. Test is pos/t7690.
if (context.ambiguousErrors)
context.issueAmbiguousError(AmbiguousImplicitTypeError(tree, msg))
}
pt match {
case Function1(_, out) =>
def prohibit(sym: Symbol) = if (sym.tpe <:< out) {
maybeInvalidConversionError(s"the result type of an implicit conversion must be more specific than ${sym.name}")
result = SearchFailure
}
prohibit(AnyRefClass)
if (settings.isScala211) prohibit(AnyValClass)
case _ => false
}
if (settings.isScala211 && isInvalidConversionSource(pt)) {
maybeInvalidConversionError("an expression of type Null is ineligible for implicit conversion")
result = SearchFailure
}
}
if (result.isFailure)
debuglog("no implicits found for "+pt+" "+pt.typeSymbol.info.baseClasses+" "+implicitsOfExpectedType)
result
}
def allImplicits: List[SearchResult] = {
def search(iss: Infoss, isLocalToCallsite: Boolean) = applicableInfos(iss, isLocalToCallsite).values
(
search(context.implicitss, isLocalToCallsite = true) ++
search(implicitsOfExpectedType, isLocalToCallsite = false)
).toList.filter(_.tree ne EmptyTree)
}
// find all implicits for some type that contains type variables
// collect the constraints that result from typing each implicit
def allImplicitsPoly(tvars: List[TypeVar]): List[(SearchResult, List[TypeConstraint])] = {
def resetTVars() = tvars foreach { _.constr = new TypeConstraint }
def eligibleInfos(iss: Infoss, isLocalToCallsite: Boolean) = {
val eligible = new ImplicitComputation(iss, isLocalToCallsite).eligible
eligible.toList.flatMap {
(ii: ImplicitInfo) =>
// each ImplicitInfo contributes a distinct set of constraints (generated indirectly by typedImplicit)
// thus, start each type var off with a fresh for every typedImplicit
resetTVars()
// any previous errors should not affect us now
context.flushBuffer()
val res = typedImplicit(ii, ptChecked = false, isLocalToCallsite)
if (res.tree ne EmptyTree) List((res, tvars map (_.constr)))
else Nil
}
}
eligibleInfos(context.implicitss, isLocalToCallsite = true) ++
eligibleInfos(implicitsOfExpectedType, isLocalToCallsite = false)
}
}
object ImplicitNotFoundMsg {
def unapply(sym: Symbol): Option[(Message)] = sym.implicitNotFoundMsg match {
case Some(m) => Some(new Message(sym, m))
case None if sym.isAliasType =>
// perform exactly one step of dealiasing
// this is necessary because ClassManifests are now aliased to ClassTags
// but we don't want to intimidate users by showing unrelated error messages
unapply(sym.info.resultType.betaReduce.typeSymbolDirect)
case _ => None
}
// check the message's syntax: should be a string literal that may contain occurrences of the string "${X}",
// where `X` refers to a type parameter of `sym`
def check(sym: Symbol): Option[String] =
sym.getAnnotation(ImplicitNotFoundClass).flatMap(_.stringArg(0) match {
case Some(m) => new Message(sym, m).validate
case None => Some("Missing argument `msg` on implicitNotFound annotation.")
})
// http://dcsobral.blogspot.com/2010/01/string-interpolation-in-scala-with.html
private val Intersobralator = """\$\{\s*([^}\s]+)\s*\}""".r
class Message(sym: Symbol, msg: String) {
private def interpolate(text: String, vars: Map[String, String]) =
Intersobralator.replaceAllIn(text, (_: Regex.Match) match {
case Regex.Groups(v) => Regex quoteReplacement vars.getOrElse(v, "")
// #3915: need to quote replacement string since it may include $'s (such as the interpreter's $iw)
})
private lazy val typeParamNames: List[String] = sym.typeParams.map(_.decodedName)
def format(paramName: Name, paramTp: Type): String = format(paramTp.typeArgs map (_.toString))
def format(typeArgs: List[String]): String =
interpolate(msg, Map((typeParamNames zip typeArgs): _*)) // TODO: give access to the name and type of the implicit argument, etc?
def validate: Option[String] = {
val refs = Intersobralator.findAllMatchIn(msg).map(_ group 1).toSet
val decls = typeParamNames.toSet
(refs &~ decls) match {
case s if s.isEmpty => None
case unboundNames =>
val singular = unboundNames.size == 1
val ess = if (singular) "" else "s"
val bee = if (singular) "is" else "are"
Some(s"The type parameter$ess ${unboundNames mkString ", "} referenced in the message of the @implicitNotFound annotation $bee not defined by $sym.")
}
}
}
}
}
object ImplicitsStats {
import scala.reflect.internal.TypesStats._
val rawTypeImpl = Statistics.newSubCounter (" of which in implicits", rawTypeCount)
val subtypeImpl = Statistics.newSubCounter(" of which in implicit", subtypeCount)
val findMemberImpl = Statistics.newSubCounter(" of which in implicit", findMemberCount)
val subtypeAppInfos = Statistics.newSubCounter(" of which in app impl", subtypeCount)
val implicitSearchCount = Statistics.newCounter ("#implicit searches", "typer")
val plausiblyCompatibleImplicits
= Statistics.newSubCounter(" #plausibly compatible", implicitSearchCount)
val matchingImplicits = Statistics.newSubCounter(" #matching", implicitSearchCount)
val typedImplicits = Statistics.newSubCounter(" #typed", implicitSearchCount)
val foundImplicits = Statistics.newSubCounter(" #found", implicitSearchCount)
val improvesCount = Statistics.newSubCounter("implicit improves tests", implicitSearchCount)
val improvesCachedCount = Statistics.newSubCounter("#implicit improves cached ", implicitSearchCount)
val inscopeImplicitHits = Statistics.newSubCounter("#implicit inscope hits", implicitSearchCount)
val oftypeImplicitHits = Statistics.newSubCounter("#implicit oftype hits ", implicitSearchCount)
val implicitNanos = Statistics.newSubTimer ("time spent in implicits", typerNanos)
val inscopeSucceedNanos = Statistics.newSubTimer (" successful in scope", typerNanos)
val inscopeFailNanos = Statistics.newSubTimer (" failed in scope", typerNanos)
val oftypeSucceedNanos = Statistics.newSubTimer (" successful of type", typerNanos)
val oftypeFailNanos = Statistics.newSubTimer (" failed of type", typerNanos)
val subtypeETNanos = Statistics.newSubTimer (" assembling parts", typerNanos)
val matchesPtNanos = Statistics.newSubTimer (" matchesPT", typerNanos)
val implicitCacheAccs = Statistics.newCounter ("implicit cache accesses", "typer")
val implicitCacheHits = Statistics.newSubCounter("implicit cache hits", implicitCacheAccs)
}
Other Scala source code examplesHere is a short list of links related to this Scala Implicits.scala source code file: |
The search page
Other Scala source code examples at this package level
Click here to learn more about this project
