SI-8341 Refine handoff of undet. params from implicit search

In SI-7944 / 251c2b93, we discovered that typechecking of an implicit
candidate could leave orphaned undetermined type parameters in the
implicit search context. This resulted in naked type parameters
leaking into implicit expansions. The fix seemed easy: just copy
any symbols from `implicitSearchContext.undetparams` to the enclosing
context (other than ones in `SearchResult#subst`).

However, the test case in this ticket reveals a subtle flaw in that
fix: `implicitSerachContext.undetparams` only contains the type params
from the most recently typechecked candidate!

Why? Implicit search uses the same context to typecheck all plausibly
compatible candidates.  The typechecking itself is driven by
`typedImplicit1`.

Side note, that explains the heisenbug behaviour noted in the ticket:
Not *all* plausibly implicit candidates are typechecked. If
the current 'best' eligible candidate is more specific than the next
candidate, we can skip that altogether.Implicit search actually
exploits this for performance by ordering the candidates according to
usage statistics. This reordering, means that commenting out lines
elsewhere in the file changed the behaviour!

This commit simply stores the undet. tparams in the `SearchResult`,
where it is safe from the vaguries of typechecking other candidates.

That makes `Test1` and `Test2` with in the enclosed test case fail
uniformly, both with each other, and with an explicit call to
the view.

This is ostensibly a regression from 2.10.3. To get there,
we need an implicit search that has to infer `Nothing` in a covariant
position. In 2.10.3, we would just let the `G` out into the wild,
which did the right thing for the wrong reasons.

3 files changed, 100 insertions, 9 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index c8ac3622e2..1a38fcf3a4 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -82,7 +82,7 @@ trait Implicits {
     //         `implicitSearchContext.undetparams`, *not* in `context.undetparams`
     //         Here, we copy them up to parent context (analogously to the way the errors are copied above),
     //         and then filter out any which *were* inferred and are part of the substitutor in the implicit search result.
-    context.undetparams = ((context.undetparams ++ implicitSearchContext.undetparams) filterNot result.subst.from.contains).distinct
+    context.undetparams = ((context.undetparams ++ result.undetparams) filterNot result.subst.from.contains).distinct
 
     if (Statistics.canEnable) Statistics.stopTimer(implicitNanos, start)
     if (Statistics.canEnable) Statistics.stopCounter(rawTypeImpl, rawTypeStart)
@@ -162,8 +162,9 @@ trait Implicits {
    *  @param  tree    The tree representing the implicit
    *  @param  subst   A substituter that represents the undetermined type parameters
    *                  that were instantiated by the winning implicit.
+   *  @param undetparams undeterminted type parameters
    */
-  class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter) {
+  class SearchResult(val tree: Tree, val subst: TreeTypeSubstituter, val undetparams: List[Symbol]) {
     override def toString = "SearchResult(%s, %s)".format(tree,
       if (subst.isEmpty) "" else subst)
 
@@ -173,16 +174,16 @@ trait Implicits {
     final def isSuccess    = !isFailure
   }
 
-  lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) {
+  lazy val SearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
     override def isFailure = true
   }
 
-  lazy val DivergentSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) {
+  lazy val DivergentSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
     override def isFailure   = true
     override def isDivergent = true
   }
 
-  lazy val AmbiguousSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter) {
+  lazy val AmbiguousSearchFailure = new SearchResult(EmptyTree, EmptyTreeTypeSubstituter, Nil) {
     override def isFailure          = true
     override def isAmbiguousFailure = true
   }
@@ -719,7 +720,7 @@ trait Implicits {
               case Some(err) =>
                 fail("typing TypeApply reported errors for the implicit tree: " + err.errMsg)
               case None      =>
-                val result = new SearchResult(unsuppressMacroExpansion(itree3), subst)
+                val result = new SearchResult(unsuppressMacroExpansion(itree3), subst, context.undetparams)
                 if (Statistics.canEnable) Statistics.incCounter(foundImplicits)
                 typingLog("success", s"inferred value of type $ptInstantiated is $result")
                 result
@@ -1126,7 +1127,7 @@ trait Implicits {
           val tree1 = typedPos(pos.focus)(arg)
           context.firstError match {
             case Some(err) => processMacroExpansionError(err.errPos, err.errMsg)
-            case None      => new SearchResult(tree1, EmptyTreeTypeSubstituter)
+            case None      => new SearchResult(tree1, EmptyTreeTypeSubstituter, Nil)
           }
         } catch {
           case ex: TypeError =>
@@ -1196,7 +1197,7 @@ trait Implicits {
       def findSubManifest(tp: Type) = findManifest(tp, if (full) FullManifestClass else OptManifestClass)
       def mot(tp0: Type, from: List[Symbol], to: List[Type]): SearchResult = {
         implicit def wrapResult(tree: Tree): SearchResult =
-          if (tree == EmptyTree) SearchFailure else new SearchResult(tree, if (from.isEmpty) EmptyTreeTypeSubstituter else new TreeTypeSubstituter(from, to))
+          if (tree == EmptyTree) SearchFailure else new SearchResult(tree, if (from.isEmpty) EmptyTreeTypeSubstituter else new TreeTypeSubstituter(from, to), Nil)
 
         val tp1 = tp0.dealias
         tp1 match {
@@ -1284,7 +1285,7 @@ trait Implicits {
     }
 
     def wrapResult(tree: Tree): SearchResult =
-      if (tree == EmptyTree) SearchFailure else new SearchResult(tree, EmptyTreeTypeSubstituter)
+      if (tree == EmptyTree) SearchFailure else new SearchResult(tree, EmptyTreeTypeSubstituter, Nil)
 
     /** Materializes implicits of predefined types (currently, manifests and tags).
      *  Will be replaced by implicit macros once we fix them.
diff --git a/test/files/neg/t8431.check b/test/files/neg/t8431.check
new file mode 100644
index 0000000000..75351a8ae7
--- /dev/null
+++ b/test/files/neg/t8431.check
@@ -0,0 +1,27 @@
+t8431.scala:24: error: type mismatch;
+ found   : CanBuildFrom[Invariant[Nothing]]
+ required: CanBuildFrom[Invariant[G]]
+  s.combined // fail
+  ^
+t8431.scala:24: error: value combined is not a member of Invariant[Nothing]
+  s.combined // fail
+    ^
+t8431.scala:35: error: type mismatch;
+ found   : CanBuildFrom[Invariant[Nothing]]
+ required: CanBuildFrom[Invariant[G]]
+  s.combined // was okay!
+  ^
+t8431.scala:35: error: value combined is not a member of Invariant[Nothing]
+  s.combined // was okay!
+    ^
+t8431.scala:45: error: type mismatch;
+ found   : CanBuildFrom[Invariant[Nothing]]
+ required: CanBuildFrom[Invariant[G]]
+  convert2(s).combined
+          ^
+t8431.scala:48: error: type mismatch;
+ found   : CanBuildFrom[Invariant[Nothing]]
+ required: CanBuildFrom[Invariant[G]]
+  {val c1 = convert2(s); c1.combined}
+                    ^
+6 errors found
diff --git a/test/files/neg/t8431.scala b/test/files/neg/t8431.scala
new file mode 100644
index 0000000000..29b852d0c0
--- /dev/null
+++ b/test/files/neg/t8431.scala
@@ -0,0 +1,63 @@
+trait Covariant[+A]
+trait Invariant[A] extends Covariant[A @annotation.unchecked.uncheckedVariance] 
+ 
+trait Combinable[G] {
+  def combined = 0
+}
+
+trait CanBuildFrom[+C]
+ 
+object C {
+  implicit def convert1[G, TRAVONCE[+e] <: Covariant[e]]
+    (xs: TRAVONCE[G]): Combinable[G] = ???
+ 
+  implicit def convert2[G, SET[e] <: Invariant[e]]
+    (xs: SET[_ <: G])
+    (implicit cbf: CanBuildFrom[SET[G]]): Combinable[G] = ???
+
+  implicit def cbf[A]: CanBuildFrom[Invariant[A]] = ???
+}
+
+class Test1 {
+  import C.{cbf, convert1, convert2}
+  val s: Invariant[Nothing] = ???
+  s.combined // fail
+}
+
+class Test2 {
+  import C.{cbf, convert2, convert1}
+
+  val s: Invariant[Nothing] = ???
+
+  // Non-uniformity with Test1 was due to order of typechecking implicit candidates:
+  // the last candidate typechecked was the only one that could contribute undetermined type parameters
+  // to the enclosing context, due to mutation of `Context#undetparam` in `doTypedApply`.
+  s.combined // was okay!
+}
+
+
+class TestExplicit {
+  import C.{cbf, convert2}
+
+  val s: Invariant[Nothing] = ???
+
+  // Now the implicit Test fail uniformly as per this explicit conversion
+  convert2(s).combined
+
+  // Breaking this expression down makes it work.
+  {val c1 = convert2(s); c1.combined}
+}
+
+// These ones work before and after; infering G=Null doesn't need to contribute an undetermined type param.
+class Test3 {
+   import C.{cbf, convert1, convert2}
+   val s: Invariant[Null] = ???
+   s.combined // okay
+}
+
+class Test4 {
+   import C.{cbf, convert2, convert1}
+
+   val s: Invariant[Null] = ???
+   s.combined // okay
+}