From 081b82fdba37734f28c00417bfad12171a096710 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Mon, 1 Dec 2014 11:58:31 +1000 Subject: SI-9018 Fix regression: cycle in LUBs Regressed in 4412a92d, which admirably sought to impose some structure on the domain of depths, but failed to preserve an imporatnt part of said structure. When calculating LUBs and GLBs, the recursion depth is limited by propagating a decreasing depth parameter. Its initial value is the recursion limit, and is calcluated from the maximum depth of the types fed into the calculation. Here are a few examples that give a flavour of this calculation: ``` scala> class M[A] defined class M scala> class N extends M[M[M[M[A]]]] :34: error: not found: type A class N extends M[M[M[M[A]]]] ^ scala> class N extends M[M[M[M[Int]]]] defined class N scala> lubDepth(typeOf[N] :: Nil) res5: scala.reflect.internal.Depth = Depth(4) scala> type T = M[Int] with M[M[Int]] defined type alias T scala> lubDepth(typeOf[T] :: Nil) res7: scala.reflect.internal.Depth = Depth(3) ``` One parts of the LUB calculation, `lub0`, truncates the lub to `Any` when the depth dives below zero. Before 4412a92d: ------------------ value decr incr ------------------ -3 -3 -2 (= AnyDepth) -2 -3 -1 -1 -2 0 0 -1 1 1 0 2 ... After 4412a92d: ----------------------- value decr incr ----------------------- -MaxInt -MaxInt -MaxInt (= AnyDepth) 0 -MaxInt 1 1 0 2 ... The crucial difference that triggered the regression is that decrementing a depth of zero now goes to the sentinel value, `AnyDepth`, rather than to `-1`. This commit modifies `Depth` to allow it to represent any negative depth. It also switches the sentinel value for `AnyDepth`. Even though I don't believe it is needed, I have also allowed for `Depth.Zero.decr.decr.decr == Depth.AnyVal`, which was historically the case in 2.10.4. To better understand what was happening, I added tracing to the calculation and diffed the before and after: https://gist.github.com/retronym/ec59608eecc52bb497fa Notice that when `elimSub(ts, depth = 0)` recursively calls `lub`, it does so with the variant that caluculates the allowable depth from the shape of the given types. We can then infinitely recurse. Before 4412a92d: ``` |-- elimSub(depth = 0, ts = List(Comparable[_ >: TestObject.E.Value with String <: Comparable[_ >: TestObject.E.Valu | |-- lub(depth = -1, ts = List(TestObject.E.Value with String, TestObject.C)) | | |-- lub0(depth = -1, ts0 = List(TestObject.E.Value with String, TestObject.C)) | | | |-- elimSub(depth = -1, ts = List(TestObject.E.Value with String, TestObject.C)) | | | |== List(TestObject.E.Value with String, TestObject.C) | | | |-- Truncating LUB to | | | |== Any | | |== Any | |== Any |== List(Comparable[_ >: TestObject.E.Value with String <: Comparable[_ >: TestObject.E.Value with String <: java.io |-- lub(depth = 0, ts = List(java.lang.type, java.lang.type)) | |-- lub0(depth = 0, ts0 = List(java.lang.type, java.lang.type)) | | |-- elimSub(depth = 0, ts = List(java.lang.type, java.lang.type)) | | |== List(java.lang.type) | |== java.lang.type |== java.lang.type |-- elimSub(depth = 0, ts = List(Object, Object)) |== List(Object) |-- elimSub(depth = 0, ts = List(Any, Any)) |== List(Any) ``` After 4412a92d: ``` |-- elimSub(depth = 0, ts = List(Comparable[_ >: TestObject.E.Value with String <: Comparable[_ >: TestObject.E.Valu | |-- lub(depth = _, ts = List(TestObject.E.Value with String, TestObject.C)) | | |-- lub(depth = 3, ts = List(TestObject.E.Value with String, TestObject.C)) | | | |-- lub0(depth = 3, ts0 = List(TestObject.E.Value with String, TestObject.C)) | | | | |-- elimSub(depth = 3, ts = List(TestObject.E.Value with String, TestObject.C)) | | | | |== List(TestObject.E.Value with String, TestObject.C) | | | | |-- lub1(depth = 3, ts = List(TestObject.E.Value with String, TestObject.C)) | | | | | |-- elimSub(depth = 3, ts = List(scala.math.Ordered[TestObject.E.Value], scala.math.Orde | | | | | |== List(scala.math.Ordered[TestObject.E.Value], scala.math.Ordered[TestObject.C]) ``` --- test/files/pos/t9018.scala | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 test/files/pos/t9018.scala (limited to 'test/files') diff --git a/test/files/pos/t9018.scala b/test/files/pos/t9018.scala new file mode 100644 index 0000000000..7fb4cf21b3 --- /dev/null +++ b/test/files/pos/t9018.scala @@ -0,0 +1,16 @@ +object TestObject { + + def m(i: Int): AnyRef = i match { + case 0 => new C() + case 1 => Some(E.A).getOrElse("") + } + + class C extends Ordered[C] { + def compare(that: C): Int = ??? + } + + object E extends Enumeration { + type CharacterClass = Value + val A = Value + } +} -- cgit v1.2.3