aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/dotty/tools/dotc/config/Config.scala6
-rw-r--r--src/dotty/tools/dotc/core/Constraint.scala150
-rw-r--r--src/dotty/tools/dotc/core/TypeComparer.scala81
-rw-r--r--src/dotty/tools/dotc/core/TyperState.scala6
-rw-r--r--src/dotty/tools/dotc/core/Types.scala3
5 files changed, 206 insertions, 40 deletions
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala
index e77b10bfb..c247699da 100644
--- a/src/dotty/tools/dotc/config/Config.scala
+++ b/src/dotty/tools/dotc/config/Config.scala
@@ -37,4 +37,10 @@ object Config {
/** The recursion depth for showing a summarized string */
final val summarizeDepth = 2
+
+ /** Track dependencies for constraint propagation satisfiability checking
+ * If turned off, constraint checking is simpler but potentially slower
+ * for large constraints.
+ */
+ final val trackConstrDeps = true
} \ No newline at end of file
diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala
index a16c85316..339dbb64a 100644
--- a/src/dotty/tools/dotc/core/Constraint.scala
+++ b/src/dotty/tools/dotc/core/Constraint.scala
@@ -10,6 +10,55 @@ 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){}
+
+ /** 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
@@ -18,8 +67,20 @@ import config.Printers._
* 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.
*/
-class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable {
+class Constraint(private val myMap: ParamInfo,
+ private val dependents: DependentMap) extends Showable {
/** Does the constraint's domain contain the type parameters of `pt`? */
def contains(pt: PolyType): Boolean = myMap(pt) != null
@@ -72,15 +133,82 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable {
}
}
+ /** 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`.
*/
private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = {
- val res = new Constraint(myMap.updated(pt, entries))
+ 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)
+ ctx.runInfo.recordConstraintSize(res, res.myMap.size)
res
}
@@ -119,7 +247,10 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable {
updateEntries(poly, myMap(poly) map op)
/** A new constraint with all entries coming from `pt` removed. */
- def remove(pt: PolyType) = new Constraint(myMap remove pt)
+ 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
@@ -190,7 +321,10 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable {
val pt = param.binder
val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp)
- val result = new Constraint(constr1.myMap mapValues subst)
+ val substMap = constr1.myMap mapValues subst
+ val result = new Constraint(
+ substMap,
+ diffDependencies(constr1.dependents, constr1.myMap, substMap))
if (Config.checkConstraintsNonCyclic) result.checkNonCyclic()
result
}
@@ -314,9 +448,9 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends Showable {
trait ConstraintRunInfo { self: RunInfo =>
private var maxSize = 0
private var maxConstraint: Constraint = _
- def recordConstraintSize(c: Constraint) =
- if (c.myMap.size > maxSize) {
- maxSize = c.myMap.size
+ def recordConstraintSize(c: Constraint, size: Int) =
+ if (size > maxSize) {
+ maxSize = size
maxConstraint = c
}
def printMaxConstraint()(implicit ctx: Context) =
diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala
index 9003de3c1..2d66e7d2f 100644
--- a/src/dotty/tools/dotc/core/TypeComparer.scala
+++ b/src/dotty/tools/dotc/core/TypeComparer.scala
@@ -84,51 +84,77 @@ class TypeComparer(initctx: Context) extends DotClass {
myAnyType
}
- /** Map that approximates each param in constraint by its lower bound */
+ /** Map that approximates each param in constraint by its lower bound.
+ * Currently only used for diagnostics.
+ */
val approxParams = new TypeMap {
def apply(tp: Type): Type = tp.stripTypeVar match {
- case tp: PolyParam if !solvedConstraint && (constraint contains tp) =>
+ case tp: PolyParam if constraint contains tp =>
this(constraint.bounds(tp).lo)
case tp =>
mapOver(tp)
}
}
- /** Propagate new constraint by comparing all bounds */
- def propagate: Boolean =
- constraint.forallParams { poly =>
- val TypeBounds(lo, hi) = constraint.bounds(poly)
+ /** If `param` is contained in constraint, test whether its
+ * bounds are non-empty. Otherwise return `true`.
+ */
+ private def checkBounds(param: PolyParam): Boolean = constraint.at(param) match {
+ case TypeBounds(lo, hi) =>
+ if (Stats.monitored) Stats.record("checkBounds")
isSubType(lo, hi)
+ case _ => true
+ }
+
+ /** Test validity of constraint for parameter `changed` and of all
+ * parameters that depend on it.
+ */
+ private def propagate(changed: PolyParam): Boolean =
+ if (Config.trackConstrDeps)
+ checkBounds(changed) &&
+ propagate(constraint.dependentParams(changed) - changed, Set(changed))
+ else
+ constraint forallParams checkBounds
+
+ /** Ensure validity of constraints for parameters `params` and of all
+ * parameters that depend on them and that have not been tested
+ * now or before. If `trackConstrDeps` is not set, do this for all
+ * parameters in the constraint.
+ * @param seen the set of parameters that have been tested before.
+ */
+ private def propagate(params: Set[PolyParam], seen: Set[PolyParam]): Boolean =
+ params.isEmpty ||
+ (params forall checkBounds) && {
+ val seen1 = seen ++ params
+ val nextParams = (Set[PolyParam]() /: params) { (ps, p) =>
+ ps ++ (constraint.dependentParams(p) -- seen1)
+ }
+ propagate(nextParams, seen1)
}
/** Check whether the lower bounds of all parameters in this
* constraint are a solution to the constraint.
+ * As an optimization, when `trackConstrDeps` is set, we
+ * only test that the solutions satisfy the constraints `changed`
+ * and all parameters that depend on it.
*/
- def isSatisfiable(useSolved: Boolean): Boolean = {
+ def isSatisfiable(changed: PolyParam): Boolean = {
val saved = solvedConstraint
solvedConstraint = true
try
- constraint.forallParams { poly =>
- val TypeBounds(lo, hi) = constraint.bounds(poly)
- isSubType(approxParams(lo), approxParams(hi)) ||
- {
+ if (Config.trackConstrDeps) propagate(changed)
+ else
+ constraint.forallParams { param =>
+ checkBounds(param) || {
+ val TypeBounds(lo, hi) = constraint.bounds(param)
ctx.log(i"sub fail $lo <:< $hi")
- solvedConstraint = saved
ctx.log(i"approximated = ${approxParams(lo)} <:< ${approxParams(hi)}")
- ctx.log(TypeComparer.explained(implicit ctx => isSubType(approxParams(lo), approxParams(hi))))
false
}
- }
+ }
finally solvedConstraint = saved
}
- def isSatisfiable: Boolean = {
- val withSolved = isSatisfiable(true)
- val withoutSolved = isSatisfiable(false)
- assert(withSolved == withoutSolved, i"sat diff for $constraint, with solved: $withSolved, without: $withoutSolved")
- withSolved
- }
-
/** Update constraint for `param` to `bounds`, check that
* new constraint is still satisfiable.
*/
@@ -136,13 +162,12 @@ class TypeComparer(initctx: Context) extends DotClass {
val saved = constraint
constraint = constraint.updated(param, bounds)
- propagate &&
- { isSatisfiable || {
- ctx.log(i"SAT $constraint produced by $param $bounds is not satisfiable")
- false
- }
- } ||
- { constraint = saved; false } // don't leave the constraint in unsatisfiable state
+ if (propagate(param)) {
+ if (isSatisfiable(param)) return true
+ ctx.log(i"SAT $constraint produced by $param $bounds is not satisfiable")
+ }
+ constraint = saved // don't leave the constraint in unsatisfiable state
+ false
}
private def addConstraint1(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = {
diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala
index 65cebf967..59c934e0d 100644
--- a/src/dotty/tools/dotc/core/TyperState.scala
+++ b/src/dotty/tools/dotc/core/TyperState.scala
@@ -14,7 +14,7 @@ import collection.mutable
class TyperState(val reporter: Reporter) extends DotClass with Showable {
/** The current constraint set */
- def constraint: Constraint = new Constraint(SimpleMap.Empty)
+ def constraint: Constraint = new Constraint(SimpleMap.Empty, SimpleMap.Empty)
def constraint_=(c: Constraint): Unit = {}
/** The uninstantiated variables */
@@ -48,7 +48,7 @@ class TyperState(val reporter: Reporter) extends DotClass with Showable {
* type variable instantiation cannot be retracted anymore. Then, remove
* no-longer needed constraint entries.
*/
- def gc(): Unit = ()
+ def gc()(implicit ctx: Context): Unit = ()
/** Is it allowed to commit this state? */
def isCommittable: Boolean = false
@@ -96,7 +96,7 @@ extends TyperState(reporter) {
reporter.flush()
}
- override def gc(): Unit = {
+ override def gc()(implicit ctx: Context): Unit = {
val toCollect = new mutable.ListBuffer[PolyType]
constraint foreachTypeVar { tvar =>
if (!tvar.inst.exists) {
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index bb882e36c..088a2e3af 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -2119,11 +2119,12 @@ object Types {
override def toString =
if (lo eq hi) s"TypeAlias($lo)" else s"TypeBounds($lo, $hi)"
+
+ override def computeHash = unsupported("computeHash")
}
class CachedTypeBounds(lo: Type, hi: Type, hc: Int) extends TypeBounds(lo, hi) {
myHash = hc
- override def computeHash = unsupported("computeHash")
}
final class CoTypeBounds(lo: Type, hi: Type, hc: Int) extends CachedTypeBounds(lo, hi, hc) {
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-30 01:19:24 +0000