summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/reflect/scala/reflect/internal/Types.scala35
-rw-r--r--test/files/neg/t8146-non-finitary-2.check9
-rw-r--r--test/files/neg/t8146-non-finitary-2.scala8
-rw-r--r--test/files/neg/t8146-non-finitary.check9
-rw-r--r--test/files/neg/t8146-non-finitary.scala7
-rw-r--r--test/files/pos/t8146a.scala9
-rw-r--r--test/files/pos/t8146b.scala77
7 files changed, 129 insertions, 25 deletions
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index c684f4d690..2f49995030 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -5230,30 +5230,15 @@ trait Types extends api.Types { self: SymbolTable =>
}
}
- class SubTypePair(val tp1: Type, val tp2: Type) {
- override def hashCode = tp1.hashCode * 41 + tp2.hashCode
- override def equals(other: Any) = other match {
- case stp: SubTypePair =>
- // suspend TypeVars in types compared by =:=,
- // since we don't want to mutate them simply to check whether a subtype test is pending
- // in addition to making subtyping "more correct" for type vars,
- // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion)
- // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold)
- def suspend(tp: Type) =
- if (tp.isGround) null else suspendTypeVarsInType(tp)
- def revive(suspension: List[TypeVar]) =
- if (suspension ne null) suspension foreach (_.suspended = false)
-
- val suspensions = Array(tp1, stp.tp1, tp2, stp.tp2) map suspend
-
- val sameTypes = (tp1 =:= stp.tp1) && (tp2 =:= stp.tp2)
-
- suspensions foreach revive
-
- sameTypes
- case _ =>
- false
- }
+ final case class SubTypePair(tp1: Type, tp2: Type) {
+ // SI-8146 we used to implement equality here in terms of pairwise =:=.
+ // But, this was inconsistent with hashCode, which was based on the
+ // Type#hashCode, based on the structure of types, not the meaning.
+ // Now, we use `Type#{equals,hashCode}` as the (consistent) basis for
+ // detecting cycles (aka keeping subtyping decidable.)
+ //
+ // I added tests to show that we detect the cycle: neg/t8146-no-finitary*
+
override def toString = tp1+" <:<? "+tp2
}
@@ -5819,7 +5804,7 @@ trait Types extends api.Types { self: SymbolTable =>
if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
val p = new SubTypePair(tp1, tp2)
if (pendingSubTypes(p))
- false
+ false // see neg/t8146-no-finitary*
else
try {
pendingSubTypes += p
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
+
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-15 23:19:52 +0000