diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/dotty/tools/dotc/config/Config.scala | 6 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/config/Printers.scala | 3 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Constraint.scala | 58 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 20 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 15 | ||||
| -rw-r--r-- | src/dotty/tools/dotc/typer/Inferencing.scala | 12 |
6 files changed, 82 insertions, 32 deletions
diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index b47233bd8..6ac25ab74 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -12,7 +12,11 @@ object Config { final val checkConstraintsNonCyclic = true - final val traceDeepSubTypes = false + /** Throw an exception if a deep subtype recursion is detected */ + final val flagDeepSubTypeRecursions = true + + /** Show subtype traces for all deep subtype recursions */ + final val traceDeepSubTypeRecursions = false final val verboseExplainSubtype = true diff --git a/src/dotty/tools/dotc/config/Printers.scala b/src/dotty/tools/dotc/config/Printers.scala index 00e8b21c6..cdba156b2 100644 --- a/src/dotty/tools/dotc/config/Printers.scala +++ b/src/dotty/tools/dotc/config/Printers.scala @@ -12,10 +12,11 @@ object Printers { val default: Printer = new Printer val core: Printer = noPrinter - val typr: Printer = new Printer + val typr: Printer = noPrinter val constr: Printer = noPrinter val overload: Printer = noPrinter val implicits: Printer = noPrinter + val subtyping: Printer = noPrinter val unapp: Printer = noPrinter val completions = noPrinter val gadts = noPrinter diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index b47cc921c..1df3c6ac5 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -71,7 +71,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit /** 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]): Constraint = { + private def updateEntries(pt: PolyType, entries: Array[Type])(implicit ctx: Context) : Constraint = { import Constraint._ val res = new Constraint(myMap.updated(pt, entries)) if (Config.checkConstraintsNonCyclic) checkNonCyclic(pt, entries) @@ -82,23 +82,28 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit res } - /** Check that no constrained parameter contains itself as a bound */ - def checkNonCyclic(pt: PolyType, entries: Array[Type]) = + /** 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 = false), s"$param occurs above $lo") - assert(!param.occursIn(hi, fromBelow = true), s"$param occurs below $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)) + } + /** A new constraint which is derived from this constraint by updating * the entry for parameter `param` to `tpe`. * @pre `this contains param`. */ - def updated(param: PolyParam, tpe: Type): Constraint = { + def updated(param: PolyParam, tpe: Type)(implicit ctx: Context): Constraint = { val newEntries = myMap(param.binder).clone newEntries(param.paramNum) = tpe updateEntries(param.binder, newEntries) @@ -108,7 +113,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit * `op` over all entries of type `poly`. * @pre `this contains poly`. */ - def transformed(poly: PolyType, op: Type => Type): Constraint = + 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. */ @@ -161,7 +166,7 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit * the type parameter `param` from the domain and replacing all occurrences * of the parameter elsewhere in the constraint by type `tp`. */ - def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = { + private def uncheckedReplace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = { def subst(poly: PolyType, entries: Array[Type]) = { var result = entries @@ -183,13 +188,46 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit val pt = param.binder val constr1 = if (isRemovable(pt, param.paramNum)) remove(pt) else updated(param, tp) - new Constraint(constr1.myMap mapValues subst) + val result = new Constraint(constr1.myMap mapValues subst) + 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 + * 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) + } + + /** 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): Constraint = { + 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) diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index 221b20e51..0834c310f 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -34,6 +34,13 @@ class TypeComparer(initctx: Context) extends DotClass { */ protected var ignoreConstraint = false + /** Is a subtype check in course? In that case we may not + * permanently instantiate type variables, because the corresponding + * constraint might still be retracted and the instantiation should + * then be reversed. + */ + def subtypeCheckInProgress: Boolean = recCount >= 0 + private var myAnyClass: ClassSymbol = null private var myNothingClass: ClassSymbol = null private var myNullClass: ClassSymbol = null @@ -86,11 +93,9 @@ class TypeComparer(initctx: Context) extends DotClass { /** Make p2 = p1, transfer all bounds of p2 to p1 */ private def unify(p1: PolyParam, p2: PolyParam): Boolean = { constr.println(s"unifying $p1 $p2") - val p1Bounds = - constraint.dropParamIn(constraint.bounds(p1), p2.binder, p2.paramNum) & - constraint.dropParamIn(constraint.bounds(p2), p1.binder, p1.paramNum) - updateConstraint(p1, p1Bounds) && - updateConstraint(p2, TypeAlias(p1)) + val constraint1 = constraint.unify(p1, p2) + val bounds = constraint1.bounds(p1) + isSubType(bounds.lo, bounds.hi) && { constraint = constraint1; true } } /** If current constraint set is not frozen, add the constraint @@ -216,8 +221,9 @@ class TypeComparer(initctx: Context) extends DotClass { if (pendingSubTypes == null) { pendingSubTypes = new mutable.HashSet[(Type, Type)] ctx.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${ctx.typerState.constraint.show}") - assert(!Config.flagDeepRecursions) - if (Config.traceDeepSubTypes && !this.isInstanceOf[ExplainingTypeComparer]) + ctx.log(s"!!! constraint = ${constraint.show}") + assert(!Config.flagDeepSubTypeRecursions) + if (Config.traceDeepSubTypeRecursions && !this.isInstanceOf[ExplainingTypeComparer]) ctx.log(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2))) } val p = (tp1, tp2) diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index bfe4ae5be..6c9bc4f10 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1696,12 +1696,12 @@ object Types { * - fromBelow and param <:< bound * - !fromBelow and param >:> bound */ - def occursIn(bound: Type, fromBelow: Boolean): Boolean = bound match { + def occursIn(bound: Type, fromBelow: Boolean)(implicit ctx: Context): Boolean = bound.stripTypeVar match { case bound: PolyParam => bound == this case bound: AndOrType => def occ1 = occursIn(bound.tp1, fromBelow) def occ2 = occursIn(bound.tp2, fromBelow) - if (fromBelow == bound.isAnd) occ1 & occ2 else occ1 || occ2 + if (fromBelow == bound.isAnd) occ1 && occ2 else occ1 || occ2 case _ => false } @@ -1761,10 +1761,11 @@ object Types { /** Instantiate variable with given type */ private def instantiateWith(tp: Type)(implicit ctx: Context): Type = { - assert(tp ne this) + assert(tp ne this, s"self instantiation of ${tp.show}, constraint = ${ctx.typerState.constraint.show}") typr.println(s"instantiating ${this.show} with ${tp.show}") assert(ctx.typerState.constraint contains this) // !!! DEBUG - if (ctx.typerState eq owningState) inst = tp + if ((ctx.typerState eq owningState) && !ctx.typeComparer.subtypeCheckInProgress) + inst = tp ctx.typerState.constraint = ctx.typerState.constraint.replace(origin, tp) tp } @@ -1807,8 +1808,10 @@ object Types { override def hashCode: Int = System.identityHashCode(this) override def equals(that: Any) = this eq that.asInstanceOf[AnyRef] - override def toString = - if (inst.exists) inst.toString else s"TypeVar($origin)" + override def toString = { + def instStr = if (inst.exists) s" -> $inst" else "" + s"TypeVar($origin$instStr)" + } } // ------ ClassInfo, Type Bounds ------------------------------------------------------------ diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 6e522b831..d815d369d 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -504,12 +504,10 @@ object Inferencing { val tp = tree.tpe.widen val constraint = ctx.typerState.constraint - /* !!! DEBUG - println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${constraint.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}") - println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (_.show)}") - println(s"fulltype: $tp") // !!! DEBUG - println(s"constraint: ${constraint.show}") - */ + constr.println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${constraint.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}") + constr.println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (tvar => s"$tvar / ${tvar.show}")}") + constr.println(s"fulltype: $tp") // !!! DEBUG + constr.println(s"constraint: ${constraint.show}") def qualifies(tvar: TypeVar) = tree contains tvar.owningTree val vs = tp.variances(tvar => (constraint contains tvar) && qualifies(tvar)) @@ -526,7 +524,7 @@ object Inferencing { else constraint.foreachUninstVar { tvar => if (!(vs contains tvar) && qualifies(tvar)) { - typr.println(s"instantiating non-occurring $tvar in $tp") + typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show}") tvar.instantiate(fromBelow = true) } } |