scala/scala — pull request #4178 by retronym (2014-12-01 11:22:16+00:00)
Title: 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 2
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 `-1`, which
can be reached by deprecmenting `Depth(0)`.

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])
```

Review by @adriaanm

AFAICR ('r' for reason), this patch should only cause programs that hang the
compiler to compile again, so I'm targetting 2.11.x.