diff options
-rw-r--r-- | src/dotty/tools/dotc/CompilationUnit.scala | 1 | ||||
-rw-r--r-- | src/dotty/tools/dotc/Main.scala | 1 | ||||
-rw-r--r-- | src/dotty/tools/dotc/config/Config.scala | 2 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Constraint.scala | 55 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/TypeComparer.scala | 62 | ||||
-rw-r--r-- | src/dotty/tools/dotc/core/Types.scala | 19 | ||||
-rw-r--r-- | src/dotty/tools/dotc/typer/FrontEnd.scala | 14 | ||||
-rw-r--r-- | src/dotty/tools/dotc/util/SourceFile.scala | 2 | ||||
-rw-r--r-- | tests/pos/typers.scala | 5 |
9 files changed, 106 insertions, 55 deletions
diff --git a/src/dotty/tools/dotc/CompilationUnit.scala b/src/dotty/tools/dotc/CompilationUnit.scala index 791e8899d..9c1431459 100644 --- a/src/dotty/tools/dotc/CompilationUnit.scala +++ b/src/dotty/tools/dotc/CompilationUnit.scala @@ -13,5 +13,4 @@ class CompilationUnit(val source: SourceFile) { var tpdTree: tpd.Tree = tpd.EmptyTree def isJava = source.file.name.endsWith(".java") - }
\ No newline at end of file diff --git a/src/dotty/tools/dotc/Main.scala b/src/dotty/tools/dotc/Main.scala index 8809cd149..217bb3f65 100644 --- a/src/dotty/tools/dotc/Main.scala +++ b/src/dotty/tools/dotc/Main.scala @@ -12,7 +12,6 @@ import reporting.Reporter * - simplify hk types * - make use of AndOrType * - review isSubType - * - cycle check for implicits * - have a second look at normalization (leave at method types if pt is method type?) * - fix problem with duplicate companion objects for classes with default parameters in constructors */ diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala index 714b8633e..b47233bd8 100644 --- a/src/dotty/tools/dotc/config/Config.scala +++ b/src/dotty/tools/dotc/config/Config.scala @@ -12,6 +12,8 @@ object Config { final val checkConstraintsNonCyclic = true + final val traceDeepSubTypes = false + final val verboseExplainSubtype = true /** When set, use new signature-based matching. diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index a9fa8f0c6..8704a35d8 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -79,8 +79,8 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit val param = PolyParam(pt, i) entry match { case TypeBounds(lo, hi) => - assert(lo != param, param) - assert(hi != param, param) + assert(!param.occursIn(lo, fromBelow = false), s"$param occurs above $lo") + assert(!param.occursIn(hi, fromBelow = true), s"$param occurs below $hi") case _ => } } @@ -126,47 +126,44 @@ class Constraint(val myMap: SimpleMap[PolyType, Array[Type]]) extends AnyVal wit noneLeft } + /** Drop parameter `PolyParam(poly, n)` from `bounds`, + * replacing with Nothing in the lower bound and by `Any` in the upper bound. + */ + 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`. */ def replace(param: PolyParam, tp: Type)(implicit ctx: Context): Constraint = { - /** Drop parameter `PolyParam(poly, n)` from bounds in type `tp` */ - def dropParamIn(tp: Type, poly: PolyType, n: Int, fromBelow: Boolean = false): Type = { - 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 - } - tp match { - case tp: TypeBounds => - tp.derivedTypeBounds( - dropParamIn(tp.lo, poly, n, !fromBelow), - dropParamIn(tp.hi, poly, n, fromBelow)) - case _ => - val tp1 = drop(tp) - if (tp1.exists || !tp.exists) tp1 - else if (fromBelow) defn.NothingType - else defn.AnyType - } - } - 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) + 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, fromBelow = false) + result(i) = dropParamIn(newBounds, poly, i) } case _ => } diff --git a/src/dotty/tools/dotc/core/TypeComparer.scala b/src/dotty/tools/dotc/core/TypeComparer.scala index cdef1ab2c..0969f814f 100644 --- a/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/src/dotty/tools/dotc/core/TypeComparer.scala @@ -53,6 +53,16 @@ class TypeComparer(initctx: Context) extends DotClass { myObjectClass } + /** Update constraint for `param` to `bounds`, check that + * new constraint is still satisfiable. + */ + private def updateConstraint(param: PolyParam, bounds: TypeBounds): Boolean = { + val saved = constraint + constraint = constraint.updated(param, bounds) + isSubType(bounds.lo, bounds.hi) || + { constraint = saved; false } // don't leave the constraint in unsatisfiable state + } + private def addConstraint1(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { val oldBounds = constraint.bounds(param) assert(!bound.isInstanceOf[TypeVar]) @@ -64,18 +74,22 @@ class TypeComparer(initctx: Context) extends DotClass { else oldBounds.derivedTypeBounds(oldBounds.lo, oldBounds.hi & bound) finally ignoreConstraint = saved val res = - (param == bound) || - (oldBounds eq newBounds) || { - val saved = constraint - constraint = constraint.updated(param, newBounds) - isSubType(newBounds.lo, newBounds.hi) || - { constraint = saved; false } // don't leave the constraint in unsatisfiable state - } + (param == bound) || (oldBounds eq newBounds) || updateConstraint(param, newBounds) constr.println(s"add constraint $param ${if (fromBelow) ">:" else "<:"} $bound = $res") if (res) constr.println(constraint.show) res } + /** 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)) + } + /** If current constraint set is not frozen, add the constraint * * param >: bound if fromBelow is true @@ -89,14 +103,27 @@ class TypeComparer(initctx: Context) extends DotClass { def addConstraint(param: PolyParam, bound: Type, fromBelow: Boolean): Boolean = { param == bound || !frozenConstraint && { - constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} to ${constraint.show}") - bound match { + constr.println(s"adding ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} (${bound.getClass}) to ${constraint.show}") + val res = bound match { case bound: PolyParam if constraint contains bound => - addConstraint1(param, bound, fromBelow) && - addConstraint1(bound, param, !fromBelow) + val TypeBounds(lo, hi) = constraint.bounds(bound) + if (lo eq hi) + addConstraint(param, lo, fromBelow) + else if (fromBelow && param.occursIn(lo, fromBelow = true)) + unify(param, bound) + else if (!fromBelow && param.occursIn(hi, fromBelow = false)) + unify(bound, param) + else + addConstraint1(param, bound, fromBelow) && + addConstraint1(bound, param, !fromBelow) + case bound: AndOrType if fromBelow != bound.isAnd => + addConstraint(param, bound.tp1, fromBelow) && + addConstraint(param, bound.tp2, fromBelow) case _ => addConstraint1(param, bound, fromBelow) } + constr.println(s"added ${param.show} ${if (fromBelow) ">:>" else "<:<"} ${bound.show} = ${constraint.show}") + res } } @@ -174,9 +201,9 @@ class TypeComparer(initctx: Context) extends DotClass { def monitoredIsSubType(tp1: Type, tp2: Type) = { if (pendingSubTypes == null) { pendingSubTypes = new mutable.HashSet[(Type, Type)] - ctx.log(s"!!! deep subtype recursion involving $tp1 <:< $tp2") - if (!this.isInstanceOf[ExplainingTypeComparer]) - ctx.log(TypeComparer.explained(implicit ctx => tp1 <:< tp2)) + ctx.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${ctx.typerState.constraint.show}") + if (Config.traceDeepSubTypes && !this.isInstanceOf[ExplainingTypeComparer]) + ctx.log(TypeComparer.explained(implicit ctx => ctx.typeComparer.isSubType(tp1, tp2))) } val p = (tp1, tp2) !pendingSubTypes(p) && { @@ -190,13 +217,6 @@ class TypeComparer(initctx: Context) extends DotClass { } def firstTry(tp1: Type, tp2: Type): Boolean = ctx.debugTraceIndented(s"$tp1 <:< $tp2") { - if (false && (tp2 isRef defn.NothingClass) && !frozenConstraint) { - tp1 match { - case tp1 @ TypeRef(_, name) => - assert(name.toString != "CONS$$U", tp1.info + "/" + tp1.symbol.isAliasType) - case _ => - } - } tp2 match { case tp2: NamedType => tp1 match { diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala index 930922b5b..f9119d060 100644 --- a/src/dotty/tools/dotc/core/Types.scala +++ b/src/dotty/tools/dotc/core/Types.scala @@ -1383,10 +1383,13 @@ object Types { trait AndOrType extends ValueType { // todo: check where we can simplify using AndOrType def tp1: Type def tp2: Type + def isAnd: Boolean } abstract case class AndType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType { + def isAnd = true + def derivedAndType(tp1: Type, tp2: Type)(implicit ctx: Context) = if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this else AndType(tp1, tp2) @@ -1409,6 +1412,8 @@ object Types { abstract case class OrType(tp1: Type, tp2: Type) extends CachedGroundType with AndOrType { assert(tp1.isInstanceOf[ValueType] && tp2.isInstanceOf[ValueType], s"$tp1 | $tp2") + def isAnd = false + def derivedOrType(tp1: Type, tp2: Type)(implicit ctx: Context) = if ((tp1 eq this.tp1) && (tp2 eq this.tp2)) this else OrType(tp1, tp2) @@ -1660,6 +1665,20 @@ object Types { case class PolyParam(binder: PolyType, paramNum: Int) extends ParamType { type BT = PolyType def copy(bt: BT) = PolyParam(bt, paramNum) + + /** Looking only at the structure of `bound`, is one of the following true? + * - fromBelow and param <:< bound + * - !fromBelow and param >:> bound + */ + def occursIn(bound: Type, fromBelow: Boolean): Boolean = bound 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 + case _ => false + } + override def underlying(implicit ctx: Context): Type = binder.paramBounds(paramNum) // no customized hashCode/equals needed because cycle is broken in PolyType override def toString = s"PolyParam(${binder.paramNames(paramNum)})" diff --git a/src/dotty/tools/dotc/typer/FrontEnd.scala b/src/dotty/tools/dotc/typer/FrontEnd.scala index 25c9de717..1cea9fe7c 100644 --- a/src/dotty/tools/dotc/typer/FrontEnd.scala +++ b/src/dotty/tools/dotc/typer/FrontEnd.scala @@ -11,19 +11,27 @@ class FrontEnd extends Phase { def name = "frontend" - def parse(implicit ctx: Context) = { + def monitor(doing: String)(body: => Unit)(implicit ctx: Context) = + try body + catch { + case ex: Throwable => + println(s"exception occured while $doing ${ctx.compilationUnit}") + throw ex + } + + def parse(implicit ctx: Context) = monitor("parsing") { val unit = ctx.compilationUnit unit.untpdTree = new Parser(unit.source).parse() typr.println("parsed:\n"+unit.untpdTree.show) } - def enterSyms(implicit ctx: Context) = { + def enterSyms(implicit ctx: Context) = monitor("indexing") { val unit = ctx.compilationUnit ctx.typer.index(unit.untpdTree) typr.println("entered: "+unit.source) } - def typeCheck(implicit ctx: Context) = { + def typeCheck(implicit ctx: Context) = monitor("typechecking") { val unit = ctx.compilationUnit unit.tpdTree = ctx.typer.typedExpr(unit.untpdTree) typr.println("typed: "+unit.source) diff --git a/src/dotty/tools/dotc/util/SourceFile.scala b/src/dotty/tools/dotc/util/SourceFile.scala index 5691ddcb8..4e1eb224a 100644 --- a/src/dotty/tools/dotc/util/SourceFile.scala +++ b/src/dotty/tools/dotc/util/SourceFile.scala @@ -125,6 +125,8 @@ case class SourceFile(file: AbstractFile, content: Array[Char]) { } col + 1 } + + override def toString = file.toString } object NoSource extends SourceFile("<no source>", Nil) { diff --git a/tests/pos/typers.scala b/tests/pos/typers.scala index c02bcda22..1626731bd 100644 --- a/tests/pos/typers.scala +++ b/tests/pos/typers.scala @@ -4,6 +4,11 @@ import annotation.{tailrec, switch} import collection.mutable._ object typers { + + val entries = Array("abc", "def") + + for ((x, i) <- entries.zipWithIndex) + println(x) object Eta { |