diff options
author | Martin Odersky <odersky@gmail.com> | 2013-11-30 13:09:43 +0100 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2013-11-30 13:09:43 +0100 |
commit | 16104754c964b49bf4bd06ea81a00f276eefae0d (patch) | |
tree | e8050d472f2e41751a10b6cae6dce3d47ffd14d7 | |
parent | eb6eb2cded84f0e0240f4b706c1ed41459946db2 (diff) | |
download | dotty-16104754c964b49bf4bd06ea81a00f276eefae0d.tar.gz dotty-16104754c964b49bf4bd06ea81a00f276eefae0d.tar.bz2 dotty-16104754c964b49bf4bd06ea81a00f276eefae0d.zip |
Added divergence check for implicit searches
-rw-r--r-- | src/dotty/tools/dotc/config/ScalaSettings.scala | 1 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Contexts.scala | 7 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/Implicits.scala | 70 |
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]] |