[nomaster] 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.

NOTE: This is a partial backport of https://github.com/scala/scala/pull/2428,
with a fix for SI-7291, but without removal of error kinds (the former is
absolutely necessary, while the latter is nice to have, but not a must,
therefore I'm not risking porting it to 2.10.x). Also, the fix for SI-7291
is hidden behind a flag named -Xdivergence211 in order not to occasionally
break the code, which relies on pre-fix behavior.

17 files changed, 171 insertions, 14 deletions

diff --git a/src/compiler/scala/tools/nsc/interactive/Global.scala b/src/compiler/scala/tools/nsc/interactive/Global.scala
index c63cca9b88..84670750d7 100644
--- a/src/compiler/scala/tools/nsc/interactive/Global.scala
+++ b/src/compiler/scala/tools/nsc/interactive/Global.scala
@@ -1174,8 +1174,13 @@ class Global(settings: Settings, _reporter: Reporter, projectName: String = "")
         debugLog("type error caught: "+ex)
         alt
       case ex: DivergentImplicit =>
-        debugLog("divergent implicit caught: "+ex)
-        alt
+        if (settings.Xdivergence211.value) {
+          debugLog("this shouldn't happen. DivergentImplicit exception has been thrown with -Xdivergence211 turned on: "+ex)
+          alt
+        } else {
+          debugLog("divergent implicit caught: "+ex)
+          alt
+        }
     }
   }
 
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 3df6334ec1..dbfaa2c531 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -110,6 +110,7 @@ trait ScalaSettings extends AbsScalaSettings
   val XoldPatmat    = BooleanSetting    ("-Xoldpatmat", "Use the pre-2.10 pattern matcher. Otherwise, the 'virtualizing' pattern matcher is used in 2.10.")
   val XnoPatmatAnalysis = BooleanSetting ("-Xno-patmat-analysis", "Don't perform exhaustivity/unreachability analysis. Also, ignore @switch annotation.")
   val XfullLubs     = BooleanSetting    ("-Xfull-lubs", "Retains pre 2.10 behavior of less aggressive truncation of least upper bounds.")
+  val Xdivergence211 = BooleanSetting   ("-Xdivergence211", "Turn on the 2.11 behavior of implicit divergence not terminating recursive implicit searches (SI-7291).")
 
   /** Compatibility stubs for options whose value name did
    *  not previously match the option name.
diff --git a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
index 49049f110d..e0dbe98780 100644
--- a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
@@ -60,6 +60,24 @@ 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.
+  // only issued when -Xdivergence211 is turned on
+  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
@@ -73,6 +91,7 @@ trait ContextErrors {
       issueTypeError(SymbolTypeError(sym, msg))
     }
 
+    // only called when -Xdivergence211 is turned off
     def issueDivergentImplicitsError(tree: Tree, msg: String)(implicit context: Context) {
       issueTypeError(NormalTypeError(tree, msg, ErrorKinds.Divergent))
     }
@@ -1152,9 +1171,13 @@ 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)
+      if (settings.Xdivergence211.value) {
+        issueTypeError(DivergentImplicitTypeError(tree, pt, sym))
+      } else {
+        issueDivergentImplicitsError(tree,
+            "diverging implicit expansion for type "+pt+"\nstarting with "+
+            sym.fullLocationString)
+      }
   }
 
   object NamesDefaultsErrorsGen {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 81e47eecb0..a8de11911c 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 || !settings.Xdivergence211.value) && saveAmbiguousDivergent && implicitSearchContext.hasErrors) {
       context.updateBuffer(implicitSearchContext.errBuffer.filter(err => err.kind == ErrorKinds.Ambiguous || err.kind == ErrorKinds.Divergent))
       debugwarn("update buffer: " + implicitSearchContext.errBuffer)
     }
@@ -152,6 +152,8 @@ trait Implicits {
 
     def isFailure          = false
     def isAmbiguousFailure = false
+    // only used when -Xdivergence211 is turned on
+    def isDivergent        = false
     final def isSuccess    = !isFailure
   }
 
@@ -159,6 +161,12 @@ trait Implicits {
     override def isFailure = true
   }
 
+  // only used when -Xdivergence211 is turned on
+  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
@@ -425,8 +433,10 @@ trait Implicits {
       (context.openImplicits find { case OpenImplicit(info, tp, tree1) => !info.sym.isMacro && tree1.symbol == tree.symbol && dominates(pt, tp)}) match {
          case Some(pending) =>
            //println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
-           throw DivergentImplicit
+           if (settings.Xdivergence211.value) DivergentSearchFailure
+           else throw DivergentImplicit
          case None =>
+           def pre211DivergenceLogic() = {
            try {
              context.openImplicits = OpenImplicit(info, pt, tree) :: context.openImplicits
              // println("  "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
@@ -444,6 +454,24 @@ trait Implicits {
            } finally {
              context.openImplicits = context.openImplicits.tail
            }
+           }
+           def post211DivergenceLogic() = {
+             try {
+               context.openImplicits = OpenImplicit(info, pt, tree) :: context.openImplicits
+               // println("  "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
+               val result = typedImplicit0(info, ptChecked, isLocal)
+               if (result.isDivergent) {
+                 //println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
+                 if (context.openImplicits.tail.isEmpty && !pt.isErroneous)
+                   DivergingImplicitExpansionError(tree, pt, info.sym)(context)
+               }
+               result
+             } finally {
+               context.openImplicits = context.openImplicits.tail
+             }
+           }
+           if (settings.Xdivergence211.value) post211DivergenceLogic()
+           else pre211DivergenceLogic()
        }
     }
 
@@ -812,6 +840,9 @@ trait Implicits {
 
       /** Preventing a divergent implicit from terminating implicit search,
        *  so that if there is a best candidate it can still be selected.
+       *
+       *  The old way of handling divergence.
+       *  Only enabled when -Xdivergence211 is turned off.
        */
       private var divergence = false
       private val divergenceHandler: PartialFunction[Throwable, SearchResult] = {
@@ -824,6 +855,28 @@ trait Implicits {
         }
       }
 
+      /** Preventing a divergent implicit from terminating implicit search,
+       *  so that if there is a best candidate it can still be selected.
+       *
+       *  The new way of handling divergence.
+       *  Only enabled when -Xdivergence211 is turned on.
+       */
+      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.
        */
       val eligible = {
@@ -850,11 +903,20 @@ trait Implicits {
       @tailrec private def rankImplicits(pending: Infos, acc: Infos): Infos = pending match {
         case Nil      => acc
         case i :: is  =>
-          def tryImplicitInfo(i: ImplicitInfo) =
+          def pre211tryImplicitInfo(i: ImplicitInfo) =
             try typedImplicit(i, ptChecked = true, isLocal)
             catch divergenceHandler
 
-          tryImplicitInfo(i) match {
+          def post211tryImplicitInfo(i: ImplicitInfo) =
+            DivergentImplicitRecovery(typedImplicit(i, ptChecked = true, isLocal), i)
+
+          {
+            if (settings.Xdivergence211.value) post211tryImplicitInfo(i)
+            else pre211tryImplicitInfo(i)
+          } match {
+            // only used if -Xdivergence211 is turned on
+            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.
@@ -906,9 +968,10 @@ 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
-          else invalidImplicits take 1 foreach { sym =>
+          if (divergence || DivergentImplicitRecovery.sym != null) {
+            if (settings.Xdivergence211.value) DivergingImplicitExpansionError(tree, pt, DivergentImplicitRecovery.sym)(context)
+            else throw DivergentImplicit
+          } else invalidImplicits take 1 foreach { sym =>
             def isSensibleAddendum = pt match {
               case Function1(_, out) => out <:< sym.tpe.finalResultType
               case tp                => tp <:< sym.tpe.finalResultType
@@ -1478,5 +1541,6 @@ object ImplicitsStats {
   val implicitCacheHits   = Statistics.newSubCounter("implicit cache hits", implicitCacheAccs)
 }
 
+// only used when -Xdivergence211 is turned off
 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 16481774d0..b89b570cd8 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -138,13 +138,18 @@ trait Typers extends Modes with Adaptations with Tags {
             mkArg = mkNamedArg // don't pass the default argument (if any) here, but start emitting named arguments for the following args
             if (!param.hasDefault && !paramFailed) {
               context.errBuffer.find(_.kind == ErrorKinds.Divergent) match {
-                case Some(divergentImplicit) =>
+                case Some(divergentImplicit) if !settings.Xdivergence211.value =>
                   // 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.condBufferFlush(_.kind  == ErrorKinds.Divergent)
                   }
+                case Some(divergentImplicit: DivergentImplicitTypeError) if settings.Xdivergence211.value =>
+                  if (context.reportErrors) {
+                    context.issue(divergentImplicit.withPt(paramTp))
+                    context.condBufferFlush(_.kind  == ErrorKinds.Divergent)
+                  }
                 case None =>
                   NoImplicitFoundError(fun, param)
               }
diff --git a/test/files/neg/t696.check b/test/files/neg/t696a.check
index ac26a864a5..490fc1a571 100644
--- a/test/files/neg/t696.check
+++ b/test/files/neg/t696a.check
@@ -1,4 +1,4 @@
-t696.scala:4: error: diverging implicit expansion for type TypeUtil0.Type[Any]
+t696a.scala:4: error: diverging implicit expansion for type TypeUtil0.Type[Any]
 starting with method WithType in object TypeUtil0
   as[Any](null);
          ^
diff --git a/test/files/neg/t696a.flags b/test/files/neg/t696a.flags
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/files/neg/t696a.flags
diff --git a/test/files/neg/t696.scala b/test/files/neg/t696a.scala
index a06a32141a..a06a32141a 100644
--- a/test/files/neg/t696.scala
+++ b/test/files/neg/t696a.scala
diff --git a/test/files/neg/t696b.check b/test/files/neg/t696b.check
new file mode 100644
index 0000000000..fcdb5440d8
--- /dev/null
+++ b/test/files/neg/t696b.check
@@ -0,0 +1,9 @@
+t696b.scala:5: error: diverging implicit expansion for type TypeUtil0.Type[Any]
+starting with method WithType in object TypeUtil0
+  as[Any](null)
+         ^
+t696b.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/t696b.flags b/test/files/neg/t696b.flags
new file mode 100644
index 0000000000..d564f2b1f8
--- /dev/null
+++ b/test/files/neg/t696b.flags
@@ -0,0 +1 @@
+-Xdivergence211
\ No newline at end of file
diff --git a/test/files/neg/t696b.scala b/test/files/neg/t696b.scala
new file mode 100644
index 0000000000..ca76f7ef6c
--- /dev/null
+++ b/test/files/neg/t696b.scala
@@ -0,0 +1,7 @@
+object TypeUtil0 {
+  trait Type[+T]
+  implicit def WithType[S,T](implicit tpeS : Type[S], tpeT : Type[T]) : Type[S with 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/t7291a.check b/test/files/run/t7291a.check
new file mode 100644
index 0000000000..126faa15b4
--- /dev/null
+++ b/test/files/run/t7291a.check
@@ -0,0 +1 @@
+conjure
diff --git a/test/files/run/t7291a.flags b/test/files/run/t7291a.flags
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/files/run/t7291a.flags
diff --git a/test/files/run/t7291a.scala b/test/files/run/t7291a.scala
new file mode 100644
index 0000000000..4b7c4a4184
--- /dev/null
+++ b/test/files/run/t7291a.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]]]
+  }
+}
diff --git a/test/files/run/t7291b.check b/test/files/run/t7291b.check
new file mode 100644
index 0000000000..c07ba986a3
--- /dev/null
+++ b/test/files/run/t7291b.check
@@ -0,0 +1,2 @@
+conjure
+traversable
diff --git a/test/files/run/t7291b.flags b/test/files/run/t7291b.flags
new file mode 100644
index 0000000000..d564f2b1f8
--- /dev/null
+++ b/test/files/run/t7291b.flags
@@ -0,0 +1 @@
+-Xdivergence211
\ No newline at end of file
diff --git a/test/files/run/t7291b.scala b/test/files/run/t7291b.scala
new file mode 100644
index 0000000000..30c4261a81
--- /dev/null
+++ b/test/files/run/t7291b.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]]] 
+  }
+}