From a09e143b7fd1c6b433386d45e9c5ae3548819b59 Mon Sep 17 00:00:00 2001
From: Jason Zaugg <jzaugg@gmail.com>
Date: Tue, 14 Jan 2014 13:37:26 +0100
Subject: SI-8146 Fix non-deterministic <:< for deeply nested types

In the interests of keeping subtyping decidable [1], 152563b
added some bookkeeping to `isSubType` to detect cycles.

However, this was based on a hash set containing instances of
`SubTypePair`, and that class had inconsistencies between its
`hashCode` (in terms of `Type#hashCode`) and `equals`
(in terms of `=:=`).

This inconsistency can be seen in:

    scala> trait C { def apply: (Int @unchecked) }
    defined trait C

    scala> val intUnchecked = typeOf[C].decls.head.info.finalResultType
    intUnchecked: $r.intp.global.Type = Int @unchecked

    scala> val p1 = new SubTypePair(intUnchecked, intUnchecked)
    p1: $r.intp.global.SubTypePair = Int @unchecked <:<? Int @unchecked

    scala> val p2 = new SubTypePair(intUnchecked.withoutAnnotations, intUnchecked.withoutAnnotations)
    p2: $r.intp.global.SubTypePair = Int <:<? Int

    scala> p1 == p2
    res0: Boolean = true

    scala> p1.hashCode == p2.hashCode
    res1: Boolean = false

This commit switches to using `Type#==`, by way of the standard
case class equality.

The risk here is that you could find a subtyping computation that
progresses in such a manner that we don't detect the cycle. It would
need to produce an infinite stream of representations for types that
were `=:=` but not `==`. If that happened, we'd fail to terminate,
rather than judging the relationship as `false`.

[1] http://research.microsoft.com/pubs/64041/fool2007.pdf
---
 test/files/pos/t8146b.scala | 77 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 test/files/pos/t8146b.scala

(limited to 'test/files/pos/t8146b.scala')

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
+
+  }
+}
-- 
cgit v1.2.3