From c4bed34b009ffc54b1eac10ee75fba27040f1533 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 13 Feb 2014 14:50:04 +0100 Subject: Two performance optimizations 1) Split out wildApprox into separate function 2) Be more careful not to follow static prefix chains where not needed --- src/dotty/tools/dotc/core/TypeComparer.scala | 23 ++++---- src/dotty/tools/dotc/core/TypeOps.scala | 9 ++-- src/dotty/tools/dotc/core/Types.scala | 7 ++- src/dotty/tools/dotc/typer/Implicits.scala | 7 +-- src/dotty/tools/dotc/typer/Inferencing.scala | 80 +++++++++++++++------------- src/dotty/tools/dotc/typer/Namer.scala | 2 +- 6 files changed, 71 insertions(+), 57 deletions(-) (limited to 'src/dotty/tools/dotc') diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 1d2d4bac9..a8ad580a7 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -163,7 +163,8 @@ class TypeComparer(initctx: Context) extends DotClass { */ def approximation(param: PolyParam, fromBelow: Boolean): Type = { val avoidParam = new TypeMap { - override def apply(tp: Type) = mapOver { + override def stopAtStatic = true + def apply(tp: Type) = mapOver { tp match { case tp: RefinedType if param occursIn tp.refinedInfo => tp.parent case _ => tp @@ -269,18 +270,16 @@ class TypeComparer(initctx: Context) extends DotClass { def compareNamed = tp1 match { case tp1: NamedType => val sym1 = tp1.symbol - val sym2 = tp2.symbol - val pre1 = tp1.prefix - val pre2 = tp2.prefix - - ( if (sym1 == sym2) ( - ctx.erasedTypes + ( if (sym1 == tp2.symbol) ( + ctx.erasedTypes || sym1.isStaticOwner - || isSubType(pre1, pre2) - || pre1.isInstanceOf[ThisType] && pre2.isInstanceOf[ThisType] - ) - else - tp1.name == tp2.name && isSubType(pre1, pre2) + || { val pre1 = tp1.prefix + val pre2 = tp2.prefix + isSubType(pre1, pre2) || + pre1.isInstanceOf[ThisType] && pre2.isInstanceOf[ThisType] + } + ) else + tp1.name == tp2.name && isSubType(tp1.prefix, tp2.prefix) ) || secondTryNamed(tp1, tp2) case _ => secondTry(tp1, tp2) diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index 6e984e43c..afa39f2a3 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -50,8 +50,11 @@ trait TypeOps { this: Context => /** Implementation of Types#simplified */ final def simplify(tp: Type, theMap: SimplifyMap): Type = tp match { case tp: NamedType => - tp.derivedSelect(simplify(tp.prefix, theMap)) - case _: ThisType | NoPrefix => + if (tp.symbol.isStatic) tp + else tp.derivedSelect(simplify(tp.prefix, theMap)) + case tp: PolyParam => + typerState.constraint.typeVarOfParam(tp) orElse tp + case _: ThisType | _: BoundType | NoPrefix => tp case tp: RefinedType => tp.derivedRefinedType(simplify(tp.parent, theMap), tp.refinedName, simplify(tp.refinedInfo, theMap)) @@ -59,8 +62,6 @@ trait TypeOps { this: Context => simplify(l, theMap) & simplify(r, theMap) case OrType(l, r) => simplify(l, theMap) | simplify(r, theMap) - case tp: PolyParam => - typerState.constraint.typeVarOfParam(tp) orElse tp case _ => (if (theMap != null) theMap else new SimplifyMap).mapOver(tp) } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index b99162383..bacbe4f9d 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -2080,6 +2080,8 @@ object Types { abstract class TypeMap(implicit ctx: Context) extends (Type => Type) { thisMap => + protected def stopAtStatic = true + def apply(tp: Type): Type protected var variance = 1 @@ -2087,7 +2089,8 @@ object Types { /** Map this function over given type */ def mapOver(tp: Type): Type = tp match { case tp: NamedType => - tp.derivedSelect(this(tp.prefix)) + if (stopAtStatic && tp.symbol.isStatic) tp + else tp.derivedSelect(this(tp.prefix)) case _: ThisType | _: BoundType @@ -2173,6 +2176,7 @@ object Types { tp.derivedClassInfo(this(tp.prefix)) def andThen(f: Type => Type): TypeMap = new TypeMap { + override def stopAtStatic = thisMap.stopAtStatic def apply(tp: Type) = f(thisMap(tp)) } } @@ -2191,6 +2195,7 @@ object Types { } object IdentityTypeMap extends TypeMap()(NoContext) { + override def stopAtStatic = true def apply(tp: Type) = tp } diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala index 5e5077cc4..74e79269f 100644 --- a/src/dotty/tools/dotc/typer/Implicits.scala +++ b/src/dotty/tools/dotc/typer/Implicits.scala @@ -56,9 +56,9 @@ object Implicits { case mt: MethodType => mt.isImplicit || mt.paramTypes.length != 1 || - !(argType <:< ((new WildApprox) apply mt.paramTypes.head))(ctx.fresh.withExploreTyperState) + !(argType <:< wildApprox(mt.paramTypes.head)(ctx.fresh.withExploreTyperState)) case rtp => - discardForView((new WildApprox) apply rtp, argType) + discardForView(wildApprox(rtp), argType) } case tpw: TermRef => false // can't discard overloaded refs @@ -270,6 +270,7 @@ trait ImplicitRunInfo { self: RunInfo => */ object liftToClasses extends TypeMap { private implicit val ctx: Context = liftingCtx + override def stopAtStatic = true def apply(tp: Type) = tp match { case tp: TypeRef if tp.symbol.isAbstractOrAliasType => val pre = tp.prefix @@ -439,7 +440,7 @@ trait Implicits { self: Typer => } /** The expected type where parameters and uninstantiated typevars are replaced by wildcard types */ - val wildProto = implicitProto(pt, new WildApprox) + val wildProto = implicitProto(pt, wildApprox(_)) /** Search failures; overridden in ExplainedImplicitSearch */ protected def nonMatchingImplicit(ref: TermRef): SearchFailure = NoImplicitMatches diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 868276598..409d4a356 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -520,44 +520,52 @@ object Inferencing { /** Approximate occurrences of parameter types and uninstantiated typevars * by wildcard types. */ - class WildApprox(implicit ctx: Context) extends TypeMap { - override def apply(tp: Type) = tp match { - case PolyParam(pt, pnum) => - WildcardType(apply(pt.paramBounds(pnum)).bounds) - case MethodParam(mt, pnum) => - WildcardType(TypeBounds.upper(apply(mt.paramTypes(pnum)))) - case tp: TypeVar => - val inst = tp.instanceOpt - if (inst.exists) apply(inst) - else ctx.typerState.constraint.at(tp.origin) match { - case bounds: TypeBounds => apply(WildcardType(bounds)) - case NoType => WildcardType - } - case tp: AndType => - val tp1a = apply(tp.tp1) - val tp2a = apply(tp.tp2) - def wildBounds(tp: Type) = - if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp) - if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) - WildcardType(wildBounds(tp1a) & wildBounds(tp2a)) - else - tp.derivedAndType(tp1a, tp2a) - case tp: OrType => - val tp1a = apply(tp.tp1) - val tp2a = apply(tp.tp2) - if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) - WildcardType(tp1a.bounds | tp2a.bounds) - else - tp.derivedOrType(tp1a, tp2a) - case tp: SelectionProto => - tp.derivedSelectionProto(tp.name, this(tp.refinedInfo), NoViewsAllowed) - case tp: ViewProto => - tp.derivedViewProto(this(tp.argType), this(tp.resultType)) - case _ => - mapOver(tp) - } + final def wildApprox(tp: Type, theMap: WildApproxMap = null)(implicit ctx: Context): Type = tp match { + case tp: NamedType => // default case, inlined for speed + if (tp.symbol.isStatic) tp + else tp.derivedSelect(wildApprox(tp.prefix, theMap)) + case PolyParam(pt, pnum) => + WildcardType(wildApprox(pt.paramBounds(pnum)).bounds) + case MethodParam(mt, pnum) => + WildcardType(TypeBounds.upper(wildApprox(mt.paramTypes(pnum)))) + case tp: TypeVar => + val inst = tp.instanceOpt + if (inst.exists) wildApprox(inst) + else ctx.typerState.constraint.at(tp.origin) match { + case bounds: TypeBounds => wildApprox(WildcardType(bounds)) + case NoType => WildcardType + } + case tp: AndType => + val tp1a = wildApprox(tp.tp1) + val tp2a = wildApprox(tp.tp2) + def wildBounds(tp: Type) = + if (tp.isInstanceOf[WildcardType]) tp.bounds else TypeBounds.upper(tp) + if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) + WildcardType(wildBounds(tp1a) & wildBounds(tp2a)) + else + tp.derivedAndType(tp1a, tp2a) + case tp: OrType => + val tp1a = wildApprox(tp.tp1) + val tp2a = wildApprox(tp.tp2) + if (tp1a.isInstanceOf[WildcardType] || tp2a.isInstanceOf[WildcardType]) + WildcardType(tp1a.bounds | tp2a.bounds) + else + tp.derivedOrType(tp1a, tp2a) + case tp: SelectionProto => + tp.derivedSelectionProto(tp.name, wildApprox(tp.refinedInfo), NoViewsAllowed) + case tp: ViewProto => + tp.derivedViewProto(wildApprox(tp.argType), wildApprox(tp.resultType)) + case _: ThisType | _: BoundType | NoPrefix => // default case, inlined for speed + tp + case tp: RefinedType => // default case, inlined for speed + tp.derivedRefinedType(wildApprox(tp.parent, theMap), tp.refinedName, wildApprox(tp.refinedInfo, theMap)) + case _ => + (if (theMap != null) theMap else new WildApproxMap).mapOver(tp) } + private[Inferencing] class WildApproxMap(implicit ctx: Context) extends TypeMap { + def apply(tp: Type) = wildApprox(tp, this) + } /** Add all parameters in given polytype `pt` to the constraint's domain. * If the constraint contains already some of these parameters in its domain, diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index fac08ea3d..96fa7f44f 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -551,7 +551,7 @@ class Namer { typer: Typer => defContext(sym).denotNamed(original) def paramProto(paramss: List[List[Type]], idx: Int): Type = paramss match { case params :: paramss1 => - if (idx < params.length) (new WildApprox) apply params(idx) + if (idx < params.length) wildApprox(params(idx)) else paramProto(paramss1, idx - params.length) case nil => WildcardType -- cgit v1.2.3