diff options
Diffstat (limited to 'src/dotty/tools/dotc')
-rw-r--r-- | src/dotty/tools/dotc/config/Config.scala | 9 | ||||
-rw-r--r-- | src/dotty/tools/dotc/config/ScalaSettings.scala | 1 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeApplications.scala | 46 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 158 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 38 | ||||
-rw-r--r-- | src/dotty/tools/dotc/printing/PlainPrinter.scala | 3 | ||||
-rw-r--r-- | src/dotty/tools/dotc/transform/Splitter.scala | 5 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/TypeAssigner.scala | 2 |
8 files changed, 174 insertions, 88 deletions
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index 7e3615416..cf43d277e 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -87,6 +87,15 @@ object Config { /** Check that certain types cannot be created in erasedTypes phases */ final val checkUnerased = true + /** In `derivedSelect`, rewrite + * + * (S & T)#A --> S#A & T#A + * (S | T)#A --> S#A | T#A + * + * Not sure whether this is useful. Preliminary measurements show a slowdown of about + * 7% for the build when this option is enabled. + */ + final val splitProjections = false /** Initial size of superId table */ final val InitialSuperIdsSize = 4096 diff --git a/src/dotty/tools/dotc/config/ScalaSettings.scala b/src/dotty/tools/dotc/config/ScalaSettings.scala index 62b071372..0c381c077 100644 --- a/src/dotty/tools/dotc/config/ScalaSettings.scala +++ b/src/dotty/tools/dotc/config/ScalaSettings.scala @@ -173,6 +173,7 @@ class ScalaSettings extends Settings.SettingGroup { val Ypatmatdebug = BooleanSetting("-Ypatmat-debug", "Trace pattern matching translation.") val Yexplainlowlevel = BooleanSetting("-Yexplain-lowlevel", "When explaining type errors, show types at a lower level.") val YnoDoubleBindings = BooleanSetting("-Yno-double-bindings", "Assert no namedtype is bound twice (should be enabled only if program is error-free).") + val YshowVarBounds = BooleanSetting("-Yshow-var-bounds", "Print type variables with their bounds") val optimise = BooleanSetting("-optimise", "Generates faster bytecode by applying optimisations to the program") withAbbreviation "-optimize" diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala index fbab4ee39..8aea3381a 100644 --- a/src/dotty/tools/dotc/core/TypeApplications.scala +++ b/src/dotty/tools/dotc/core/TypeApplications.scala @@ -173,8 +173,46 @@ object TypeApplications { if (tparams.isEmpty) args else args.zipWithConserve(tparams)((arg, tparam) => arg.etaExpandIfHK(tparam.infoOrCompleter)) + /** The references `<rt>.this.$hk0, ..., <rt>.this.$hk<n-1>`. */ def argRefs(rt: RefinedType, n: Int)(implicit ctx: Context) = List.range(0, n).map(i => RefinedThis(rt).select(tpnme.hkArg(i))) + + /** Merge `tp1` and `tp2` under a common lambda, combining them with `op`. + * @param tparams1 The type parameters of `tp1` + * @param tparams2 The type parameters of `tp2` + * @pre tparams1.length == tparams2.length + * Produces the type lambda + * + * [v1 X1 B1, ..., vn Xn Bn] -> op(tp1[X1, ..., Xn], tp2[X1, ..., Xn]) + * + * where + * + * - variances `vi` are the variances of corresponding type parameters for `tp1` + * or `tp2`, or are 0 of the latter disagree. + * - bounds `Bi` are the intersection of the corresponding type parameter bounds + * of `tp1` and `tp2`. + */ + def hkCombine(tp1: Type, tp2: Type, + tparams1: List[TypeSymbol], tparams2: List[TypeSymbol], op: (Type, Type) => Type) + (implicit ctx: Context): Type = { + val variances = (tparams1, tparams2).zipped.map { (tparam1, tparam2) => + val v1 = tparam1.variance + val v2 = tparam2.variance + if (v1 == v2) v1 else 0 + } + val bounds: List[RefinedType => TypeBounds] = + (tparams1, tparams2).zipped.map { (tparam1, tparam2) => + val b1: RefinedType => TypeBounds = + tp1.memberInfo(tparam1).bounds.internalizeFrom(tparams1) + val b2: RefinedType => TypeBounds = + tp2.memberInfo(tparam2).bounds.internalizeFrom(tparams2) + (rt: RefinedType) => b1(rt) & b2(rt) + } + val app1: RefinedType => Type = rt => tp1.appliedTo(argRefs(rt, tparams1.length)) + val app2: RefinedType => Type = rt => tp2.appliedTo(argRefs(rt, tparams2.length)) + val body: RefinedType => Type = rt => op(app1(rt), app2(rt)) + TypeLambda(variances, bounds, body) + } } import TypeApplications._ @@ -273,6 +311,14 @@ class TypeApplications(val self: Type) extends AnyVal { false } + /** Replace references to type parameters with references to hk arguments `this.$hk_i` + * Care is needed not to cause cyclic reference errors, hence `SafeSubstMap`. + */ + private[TypeApplications] def internalizeFrom[T <: Type](tparams: List[Symbol])(implicit ctx: Context): RefinedType => T = + (rt: RefinedType) => + new ctx.SafeSubstMap(tparams , argRefs(rt, tparams.length)) + .apply(self).asInstanceOf[T] + /** Lambda abstract `self` with given type parameters. Examples: * * type T[X] = U becomes type T = [X] -> U diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 163fa4919..1e90bd6c8 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -144,49 +144,43 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { def compareNamed(tp1: Type, tp2: NamedType): Boolean = { implicit val ctx: Context = this.ctx tp2.info match { - case info2: TypeAlias if tp2.prefix.isStable => - // If prefix is not stable (i.e. is not a path), then we have a true - // projection `T # A` which is treated as the existential type - // `ex(x: T)x.A`. We need to deal with the existential first before - // following the alias. If we did follow the alias we could be - // unsound as well as incomplete. An example of this was discovered in Iter2.scala. - // It failed to validate the subtype test - // - // (([+X] -> Seq[X]) & C)[SA] <: C[SA] - // - // Both sides are projections of $Apply. The left $Apply does have an - // aliased info, namely, Seq[SA]. But that is not a subtype of C[SA]. - // The problem is that, with the prefix not being a path, an aliased info - // does not necessarily give all of the information of the original projection. - // So we can't follow the alias without a backup strategy. If the alias - // would appear on the right then I believe this can be turned into a case - // of unsoundness. - isSubType(tp1, info2.alias) + case info2: TypeAlias => isSubType(tp1, info2.alias) case _ => tp1 match { case tp1: NamedType => tp1.info match { - case info1: TypeAlias if tp1.prefix.isStable => - isSubType(info1.alias, tp2) + case info1: TypeAlias => + if (isSubType(info1.alias, tp2)) return true + if (tp1.prefix.isStable) return false + // If tp1.prefix is stable, the alias does contain all information about the original ref, so + // there's no need to try something else. (This is important for performance). + // To see why we cannot in general stop here, consider: + // + // trait C { type A } + // trait D { type A = String } + // (C & D)#A <: C#A + // + // Following the alias leads to the judgment `String <: C#A` which is false. + // However the original judgment should be true. case _ => - val sym1 = tp1.symbol - if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) - ctx.erasedTypes || - sym1.isStaticOwner || - isSubType(tp1.prefix, tp2.prefix) || - thirdTryNamed(tp1, tp2) - else - ( (tp1.name eq tp2.name) - && isSubType(tp1.prefix, tp2.prefix) - && tp1.signature == tp2.signature - && !tp1.isInstanceOf[WithFixedSym] - && !tp2.isInstanceOf[WithFixedSym] - ) || - compareHK(tp1, tp2, inOrder = true) || - compareHK(tp2, tp1, inOrder = false) || - thirdTryNamed(tp1, tp2) } + val sym1 = tp1.symbol + if ((sym1 ne NoSymbol) && (sym1 eq tp2.symbol)) + ctx.erasedTypes || + sym1.isStaticOwner || + isSubType(tp1.prefix, tp2.prefix) || + thirdTryNamed(tp1, tp2) + else + ( (tp1.name eq tp2.name) + && isSubType(tp1.prefix, tp2.prefix) + && tp1.signature == tp2.signature + && !tp1.isInstanceOf[WithFixedSym] + && !tp2.isInstanceOf[WithFixedSym] + ) || + compareHkApply(tp1, tp2, inOrder = true) || + compareHkApply(tp2, tp1, inOrder = false) || + thirdTryNamed(tp1, tp2) case _ => - compareHK(tp2, tp1, inOrder = false) || + compareHkApply(tp2, tp1, inOrder = false) || secondTry(tp1, tp2) } } @@ -258,11 +252,13 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { private def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match { case tp1: NamedType => tp1.info match { - case info1: TypeAlias => isSubType(info1.alias, tp2) + case info1: TypeAlias => + if (isSubType(info1.alias, tp2)) return true + if (tp1.prefix.isStable) return false case _ => - compareHK(tp1, tp2, inOrder = true) || - thirdTry(tp1, tp2) } + compareHkApply(tp1, tp2, inOrder = true) || + thirdTry(tp1, tp2) case tp1: PolyParam => def flagNothingBound = { if (!frozenConstraint && tp2.isRef(defn.NothingClass) && state.isGlobalCommittable) { @@ -356,8 +352,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { isSubType(tp1, tp2.parent) && (name2 == nme.WILDCARD || hasMatchingMember(name2, tp1, tp2)) } - def etaExpandedSubType(tp1: Type) = - isSubType(tp1.typeConstructor.EtaExpand(tp2.typeParams), tp2) def compareRefined: Boolean = { val tp1w = tp1.widen val skipped2 = skipMatching(tp1w, tp2) @@ -371,7 +365,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case _ => compareRefinedSlow || fourthTry(tp1, tp2) || - needsEtaLift(tp1, tp2) && testLifted(tp1, tp2, tp2.typeParams, etaExpandedSubType) + compareHkLambda(tp2, tp1, inOrder = false) } else // fast path, in particular for refinements resulting from parameterization. isSubType(tp1, skipped2) && @@ -491,10 +485,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { } isNewSubType(tp1.underlying.widenExpr, tp2) || comparePaths case tp1: RefinedType => - isNewSubType(tp1.parent, tp2) || - needsEtaLift(tp2, tp1) && - tp2.typeParams.length == tp1.typeParams.length && - isSubType(tp1, tp2.EtaExpand(tp1.typeParams)) + isNewSubType(tp1.parent, tp2) || compareHkLambda(tp1, tp2, inOrder = true) case AndType(tp11, tp12) => // Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2 // and analogously for T11 & (T121 | T122) & T12 <: T2 @@ -525,14 +516,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { false } - /** Does `tp` need to be eta lifted to be comparable to `target`? - * This is the case if: - * - target is a type lambda, and - * - `tp` is eta-expandable (i.e. is a non-lambda class ref) - */ - private def needsEtaLift(tp: Type, target: RefinedType): Boolean = - target.refinedName == tpnme.hkApply && tp.isEtaExpandable - /** Test whether `tp1` has a base type of the form `B[T1, ..., Tn]` where * - `B` derives from one of the class symbols of `tp2`, * - the type parameters of `B` match one-by-one the variances of `tparams`, @@ -574,7 +557,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { * * (4) If `inOrder`, test `projection <: other` else test `other <: projection`. */ - def compareHK(projection: NamedType, other: Type, inOrder: Boolean): Boolean = { + def compareHkApply(projection: NamedType, other: Type, inOrder: Boolean): Boolean = { def tryInfer(tp: Type): Boolean = ctx.traceIndented(i"compareHK($projection, $other, inOrder = $inOrder, constr = $tp)", subtyping) { tp match { case tp: TypeVar => tryInfer(tp.underlying) @@ -609,6 +592,18 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { tryInfer(projection.prefix.typeConstructor.dealias) } + /** Compare type lambda with non-lambda type. */ + def compareHkLambda(rt: RefinedType, other: Type, inOrder: Boolean) = rt match { + case TypeLambda(vs, args, body) => + other.isInstanceOf[TypeRef] && + args.length == other.typeParams.length && { + val applied = other.appliedTo(argRefs(rt, args.length)) + if (inOrder) isSubType(body, applied) else isSubType(applied, body) + } + case _ => + false + } + /** Returns true iff either `tp11 <:< tp21` or `tp12 <:< tp22`, trying at the same time * to keep the constraint as wide as possible. Specifically, if * @@ -1007,12 +1002,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { val t2 = distributeAnd(tp2, tp1) if (t2.exists) t2 else if (erased) erasedGlb(tp1, tp2, isJava = false) - else { - //if (isHKRef(tp1)) tp2 - //else if (isHKRef(tp2)) tp1 - //else - AndType(tp1, tp2) - } + else liftIfHK(tp1, tp2, AndType(_, _)) } } @@ -1036,14 +1026,23 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { val t2 = distributeOr(tp2, tp1) if (t2.exists) t2 else if (erased) erasedLub(tp1, tp2) - else - //if (isHKRef(tp1)) tp1 - //else if (isHKRef(tp2)) tp2 - //else - OrType(tp1, tp2) + else liftIfHK(tp1, tp2, OrType(_, _)) } } + /** `op(tp1, tp2)` unless `tp1` and `tp2` are type-constructors. + * In the latter case, combine `tp1` and `tp2` under a type lambda like this: + * + * [X1, ..., Xn] -> op(tp1[X1, ..., Xn], tp2[X1, ..., Xn]) + */ + private def liftIfHK(tp1: Type, tp2: Type, op: (Type, Type) => Type) = { + val tparams1 = tp1.typeParams + val tparams2 = tp2.typeParams + if (tparams1.isEmpty || tparams2.isEmpty) op(tp1, tp2) + else if (tparams1.length != tparams2.length) mergeConflict(tp1, tp2) + else hkCombine(tp1, tp2, tparams1, tparams2, op) + } + /** Try to distribute `&` inside type, detect and handle conflicts */ private def distributeAnd(tp1: Type, tp2: Type): Type = tp1 match { // opportunistically merge same-named refinements @@ -1106,18 +1105,15 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { NoType } - /** Try to distribute `|` inside type, detect and handle conflicts */ + /** Try to distribute `|` inside type, detect and handle conflicts + * Note that, unlike for `&`, a disjunction cannot be pushed into + * a refined or applied type. Example: + * + * List[T] | List[U] is not the same as List[T | U]. + * + * The rhs is a proper supertype of the lhs. + */ private def distributeOr(tp1: Type, tp2: Type): Type = tp1 match { - case tp1: RefinedType => - tp2 match { - case tp2: RefinedType if tp1.refinedName == tp2.refinedName => - tp1.derivedRefinedType( - tp1.parent | tp2.parent, - tp1.refinedName, - tp1.refinedInfo | tp2.refinedInfo.substRefinedThis(tp2, RefinedThis(tp1))) - case _ => - NoType - } case tp1: TypeBounds => tp2 match { case tp2: TypeBounds => tp1 | tp2 @@ -1325,12 +1321,12 @@ class ExplainingTypeComparer(initctx: Context) extends TypeComparer(initctx) { override def copyIn(ctx: Context) = new ExplainingTypeComparer(ctx) - override def compareHK(projection: NamedType, other: Type, inOrder: Boolean) = + override def compareHkApply(projection: NamedType, other: Type, inOrder: Boolean) = if (projection.name == tpnme.hkApply) traceIndented(i"compareHK $projection, $other, $inOrder") { - super.compareHK(projection, other, inOrder) + super.compareHkApply(projection, other, inOrder) } - else super.compareHK(projection, other, inOrder) + else super.compareHkApply(projection, other, inOrder) override def toString = "Subtype trace:" + { try b.toString finally b.clear() } } diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 21b74e07b..624549bac 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1533,19 +1533,49 @@ object Types { ctx.underlyingRecursions -= 1 } + /** A selection of the same kind, but with potentially a differet prefix. + * The following normalizations are performed for type selections T#A: + * + * T#A --> B if A is bound to an alias `= B` in T + * + * (S & T)#A --> S#A if T does not have a member namd A + * --> T#A if S does not have a member namd A + * --> S#A & T#A otherwise + * (S | T)#A --> S#A | T#A + */ def derivedSelect(prefix: Type)(implicit ctx: Context): Type = if (prefix eq this.prefix) this - else { + else if (isType) { val res = prefix.lookupRefined(name) if (res.exists) res - else if (name == tpnme.hkApply && prefix.classNotLambda) { + else if (name == tpnme.hkApply && prefix.classNotLambda) // After substitution we might end up with a type like // `C { type hk$0 = T0; ...; type hk$n = Tn } # $Apply` // where C is a class. In that case we eta expand `C`. derivedSelect(prefix.EtaExpandCore(this.prefix.typeConstructor.typeParams)) - } + else if (Config.splitProjections) + prefix match { + case prefix: AndType => + def isMissing(tp: Type) = tp match { + case tp: TypeRef => !tp.info.exists + case _ => false + } + val derived1 = derivedSelect(prefix.tp1) + val derived2 = derivedSelect(prefix.tp2) + return ( + if (isMissing(derived1)) derived2 + else if (isMissing(derived2)) derived1 + else prefix.derivedAndType(derived1, derived2)) + case prefix: OrType => + val derived1 = derivedSelect(prefix.tp1) + val derived2 = derivedSelect(prefix.tp2) + return prefix.derivedOrType(derived1, derived2) + case _ => + newLikeThis(prefix) + } else newLikeThis(prefix) } + else newLikeThis(prefix) /** Create a NamedType of the same kind as this type, but with a new prefix. */ @@ -2774,7 +2804,7 @@ object Types { } override def toString = - if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)" + if (lo eq hi) s"TypeAlias($lo, $variance)" else s"TypeBounds($lo, $hi)" } class RealTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi) { diff --git a/src/dotty/tools/dotc/printing/PlainPrinter.scala b/src/dotty/tools/dotc/printing/PlainPrinter.scala index 9e5ab5d8c..8f9d70d4c 100644 --- a/src/dotty/tools/dotc/printing/PlainPrinter.scala +++ b/src/dotty/tools/dotc/printing/PlainPrinter.scala @@ -170,7 +170,8 @@ class PlainPrinter(_ctx: Context) extends Printer { val bounds = if (constr.contains(tp)) constr.fullBounds(tp.origin)(ctx.addMode(Mode.Printing)) else TypeBounds.empty - "(" ~ toText(tp.origin) ~ "?" ~ toText(bounds) ~ ")" + if (ctx.settings.YshowVarBounds.value) "(" ~ toText(tp.origin) ~ "?" ~ toText(bounds) ~ ")" + else toText(tp.origin) } case tp: LazyRef => "LazyRef(" ~ toTextGlobal(tp.ref) ~ ")" diff --git a/src/dotty/tools/dotc/transform/Splitter.scala b/src/dotty/tools/dotc/transform/Splitter.scala index 62a080f37..410b412e0 100644 --- a/src/dotty/tools/dotc/transform/Splitter.scala +++ b/src/dotty/tools/dotc/transform/Splitter.scala @@ -47,7 +47,10 @@ class Splitter extends MiniPhaseTransform { thisTransform => if (!mbr.isOverloaded) mbr.asSingleDenotation else tree.tpe match { case tref: TermRefWithSignature => mbr.atSignature(tref.sig) - case _ => ctx.error(s"cannot disambiguate overloaded member $mbr"); NoDenotation + case _ => + def alts = mbr.alternatives.map(alt => i"$alt: ${alt.info}").mkString(", ") + ctx.error(s"cannot disambiguate overloaded members $alts", tree.pos) + NoDenotation } } diff --git a/src/dotty/tools/dotc/typer/TypeAssigner.scala b/src/dotty/tools/dotc/typer/TypeAssigner.scala index 2b7eb3936..42ee513cd 100644 --- a/src/dotty/tools/dotc/typer/TypeAssigner.scala +++ b/src/dotty/tools/dotc/typer/TypeAssigner.scala @@ -282,7 +282,7 @@ trait TypeAssigner { else if (!mix.isEmpty) findMixinSuper(cls.info) else if (inConstrCall || ctx.erasedTypes) cls.info.firstParent else { - val ps = cls.info.parents + val ps = cls.classInfo.instantiatedParents if (ps.isEmpty) defn.AnyType else ps.reduceLeft((x: Type, y: Type) => x & y) } tree.withType(SuperType(cls.thisType, owntype)) |