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

sankalpgambhir · 2023-11-23T11:59:01Z

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 · 2023-11-23T13:57:30Z

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 · 2023-11-29T18:34:08Z

After bisect:
0dae27d531057ba5a212fdb110870c624a14a2cc is the first bad commit.

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

Decel · 2023-12-18T23:23:38Z

@sankalpgambhir

Are you able to update LISA now?

sankalpgambhir · 2023-12-19T11:39:48Z

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>

sankalpgambhir · 2023-12-19T11:46:47Z

We have a similar base case in LISA as well :(

Setting the scala version in sbt to the nightly from maven: 3.4.0-RC1-bin-20231218-ec2b8bc-NIGHTLY

I get a similar crash while compiling LISA as well.

The base case was not necessary to reproduce the crash before, so I did not think of including it in my minimal example for this issue, sorry about that.

sankalpgambhir · 2023-12-19T11:48:06Z

Do you mind if I reopen the issue, @Decel, or would it be better to create a separate one?

Fix #19031

sankalpgambhir added itype:bug itype:crash stat:needs triage Every issue needs to have an "area" and "itype" label labels Nov 23, 2023

sankalpgambhir mentioned this issue Nov 23, 2023

Unsealed Proof class epfl-lara/lisa#190

Closed

sankalpgambhir changed the title ~~Pattern Matching on a sealed trait extended by its child leads to stack overflow and crash~~ Pattern matching on a sealed trait extended by its child leads to stack overflow and crash Nov 23, 2023

nicolasstucki added area:pattern-matching and removed stat:needs triage Every issue needs to have an "area" and "itype" label labels Nov 23, 2023

nicolasstucki assigned dwijnand Nov 23, 2023

Decel added the regression This worked in a previous version but doesn't anymore label Nov 29, 2023

dwijnand linked a pull request Dec 6, 2023 that will close this issue

Remove unnecessary and recursive Space decomposition #19216

Merged

dwijnand closed this as completed in #19216 Dec 18, 2023

Decel reopened this Dec 19, 2023

dwijnand mentioned this issue Jan 4, 2024

Improve recursive decompose prefix fix #19375

Merged

Decel closed this as completed in #19375 Jan 6, 2024

Decel added a commit that referenced this issue Jan 6, 2024

Improve recursive decompose prefix fix (#19375)

c15cc9c

Fix #19031

Kordyjan added this to the 3.4.1 milestone Feb 14, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

sankalpgambhir commented Nov 23, 2023

sankalpgambhir commented Nov 23, 2023

Decel commented Nov 29, 2023 •

edited

Loading

Decel commented Dec 18, 2023

sankalpgambhir commented Dec 19, 2023 •

edited

Loading

sankalpgambhir commented Dec 19, 2023

sankalpgambhir commented Dec 19, 2023 •

edited

Loading

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

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

Comments

sankalpgambhir commented Nov 23, 2023

Compiler version

Minimized code

Output (click arrow to expand)

Source and Problem

sankalpgambhir commented Nov 23, 2023

Decel commented Nov 29, 2023 • edited Loading

Decel commented Dec 18, 2023

sankalpgambhir commented Dec 19, 2023 • edited Loading

sankalpgambhir commented Dec 19, 2023

sankalpgambhir commented Dec 19, 2023 • edited Loading

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

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

Decel commented Nov 29, 2023 •

edited

Loading

sankalpgambhir commented Dec 19, 2023 •

edited

Loading

sankalpgambhir commented Dec 19, 2023 •

edited

Loading