Skip to content

Recursion limit exceeded (F-bounded type and sealed pattern match) #9631

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
Sciss opened this issue Aug 24, 2020 · 4 comments · Fixed by #9816
Closed

Recursion limit exceeded (F-bounded type and sealed pattern match) #9631

Sciss opened this issue Aug 24, 2020 · 4 comments · Fixed by #9816
Assignees
@liufengyun
Labels
area:f-bounds area:pattern-matching itype:bug itype:crash
Milestone
3.0.0

Comments

@Sciss
Copy link
Contributor

Sciss commented Aug 24, 2020

Minimized code

git clone https://github.com/Sciss/DottyLucre.git
cd DottyLucre
git checkout dotty-issue-9626
sbt compile

Output (click arrow to expand)

crashes in either SkipList or HASkipList of the data module (crash doesn't indicate file or line number)

[info] exception occurred while compiling /home/hhrutz/Documents/devel/DottyLucre/data/src/main/scala/de/sciss/lucre/data/HASkipList.scala, /home/hhrutz/Documents/devel/DottyLucre/data/src/main/scala/de/sciss/lucre/data/Ordered.scala, /home/hhrutz/Documents/devel/DottyLucre/data/src/main/scala/de/sciss/lucre/data/Ordering.scala, /home/hhrutz/Documents/devel/DottyLucre/data/src/main/scala/de/sciss/lucre/data/SkipList.scala
Recursion limit exceeded.
Maybe there is an illegal cyclic reference?
If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
A recurring operation is (inner to outer):

  subtype LazyRef(ile / compileIncremental 1s
  de.sciss.lucre.stm.Txn[
    LazyRef(
      de.sciss.lucre.stm.Txn[
        LazyRef(
          de.sciss.lucre.stm.Txn[

Compiles fine under ++2.13.3.
@smarter smarter added the stat:needs minimization Needs a self contained minimization label Aug 24, 2020
@Sciss
Copy link
Contributor Author

Sciss commented Aug 24, 2020

full log: https://gist.github.com/Sciss/254f302679b21ba2c6b4f00b414624f4

@smarter
Copy link
Member

smarter commented Aug 24, 2020

Reproduce on the latest nightly. Interestingly the crash happens in the exhaustivity checker and not in the typechecker as I thought (/cc @liufengyun ). The interesting part of the stacktrace is:

[error] dotty.tools.dotc.core.TypeComparer.compareAppliedType2$1(TypeComparer.scala:1088)
[error] dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:504)
[error] dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:454)
[error] dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:351)
[error] dotty.tools.dotc.core.TypeComparer.op$proxy4$1(TypeComparer.scala:1204)
[error] dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1219)
[error] dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:408)
[error] dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:351)
[error] dotty.tools.dotc.core.TypeComparer.op$proxy4$1(TypeComparer.scala:1204)
[error] dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1219)
[error] dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:296)
[error] dotty.tools.dotc.core.TypeComparer.op$proxy4$1(TypeComparer.scala:1204)
[error] dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1219)
[error] dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:164)
[error] dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:174)
[error] dotty.tools.dotc.core.TypeComparer.isSubArg$1(TypeComparer.scala:1415)
[error] dotty.tools.dotc.core.TypeComparer.recurArgs$1(TypeComparer.scala:1420)
[error] dotty.tools.dotc.core.TypeComparer.isSubArgs(TypeComparer.scala:1423)
[error] dotty.tools.dotc.core.TypeComparer.checkSubArgs$1(TypeComparer.scala:1012)
[error] dotty.tools.dotc.core.TypeComparer.loop$3(TypeComparer.scala:1014)
[error] dotty.tools.dotc.core.TypeComparer.isMatchingApply$1(TypeComparer.scala:1029)
[error] dotty.tools.dotc.core.TypeComparer.compareAppliedType2$1(TypeComparer.scala:1088)
[error] dotty.tools.dotc.core.TypeComparer.thirdTry$1(TypeComparer.scala:504)
[error] dotty.tools.dotc.core.TypeComparer.secondTry$1(TypeComparer.scala:454)
[error] dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:351)
[error] dotty.tools.dotc.core.TypeComparer.op$proxy4$1(TypeComparer.scala:1204)
[error] dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1219)
[error] dotty.tools.dotc.core.TypeComparer.firstTry$1(TypeComparer.scala:322)
[error] dotty.tools.dotc.core.TypeComparer.op$proxy4$1(TypeComparer.scala:1204)
[error] dotty.tools.dotc.core.TypeComparer.recur(TypeComparer.scala:1219)
[error] dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:164)
[error] dotty.tools.dotc.core.TypeComparer.isSubType(TypeComparer.scala:174)
[error] dotty.tools.dotc.core.TypeComparer.isSub(TypeComparer.scala:176)
[error] dotty.tools.dotc.core.ConstraintHandling.op$proxy1$1(ConstraintHandling.scala:233)
[error] dotty.tools.dotc.core.ConstraintHandling.isSubTypeWhenFrozen(ConstraintHandling.scala:233)
[error] dotty.tools.dotc.core.ConstraintHandling.isSubTypeWhenFrozen$(ConstraintHandling.scala:25)
[error] dotty.tools.dotc.core.TypeComparer.isSubTypeWhenFrozen(TypeComparer.scala:30)
[error] dotty.tools.dotc.core.TypeComparer$.isSubTypeWhenFrozen(TypeComparer.scala:2538)
[error] dotty.tools.dotc.typer.Inferencing$.dotty$tools$dotc$typer$Inferencing$$$instDirection(Inferencing.scala:328)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.apply(Inferencing.scala:130)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.apply(Inferencing.scala:123)
[error] dotty.tools.dotc.core.Types$TypeAccumulator.op$proxy15$1(Types.scala:5392)
[error] dotty.tools.dotc.core.Types$TypeAccumulator.foldArgs$1(Types.scala:5392)
[error] dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5396)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.apply(Inferencing.scala:146)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.apply(Inferencing.scala:123)
[error] dotty.tools.dotc.core.Types$TypeAccumulator.foldOver(Types.scala:5427)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.apply(Inferencing.scala:146)
[error] dotty.tools.dotc.typer.Inferencing$IsFullyDefinedAccumulator.process(Inferencing.scala:157)
[error] dotty.tools.dotc.typer.Inferencing$.isFullyDefined(Inferencing.scala:36)
[error] dotty.tools.dotc.core.TypeOps$.instantiateToSubType(TypeOps.scala:739)
[error] dotty.tools.dotc.core.TypeOps$.refineUsingParent(TypeOps.scala:639)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.$anonfun$4(Space.scala:611)
[error] scala.collection.immutable.List.map(List.scala:246)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.decompose(Space.scala:623)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.tryDecompose2$2(Space.scala:193)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.op$proxy4$1(Space.scala:203)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect(Space.scala:228)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect$(Space.scala:77)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.intersect(Space.scala:316)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.op$proxy4$4$$anonfun$3(Space.scala:198)
[error] scala.collection.immutable.List.map(List.scala:250)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.op$proxy4$1(Space.scala:198)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect(Space.scala:228)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect$(Space.scala:77)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.intersect(Space.scala:316)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.op$proxy4$2$$anonfun$1(Space.scala:197)
[error] scala.collection.immutable.List.map(List.scala:246)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.op$proxy4$1(Space.scala:197)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect(Space.scala:228)
[error] dotty.tools.dotc.transform.patmat.SpaceLogic.intersect$(Space.scala:77)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.intersect(Space.scala:316)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.checkRedundancy$$anonfun$1(Space.scala:881)
[error] dotty.runtime.function.JFunction1$mcVI$sp.apply(JFunction1$mcVI$sp.java:12)
[error] scala.collection.immutable.Range.foreach(Range.scala:190)
[error] dotty.tools.dotc.transform.patmat.SpaceEngine.checkRedundancy(Space.scala:902)
[error] dotty.tools.dotc.transform.PatternMatcher.transformMatch(PatternMatcher.scala:46)
[error] dotty.tools.dotc.transform.MegaPhase.goMatch(MegaPhase.scala:778)
[error] dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:368)
[error] dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:428)
[error] dotty.tools.dotc.transform.MegaPhase.mapDefDef$1(MegaPhase.scala:248)
[error] dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:251)
[error] dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:426)
[error] dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:436)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:441)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:441)
[error] dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:361)
[error] dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:428)
[error] dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:255)
[error] dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:426)
[error] dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:436)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:441)
[error] dotty.tools.dotc.transform.MegaPhase.recur$1(MegaPhase.scala:1060)
[error] dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:441)
[error] dotty.tools.dotc.transform.MegaPhase.mapPackage$1(MegaPhase.scala:381)
[error] dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:384)
[error] dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:428)
[error] dotty.tools.dotc.transform.MegaPhase.transformUnit(MegaPhase.scala:447)
[error] dotty.tools.dotc.transform.MegaPhase.run(MegaPhase.scala:459)

(make sure -XX:MaxJavaStackTraceDepth=100000 to not get a truncated stacktrace)

@Sciss
Copy link
Contributor Author

Sciss commented Aug 24, 2020 •
edited
Loading

Well, there is only one pattern match that could cause it, and indeed removing that avoids the crash. It's comparing SkipList[T, A, _] to Impl[T, A, _] in line 85, which is a debugging function, so for now I can just remove that.

@Sciss
Copy link
Contributor Author

Sciss commented Aug 24, 2020 •
edited
Loading

Minimised:

trait Txn[T <: Txn[T]]

object SkipList {
  trait Set[T <: Txn[T], A] extends SkipList[T, A, A]
}
sealed trait SkipList[T <: Txn[T], A, E]

object HASkipList {
  def debug[T <: Txn[T], A](in: SkipList[T, A, _], key: A)(implicit tx: T): Int = in match {
    case impl: Impl[T, A, _] => impl.foo(key)
    case _ => -1
  }

  private trait Impl[T <: Txn[T], A, E] {
    self: SkipList[T, A, E] =>

    def foo(key: A)(implicit tx: T): Int
  }
}

@Sciss Sciss changed the title Recursion limit exceeded (F-bounded type?) Recursion limit exceeded (F-bounded type and sealed pattern match) Aug 24, 2020
@smarter smarter removed the stat:needs minimization Needs a self contained minimization label Aug 25, 2020
liufengyun added a commit to dotty-staging/dotty that referenced this issue Sep 4, 2020
@liufengyun
Fix scala#9631: handle F-bounds in type expansion
a5b6025
@liufengyun liufengyun mentioned this issue Sep 4, 2020
Closed
@liufengyun liufengyun mentioned this issue Sep 17, 2020
Merged
liufengyun added a commit to dotty-staging/dotty that referenced this issue Sep 18, 2020
@liufengyun
Fix scala#9631: Handle F-bounds with LazyRef
46c87c3
liufengyun added a commit to dotty-staging/dotty that referenced this issue Sep 18, 2020
@liufengyun
Fix scala#9631: Handle F-bounds with LazyRef
6623a5b
@Sciss Sciss mentioned this issue Sep 21, 2020
Closed
liufengyun added a commit to dotty-staging/dotty that referenced this issue Sep 24, 2020
@liufengyun
Fix scala#9631: Handle F-bounds with LazyRef
364a114
@Kordyjan Kordyjan added this to the 3.0.0 milestone Aug 2, 2023
Sciss added a commit to Sciss/HistoricalCode that referenced this issue Sep 1, 2023
@Sciss
work around scala/scala3#9631
764b18a 
by making sure we pat-mat against a known sub-type of `SkipList`
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@liufengyun liufengyun

Labels
area:f-bounds area:pattern-matching itype:bug itype:crash
Projects
None yet
Milestone
3.0.0
4 participants
@smarter @Sciss @liufengyun @Kordyjan