From 5daae278392ed6fabd45c9fa55aded970ca2a348 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Wed, 29 Jun 2016 19:12:29 +0200 Subject: Multiple fixes - Swap order of tests in lookupRefined - Change joins of BindingKinds. A type parameter joint with a normal refinement represents a type parameter that has been filled in. So the Binding attribute should be removed. - Fix printing of type lambdas under new hk scheme - refine isRef for hk type The new definition avoids that a higher-kinded type "isRef" of an underlying class. I.e. `[X] -> Any` is not longer a ref to `Any`. - Fix withBindingKind for type aliases Old definition converted aliases to type bounds. - Multiple fixes to BetaReduce - Fix logic for hk subtype tests - Make isHK more precise --- src/dotty/tools/dotc/core/TypeApplications.scala | 84 +++++++++++++++++----- src/dotty/tools/dotc/core/TypeComparer.scala | 33 ++++----- src/dotty/tools/dotc/core/Types.scala | 32 ++++++--- src/dotty/tools/dotc/printing/RefinedPrinter.scala | 7 +- 4 files changed, 109 insertions(+), 47 deletions(-) (limited to 'src/dotty') diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala index 9ceae6e5f..dfd1caf62 100644 --- a/src/dotty/tools/dotc/core/TypeApplications.scala +++ b/src/dotty/tools/dotc/core/TypeApplications.scala @@ -285,17 +285,18 @@ object TypeApplications { TypeLambda.applyOBS(variances, bounds, body) } - private class InstMap(fullType: Type)(implicit ctx: Context) extends TypeMap { + private class InstMap(fullType: Type, shortLived: Boolean)(implicit ctx: Context) extends TypeMap { var localRecs: Set[RecType] = Set.empty var keptRefs: Set[Name] = Set.empty var isSafe: Boolean = true + var tyconIsHK: Boolean = true def apply(tp: Type): Type = tp match { case tp @ TypeRef(RecThis(rt), sel) if sel.isHkArgName && localRecs.contains(rt) => fullType.member(sel).info match { case TypeAlias(alias) => apply(alias) case _ => keptRefs += sel; tp } - case tp: TypeVar if !tp.inst.exists => + case tp: TypeVar if !tp.inst.exists && !shortLived => isSafe = false tp case _ => @@ -451,8 +452,10 @@ class TypeApplications(val self: Type) extends AnyVal { def isHK(implicit ctx: Context): Boolean = self.dealias match { case self: TypeRef => self.info.isHK case self: RefinedType => self.refinedName == tpnme.hkApplyOBS || self.isTypeParam - case self: RecType => self.parent.isHK - case TypeBounds(_, hi) => hi.isHK + case self: SingletonType => false + case self: TypeVar => self.origin.isHK + case self: WildcardType => self.optBounds.isHK + case self: TypeProxy => self.underlying.isHK case _ => false } @@ -552,20 +555,55 @@ class TypeApplications(val self: Type) extends AnyVal { assert(!isHK, self) self match { case self: TypeAlias => - self.derivedTypeAlias(expand(self.alias.BetaReduce)) + self.derivedTypeAlias(expand(self.alias.BetaReduce())) case self @ TypeBounds(lo, hi) => if (Config.newHK) - self.derivedTypeBounds(lo, expand(hi.BetaReduce)) + self.derivedTypeBounds(lo, expand(hi.BetaReduce())) else - self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi.BetaReduce))) + self.derivedTypeBounds(lo, expand(TypeBounds.upper(hi.BetaReduce()))) case _ => expand(self) } } - def BetaReduce(implicit ctx: Context): Type = self.dealias match { - case self1 @ RefinedType(_, rname, _) if Config.newHK && rname.isHkArgName => - val inst = new InstMap(self) - def instTop(tp: Type): Type = { + /** If `self` is a * type, perform the following rewritings: + * + * 1. For every occurrence of `z.$hk_i`, where `z` is a RecThis type that refers + * to some recursive type in `self`, if the member of `self.hk$i` has an alias + * type `= U`: + * + * z.$hk_i --> U + * + * 2. For every top-level binding `type A = z.$hk_i$, where `z` is a RecThis type that refers + * to some recursive type in `self`, if the member of `self` has bounds `S..U`: + * + * type A = z.$hk_i --> type A >: S <: U + * + * 3. If the type constructor preceding all bindings is a * type, delete every top-level + * binding `{ type $hk_i ... }` where `$hk_i` does not appear in the prefix of the binding. + * I.e. + * + * T { type $hk_i ... } --> T + * + * If `$hk_i` does not appear in `T`. + * + * A binding is top-level if it can be reached by + * + * - following aliases + * - dropping refinements and rec-types + * - going from a wildcard type to its upper bound + * + * @param shortLived If `false` suppresses all rewritings where a type variable with + * an unknown or uncommitted instance is rewritten. Reason: If the + * type variable is finally instantiated to something else, the + * reduction might not be valid anymore. However, when reducing + * during `<:<` tests `shortLived` is true and the reduction + * is never suppressed, because then we are only interested + * in subtyping relative to the current context. + */ + def BetaReduce(shortLived: Boolean = false)(implicit ctx: Context): Type = self.dealias match { + case self1 @ RefinedType(_, rname, _) if Config.newHK && rname.isHkArgName && self1.typeParams.isEmpty => + val inst = new InstMap(self, shortLived) + def instTop(tp: Type): Type = if (!inst.isSafe) tp else tp.dealias match { case tp: RecType => @@ -574,18 +612,30 @@ class TypeApplications(val self: Type) extends AnyVal { case tp @ RefinedType(parent, rname, rinfo) => rinfo match { case TypeAlias(TypeRef(RecThis(rt), sel)) if sel.isHkArgName && inst.localRecs.contains(rt) => - instTop(tp.derivedRefinedType(parent, rname, self.member(sel).info)) + val bounds @ TypeBounds(_, _) = self.member(sel).info + instTop(tp.derivedRefinedType(parent, rname, bounds.withBindingKind(NoBinding))) case _ => val parent1 = instTop(parent) - if (rname.isHkArgName && !inst.keptRefs.contains(rname)) parent1 + if (rname.isHkArgName && + !inst.tyconIsHK && + !inst.keptRefs.contains(rname)) parent1 else tp.derivedRefinedType(parent1, rname, inst(rinfo)) } + case tp @ WildcardType(bounds @ TypeBounds(lo, hi)) => + tp.derivedWildcardType(bounds.derivedTypeBounds(inst(lo), instTop(hi))) case tp => - inst(tp) - }} + inst.tyconIsHK = tp.isHK + val res = inst(tp) + tp match { + case tp: WildcardType => + println(s"inst $tp --> $res") + case _ => + } + res + } val reduced = instTop(self) if (inst.isSafe) reduced else self - case self1 => self1 + case _ => self } /** A type ref is eta expandable if it refers to a non-lambda class. @@ -761,7 +811,7 @@ class TypeApplications(val self: Type) extends AnyVal { matchParams(RefinedType(t, tparam.memberName, arg.toBounds(tparam)), tparams1, args1) } catch { case ex: MatchError => - println(s"applied type mismatch: $self $args, typeParams = $typParams") // !!! DEBUG + println(s"applied type mismatch: $self with underlying ${self.underlyingIfProxy}, args = $args, typeParams = $typParams") // !!! DEBUG //println(s"precomplete decls = ${self.typeSymbol.unforcedDecls.toList.map(_.denot).mkString("\n ")}") throw ex } diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 3648b3764..b0c36ca58 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -354,12 +354,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp2: RefinedType => def compareRefinedSlow: Boolean = { val name2 = tp2.refinedName - if (name2.isHkArgName) { - val tp2reduced = tp2.BetaReduce - if (Config.newHK && (tp2reduced ne tp2)) return isSubType(tp1, tp2reduced) - if (Config.newHK && tp2.isTypeParam) return compareHkLambda(tp2, tp1, inOrder = false) - if (Config.newHK && !tp1.isHKApply) return compareHkApply(tp2, tp1, inOrder = false) - } isSubType(tp1, tp2.parent) && (name2 == nme.WILDCARD || hasMatchingMember(name2, tp1, tp2)) } @@ -374,10 +368,10 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { // This twist is needed to make collection/generic/ParFactory.scala compile fourthTry(tp1, tp2) || compareRefinedSlow case _ => - compareRefinedSlow || - fourthTry(tp1, tp2) || compareHkApply(tp2, tp1, inOrder = false) || compareHkLambda(tp2, tp1, inOrder = false) || + compareRefinedSlow || + fourthTry(tp1, tp2) || compareAliasedRefined(tp2, tp1, inOrder = false) } else // fast path, in particular for refinements resulting from parameterization. @@ -501,15 +495,10 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { } isNewSubType(tp1.underlying.widenExpr, tp2) || comparePaths case tp1: RefinedType => - if (Config.newHK && tp1.refinedName.isHkArgName) { - val tp1reduced = tp1.BetaReduce - if (Config.newHK && (tp1reduced ne tp1)) return isSubType(tp1reduced, tp2) - if (Config.newHK && tp1.isTypeParam) return compareHkLambda(tp1, tp2, inOrder = true) - if (Config.newHK && !tp2.isHKApply) return compareHkApply(tp1, tp2, inOrder = true) - } isNewSubType(tp1.parent, tp2) || - !Config.newHK && compareHkLambda(tp1, tp2, inOrder = true) || - !Config.newHK && compareAliasedRefined(tp1, tp2, inOrder = true) + compareHkApply(tp1, tp2, inOrder = true) || + compareHkLambda(tp1, tp2, inOrder = true) || + compareAliasedRefined(tp1, tp2, inOrder = true) case tp1: RecType => isNewSubType(tp1.parent, tp2) case AndType(tp11, tp12) => @@ -609,7 +598,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { val hkTypeParams = param.typeParams subtyping.println(i"classBounds = ${projection.prefix.member(tpnme.hkApplyOBS).info.classSymbols}") subtyping.println(i"base classes = ${other.baseClasses}") - subtyping.println(i"type params = $hkTypeParams") + subtyping.println(i"type params = ${hkTypeParams.map(_.memberName)}") if (inOrder) unifyWith(other) else testLifted(other, projection.prefix, hkTypeParams, unifyWith) case _ => @@ -671,13 +660,17 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { false } } - Config.newHK && app.isHKApply && !other.isHKApply && tryInfer(app.typeConstructor.dealias) + Config.newHK && app.isHKApply && !other.isHKApply && { + val reduced = app.BetaReduce(shortLived = true) + if (reduced ne app) + if (inOrder) isSubType(reduced, other) else isSubType(other, reduced) + else tryInfer(app.typeConstructor.dealias) + } } /** Compare type lambda with non-lambda type. */ def compareHkLambda(rt: RefinedType, other: Type, inOrder: Boolean) = rt match { case TypeLambda(args, body) => - other.isInstanceOf[TypeRef] && args.length == other.typeParams.length && { val applied = other.appliedTo(argRefs(rt, args.length)) if (inOrder) isSubType(body, applied) @@ -1510,7 +1503,7 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) { override def compareHkApply(app: RefinedType, other: Type, inOrder: Boolean) = if (app.isHKApply) - traceIndented(i"compareHkApply $app, $other, $inOrder, ${app.typeConstructor.dealias}") { + traceIndented(i"compareHkApply $app, $other, $inOrder, ${app.BetaReduce(shortLived = true)}") { super.compareHkApply(app, other, inOrder) } else super.compareHkApply(app, other, inOrder) diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 22a26968c..78003d972 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -114,7 +114,9 @@ object Types { case TypeAlias(tp) => tp.isRef(sym) case _ => this1.symbol eq sym } - case this1: RefinedOrRecType => + case this1: RefinedType => + !this1.isTypeParam && this1.parent.isRef(sym) + case this1: RecType => this1.parent.isRef(sym) case _ => false @@ -895,6 +897,14 @@ object Types { def narrow(implicit ctx: Context): TermRef = TermRef(NoPrefix, ctx.newSkolem(this)) + /** Useful for diagnsotics: The underlying type if this type is a type proxy, + * otherwise NoType + */ + def underlyingIfProxy(implicit ctx: Context) = this match { + case this1: TypeProxy => this1.underlying + case _ => NoType + } + // ----- Normalizing typerefs over refined types ---------------------------- /** If this normalizes* to a refinement type that has a refinement for `name` (which might be followed @@ -959,10 +969,12 @@ object Types { pre.refinedInfo match { case TypeAlias(alias) => if (pre.refinedName ne name) loop(pre.parent) - else if (!pre.refinementRefersToThis) alias else alias match { case TypeRef(RefinedThis(`pre`), aliasName) => lookupRefined(aliasName) // (1) - case _ => if (name == tpnme.hkApplyOBS) betaReduce(alias) else NoType // (2) // ### use TypeApplication's betaReduce + case _ => + if (!pre.refinementRefersToThis) alias + else if (name == tpnme.hkApplyOBS) betaReduce(alias) + else NoType } case _ => loop(pre.parent) } @@ -3019,7 +3031,10 @@ object Types { case _ => this } - def withBindingKind(bk: BindingKind)(implicit ctx: Context) = derivedTypeBounds(lo, hi, bk) + def withBindingKind(bk: BindingKind)(implicit ctx: Context) = this match { + case tp: TypeAlias => assert(bk == NoBinding); this + case _ => derivedTypeBounds(lo, hi, bk) + } //def checkBinding: this.type = { assert(isBinding); this } @@ -3070,7 +3085,7 @@ object Types { } override def toString = { - def bkString = if (isBinding) s"|bk=${BindingKind.toVariance(bindingKind)}" else "" + def bkString = if (isBinding) s"|v=${BindingKind.toVariance(bindingKind)}" else "" if (lo eq hi) s"TypeAlias($lo, $variance)" else s"TypeBounds($lo, $hi$bkString)" } @@ -3129,8 +3144,7 @@ object Types { class BindingKind(val n: Byte) extends AnyVal { def join(that: BindingKind) = if (this == that) this - else if (this == NoBinding) that - else if (that == NoBinding) this + else if (this == NoBinding || that == NoBinding) NoBinding else NonvariantBinding } @@ -3202,7 +3216,9 @@ object Types { /** Wildcard type, possibly with bounds */ abstract case class WildcardType(optBounds: Type) extends CachedGroundType with TermType { def derivedWildcardType(optBounds: Type)(implicit ctx: Context) = - if (optBounds eq this.optBounds) this else WildcardType(optBounds.asInstanceOf[TypeBounds]) + if (optBounds eq this.optBounds) this + else if (!optBounds.exists) WildcardType + else WildcardType(optBounds.asInstanceOf[TypeBounds]) override def computeHash = doHash(optBounds) } diff --git a/src/dotty/tools/dotc/printing/RefinedPrinter.scala b/src/dotty/tools/dotc/printing/RefinedPrinter.scala index b5bc17c0c..61e29982b 100644 --- a/src/dotty/tools/dotc/printing/RefinedPrinter.scala +++ b/src/dotty/tools/dotc/printing/RefinedPrinter.scala @@ -12,6 +12,7 @@ import typer.ProtoTypes.{SelectionProto, ViewProto, FunProto, IgnoredProto, dumm import Trees._ import TypeApplications._ import Decorators._ +import config.Config import scala.annotation.switch import language.implicitConversions @@ -117,9 +118,11 @@ class RefinedPrinter(_ctx: Context) extends PlainPrinter(_ctx) { if (defn.isTupleClass(cls)) return toTextTuple(args) return (toTextLocal(tycon) ~ "[" ~ Text(args map argText, ", ") ~ "]").close case tp @ TypeLambda(argBoundss, body) => - val variances = tp.classSymbol.typeParams.map(_.variance) + val variances = + if (Config.newHK) argBoundss.map(b => BindingKind.toVariance(b.bindingKind)) + else tp.classSymbol.typeParams.map(_.variance) val prefix = ((('X' - 'A') + lambdaNestingLevel) % 26 + 'A').toChar - val paramNames = variances.indices.toList.map(prefix.toString + _) + val paramNames = argBoundss.indices.toList.map(prefix.toString + _) val instantiate = new TypeMap { def contains(tp1: Type, tp2: Type): Boolean = tp1.eq(tp2) || { -- cgit v1.2.3