Pattern matching on a `sealed trait` extended by its child leads to stack overflow and crash

[sankalpgambhir]

Compiler version

main: 3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-c90ad6b
3.3.1

originally discovered on 3.3.1, used main for isolation and for the logs below

HOWEVER, works on 3.2.2

Minimized code

sealed trait A:
  class B extends A

def compute(a: A): Boolean =
  a match
    case b: A#B => true

Output (click arrow to expand)

With 3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-c90ad6b (failing):
Identical output for 3.3.1

[�[0minfo�[0m] entering *experimental* thin client - BEEP WHIRR
[�[0minfo�[0m] terminate the server with `shutdown`
> run -color:never /tmp/dotty-test/rec.scala
[info] running (fork) dotty.tools.dotc.Main -classpath /home/sankalp/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.10/scala-library-2.13.10.jar:/home/sankalp/projects/scala-spree/dotty-working/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.4.0-RC1-bin-SNAPSHOT.jar -color:never /tmp/dotty-test/rec.scala
Exception in thread "main" java.lang.StackOverflowError

  unhandled exception while running MegaPhase{protectedAccessors, extmethods, uncacheGivenAliases, elimByName, hoistSuperArgs, forwardDepChecks, specializeApplyMethods, tryCatchPatterns, patternMatcher} on /tmp/dotty-test/rec.scala

  An unhandled exception was thrown in the compiler.
  Please file a crash report here:
  https://github.com/lampepfl/dotty/issues/new/choose

     while compiling: /tmp/dotty-test/rec.scala
        during phase: MegaPhase{protectedAccessors, extmethods, uncacheGivenAliases, elimByName, hoistSuperArgs, forwardDepChecks, specializeApplyMethods, tryCatchPatterns, patternMatcher}
                mode: Mode(ImplicitsEnabled)
     library version: version 2.13.10
    compiler version: version 3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-c90ad6b
            settings: -classpath /home/sankalp/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.10/scala-library-2.13.10.jar:/home/sankalp/projects/scala-spree/dotty-working/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.4.0-RC1-bin-SNAPSHOT.jar -color never

                tree: EmptyTree
       tree position: :<unknown>
           tree type: <notype>
              symbol: val <none>
           call site: package <root> in module class <root>

  == Source file context for tree position ==


	at dotty.tools.dotc.core.Types$LambdaType.paramRefs(Types.scala:3703)
	at dotty.tools.dotc.core.Types$LambdaType.paramRefs$(Types.scala:3680)
	at dotty.tools.dotc.core.Types$MethodOrPoly.paramRefs(Types.scala:3766)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps$$anonfun$2(OrderingConstraint.scala:431)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps$$anonfun$adapted$1(OrderingConstraint.scala:432)
	at scala.collection.immutable.Range.foreach(Range.scala:190)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps(OrderingConstraint.scala:432)
	at dotty.tools.dotc.core.OrderingConstraint.init(OrderingConstraint.scala:535)
	at dotty.tools.dotc.core.OrderingConstraint.add(OrderingConstraint.scala:513)
	at dotty.tools.dotc.core.OrderingConstraint.add(OrderingConstraint.scala:506)
	at dotty.tools.dotc.core.ConstraintHandling.addToConstraint(ConstraintHandling.scala:768)
	at dotty.tools.dotc.core.ConstraintHandling.addToConstraint$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.addToConstraint(TypeComparer.scala:31)
	at dotty.tools.dotc.core.TypeComparer$.addToConstraint(TypeComparer.scala:3116)
	at dotty.tools.dotc.typer.ProtoTypes$.constrained(ProtoTypes.scala:747)
	at dotty.tools.dotc.typer.ProtoTypes$.newTypeVar(ProtoTypes.scala:780)
	at dotty.tools.dotc.core.TypeOps$InferPrefixMap$1.apply(TypeOps.scala:892)
	at dotty.tools.dotc.core.Types$TypeMap.op$proxy18$1(Types.scala:5823)
	at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:5823)
	at dotty.tools.dotc.core.TypeOps$InferPrefixMap$1.apply(TypeOps.scala:895)
	at dotty.tools.dotc.core.TypeOps$.instantiateToSubType(TypeOps.scala:901)
	at dotty.tools.dotc.core.TypeOps$.refineUsingParent(TypeOps.scala:757)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.$anonfun$13(Space.scala:650)
	at scala.collection.immutable.List.map(List.scala:246)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:661)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:669)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:689)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:624)
	<STACK TRACE TRIMMED BY PR AUTHOR>

With 3.2.2 (working):

sbt:rectest> compile
[info] compiling 2 Scala sources to /tmp/dotty-test/rectest/target/scala-3.2.2/classes ...
[success] Total time: 7 s, completed Nov 23, 2023, 12:53:07 PM

Source and Problem

Discovered as epfl-lara/lisa#190, where we are unable to upgrade from 3.2.2, where this does work, to 3.3.1 as we would like to.

[sankalpgambhir]

To add a small thing: note that the following is indeed a complete pattern match:

def compute(a: A): Boolean =
  a match
    case inductive: A#B => ???
    case base: A => ???

It seems to me that the difference of types may be computed incorrectly here? Leading to what looks like the type A#B#B...#B showing up in the minus function in Space.scala

Hope this helps

[Decel]

After bisect:
0dae27d531057ba5a212fdb110870c624a14a2cc is the first bad commit.

Will continue looking, I think it may be a bit more complex.

[Decel]

@sankalpgambhir

Are you able to update LISA now?

[sankalpgambhir]

Thanks for the very quick response, I had been following some of the discussion on the PR.

I am attempting to compile LISA with dotty main, but I ran into some trouble with my little example before, which may be worth a look:

The base example I posted above works now (thanks!):

sealed trait A:
  class B extends A

def compute(a: A): Boolean =
  a match
    case b: A#B => true

But adding a single line base case can lend you a crash again:

sealed trait A:
  class B extends A

class C extends A // <== base case

def compute(a: A): Boolean =
  a match
    case b: A#B => true

    library version: version 2.13.12
    compiler version: version 3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-8d9da73

Running via sbt here.

> run /tmp/sctest/Sealed.scala
[info] running (fork) dotty.tools.dotc.Main -d /home/sankalp/projects/scala-spree/dotty-working/compiler/../out/default-last-scalac-out.jar -classpath /home/sankalp/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.12/scala-library-2.13.12.jar:/home/sankalp/projects/scala-spree/dotty-working/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.4.0-RC1-bin-SNAPSHOT.jar /tmp/sctest/Sealed.scala
Exception in thread "main" java.lang.StackOverflowError

  unhandled exception while running MegaPhase{protectedAccessors, extmethods, uncacheGivenAliases, elimByName, hoistSuperArgs, forwardDepChecks, specializeApplyMethods, tryCatchPatterns, patternMatcher} on /tmp/sctest/Sealed.scala

  An unhandled exception was thrown in the compiler.
  Please file a crash report here:
  https://github.com/lampepfl/dotty/issues/new/choose
  For non-enriched exceptions, compile with -Yno-enrich-error-messages.

     while compiling: /tmp/sctest/Sealed.scala
        during phase: MegaPhase{protectedAccessors, extmethods, uncacheGivenAliases, elimByName, hoistSuperArgs, forwardDepChecks, specializeApplyMethods, tryCatchPatterns, patternMatcher}
                mode: Mode(ImplicitsEnabled)
     library version: version 2.13.12
    compiler version: version 3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped-git-8d9da73
            settings: -classpath /home/sankalp/.cache/coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.12/scala-library-2.13.12.jar:/home/sankalp/projects/scala-spree/dotty-working/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.4.0-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.4.0-RC1-bin-SNAPSHOT.jar -d /

	at dotty.tools.dotc.core.Types$LambdaType.paramRefs(Types.scala:3743)
	at dotty.tools.dotc.core.Types$LambdaType.paramRefs$(Types.scala:3720)
	at dotty.tools.dotc.core.Types$MethodOrPoly.paramRefs(Types.scala:3804)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps$$anonfun$2(OrderingConstraint.scala:433)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps$$anonfun$adapted$1(OrderingConstraint.scala:434)
	at scala.collection.immutable.Range.foreach(Range.scala:190)
	at dotty.tools.dotc.core.OrderingConstraint.adjustDeps(OrderingConstraint.scala:434)
	at dotty.tools.dotc.core.OrderingConstraint.init(OrderingConstraint.scala:537)
	at dotty.tools.dotc.core.OrderingConstraint.add(OrderingConstraint.scala:515)
	at dotty.tools.dotc.core.OrderingConstraint.add(OrderingConstraint.scala:508)
	at dotty.tools.dotc.core.ConstraintHandling.addToConstraint(ConstraintHandling.scala:761)
	at dotty.tools.dotc.core.ConstraintHandling.addToConstraint$(ConstraintHandling.scala:29)
	at dotty.tools.dotc.core.TypeComparer.addToConstraint(TypeComparer.scala:30)
	at dotty.tools.dotc.core.TypeComparer$.addToConstraint(TypeComparer.scala:3217)
	at dotty.tools.dotc.typer.ProtoTypes$.constrained(ProtoTypes.scala:746)
	at dotty.tools.dotc.typer.ProtoTypes$.newTypeVar(ProtoTypes.scala:779)
	at dotty.tools.dotc.core.TypeOps$InferPrefixMap$1.apply(TypeOps.scala:896)
	at dotty.tools.dotc.core.Types$TypeMap.op$proxy18$1(Types.scala:6056)
	at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:6056)
	at dotty.tools.dotc.core.TypeOps$InferPrefixMap$1.apply(TypeOps.scala:899)
	at dotty.tools.dotc.core.TypeOps$.instantiateToSubType(TypeOps.scala:905)
	at dotty.tools.dotc.core.TypeOps$.refineUsingParent(TypeOps.scala:757)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.$anonfun$13(Space.scala:648)
	at scala.collection.immutable.List.map(List.scala:246)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:659)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$Parts$.unapply(Space.scala:687)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.rec$1(Space.scala:622)
	at dotty.tools.dotc.transform.patmat.SpaceEngine$.decompose(Space.scala:667)

       <STACK TRACE TRIMMED BY AUTHOR>