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.

3 files changed, 17 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))