Improvements in implicits error reporting

Plus a few bugfixes for implicits

1 files changed, 181 insertions, 107 deletions

diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala
index 043ecd29f..cb028a080 100644
--- a/src/dotty/tools/dotc/typer/Implicits.scala
+++ b/src/dotty/tools/dotc/typer/Implicits.scala
@@ -20,6 +20,7 @@ import StdNames._
 import Constants._
 import Inferencing._
 import Applications._
+import ErrorReporting._
 import collection.mutable
 
 /** Implicit resolution */
@@ -31,13 +32,13 @@ object Implicits {
   abstract class ImplicitRefs extends Compatibility {
 
     /** The implicit references */
-    def refs: Set[TermRef]
+    def refs: List[TermRef]
 
     /** Return those references in `refs` that are compatible with type `pt`. */
-    protected def filterMatching(pt: Type)(implicit ctx: Context) = {
+    protected def filterMatching(pt: Type)(implicit ctx: Context): List[TermRef] = {
       def result(implicit ctx: Context) =
-        refs.toList filter (ref => isCompatible(normalize(ref), pt))
-      result(ctx.fresh.withNewTyperState)
+        refs filter (ref => isCompatible(normalize(ref), pt))
+      result(ctx.fresh.withNewTyperState) // create a defensive copy of ctx to avoid constraint pollution
     }
 
     /** No further implicit conversions can be applied when searching for implicits. */
@@ -48,20 +49,24 @@ object Implicits {
    *  @param tp              the type determining the implicit scope
    *  @param companionRefs   the companion objects in the implicit scope.
    */
-  class OfTypeImplicits(tp: Type, val companionRefs: Set[TermRef])(initctx: Context)
+  class OfTypeImplicits(tp: Type, val companionRefs: collection.Set[TermRefBySym])(initctx: Context)
     extends ImplicitRefs {
+    assert(initctx.typer != null)
     implicit val ctx: Context = initctx retractMode ImplicitsEnabled
-    val refs: Set[TermRef] = companionRefs flatMap (_.implicitMembers)
+    val refs: List[TermRef] = companionRefs.toList flatMap (_.implicitMembers)
 
     /** The implicit references that are eligible for expected type `tp` */
     lazy val eligible: List[TermRef] = filterMatching(tp)
   }
 
   /** The implicit references coming from the context.
-   *  @param refs      the implicit references made visible by the current context
+   *  @param refs      the implicit references made visible by the current context.
+   *                   Note: The name of the reference might be different from the name of its symbol.
+   *                   In the case of a renaming import a => b, the name of the reference is the renamed
+   *                   name, b, whereas the name of the symbol is the original name, a.
    *  @param outerCtx  the next outer context that makes visible further implicits
    */
-  class ContextualImplicits(val refs: Set[TermRef], val outerCtx: Context)(initctx: Context) extends ImplicitRefs {
+  class ContextualImplicits(val refs: List[TermRefBySym], val outerCtx: Context)(initctx: Context) extends ImplicitRefs {
     implicit val ctx: Context =
       if (initctx == NoContext) initctx else initctx retractMode Mode.ImplicitsEnabled
 
@@ -95,16 +100,57 @@ object Implicits {
    *  @param tree  The typed tree that can needs to be inserted
    *  @param ctx   The context after the implicit search
    */
-  case class SearchSuccess(ref: TermRef, tree: tpd.Tree, tstate: TyperState) extends SearchResult
+  case class SearchSuccess(tree: tpd.Tree)(val ref: TermRef, val tstate: TyperState) extends SearchResult
 
   /** A failed search */
-  abstract class SearchFailure extends SearchResult
-
-  /** An ambiguous implicits failure */
-  case class AmbiguousImplicits(alt1: TermRef, alt2: TermRef) extends SearchFailure
+  abstract class SearchFailure extends SearchResult {
+    /** A note describing the failure in more detail - this
+     *  is either empty or starts with a '\n'
+     */
+    def postscript(implicit ctx: Context): String = ""
+  }
 
   /** A "no matching implicit found" failure */
   case object NoImplicitMatches extends SearchFailure
+
+  /** A search failure that can show information about the cause */
+  abstract class ExplainedSearchFailure extends SearchFailure {
+    protected def pt: Type
+    protected def argument: tpd.Tree
+    protected def qualify(implicit ctx: Context) =
+      if (argument.isEmpty) i"match type $pt"
+      else i"convert from ${argument.tpe} to $pt"
+
+    /** An explanation of the cause of the failure as a string */
+    def explanation(implicit ctx: Context): String
+  }
+
+  /** An ambiguous implicits failure */
+  class AmbiguousImplicits(alt1: TermRef, alt2: TermRef, val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
+    def explanation(implicit ctx: Context): String =
+      i"both ${err.refStr(alt1)} and ${err.refStr(alt2)} $qualify"
+    override def postscript(implicit ctx: Context) =
+      "\nNote that implicit conversions cannot be applied because they are ambiguous;" +
+      "\n " + explanation
+  }
+
+  class NonMatchingImplicit(ref: TermRef, val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
+    def explanation(implicit ctx: Context): String =
+      i"${err.refStr(ref)} does not $qualify"
+  }
+
+  class ShadowedImplicit(ref: TermRef, shadowing: Type, val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
+    def explanation(implicit ctx: Context): String =
+      i"${err.refStr(ref)} does $qualify but is shadowed by ${err.refStr(shadowing)}"
+  }
+
+  class FailedImplicit(failures: List[ExplainedSearchFailure], val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
+    def explanation(implicit ctx: Context): String =
+      if (failures.isEmpty) s"  No implicit candidates were found that $qualify"
+      else "  " + (failures map (_.explanation) mkString "\n  ")
+    override def postscript(implicit ctx: Context): String =
+      "\nImplicit search failure summary:\n" + explanation
+  }
 }
 
 import Implicits._
@@ -132,26 +178,34 @@ trait ImplicitRunInfo { self: RunInfo =>
     }
   }
 
-  private def computeImplicitScope(tp: Type): OfTypeImplicits =
-    new OfTypeImplicits(tp,
-      tp match {
-        case tp: NamedType =>
-          val pre = tp.prefix
-          def addClassScope(comps: Set[TermRef], cls: ClassSymbol): Set[TermRef] = {
-            def addRef(comps: Set[TermRef], comp: TermRef): Set[TermRef] =
-              comps + comp.asSeenFrom(pre, comp.symbol.owner).asInstanceOf[TermRef]
-            def addInheritedScope(comps: Set[TermRef], parent: TypeRef): Set[TermRef] = {
-              val baseTp = cls.thisType.baseType(parent.symbol)
-              (comps /: implicitScope(baseTp).companionRefs)(addRef)
-            }
-            val companion = cls.companionModule
-            val comps1 = if (companion.exists) addRef(comps, companion.symTermRef) else comps
-            (comps1 /: cls.classParents)(addInheritedScope)
+  // todo: compute implicits directly, without going via companionRefs
+  private def computeImplicitScope(tp: Type): OfTypeImplicits = {
+    val comps = new mutable.LinkedHashSet[TermRefBySym]()
+    tp match {
+      case tp: NamedType =>
+        val pre = tp.prefix
+        comps ++= implicitScope(pre).companionRefs
+        def addClassScope(cls: ClassSymbol): Unit = {
+          def addRef(companion: TermRefBySym): Unit = {
+            val comp1 @ TermRef(p, _) = companion.asSeenFrom(pre, companion.symbol.owner)
+            comps += TermRef.withSym(p, comp1.symbol.asTerm).withDenot(comp1.denot)
+          }
+          def addParentScope(parent: TypeRef): Unit = {
+            implicitScope(parent).companionRefs foreach addRef
+            for (param <- parent.typeParams)
+              comps ++= implicitScope(pre.member(param.name).info).companionRefs
           }
-          (implicitScope(pre).companionRefs /: tp.classSymbols)(addClassScope)
-        case _ =>
-          tp.namedParts.flatMap(implicitScope(_).companionRefs)
-      })(ctx)
+          val companion = cls.companionModule
+          if (companion.exists) addRef(companion.symTermRef)
+          cls.classParents foreach addParentScope
+        }
+        tp.classSymbols foreach addClassScope
+      case _ =>
+        for (part <- tp.namedParts)
+          comps ++= implicitScope(part).companionRefs
+    }
+    new OfTypeImplicits(tp, comps)(ctx)
+  }
 
   /** The implicit scope of a type
    *  @param isLifted    Type `tp` is the result of a `liftToClasses` application
@@ -179,98 +233,99 @@ trait Implicits { self: Typer =>
        !from.isError
     && !to.isError
     && (ctx.mode is Mode.ImplicitsEnabled)
-    && (inferView(dummyTreeOfType(from), to) ne EmptyTree))
+    && (inferView(dummyTreeOfType(from), to).isInstanceOf[SearchSuccess]))
 
   /** Find an implicit conversion to apply to given tree `from` so that the
    *  result is compatible with type `to`.
    */
-  def inferView(from: tpd.Tree, to: Type)(implicit ctx: Context): Tree =
-    inferImplicit(to, from, from.pos, reportAmbiguous = false)
+  def inferView(from: tpd.Tree, to: Type)(implicit ctx: Context): SearchResult =
+    inferImplicit(to, from, from.pos)
 
   /** Find an implicit parameter or conversion.
    *  @param pt              The expected type of the parameter or conversion.
    *  @param argument        If an implicit conversion is searched, the argument to which
    *                         it should be applied, EmptyTree otherwise.
    *  @param pos             The position where errors should be reported.
-   *  @param reportAmbiguous Should ambiguity errors be reported? False when called from `viewExists`.
    */
-  def inferImplicit(pt: Type, argument: Tree, pos: Position, reportAmbiguous: Boolean = true)(implicit ctx: Context): Tree =
-    ctx.traceIndented(s"search implicit $pt, arg = ${argument.show}, reportAmbiguous = $reportAmbiguous", show = true) {
-    new ImplicitSearch(pt, argument, pos).bestImplicit match {
-      case SearchSuccess(_, tree, tstate) =>
-        tstate.commit()
-        tree
-      case NoImplicitMatches =>
-        EmptyTree
-      case AmbiguousImplicits(alt1, alt2) =>
-        if (reportAmbiguous) {
-          val qualify =
-            if (argument.isEmpty) s"match type $pt"
-            else s"can convert from ${argument.tpe} to $pt"
-          ctx.error(s"ambiguous implicits; both $alt1 and $alt2 $qualify")
-        }
-        EmptyTree
+  def inferImplicit(pt: Type, argument: Tree, pos: Position)(implicit ctx: Context): SearchResult =
+    ctx.traceIndented(s"search implicit $pt, arg = ${argument.show}", show = true) {
+    val isearch =
+      if (ctx.settings.explaintypes.value) new ExplainedImplicitSearch(pt, argument, pos)
+      else new ImplicitSearch(pt, argument, pos)
+    val result = isearch.bestImplicit
+    result match {
+      case success: SearchSuccess => success.tstate.commit()
+      case _ =>
     }
+    result
   }
 
   /** An implicit search; parameters as in `inferImplicit` */
-  class ImplicitSearch(pt: Type, argument: Tree, pos: Position)(implicit ctx: Context) {
-
-    /** Try to typecheck an implicit reference */
-    def typedImplicit(ref: TermRef)(implicit ctx: Context): SearchResult = {
-      val id = Ident(ref).withPos(pos)
-      val tree =
-        if (argument.isEmpty) adapt(id, pt)
-        else typedApply(id, ref, argument :: Nil, pt)
-      if (tree.tpe.isError) NoImplicitMatches // todo: replace by checking if local errors were reported in ctx.
-      else SearchSuccess(ref, tree, ctx.typerState)
-    }
-
-    /** Given a list of implicit references, produce a list of all implicit search successes,
-     *  where the first is supposed to be the best one.
-     *  @param pending   The list of implicit references
-     *  @param acc       An accumulator of successful matches found so far.
-     */
-    private def rankImplicits(pending: List[TermRef], acc: List[SearchSuccess]): List[SearchSuccess] = pending match {
-      case ref :: pending1 =>
-        typedImplicit(ref)(ctx.fresh.withNewTyperState.retractMode(ImplicitsEnabled)) match {
-          case fail: SearchFailure =>
-            rankImplicits(pending1, acc)
-          case best @ SearchSuccess(bestRef, _, _) =>
-            val newPending = pending filterNot (isAsGood(_, bestRef))
-            rankImplicits(newPending, best :: acc)
-        }
-      case nil => acc
-    }
+  class ImplicitSearch(protected val pt: Type, protected val argument: Tree, pos: Position)(implicit ctx: Context) {
 
-    /** Convert a (possibly empty) list of search successes into a single search result */
-    def condense(hits: List[SearchSuccess]): SearchResult = hits match {
-      case best :: alts =>
-        alts find (alt => isAsGood(alt.ref, best.ref)) match {
-          case Some(alt) =>
-            AmbiguousImplicits(best.ref, alt.ref)
-          case None =>
-            ctx.runInfo.useCount(best.ref) += 1
-            best
-        }
-      case Nil =>
-        NoImplicitMatches
-    }
+    protected def nonMatchingImplicit(ref: TermRef): SearchFailure = NoImplicitMatches
+    protected def shadowedImplicit(ref: TermRef, shadowing: Type): SearchFailure = NoImplicitMatches
+    protected def failedSearch: SearchFailure = NoImplicitMatches
 
-    /** Sort list of implicit references according to their popularity
-     *  (# of times each was picked in current run).
-     */
-    def sort(eligible: List[TermRef]) = eligible match {
-      case Nil => eligible
-      case e1 :: Nil => eligible
-      case e1 :: e2 :: Nil =>
-        if (ctx.runInfo.useCount(e1) < ctx.runInfo.useCount(e2)) e2 :: e1 :: Nil
-        else eligible
-      case _ => eligible.sortBy(-ctx.runInfo.useCount(_))
-    }
 
     /** Search a list of eligible implicit references */
-    def searchImplicits(eligible: List[TermRef]): SearchResult = {
+    def searchImplicits(eligible: List[TermRef], contextual: Boolean): SearchResult = {
+
+      /** Try to typecheck an implicit reference */
+      def typedImplicit(ref: TermRef)(implicit ctx: Context): SearchResult = {
+        val id = Ident(ref).withPos(pos)
+        val tree =
+          if (argument.isEmpty) adapt(id, pt)
+          else typedApply(id, ref, argument :: Nil, pt)
+        lazy val shadowing = typed(untpd.Ident(ref.name), ref).tpe
+        if (ctx.typerState.reporter.hasErrors) nonMatchingImplicit(ref)
+        else if (contextual && !(shadowing =:= ref)) shadowedImplicit(ref, shadowing)
+        else SearchSuccess(tree)(ref, ctx.typerState)
+      }
+
+      /** Given a list of implicit references, produce a list of all implicit search successes,
+       *  where the first is supposed to be the best one.
+       *  @param pending   The list of implicit references
+       *  @param acc       An accumulator of successful matches found so far.
+       */
+      def rankImplicits(pending: List[TermRef], acc: List[SearchSuccess]): List[SearchSuccess] = pending match {
+        case ref :: pending1 =>
+          typedImplicit(ref)(ctx.fresh.withNewTyperState.retractMode(ImplicitsEnabled)) match {
+            case fail: SearchFailure =>
+              rankImplicits(pending1, acc)
+            case best: SearchSuccess =>
+              val newPending = pending filterNot (isAsGood(_, best.ref))
+              rankImplicits(newPending, best :: acc)
+          }
+        case nil => acc
+      }
+
+      /** Convert a (possibly empty) list of search successes into a single search result */
+      def condense(hits: List[SearchSuccess]): SearchResult = hits match {
+        case best :: alts =>
+          alts find (alt => isAsGood(alt.ref, best.ref)) match {
+            case Some(alt) =>
+              new AmbiguousImplicits(best.ref, alt.ref, pt, argument)
+            case None =>
+              ctx.runInfo.useCount(best.ref) += 1
+              best
+          }
+        case Nil =>
+          failedSearch
+      }
+
+      /** Sort list of implicit references according to their popularity
+       *  (# of times each was picked in current run).
+       */
+      def sort(eligible: List[TermRef]) = eligible match {
+        case Nil => eligible
+        case e1 :: Nil => eligible
+        case e1 :: e2 :: Nil =>
+          if (ctx.runInfo.useCount(e1) < ctx.runInfo.useCount(e2)) e2 :: e1 :: Nil
+          else eligible
+        case _ => eligible.sortBy(-ctx.runInfo.useCount(_))
+      }
+
       condense(rankImplicits(sort(eligible), Nil))
     }
 
@@ -285,14 +340,33 @@ trait Implicits { self: Typer =>
 
     /** Find a unique best implicit reference */
     def bestImplicit: SearchResult = {
-      searchImplicits(ctx.implicits.eligible(wildPt)) match {
+      searchImplicits(ctx.implicits.eligible(wildPt), contextual = true) match {
         case result: SearchSuccess => result
         case result: AmbiguousImplicits => result
-        case NoImplicitMatches => searchImplicits(implicitScope(wildPt).eligible)
+        case result: SearchFailure =>
+          searchImplicits(implicitScope(wildPt).eligible, contextual = false)
       }
     }
 
     def implicitScope(tp: Type): OfTypeImplicits = ctx.runInfo.implicitScope(tp)
   }
 
+  final class ExplainedImplicitSearch(pt: Type, argument: Tree, pos: Position)(implicit ctx: Context)
+  extends ImplicitSearch(pt, argument, pos) {
+    private var myFailures = new mutable.ListBuffer[ExplainedSearchFailure]
+    private def record(fail: ExplainedSearchFailure) = {
+      myFailures += fail
+      fail
+    }
+    def failures = myFailures.toList
+    override def nonMatchingImplicit(ref: TermRef) =
+      record(new NonMatchingImplicit(ref, pt, argument))
+    override def shadowedImplicit(ref: TermRef, shadowing: Type): SearchFailure =
+      record(new ShadowedImplicit(ref, shadowing, pt, argument))
+    override def failedSearch: SearchFailure = {
+      println(s"wildPt = $wildPt")
+      println(s"implicit scope = ${implicitScope(wildPt).companionRefs}")
+      new FailedImplicit(failures, pt, argument)
+    }
+  }
 }
\ No newline at end of file