Added divergence check for implicit searches

3 files changed, 77 insertions, 1 deletions

diff --git a/src/dotty/tools/dotc/config/ScalaSettings.scala b/src/dotty/tools/dotc/config/ScalaSettings.scala
index ef926c664..aaf3b8385 100644
--- a/src/dotty/tools/dotc/config/ScalaSettings.scala
+++ b/src/dotty/tools/dotc/config/ScalaSettings.scala
@@ -60,6 +60,7 @@ class ScalaSettings extends Settings.SettingGroup {
   val noForwarders = BooleanSetting("-Xno-forwarders", "Do not generate static forwarders in mirror classes.")
   val genPhaseGraph = StringSetting("-Xgenerate-phase-graph", "file", "Generate the phase graphs (outputs .dot files) to fileX.dot.", "")
   val XlogImplicits = BooleanSetting("-Xlog-implicits", "Show more detail on why some implicits are not applicable.")
+  val XminImplicitSearchDepth = IntSetting("-Xmin-implicit-search-depth", "Set number of levels of implicit searches undertaken before checking for divergence.", 5)
   val logImplicitConv = BooleanSetting("-Xlog-implicit-conversions", "Print a message whenever an implicit conversion is inserted.")
   val logReflectiveCalls = BooleanSetting("-Xlog-reflective-calls", "Print a message when a reflective method call is generated")
   val logFreeTerms = BooleanSetting("-Xlog-free-terms", "Print a message when reification creates a free term.")
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index d06670b94..ac0e243ff 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -169,6 +169,11 @@ object Contexts {
       implicitsCache
     }
 
+    /** The history of implicit searches that are currently active */
+    private var _searchHistory: SearchHistory = null
+    protected def searchHistory_= (searchHistory: SearchHistory) = _searchHistory = searchHistory
+    def searchHistory: SearchHistory = _searchHistory
+
   /** If -Ydebug is on, the top of the stack trace where this context
      *  was created, otherwise `null`.
      */
@@ -302,6 +307,7 @@ object Contexts {
     def withRunInfo(runInfo: RunInfo): this.type = { this.runInfo = runInfo; this }
     def withDiagnostics(diagnostics: Option[StringBuilder]): this.type = { this.diagnostics = diagnostics; this }
     def withTypeComparerFn(tcfn: Context => TypeComparer): this.type = { this.typeComparer = tcfn(this); this }
+    def withSearchHistory(searchHistory: SearchHistory): this.type = { this.searchHistory = searchHistory; this }
     def withMoreProperties(moreProperties: Map[String, Any]): this.type = { this.moreProperties = moreProperties; this }
 
     def withProperty(prop: (String, Any)): this.type = withMoreProperties(moreProperties + prop)
@@ -330,6 +336,7 @@ object Contexts {
     diagnostics = None
     moreProperties = Map.empty
     typeComparer = new TypeComparer(this)
+    searchHistory = new SearchHistory(0, Map())
   }
 
   object NoContext extends Context {
diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala
index 5f9f49453..48b8bafe0 100644
--- a/src/dotty/tools/dotc/typer/Implicits.scala
+++ b/src/dotty/tools/dotc/typer/Implicits.scala
@@ -149,6 +149,11 @@ object Implicits {
       i"${err.refStr(ref)} does $qualify but is shadowed by ${err.refStr(shadowing)}"
   }
 
+  class DivergingImplicit(ref: TermRef, val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
+    def explanation(implicit ctx: Context): String =
+      i"${err.refStr(ref)} produces a diverging implicit search when trying to $qualify"
+  }
+
   class FailedImplicit(failures: List[ExplainedSearchFailure], val pt: Type, val argument: tpd.Tree) extends ExplainedSearchFailure {
     def explanation(implicit ctx: Context): String =
       if (failures.isEmpty) s"  No implicit candidates were found that $qualify"
@@ -293,6 +298,7 @@ trait Implicits { self: Typer =>
 
     /** Search failures; overridden in ExplainedImplicitSearch */
     protected def nonMatchingImplicit(ref: TermRef): SearchFailure = NoImplicitMatches
+    protected def divergingImplicit(ref: TermRef): SearchFailure = NoImplicitMatches
     protected def shadowedImplicit(ref: TermRef, shadowing: Type): SearchFailure = NoImplicitMatches
     protected def failedSearch: SearchFailure = NoImplicitMatches
 
@@ -321,7 +327,11 @@ trait Implicits { self: Typer =>
        */
       def rankImplicits(pending: List[TermRef], acc: List[SearchSuccess]): List[SearchSuccess] = pending match {
         case ref :: pending1 =>
-          typedImplicit(ref)(nestedContext.withNewTyperState) match {
+          val history = ctx.searchHistory nest wildProto
+          val result =
+            if (history eq ctx.searchHistory) divergingImplicit(ref)
+            else typedImplicit(ref)(nestedContext.withNewTyperState.withSearchHistory(history))
+          result match {
             case fail: SearchFailure =>
               rankImplicits(pending1, acc)
             case best: SearchSuccess =>
@@ -387,6 +397,8 @@ trait Implicits { self: Typer =>
     def failures = myFailures.toList
     override def nonMatchingImplicit(ref: TermRef) =
       record(new NonMatchingImplicit(ref, pt, argument))
+    override def divergingImplicit(ref: TermRef) =
+      record(new DivergingImplicit(ref, pt, argument))
     override def shadowedImplicit(ref: TermRef, shadowing: Type): SearchFailure =
       record(new ShadowedImplicit(ref, shadowing, pt, argument))
     override def failedSearch: SearchFailure = {
@@ -397,6 +409,62 @@ trait Implicits { self: Typer =>
   }
 }
 
+/** Records the history of currently open implicit searches
+ *  @param  searchDepth   The number of open searches.
+ *  @param  seen          A map that records for each class symbol of a type
+ *                        that's currently searched for the complexity of the
+ *                        type that is searched for (wrt `typeSize`). The map
+ *                        is populated only once `searchDepth` is greater than
+ *                        the threshold given in the `XminImplicitSearchDepth` setting.
+ */
+class SearchHistory(val searchDepth: Int, val seen: Map[ClassSymbol, Int]) {
+
+  /** The number of RefinementTypes in this type, after all aliases are expanded */
+  private def typeSize(tp: Type)(implicit ctx: Context): Int = {
+    val accu = new TypeAccumulator[Int] {
+      def apply(n: Int, tp: Type): Int = tp match {
+        case tp: RefinedType =>
+          foldOver(n + 1, tp)
+        case tp: TypeRef if tp.symbol.isAliasType =>
+          apply(n, tp.info.bounds.hi)
+        case _ =>
+          foldOver(n, tp)
+      }
+    }
+    accu.apply(0, tp)
+  }
+
+  /** Check for possible divergence. If one is detected return the current search history
+   *  (this will be used as a criterion to abandon the implicit search in rankImplicits).
+   *  If no divergence is detected, produce a new search history nested in the current one
+   *  which records that we are now also looking for type `proto`.
+   *
+   *  As long as `searchDepth` is lower than the `XminImplicitSearchDepth` value
+   *  in settings, a new history is always produced, so the implicit search is always
+   *  undertaken. If `searchDepth` matches or exceeds the `XminImplicitSearchDepth` value,
+   *  we test that the new search is for a class that is either not yet in the set of
+   *  `seen` classes, or the complexity of the type `proto` being searched for is strictly
+   *  lower than the complexity of the type that was previously encountered and that had
+   *  the same class symbol as `proto`. A possible divergence is detected if that test fails.
+   */
+  def nest(proto: Type)(implicit ctx: Context): SearchHistory = {
+    if (searchDepth < ctx.settings.XminImplicitSearchDepth.value)
+      new SearchHistory(searchDepth + 1, seen)
+    else {
+      val size = typeSize(proto)
+      def updateMap(csyms: List[ClassSymbol], seen: Map[ClassSymbol, Int]): SearchHistory = csyms match {
+        case csym :: csyms1 =>
+          seen get csym match {
+            case Some(prevSize) if size >= prevSize => this
+            case _ => updateMap(csyms1, seen.updated(csym, size))
+          }
+        case _ => new SearchHistory(searchDepth + 1, seen)
+      }
+      updateMap(proto.classSymbols, seen)
+    }
+  }
+}
+
 /** A set of term references where equality is =:= */
 class TermRefSet(implicit ctx: Context) extends mutable.Traversable[TermRef] {
   private val elems = new mutable.LinkedHashMap[TermSymbol, List[Type]]