From 6728b51613c6a3ee858ace014fb9c9097d15c35b Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 3 Nov 2013 12:45:49 +0100 Subject: Adding simplification and fixing a variance problem. 1. Added a "simplified" method which gets called on type varianvle instantiation and interpolation. 2. Fixed a problem in TypeAccumulator which did not take the variance into account for Co/Contra type aliases. --- src/dotty/tools/dotc/ast/Trees.scala | 9 ++++- src/dotty/tools/dotc/core/TypeComparer.scala | 4 +- src/dotty/tools/dotc/core/Types.scala | 55 ++++++++++++++++++++++++++-- src/dotty/tools/dotc/typer/Implicits.scala | 4 +- src/dotty/tools/dotc/typer/Inferencing.scala | 7 +++- src/dotty/tools/dotc/typer/Typer.scala | 1 + 6 files changed, 71 insertions(+), 9 deletions(-) diff --git a/src/dotty/tools/dotc/ast/Trees.scala b/src/dotty/tools/dotc/ast/Trees.scala index 2392e52be..628e7f9d3 100644 --- a/src/dotty/tools/dotc/ast/Trees.scala +++ b/src/dotty/tools/dotc/ast/Trees.scala @@ -156,7 +156,12 @@ object Trees { private[this] var myTpe: T = _ - private def setMyTpe(tpe: T) = myTpe = tpe + /** Destructively set the type of the tree. This should be called only when it is known that + * it is safe under sharing to do so. One user-case is in the withType method below + * which implements copy-on-write. Another user-case is in method interpolateAndAdapt in Typer, + * where we overwrite with a simplified version of the type itself. + */ + private[dotc] def overwriteType(tpe: T) = myTpe = tpe /** The type of the tree. In case of an untyped tree, * an UnAssignedTypeException is thrown. (Overridden by empty trees) @@ -191,7 +196,7 @@ object Trees { (if (myTpe == null || (myTpe.asInstanceOf[AnyRef] eq tpe.asInstanceOf[AnyRef])) this else clone).asInstanceOf[Tree[Type]] - tree setMyTpe tpe + tree overwriteType tpe tree.asInstanceOf[ThisTree[Type]] } diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 5c261a03d..516098c39 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -199,7 +199,7 @@ class TypeComparer(initctx: Context) extends DotClass { case tp2: PolyParam => tp2 == tp1 || { isSubTypeWhenFrozen(tp1, bounds(tp2).lo) || { - println(s"adding ${tp1.show} <:< ${tp2.show} to ${constraint.show}") // !!!DEBUG + if (!frozenConstraint) println(s"adding ${tp1.show} <:< ${tp2.show} to ${constraint.show}") // !!!DEBUG constraint(tp2) match { case TypeBounds(lo, _) => addConstraint(tp2, tp1.widen, fromBelow = true) case _ => secondTry(tp1, tp2) @@ -238,7 +238,7 @@ class TypeComparer(initctx: Context) extends DotClass { case tp1: PolyParam => (tp1 == tp2) || { isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || { - println(s"adding ${tp1.show} <:< ${tp2.show} to ${constraint.show}") + if (!frozenConstraint) println(s"adding ${tp1.show} <:< ${tp2.show} to ${constraint.show}") assert(frozenConstraint || !(tp2 isRef defn.NothingClass)) // !!!DEBUG constraint(tp1) match { case TypeBounds(_, hi) => addConstraint(tp1, tp2, fromBelow = false) diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index ba8b4f139..f27822639 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1092,6 +1092,9 @@ object Types { case None => vmap updated (t, variance) } + case t: TypeRef => + val t1 = t.losslessDealias + if (t1 ne t) apply(vmap, t1) else foldOver(vmap, t) case _ => foldOver(vmap, t) } @@ -1099,6 +1102,30 @@ object Types { accu(Map.empty, this) } + /** A simplified version of this type which is equivalent wrt =:= to this type. + * Rules applied are: + * T { type U = V } # U --> V + * Also, type variables are instantiated and &/| operations are re-done because + * what was a union or intersection of type variables might be a simpler type + * after the type variables are instantiated. + */ + def simplified(implicit ctx: Context) = { + class Simplify extends TypeMap { + def apply(tp: Type): Type = tp match { + case tp: TypeRef => + val tp1 = tp.losslessDealias + if (tp1 ne tp) apply(tp1) else mapOver(tp) + case AndType(l, r) => + mapOver(l) & mapOver(r) + case OrType(l, r) => + mapOver(l) | mapOver(r) + case _ => + mapOver(tp) + } + } + new Simplify().apply(this) + } + // ----- hashing ------------------------------------------------------ /** customized hash code of this type. @@ -1409,6 +1436,28 @@ object Types { } abstract case class TypeRef(override val prefix: Type, name: TypeName) extends NamedType { + + /** If this TypeRef can be dealiased, its alias type, otherwise the type itself. + * A TypeRef can be safely dealiased if it refers to an alias type and either the + * referenced name is a type parameter or it is refined in the prefix of the TypeRef. + * The idea is than in those two cases we don't lose any info or clarity by + * dereferencing. + */ + def losslessDealias(implicit ctx: Context) = { + def isRefinedIn(tp: Type, name: Name): Boolean = tp match { + case RefinedType(parent, refinedName) => + name == refinedName || isRefinedIn(parent, name) + case _ => + false + } + if ((symbol is TypeArgument) || isRefinedIn(prefix, name)) + info match { + case TypeBounds(lo, hi) if lo eq hi => hi + case _ => this + } + else this + } + override def equals(that: Any) = that match { case that: TypeRef => this.prefix == that.prefix && @@ -1951,7 +2000,7 @@ object Types { var inst = ctx.typeComparer.approximate(origin, fromBelow) if (fromBelow && isSingleton(inst) && !isSingleton(upperBound)) inst = inst.widen - instantiateWith(inst) + instantiateWith(inst.simplified) } } @@ -2383,10 +2432,10 @@ object Types { case SuperType(thistp, supertp) => this(this(x, thistp), supertp) - case TypeBounds(lo, hi) => + case bounds @ TypeBounds(lo, hi) => if (lo eq hi) { val saved = variance - variance = 0 + variance = variance * bounds.variance try this(x, lo) finally variance = saved } diff --git a/src/dotty/tools/dotc/typer/Implicits.scala b/src/dotty/tools/dotc/typer/Implicits.scala index 8238b3e34..6e1044281 100644 --- a/src/dotty/tools/dotc/typer/Implicits.scala +++ b/src/dotty/tools/dotc/typer/Implicits.scala @@ -264,7 +264,9 @@ trait Implicits { self: Typer => else new ImplicitSearch(pt, argument, pos) val result = isearch.bestImplicit result match { - case success: SearchSuccess => success.tstate.commit() + case success: SearchSuccess => + println(s"committing to ${success.tstate.show}") + success.tstate.commit() case _ => } result diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 651cb16f7..8fbff0914 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -200,11 +200,16 @@ object Inferencing { * in type `tp` approximate it by its upper bound. */ def interpolateUndetVars(tp: Type, pos: Position): Unit = Stats.track("interpolateUndetVars") { + println(s"interpolate undet vars in ${tp.show}, pos = $pos, mode = ${ctx.mode}, undets = ${ctx.typerState.undetVars map (tvar => s"${tvar.show}@${tvar.pos}")}") + println(s"qualifying undet vars: ${ctx.typerState.undetVars filter qualifies map (_.show)}") + println(s"fulltype: $tp") // !!! DEBUG + def qualifies(tvar: TypeVar) = (pos contains tvar.pos) && !((ctx.mode is Mode.RestrictedInterpolation) && (tvar.pos contains pos)) val vs = tp.variances(tvar => (ctx.typerState.undetVars contains tvar) && qualifies(tvar)) + println(s"variances = $vs") var changed = false for ((tvar, v) <- vs) if (v != 0) { @@ -217,7 +222,7 @@ object Inferencing { else for (tvar <- ctx.typerState.undetVars) if (!(vs contains tvar) && qualifies(tvar)) { - // println(s"instantiating non-occurring $tvar in $tp") + println(s"instantiating non-occurring $tvar in $tp") tvar.instantiate(fromBelow = true) } } diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index d607d547b..eec005bc5 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -929,6 +929,7 @@ class Typer extends Namer with Applications with Implicits { def interpolateAndAdapt(tree: Tree, pt: Type)(implicit ctx: Context) = { ctx.interpolateUndetVars(tree.tpe.widen, tree.pos) + tree overwriteType tree.tpe.simplified adapt(tree, pt) } -- cgit v1.2.3