From 4fb19e43f696845a18cbe2a7671654674ffce9b7 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sat, 3 Dec 2016 19:32:09 +0100 Subject: Refactor function operations in Definitions Also: show implicit function types correctly. Also: refine applications of implicit funcitons - don't do it for closure trees - don't do it after typer. --- compiler/src/dotty/tools/dotc/typer/Applications.scala | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/typer/Applications.scala') diff --git a/compiler/src/dotty/tools/dotc/typer/Applications.scala b/compiler/src/dotty/tools/dotc/typer/Applications.scala index 4203ab9b2..469d657a9 100644 --- a/compiler/src/dotty/tools/dotc/typer/Applications.scala +++ b/compiler/src/dotty/tools/dotc/typer/Applications.scala @@ -1294,7 +1294,7 @@ trait Applications extends Compatibility { self: Typer with Dynamic => val alts1 = alts filter pt.isMatchedBy resolveOverloaded(alts1, pt1, targs1) - case defn.FunctionOf(args, resultType) => + case defn.FunctionOf(args, resultType, _) => narrowByTypes(alts, args, resultType) case pt => @@ -1345,7 +1345,7 @@ trait Applications extends Compatibility { self: Typer with Dynamic => // (p_1_1, ..., p_m_1) => r_1 // ... // (p_1_n, ..., p_m_n) => r_n - val decomposedFormalsForArg: List[Option[(List[Type], Type)]] = + val decomposedFormalsForArg: List[Option[(List[Type], Type, Boolean)]] = formalsForArg.map(defn.FunctionOf.unapply) if (decomposedFormalsForArg.forall(_.isDefined)) { val formalParamTypessForArg: List[List[Type]] = -- cgit v1.2.3 From 0336785a2280a4a1e51e739e9aac3d5015f7c16f Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 5 Dec 2016 09:52:28 +0100 Subject: Take nesting into account when ranking implicits This will need a spec change. It's necessary in order not to confuse synthetic implicits with each other or with explicit ones in the environment. --- .../src/dotty/tools/dotc/typer/Applications.scala | 20 +++++-- .../src/dotty/tools/dotc/typer/Implicits.scala | 64 ++++++++++++++-------- .../src/dotty/tools/dotc/typer/ImportInfo.scala | 2 +- compiler/src/dotty/tools/dotc/typer/Typer.scala | 4 +- 4 files changed, 59 insertions(+), 31 deletions(-) (limited to 'compiler/src/dotty/tools/dotc/typer/Applications.scala') diff --git a/compiler/src/dotty/tools/dotc/typer/Applications.scala b/compiler/src/dotty/tools/dotc/typer/Applications.scala index 469d657a9..1cb656ca3 100644 --- a/compiler/src/dotty/tools/dotc/typer/Applications.scala +++ b/compiler/src/dotty/tools/dotc/typer/Applications.scala @@ -975,9 +975,21 @@ trait Applications extends Compatibility { self: Typer with Dynamic => } /** In a set of overloaded applicable alternatives, is `alt1` at least as good as - * `alt2`? `alt1` and `alt2` are non-overloaded references. + * `alt2`? Also used for implicits disambiguation. + * + * @param alt1, alt2 Non-overloaded references indicating the two choices + * @param level1, level2 If alternatives come from a comparison of two contextual + * implicit candidates, the nesting levels of the candidates. + * In all other cases the nesting levels are both 0. + * + * An alternative A1 is "as good as" an alternative A2 if it wins or draws in a tournament + * that awards one point for each of the following + * + * - A1 is nested more deeply than A2 + * - The nesting levels of A1 and A2 are the same, and A1's owner derives from A2's owner + * - A1's type is more specific than A2's type. */ - def isAsGood(alt1: TermRef, alt2: TermRef)(implicit ctx: Context): Boolean = track("isAsGood") { ctx.traceIndented(i"isAsGood($alt1, $alt2)", overload) { + def isAsGood(alt1: TermRef, alt2: TermRef, nesting1: Int = 0, nesting2: Int = 0)(implicit ctx: Context): Boolean = track("isAsGood") { ctx.traceIndented(i"isAsGood($alt1, $alt2)", overload) { assert(alt1 ne alt2) @@ -1092,9 +1104,9 @@ trait Applications extends Compatibility { self: Typer with Dynamic => val tp1 = stripImplicit(alt1.widen) val tp2 = stripImplicit(alt2.widen) - def winsOwner1 = isDerived(owner1, owner2) + def winsOwner1 = nesting1 > nesting2 || isDerived(owner1, owner2) def winsType1 = isAsSpecific(alt1, tp1, alt2, tp2) - def winsOwner2 = isDerived(owner2, owner1) + def winsOwner2 = nesting2 > nesting1 || isDerived(owner2, owner1) def winsType2 = isAsSpecific(alt2, tp2, alt1, tp1) overload.println(i"isAsGood($alt1, $alt2)? $tp1 $tp2 $winsOwner1 $winsType1 $winsOwner2 $winsType2") diff --git a/compiler/src/dotty/tools/dotc/typer/Implicits.scala b/compiler/src/dotty/tools/dotc/typer/Implicits.scala index 1a9a8f64c..79881dc5b 100644 --- a/compiler/src/dotty/tools/dotc/typer/Implicits.scala +++ b/compiler/src/dotty/tools/dotc/typer/Implicits.scala @@ -35,6 +35,9 @@ import collection.mutable /** Implicit resolution */ object Implicits { + /** An eligible implicit candidate, consisting of an implicit reference and a nesting level */ + case class Candidate(ref: TermRef, level: Int) + /** A common base class of contextual implicits and of-type implicits which * represents a set of implicit references. */ @@ -42,11 +45,14 @@ object Implicits { implicit val ctx: Context = if (initctx == NoContext) initctx else initctx retractMode Mode.ImplicitsEnabled + /** The nesting level of this context. Non-zero only in ContextialImplicits */ + def level: Int = 0 + /** The implicit references */ def refs: List[TermRef] /** Return those references in `refs` that are compatible with type `pt`. */ - protected def filterMatching(pt: Type)(implicit ctx: Context): List[TermRef] = track("filterMatching") { + protected def filterMatching(pt: Type)(implicit ctx: Context): List[Candidate] = track("filterMatching") { def refMatches(ref: TermRef)(implicit ctx: Context) = /*ctx.traceIndented(i"refMatches $ref $pt")*/ { @@ -97,8 +103,9 @@ object Implicits { } } - if (refs.isEmpty) refs - else refs filter (refMatches(_)(ctx.fresh.addMode(Mode.TypevarsMissContext).setExploreTyperState)) // create a defensive copy of ctx to avoid constraint pollution + if (refs.isEmpty) Nil + else refs.filter(refMatches(_)(ctx.fresh.addMode(Mode.TypevarsMissContext).setExploreTyperState)) // create a defensive copy of ctx to avoid constraint pollution + .map(Candidate(_, level)) } } @@ -114,8 +121,8 @@ object Implicits { buf.toList } - /** The implicit references that are eligible for expected type `tp` */ - lazy val eligible: List[TermRef] = + /** The candidates that are eligible for expected type `tp` */ + lazy val eligible: List[Candidate] = /*>|>*/ track("eligible in tpe") /*<|<*/ { /*>|>*/ ctx.traceIndented(i"eligible($tp), companions = ${companionRefs.toList}%, %", implicitsDetailed, show = true) /*<|<*/ { if (refs.nonEmpty && monitored) record(s"check eligible refs in tpe", refs.length) @@ -135,10 +142,15 @@ object Implicits { * @param outerCtx the next outer context that makes visible further implicits */ class ContextualImplicits(val refs: List[TermRef], val outerImplicits: ContextualImplicits)(initctx: Context) extends ImplicitRefs(initctx) { - private val eligibleCache = new mutable.AnyRefMap[Type, List[TermRef]] + private val eligibleCache = new mutable.AnyRefMap[Type, List[Candidate]] + + override val level: Int = + if (outerImplicits == null) 1 + else if (ctx.scope eq outerImplicits.ctx.scope) outerImplicits.level + else outerImplicits.level + 1 /** The implicit references that are eligible for type `tp`. */ - def eligible(tp: Type): List[TermRef] = /*>|>*/ track(s"eligible in ctx") /*<|<*/ { + def eligible(tp: Type): List[Candidate] = /*>|>*/ track(s"eligible in ctx") /*<|<*/ { if (tp.hash == NotCached) computeEligible(tp) else eligibleCache get tp match { case Some(eligibles) => @@ -162,13 +174,13 @@ object Implicits { } } - private def computeEligible(tp: Type): List[TermRef] = /*>|>*/ ctx.traceIndented(i"computeEligible $tp in $refs%, %", implicitsDetailed) /*<|<*/ { + private def computeEligible(tp: Type): List[Candidate] = /*>|>*/ ctx.traceIndented(i"computeEligible $tp in $refs%, %", implicitsDetailed) /*<|<*/ { if (monitored) record(s"check eligible refs in ctx", refs.length) val ownEligible = filterMatching(tp) if (outerImplicits == NoContext.implicits) ownEligible else ownEligible ::: { - val shadowed = (ownEligible map (_.name)).toSet - outerImplicits.eligible(tp) filterNot (ref => shadowed contains ref.name) + val shadowed = ownEligible.map(_.ref.name).toSet + outerImplicits.eligible(tp).filterNot(cand => shadowed.contains(cand.ref.name)) } } @@ -198,7 +210,7 @@ object Implicits { * @param tree The typed tree that needs to be inserted * @param ctx The context after the implicit search */ - case class SearchSuccess(tree: tpd.Tree, ref: TermRef, tstate: TyperState) extends SearchResult { + case class SearchSuccess(tree: tpd.Tree, ref: TermRef, level: Int, tstate: TyperState) extends SearchResult { override def toString = s"SearchSuccess($tree, $ref)" } @@ -478,7 +490,7 @@ trait Implicits { self: Typer => */ def inferImplicitArg(formal: Type, error: (String => String) => Unit, pos: Position)(implicit ctx: Context): Tree = inferImplicit(formal, EmptyTree, pos) match { - case SearchSuccess(arg, _, _) => + case SearchSuccess(arg, _, _, _) => arg case ambi: AmbiguousImplicits => error(where => s"ambiguous implicits: ${ambi.explanation} of $where") @@ -621,12 +633,13 @@ trait Implicits { self: Typer => protected def failedSearch: SearchFailure = NoImplicitMatches /** Search a list of eligible implicit references */ - def searchImplicits(eligible: List[TermRef], contextual: Boolean): SearchResult = { + def searchImplicits(eligible: List[Candidate], contextual: Boolean): SearchResult = { val constr = ctx.typerState.constraint /** Try to typecheck an implicit reference */ - def typedImplicit(ref: TermRef)(implicit ctx: Context): SearchResult = track("typedImplicit") { ctx.traceIndented(i"typed implicit $ref, pt = $pt, implicitsEnabled == ${ctx.mode is ImplicitsEnabled}", implicits, show = true) { + def typedImplicit(cand: Candidate)(implicit ctx: Context): SearchResult = track("typedImplicit") { ctx.traceIndented(i"typed implicit ${cand.ref}, pt = $pt, implicitsEnabled == ${ctx.mode is ImplicitsEnabled}", implicits, show = true) { assert(constr eq ctx.typerState.constraint) + val ref = cand.ref var generated: Tree = tpd.ref(ref).withPos(pos) if (!argument.isEmpty) generated = typedUnadapted( @@ -667,7 +680,7 @@ trait Implicits { self: Typer => if fn.symbol == defn.Predef_eqAny && !validEqAnyArgs(arg1.tpe, arg2.tpe) => nonMatchingImplicit(ref, Nil) case _ => - SearchSuccess(generated1, ref, ctx.typerState) + SearchSuccess(generated1, ref, cand.level, ctx.typerState) } }} @@ -676,19 +689,20 @@ trait Implicits { self: Typer => * @param pending The list of implicit references that remain to be investigated * @param acc An accumulator of successful matches found so far. */ - def rankImplicits(pending: List[TermRef], acc: List[SearchSuccess]): List[SearchSuccess] = pending match { - case ref :: pending1 => + def rankImplicits(pending: List[Candidate], acc: List[SearchSuccess]): List[SearchSuccess] = pending match { + case cand :: pending1 => val history = ctx.searchHistory nest wildProto val result = - if (history eq ctx.searchHistory) divergingImplicit(ref) - else typedImplicit(ref)(nestedContext.setNewTyperState.setSearchHistory(history)) + if (history eq ctx.searchHistory) divergingImplicit(cand.ref) + else typedImplicit(cand)(nestedContext.setNewTyperState.setSearchHistory(history)) result match { case fail: SearchFailure => rankImplicits(pending1, acc) case best: SearchSuccess => if (ctx.mode.is(Mode.ImplicitExploration)) best :: Nil else { - val newPending = pending1 filter (isAsGood(_, best.ref)(nestedContext.setExploreTyperState)) + val newPending = pending1.filter(cand1 => + isAsGood(cand1.ref, best.ref, cand1.level, best.level)(nestedContext.setExploreTyperState)) rankImplicits(newPending, best :: acc) } } @@ -717,7 +731,7 @@ trait Implicits { self: Typer => /** Convert a (possibly empty) list of search successes into a single search result */ def condense(hits: List[SearchSuccess]): SearchResult = hits match { case best :: alts => - alts find (alt => isAsGood(alt.ref, best.ref)(ctx.fresh.setExploreTyperState)) match { + alts find (alt => isAsGood(alt.ref, best.ref, alt.level, best.level)(ctx.fresh.setExploreTyperState)) match { case Some(alt) => /* !!! DEBUG println(i"ambiguous refs: ${hits map (_.ref) map (_.show) mkString ", "}") @@ -735,16 +749,18 @@ trait Implicits { self: Typer => failedSearch } + def ranking(cand: Candidate) = -ctx.runInfo.useCount(cand.ref) + /** Sort list of implicit references according to their popularity * (# of times each was picked in current run). */ - def sort(eligible: List[TermRef]) = eligible match { + def sort(eligible: List[Candidate]) = eligible match { case Nil => eligible case e1 :: Nil => eligible case e1 :: e2 :: Nil => - if (ctx.runInfo.useCount(e1) < ctx.runInfo.useCount(e2)) e2 :: e1 :: Nil + if (ranking(e2) < ranking(e1)) e2 :: e1 :: Nil else eligible - case _ => eligible.sortBy(-ctx.runInfo.useCount(_)) + case _ => eligible.sortBy(ranking) } condense(rankImplicits(sort(eligible), Nil)) diff --git a/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala b/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala index b4ec3390e..e44343e70 100644 --- a/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala +++ b/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala @@ -98,7 +98,7 @@ class ImportInfo(symf: => Symbol, val selectors: List[untpd.Tree], val isRootImp * * TODO: Once we have fully bootstrapped, I would prefer if we expressed * unimport with an `override` modifier, and generalized it to all imports. - * I believe this would be more transparent than the curren set of conditions. E.g. + * I believe this would be more transparent than the current set of conditions. E.g. * * override import Predef.{any2stringAdd => _, StringAdd => _, _} // disables String + * override import java.lang.{} // disables all imports diff --git a/compiler/src/dotty/tools/dotc/typer/Typer.scala b/compiler/src/dotty/tools/dotc/typer/Typer.scala index e016ba3a6..1967275e9 100644 --- a/compiler/src/dotty/tools/dotc/typer/Typer.scala +++ b/compiler/src/dotty/tools/dotc/typer/Typer.scala @@ -519,7 +519,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit case tref: TypeRef if !tref.symbol.isClass && !ctx.isAfterTyper => inferImplicit(defn.ClassTagType.appliedTo(tref), EmptyTree, tpt1.pos)(ctx.retractMode(Mode.Pattern)) match { - case SearchSuccess(arg, _, _) => + case SearchSuccess(arg, _, _, _) => return typed(untpd.Apply(untpd.TypedSplice(arg), tree.expr), pt) case _ => } @@ -1960,7 +1960,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit } // try an implicit conversion inferView(tree, pt) match { - case SearchSuccess(inferred, _, _) => + case SearchSuccess(inferred, _, _, _) => adapt(inferred, pt) case failure: SearchFailure => if (pt.isInstanceOf[ProtoType] && !failure.isInstanceOf[AmbiguousImplicits]) tree -- cgit v1.2.3