From eef9be9817f5c0516e221aab1d14d748a12b386c Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 26 Aug 2016 10:26:22 +0200 Subject: Implement constraint merging Not used yet, but we might use it as an alternative to typedArg invalidation later. --- src/dotty/tools/dotc/core/Constraint.scala | 3 ++ src/dotty/tools/dotc/core/OrderingConstraint.scala | 44 +++++++++++++++++++++- src/dotty/tools/dotc/core/TyperState.scala | 6 +-- 3 files changed, 48 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/dotty/tools/dotc/core/Constraint.scala b/src/dotty/tools/dotc/core/Constraint.scala index 436b035dc..99b4af0a9 100644 --- a/src/dotty/tools/dotc/core/Constraint.scala +++ b/src/dotty/tools/dotc/core/Constraint.scala @@ -143,6 +143,9 @@ abstract class Constraint extends Showable { /** The uninstantiated typevars of this constraint */ def uninstVars: collection.Seq[TypeVar] + /** The weakest constraint that subsumes both this constraint and `other` */ + def & (other: Constraint)(implicit ctx: Context): Constraint + /** Check that no constrained parameter contains itself as a bound */ def checkNonCyclic()(implicit ctx: Context): Unit diff --git a/src/dotty/tools/dotc/core/OrderingConstraint.scala b/src/dotty/tools/dotc/core/OrderingConstraint.scala index b0170b67c..e7e388be9 100644 --- a/src/dotty/tools/dotc/core/OrderingConstraint.scala +++ b/src/dotty/tools/dotc/core/OrderingConstraint.scala @@ -15,11 +15,13 @@ import annotation.tailrec object OrderingConstraint { + type ArrayValuedMap[T] = SimpleMap[GenericType, Array[T]] + /** The type of `OrderingConstraint#boundsMap` */ - type ParamBounds = SimpleMap[GenericType, Array[Type]] + type ParamBounds = ArrayValuedMap[Type] /** The type of `OrderingConstraint#lowerMap`, `OrderingConstraint#upperMap` */ - type ParamOrdering = SimpleMap[GenericType, Array[List[PolyParam]]] + type ParamOrdering = ArrayValuedMap[List[PolyParam]] /** A new constraint with given maps */ private def newConstraint(boundsMap: ParamBounds, lowerMap: ParamOrdering, upperMap: ParamOrdering)(implicit ctx: Context) : OrderingConstraint = { @@ -495,6 +497,44 @@ class OrderingConstraint(private val boundsMap: ParamBounds, } } + def & (other: Constraint)(implicit ctx: Context) = { + def merge[T](m1: ArrayValuedMap[T], m2: ArrayValuedMap[T], join: (T, T) => T): ArrayValuedMap[T] = { + var merged = m1 + def mergeArrays(xs1: Array[T], xs2: Array[T]) = { + val xs = xs1.clone + for (i <- xs.indices) xs(i) = join(xs1(i), xs2(i)) + xs + } + m2.foreachBinding { (poly, xs2) => + merged = merged.updated(poly, + if (m1.contains(poly)) mergeArrays(m1(poly), xs2) else xs2) + } + merged + } + + def mergeParams(ps1: List[PolyParam], ps2: List[PolyParam]) = + (ps1 /: ps2)((ps1, p2) => if (ps1.contains(p2)) ps1 else p2 :: ps1) + + def mergeEntries(e1: Type, e2: Type): Type = e1 match { + case e1: TypeBounds => + e2 match { + case e2: TypeBounds => e1 & e2 + case _ if e1 contains e2 => e2 + case _ => mergeError + } + case _ if e1 eq e2 => e1 + case _ => mergeError + } + + def mergeError = throw new AssertionError(i"cannot merge $this with $other") + + val that = other.asInstanceOf[OrderingConstraint] + new OrderingConstraint( + merge(this.boundsMap, that.boundsMap, mergeEntries), + merge(this.lowerMap, that.lowerMap, mergeParams), + merge(this.upperMap, that.upperMap, mergeParams)) + } + override def checkClosed()(implicit ctx: Context): Unit = { def isFreePolyParam(tp: Type) = tp match { case PolyParam(binder: GenericType, _) => !contains(binder) diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index 69c35faf5..4b3c1554d 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -128,14 +128,14 @@ extends TyperState(r) { */ override def commit()(implicit ctx: Context) = { val targetState = ctx.typerState - assert(targetState eq previous) assert(isCommittable) - targetState.constraint = constraint + if (targetState eq previous) targetState.constraint = constraint + else targetState.constraint &= constraint constraint foreachTypeVar { tvar => if (tvar.owningState eq this) tvar.owningState = targetState } - targetState.ephemeral = ephemeral + targetState.ephemeral |= ephemeral targetState.gc() reporter.flush() myIsCommitted = true -- cgit v1.2.3 From 36648547105bc8ac53dd63a03821a27243af13cd Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 26 Aug 2016 16:38:37 +0200 Subject: Handle complex context merging cases Test case in isApplicableSafe.scala. It turns out that this requires a context merge using the new `&' operator. Sequence of actions: 1) Typecheck argument in typerstate 1. 2) Cache argument. 3) Evolve same typer state (to typecheck other arguments, say) leading to a different constraint. 4) Take typechecked argument in same state. It turns out that the merge in TyperState is needed not just for isApplicableSafe but also for (e.g. erased-lubs.scala) as well as many parts of dotty itself. --- src/dotty/tools/dotc/core/TyperState.scala | 8 +++++--- src/dotty/tools/dotc/typer/Inferencing.scala | 3 ++- 2 files changed, 7 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index 4b3c1554d..a7ad6824f 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -96,7 +96,8 @@ extends TyperState(r) { override def reporter = myReporter - private var myConstraint: Constraint = previous.constraint + private val previousConstraint = previous.constraint + private var myConstraint: Constraint = previousConstraint override def constraint = myConstraint override def constraint_=(c: Constraint)(implicit ctx: Context) = { @@ -129,8 +130,9 @@ extends TyperState(r) { override def commit()(implicit ctx: Context) = { val targetState = ctx.typerState assert(isCommittable) - if (targetState eq previous) targetState.constraint = constraint - else targetState.constraint &= constraint + targetState.constraint = + if (targetState.constraint eq previousConstraint) constraint + else targetState.constraint & constraint constraint foreachTypeVar { tvar => if (tvar.owningState eq this) tvar.owningState = targetState diff --git a/src/dotty/tools/dotc/typer/Inferencing.scala b/src/dotty/tools/dotc/typer/Inferencing.scala index 7c61f8c23..719e8d7fc 100644 --- a/src/dotty/tools/dotc/typer/Inferencing.scala +++ b/src/dotty/tools/dotc/typer/Inferencing.scala @@ -78,7 +78,8 @@ object Inferencing { def apply(x: Boolean, tp: Type): Boolean = tp.dealias match { case _: WildcardType | _: ProtoType => false - case tvar: TypeVar if !tvar.isInstantiated => + case tvar: TypeVar + if !tvar.isInstantiated && ctx.typerState.constraint.contains(tvar) => force.appliesTo(tvar) && { val direction = instDirection(tvar.origin) if (direction != 0) { -- cgit v1.2.3 From a438d3e4cb39ea7c12eba2ebc3a2399a680549f6 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 26 Aug 2016 16:43:30 +0200 Subject: Handle case where expected type of a SeqLiteral has an undetermined element type. Test case is isApplicableSafe -Ycheck:first. --- src/dotty/tools/dotc/typer/Typer.scala | 6 +++- tests/pending/pos/isApplicableSafe.scala | 8 ----- tests/pos/isApplicableSafe.scala | 54 ++++++++++++++++++++++++++++++++ 3 files changed, 59 insertions(+), 9 deletions(-) delete mode 100644 tests/pending/pos/isApplicableSafe.scala create mode 100644 tests/pos/isApplicableSafe.scala (limited to 'src') diff --git a/src/dotty/tools/dotc/typer/Typer.scala b/src/dotty/tools/dotc/typer/Typer.scala index f0086b0ab..fdcfe347b 100644 --- a/src/dotty/tools/dotc/typer/Typer.scala +++ b/src/dotty/tools/dotc/typer/Typer.scala @@ -895,7 +895,11 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit } def typedSeqLiteral(tree: untpd.SeqLiteral, pt: Type)(implicit ctx: Context): SeqLiteral = track("typedSeqLiteral") { - val proto1 = pt.elemType orElse WildcardType + val proto1 = pt.elemType match { + case NoType => WildcardType + case bounds: TypeBounds => WildcardType(bounds) + case elemtp => elemtp + } val elems1 = tree.elems mapconserve (typed(_, proto1)) val proto2 = // the computed type of the `elemtpt` field if (!tree.elemtpt.isEmpty) WildcardType diff --git a/tests/pending/pos/isApplicableSafe.scala b/tests/pending/pos/isApplicableSafe.scala deleted file mode 100644 index b4cacbf28..000000000 --- a/tests/pending/pos/isApplicableSafe.scala +++ /dev/null @@ -1,8 +0,0 @@ -class A { - // Any of Array[List[Symbol]], List[Array[Symbol]], or List[List[Symbol]] compile. - var xs: Array[Array[Symbol]] = _ - var ys: Array[Map[Symbol, Set[Symbol]]] = _ - - xs = Array(Array()) - ys = Array(Map(), Map()) -} diff --git a/tests/pos/isApplicableSafe.scala b/tests/pos/isApplicableSafe.scala new file mode 100644 index 000000000..c54df1f22 --- /dev/null +++ b/tests/pos/isApplicableSafe.scala @@ -0,0 +1,54 @@ +import reflect.ClassTag + +// The same problems arise in real arrays. +class A { + + class Array[T] + object Array { + def apply[T: ClassTag](xs: T*): Array[T] = ??? + def apply(x: Int, xs: Int*): Array[Int] = ??? + } + + // Any of Array[List[Symbol]], List[Array[Symbol]], or List[List[Symbol]] compile. + var xs: Array[Array[Symbol]] = _ + var ys: Array[Map[Symbol, Set[Symbol]]] = _ + + //xs = Array(Array()) + // gives: + // + // isApplicableSafe.scala:15: error: type mismatch: + // found : A.this.Array[Nothing] + // required: A.this.Array[Symbol] + // xs = Array(Array()) + // + // Here's the sequence of events that leads to this problem: + // + // 1. the outer Array.apply is overloaded, so we need to typecheck the inner one + // without an expected prototype + // + // 2. The inner Array.apply needs a ClassTag, so we need to instantiate + // its type variable, and the best instantiation is Nothing. + // + // To prevent this, we'd need to do several things: + // + // 1. Pass argument types lazily into the isApplicable call in resolveOverloaded, + // so that we can call constrainResult before any arguments are evaluated. + // + // 2. This is still not enough because the result type is initially an IgnoredProto. + // (because an implicit might have to be inserted around the call, so we cannot + // automatically assume that the call result is a subtype of the expected type). + // Hence, we need to somehow create a closure in constrainResult that does the + // comparison with the real expected result type "on demand". + // + // 3. When instantiating a type variable we need to categorize that some instantiations + // are suspicous (e.g. scalac avoids instantiating to Nothing). In these + // circumstances we should try to excute the delayed constrainResult closures + // in order to get a better instance type. + // + // Quite a lot of work. It's looking really complicated to fix this. + + + ys = Array(Map(), Map()) + + val zs = Array(Map()) +} -- cgit v1.2.3 From 2dfe4db8b3babefeba83eb30ffdc92a5d84665bb Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Fri, 26 Aug 2016 17:35:17 +0200 Subject: TyperState refactoring. Need to export just uncommittedAncestor, can hide isCommitted and parent. --- src/dotty/tools/dotc/core/TyperState.scala | 24 +++++++----------------- 1 file changed, 7 insertions(+), 17 deletions(-) (limited to 'src') diff --git a/src/dotty/tools/dotc/core/TyperState.scala b/src/dotty/tools/dotc/core/TyperState.scala index a7ad6824f..7b8867ccc 100644 --- a/src/dotty/tools/dotc/core/TyperState.scala +++ b/src/dotty/tools/dotc/core/TyperState.scala @@ -59,18 +59,10 @@ class TyperState(r: Reporter) extends DotClass with Showable { /** Commit state so that it gets propagated to enclosing context */ def commit()(implicit ctx: Context): Unit = unsupported("commit") - /** The typer state has already been committed */ - def isCommitted: Boolean = false - - /** Optionally, if this is a mutable typerstate, it's creator state */ - def parent: Option[TyperState] = None - /** The closest ancestor of this typer state (including possibly this typer state itself) * which is not yet committed, or which does not have a parent. */ - def uncommittedAncestor: TyperState = - if (!isCommitted || !parent.isDefined) this - else parent.get.uncommittedAncestor + def uncommittedAncestor: TyperState = this /** Make type variable instances permanent by assigning to `inst` field if * type variable instantiation cannot be retracted anymore. Then, remove @@ -110,7 +102,6 @@ extends TyperState(r) { override def ephemeral = myEphemeral override def ephemeral_=(x: Boolean): Unit = { myEphemeral = x } - override def fresh(isCommittable: Boolean): TyperState = new MutableTyperState(this, new StoreReporter(reporter), isCommittable) @@ -121,6 +112,11 @@ extends TyperState(r) { isCommittable && (!previous.isInstanceOf[MutableTyperState] || previous.isGlobalCommittable) + private var isCommitted = false + + override def uncommittedAncestor: TyperState = + if (isCommitted) previous.uncommittedAncestor else this + /** Commit typer state so that its information is copied into current typer state * In addition (1) the owning state of undetermined or temporarily instantiated * type variables changes from this typer state to the current one. (2) Variables @@ -140,15 +136,9 @@ extends TyperState(r) { targetState.ephemeral |= ephemeral targetState.gc() reporter.flush() - myIsCommitted = true + isCommitted = true } - private var myIsCommitted = false - - override def isCommitted: Boolean = myIsCommitted - - override def parent = Some(previous) - override def gc()(implicit ctx: Context): Unit = { val toCollect = new mutable.ListBuffer[GenericType] constraint foreachTypeVar { tvar => -- cgit v1.2.3