From 4611bdf0972fc01dfdfa647a0e84e3bccf98ea05 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sat, 8 Mar 2014 19:05:54 +0100 Subject: Appromiximate union types by intersections. Appromiximate union types by intersections of their common base classes. Controlled by option -Xkeep-unions. If option is set, no approximation is done. Motivations for approximating: There are two. First, union types are departure from Scala 2. From time to time they lead to failure of inference. One example experiences in Dotty was in a foldLeft, where the accumulator type was inferred to be Tree before and was now a union of two tree specific kinds. Tree was the correct type, whereas the union type was too specific. These failures are not common (in the Dotty codebase there were 3, I believe), but they cause considerable difficulty to diagnose. So it seems safer to have a compatibility mode with Scala 2. The second motivation is that union types can become large and unwieldy. A function like TreeCopier has a result type consisting of ~ 40 alternatives, where the alternative type would be just Tree. Once we gain more experience with union types, we might consider flipping the option, and making union types the default. But for now it is safer this way, I believe. --- src/dotty/tools/dotc/core/TypeOps.scala | 31 ++++++++++++++++++++++ src/dotty/tools/dotc/core/Types.scala | 47 ++++++++++++++++++++++++++++++++- src/dotty/tools/dotc/typer/Namer.scala | 2 +- 3 files changed, 78 insertions(+), 2 deletions(-) (limited to 'src/dotty/tools') diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index 22a86766b..f9ff42709 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -77,6 +77,37 @@ trait TypeOps { this: Context => def apply(tp: Type) = simplify(tp, this) } + /** Approximate union type by intersection of its dominators. + * See Type#approximateUnion for an explanation. + */ + def approximateUnion(tp: Type): Type = { + /** a faster version of cs1 intersect cs2 */ + def intersect(cs1: List[ClassSymbol], cs2: List[ClassSymbol]): List[ClassSymbol] = { + val cs2AsSet = new util.HashSet[ClassSymbol](100) + cs2.foreach(cs2AsSet.addEntry) + cs1.filter(cs2AsSet.contains) + } + /** The minimal set of classes in `cs` which derive all other classes in `cs` */ + def dominators(cs: List[ClassSymbol], accu: List[ClassSymbol]): List[ClassSymbol] = (cs: @unchecked) match { + case c :: rest => + val accu1 = if (accu exists (_ derivesFrom c)) accu else c :: accu + if (cs == c.baseClasses) accu1 else dominators(rest, accu1) + } + if (ctx.featureEnabled(defn.LanguageModuleClass, nme.keepUnions)) tp + else tp match { + case tp: OrType => + val commonBaseClasses = tp.mapReduceOr(_.baseClasses)(intersect) + val doms = dominators(commonBaseClasses, Nil) + doms.map(tp.baseTypeWithArgs).reduceLeft(AndType.apply) + case tp @ AndType(tp1, tp2) => + tp derived_& (approximateUnion(tp1), approximateUnion(tp2)) + case tp: RefinedType => + tp.derivedRefinedType(approximateUnion(tp.parent), tp.refinedName, tp.refinedInfo) + case _ => + tp + } + } + /** A type is volatile if its DNF contains an alternative of the form * {P1, ..., Pn}, {N1, ..., Nk}, where the Pi are parent typerefs and the * Nj are refinement names, and one the 4 following conditions is met: diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index b06a95dc7..9b5e02186 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -845,6 +845,19 @@ object Types { */ def simplified(implicit ctx: Context) = ctx.simplify(this, null) + /** Approximations of union types: We replace a union type Tn | ... | Tn + * by the smallest intersection type of baseclass instances of T1,...,Tn. + * Example: Given + * + * trait C[+T] + * trait D + * class A extends C[A] with D + * class B extends C[B] with D with E + * + * we approximate `A | B` by `C[A | B] with D` + */ + def approximateUnion(implicit ctx: Context) = ctx.approximateUnion(this) + /** customized hash code of this type. * NotCached for uncached types. Cached types * compute hash and use it as the type's hashCode. @@ -1355,6 +1368,10 @@ object Types { if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this else AndType.make(tp1, tp2) + def derived_& (tp1: Type, tp2: Type)(implicit ctx: Context): Type = + if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this + else tp1 & tp2 + def derivedAndOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type = derivedAndType(tp1, tp2) @@ -1735,10 +1752,38 @@ object Types { case OrType(tp1, tp2) => isSingleton(tp1) & isSingleton(tp2) case _ => false } + def isFullyDefined(tp: Type): Boolean = tp match { + case tp: TypeVar => tp.isInstantiated && isFullyDefined(tp.instanceOpt) + case tp: TypeProxy => isFullyDefined(tp.underlying) + case tp: AndOrType => isFullyDefined(tp.tp1) && isFullyDefined(tp.tp2) + case _ => true + } + def isOrType(tp: Type): Boolean = tp.stripTypeVar.dealias match { + case tp: OrType => true + case AndType(tp1, tp2) => isOrType(tp1) | isOrType(tp2) + case RefinedType(parent, _) => isOrType(parent) + case WildcardType(bounds: TypeBounds) => isOrType(bounds.hi) + case _ => false + } + + // First, solve the constraint. var inst = ctx.typeComparer.approximation(origin, fromBelow) + + // Then, approximate by (1.) and (2.) and simplify as follows. + // 1. If instance is from below and is a singleton type, yet + // upper bound is not a singleton type, widen the instance. if (fromBelow && isSingleton(inst) && !isSingleton(upperBound)) inst = inst.widen - instantiateWith(inst.simplified) + + inst = inst.simplified + + // 2. If instance is from below and is a fully-defined union type, yet upper bound + // is not a union type, approximate the union type from above by an intersection + // of all common base types. + if (fromBelow && isOrType(inst) && isFullyDefined(inst) && !isOrType(upperBound)) + inst = inst.approximateUnion + + instantiateWith(inst) } /** Unwrap to instance (if instantiated) or origin (if not), until result diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index 2c5022726..c318ddf36 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -576,7 +576,7 @@ class Namer { typer: Typer => // println(s"final inherited for $sym: ${inherited.toString}") !!! // println(s"owner = ${sym.owner}, decls = ${sym.owner.info.decls.show}") val rhsCtx = ctx.fresh addMode Mode.InferringReturnType - def rhsType = typedAheadExpr(mdef.rhs, rhsProto)(rhsCtx).tpe.widen + def rhsType = typedAheadExpr(mdef.rhs, rhsProto)(rhsCtx).tpe.widen.approximateUnion def lhsType = fullyDefinedType(rhsType, "right-hand side", mdef.pos) inherited orElse lhsType } -- cgit v1.2.3