added missing Implicits.scala file

1 files changed, 574 insertions, 0 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
new file mode 100644
index 0000000000..9f200c94cf
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -0,0 +1,574 @@
+/* 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
+
+  /** 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 (!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)
+
+  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)
+
+    /** 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) =>
+           throw DivergentImplicit
+           SearchFailure
+         case None =>
+           try {
+             context.openImplicits = pt :: context.openImplicits
+             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
+      }
+
+      if (!isPlausiblyCompatible(info.tpe, pt) || !isStable(info.pre)) return SearchFailure
+
+      val tvars = undetParams map freshVar
+
+      // println("typed impl for "+pt+"? "+info.name+":"+info.tpe+(isPlausiblyCompatible(info.tpe, pt))+isCompatible(depoly(info.tpe), pt)+isStable(info.pre))
+      if (isCompatible(depoly(info.tpe), pt.instantiateTypeParams(undetParams, tvars))) {
+        val itree = atPos(tree.pos) {
+          if (info.pre == NoPrefix) Ident(info.name)
+          else Select(gen.mkAttributedQualifier(info.pre), info.name)
+        }
+        // println("typed impl?? "+info.name+":"+info.tpe+" ==> "+itree+" with "+pt)
+        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(Apply(itree, List(Ident("<argument>") setType pt0.paramTypes.head)), EXPRmode, pt0.resultType)
+            else
+              typed1(itree, EXPRmode, pt)
+          //if (settings.debug.value) println("typed implicit "+itree1+":"+itree1.tpe+", pt = "+pt)
+          val itree2 = if (isView) (itree1: @unchecked) match { case Apply(fun, _) => fun }
+                       else adapt(itree1, EXPRmode, pt)
+          //if (settings.debug.value) println("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+pt)("adapted implicit "+itree1.symbol+":"+itree2.tpe+" to "+pt)
+          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 targs = solvedTypes(tvars, undetParams, undetParams map varianceInType(pt),
+                                    false, lubDepth(List(depoly(info.tpe), pt)))
+            val subst = new TreeTypeSubstituter(undetParams, targs)
+            subst traverse itree2
+            // todo: remove type params that have been instantiated to Nothing, similar
+            // to methTypeArgs
+            new SearchResult(itree2, subst)
+          } 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()
+}