Skip to content

Matching on abstract tuples causes dotty to stackoverflow #8905

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
yilinwei opened this issue May 7, 2020 · 1 comment
Closed

Matching on abstract tuples causes dotty to stackoverflow #8905

yilinwei opened this issue May 7, 2020 · 1 comment
Assignees
@OlivierBlanvillain
Labels
itype:bug

Comments

@yilinwei
Copy link
Contributor

yilinwei commented May 7, 2020 •
edited by smarter
Loading

Minimized code

object Example {

  def failsHorribly[T1 <: Tuple, T2 <: Tuple](f: () => Either[Unit, Tuple.Concat[T1, T2]])(using size: Tuple.Size[T1]): () => Either[Unit, T2] = {
    () => {
      f() match {
        case Left(_) => Left(())
        case Right(item) => Right(item.drop(size).asInstanceOf[T2])
      }
    }
  }
}

Output

...
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4956)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:541)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:530)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4956)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:541)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:530)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4956)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:541)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.op$4(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4895)
        at dotty.tools.dotc.core.Types$TypeMap.mapArgs$1(Types.scala:4897)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4903)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:530)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4956)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.Types$TypeMap.mapOverLambda$1(Types.scala:4934)
        at dotty.tools.dotc.core.Types$TypeMap.mapOver(Types.scala:4936)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:548)
        at dotty.tools.dotc.core.TypeOps$AbstractTypeMap$1.apply(TypeOps.scala:541)
        at dotty.tools.dotc.core.TypeOps.instantiateToSubType(TypeOps.scala:608)
        at dotty.tools.dotc.core.TypeOps.refineUsingParent(TypeOps.scala:509)
        at dotty.tools.dotc.core.Contexts$Context.refineUsingParent(Contexts.scala:78)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.$anonfun$4(Space.scala:608)
        at scala.collection.immutable.List.map(List.scala:246)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.decompose(Space.scala:620)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.tryDecompose1$2(Space.scala:193)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$3(Space.scala:203)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.intersect(Space.scala:229)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.intersect(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$9$$anonfun$1(Space.scala:198)
        at scala.collection.immutable.List.map(List.scala:250)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$3(Space.scala:198)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.intersect(Space.scala:229)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.intersect(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$18$$anonfun$4(Space.scala:266)
        at scala.collection.immutable.List.exists(List.scala:395)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$4(Space.scala:266)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:275)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$4(Space.scala:246)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:275)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$17$$anonfun$3(Space.scala:252)
        at scala.collection.immutable.List.map(List.scala:250)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$4(Space.scala:252)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:275)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$16$$anonfun$2(Space.scala:250)
        at scala.collection.LinearSeqOps.foldLeft(LinearSeq.scala:168)
        at scala.collection.LinearSeqOps.foldLeft$(LinearSeq.scala:164)
        at scala.collection.immutable.List.foldLeft(List.scala:79)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.op$4(Space.scala:250)
        at dotty.tools.dotc.transform.patmat.SpaceLogic.minus(Space.scala:275)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.minus(Space.scala:311)
        at dotty.tools.dotc.transform.patmat.SpaceEngine.checkExhaustivity(Space.scala:829)
        at dotty.tools.dotc.transform.PatternMatcher.transformMatch(PatternMatcher.scala:45)
        at dotty.tools.dotc.transform.MegaPhase.goMatch(MegaPhase.scala:746)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:345)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:287)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.mapDefDef$1(MegaPhase.scala:245)
        at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:248)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:394)
        at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:404)
        at dotty.tools.dotc.transform.MegaPhase.$anonfun$1(MegaPhase.scala:409)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:409)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:286)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:287)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.mapDefDef$1(MegaPhase.scala:245)
        at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:248)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:394)
        at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:404)
        at dotty.tools.dotc.transform.MegaPhase.$anonfun$1(MegaPhase.scala:409)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:409)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:339)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.transformNamed$1(MegaPhase.scala:251)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:394)
        at dotty.tools.dotc.transform.MegaPhase.transformStat$2(MegaPhase.scala:404)
        at dotty.tools.dotc.transform.MegaPhase.$anonfun$1(MegaPhase.scala:409)
        at scala.collection.immutable.List.mapConserve(List.scala:472)
        at dotty.tools.dotc.transform.MegaPhase.transformStats(MegaPhase.scala:409)
        at dotty.tools.dotc.transform.MegaPhase.mapPackage$1(MegaPhase.scala:356)
        at dotty.tools.dotc.transform.MegaPhase.transformUnnamed$1(MegaPhase.scala:359)
        at dotty.tools.dotc.transform.MegaPhase.transformTree(MegaPhase.scala:396)
        at dotty.tools.dotc.transform.MegaPhase.transformUnit(MegaPhase.scala:415)
        at dotty.tools.dotc.transform.MegaPhase.run(MegaPhase.scala:427)
        at dotty.tools.dotc.core.Phases$Phase.runOn$$anonfun$1(Phases.scala:318)
        at scala.collection.immutable.List.map(List.scala:246)
        at dotty.tools.dotc.core.Phases$Phase.runOn(Phases.scala:319)
        at dotty.tools.dotc.Run.runPhases$4$$anonfun$4(Run.scala:165)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:15)
        at dotty.runtime.function.JProcedure1.apply(JProcedure1.java:10)
        at scala.collection.ArrayOps$.foreach$extension(ArrayOps.scala:1323)
        at dotty.tools.dotc.Run.runPhases$5(Run.scala:175)
        at dotty.tools.dotc.Run.compileUnits$$anonfun$1(Run.scala:183)
        at dotty.runtime.function.JFunction0$mcV$sp.apply(JFunction0$mcV$sp.java:12)
        at dotty.tools.dotc.util.Stats$.maybeMonitored(Stats.scala:64)
        at dotty.tools.dotc.Run.compileUnits(Run.scala:190)
        at dotty.tools.dotc.Run.compileSources(Run.scala:127)
        at dotty.tools.dotc.Run.compile(Run.scala:110)
        at dotty.tools.dotc.Driver.doCompile(Driver.scala:38)
        at dotty.tools.dotc.Driver.process(Driver.scala:194)
        at dotty.tools.dotc.Driver.process(Driver.scala:163)
        at dotty.tools.dotc.Driver.process(Driver.scala:175)
        at dotty.tools.dotc.Driver.main(Driver.scala:202)
        at dotty.tools.dotc.Main.main(Main.scala)

Expectation

Probably shouldn't stackoverflow.
@smarter
Copy link
Member

smarter commented May 7, 2020 •
edited
Loading 

  at dotty.tools.dotc.core.TypeOps.instantiateToSubType(TypeOps.scala:608)
  at dotty.tools.dotc.core.Contexts$Context.refineUsingParent(Contexts.scala:78)
  at dotty.tools.dotc.transform.patmat.SpaceEngine.$anonfun$4(Space.scala:608)

The input torefineUsingParent is:

parent = AppliedType(TypeRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class <root>)),module scala),module Tuple),type Concat),List(TypeRef(NoPrefix,type T1), TypeRef(NoPrefix,type T2)))
child = trait NonEmptyTuple

It seems that instantiateToSubType loops on recursive match types /cc @OlivierBlanvillain, @liufengyun

@smarter smarter mentioned this issue May 7, 2020
Merged
OlivierBlanvillain added a commit to dotty-staging/dotty that referenced this issue May 28, 2020
@OlivierBlanvillain
Fix scala#8905: break cycles in instantiateToSubType
2acd964 
Because MatchAliases are bounds, it's unsafe to do a traversal that recursively
inspects bounds. It's kind of a pit fall...
OlivierBlanvillain added a commit to dotty-staging/dotty that referenced this issue May 28, 2020
@OlivierBlanvillain
Fix a similar bug in TypeTestsCasts
68227cc 
I manually inspected all calls to loBound/hiBound and found another place in
the compiler where they are use during a traversal. The added test case fails
on master with a SO, just like scala#8905.
OlivierBlanvillain added a commit to dotty-staging/dotty that referenced this issue May 29, 2020
@OlivierBlanvillain
Fix a similar bug in TypeTestsCasts
1659aab 
I manually inspected all calls to loBound/hiBound and found another place in
the compiler where they are use during a traversal. The added test case fails
on master with a SO, just like scala#8905.
liufengyun added a commit that referenced this issue May 30, 2020
@liufengyun
Merge pull request #9072 from dotty-staging/fix-8905
9a2a3db 
Fix #8905: break cycles in instantiateToSubType
smarter pushed a commit to dotty-staging/dotty that referenced this issue May 30, 2020
@OlivierBlanvillain @smarter
Fix scala#8905: break cycles in instantiateToSubType
85dbbb3 
Because MatchAliases are bounds, it's unsafe to do a traversal that recursively
inspects bounds. It's kind of a pit fall...
smarter pushed a commit to dotty-staging/dotty that referenced this issue May 30, 2020
@OlivierBlanvillain @smarter
Fix a similar bug in TypeTestsCasts
6e0edf2 
I manually inspected all calls to loBound/hiBound and found another place in
the compiler where they are use during a traversal. The added test case fails
on master with a SO, just like scala#8905.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@OlivierBlanvillain OlivierBlanvillain

Labels
itype:bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@smarter @OlivierBlanvillain @yilinwei