Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1, Scala 2.9.2
    • Fix Version/s: None
    • Component/s: Misc Compiler
    • Labels:

      Description

      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)
      

        Activity

        Hide
        Commit Message Bot added a comment -

        (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 SI-5156, review by moors.

        Show
        Commit Message Bot added a comment - (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 SI-5156 , review by moors.

          People

          • Assignee:
            Paul Phillips
            Reporter:
            Miles Sabin
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development