path: root/src/compiler/scala/tools/nsc/typechecker/Implicits.scala

/* NSC -- new Scala compiler
 * Copyright 2005-2009 LAMP/EPFL
 * @author  Martin Odersky
 */
// $Id: Typers.scala 17229 2009-03-02 19:09:42Z extempore $

//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.typechecker

import scala.collection.mutable.{HashMap, ListBuffer}
import scala.compat.Platform.currentTime
import scala.tools.nsc.util.{HashSet, Position, Set, NoPosition, SourceFile}
import symtab.Flags._
import util.HashSet

/** 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 posAssigner.atPos

  final val traceImplicits = false

  /** 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 pt0              The original expected type of the implicit. A method type
   *                          for `pt0` implies we are looking for a view, any other type implies
   *                          we are looking for an implicit parameter.
   *  @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 context          The current context
   *  @return                 A search result
   */
  def inferImplicit(tree: Tree, pt0: Type, reportAmbiguous: Boolean, context: Context): SearchResult = {
    if (traceImplicits && !tree.isEmpty && !context.undetparams.isEmpty)
      println("typing implicit with undetermined type params: "+context.undetparams+"\n"+tree)
    val search = new ImplicitSearch(tree, pt0, context.makeImplicit(reportAmbiguous))
    context.undetparams = context.undetparams remove (search.result.subst.from contains _)
    search.result
  }

  /** 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
    }

    override def equals(other: Any) = other match {
      case that: ImplicitInfo =>
        if (this eq NoImplicitInfo) that eq this
        else
          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, null, null)

  /** 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 pt0              The original expected type of the implicit. A method type
   *                          for `pt0` implies we are looking for a view, any other type implies
   *                          we are looking for an implicit parameter.
   *  @param context0         The context used for the implicit search
   */
  private class ImplicitSearch(tree: Tree, pt0: Type, context0: Context)
    extends Typer(context0) {

    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 `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(formals, restpe) => (formals exists (_.isError)) || containsError(restpe)
      case _ => tp.isError
    }

    /** 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(attribs, 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))
    }

    /** The normalized expected type (which is a value type). */
    private val pt = normalize(pt0)

    /** Are we looking for an implicit view? This is signalled by the original expected type
     *  being a method or a polymorphic type.
     */
    private val isView = pt0 match {
      case MethodType(_, _) | PolyType(_, _) => true
      case _ => false
    }

    if (util.Statistics.enabled) implcnt += 1
    private val startTime = if (util.Statistics.enabled) currentTime else 0l

    /** 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)
           throw DivergentImplicit
           SearchFailure
         case None =>
           try {
             context.openImplicits = pt :: context.openImplicits
             //println("  "*context.openImplicits.length+"typed implicit "+info+" for "+pt)
             typedImplicit0(info)
           } catch {
             case DivergentImplicit =>
               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 covariant occurrences of undetermined
       *  type parameters are replaced by Any, and all other occurrences
       *  are replaced by Nothing
       */
      val wildPt = approximate(pt)

      if (traceImplicits) println("typed impl for "+wildPt+"? "+info.name+":"+info.tpe+"/"+undetParams)
      if (isPlausiblyCompatible(info.tpe, wildPt) &&
          isCompatible(depoly(info.tpe), wildPt) &&
          isStable(info.pre)) {

        val itree = atPos(tree.pos) {
          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 "+wildPt)
        def fail(reason: String): SearchResult = {
          if (settings.XlogImplicits.value)
            inform(itree+" is not a valid implicit value for "+pt0+" because:\n"+reason)
          SearchFailure
        }
        try {
          val itree1 =
            if (isView)
              typed1(
                Apply(itree, List(Ident("<argument>").setType(approximate(pt0.paramTypes.head)))),
                EXPRmode, approximate(pt0.resultType))
            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 (isCompatible(itree2.tpe, pt.instantiateTypeParams(undetParams, tvars))) {
              if (traceImplicits) println("tvars = "+tvars+"/"+(tvars map (_.constr)))
              val targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt),
                                      false, lubDepth(List(itree2.tpe, pt)))
              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)
              result
            } else {
              if (traceImplicits) println("incompatible???")
              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
      }
    }

    /** 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 = {

      /** A set containing names that are shadowed by implicit infos */
      val shadowed = new HashSet[Name](8)

      /** 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.offset.getOrElse(0) < owner.pos.offset.getOrElse(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)
      }

      /** 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]

      /** 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,
       *   - if the symbol is Predef.identity, then we are not looking for a view,
       *   - 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 (!containsError(info.tpe) &&
            !(isLocal && shadowed.contains(info.name)) &&
            (!isView || info.sym != Predef_identity)) typedImplicit(info)
        else SearchFailure

      /** Computes from a list 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).
       */
      def applicableInfos(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
      }

      /** A map which takes applicable infos to their attributed trees. */
      val applicable: Map[ImplicitInfo, SearchResult] =
          (Map[ImplicitInfo, SearchResult]() /: (implicitInfoss map applicableInfos))(_ ++ _)

      if (applicable.isEmpty && !invalidImplicits.isEmpty) {
        infer.setAddendum(tree.pos, () =>
          "\n Note: implicit "+invalidImplicits.first+" 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.keySet) (
        (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.elements.next, "both", "and", "") // !!! streamline when new collection is there

        // 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.
        for (alt <- applicable.keySet) {
          /** Is (the companion class of) `sym1` a subclass of (the compansion class of) `sym2`? */
          def isSubClassOrObject(sym1: Symbol, sym2: Symbol): Boolean =
            sym1 != NoSymbol && (sym1 isSubClass sym2) ||
            sym1.isModuleClass && isSubClassOrObject(sym1.linkedClassOfClass, sym2) ||
            sym2.isModuleClass && isSubClassOrObject(sym1, sym2.linkedClassOfClass)

          if (alt.sym.owner != best.sym.owner && isSubClassOrObject(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 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]] = {
        def getParts(tp: Type, s: collection.jcl.Set[Type]) {
          tp match {
            case TypeRef(pre, sym, args) if (!sym.isPackageClass) =>
              for (bc <- sym.info.baseClasses)
                if (sym.isClass) s add (tp.baseType(bc))
              getParts(pre, s)
              for (arg <- args) getParts(arg, s)
            case ThisType(_) =>
              getParts(tp.widen, s)
            case _: SingletonType =>
              getParts(tp.widen, s)
            case RefinedType(ps, _) =>
              for (p <- ps) getParts(p, s)
            case AnnotatedType(_, t, _) =>
              getParts(t, s)
            case _ =>
          }
        }
        val tps = new collection.jcl.LinkedHashSet[Type]
        getParts(pt, tps)
        tps.elements.map(implicitsOfClass).toList
      }

    /** The manifest corresponding to type `pt`, provided `pt` is an instance of Manifest.
     */
    private def implicitManifest(pt: Type): Tree = pt match {
      case TypeRef(_, ManifestClass, List(arg)) =>
        manifestOfType(arg)
      case TypeRef(_, OptManifestClass, List(arg)) =>
        val itree = manifestOfType(arg)
        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): Tree = {

      /** Creates a tree that calls the factory method called constructor in object reflect.Manifest */
      def manifestFactoryCall(constructor: String, args: Tree*): Tree =
        if (args contains EmptyTree) EmptyTree
        else
          typed(atPos(tree.pos) {
            Apply(
              TypeApply(
                Select(gen.mkAttributedRef(ManifestModule), constructor),
                List(TypeTree(tp))
              ),
              args.toList
            )
          })

      /** Re-wraps a type in a manifest before calling inferImplicit on the result */
      def findManifest(tp: Type): Tree =
        inferImplicit(tree, appliedType(ManifestClass.typeConstructor, List(tp)), true, context).tree

      tp.normalize match {
        case ThisType(_) | SingleType(_, _) =>
          manifestFactoryCall("singleType", gen.mkAttributedQualifier(tp))
        case ConstantType(value) =>
          findManifest(tp.deconst)
        case TypeRef(pre, sym, args) =>
          if (sym.isClass) {
            val suffix = gen.mkClassOf(tp) :: (args map findManifest)
            manifestFactoryCall(
              "classType",
              (if ((pre eq NoPrefix) || pre.typeSymbol.isStaticOwner) suffix
               else findManifest(pre) :: suffix): _*)
          }
          else if (sym.isTypeParameterOrSkolem) {
            EmptyTree  // a manifest should have been found by normal searchImplicit
          }
          else {
            manifestFactoryCall(
              "abstractType",
              findManifest(pre) :: Literal(sym.name.toString) :: findManifest(tp.bounds.hi) :: (args map findManifest): _*)
          }
        case RefinedType(parents, decls) =>
          // refinement is not generated yet
          if (parents.length == 1) findManifest(parents.head)
          else manifestFactoryCall("intersectionType", parents map findManifest: _*)
        case _ =>
          EmptyTree
      }
    }

    /** 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
     */
    var result = searchImplicit(context.implicitss, true)
    if (result == SearchFailure) {
      result = searchImplicit(implicitsOfExpectedType, false)
    }
    if (result == SearchFailure) {
      val resultTree = implicitManifest(pt)
      if (resultTree != EmptyTree) result = new SearchResult(resultTree, EmptyTreeTypeSubstituter)
    }
    if (util.Statistics.enabled) impltime += (currentTime - startTime)
    result
  }

  private val DivergentImplicit = new Exception()
}