From 8a61ff432543a29234193cd1f7c14abd3f3d31a0 Mon Sep 17 00:00:00 2001 From: Felix Mulder Date: Wed, 2 Nov 2016 11:08:28 +0100 Subject: Move compiler and compiler tests to compiler dir --- .../dotty/tools/dotc/core/ConstraintHandling.scala | 458 +++++++++++++++++++++ 1 file changed, 458 insertions(+) create mode 100644 compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala (limited to 'compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala') diff --git a/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala b/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala new file mode 100644 index 000000000..0e155b9e1 --- /dev/null +++ b/compiler/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -0,0 +1,458 @@ +package dotty.tools +package dotc +package core + +import Types._, Contexts._, Symbols._ +import Decorators._ +import config.Config +import config.Printers.{constr, typr} +import TypeApplications.EtaExpansion +import collection.mutable + +/** Methods for adding constraints and solving them. + * + * What goes into a Constraint as opposed to a ConstrainHandler? + * + * Constraint code is purely functional: Operations get constraints and produce new ones. + * Constraint code does not have access to a type-comparer. Anything regarding lubs and glbs has to be done + * elsewhere. + * + * By comparison: Constraint handlers are parts of type comparers and can use their functionality. + * Constraint handlers update the current constraint as a side effect. + */ +trait ConstraintHandling { + + implicit val ctx: Context + + protected def isSubType(tp1: Type, tp2: Type): Boolean + protected def isSameType(tp1: Type, tp2: Type): Boolean + + val state: TyperState + import state.constraint + + private var addConstraintInvocations = 0 + + /** 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 polytypes. Used as a flag for + * optimization: when `false`, no need to do an expensive `pruneLambdaParams` + */ + protected var comparedPolyTypes: Set[PolyType] = Set.empty + + private def addOneBound(param: PolyParam, bound: Type, isUpper: Boolean): Boolean = + !constraint.contains(param) || { + def occursIn(bound: Type): Boolean = { + val b = bound.dealias + (b eq param) || { + b match { + case b: AndOrType => occursIn(b.tp1) || occursIn(b.tp2) + case b: TypeVar => occursIn(b.origin) + case _ => false + } + } + } + if (Config.checkConstraintsSeparated) + assert(!occursIn(bound), s"$param occurs in $bound") + val c1 = constraint.narrowBound(param, bound, isUpper) + (c1 eq constraint) || { + constraint = c1 + val TypeBounds(lo, hi) = constraint.entry(param) + isSubType(lo, hi) + } + } + + protected def addUpperBound(param: PolyParam, bound: Type): Boolean = { + def description = i"constraint $param <: $bound to\n$constraint" + if (bound.isRef(defn.NothingClass) && ctx.typerState.isGlobalCommittable) { + def msg = s"!!! instantiated to Nothing: $param, constraint = ${constraint.show}" + if (Config.failOnInstantiationToNothing) assert(false, msg) + else ctx.log(msg) + } + constr.println(i"adding $description") + val lower = constraint.lower(param) + val res = + addOneBound(param, bound, isUpper = true) && + lower.forall(addOneBound(_, bound, isUpper = true)) + constr.println(i"added $description = $res") + res + } + + protected def addLowerBound(param: PolyParam, bound: Type): Boolean = { + def description = i"constraint $param >: $bound to\n$constraint" + constr.println(i"adding $description") + val upper = constraint.upper(param) + val res = + addOneBound(param, bound, isUpper = false) && + upper.forall(addOneBound(_, bound, isUpper = false)) + constr.println(i"added $description = $res") + res + } + + protected def addLess(p1: PolyParam, p2: PolyParam): Boolean = { + def description = i"ordering $p1 <: $p2 to\n$constraint" + val res = + if (constraint.isLess(p2, p1)) unify(p2, p1) + else { + val down1 = p1 :: constraint.exclusiveLower(p1, p2) + val up2 = p2 :: constraint.exclusiveUpper(p2, p1) + val lo1 = constraint.nonParamBounds(p1).lo + val hi2 = constraint.nonParamBounds(p2).hi + constr.println(i"adding $description down1 = $down1, up2 = $up2") + constraint = constraint.addLess(p1, p2) + down1.forall(addOneBound(_, hi2, isUpper = true)) && + up2.forall(addOneBound(_, lo1, isUpper = false)) + } + constr.println(i"added $description = $res") + res + } + + /** Make p2 = p1, transfer all bounds of p2 to p1 + * @pre less(p1)(p2) + */ + private def unify(p1: PolyParam, p2: PolyParam): Boolean = { + constr.println(s"unifying $p1 $p2") + assert(constraint.isLess(p1, p2)) + val down = constraint.exclusiveLower(p2, p1) + val up = constraint.exclusiveUpper(p1, p2) + constraint = constraint.unify(p1, p2) + val bounds = constraint.nonParamBounds(p1) + val lo = bounds.lo + val hi = bounds.hi + isSubType(lo, hi) && + down.forall(addOneBound(_, hi, isUpper = true)) && + up.forall(addOneBound(_, lo, isUpper = false)) + } + + final def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { + val saved = frozenConstraint + frozenConstraint = !alwaysFluid + try isSubType(tp1, tp2) + finally frozenConstraint = saved + } + + final def isSameTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { + val saved = frozenConstraint + frozenConstraint = !alwaysFluid + try isSameType(tp1, tp2) + finally frozenConstraint = saved + } + + /** Test whether the lower bounds of all parameters in this + * constraint are a solution to the constraint. + */ + protected final def isSatisfiable: Boolean = + constraint.forallParams { param => + val TypeBounds(lo, hi) = constraint.entry(param) + isSubType(lo, hi) || { + ctx.log(i"sub fail $lo <:< $hi") + false + } + } + + /** Solve constraint set for given type parameter `param`. + * If `fromBelow` is true the parameter is approximated by its lower bound, + * otherwise it is approximated by its upper bound. However, any occurrences + * of the parameter in a refinement somewhere in the bound are removed. Also + * wildcard types in bounds are approximated by their upper or lower bounds. + * (Such occurrences can arise for F-bounded types). + * The constraint is left unchanged. + * @return the instantiating type + * @pre `param` is in the constraint's domain. + */ + final def approximation(param: PolyParam, fromBelow: Boolean): Type = { + val avoidParam = new TypeMap { + override def stopAtStatic = true + def apply(tp: Type) = mapOver { + tp match { + case tp: RefinedType if param occursIn tp.refinedInfo => tp.parent + case tp: WildcardType => + val bounds = tp.optBounds.orElse(TypeBounds.empty).bounds + // Try to instantiate the wildcard to a type that is known to conform to it. + // This means: + // If fromBelow is true, we minimize the type overall + // Hence, if variance < 0, pick the maximal safe type: bounds.lo + // (i.e. the whole bounds range is over the type) + // if variance > 0, pick the minimal safe type: bounds.hi + // (i.e. the whole bounds range is under the type) + // if variance == 0, pick bounds.lo anyway (this is arbitrary but in line with + // the principle that we pick the smaller type when in doubt). + // If fromBelow is false, we maximize the type overall and reverse the bounds + // if variance != 0. For variance == 0, we still minimize. + // In summary we pick the bound given by this table: + // + // variance | -1 0 1 + // ------------------------ + // from below | lo lo hi + // from above | hi lo lo + // + if (variance == 0 || fromBelow == (variance < 0)) bounds.lo else bounds.hi + case _ => tp + } + } + } + assert(constraint.contains(param)) + val bound = if (fromBelow) constraint.fullLowerBound(param) else constraint.fullUpperBound(param) + val inst = avoidParam(bound) + typr.println(s"approx ${param.show}, from below = $fromBelow, bound = ${bound.show}, inst = ${inst.show}") + inst + } + + /** The instance type of `param` in the current constraint (which contains `param`). + * If `fromBelow` is true, the instance type is the lub of the parameter's + * lower bounds; otherwise it is the glb of its upper bounds. However, + * a lower bound instantiation can be a singleton type only if the upper bound + * is also a singleton type. + */ + def instanceType(param: PolyParam, fromBelow: Boolean): Type = { + def upperBound = constraint.fullUpperBound(param) + def isSingleton(tp: Type): Boolean = tp match { + case tp: SingletonType => true + case AndType(tp1, tp2) => isSingleton(tp1) | isSingleton(tp2) + 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 tp: RefinedOrRecType => isOrType(tp.parent) + case AndType(tp1, tp2) => isOrType(tp1) | isOrType(tp2) + case WildcardType(bounds: TypeBounds) => isOrType(bounds.hi) + case _ => false + } + + // First, solve the constraint. + var inst = approximation(param, fromBelow) + + // Then, approximate by (1.) - (3.) 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 + + 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 = 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. + if (fromBelow) inst = inst.widenToNamedTypeParams(param.namedTypeParams) + inst + } + + /** Constraint `c1` subsumes constraint `c2`, if under `c2` as constraint we have + * for all poly params `p` defined in `c2` as `p >: L2 <: U2`: + * + * c1 defines p with bounds p >: L1 <: U1, and + * L2 <: L1, and + * U1 <: U2 + * + * Both `c1` and `c2` are required to derive from constraint `pre`, possibly + * narrowing it with further bounds. + */ + protected final def subsumes(c1: Constraint, c2: Constraint, pre: Constraint): Boolean = + if (c2 eq pre) true + else if (c1 eq pre) false + else { + val saved = constraint + try + c2.forallParams(p => + c1.contains(p) && + c2.upper(p).forall(c1.isLess(p, _)) && + isSubTypeWhenFrozen(c1.nonParamBounds(p), c2.nonParamBounds(p))) + finally constraint = saved + } + + /** The current bounds of type parameter `param` */ + final def bounds(param: PolyParam): TypeBounds = { + val e = constraint.entry(param) + if (e.exists) e.bounds else param.binder.paramBounds(param.paramNum) + } + + /** Add polytype `pt`, possibly with type variables `tvars`, to current constraint + * and propagate all bounds. + * @param tvars See Constraint#add + */ + def addToConstraint(pt: PolyType, tvars: List[TypeVar]): Unit = + assert { + checkPropagated(i"initialized $pt") { + constraint = constraint.add(pt, tvars) + pt.paramNames.indices.forall { i => + val param = PolyParam(pt, i) + val bounds = constraint.nonParamBounds(param) + val lower = constraint.lower(param) + val upper = constraint.upper(param) + if (lower.nonEmpty && !bounds.lo.isRef(defn.NothingClass) || + upper.nonEmpty && !bounds.hi.isRef(defn.AnyClass)) constr.println(i"INIT*** $pt") + lower.forall(addOneBound(_, bounds.hi, isUpper = true)) && + upper.forall(addOneBound(_, bounds.lo, isUpper = false)) + } + } + } + + /** Can `param` be constrained with new bounds? */ + final def canConstrain(param: PolyParam): Boolean = + !frozenConstraint && (constraint contains param) + + /** Add constraint `param <: bound` if `fromBelow` is false, `param >: bound` otherwise. + * `bound` is assumed to be in normalized form, as specified in `firstTry` and + * `secondTry` of `TypeComparer`. In particular, it should not be an alias type, + * lazy ref, typevar, wildcard type, error type. In addition, upper bounds may + * not be AndTypes and lower bounds may not be OrTypes. This is assured by the + * way isSubType is organized. + */ + protected def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { + def description = i"constr $param ${if (fromBelow) ">:" else "<:"} $bound:\n$constraint" + //checkPropagated(s"adding $description")(true) // DEBUG in case following fails + checkPropagated(s"added $description") { + addConstraintInvocations += 1 + + /** When comparing lambdas we might get constraints such as + * `A <: X0` or `A = List[X0]` where `A` is a constrained parameter + * and `X0` is a lambda parameter. The constraint for `A` is not allowed + * to refer to such a lambda parameter because the lambda parameter is + * not visible where `A` is defined. Consequently, we need to + * approximate the bound so that the lambda parameter does not appear in it. + * If `tp` is an upper bound, we need to approximate with something smaller, + * otherwise something larger. + * Test case in pos/i94-nada.scala. This test crashes with an illegal instance + * error in Test2 when the rest of the SI-2712 fix is applied but `pruneLambdaParams` is + * missing. + */ + def pruneLambdaParams(tp: Type) = + if (comparedPolyTypes.nonEmpty) { + val approx = new ApproximatingTypeMap { + def apply(t: Type): Type = t match { + case t @ PolyParam(pt: PolyType, n) if comparedPolyTypes contains pt => + val effectiveVariance = if (fromBelow) -variance else variance + val bounds = pt.paramBounds(n) + if (effectiveVariance > 0) bounds.lo + else if (effectiveVariance < 0) bounds.hi + else NoType + case _ => + mapOver(t) + } + } + approx(tp) + } + else tp + + def addParamBound(bound: PolyParam) = + if (fromBelow) addLess(bound, param) else addLess(param, bound) + + /** Drop all constrained parameters that occur at the toplevel in `bound` and + * handle them by `addLess` calls. + * The preconditions make sure that such parameters occur only + * in one of two ways: + * + * 1. + * + * P <: Ts1 | ... | Tsm (m > 0) + * Tsi = T1 & ... Tn (n >= 0) + * Some of the Ti are constrained parameters + * + * 2. + * + * Ts1 & ... & Tsm <: P (m > 0) + * Tsi = T1 | ... | Tn (n >= 0) + * Some of the Ti are constrained parameters + * + * In each case we cannot leave the parameter in place, + * because that would risk making a parameter later a subtype or supertype + * of a bound where the parameter occurs again at toplevel, which leads to cycles + * in the subtyping test. So we intentionally narrow the constraint by + * recording an isLess relationship instead (even though this is not implied + * by the bound). + * + * Narrowing a constraint is better than widening it, because narrowing leads + * to incompleteness (which we face anyway, see for instance eitherIsSubType) + * but widening leads to unsoundness. + * + * A test case that demonstrates the problem is i864.scala. + * Turn Config.checkConstraintsSeparated on to get an accurate diagnostic + * of the cycle when it is created. + * + * @return The pruned type if all `addLess` calls succeed, `NoType` otherwise. + */ + def prune(bound: Type): Type = bound match { + case bound: AndOrType => + val p1 = prune(bound.tp1) + val p2 = prune(bound.tp2) + if (p1.exists && p2.exists) bound.derivedAndOrType(p1, p2) + else NoType + case bound: TypeVar if constraint contains bound.origin => + prune(bound.underlying) + case bound: PolyParam => + constraint.entry(bound) match { + case NoType => pruneLambdaParams(bound) + case _: TypeBounds => + if (!addParamBound(bound)) NoType + else if (fromBelow) defn.NothingType + else defn.AnyType + case inst => + prune(inst) + } + case _ => + pruneLambdaParams(bound) + } + + try bound match { + case bound: PolyParam if constraint contains bound => + addParamBound(bound) + case _ => + val pbound = prune(bound) + pbound.exists && ( + if (fromBelow) addLowerBound(param, pbound) else addUpperBound(param, pbound)) + } + finally addConstraintInvocations -= 1 + } + } + + /** Instantiate `param` to `tp` if the constraint stays satisfiable */ + protected def tryInstantiate(param: PolyParam, tp: Type): Boolean = { + val saved = constraint + constraint = + if (addConstraint(param, tp, fromBelow = true) && + addConstraint(param, tp, fromBelow = false)) constraint.replace(param, tp) + else saved + constraint ne saved + } + + /** Check that constraint is fully propagated. See comment in Config.checkConstraintsPropagated */ + def checkPropagated(msg: => String)(result: Boolean): Boolean = { + if (Config.checkConstraintsPropagated && result && addConstraintInvocations == 0) { + val saved = frozenConstraint + frozenConstraint = true + for (p <- constraint.domainParams) { + def check(cond: => Boolean, q: PolyParam, ordering: String, explanation: String): Unit = + assert(cond, i"propagation failure for $p $ordering $q: $explanation\n$msg") + for (u <- constraint.upper(p)) + check(bounds(p).hi <:< bounds(u).hi, u, "<:", "upper bound not propagated") + for (l <- constraint.lower(p)) { + check(bounds(l).lo <:< bounds(p).hi, l, ">:", "lower bound not propagated") + check(constraint.isLess(l, p), l, ">:", "reverse ordering (<:) missing") + } + } + frozenConstraint = saved + } + result + } +} -- cgit v1.2.3