diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2014-01-14 13:37:26 +0100 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2014-01-14 16:00:29 +0100 |
commit | a09e143b7fd1c6b433386d45e9c5ae3548819b59 (patch) | |
tree | 09ab06f0c5532588f6cf96bc132e751f116eea5b /test/files/pos | |
parent | 2e28cf7f76c3d5fd0c2df4274f1af9acb42de699 (diff) | |
download | scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.tar.gz scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.tar.bz2 scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.zip |
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
Diffstat (limited to 'test/files/pos')
-rw-r--r-- | test/files/pos/t8146a.scala | 9 | ||||
-rw-r--r-- | test/files/pos/t8146b.scala | 77 |
2 files changed, 86 insertions, 0 deletions
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 + + } +} |