diff options
| -rw-r--r-- | src/dotty/tools/dotc/core/ConstraintHandling.scala | 15 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/StdNames.scala | 1 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TypeOps.scala | 128 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 46 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/typer/Namer.scala | 2 |
5 files changed, 110 insertions, 82 deletions
diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala index 5911af72c..84f531385 100644 --- a/src/dotty/tools/dotc/core/ConstraintHandling.scala +++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -35,6 +35,15 @@ trait ConstraintHandling { /** If the constraint is frozen we cannot add new bounds to the constraint. */ protected var frozenConstraint = false + protected var alwaysFluid = false + + /** Perform `op` in a mode where all attempts to set `frozen` to true are ignored */ + def fluidly[T](op: => T): T = { + val saved = alwaysFluid + alwaysFluid = true + try op finally alwaysFluid = saved + } + /** We are currently comparing lambdas. Used as a flag for * optimization: when `false`, no need to do an expensive `pruneLambdaParams` */ @@ -126,14 +135,14 @@ trait ConstraintHandling { final def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { val saved = frozenConstraint - frozenConstraint = true + frozenConstraint = !alwaysFluid try isSubType(tp1, tp2) finally frozenConstraint = saved } final def isSameTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { val saved = frozenConstraint - frozenConstraint = true + frozenConstraint = !alwaysFluid try isSameType(tp1, tp2) finally frozenConstraint = saved } @@ -219,7 +228,7 @@ trait ConstraintHandling { // 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 + inst = ctx.harmonizeUnion(inst) // 3. If instance is from below, and upper bound has open named parameters // make sure the instance has all named parameters of the bound. diff --git a/src/dotty/tools/dotc/core/StdNames.scala b/src/dotty/tools/dotc/core/StdNames.scala index c52264637..920c9635e 100644 --- a/src/dotty/tools/dotc/core/StdNames.scala +++ b/src/dotty/tools/dotc/core/StdNames.scala @@ -429,7 +429,6 @@ object StdNames { val isEmpty: N = "isEmpty" val isInstanceOf_ : N = "isInstanceOf" val java: N = "java" - val keepUnions: N = "keepUnions" val key: N = "key" val lang: N = "lang" val length: N = "length" diff --git a/src/dotty/tools/dotc/core/TypeOps.scala b/src/dotty/tools/dotc/core/TypeOps.scala index bee69ae69..5edd61c70 100644 --- a/src/dotty/tools/dotc/core/TypeOps.scala +++ b/src/dotty/tools/dotc/core/TypeOps.scala @@ -173,21 +173,53 @@ trait TypeOps { this: Context => // TODO: Make standalone object. } /** Approximate union type by intersection of its dominators. - * See Type#approximateUnion for an explanation. + * That is, replace a union type Tn | ... | Tn + * by the smallest intersection type of base-class 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(tp: Type): Type = { + def orDominator(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) } + + def mergeRefined(tp1: Type, tp2: Type): Type = { + def fail = throw new AssertionError(i"Failure to join alternatives $tp1 and $tp2") + tp1 match { + case tp1 @ RefinedType(parent1, name1, rinfo1) => + tp2 match { + case RefinedType(parent2, `name1`, rinfo2) => + tp1.derivedRefinedType( + mergeRefined(parent1, parent2), name1, rinfo1 | rinfo2) + case _ => fail + } + case tp1 @ TypeRef(pre1, name1) => + tp2 match { + case tp2 @ TypeRef(pre2, `name1`) => + tp1.derivedSelect(pre1 | pre2) + case _ => fail + } + case _ => fail + } + } + def approximateOr(tp1: Type, tp2: Type): Type = { def isClassRef(tp: Type): Boolean = tp match { case tp: TypeRef => tp.symbol.isClass @@ -195,78 +227,70 @@ trait TypeOps { this: Context => // TODO: Make standalone object. case _ => false } - /** If `tp1` and `tp2` are typebounds, try to make one fit into the other - * or to make them equal, by instantiating uninstantiated type variables. - */ - def homogenizedUnion(tp1: Type, tp2: Type): Type = { - tp1 match { - case tp1: TypeBounds => - tp2 match { - case tp2: TypeBounds => - def fitInto(tp1: TypeBounds, tp2: TypeBounds): Unit = { - val nestedCtx = ctx.fresh.setNewTyperState - if (tp2.boundsInterval.contains(tp1.boundsInterval)(nestedCtx)) - nestedCtx.typerState.commit() - } - fitInto(tp1, tp2) - fitInto(tp2, tp1) - case _ => - } - case _ => - } - tp1 | tp2 - } - - tp1 match { - case tp1: RefinedType => - tp2 match { - case tp2: RefinedType if tp1.refinedName == tp2.refinedName => - return tp1.derivedRefinedType( - approximateUnion(OrType(tp1.parent, tp2.parent)), - tp1.refinedName, - homogenizedUnion(tp1.refinedInfo, tp2.refinedInfo)) - //.ensuring { x => println(i"approx or $tp1 | $tp2 = $x\n constr = ${ctx.typerState.constraint}"); true } // DEBUG - case _ => - } - case _ => - } - tp1 match { case tp1: RecType => tp1.rebind(approximateOr(tp1.parent, tp2)) case tp1: TypeProxy if !isClassRef(tp1) => - approximateUnion(tp1.superType | tp2) + orDominator(tp1.superType | tp2) case _ => tp2 match { case tp2: RecType => tp2.rebind(approximateOr(tp1, tp2.parent)) case tp2: TypeProxy if !isClassRef(tp2) => - approximateUnion(tp1 | tp2.superType) + orDominator(tp1 | tp2.superType) case _ => val commonBaseClasses = tp.mapReduceOr(_.baseClasses)(intersect) val doms = dominators(commonBaseClasses, Nil) - def baseTp(cls: ClassSymbol): Type = - if (tp1.typeParams.nonEmpty) tp.baseTypeRef(cls) - else tp.baseTypeWithArgs(cls) + def baseTp(cls: ClassSymbol): Type = { + val base = + if (tp1.typeParams.nonEmpty) tp.baseTypeRef(cls) + else tp.baseTypeWithArgs(cls) + base.mapReduceOr(identity)(mergeRefined) + } doms.map(baseTp).reduceLeft(AndType.apply) } } } - if (ctx.featureEnabled(defn.LanguageModuleClass, nme.keepUnions)) tp - else tp match { + + tp match { case tp: OrType => - approximateOr(tp.tp1, tp.tp2) // Maybe refactor using liftToRec? - 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: RecType => - tp.rebind(approximateUnion(tp.parent)) + approximateOr(tp.tp1, tp.tp2) case _ => tp } } + /** Given a disjunction T1 | ... | Tn of types with potentially embedded + * type variables, constrain type variables further if this eliminates + * some of the branches of the disjunction. Do this also for disjunctions + * embedded in intersections, as parents in refinements, and in recursive types. + * + * For instance, if `A` is an unconstrained type variable, then + * + * ArrayBuffer[Int] | ArrayBuffer[A] + * + * is approximated by constraining `A` to be =:= to `Int` and returning `ArrayBuffer[Int]` + * instead of `ArrayBuffer[_ >: Int | A <: Int & A]` + */ + def harmonizeUnion(tp: Type): Type = tp match { + case tp: OrType => + joinIfScala2(typeComparer.fluidly(tp.tp1 | tp.tp2)) + case tp @ AndType(tp1, tp2) => + tp derived_& (harmonizeUnion(tp1), harmonizeUnion(tp2)) + case tp: RefinedType => + tp.derivedRefinedType(harmonizeUnion(tp.parent), tp.refinedName, tp.refinedInfo) + case tp: RecType => + tp.rebind(harmonizeUnion(tp.parent)) + case _ => + tp + } + + /** Under -language:Scala2: Replace or-types with their joins */ + private def joinIfScala2(tp: Type) = tp match { + case tp: OrType if scala2Mode => tp.join + case _ => tp + } + /** Not currently needed: * def liftToRec(f: (Type, Type) => Type)(tp1: Type, tp2: Type)(implicit ctx: Context) = { diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 2f1b6b829..0f81f8c38 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -436,8 +436,12 @@ object Types { tp.cls.findMember(name, pre, excluded) case AndType(l, r) => goAnd(l, r) - case OrType(l, r) => - goOr(l, r) + case tp: OrType => + // we need to keep the invariant that `pre <: tp`. Branch `union-types-narrow-prefix` + // achieved that by narrowing `pre` to each alternative, but it led to merge errors in + // lots of places. The present strategy is instead of widen `tp` using `join` to be a + // supertype of `pre`. + go(tp.join) case tp: JavaArrayType => defn.ObjectType.findMember(name, pre, excluded) case ErrorType => @@ -556,7 +560,6 @@ object Types { def goAnd(l: Type, r: Type) = { go(l) & (go(r), pre, safeIntersection = ctx.pendingMemberSearches.contains(name)) } - def goOr(l: Type, r: Type) = go(l) | (go(r), pre) { val recCount = ctx.findMemberCount + 1 ctx.findMemberCount = recCount @@ -1230,28 +1233,6 @@ 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` - * - * As a second measure we also homogenize refinements containing - * type variables. For instance, if `A` is an instantiatable type variable, - * then - * - * ArrayBuffer[Int] | ArrayBuffer[A] - * - * is approximated by instantiating `A` to `Int` and returning `ArrayBuffer[Int]` - * instead of `ArrayBuffer[_ >: Int | A <: Int & A]` - */ - 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. @@ -2233,9 +2214,24 @@ object Types { } abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType { + assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType]) def isAnd = false + private[this] var myJoin: Type = _ + private[this] var myJoinPeriod: Period = Nowhere + + /** Replace or type by the closest non-or type above it */ + def join(implicit ctx: Context): Type = { + if (myJoinPeriod != ctx.period) { + myJoin = ctx.orDominator(this) + core.println(i"join of $this == $myJoin") + assert(myJoin != this) + myJoinPeriod = ctx.period + } + myJoin + } + def derivedOrType(tp1: Type, tp2: Type)(implicit ctx: Context): Type = if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this else OrType.make(tp1, tp2) diff --git a/src/dotty/tools/dotc/typer/Namer.scala b/src/dotty/tools/dotc/typer/Namer.scala index 4f4278468..00e92cbfb 100644 --- a/src/dotty/tools/dotc/typer/Namer.scala +++ b/src/dotty/tools/dotc/typer/Namer.scala @@ -898,7 +898,7 @@ class Namer { typer: Typer => // definition is inline (i.e. final in Scala2). def widenRhs(tp: Type): Type = tp.widenTermRefExpr match { case tp: ConstantType if isInline => tp - case _ => tp.widen.approximateUnion + case _ => ctx.harmonizeUnion(tp.widen) } // Replace aliases to Unit by Unit itself. If we leave the alias in |