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

/* 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._
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._

  final val traceImplicits = false

  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
  var uncached = 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[AnyRef, SearchResult]

  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
    }

    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, NoType, NoSymbol)

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

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

      //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.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 "+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 (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)
              // println("RESULT = "+itree+"///"+itree1+"///"+itree2)//DEBUG
              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
      }
    }

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

    /** 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 */
      val shadowed = new HashSet[Name](8)

      /** 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 (containsError(info.tpe) ||
            (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),
            // 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.info.baseClasses.tail)
                  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]] =
      parts(pt).iterator.map(implicitsOfClass).toList

    /** 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 && !sym.isTypeParameterOrSkolem && !sym.isExistential) {
            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) =>
          mot(result)
        case _ =>
          EmptyTree
      }

      mot(tp)
    }

    /** An extractor for types of the form ? { name: ? }
     */
    object WildcardName {
      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
      }
    }

    /** Construct a fresh symbol tree for an implicit parameter
        because of caching, must clone symbols that represent bound variables,
        or we will end up with different bound variables that are represented by the same symbol */
    def freshenFunctionParameters(tree : Tree) : Tree = new Transformer {
      currentOwner = context.owner
      override val treeCopy = new LazyTreeCopier
      override def transform(tr : Tree) = super.transform(tr match {
        case Function(vparams, body) => {
          // New tree
          val sym = tr.symbol cloneSymbol currentOwner
          val res = tr.duplicate setSymbol sym
          // New parameter symbols
          var oldsyms = vparams map (_.symbol)
          var newsyms = cloneSymbols(oldsyms, sym)
          // Fix all symbols
          new TreeSymSubstituter(oldsyms, newsyms) traverse res
          res
        }
        case x => x
      })
    } transform tree

    /** Return cached search result if found. Otherwise update cache
     *  but keep within sizeLimit entries
     */
    def cacheResult(key: AnyRef): SearchResult = implicitsCache get key match {
      case Some(sr: SearchResult) =>
        hits += 1
        if (sr == SearchFailure) sr
        else {
          val result = new SearchResult(freshenFunctionParameters(sr.tree.duplicate), sr.subst) // #2201: generate fresh symbols for parameters
          for (t <- result.tree) t.setPos(tree.pos.focus)
          result
        }
      case None =>
        misses += 1
        val r = searchImplicit(implicitsOfExpectedType, false)
        //println("new fact: search implicit of "+key+" = "+r)
        implicitsCache(key) = r
        if (implicitsCache.size >= sizeLimit)
          implicitsCache -= implicitsCache.keysIterator.next
        r
    }

    /** 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 = pt match {
          case _: UniqueType => cacheResult(pt)
          case WildcardName(name) => cacheResult(name)
          case _ => uncached += 1; 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()
}