SI-7291: No exception throwing for diverging implicit expansion

Since we don't throw exceptions for normal errors it was a bit odd
that we don't do that for DivergingImplicit.
As SI-7291 shows, the logic behind catching/throwing exception
was broken for divergence. Instead of patching it, I rewrote
the mechanism so that we now another SearchFailure type related
to diverging expansion, similar to ambiguous implicit scenario.
The logic to prevent diverging expansion from stopping the search
had to be slightly adapted but works as usual.

The upside is that we don't have to catch diverging implicit
for example in the presentation compiler which was again showing
that something was utterly broken with the exception approach.

9 files changed, 116 insertions, 76 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
index 89fc55bc2c..5dd945eaea 100644
--- a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
@@ -59,6 +59,23 @@ trait ContextErrors {
     def errPos = tree.pos
   }
 
+  // Unlike other type errors diverging implicit expansion
+  // will be re-issued explicitly on failed implicit argument search.
+  // This is because we want to:
+  // 1) provide better error message than just "implicit not found"
+  // 2) provide the type of the implicit parameter for which we got diverging expansion
+  //    (pt at the point of divergence gives less information to the user)
+  // Note: it is safe to delay error message generation in this case
+  // becasue we don't modify implicits' infos.
+  case class DivergentImplicitTypeError(tree: Tree, pt0: Type, sym: Symbol) extends AbsTypeError {
+    def errPos: Position = tree.pos
+    def errMsg: String   = errMsgForPt(pt0)
+    def kind = ErrorKinds.Divergent
+    def withPt(pt: Type): AbsTypeError = NormalTypeError(tree, errMsgForPt(pt), kind)
+    private def errMsgForPt(pt: Type) = 
+      s"diverging implicit expansion for type ${pt}\nstarting with ${sym.fullLocationString}"
+  }
+
   case class AmbiguousTypeError(underlyingTree: Tree, errPos: Position, errMsg: String, kind: ErrorKind = ErrorKinds.Ambiguous) extends AbsTypeError
 
   case class PosAndMsgTypeError(errPos: Position, errMsg: String, kind: ErrorKind = ErrorKinds.Normal) extends AbsTypeError
@@ -72,9 +89,6 @@ trait ContextErrors {
       issueTypeError(SymbolTypeError(sym, msg))
     }
 
-    def issueDivergentImplicitsError(tree: Tree, msg: String)(implicit context: Context) {
-      issueTypeError(NormalTypeError(tree, msg, ErrorKinds.Divergent))
-    }
 
     def issueAmbiguousTypeError(pre: Type, sym1: Symbol, sym2: Symbol, err: AmbiguousTypeError)(implicit context: Context) {
       context.issueAmbiguousError(pre, sym1, sym2, err)
@@ -1182,9 +1196,7 @@ trait ContextErrors {
     }
 
     def DivergingImplicitExpansionError(tree: Tree, pt: Type, sym: Symbol)(implicit context0: Context) =
-      issueDivergentImplicitsError(tree,
-          "diverging implicit expansion for type "+pt+"\nstarting with "+
-          sym.fullLocationString)
+      issueTypeError(DivergentImplicitTypeError(tree, pt, sym))
   }
 
   object NamesDefaultsErrorsGen {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index b0c8baae20..59ed64ac03 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -80,7 +80,7 @@ trait Implicits {
       printTyping("typing implicit: %s %s".format(tree, context.undetparamsString))
     val implicitSearchContext = context.makeImplicit(reportAmbiguous)
     val result = new ImplicitSearch(tree, pt, isView, implicitSearchContext, pos).bestImplicit
-    if (saveAmbiguousDivergent && implicitSearchContext.hasErrors) {
+    if (result.isFailure && saveAmbiguousDivergent && implicitSearchContext.hasErrors) {
       context.updateBuffer(implicitSearchContext.reportBuffer.errors.filter(err => err.kind == ErrorKinds.Ambiguous || err.kind == ErrorKinds.Divergent))
       debuglog("update buffer: " + implicitSearchContext.reportBuffer.errors)
     }
@@ -152,6 +152,7 @@ trait Implicits {
 
     def isFailure          = false
     def isAmbiguousFailure = false
+    def isDivergent        = false
     final def isSuccess    = !isFailure
   }
 
@@ -159,6 +160,11 @@ trait Implicits {
     override def isFailure = true
   }
 
+  lazy val DivergentSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) {
+    override def isFailure   = true
+    override def isDivergent = true
+  }
+  
   lazy val AmbiguousSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) {
     override def isFailure          = true
     override def isAmbiguousFailure = true
@@ -397,22 +403,18 @@ trait Implicits {
       (context.openImplicits find { case (tp, tree1) => tree1.symbol == tree.symbol && dominates(pt, tp)}) match {
          case Some(pending) =>
            //println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
-           throw DivergentImplicit
+           DivergentSearchFailure
          case None =>
            try {
              context.openImplicits = (pt, tree) :: context.openImplicits
              // println("  "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
-             typedImplicit0(info, ptChecked, isLocal)
-           } catch {
-             case ex: DivergentImplicit =>
+             val result = typedImplicit0(info, ptChecked, isLocal)
+             if (result.isDivergent) {
                //println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
-               if (context.openImplicits.tail.isEmpty) {
-                 if (!(pt.isErroneous))
-                   DivergingImplicitExpansionError(tree, pt, info.sym)(context)
-                 SearchFailure
-               } else {
-                 throw DivergentImplicit
-               }
+               if (context.openImplicits.tail.isEmpty && !pt.isErroneous)
+                 DivergingImplicitExpansionError(tree, pt, info.sym)(context)
+             }
+             result
            } finally {
              context.openImplicits = context.openImplicits.tail
            }
@@ -789,16 +791,21 @@ trait Implicits {
       /** Preventing a divergent implicit from terminating implicit search,
        *  so that if there is a best candidate it can still be selected.
        */
-      private var divergence = false
-      private val divergenceHandler: PartialFunction[Throwable, SearchResult] = {
-        var remaining = 1;
-        { case x: DivergentImplicit if remaining > 0 =>
-            remaining -= 1
-            divergence = true
-            log("discarding divergent implicit during implicit search")
+      object DivergentImplicitRecovery {
+        // symbol of the implicit that caused the divergence.
+        // Initially null, will be saved on first diverging expansion.
+        private var implicitSym: Symbol    = _
+        private var countdown: Int = 1
+        
+        def sym: Symbol = implicitSym
+        def apply(search: SearchResult, i: ImplicitInfo): SearchResult = 
+          if (search.isDivergent && countdown > 0) {
+            countdown -= 1
+            implicitSym = i.sym
+            log("discarding divergent implicit ${implicitSym} during implicit search")
             SearchFailure
-        }
-      }
+          } else search
+      } 
 
       /** Sorted list of eligible implicits.
        */
@@ -826,11 +833,9 @@ trait Implicits {
       @tailrec private def rankImplicits(pending: Infos, acc: Infos): Infos = pending match {
         case Nil      => acc
         case i :: is  =>
-          def tryImplicitInfo(i: ImplicitInfo) =
-            try typedImplicit(i, ptChecked = true, isLocal)
-            catch divergenceHandler
-
-          tryImplicitInfo(i) match {
+          DivergentImplicitRecovery(typedImplicit(i, ptChecked = true, isLocal), i) match {
+            case sr if sr.isDivergent =>
+              Nil
             case sr if sr.isFailure =>
               // We don't want errors that occur during checking implicit info
               // to influence the check of further infos.
@@ -882,10 +887,9 @@ trait Implicits {
           /* If there is no winner, and we witnessed and caught divergence,
            * now we can throw it for the error message.
            */
-          if (divergence)
-            throw DivergentImplicit
-
-          if (invalidImplicits.nonEmpty)
+          if (DivergentImplicitRecovery.sym != null) {
+            DivergingImplicitExpansionError(tree, pt, DivergentImplicitRecovery.sym)(context)
+          } else if (invalidImplicits.nonEmpty)
             setAddendum(pos, () =>
               "\n Note: implicit "+invalidImplicits.head+" is not applicable here"+
               " because it comes after the application point and it lacks an explicit result type")
@@ -1438,6 +1442,3 @@ object ImplicitsStats {
   val implicitCacheAccs   = Statistics.newCounter   ("implicit cache accesses", "typer")
   val implicitCacheHits   = Statistics.newSubCounter("implicit cache hits", implicitCacheAccs)
 }
-
-class DivergentImplicit extends Exception
-object DivergentImplicit extends DivergentImplicit
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 6e26b12226..637abe4be2 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -151,11 +151,11 @@ trait Typers extends Adaptations with Tags {
             mkArg = gen.mkNamedArg // don't pass the default argument (if any) here, but start emitting named arguments for the following args
             if (!param.hasDefault && !paramFailed) {
               context.reportBuffer.errors.find(_.kind == ErrorKinds.Divergent) match {
-                case Some(divergentImplicit) =>
+                case Some(divergent: DivergentImplicitTypeError) =>
                   // DivergentImplicit error has higher priority than "no implicit found"
                   // no need to issue the problem again if we are still in silent mode
                   if (context.reportErrors) {
-                    context.issue(divergentImplicit)
+                    context.issue(divergent.withPt(paramTp))
                     context.reportBuffer.clearErrors(ErrorKinds.Divergent)
                   }
                 case None =>
@@ -1627,22 +1627,27 @@ trait Typers extends Adaptations with Tags {
 
     /** Makes sure that the first type tree in the list of parent types is always a class.
      *  If the first parent is a trait, prepend its supertype to the list until it's a class.
-*/
-    private def normalizeFirstParent(parents: List[Tree]): List[Tree] = parents match {
-      case first :: rest if treeInfo.isTraitRef(first) =>
-        def explode(supertpt: Tree, acc: List[Tree]): List[Tree] = {
-          if (treeInfo.isTraitRef(supertpt)) {
-            val supertpt1 = typedType(supertpt)
-            if (!supertpt1.isErrorTyped) {
-              val supersupertpt = TypeTree(supertpt1.tpe.firstParent) setPos supertpt.pos.focus
-              return explode(supersupertpt, supertpt1 :: acc)
-            }
-          }
-          if (supertpt.tpe.typeSymbol == AnyClass) supertpt setType AnyRefClass.tpe
-          supertpt :: acc
-        }
-        explode(first, Nil) ++ rest
-      case _ => parents
+     */
+    private def normalizeFirstParent(parents: List[Tree]): List[Tree] = {
+      @annotation.tailrec
+      def explode0(parents: List[Tree]): List[Tree] = {
+        val supertpt :: rest = parents // parents is always non-empty here - it only grows
+        if (supertpt.tpe.typeSymbol == AnyClass) {
+          supertpt setType AnyRefTpe
+          parents
+        } else if (treeInfo isTraitRef supertpt) {
+          val supertpt1  = typedType(supertpt)
+          def supersuper = TypeTree(supertpt1.tpe.firstParent) setPos supertpt.pos.focus
+          if (supertpt1.isErrorTyped) rest
+          else explode0(supersuper :: supertpt1 :: rest)
+        } else parents
+      }
+
+      def explode(parents: List[Tree]) =
+        if (treeInfo isTraitRef parents.head) explode0(parents)
+        else parents
+
+      if (parents.isEmpty) Nil else explode(parents)
     }
 
     /** Certain parents are added in the parser before it is known whether
diff --git a/src/compiler/scala/tools/reflect/ToolBoxFactory.scala b/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
index 66dda2b530..6fb8b4ea37 100644
--- a/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
+++ b/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
@@ -181,16 +181,15 @@ abstract class ToolBoxFactory[U <: JavaUniverse](val u: U) { factorySelf =>
           (currentTyper, tree) => {
             trace("inferring implicit %s (macros = %s): ".format(if (isView) "view" else "value", !withMacrosDisabled))(showAttributed(pt, true, true, settings.Yshowsymkinds.value))
             val context = currentTyper.context
-            analyzer.inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos) match {
-              case failure if failure.tree.isEmpty =>
-                trace("implicit search has failed. to find out the reason, turn on -Xlog-implicits: ")(failure.tree)
-                context.firstError foreach { err =>
-                  throw ToolBoxError("reflective implicit search has failed: %s".format(err.errMsg))
-                }
-                EmptyTree
-              case success =>
-                success.tree
+            val result = analyzer.inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos)
+            if (result.isFailure) {
+              // @H: what's the point of tracing an empty tree?
+              trace("implicit search has failed. to find out the reason, turn on -Xlog-implicits: ")(result.tree)
+              context.firstError foreach { err =>
+                throw ToolBoxError("reflective implicit search has failed: %s".format(err.errMsg))
+              }
             }
+            result.tree
           })
 
       def compile(expr0: Tree): () => Any = {
diff --git a/src/interactive/scala/tools/nsc/interactive/Global.scala b/src/interactive/scala/tools/nsc/interactive/Global.scala
index 43b8bd2738..792ca6efa6 100644
--- a/src/interactive/scala/tools/nsc/interactive/Global.scala
+++ b/src/interactive/scala/tools/nsc/interactive/Global.scala
@@ -15,7 +15,7 @@ import scala.reflect.internal.util.{ SourceFile, BatchSourceFile, Position, NoPo
 import scala.tools.nsc.reporters._
 import scala.tools.nsc.symtab._
 import scala.tools.nsc.doc.ScaladocAnalyzer
-import scala.tools.nsc.typechecker.{ Analyzer, DivergentImplicit }
+import scala.tools.nsc.typechecker.Analyzer
 import symtab.Flags.{ACCESSOR, PARAMACCESSOR}
 import scala.annotation.{ elidable, tailrec }
 import scala.language.implicitConversions
@@ -1210,9 +1210,6 @@ class Global(settings: Settings, _reporter: Reporter, projectName: String = "")
       case ex: TypeError =>
         debugLog("type error caught: "+ex)
         alt
-      case ex: DivergentImplicit =>
-        debugLog("divergent implicit caught: "+ex)
-        alt
     }
   }
 
diff --git a/test/files/neg/t696.check b/test/files/neg/t696.check
index ac26a864a5..b7bc5cdf98 100644
--- a/test/files/neg/t696.check
+++ b/test/files/neg/t696.check
@@ -1,5 +1,9 @@
-t696.scala:4: error: diverging implicit expansion for type TypeUtil0.Type[Any]
+t696.scala:5: error: diverging implicit expansion for type TypeUtil0.Type[Any]
 starting with method WithType in object TypeUtil0
-  as[Any](null);
+  as[Any](null)
          ^
-one error found
+t696.scala:6: error: diverging implicit expansion for type TypeUtil0.Type[X]
+starting with method WithType in object TypeUtil0
+  def foo[X]() = as[X](null)
+                      ^
+two errors found
diff --git a/test/files/neg/t696.scala b/test/files/neg/t696.scala
index a06a32141a..ca76f7ef6c 100644
--- a/test/files/neg/t696.scala
+++ b/test/files/neg/t696.scala
@@ -1,6 +1,7 @@
 object TypeUtil0 {
-  trait Type[+T];
+  trait Type[+T]
   implicit def WithType[S,T](implicit tpeS : Type[S], tpeT : Type[T]) : Type[S with T] = null
-  as[Any](null);
-  def as[T](x : Any)(implicit tpe : Type[T]) = null;
+  def as[T](x : Any)(implicit tpe : Type[T]) = null
+  as[Any](null)
+  def foo[X]() = as[X](null)
 }
diff --git a/test/files/run/t7291.check b/test/files/run/t7291.check
new file mode 100644
index 0000000000..c07ba986a3
--- /dev/null
+++ b/test/files/run/t7291.check
@@ -0,0 +1,2 @@
+conjure
+traversable
diff --git a/test/files/run/t7291.scala b/test/files/run/t7291.scala
new file mode 100644
index 0000000000..30c4261a81
--- /dev/null
+++ b/test/files/run/t7291.scala
@@ -0,0 +1,19 @@
+trait Fooable[T]
+object Fooable {
+  implicit def conjure[T]: Fooable[T] = {
+    println("conjure")
+    new Fooable[T]{}
+  }
+
+}
+
+object Test {
+  implicit def traversable[T, Coll[_] <: Traversable[_]](implicit
+elem: Fooable[T]): Fooable[Coll[T]] = {
+    println("traversable")
+    new Fooable[Coll[T]]{}
+  }
+  def main(args: Array[String]) {
+    implicitly[Fooable[List[Any]]] 
+  }
+}