diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2014-01-15 00:03:31 -0800 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2014-01-15 00:03:31 -0800 |
commit | fadf42bc20c8596ffcf421b9e283ebc780ecf602 (patch) | |
tree | 87f0bda057be3845781bb69c405198cbf43016c1 | |
parent | dd875814166f60dd136397ec12ba92d223cb10d0 (diff) | |
parent | a09e143b7fd1c6b433386d45e9c5ae3548819b59 (diff) | |
download | scala-fadf42bc20c8596ffcf421b9e283ebc780ecf602.tar.gz scala-fadf42bc20c8596ffcf421b9e283ebc780ecf602.tar.bz2 scala-fadf42bc20c8596ffcf421b9e283ebc780ecf602.zip |
Merge pull request #3363 from retronym/ticket/8146
Fix non-deterministic <:< for deeply nested types
-rw-r--r-- | src/reflect/scala/reflect/internal/tpe/TypeComparers.scala | 25 | ||||
-rw-r--r-- | src/reflect/scala/reflect/runtime/JavaUniverseForce.scala | 1 | ||||
-rw-r--r-- | test/files/neg/t8146-non-finitary-2.check | 9 | ||||
-rw-r--r-- | test/files/neg/t8146-non-finitary-2.scala | 8 | ||||
-rw-r--r-- | test/files/neg/t8146-non-finitary.check | 9 | ||||
-rw-r--r-- | test/files/neg/t8146-non-finitary.scala | 7 | ||||
-rw-r--r-- | test/files/pos/t8146a.scala | 9 | ||||
-rw-r--r-- | test/files/pos/t8146b.scala | 77 |
8 files changed, 130 insertions, 15 deletions
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala index 2623a47be6..1620d8156b 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -17,20 +17,15 @@ trait TypeComparers { private val _pendingSubTypes = new mutable.HashSet[SubTypePair] def pendingSubTypes = _pendingSubTypes - class SubTypePair(val tp1: Type, val tp2: Type) { - override def hashCode = tp1.hashCode * 41 + tp2.hashCode - override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match { - // 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) - case stp: SubTypePair => - val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t)) - suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2) - 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 a tests to show that we detect the cycle: neg/t8146-no-finitary* + override def toString = tp1+" <:<? "+tp2 } @@ -271,7 +266,7 @@ trait TypeComparers { 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/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala index b3b20a888e..6b3985d434 100644 --- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala +++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala @@ -198,6 +198,7 @@ trait JavaUniverseForce { self: runtime.JavaUniverse => this.ErroneousCollector this.adaptToNewRunMap // inaccessible: this.commonOwnerMapObj + this.SubTypePair this.SymbolKind this.NoSymbol this.CyclicReference 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 + + } +} |