diff options
| -rw-r--r-- | src/dotty/tools/dotc/core/Constraint.scala | 536 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/ConstraintHandling.scala | 18 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/ConstraintRunInfo.scala | 16 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/NaiveConstraint.scala | 383 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 7 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TyperState.scala | 2 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 2 | ||||
| -rw-r--r-- | tests/pos/subtyping.scala | 13 |
8 files changed, 521 insertions, 456 deletions
diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index 86d686d37..a5c55ccce 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -10,489 +10,143 @@ import printing.Texts._ import config.Config import config.Printers._ -object Constraint { - - /** The type of `Constraint#myMap` */ - type ParamInfo = SimpleMap[PolyType, Array[Type]] - - /** The type of `Constraint#dependents */ - type DependentMap = SimpleMap[PolyType, Array[Set[PolyParam]]] - - /** The type of functions that include or exclude a `PolyParam` in or from a set*/ - private type DepDelta = (Set[PolyParam], PolyParam) => Set[PolyParam] - - private val addDep: DepDelta = (_ + _) - private val removeDep: DepDelta = (_ - _) - - private val NoTypeBounds = new TypeBounds(WildcardType, WildcardType) { - override def computeHash = unsupported("computeHash") - } - - /** An accumulator that changes dependencies on `param`. - * @param param The parameter to which changed dependencies refer. - * @param ofVariance Include `PolyParams` occurring at this variance in the dependencies. - * @param delta The dependency change to perform (add or remove). - */ - private class ChangeDependencies(param: PolyParam, ofVariance: Int, delta: DepDelta)(implicit ctx: Context) - extends TypeAccumulator[DependentMap] { - def apply(deps: DependentMap, tp: Type): DependentMap = tp match { - case tp @ PolyParam(pt, n) if - this.variance == 0 || this.variance == ofVariance => - val oldDeps = deps(pt) - val original = safeSelect(oldDeps, n) - val changed = delta(original, param) - if (original eq changed) deps - else { - val newDeps = - if (oldDeps == null) new Array[Set[PolyParam]](pt.paramBounds.length) - else oldDeps.clone - newDeps(n) = changed - deps.updated(pt, newDeps) - } - case _ => foldOver(deps, tp) - } - } - - /** `deps(n)`, except that `Set()` is returned if `deps` or `deps(n)` are null */ - private def safeSelect(deps: Array[Set[PolyParam]], n: Int) : Set[PolyParam] = - if (deps == null || deps(n) == null) Set() - else deps(n) -} - -import Constraint._ - -/** Constraint over undetermined type parameters - * @param myMap a map from PolyType to arrays. - * Each array contains twice the number of entries as there a type parameters - * in the PolyType. The first half of the array contains the type bounds that constrain the - * polytype's type parameters. The second half might contain type variables that - * track the corresponding parameters, or is left empty (filled with nulls). - * An instantiated type parameter is represented by having its instance type in - * the corresponding array entry. - * @param dependents a map from PolyTypes to arrays of Sets of PolyParams. - * The i'th set in an array corresponding to polytype `pt` contains - * those dependent `PolyParam`s `dp` that have `PolyParam(pt, i)` in their bounds in - * significant position. A position is significant if solving the - * constraint for `(pt, i)` with a type higher than its lower bound - * would lead to a constraint for `dp` that was not looser than - * the existing constraint. Specifically, it means that all poly params - * appearing covariantly in the lower bound and contravariantly in the - * upper bound, as well as all poly params appearing nonvariantly are - * significant. - * The `dependents` map is maintained and queried only of `Config.trackConstrDeps` is set. +/** Constraint over undetermined type parameters. Constraints are built + * over values of the following types: + * + * - PolyType A constraint constrains the type parameters of a set of PolyTypes + * - PolyParam The parameters of the constrained polytypes + * - TypeVar Every constrained parameter might be associated with a TypeVar + * that has the PolyParam as origin. */ -class Constraint(private val myMap: ParamInfo, - private val dependents: DependentMap) extends Showable { - +abstract class Constraint extends Showable { + + type This <: Constraint + /** Does the constraint's domain contain the type parameters of `pt`? */ - def contains(pt: PolyType): Boolean = myMap(pt) != null + def contains(pt: PolyType): Boolean /** Does the constraint's domain contain the type parameter `param`? */ - def contains(param: PolyParam): Boolean = { - val entries = myMap(param.binder) - entries != null && entries(param.paramNum).isInstanceOf[TypeBounds] - } + def contains(param: PolyParam): Boolean /** Does this constraint contain the type variable `tvar` and is it uninstantiated? */ - def contains(tvar: TypeVar): Boolean = { - val origin = tvar.origin - val entries = myMap(origin.binder) - val pnum = origin.paramNum - entries != null && isBounds(entries(pnum)) && (typeVar(entries, pnum) eq tvar) - } - - /** The number of type parameters in the given entry array */ - private def paramCount(entries: Array[Type]) = entries.length >> 1 - - /** The type variable corresponding to parameter numbered `n`, null if none was created */ - private def typeVar(entries: Array[Type], n: Int): Type = - entries(paramCount(entries) + n) - - private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds] - + def contains(tvar: TypeVar): Boolean + /** The constraint for given type parameter `param`, or NoType if `param` is not part of * the constraint domain. */ - def at(param: PolyParam): Type = { - val entries = myMap(param.binder) - if (entries == null) NoType else entries(param.paramNum) - } - - /** The constraint bounds for given type parameter `param`. - * @pre `param` is not part of the constraint domain. - */ - def bounds(param: PolyParam): TypeBounds = at(param).asInstanceOf[TypeBounds] - + def at(param: PolyParam): Type + /** The type variable corresponding to parameter `param`, or * NoType, if `param` is not in constrained or is not paired with a type variable. */ - def typeVarOfParam(param: PolyParam): Type = { - val entries = myMap(param.binder) - if (entries == null) NoType - else { - val tvar = typeVar(entries, param.paramNum) - if (tvar != null) tvar else NoType - } - } - - /** Change dependencies in map `deps` to reflect new parameter bounds. - * @param deps The map to change - * @param pt the polytype that contains the parameters which might have new bounds - * @param entries the entries for the parameters which might have new bounds - * @param delta the change operation, one of `addDep` or `removeDep`. - * @param cmpEntries the comparison entries or `null` if no such entries exist. - * As an optimization, only bounds that differ between `entries` - * and `cmpEntries` will record their dependencies. - */ - def changeDependencies(deps: DependentMap, pt: PolyType, entries: Array[Type], delta: DepDelta, cmpEntries: Array[Type])(implicit ctx: Context): DependentMap = { - val limit = paramCount(entries) - def loop(deps: DependentMap, n: Int): DependentMap = { - if (n >= limit) deps - else { - val newDeps = entries(n) match { - case bounds @ TypeBounds(lo, hi) => - val cmpBounds = - if (cmpEntries == null) NoTypeBounds - else cmpEntries(n) match { - case bounds: TypeBounds => bounds - case _ => NoTypeBounds - } - if (cmpBounds eq bounds) deps - else { - val param = PolyParam(pt, n) - val deps1 = - if (cmpBounds.lo eq lo) deps - else new ChangeDependencies(param, 1, delta).apply(deps, lo) - val deps2 = - if (cmpBounds.hi eq hi) deps1 - else new ChangeDependencies(param, -1, delta).apply(deps1, hi) - deps2 - } - case _ => - deps - } - loop(newDeps, n + 1) - } - } - if (Config.trackConstrDeps) loop(deps, 0) else deps - } - - /** Change dependencies to reflect all changes between the bounds in `oldMap` and `newMap`. - */ - def diffDependencies(deps: DependentMap, oldMap: ParamInfo, newMap: ParamInfo)(implicit ctx: Context): DependentMap = - if (Config.trackConstrDeps) { - var d = deps - oldMap foreachBinding { (poly, entries) => - val newEntries = newMap(poly) - if (newEntries ne entries) d = changeDependencies(d, poly, entries, removeDep, newEntries) - } - newMap foreachBinding { (poly, entries) => - val oldEntries = oldMap(poly) - if (oldEntries ne entries) d = changeDependencies(d, poly, entries, addDep, oldEntries) - } - d - } else deps - - /** The set of parameters that depend directly on `param` - * according to what's stored in `dependents`. - */ - def dependentParams(param: PolyParam): Set[PolyParam] = - safeSelect(dependents(param.binder), param.paramNum) - - /** A new constraint which is derived from this constraint by adding or replacing - * the entries corresponding to `pt` with `entries`. + def typeVarOfParam(param: PolyParam): Type + + /** The constraint bounds for given type parameter `param`. + * @pre `param` is not part of the constraint domain. */ - private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = { - val res = new Constraint( - myMap.updated(pt, entries), - changeDependencies(dependents, pt, entries, addDep, myMap(pt))) - - //assert(res.domainPolys.filter(pt => - // pt.resultType.resultType.widen.classSymbol.name.toString == "Ensuring").length < 2) //DEBUG - if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries) - ctx.runInfo.recordConstraintSize(res, res.myMap.size) - res - } - - /** Check that no constrained parameter in `pt` contains itself as a bound */ - def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit = - for ((entry, i) <- entries.zipWithIndex) { - val param = PolyParam(pt, i) - entry match { - case TypeBounds(lo, hi) => - assert(!param.occursIn(lo, fromBelow = true), s"$param occurs below $lo") - assert(!param.occursIn(hi, fromBelow = false), s"$param occurs above $hi") - case _ => - } - } - - /** Check that no constrained parameter contains itself as a bound */ - def checkNonCyclic()(implicit ctx: Context): Unit = { - for (pt <- domainPolys) checkNonCyclic(pt, myMap(pt)) - } - - /** Check that no constrained parameter contains itself as a bound, - * either directly or indirectly. This should be not a structer criterion - * than checkNonCyclic because transitivity should be eliminated always, - * but it's good to be paranoid. + def bounds(param: PolyParam): TypeBounds + + /** The non-parameter bounds of this constraint. + * Poly params that are `related` are not contained in the return bounds. */ - def checkNonCyclicTrans()(implicit ctx: Context): Unit = { - for (pt <- domainPolys) - checkNonCyclicTrans(pt, myMap(pt)) - } + def nonParamBounds(param: PolyParam)(implicit ctx: Context): TypeBounds - def checkNonCyclicTrans(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit = - for ((entry, i) <- entries.zipWithIndex) { - def occursIn(params: Set[PolyParam], bound: Type, fromBelow: Boolean): Boolean = bound.stripTypeVar match { - case bound: PolyParam => - params.contains(bound) || { - at(bound) match { - case TypeBounds(lo, hi) => - occursIn(params + bound, if (fromBelow) lo else hi, fromBelow) - case _ => - false - } - } - case bound: AndOrType => - def occ1 = occursIn(params, bound.tp1, fromBelow) - def occ2 = occursIn(params, bound.tp2, fromBelow) - if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2 - case _ => false - } - val param = PolyParam(pt, i) - entry match { - case TypeBounds(lo, hi) => - assert(!occursIn(Set(param), lo, fromBelow = true), s"$param occurs below $lo") - assert(!occursIn(Set(param), hi, fromBelow = false), s"$param occurs above $hi") - case _ => - } - } + /** If `firstIsLower` is `param1 <:< param2`? + * Otherwise, is `param2 <:< param1`? + */ + def related(param1: PolyParam, param2: PolyParam, firstIsLower: Boolean)(implicit ctx: Context): Boolean + /** A new constraint which is derived from this constraint by adding + * entries for all type parameters of `poly`. + * @param tvars A list of type variables associated with the params, + * or Nil if the constraint will just be checked for + * satisfiability but will solved to give instances of + * type variables. + */ + def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This /** A new constraint which is derived from this constraint by updating * the entry for parameter `param` to `tpe`. * @pre `this contains param`. + * + * `tp` can be one of the following: + * + * - A TypeBounds value, indicating new constraint bounds + * - Another type, indicating a solution for the parameter */ - def updated(param: PolyParam, tpe: Type)(implicit ctx: Context): Constraint = { - val newEntries = myMap(param.binder).clone - newEntries(param.paramNum) = tpe - updateEntries(param.binder, newEntries) - } - - /** A new constraint which is derived from this constraint by mapping - * `op` over all entries of `poly`. - * @pre `this contains poly`. - */ - def transformed(poly: PolyType, op: Type => Type)(implicit ctx: Context) : Constraint = - updateEntries(poly, myMap(poly) map op) - - /** A new constraint with all entries coming from `pt` removed. */ - def remove(pt: PolyType)(implicit ctx: Context) = - new Constraint( - myMap remove pt, - changeDependencies(dependents, pt, myMap(pt), removeDep, null)) - - /** Is entry associated with `pt` removable? - * @param removedParam The index of a parameter which is still present in the - * entry array, but is going to be removed at the same step, - * or -1 if no such parameter exists. - */ - def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = { - val entries = myMap(pt) - var noneLeft = true - var i = paramCount(entries) - while (noneLeft && i > 0) { - i -= 1 - if (i != removedParam && isBounds(entries(i))) noneLeft = false - else typeVar(entries, i) match { - case tv: TypeVar => - if (!tv.inst.exists) noneLeft = false // need to keep line around to compute instType - case _ => - } - } - noneLeft - } - - /** Drop parameter `PolyParam(poly, n)` from `bounds`, - * replacing with Nothing in the lower bound and by `Any` in the upper bound. + def updated(param: PolyParam, tp: Type)(implicit ctx: Context): This + + /** A constraint that includes a the relationship `bound <: param` if `fromBelow` is true + * or else `param <: bound` if `fromBelow` is false. */ - def dropParamIn(bounds: TypeBounds, poly: PolyType, n: Int)(implicit ctx: Context): TypeBounds = { - def drop(tp: Type): Type = tp match { - case tp: AndOrType => - val tp1 = drop(tp.tp1) - val tp2 = drop(tp.tp2) - if (!tp1.exists) tp2 - else if (!tp2.exists) tp1 - else tp - case PolyParam(`poly`, `n`) => NoType - case _ => tp - } - def approx(tp: Type, limit: Type): Type = { - val tp1 = drop(tp) - if (tp1.exists || !tp.exists) tp1 else limit - } - bounds.derivedTypeBounds( - approx(bounds.lo, defn.NothingType), approx(bounds.hi, defn.AnyType)) - } + def order(param: PolyParam, bound: PolyParam, fromBelow: Boolean)(implicit ctx: Context): This /** A new constraint which is derived from this constraint by removing * the type parameter `param` from the domain and replacing all occurrences * of the parameter elsewhere in the constraint by type `tp`. - */ - private def uncheckedReplace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = { - - def subst(poly: PolyType, entries: Array[Type]) = { - var result = entries - var i = 0 - while (i < paramCount(entries)) { - entries(i) match { - case oldBounds: TypeBounds => - val newBounds = oldBounds.substParam(param, tp).asInstanceOf[TypeBounds] - if (oldBounds ne newBounds) { - if (result eq entries) result = entries.clone - result(i) = dropParamIn(newBounds, poly, i) - } - case _ => - } - i += 1 - } - result - } - - val pt = param.binder - val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp) - val substMap = constr1.myMap mapValues subst - val result = new Constraint( - substMap, - diffDependencies(constr1.dependents, constr1.myMap, substMap)) - if (Config.checkConstraintsNonCyclic) result.checkNonCyclic() - result - } - - /** A new constraint which is derived from this constraint by removing - * the type parameter `param` from the domain and replacing all occurrences - * of the parameter elsewhere in the constraint by type `tp`. - * `tp` is another polyparam, applies the necessary unifications to avoud a cyclic + * If `tp` is another polyparam, applies the necessary unifications to avoid a cyclic * constraint. */ - def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = - tp.dealias.stripTypeVar match { - case tp: PolyParam if this contains tp => - val bs = bounds(tp) - if (tp == param) - this - else if (param.occursIn(bs.lo, fromBelow = true) || - param.occursIn(bs.hi, fromBelow = false)) - unify(tp, param).uncheckedReplace(param, tp) - else - uncheckedReplace(param, tp) - case _ => - uncheckedReplace(param, tp) - } + def replace(param: PolyParam, tp: Type)(implicit ctx: Context): This + + /** Is entry associated with `pt` removable? + * @param removedParam The index of a parameter which is still present in the + * entry array, but is going to be removed at the same step, + * or -1 if no such parameter exists. + */ + def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean + + /** A new constraint with all entries coming from `pt` removed. */ + def remove(pt: PolyType)(implicit ctx: Context): This /** A constraint resulting by adding p2 = p1 to this constraint, and at the same * time transferring all bounds of p2 to p1 */ - def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): Constraint = { - val p1Bounds = - dropParamIn(bounds(p1), p2.binder, p2.paramNum) & - dropParamIn(bounds(p2), p1.binder, p1.paramNum) - this.updated(p1, p1Bounds).updated(p2, TypeAlias(p1)) - } - - /** A new constraint which is derived from this constraint by adding - * entries for all type parameters of `poly`. - */ - def add(poly: PolyType, tvars: List[TypeVar] = Nil)(implicit ctx: Context) : Constraint = { - val nparams = poly.paramNames.length - val entries = new Array[Type](nparams * 2) - poly.paramBounds.copyToArray(entries, 0) - tvars.copyToArray(entries, nparams) - updateEntries(poly, entries) - } + def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This /** The polytypes constrained by this constraint */ - def domainPolys: List[PolyType] = myMap.keys + def domainPolys: List[PolyType] /** The polytype parameters constrained by this constraint */ - def domainParams: List[PolyParam] = - for { - (poly, entries) <- myMap.toList - n <- 0 until paramCount(entries) - if isBounds(entries(n)) - } yield PolyParam(poly, n) + def domainParams: List[PolyParam] - /** Check whether predicate holds for all parameters in constraint - */ - def forallParams(p: PolyParam => Boolean): Boolean = { - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) - if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false - } - true - } + /** Check whether predicate holds for all parameters in constraint */ + def forallParams(p: PolyParam => Boolean): Boolean /** Perform operation `op` on all typevars, or only on uninstantiated * typevars, depending on whether `uninstOnly` is set or not. */ - def foreachTypeVar(op: TypeVar => Unit): Unit = - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) { - typeVar(entries, i) match { - case tv: TypeVar if !tv.inst.exists => op(tv) - case _ => - } - } - } - - private var myUninstVars: mutable.ArrayBuffer[TypeVar] = null + def foreachTypeVar(op: TypeVar => Unit): Unit /** The uninstantiated typevars of this constraint */ - def uninstVars: collection.Seq[TypeVar] = { - if (myUninstVars == null) { - myUninstVars = new mutable.ArrayBuffer[TypeVar] - myMap.foreachBinding { (poly, entries) => - for (i <- 0 until paramCount(entries)) { - typeVar(entries, i) match { - case tv: TypeVar if isBounds(entries(i)) => myUninstVars += tv - case _ => - } - } - } - } - myUninstVars - } + def uninstVars: collection.Seq[TypeVar] - def constrainedTypesText(printer: Printer): Text = - Text(domainPolys map (_.toText(printer)), ", ") - - def constraintText(indent: Int, printer: Printer): Text = { - val assocs = - for (param <- domainParams) - yield (" " * indent) ~ param.toText(printer) ~ at(param).toText(printer) - Text(assocs, "\n") - } - - override def toText(printer: Printer): Text = { - val header: Text = "Constraint(" - val uninstVarsText = " uninstVars = " ~ - Text(uninstVars map (_.toText(printer)), ", ") ~ ";" - val constrainedText = - " constrained types = " ~ constrainedTypesText(printer) ~ ";" - val constraintsText = - " constraint = " ~ constraintText(3, printer) ~ ")" - Text.lines(List(header, uninstVarsText, constrainedText, constraintsText)) - } -} - -trait ConstraintRunInfo { self: RunInfo => - private var maxSize = 0 - private var maxConstraint: Constraint = _ - def recordConstraintSize(c: Constraint, size: Int) = - if (size > maxSize) { - maxSize = size - maxConstraint = c - } - def printMaxConstraint()(implicit ctx: Context) = - if (maxSize > 0) typr.println(s"max constraint = ${maxConstraint.show}") + /** Check that no constrained parameter in `pt` contains itself as a bound */ + def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit + + /** Check that no constrained parameter contains itself as a bound */ + def checkNonCyclic()(implicit ctx: Context): Unit + + /** Check that no constrained parameter contains itself as a bound, + * either directly or indirectly. This should be not a stricter criterion + * than checkNonCyclic because transitivity should be eliminated always, + * but it's good to be paranoid. + */ + def checkNonCyclicTrans()(implicit ctx: Context): Unit + + protected def splitParams(tp: Type, seenFromBelow: Boolean, handleParam: PolyParam => Unit)(implicit ctx: Context): Type = tp match { + case tp: PolyParam if contains(tp) => + handleParam(tp) + NoType + case tp: AndOrType if seenFromBelow == tp.isAnd => + val tp1 = splitParams(tp.tp1, seenFromBelow, handleParam) + val tp2 = splitParams(tp.tp2, seenFromBelow, handleParam) + if (tp1.exists) + if (tp2.exists) tp.derivedAndOrType(tp1, tp2) + else tp1 + else if (tp2.exists) tp2 + else NoType + case _ => + tp + } } diff --git a/src/dotty/tools/dotc/core/ConstraintHandling.scala b/src/dotty/tools/dotc/core/ConstraintHandling.scala index 98649234f..d8078e26b 100644 --- a/src/dotty/tools/dotc/core/ConstraintHandling.scala +++ b/src/dotty/tools/dotc/core/ConstraintHandling.scala @@ -62,8 +62,15 @@ trait ConstraintHandling { } } + protected def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { + val saved = frozenConstraint + frozenConstraint = true + try isSubType(tp1, tp2) + finally frozenConstraint = saved + } + /** The current bounds of type parameter `param` */ - def bounds(param: PolyParam): TypeBounds = constraint at param match { + final def bounds(param: PolyParam): TypeBounds = constraint at param match { case bounds: TypeBounds if !ignoreConstraint => bounds case _ => param.binder.paramBounds(param.paramNum) } @@ -204,7 +211,6 @@ trait ConstraintHandling { } if (ok) newBounds else NoType } - val bound = deSkolemize(bound0, toSuper = fromBelow).dealias.stripTypeVar def description = s"${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} to ${constraint.show}" constr.println(s"adding $description") @@ -214,13 +220,13 @@ trait ConstraintHandling { res } - def isConstrained(param: PolyParam): Boolean = + final def isConstrained(param: PolyParam): Boolean = !frozenConstraint && !solvedConstraint && (constraint contains param) /** Test whether the lower bounds of all parameters in this * constraint are a solution to the constraint. */ - def isSatisfiable: Boolean = { + final def isSatisfiable: Boolean = { val saved = solvedConstraint solvedConstraint = true try @@ -244,7 +250,7 @@ trait ConstraintHandling { * @return the instantiating type * @pre `param` is in the constraint's domain. */ - def approximation(param: PolyParam, fromBelow: Boolean): Type = { + final def approximation(param: PolyParam, fromBelow: Boolean): Type = { val avoidParam = new TypeMap { override def stopAtStatic = true def apply(tp: Type) = mapOver { @@ -264,7 +270,7 @@ trait ConstraintHandling { /** Map that approximates each param in constraint by its lower bound. * Currently only used for diagnostics. */ - def approxParams = new TypeMap { // !!! Dotty problem: Turn this def into a val => -Ycheck:mix fails + final def approxParams = new TypeMap { // !!! Dotty problem: Turn this def into a val => -Ycheck:mix fails def apply(tp: Type): Type = tp.stripTypeVar match { case tp: PolyParam if constraint contains tp => this(constraint.bounds(tp).lo) diff --git a/src/dotty/tools/dotc/core/ConstraintRunInfo.scala b/src/dotty/tools/dotc/core/ConstraintRunInfo.scala new file mode 100644 index 000000000..4b7e22653 --- /dev/null +++ b/src/dotty/tools/dotc/core/ConstraintRunInfo.scala @@ -0,0 +1,16 @@ +package dotty.tools.dotc +package core + +import Contexts._, config.Printers._ + +trait ConstraintRunInfo { self: RunInfo => + private var maxSize = 0 + private var maxConstraint: Constraint = _ + def recordConstraintSize(c: Constraint, size: Int) = + if (size > maxSize) { + maxSize = size + maxConstraint = c + } + def printMaxConstraint()(implicit ctx: Context) = + if (maxSize > 0) typr.println(s"max constraint = ${maxConstraint.show}") +} diff --git a/src/dotty/tools/dotc/core/NaiveConstraint.scala b/src/dotty/tools/dotc/core/NaiveConstraint.scala new file mode 100644 index 000000000..34affc35a --- /dev/null +++ b/src/dotty/tools/dotc/core/NaiveConstraint.scala @@ -0,0 +1,383 @@ +package dotty.tools +package dotc +package core + +import Types._, Contexts._, Symbols._ +import util.SimpleMap +import collection.mutable +import printing.{Printer, Showable} +import printing.Texts._ +import config.Config +import config.Printers._ + +object NaiveConstraint { + + /** The type of `Constraint#myMap` */ + type ParamInfo = SimpleMap[PolyType, Array[Type]] + + /** The type of `Constraint#dependents */ + type DependentMap = SimpleMap[PolyType, Array[Set[PolyParam]]] + + /** The type of functions that include or exclude a `PolyParam` in or from a set*/ + private type DepDelta = (Set[PolyParam], PolyParam) => Set[PolyParam] + + private val addDep: DepDelta = (_ + _) + private val removeDep: DepDelta = (_ - _) + + private val NoTypeBounds = new TypeBounds(WildcardType, WildcardType) { + override def computeHash = unsupported("computeHash") + } + + /** An accumulator that changes dependencies on `param`. + * @param param The parameter to which changed dependencies refer. + * @param ofVariance Include `PolyParams` occurring at this variance in the dependencies. + * @param delta The dependency change to perform (add or remove). + */ + private class ChangeDependencies(param: PolyParam, ofVariance: Int, delta: DepDelta)(implicit ctx: Context) + extends TypeAccumulator[DependentMap] { + def apply(deps: DependentMap, tp: Type): DependentMap = tp match { + case tp @ PolyParam(pt, n) if + this.variance == 0 || this.variance == ofVariance => + val oldDeps = deps(pt) + val original = safeSelect(oldDeps, n) + val changed = delta(original, param) + if (original eq changed) deps + else { + val newDeps = + if (oldDeps == null) new Array[Set[PolyParam]](pt.paramBounds.length) + else oldDeps.clone + newDeps(n) = changed + deps.updated(pt, newDeps) + } + case _ => foldOver(deps, tp) + } + } + + /** `deps(n)`, except that `Set()` is returned if `deps` or `deps(n)` are null */ + private def safeSelect(deps: Array[Set[PolyParam]], n: Int) : Set[PolyParam] = + if (deps == null || deps(n) == null) Set() + else deps(n) + + private def ignoreParam(p: PolyParam): Unit = {} +} + +import NaiveConstraint._ + +/** Constraint over undetermined type parameters + * @param myMap a map from PolyType to arrays. + * Each array contains twice the number of entries as there a type parameters + * in the PolyType. The first half of the array contains the type bounds that constrain the + * polytype's type parameters. The second half might contain type variables that + * track the corresponding parameters, or is left empty (filled with nulls). + * An instantiated type parameter is represented by having its instance type in + * the corresponding array entry. + */ +class NaiveConstraint(private val myMap: ParamInfo) extends Constraint { + + type This = NaiveConstraint + + def contains(pt: PolyType): Boolean = myMap(pt) != null + + def contains(param: PolyParam): Boolean = { + val entries = myMap(param.binder) + entries != null && entries(param.paramNum).isInstanceOf[TypeBounds] + } + + def contains(tvar: TypeVar): Boolean = { + val origin = tvar.origin + val entries = myMap(origin.binder) + val pnum = origin.paramNum + entries != null && isBounds(entries(pnum)) && (typeVar(entries, pnum) eq tvar) + } + + /** The number of type parameters in the given entry array */ + private def paramCount(entries: Array[Type]) = entries.length >> 1 + + /** The type variable corresponding to parameter numbered `n`, null if none was created */ + private def typeVar(entries: Array[Type], n: Int): Type = + entries(paramCount(entries) + n) + + private def isBounds(tp: Type) = tp.isInstanceOf[TypeBounds] + + def at(param: PolyParam): Type = { + val entries = myMap(param.binder) + if (entries == null) NoType else entries(param.paramNum) + } + + def bounds(param: PolyParam): TypeBounds = at(param).asInstanceOf[TypeBounds] + + def nonParamBounds(param: PolyParam)(implicit ctx: Context): TypeBounds = { + val bs @ TypeBounds(lo, hi) = bounds(param) + val lo1 = splitParams(lo, seenFromBelow = false, ignoreParam) + val hi1 = splitParams(hi, seenFromBelow = true, ignoreParam) + bs.derivedTypeBounds(lo1.orElse(defn.NothingType), hi1.orElse(defn.AnyType)) + } + + def related(param1: PolyParam, param2: PolyParam, firstIsLower: Boolean)(implicit ctx: Context): Boolean = { + var isRelated = false + def registerParam(p: PolyParam) = if (p == param2) isRelated = true + val TypeBounds(lo, hi) = bounds(param1) + if (firstIsLower) splitParams(hi, seenFromBelow = true, registerParam) + else splitParams(lo, seenFromBelow = false, registerParam) + isRelated + } + + def typeVarOfParam(param: PolyParam): Type = { + val entries = myMap(param.binder) + if (entries == null) NoType + else { + val tvar = typeVar(entries, param.paramNum) + if (tvar != null) tvar else NoType + } + } + + /** A new constraint which is derived from this constraint by adding or replacing + * the entries corresponding to `pt` with `entries`. + */ + private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : NaiveConstraint = { + val res = new NaiveConstraint(myMap.updated(pt, entries)) + + //assert(res.domainPolys.filter(pt => + // pt.resultType.resultType.widen.classSymbol.name.toString == "Ensuring").length < 2) //DEBUG + if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries) + ctx.runInfo.recordConstraintSize(res, res.myMap.size) + res + } + + def checkNonCyclic(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit = + for ((entry, i) <- entries.zipWithIndex) { + val param = PolyParam(pt, i) + entry match { + case TypeBounds(lo, hi) => + assert(!param.occursIn(lo, fromBelow = true), s"$param occurs below $lo") + assert(!param.occursIn(hi, fromBelow = false), s"$param occurs above $hi") + case _ => + } + } + + def checkNonCyclic()(implicit ctx: Context): Unit = { + for (pt <- domainPolys) checkNonCyclic(pt, myMap(pt)) + } + + /** Check that no constrained parameter contains itself as a bound, + * either directly or indirectly. This should be not a structer criterion + * than checkNonCyclic because transitivity should be eliminated always, + * but it's good to be paranoid. + */ + def checkNonCyclicTrans()(implicit ctx: Context): Unit = { + for (pt <- domainPolys) + checkNonCyclicTrans(pt, myMap(pt)) + } + + private def checkNonCyclicTrans(pt: PolyType, entries: Array[Type])(implicit ctx: Context): Unit = + for ((entry, i) <- entries.zipWithIndex) { + def occursIn(params: Set[PolyParam], bound: Type, fromBelow: Boolean): Boolean = bound.stripTypeVar match { + case bound: PolyParam => + params.contains(bound) || { + at(bound) match { + case TypeBounds(lo, hi) => + occursIn(params + bound, if (fromBelow) lo else hi, fromBelow) + case _ => + false + } + } + case bound: AndOrType => + def occ1 = occursIn(params, bound.tp1, fromBelow) + def occ2 = occursIn(params, bound.tp2, fromBelow) + if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2 + case _ => false + } + val param = PolyParam(pt, i) + entry match { + case TypeBounds(lo, hi) => + assert(!occursIn(Set(param), lo, fromBelow = true), s"$param occurs below $lo") + assert(!occursIn(Set(param), hi, fromBelow = false), s"$param occurs above $hi") + case _ => + } + } + + def updated(param: PolyParam, tpe: Type)(implicit ctx: Context): This = { + val newEntries = myMap(param.binder).clone + newEntries(param.paramNum) = tpe + updateEntries(param.binder, newEntries) + } + + def order(param: PolyParam, bound: PolyParam, fromBelow: Boolean)(implicit ctx: Context): This = + if (related(param, bound, firstIsLower = !fromBelow)) this + else { + val oldBounds = bounds(param) + val newBounds = + if (fromBelow) TypeBounds(OrType(oldBounds.lo, bound), oldBounds.hi) + else TypeBounds(oldBounds.lo, AndType(oldBounds.hi, bound)) + updated(param, newBounds) + } + + /** A new constraint with all entries coming from `pt` removed. */ + def remove(pt: PolyType)(implicit ctx: Context): This = + new NaiveConstraint(myMap remove pt) + + def isRemovable(pt: PolyType, removedParam: Int = -1): Boolean = { + val entries = myMap(pt) + var noneLeft = true + var i = paramCount(entries) + while (noneLeft && i > 0) { + i -= 1 + if (i != removedParam && isBounds(entries(i))) noneLeft = false + else typeVar(entries, i) match { + case tv: TypeVar => + if (!tv.inst.exists) noneLeft = false // need to keep line around to compute instType + case _ => + } + } + noneLeft + } + + /** Drop parameter `PolyParam(poly, n)` from `bounds`, + * replacing with Nothing in the lower bound and by `Any` in the upper bound. + */ + private def dropParamIn(bounds: TypeBounds, poly: PolyType, n: Int)(implicit ctx: Context): TypeBounds = { + def drop(tp: Type): Type = tp match { + case tp: AndOrType => + val tp1 = drop(tp.tp1) + val tp2 = drop(tp.tp2) + if (!tp1.exists) tp2 + else if (!tp2.exists) tp1 + else tp + case PolyParam(`poly`, `n`) => NoType + case _ => tp + } + def approx(tp: Type, limit: Type): Type = { + val tp1 = drop(tp) + if (tp1.exists || !tp.exists) tp1 else limit + } + bounds.derivedTypeBounds( + approx(bounds.lo, defn.NothingType), approx(bounds.hi, defn.AnyType)) + } + + /** A new constraint which is derived from this constraint by removing + * the type parameter `param` from the domain and replacing all occurrences + * of the parameter elsewhere in the constraint by type `tp`. + */ + private def uncheckedReplace(param: PolyParam, tp: Type)(implicit ctx: Context): NaiveConstraint = { + + def subst(poly: PolyType, entries: Array[Type]) = { + var result = entries + var i = 0 + while (i < paramCount(entries)) { + entries(i) match { + case oldBounds: TypeBounds => + val newBounds = oldBounds.substParam(param, tp).asInstanceOf[TypeBounds] + if (oldBounds ne newBounds) { + if (result eq entries) result = entries.clone + result(i) = dropParamIn(newBounds, poly, i) + } + case _ => + } + i += 1 + } + result + } + + val pt = param.binder + val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp) + val result = new NaiveConstraint(constr1.myMap mapValues subst) + if (Config.checkConstraintsNonCyclic) result.checkNonCyclic() + result + } + + def replace(param: PolyParam, tp: Type)(implicit ctx: Context): This = + tp.dealias.stripTypeVar match { + case tp: PolyParam if this contains tp => + val bs = bounds(tp) + if (tp == param) + this + else if (param.occursIn(bs.lo, fromBelow = true) || + param.occursIn(bs.hi, fromBelow = false)) + unify(tp, param).uncheckedReplace(param, tp) + else + uncheckedReplace(param, tp) + case _ => + uncheckedReplace(param, tp) + } + + def unify(p1: PolyParam, p2: PolyParam)(implicit ctx: Context): This = { + val p1Bounds = + dropParamIn(bounds(p1), p2.binder, p2.paramNum) & + dropParamIn(bounds(p2), p1.binder, p1.paramNum) + this.updated(p1, p1Bounds).updated(p2, TypeAlias(p1)) + } + + def add(poly: PolyType, tvars: List[TypeVar])(implicit ctx: Context): This = { + val nparams = poly.paramNames.length + val entries = new Array[Type](nparams * 2) + poly.paramBounds.copyToArray(entries, 0) + tvars.copyToArray(entries, nparams) + updateEntries(poly, entries) + } + + def domainPolys: List[PolyType] = myMap.keys + + def domainParams: List[PolyParam] = + for { + (poly, entries) <- myMap.toList + n <- 0 until paramCount(entries) + if isBounds(entries(n)) + } yield PolyParam(poly, n) + + def forallParams(p: PolyParam => Boolean): Boolean = { + myMap.foreachBinding { (poly, entries) => + for (i <- 0 until paramCount(entries)) + if (isBounds(entries(i)) && !p(PolyParam(poly, i))) return false + } + true + } + + def foreachTypeVar(op: TypeVar => Unit): Unit = + myMap.foreachBinding { (poly, entries) => + for (i <- 0 until paramCount(entries)) { + typeVar(entries, i) match { + case tv: TypeVar if !tv.inst.exists => op(tv) + case _ => + } + } + } + + private var myUninstVars: mutable.ArrayBuffer[TypeVar] = null + + /** The uninstantiated typevars of this constraint */ + def uninstVars: collection.Seq[TypeVar] = { + if (myUninstVars == null) { + myUninstVars = new mutable.ArrayBuffer[TypeVar] + myMap.foreachBinding { (poly, entries) => + for (i <- 0 until paramCount(entries)) { + typeVar(entries, i) match { + case tv: TypeVar if isBounds(entries(i)) => myUninstVars += tv + case _ => + } + } + } + } + myUninstVars + } + + def constrainedTypesText(printer: Printer): Text = + Text(domainPolys map (_.toText(printer)), ", ") + + def constraintText(indent: Int, printer: Printer): Text = { + val assocs = + for (param <- domainParams) + yield (" " * indent) ~ param.toText(printer) ~ at(param).toText(printer) + Text(assocs, "\n") + } + + override def toText(printer: Printer): Text = { + val header: Text = "Constraint(" + val uninstVarsText = " uninstVars = " ~ + Text(uninstVars map (_.toText(printer)), ", ") ~ ";" + val constrainedText = + " constrained types = " ~ constrainedTypesText(printer) ~ ";" + val constraintsText = + " constraint = " ~ constraintText(3, printer) ~ ")" + Text.lines(List(header, uninstVarsText, constrainedText, constraintsText)) + } +} diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 4eaea31e1..457b29829 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -513,13 +513,6 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling wi false } else isSubType(tp1, tp2) - private def isSubTypeWhenFrozen(tp1: Type, tp2: Type): Boolean = { - val saved = frozenConstraint - frozenConstraint = true - try isSubType(tp1, tp2) - finally frozenConstraint = saved - } - protected def hasMatchingMember(name: Name, tp1: Type, tp2: RefinedType): Boolean = { val saved = skolemsOutstanding try { diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index 86dc0d24e..5d910c905 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -17,7 +17,7 @@ class TyperState(r: Reporter) extends DotClass with Showable { def reporter = r /** The current constraint set */ - def constraint: Constraint = new Constraint(SimpleMap.Empty, SimpleMap.Empty) + def constraint: Constraint = new NaiveConstraint(SimpleMap.Empty) def constraint_=(c: Constraint): Unit = {} /** The uninstantiated variables */ diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index c476a8be9..080596321 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -744,7 +744,7 @@ object Types { } /** A prefix-less refined this or a termRef to a new skolem symbol - * that has the given type as info + * that has the given type as info. */ def narrow(implicit ctx: Context): TermRef = TermRef(NoPrefix, ctx.newSkolem(this)) diff --git a/tests/pos/subtyping.scala b/tests/pos/subtyping.scala index 95e813bdd..29d830dd2 100644 --- a/tests/pos/subtyping.scala +++ b/tests/pos/subtyping.scala @@ -16,4 +16,17 @@ object test { } +object test2 { + + class A + class B + + val x: A | B = ??? + val y: B | A = x + + val a: A & B = ??? + val b: B & A = a + +} + |