fixed #2316: No longer cache entire SearchResul...

fixed #2316: No longer cache entire SearchResult when looking for implicits in the parts of the expected type. (patch by retronym -- see ticket)

A SearchResult may contain symbols local to the scope of the search that
were used as implicit parameters, so they are not safely cacheable. The
fix for #2101 does not suffice. That patch avoided bound symbols being
duplicated, but the problem is much worse.

The implicits for an expected type depend on more than just that type,
so we cannot cache them using the expected type as a key.

The neg/t2316 test illustrates this: T1 may provide two implicits, one
requires an implicit T2, another an implicit T3. If an implicit T1
is first required when only a T2 is in scope, the SearchResult will
describe the corresponding implicit. Now, if we enter an implicit value
of type T3 into scope, the search should fail (it is ambiguous), but the
cache does not take this new fact into account.

The patch replaces the erroneous aggressive caching with a more
conservative version that only caches ImplicitInfo's.

6 files changed, 99 insertions, 57 deletions

diff --git a/src/compiler/scala/tools/nsc/ast/Trees.scala b/src/compiler/scala/tools/nsc/ast/Trees.scala
index 20464f2468..90af63c267 100644
--- a/src/compiler/scala/tools/nsc/ast/Trees.scala
+++ b/src/compiler/scala/tools/nsc/ast/Trees.scala
@@ -1714,7 +1714,7 @@ trait Trees {
     }
   }
 
-  class TreeTypeSubstituter(val from: List[Symbol], to: List[Type]) extends Traverser {
+  case class TreeTypeSubstituter(val from: List[Symbol], to: List[Type]) extends Traverser {
     val typeSubst = new SubstTypeMap(from, to)
     override def traverse(tree: Tree) {
       if (tree.tpe ne null) tree.tpe = typeSubst(tree.tpe)
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 90af1e479b..2289d12617 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -38,7 +38,6 @@ self: Analyzer =>
   var manifFail = 0L
   var hits = 0
   var misses = 0
-  var uncached = 0
 
   /** Search for an implicit value. See the comment on `result` at the end of class `ImplicitSearch`
    *  for more info how the search is conducted.
@@ -62,7 +61,7 @@ self: Analyzer =>
   }
 
   final val sizeLimit = 50000
-  val implicitsCache = new LinkedHashMap[AnyRef, SearchResult]
+  val implicitsCache = new LinkedHashMap[Type, List[List[ImplicitInfo]]]
 
   def resetImplicits() { implicitsCache.clear() }
 
@@ -577,8 +576,18 @@ self: Analyzer =>
      *  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]] =
-      parts(pt).iterator.map(implicitsOfClass).toList
+    private def implicitsOfExpectedType: List[List[ImplicitInfo]] = implicitsCache get pt match {
+      case Some(implicitInfoss) => hits += 1; implicitInfoss
+      case None                 => {
+        misses += 1
+        val implicitInfoss = parts(pt).iterator.map(implicitsOfClass).toList
+        implicitsCache(pt) = implicitInfoss
+        if (implicitsCache.size >= sizeLimit)
+          implicitsCache -= implicitsCache.keysIterator.next
+        implicitInfoss
+      }
+    }
+
 
     /** The manifest corresponding to type `pt`, provided `pt` is an instance of Manifest.
      */
@@ -674,50 +683,6 @@ self: Analyzer =>
       }
     }
 
-    /** Construct a fresh symbol tree for an implicit parameter
-        because of caching, must clone symbols that represent bound variables,
-        or we will end up with different bound variables that are represented by the same symbol */
-    def freshenFunctionParameters(tree : Tree) : Tree = new Transformer {
-      currentOwner = context.owner
-      override val treeCopy = new LazyTreeCopier
-      override def transform(tr : Tree) = super.transform(tr match {
-        case Function(vparams, body) => {
-          // New tree
-          val sym = tr.symbol cloneSymbol currentOwner
-          val res = tr.duplicate setSymbol sym
-          // New parameter symbols
-          var oldsyms = vparams map (_.symbol)
-          var newsyms = cloneSymbols(oldsyms, sym)
-          // Fix all symbols
-          new TreeSymSubstituter(oldsyms, newsyms) traverse res
-          res
-        }
-        case x => x
-      })
-    } transform tree
-
-    /** Return cached search result if found. Otherwise update cache
-     *  but keep within sizeLimit entries
-     */
-    def cacheResult(key: AnyRef): SearchResult = implicitsCache get key match {
-      case Some(sr: SearchResult) =>
-        hits += 1
-        if (sr == SearchFailure) sr
-        else {
-          val result = new SearchResult(freshenFunctionParameters(sr.tree.duplicate), sr.subst) // #2201: generate fresh symbols for parameters
-          for (t <- result.tree) t.setPos(tree.pos.focus)
-          result
-        }
-      case None =>
-        misses += 1
-        val r = searchImplicit(implicitsOfExpectedType, false)
-        //println("new fact: search implicit of "+key+" = "+r)
-        implicitsCache(key) = r
-        if (implicitsCache.size >= sizeLimit)
-          implicitsCache -= implicitsCache.keysIterator.next
-        r
-    }
-
     /** The result of the implicit search:
      *  First search implicits visible in current context.
      *  If that fails, search implicits in expected type `pt`.
@@ -729,13 +694,8 @@ self: Analyzer =>
       var result = searchImplicit(context.implicitss, true)
       val timer1 = System.nanoTime()
       if (result == SearchFailure) inscopeFail += timer1 - start else inscopeSucceed += timer1 - start
-      if (result == SearchFailure) {
-        result = pt match {
-          case _: UniqueType => cacheResult(pt)
-          case WildcardName(name) => cacheResult(name)
-          case _ => uncached += 1; searchImplicit(implicitsOfExpectedType, false)
-         }
-      }
+      if (result == SearchFailure)
+        result = searchImplicit(implicitsOfExpectedType, false)
 
       val timer2 = System.nanoTime()
       if (result == SearchFailure) oftypeFail += timer2 - timer1 else oftypeSucceed += timer2 - timer1
diff --git a/src/compiler/scala/tools/nsc/util/Statistics.scala b/src/compiler/scala/tools/nsc/util/Statistics.scala
index 6864eb2335..8e4692a800 100644
--- a/src/compiler/scala/tools/nsc/util/Statistics.scala
+++ b/src/compiler/scala/tools/nsc/util/Statistics.scala
@@ -57,7 +57,7 @@ abstract class Statistics {
         inform("    successful manifest: "+showRelTyper(analyzer.manifSucceed))
         inform("        failed manifest: "+showRelTyper(analyzer.manifFail))
         inform("implicit cache hitratio: "+"%2.1f".format(analyzer.hits.toDouble / (analyzer.hits + analyzer.misses) * 100))
-        inform("implicit cache coverage: "+"%2.1f".format((analyzer.hits + analyzer.misses).toDouble / (analyzer.uncached + analyzer.hits + analyzer.misses) * 100))
+        inform("implicit cache coverage: "+"%2.1f".format((analyzer.hits + analyzer.misses).toDouble / (analyzer.hits + analyzer.misses) * 100))
         inform("time spent in failed   : "+showRelTyper(analyzer.failedSilent))
         inform("       failed op=      : "+showRelTyper(analyzer.failedOpEqs))
         inform("       failed apply    : "+showRelTyper(analyzer.failedApplies))
diff --git a/test/files/neg/t2316.check b/test/files/neg/t2316.check
new file mode 100644
index 0000000000..fea1745663
--- /dev/null
+++ b/test/files/neg/t2316.check
@@ -0,0 +1,7 @@
+t2316.scala:28: error: ambiguous implicit values:
+ both method T1FromT3 in object T1 of type (implicit t3: test.T3)test.T1
+ and method T1FromT2 in object T1 of type (implicit t2: test.T2)test.T1
+ match expected type test.T1
+      val t1 = requireT1
+               ^
+one error found
diff --git a/test/files/neg/t2316.scala b/test/files/neg/t2316.scala
new file mode 100644
index 0000000000..ccda9d5aac
--- /dev/null
+++ b/test/files/neg/t2316.scala
@@ -0,0 +1,43 @@
+object test {
+  case class T1(val source: String)
+
+
+  object T1 {
+    implicit def T1FromT2(implicit t2: T2): T1 = T1("implicit def T1FromT2")
+    implicit def T1FromT3(implicit t3: T3): T1 = T1("implicit def T1FromT3")
+  }
+
+  trait T2 {
+  }
+
+  object T2 {
+    implicit val t2: T2 = new T2 {}
+  }
+
+  trait T3
+
+  def requireT1(implicit t1: T1) = t1
+
+  {
+      val t1 = requireT1
+      assert(t1.source == "implicit def T1FromT2")
+  }
+
+  {
+      implicit def t3: T3 = new T3 {}
+      val t1 = requireT1
+      assert(t1.source == "implicit def T1FromT2")
+
+      // Expected a compile error here, but because T1.T1FromT2(T2.t2) was cached as a non-local implicit
+      // expression for type T1, this is not checked!
+      //
+      // (fragment of implicit-cache-error2.scala):26: error: ambiguous implicit values:
+      // both method T1FromT3 in object T1 of type (implicit t3: this.T3)this.T1
+      // and method T1FromT2 in object T1 of type (implicit t2: this.T2)this.T1
+      // match expected type this.T1
+      //    val t1 = requireT1
+      //              ^
+      // one error found
+
+  }
+}
\ No newline at end of file
diff --git a/test/files/run/t2316.scala b/test/files/run/t2316.scala
new file mode 100644
index 0000000000..a3d5bf890b
--- /dev/null
+++ b/test/files/run/t2316.scala
@@ -0,0 +1,32 @@
+case class T1(source: String)
+
+object T1 {
+  implicit def T1FromT2(implicit t2: T2) = new T1(t2.source)
+}
+
+case class T2(source: String)
+
+object A {
+  def requireT1(implicit t1: T1) = t1
+
+  object B1 {
+    implicit val t2_b1 = new T2("from B1")
+    requireT1
+  }
+
+  object B2 {
+    def t1 = {
+      implicit val t2_b2 = new T2("from B2")
+      // Implicits.cacheResult returns T1.T1FromT2(t2_b1) here, which is bogus. Even though T1.T1FromT2 was found
+      // outside of the scope of A.B1, this implicit expression should _not_ be cached, as it includes the bound
+      // variable t2_b1 from this scope.
+      requireT1
+    }
+  }
+}
+
+object Test {
+  def main(args: Array[String]) {
+    assert(A.B2.t1.source == "from B2")
+  }
+}
\ No newline at end of file