From 2b069593c84194e21f88b8552ad12917decc14d5 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 24 Nov 2011 02:01:00 +0000 Subject: Minor restructuring in Implicits. Another case where I tried to get into the performance party but ended up playing dungeons and dragons next door. However I did come away with an attractive tablecloth, which I draped over Implicits.scala before waving my magic wand. TRANSLATION: it's probably not faster but it's still better. --- .../scala/reflect/internal/Definitions.scala | 9 +- src/compiler/scala/reflect/internal/Symbols.scala | 3 + src/compiler/scala/reflect/internal/Types.scala | 12 +- .../scala/tools/nsc/typechecker/Implicits.scala | 191 +++++++++++++++------ .../scala/tools/nsc/typechecker/Infer.scala | 136 --------------- 5 files changed, 154 insertions(+), 197 deletions(-) diff --git a/src/compiler/scala/reflect/internal/Definitions.scala b/src/compiler/scala/reflect/internal/Definitions.scala index 5802174a5b..092c478bef 100644 --- a/src/compiler/scala/reflect/internal/Definitions.scala +++ b/src/compiler/scala/reflect/internal/Definitions.scala @@ -72,10 +72,11 @@ trait Definitions extends reflect.api.StandardDefinitions { clazz } - def isNumericSubClass(sub: Symbol, sup: Symbol) = { - val cmp = for (w1 <- numericWeight get sub ; w2 <- numericWeight get sup) yield w2 % w1 - cmp exists (_ == 0) - } + def isNumericSubClass(sub: Symbol, sup: Symbol) = ( + (numericWeight contains sub) + && (numericWeight contains sup) + && (numericWeight(sup) % numericWeight(sub) == 0) + ) /** Is symbol a numeric value class? */ def isNumericValueClass(sym: Symbol): Boolean = diff --git a/src/compiler/scala/reflect/internal/Symbols.scala b/src/compiler/scala/reflect/internal/Symbols.scala index 1b1d26d038..65b60bfa39 100644 --- a/src/compiler/scala/reflect/internal/Symbols.scala +++ b/src/compiler/scala/reflect/internal/Symbols.scala @@ -1250,6 +1250,9 @@ trait Symbols extends api.Symbols { self: SymbolTable => final def isNumericSubClass(that: Symbol): Boolean = definitions.isNumericSubClass(this, that) + final def isWeakSubClass(that: Symbol) = + isSubClass(that) || isNumericSubClass(that) + // ------ overloaded alternatives ------------------------------------------------------ def alternatives: List[Symbol] = diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala index 0f8d28ff03..a69db8e0f4 100644 --- a/src/compiler/scala/reflect/internal/Types.scala +++ b/src/compiler/scala/reflect/internal/Types.scala @@ -5559,9 +5559,15 @@ A type's typeSymbol should never be inspected directly. isSubType(tp1, tp2) } - def isNumericSubType(tp1: Type, tp2: Type) = - isNumericValueType(tp1) && isNumericValueType(tp2) && - isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol) + /** The isNumericValueType tests appear redundant, but without them + * test/continuations-neg/function3.scala goes into an infinite loop. + * (Even if the calls are to typeSymbolDirect.) + */ + def isNumericSubType(tp1: Type, tp2: Type) = ( + isNumericValueType(tp1) + && isNumericValueType(tp2) + && isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol) + ) private val lubResults = new mutable.HashMap[(Int, List[Type]), Type] private val glbResults = new mutable.HashMap[(Int, List[Type]), Type] diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index a355085246..08dd44dcf4 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -93,6 +93,24 @@ trait Implicits { private val ManifestSymbols = Set(PartialManifestClass, FullManifestClass, OptManifestClass) + /** Map all type params in given list to WildcardType + * @param tparams The list of type parameters to map + * @param tp The type in which to do the mapping + */ + private def tparamsToWildcards(tparams: List[Symbol], tp: Type) = + if (tparams.isEmpty) tp + else tp.instantiateTypeParams(tparams, tparams map (_ => WildcardType)) + + /* Map a polytype to one in which all type parameters and argument-dependent types are replaced by wildcards. + * Consider `implicit def b(implicit x: A): x.T = error("")`. We need to approximate DebruijnIndex types + * when checking whether `b` is a valid implicit, as we haven't even searched a value for the implicit arg `x`, + * so we have to approximate (otherwise it is excluded a priori). + */ + private def depoly(tp: Type): Type = tp match { + case PolyType(tparams, restpe) => tparamsToWildcards(tparams, ApproximateDependentMap(restpe)) + case _ => ApproximateDependentMap(tp) + } + /** The result of an implicit search * @param tree The tree representing the implicit * @param subst A substituter that represents the undetermined type parameters @@ -119,6 +137,10 @@ trait Implicits { tpeCache } + def isCyclicOrErroneous = + try containsError(tpe) + catch { case _: CyclicReference => true } + var useCountArg: Int = 0 var useCountView: Int = 0 @@ -135,9 +157,15 @@ trait Implicits { tp.isError } - def isCyclicOrErroneous = - try containsError(tpe) - catch { case _: CyclicReference => true } + /** Todo reconcile with definition of stability given in Types.scala */ + private def isStable(tp: Type): Boolean = tp match { + case TypeRef(pre, sym, _) => + sym.isPackageClass || + sym.isModuleClass && isStable(pre) /*|| + sym.isAliasType && isStable(tp.normalize)*/ + case _ => tp.isStable + } + def isStablePrefix = isStable(pre) override def equals(other: Any) = other match { case that: ImplicitInfo => @@ -225,8 +253,7 @@ trait Implicits { * @param isView We are looking for a view * @param context0 The context used for the implicit search */ - class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context) - extends Typer(context0) { + class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context) extends Typer(context0) { printTyping( ptBlock("new ImplicitSearch", "tree" -> tree, @@ -256,23 +283,8 @@ trait Implicits { } else isStrictlyMoreSpecific(info1.tpe, info2.tpe, info1.sym, info2.sym) } } - - /** Map all type params in given list to WildcardType - * @param tp The type in which to do the mapping - * @param tparams The list of type parameters to map - */ - private def tparamsToWildcards(tp: Type, tparams: List[Symbol]) = - tp.instantiateTypeParams(tparams, tparams map (t => WildcardType)) - - /* Map a polytype to one in which all type parameters and argument-dependent types are replaced by wildcards. - * Consider `implicit def b(implicit x: A): x.T = error("")`. We need to approximate DebruijnIndex types - * when checking whether `b` is a valid implicit, as we haven't even searched a value for the implicit arg `x`, - * so we have to approximate (otherwise it is excluded a priori). - */ - private def depoly(tp: Type): Type = tp match { - case PolyType(tparams, restpe) => tparamsToWildcards(ApproximateDependentMap(restpe), tparams) - case _ => ApproximateDependentMap(tp) - } + def isPlausiblyCompatible(tp: Type, pt: Type) = checkCompatibility(fast = true, tp, pt) + def normSubType(tp: Type, pt: Type) = checkCompatibility(fast = false, tp, pt) /** Does type `dtor` dominate type `dted`? * This is the case if the stripped cores `dtor1` and `dted1` of both types are @@ -370,6 +382,8 @@ trait Implicits { /** The type parameters to instantiate */ val undetParams = if (isView) List() else context.outer.undetparams + + /** The expected type with all undetermined type parameters replaced with wildcards. */ def approximate(tp: Type) = deriveTypeWithWildcards(undetParams)(tp) val wildPt = approximate(pt) @@ -409,15 +423,6 @@ trait Implicits { } } - /** Todo reconcile with definition of stability given in Types.scala */ - private def isStable(tp: Type): Boolean = tp match { - case TypeRef(pre, sym, _) => - sym.isPackageClass || - sym.isModuleClass && isStable(pre) /*|| - sym.isAliasType && isStable(tp.normalize)*/ - case _ => tp.isStable - } - /** Does type `tp` match expected type `pt` * This is the case if either `pt` is a unary function type with a * HasMethodMatching type as result, and `tp` is a unary function @@ -426,7 +431,7 @@ trait Implicits { * or otherwise if `tp` is compatible with `pt`. * This method is performance critical: 5-8% of typechecking time. */ - private def matchesPt(tp: Type, pt: Type, undet: List[Symbol]) = { + private def matchesPt(tp: Type, pt: Type, undet: List[Symbol]): Boolean = { val start = startTimer(matchesPtNanos) val result = normSubType(tp, pt) || isView && { pt match { @@ -439,6 +444,9 @@ trait Implicits { stopTimer(matchesPtNanos, start) result } + private def matchesPt(info: ImplicitInfo): Boolean = ( + info.isStablePrefix && matchesPt(depoly(info.tpe), wildPt, Nil) + ) private def matchesPtView(tp: Type, ptarg: Type, ptres: Type, undet: List[Symbol]): Boolean = tp match { case MethodType(p :: _, restpe) if p.isImplicit => matchesPtView(restpe, ptarg, ptres, undet) @@ -459,25 +467,93 @@ trait Implicits { } } + /** Capturing the overlap between isPlausiblyCompatible and normSubType. + * This is a faithful translation of the code which was there, but it + * seems likely the methods are intended to be even more similar than + * they are: perhaps someone more familiar with the intentional distinctions + * can examine the now much smaller concrete implementations below. + */ + private def checkCompatibility(fast: Boolean, tp0: Type, pt0: Type): Boolean = { + @tailrec def loop(tp: Type, pt: Type): Boolean = tp match { + case mt @ MethodType(params, restpe) => + if (mt.isImplicit) + loop(restpe, pt) + else pt match { + case tr @ TypeRef(pre, sym, args) => + if (sym.isAliasType) loop(tp, pt.normalize) + else if (sym.isAbstractType) loop(tp, pt.bounds.lo) + else { + val len = args.length - 1 + hasLength(params, len) && + sym == FunctionClass(len) && { + var ps = params + var as = args + if (fast) { + while (ps.nonEmpty && as.nonEmpty) { + if (!isPlausiblySubType(as.head, ps.head.tpe)) + return false + ps = ps.tail + as = as.tail + } + } else { + while (ps.nonEmpty && as.nonEmpty) { + if (!(as.head <:< ps.head.tpe)) + return false + ps = ps.tail + as = as.tail + } + } + ps.isEmpty && as.nonEmpty && { + val lastArg = as.head + as.tail.isEmpty && loop(restpe, lastArg) + } + } + } + + case _ => if (fast) false else tp <:< pt + } + case NullaryMethodType(restpe) => loop(restpe, pt) + case PolyType(_, restpe) => loop(restpe, pt) + case ExistentialType(_, qtpe) => if (fast) loop(qtpe, pt) else normalize(tp) <:< pt // is !fast case needed?? + case _ => if (fast) isPlausiblySubType(tp, pt) else tp <:< pt + } + loop(tp0, pt0) + } + + /** This expresses more cleanly in the negative: there's a linear path + * to a final true or false. + */ + private def isPlausiblySubType(tp1: Type, tp2: Type) = !isImpossibleSubType(tp1, tp2) + private def isImpossibleSubType(tp1: Type, tp2: Type) = tp1.normalize.widen match { + case tr1 @ TypeRef(_, sym1, _) => + // We can only rule out a subtype relationship if the left hand + // side is a class, else we may not know enough. + sym1.isClass && (tp2.normalize.widen match { + case TypeRef(_, sym2, _) => + sym2.isClass && !(sym1 isWeakSubClass sym2) + case RefinedType(parents, decls) => + decls.nonEmpty && + tr1.member(decls.head.name) == NoSymbol + case _ => false + }) + case _ => false + } + private def typedImplicit0(info: ImplicitInfo, ptChecked: Boolean): SearchResult = { incCounter(plausiblyCompatibleImplicits) printTyping( ptBlock("typedImplicit0", "info.name" -> info.name, - "info.tpe" -> depoly(info.tpe), "ptChecked" -> ptChecked, "pt" -> wildPt, "orig" -> ptBlock("info", - "matchesPt" -> matchesPt(depoly(info.tpe), wildPt, Nil), "undetParams" -> undetParams, - "isPlausiblyCompatible" -> isPlausiblyCompatible(info.tpe, wildPt), - "info.pre" -> info.pre, - "isStable" -> isStable(info.pre) + "info.pre" -> info.pre ).replaceAll("\\n", "\n ") ) ) - if (ptChecked || matchesPt(depoly(info.tpe), wildPt, Nil) && isStable(info.pre)) + if (ptChecked || matchesPt(info)) typedImplicit1(info) else SearchFailure @@ -610,14 +686,6 @@ trait Implicits { } } - /** Is `sym` the standard conforms method in Predef? - * Note: DON't replace this by sym == Predef_conforms, as Predef_conforms is a `def` - * which does a member lookup (it can't be a lazy val because we might reload Predef - * during resident compilations). - */ - private def isConformsMethod(sym: Symbol) = - sym.name == nme.conforms && sym.owner == PredefModule.moduleClass - /** Should implicit definition symbol `sym` be considered for applicability testing? * This is the case if one of the following holds: * - the symbol's type is initialized @@ -666,17 +734,23 @@ trait Implicits { */ class ImplicitComputation(iss: Infoss, shadowed: util.HashSet[Name]) { private var best: SearchResult = SearchFailure + private def isShadowed(name: Name) = ( + (shadowed != null) + && (shadowed(name) || nonImplicitSynonymInScope(name)) + ) + private def isIneligible(info: ImplicitInfo) = ( + info.isCyclicOrErroneous + || isView && isConforms(info.sym) + || isShadowed(info.name) + ) /** True if a given ImplicitInfo (already known isValid) is eligible. */ - def survives(info: ImplicitInfo): Boolean = { - !info.isCyclicOrErroneous && - !(isView && isConformsMethod(info.sym)) && - isPlausiblyCompatible(info.tpe, wildPt) && // <--- cheaper than matchesPt - matchesPt(depoly(info.tpe), wildPt, Nil) && - isStable(info.pre) && - (shadowed == null || (!shadowed(info.name) && !nonImplicitSynonymInScope(info.name))) - } + def survives(info: ImplicitInfo) = ( + !isIneligible(info) // cyclic, erroneous, shadowed, or specially excluded + && isPlausiblyCompatible(info.tpe, wildPt) // optimization to avoid matchesPt + && matchesPt(info) // stable and matches expected type + ) /** The implicits that are not valid because they come later in the source and * lack an explicit result type. Used for error diagnostics only. */ @@ -686,6 +760,15 @@ trait Implicits { */ private def checkValid(sym: Symbol) = isValid(sym) || { invalidImplicits += sym ; false } + /** Is `sym` the standard conforms method in Predef? + * Note: DON't replace this by sym == Predef_conforms, as Predef_conforms is a `def` + * which does a member lookup (it can't be a lazy val because we might reload Predef + * during resident compilations). + */ + private def isConforms(sym: Symbol) = ( + (sym.name == nme.conforms) && (sym.owner == PredefModule.moduleClass) + ) + /** Preventing a divergent implicit from terminating implicit search, * so that if there is a best candidate it can still be selected. */ diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 68c84b8e15..79db9ab000 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -330,142 +330,6 @@ trait Infer { } } - /** Capturing the overlap between isPlausiblyCompatible and normSubType. - * This is a faithful translation of the code which was there, but it - * seems likely the methods are intended to be even more similar than - * they are: perhaps someone more familiar with the intentional distinctions - * can examine the now much smaller concrete implementations below. - */ -/* - abstract class CompatibilityChecker { - def resultTypeCheck(restpe: Type, arg: Type): Boolean - def argumentCheck(arg: Type, param: Type): Boolean - def lastChanceCheck(tp: Type, pt: Type): Boolean - - final def mtcheck(tp: MethodType, pt: TypeRef): Boolean = { - val MethodType(params, restpe) = tp - val TypeRef(pre, sym, args) = pt - - if (sym.isAliasType) apply(tp, pt.normalize) - else if (sym.isAbstractType) apply(tp, pt.bounds.lo) - else { - val len = args.length - 1 - hasLength(params, len) && - sym == FunctionClass(len) && { - val ps = params.iterator - val as = args.iterator - while (ps.hasNext && as.hasNext) { - if (!argumentCheck(as.next, ps.next.tpe)) - return false - } - ps.isEmpty && as.hasNext && { - val lastArg = as.next - as.isEmpty && resultTypeCheck(restpe, lastArg) - } - } - } - } - - def apply(tp: Type, pt: Type): Boolean = tp match { - case mt @ MethodType(_, restpe) => - if (mt.isImplicit) - apply(restpe, pt) - else pt match { - case tr: TypeRef => mtcheck(mt, tr) - case _ => lastChanceCheck(tp, pt) - } - case NullaryMethodType(restpe) => apply(restpe, pt) - case PolyType(_, restpe) => apply(restpe, pt) - case ExistentialType(_, qtpe) => apply(qtpe, pt) - case _ => argumentCheck(tp, pt) - } - } - - object isPlausiblyCompatible extends CompatibilityChecker { - def resultTypeCheck(restpe: Type, arg: Type) = isPlausiblyCompatible(restpe, arg) - def argumentCheck(arg: Type, param: Type) = isPlausiblySubType(arg, param) - def lastChanceCheck(tp: Type, pt: Type) = false - } - object normSubType extends CompatibilityChecker { - def resultTypeCheck(restpe: Type, arg: Type) = normSubType(restpe, arg) - def argumentCheck(arg: Type, param: Type) = arg <:< param - def lastChanceCheck(tp: Type, pt: Type) = tp <:< pt - - override def apply(tp: Type, pt: Type): Boolean = tp match { - case ExistentialType(_, _) => normalize(tp) <:< pt - case _ => super.apply(tp, pt) - } - } -*/ - def isPlausiblyCompatible(tp: Type, pt: Type) = checkCompatibility(true, tp, pt) - def normSubType(tp: Type, pt: Type) = checkCompatibility(false, tp, pt) - - @tailrec private def checkCompatibility(fast: Boolean, tp: Type, pt: Type): Boolean = tp match { - case mt @ MethodType(params, restpe) => - if (mt.isImplicit) - checkCompatibility(fast, restpe, pt) - else pt match { - case tr @ TypeRef(pre, sym, args) => - - if (sym.isAliasType) checkCompatibility(fast, tp, pt.normalize) - else if (sym.isAbstractType) checkCompatibility(fast, tp, pt.bounds.lo) - else { - val len = args.length - 1 - hasLength(params, len) && - sym == FunctionClass(len) && { - var ps = params - var as = args - if (fast) { - while (ps.nonEmpty && as.nonEmpty) { - if (!isPlausiblySubType(as.head, ps.head.tpe)) - return false - ps = ps.tail - as = as.tail - } - } else { - while (ps.nonEmpty && as.nonEmpty) { - if (!(as.head <:< ps.head.tpe)) - return false - ps = ps.tail - as = as.tail - } - } - ps.isEmpty && as.nonEmpty && { - val lastArg = as.head - as.tail.isEmpty && checkCompatibility(fast, restpe, lastArg) - } - } - } - - case _ => if (fast) false else tp <:< pt - } - case NullaryMethodType(restpe) => checkCompatibility(fast, restpe, pt) - case PolyType(_, restpe) => checkCompatibility(fast, restpe, pt) - case ExistentialType(_, qtpe) => if (fast) checkCompatibility(fast, qtpe, pt) else normalize(tp) <:< pt // is !fast case needed?? - case _ => if (fast) isPlausiblySubType(tp, pt) else tp <:< pt - } - - - /** This expresses more cleanly in the negative: there's a linear path - * to a final true or false. - */ - private def isPlausiblySubType(tp1: Type, tp2: Type) = !isImpossibleSubType(tp1, tp2) - private def isImpossibleSubType(tp1: Type, tp2: Type) = tp1.normalize.widen match { - case tr1 @ TypeRef(_, sym1, _) => - // We can only rule out a subtype relationship if the left hand - // side is a class, else we may not know enough. - sym1.isClass && (tp2.normalize.widen match { - case TypeRef(_, sym2, _) => - sym2.isClass && - !(sym1 isSubClass sym2) && - !(sym1 isNumericSubClass sym2) - case RefinedType(parents, decls) => - decls.nonEmpty && - tr1.member(decls.head.name) == NoSymbol - case _ => false - }) - case _ => false - } def isCompatible(tp: Type, pt: Type): Boolean = { val tp1 = normalize(tp) -- cgit v1.2.3