pattern-matching a recursive type - "error during expansion of this match (this is a scalac bug)"

[winitzki]

Reproduction steps

Scala version: 2.13.15

JVM 17

openjdk version "17.0.8.1" 2023-08-24 LTS, OpenJDK Runtime Environment Zulu17.44+53-CA (build 17.0.8.1+1-LTS)

Running on MacBook (Intel)

Compile this Scala code:

object Test {
    final case class Fix[+F[+_]](unfix: F[Fix[F]])   // Define a fixpoint of F.

// Define an example of `F` to use with the Fix constructor.
    sealed trait ExampleF[+A]

    object ExampleF {
      final case class Leaf(s: String) extends ExampleF[Nothing]

      final case class Branch[+A](l: A, r: A) extends ExampleF[A]
    }

    import ExampleF._

// The type Fix[ExampleF] is a binary tree with a String at each leaf.
// Create some values of this type.

    val x = Fix[ExampleF](Branch(Fix(Leaf("x")), Fix(Leaf("y"))))
    val y = Fix[ExampleF](Branch(x, Fix(Leaf("z"))))

// Pattern-match on those trees now:

    x match {
      case Fix(Branch(Fix(_), Fix(_))) => true
    }  // Returns `true`.

    x match {
      case Fix(Branch(Fix(_), Fix(Leaf(_)))) => true  // Causes scalac error with Scala 2.13
    }

    y match {
      case Fix(Branch(Fix(Branch(_, _)), Fix(_))) => true // Causes scalac error with Scala 2.13
    }
}

Result: compilation in Scala 2.13.15 fails with an error:

[error] error during expansion of this match (this is a scalac bug).
[error] The underlying error was: type mismatch;
[error]  found   : Test.ExampleF[Test.Fix[[+A]Test.ExampleF[A]]]
[error]  required: Test.ExampleF[A]

There is no failure with Scala 3.3.1 or 3.4.1.

Problem

The pattern-matching code is expected to be valid Scala, because this looks like a straightforward ADT.

The pattern-matching code as shown can be compiled as long as the depth is not more than 3 nested case classes. The pattern match fails to compile whenever the pattern is deep enough (at least 4 nested case classes or more). In the example shown above, the pattern match on Fix(Branch(Fix(_)... compiles but the pattern Fix(Branch(Fix(Leaf(_)... fails to compile.

The compilation failure occurs with Scala 2.13 but not with Scala 3. (I tested Scala 3.3.1 and Scala 3.4.1.)

There is a possibly related issue #9446 but that issue involves an existential type and no deeply-nested patterns.