Recursive match type used as a bound diverges, OK as type constraint

[milessabin]

In the following example, call sites using p1 (which uses the match type as a bound) diverge, whereas call sites using p2 (which uses the match type as a constraint) compile successfully.

object Test {
  // The identity on types of the form N | P[a, P[b, ... P[z, N]]]
  type Nested[X, P[_, _], N] = X match {
    case N => N
    case P[a, b] => P[a, Nested[b, P, N]]
  }

  // Type bound:
  //   Recursion limit exceeded.
  //   Maybe there is an illegal cyclic reference?
  def p1[T <: Nested[T, Tuple2, Unit]](t: T): T = t
  p1(())
  p1((23, ()))
  p1(("foo", (23, ())))

  // Type constraint: OK
  def p2[T](t: T)(erased implicit ev: T <:< Nested[T, Tuple2, Unit]): T = t
  p2(())
  p2((23, ()))
  p2(("foo", (23, ())))
}

It's not immediately obvious to me why the two cases should differ.

[milessabin]

I suspected that #5657 might improve things on this issue, but sadly not.

Reduced the example more to,

object Test {
  // The identity on Unit
  type IdUnit[X] = X match {
    case Unit => Unit
  }

  // Type bound:
  //   Recursion limit exceeded.
  //   Maybe there is an illegal cyclic reference?
  def p1[T <: IdUnit[T]](t: T): T = t
  p1(())

  // Type constraint: OK
  def p2[T](t: T)(erased implicit ev: T <:< IdUnit[T]): T = t
  p2(())
}

[abgruszecki]

The issue described in #5682 is that F-bounds involving match types are problematic. Here's an idea to possibly explore later: are "indirect" F-bounds problematic? Consider:

def p1[T, Y >: T <: Nested[T, Tuple2, Unit](t: T): T = t

The above enforces that T <: Y <: Nested[T, Tuple2, Unit], which still indirectly enforces that T <: Nested[T, Tuple2, Unit]. It also still causes a cyclic reference error. The following semi-works, but only for equivalent of p1(()):

object Test {
  // The identity on types of the form N | P[a, P[b, ... P[z, N]]]
  type Nested[X, P[_, _], N] = X match {
    case N => N
    case P[a, b] => P[a, Nested[b, P, N]]
  }

  class Foo[T] { def apply[Y >: T <: Nested[T, Tuple2, Unit]](t: T): T = t }
  def foo[T] = new Foo[T]
  foo.apply(())
}

(See #5735)

Idea to explore in future: if we had multiple parameter lists, could we simulate such bounds with the below?

  def p1[T][Y >: T <: Nested[T, Tuple2, Unit]]