Skip to content
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.

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

Hang in typechecker #5156

Closed
scabug opened this issue Nov 7, 2011 · 2 comments
Closed

Hang in typechecker #5156

scabug opened this issue Nov 7, 2011 · 2 comments
Assignees
Labels

Comments

@scabug
Copy link

scabug commented Nov 7, 2011

The following causes the compiler (2.9.1.final and 2.10.0.r25946-b20111105020221) to hang during implicit search,

sealed trait HList
final case class HCons[H, T <: HList](head : H, tail : T) extends HList 
case object HNil extends HList 

object HList {
  type ::[H, T <: HList] = HCons[H, T]
  type HNil = HNil.type

  implicit def hlistOps[L <: HList](l : L) = new {
    def ::[H](h : H) : H :: L = HCons(h, l)
    def last(implicit last : Last[L]) {}
  }

  class Last[L <: HList]
  implicit def hsingleLast[H] = new Last[H :: HNil]
  implicit def hlistLast[H, T <: HList](implicit lt : Last[T]) = new Last[H :: T]

  type III = Int :: Int :: Int :: HNil
  val iii : III = 0 :: 0 :: 0 :: HNil
  val l = iii.last
}

I haven't been able to minimise this much further. In particular, the hang doesn't occur if there are less than three elements in the list, or if the III type annotation is omitted, or if the last method is not invoked, or if any of the method signatures or implicit structure is altered non-trivially.

The hang seems to be consuming CPU only ... it doesn't appear to be consuming stack or heap, so somehow or other this source seems to have tricked the compiler into a tight loop.

Hitting ctrl-\ on the console for a thread dump gives me this with 2.10.0.r25946-b20111105020221,

Full thread dump Java HotSpot(TM) 64-Bit Server VM (21.1-b02 mixed mode):

"Service Thread" daemon prio=10 tid=0x00007f2ef011a800 nid=0x384c runnable [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C2 CompilerThread1" daemon prio=10 tid=0x00007f2ef0118000 nid=0x384b waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"C2 CompilerThread0" daemon prio=10 tid=0x00007f2ef0115000 nid=0x384a waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"Signal Dispatcher" daemon prio=10 tid=0x00007f2ef0113000 nid=0x3849 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

"Finalizer" daemon prio=10 tid=0x00007f2ef00c8800 nid=0x3848 in Object.wait() [0x00007f2ee7cfb000]
   java.lang.Thread.State: WAITING (on object monitor)
        at java.lang.Object.wait(Native Method)
        - waiting on <0x00000000f050e1b8> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:135)
        - locked <0x00000000f050e1b8> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:151)
        at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:177)

"Reference Handler" daemon prio=10 tid=0x00007f2ef00c6800 nid=0x3847 in Object.wait() [0x00007f2ee7dfc000]
   java.lang.Thread.State: WAITING (on object monitor)
        at java.lang.Object.wait(Native Method)
        - waiting on <0x00000000f050dea8> (a java.lang.ref.Reference$Lock)
        at java.lang.Object.wait(Object.java:503)
        at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:133)
        - locked <0x00000000f050dea8> (a java.lang.ref.Reference$Lock)

"main" prio=10 tid=0x00007f2ef0006800 nid=0x3843 runnable [0x00007f2ef43ff000]
   java.lang.Thread.State: RUNNABLE
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.complexity$1(Implicits.scala:308)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$complexity$1$1.apply(Implicits.scala:310)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$complexity$1$1.apply(Implicits.scala:310)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:233)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:233)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.collection.TraversableLike$class.map(TraversableLike.scala:233)
        at scala.collection.immutable.List.map(List.scala:77)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.complexity$1(Implicits.scala:310)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$complexity$1$1.apply(Implicits.scala:310)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$complexity$1$1.apply(Implicits.scala:310)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:233)
        at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:233)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.collection.TraversableLike$class.map(TraversableLike.scala:233)
        at scala.collection.immutable.List.map(List.scala:77)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.complexity$1(Implicits.scala:310)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$dominates(Implicits.scala:323)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit$2.apply(Implicits.scala:390)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$$anonfun$scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit$2.apply(Implicits.scala:390)
        at scala.collection.LinearSeqOptimized$class.find(LinearSeqOptimized.scala:100)
        at scala.collection.immutable.List.find(List.scala:77)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit(Implicits.scala:390)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.tryImplicitInfo$1(Implicits.scala:740)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.rankImplicits(Implicits.scala:743)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.findBest(Implicits.scala:767)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:825)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.bestImplicit(Implicits.scala:1157)
        at scala.tools.nsc.typechecker.Implicits$class.inferImplicit(Implicits.scala:67)
        at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:401)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:122)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:117)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.tools.nsc.typechecker.Typers$Typer.applyImplicitArgs(Typers.scala:117)
        at scala.tools.nsc.typechecker.Typers$Typer.adaptToImplicitMethod$1(Typers.scala:749)
        at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:897)
        at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:895)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit1(Implicits.scala:524)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit0(Implicits.scala:486)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit(Implicits.scala:398)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.tryImplicitInfo$1(Implicits.scala:740)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.rankImplicits(Implicits.scala:743)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.findBest(Implicits.scala:767)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:825)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.bestImplicit(Implicits.scala:1157)
        at scala.tools.nsc.typechecker.Implicits$class.inferImplicit(Implicits.scala:67)
        at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:401)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:122)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:117)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.tools.nsc.typechecker.Typers$Typer.applyImplicitArgs(Typers.scala:117)
        at scala.tools.nsc.typechecker.Typers$Typer.adaptToImplicitMethod$1(Typers.scala:749)
        at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:897)
        at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:895)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit1(Implicits.scala:524)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.typedImplicit0(Implicits.scala:486)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.scala$tools$nsc$typechecker$Implicits$ImplicitSearch$$typedImplicit(Implicits.scala:398)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.tryImplicitInfo$1(Implicits.scala:740)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.rankImplicits(Implicits.scala:743)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch$ImplicitComputation.findBest(Implicits.scala:767)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.searchImplicit(Implicits.scala:825)
        at scala.tools.nsc.typechecker.Implicits$ImplicitSearch.bestImplicit(Implicits.scala:1157)
        at scala.tools.nsc.typechecker.Implicits$class.inferImplicit(Implicits.scala:67)
        at scala.tools.nsc.Global$$anon$1.inferImplicit(Global.scala:401)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:122)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$applyImplicitArgs$1.apply(Typers.scala:117)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.tools.nsc.typechecker.Typers$Typer.applyImplicitArgs(Typers.scala:117)
        at scala.tools.nsc.typechecker.Typers$Typer.adaptToImplicitMethod$1(Typers.scala:749)
        at scala.tools.nsc.typechecker.Typers$Typer.adapt(Typers.scala:897)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4328)
        at scala.tools.nsc.typechecker.Typers$Typer.typedSelect$1(Typers.scala:3630)
        at scala.tools.nsc.typechecker.Typers$Typer.typed1(Typers.scala:4225)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4319)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4394)
        at scala.tools.nsc.typechecker.Typers$Typer.computeType(Typers.scala:4471)
        at scala.tools.nsc.typechecker.Namers$Namer.assignTypeToTree(Namers.scala:763)
        at scala.tools.nsc.typechecker.Namers$Namer.getSig$1(Namers.scala:1240)
        at scala.tools.nsc.typechecker.Namers$Namer.typeSig(Namers.scala:1264)
        at scala.tools.nsc.typechecker.Namers$Namer$$anonfun$monoTypeCompleter$1$$anonfun$apply$1.apply$mcV$sp(Namers.scala:672)
        at scala.tools.nsc.typechecker.Namers$Namer$$anonfun$monoTypeCompleter$1$$anonfun$apply$1.apply(Namers.scala:671)
        at scala.tools.nsc.typechecker.Namers$Namer$$anonfun$monoTypeCompleter$1$$anonfun$apply$1.apply(Namers.scala:671)
        at scala.tools.nsc.typechecker.Namers$Namer.scala$tools$nsc$typechecker$Namers$Namer$$logAndValidate(Namers.scala:1286)
        at scala.tools.nsc.typechecker.Namers$Namer$$anonfun$monoTypeCompleter$1.apply(Namers.scala:671)
        at scala.tools.nsc.typechecker.Namers$Namer$$anonfun$monoTypeCompleter$1.apply(Namers.scala:670)
        at scala.tools.nsc.typechecker.Namers$$anon$1.completeImpl(Namers.scala:1390)
        at scala.tools.nsc.typechecker.Namers$LockingTypeCompleter$class.complete(Namers.scala:1398)
        at scala.tools.nsc.typechecker.Namers$$anon$1.complete(Namers.scala:1388)
        at scala.reflect.internal.Symbols$Symbol.info(Symbols.scala:890)
        at scala.reflect.internal.Symbols$Symbol.initialize(Symbols.scala:1006)
        at scala.reflect.internal.Symbols$Symbol.annotations(Symbols.scala:1172)
        at scala.tools.nsc.typechecker.MethodSynthesis$MethodSynth$class.finishGetterSetter(MethodSynthesis.scala:77)
        at scala.tools.nsc.typechecker.Namers$Namer.finishGetterSetter(Namers.scala:76)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$12.apply(Typers.scala:1477)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$12.apply(Typers.scala:1477)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$rewrappingWrapperTrees$1.apply(Typers.scala:1416)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$rewrappingWrapperTrees$1.apply(Typers.scala:1413)
        at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:239)
        at scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:239)
        at scala.collection.LinearSeqOptimized$class.foreach(LinearSeqOptimized.scala:59)
        at scala.collection.immutable.List.foreach(List.scala:77)
        at scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:239)
        at scala.collection.immutable.List.flatMap(List.scala:77)
        at scala.tools.nsc.typechecker.Typers$Typer.typedTemplate(Typers.scala:1477)
        at scala.tools.nsc.typechecker.Typers$Typer.typedModuleDef(Typers.scala:1389)
        at scala.tools.nsc.typechecker.Typers$Typer.typed1(Typers.scala:3992)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4319)
        at scala.tools.nsc.typechecker.Typers$Typer.typedStat$1(Typers.scala:2070)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$23.apply(Typers.scala:2159)
        at scala.tools.nsc.typechecker.Typers$Typer$$anonfun$23.apply(Typers.scala:2159)
        at scala.collection.immutable.List.loop$1(List.scala:150)
        at scala.collection.immutable.List.mapConserve(List.scala:166)
        at scala.tools.nsc.typechecker.Typers$Typer.typedStats(Typers.scala:2159)
        at scala.tools.nsc.typechecker.Typers$Typer.typed1(Typers.scala:3985)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4319)
        at scala.tools.nsc.typechecker.Typers$Typer.typed(Typers.scala:4378)
        at scala.tools.nsc.typechecker.Analyzer$typerFactory$$anon$3.apply(Analyzer.scala:94)
        at scala.tools.nsc.Global$GlobalPhase.applyPhase(Global.scala:372)
        at scala.tools.nsc.typechecker.Analyzer$typerFactory$$anon$3$$anonfun$run$1.apply(Analyzer.scala:86)
        at scala.tools.nsc.typechecker.Analyzer$typerFactory$$anon$3$$anonfun$run$1.apply(Analyzer.scala:86)
        at scala.collection.Iterator$class.foreach(Iterator.scala:690)
        at scala.collection.mutable.ListBuffer$$anon$1.foreach(ListBuffer.scala:319)
        at scala.tools.nsc.typechecker.Analyzer$typerFactory$$anon$3.run(Analyzer.scala:86)
        at scala.tools.nsc.Global$Run.compileUnits(Global.scala:1033)
        at scala.tools.nsc.Global$Run.compileSources(Global.scala:1008)
        at scala.tools.nsc.Global$Run.compile(Global.scala:1121)
        at scala.tools.nsc.Driver.doCompile(Driver.scala:31)
        at scala.tools.nsc.Main$.doCompile(Main.scala:81)
        at scala.tools.nsc.Driver.process(Driver.scala:52)
        at scala.tools.nsc.Driver.main(Driver.scala:65)
        at scala.tools.nsc.Main.main(Main.scala)

"VM Thread" prio=10 tid=0x00007f2ef00bf000 nid=0x3846 runnable 

"GC task thread#0 (ParallelGC)" prio=10 tid=0x00007f2ef0012000 nid=0x3844 runnable 

"GC task thread#1 (ParallelGC)" prio=10 tid=0x00007f2ef0014000 nid=0x3845 runnable 

"VM Periodic Task Thread" prio=10 tid=0x00007f2ef0125000 nid=0x384d waiting on condition 

JNI global references: 217

Heap
 PSYoungGen      total 17728K, used 13174K [0x00000000faab0000, 0x00000000fcd50000, 0x0000000100000000)
  eden space 16384K, 80% used [0x00000000faab0000,0x00000000fb78d938,0x00000000fbab0000)
  from space 1344K, 0% used [0x00000000fbab0000,0x00000000fbab0000,0x00000000fbc00000)
  to   space 1344K, 0% used [0x00000000fcc00000,0x00000000fcc00000,0x00000000fcd50000)
 PSOldGen        total 37184K, used 17475K [0x00000000f0000000, 0x00000000f2450000, 0x00000000faab0000)
  object space 37184K, 46% used [0x00000000f0000000,0x00000000f1110d68,0x00000000f2450000)
 PSPermGen       total 45888K, used 23707K [0x00000000eae00000, 0x00000000edad0000, 0x00000000f0000000)
  object space 45888K, 51% used [0x00000000eae00000,0x00000000ec526ec8,0x00000000edad0000)
@scabug
Copy link
Author

scabug commented Nov 7, 2011

Imported From: https://issues.scala-lang.org/browse/SI-5156?orig=1
Reporter: @milessabin
Affected Versions: 2.9.1, 2.9.2

@scabug
Copy link
Author

scabug commented Nov 7, 2011

Commit Message Bot (anonymous) said:
(extempore in r25952) Fixed hang in typechecker.

Another page in the storied history of "check the normalized type,
then act on the unnormalized type", in this case leading to a tight
loop of foreverness. Closes #5156, review by moors.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants