diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/dotty/tools/dotc/core/TypeOps.scala | 31 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 47 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/typer/Namer.scala | 2 |
3 files changed, 78 insertions, 2 deletions
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 } |