Merge pull request #3367 from retronym/backport/3363

[nomaster]  Fix non-deterministic <:< for deeply nested types

6 files changed, 119 insertions, 0 deletions

diff --git a/test/files/neg/t8146-non-finitary-2.check b/test/files/neg/t8146-non-finitary-2.check
new file mode 100644
index 0000000000..8c2e1436c2
--- /dev/null
+++ b/test/files/neg/t8146-non-finitary-2.check
@@ -0,0 +1,9 @@
+t8146-non-finitary-2.scala:5: error: class graph is not finitary because type parameter X is expansively recursive
+trait C[X] extends N[N[C[D[X]]]]
+        ^
+t8146-non-finitary-2.scala:7: error: type mismatch;
+ found   : C[Int]
+ required: N[C[Int]]
+  def foo(c: C[Int]): N[C[Int]] = c
+                                  ^
+two errors found
diff --git a/test/files/neg/t8146-non-finitary-2.scala b/test/files/neg/t8146-non-finitary-2.scala
new file mode 100644
index 0000000000..c12f5f8f49
--- /dev/null
+++ b/test/files/neg/t8146-non-finitary-2.scala
@@ -0,0 +1,8 @@
+// Example 3 from "On Decidability of Nominal Subtyping with Variance" (Pierce, Kennedy)
+// http://research.microsoft.com/pubs/64041/fool2007.pdf
+trait N[-Z]
+trait D[Y]
+trait C[X] extends N[N[C[D[X]]]]
+object Test {
+  def foo(c: C[Int]): N[C[Int]] = c
+}
diff --git a/test/files/neg/t8146-non-finitary.check b/test/files/neg/t8146-non-finitary.check
new file mode 100644
index 0000000000..8363b750ca
--- /dev/null
+++ b/test/files/neg/t8146-non-finitary.check
@@ -0,0 +1,9 @@
+t8146-non-finitary.scala:4: error: class graph is not finitary because type parameter A is expansively recursive
+trait C[A] extends N[N[C[C[A]]]]
+        ^
+t8146-non-finitary.scala:6: error: type mismatch;
+ found   : C[Int]
+ required: N[C[Int]]
+  def foo(c: C[Int]): N[C[Int]] = c
+                                  ^
+two errors found
diff --git a/test/files/neg/t8146-non-finitary.scala b/test/files/neg/t8146-non-finitary.scala
new file mode 100644
index 0000000000..3d8a3074c7
--- /dev/null
+++ b/test/files/neg/t8146-non-finitary.scala
@@ -0,0 +1,7 @@
+// Example 3 from "On Decidability of Nominal Subtyping with Variance" (Pierce, Kennedy)
+// http://research.microsoft.com/pubs/64041/fool2007.pdf
+trait N[-A]
+trait C[A] extends N[N[C[C[A]]]]
+object Test {
+  def foo(c: C[Int]): N[C[Int]] = c
+}
diff --git a/test/files/pos/t8146a.scala b/test/files/pos/t8146a.scala
new file mode 100644
index 0000000000..e4eb8d3fd1
--- /dev/null
+++ b/test/files/pos/t8146a.scala
@@ -0,0 +1,9 @@
+trait M[+A]
+
+object Test {
+  type Inty = Int
+  def t1(
+          x: M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[Int @unchecked]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
+        ):   M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[M[Inty @unchecked]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
+        = x
+}
diff --git a/test/files/pos/t8146b.scala b/test/files/pos/t8146b.scala
new file mode 100644
index 0000000000..dd031f66c8
--- /dev/null
+++ b/test/files/pos/t8146b.scala
@@ -0,0 +1,77 @@
+// non-deterministic type errors, non-termination.
+// seems to be due to inconsistent hashing/equality in SubTypePair
+
+import scala.language.{existentials, implicitConversions}
+import scala.annotation.unchecked.uncheckedVariance
+
+trait Column[T]
+
+// Turning this into a trait reduces (eliminates?) the likelihood of type errors (but not of non-termination)
+abstract class Shape[Level <: ShapeLevel, -Mixed_, Unpacked_, Packed_]
+
+trait ShapeLevel
+trait NestedShapeLevel extends ShapeLevel
+trait FlatShapeLevel extends NestedShapeLevel
+trait ColumnsShapeLevel extends FlatShapeLevel
+
+trait ProvenShape[U]
+
+object ProvenShape {
+  implicit def proveShapeOf[T, U](v: T)(implicit sh: Shape[_ <: FlatShapeLevel, T, U, _]): ProvenShape[U] = ???
+}
+
+sealed abstract class HList {
+  type Self <: HList
+  type :: [E] = HCons[E, Self]
+  final def :: [E](elem: E): :: [E] = ???
+}
+
+final class HCons[+H, +T <: HList](val head: H, val tail: T) extends HList {
+  type Self = HCons[H @uncheckedVariance, T @uncheckedVariance]
+}
+
+final object HNil extends HList {
+  type Self = HNil.type
+}
+
+// Success is more likely when not using these aliases
+object syntax {
+  type :: [+H, +T <: HList] = HCons[H, T]
+  type HNil = HNil.type
+}
+
+class HListBench {
+
+  import syntax._
+
+  implicit def columnShape[T, Level <: ShapeLevel]: Shape[Level, Column[T], T, Column[T]] = ???
+  implicit def provenShape[T, P](implicit shape: Shape[_ <: FlatShapeLevel, T, _, P]): Shape[FlatShapeLevel, ProvenShape[T], T, P] = ???
+  final class HListShape[Level <: ShapeLevel, M <: HList, U <: HList, P <: HList](val shapes: Seq[Shape[_ <: ShapeLevel, _, _, _]]) extends Shape[Level, M, U, P]
+  implicit def hnilShape[Level <: ShapeLevel] = new HListShape[Level, HNil.type, HNil.type, HNil.type](Nil)
+  implicit def hconsShape[Level <: ShapeLevel, M1, M2 <: HList, U1, U2 <: HList, P1, P2 <: HList]
+    (implicit s1: Shape[_ <: Level, M1, U1, P1], s2: HListShape[_ <: Level, M2, U2, P2]) =
+    new HListShape[Level, M1 :: M2, U1 :: U2, P1 :: P2](s1 +: s2.shapes)
+
+  trait A[T] {
+    def * : ProvenShape[T]
+  }
+
+  trait B extends A[
+    Int :: Int :: Int :: Int :: Int ::
+    Int :: Int :: Int :: Int :: Int ::
+    Int :: Int :: Int :: Int :: Int ::
+    Int :: Int :: Int :: Int :: Int ::
+    Int :: Int :: Int :: Int :: Int ::
+    Int :: Int :: HNil ] {
+
+    def c: Column[Int]
+
+    def * = c :: c :: c :: c :: c ::
+            c :: c :: c :: c :: c ::
+            c :: c :: c :: c :: c ::
+            c :: c :: c :: c :: c ::
+            c :: c :: c :: c :: c ::
+            c :: c :: HNil
+
+  }
+}