Experimental option -Ybreak-cycles.

Overcomes cycles encountered during classfile parsing
in possibly sketchy fashion.

  "illegal cyclic reference involving class Foo"

is the watchword.  See SI-3809.

21 files changed, 152 insertions, 45 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index cb5e2ad555..fb9539e2b2 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -1046,6 +1046,12 @@ class Global(var currentSettings: Settings, var reporter: Reporter)
   def currentUnit: CompilationUnit = if (currentRun eq null) NoCompilationUnit else currentRun.currentUnit
   def currentSource: SourceFile    = if (currentUnit.exists) currentUnit.source else lastSeenSourceFile
 
+  override def isPastTyper = (
+       (curRun ne null)
+    && (currentRun.typerPhase ne null)
+    && (globalPhase.id > currentRun.typerPhase.id)
+  )
+
   // TODO - trim these to the absolute minimum.
   @inline final def exitingErasure[T](op: => T): T        = exitingPhase(currentRun.erasurePhase)(op)
   @inline final def exitingPostErasure[T](op: => T): T    = exitingPhase(currentRun.posterasurePhase)(op)
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 3ff7af791b..4829fb81b5 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -127,6 +127,7 @@ trait ScalaSettings extends AbsScalaSettings
   val overrideObjects = BooleanSetting    ("-Yoverride-objects", "Allow member objects to be overridden.")
   val overrideVars    = BooleanSetting    ("-Yoverride-vars", "Allow vars to be overridden.")
   val Yhelp           = BooleanSetting    ("-Y", "Print a synopsis of private options.")
+  val breakCycles     = BooleanSetting    ("-Ybreak-cycles", "Attempt to break cycles encountered during classfile parsing")
   val browse          = PhasesSetting     ("-Ybrowse", "Browse the abstract syntax tree after")
   val check           = PhasesSetting     ("-Ycheck", "Check the tree at the end of")
   val Yshow           = PhasesSetting     ("-Yshow", "(Requires -Xshow-class or -Xshow-object) Show after")
diff --git a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
index f12f08030b..7c02f094ed 100644
--- a/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/ContextErrors.scala
@@ -657,8 +657,8 @@ trait ContextErrors {
       def CyclicAliasingOrSubtypingError(errPos: Position, sym0: Symbol) =
         issueTypeError(PosAndMsgTypeError(errPos, "cyclic aliasing or subtyping involving "+sym0))
 
-      def CyclicReferenceError(errPos: Position, lockedSym: Symbol) =
-        issueTypeError(PosAndMsgTypeError(errPos, "illegal cyclic reference involving " + lockedSym))
+      def CyclicReferenceError(errPos: Position, tp: Type, lockedSym: Symbol) =
+        issueTypeError(PosAndMsgTypeError(errPos, s"illegal cyclic reference involving $tp and $lockedSym"))
 
       // macro-related errors (also see MacroErrors below)
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Namers.scala b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
index 9e1a9d6d17..4b60fd8b27 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Namers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Namers.scala
@@ -711,8 +711,9 @@ trait Namers extends MethodSynthesis {
       tp match {
         case TypeBounds(lo, _) =>
           // check that lower bound is not an F-bound
+          // but carefully: class Foo[T <: Bar[_ >: T]] should be allowed
           for (TypeRef(_, sym, _) <- lo)
-            sym.initialize
+            sym.maybeInitialize
         case _ =>
       }
       tp
@@ -731,17 +732,6 @@ trait Namers extends MethodSynthesis {
         if (needsCycleCheck && !typer.checkNonCyclic(tree.pos, tp))
           sym setInfo ErrorType
       }
-      // tree match {
-      //   case ClassDef(_, _, _, impl) =>
-      //     val parentsOK = (
-      //          treeInfo.isInterface(sym, impl.body)
-      //       || (sym eq ArrayClass)
-      //       || (sym isSubClass AnyValClass)
-      //     )
-      //     if (!parentsOK)
-      //       ensureParent(sym, AnyRefClass)
-      //   case _ => ()
-      // }
     }
 
     def moduleClassTypeCompleter(tree: ModuleDef) = {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 688b4b5160..7a2c64142d 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -292,8 +292,7 @@ trait Typers extends Modes with Adaptations with Tags {
      */
     def checkNonCyclic(pos: Position, tp: Type): Boolean = {
       def checkNotLocked(sym: Symbol) = {
-        sym.initialize
-        sym.lockOK || { CyclicAliasingOrSubtypingError(pos, sym); false }
+        sym.initialize.lockOK || { CyclicAliasingOrSubtypingError(pos, sym); false }
       }
       tp match {
         case TypeRef(pre, sym, args) =>
@@ -320,7 +319,7 @@ trait Typers extends Modes with Adaptations with Tags {
     }
 
     def checkNonCyclic(pos: Position, tp: Type, lockedSym: Symbol): Boolean = try {
-      if (!lockedSym.lock(CyclicReferenceError(pos, lockedSym))) false
+      if (!lockedSym.lock(CyclicReferenceError(pos, tp, lockedSym))) false
       else checkNonCyclic(pos, tp)
     } finally {
       lockedSym.unlock()
diff --git a/src/reflect/scala/reflect/internal/SymbolTable.scala b/src/reflect/scala/reflect/internal/SymbolTable.scala
index 90e49f2043..38e33c001c 100644
--- a/src/reflect/scala/reflect/internal/SymbolTable.scala
+++ b/src/reflect/scala/reflect/internal/SymbolTable.scala
@@ -48,6 +48,7 @@ abstract class SymbolTable extends macros.Universe
   def abort(msg: String): Nothing    = throw new FatalError(supplementErrorMessage(msg))
 
   def shouldLogAtThisPhase = false
+  def isPastTyper = false
 
   @deprecated("Give us a reason", "2.10.0")
   def abort(): Nothing = abort("unknown error")
diff --git a/src/reflect/scala/reflect/internal/Symbols.scala b/src/reflect/scala/reflect/internal/Symbols.scala
index f9f1ea3936..d506a43829 100644
--- a/src/reflect/scala/reflect/internal/Symbols.scala
+++ b/src/reflect/scala/reflect/internal/Symbols.scala
@@ -1398,6 +1398,10 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
       if (!isInitialized) info
       this
     }
+    def maybeInitialize: this.type = {
+      try initialize
+      catch { case _: CyclicReference => debuglog("Encountering cycle in maybe-initialization of $this") ; this }
+    }
 
     /** Called when the programmer requests information that might require initialization of the underlying symbol.
      *
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 3f0b620ee2..9a43ad441f 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -91,6 +91,7 @@ trait Types extends api.Types { self: SymbolTable =>
 
   private final val printLubs = sys.props contains "scalac.debug.lub"
   private final val traceTypeVars = sys.props contains "scalac.debug.tvar"
+  private final val breakCycles = settings.breakCycles.value
   /** In case anyone wants to turn off lub verification without reverting anything. */
   private final val verifyLubs = true
   /** In case anyone wants to turn off type parameter bounds being used
@@ -1615,6 +1616,37 @@ trait Types extends api.Types { self: SymbolTable =>
     )
   }
 
+  protected def computeBaseClasses(tpe: Type): List[Symbol] = {
+    def csym = tpe.typeSymbol
+    csym :: {
+      if (tpe.parents.isEmpty || csym.hasFlag(PACKAGE)) Nil
+      else {
+        //Console.println("computing base classes of " + typeSymbol + " at phase " + phase);//DEBUG
+        // optimized, since this seems to be performance critical
+        val superclazz = tpe.firstParent
+        var mixins     = tpe.parents.tail
+        val sbcs       = superclazz.baseClasses
+        var bcs        = sbcs
+        def isNew(clazz: Symbol): Boolean = (
+          superclazz.baseTypeIndex(clazz) < 0 &&
+          { var p = bcs;
+            while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
+            p eq sbcs
+          }
+        )
+        while (!mixins.isEmpty) {
+          def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
+            if (mbcs.isEmpty) bcs
+            else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
+            else addMixinBaseClasses(mbcs.tail)
+          bcs = addMixinBaseClasses(mixins.head.baseClasses)
+          mixins = mixins.tail
+        }
+        bcs
+      }
+    }
+  }
+
   protected def defineBaseTypeSeqOfCompoundType(tpe: CompoundType) = {
     val period = tpe.baseTypeSeqPeriod
     if (period != currentPeriod) {
@@ -1675,41 +1707,60 @@ trait Types extends api.Types { self: SymbolTable =>
       throw new TypeError("illegal cyclic inheritance involving " + tpe.typeSymbol)
   }
 
-  protected def defineBaseClassesOfCompoundType(tpe: CompoundType) = {
-    def computeBaseClasses: List[Symbol] =
-      if (tpe.parents.isEmpty) List(tpe.typeSymbol)
-      else {
-        //Console.println("computing base classes of " + typeSymbol + " at phase " + phase);//DEBUG
-        // optimized, since this seems to be performance critical
-        val superclazz = tpe.firstParent
-        var mixins = tpe.parents.tail
-        val sbcs = superclazz.baseClasses
-        var bcs = sbcs
-        def isNew(clazz: Symbol): Boolean =
-          superclazz.baseTypeIndex(clazz) < 0 &&
-          { var p = bcs;
-            while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
-            p eq sbcs
-          }
-        while (!mixins.isEmpty) {
-          def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
-            if (mbcs.isEmpty) bcs
-            else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
-            else addMixinBaseClasses(mbcs.tail)
-          bcs = addMixinBaseClasses(mixins.head.baseClasses)
-          mixins = mixins.tail
+  object baseClassesCycleMonitor {
+    private var open: List[Symbol] = Nil
+    @inline private def cycleLog(msg: => String) {
+      Console.err.println(msg)
+    }
+    def size = open.size
+    def push(clazz: Symbol) {
+      cycleLog("+ " + ("  " * size) + clazz.fullNameString)
+      open ::= clazz
+    }
+    def pop(clazz: Symbol) {
+      assert(open.head eq clazz, (clazz, open))
+      open = open.tail
+    }
+    def isOpen(clazz: Symbol) = open contains clazz
+  }
+
+  protected def defineBaseClassesOfCompoundType(tpe: CompoundType) {
+    def define = defineBaseClassesOfCompoundType(tpe, force = false)
+    if (isPastTyper || !breakCycles) define
+    else tpe match {
+      // non-empty parents helpfully excludes all package classes
+      case tpe @ ClassInfoType(_ :: _, _, clazz) if !clazz.isAnonOrRefinementClass =>
+        // Cycle: force update
+        if (baseClassesCycleMonitor isOpen clazz)
+          defineBaseClassesOfCompoundType(tpe, force = true)
+        else {
+          baseClassesCycleMonitor push clazz
+          try define
+          finally baseClassesCycleMonitor pop clazz
         }
-        tpe.typeSymbol :: bcs
-      }
+      case _ =>
+        define
+    }
+  }
+  private def defineBaseClassesOfCompoundType(tpe: CompoundType, force: Boolean) {
     val period = tpe.baseClassesPeriod
-    if (period != currentPeriod) {
+    if (period == currentPeriod) {
+      if (force && breakCycles) {
+        def what = tpe.typeSymbol + " in " + tpe.typeSymbol.owner.fullNameString
+        val bcs  = computeBaseClasses(tpe)
+        tpe.baseClassesCache = bcs
+        warning(s"Breaking cycle in base class computation of $what ($bcs)")
+      }
+    }
+    else {
       tpe.baseClassesPeriod = currentPeriod
       if (!isValidForBaseClasses(period)) {
         val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, baseClassesNanos) else null
         try {
           tpe.baseClassesCache = null
-          tpe.baseClassesCache = tpe.memo(computeBaseClasses)(tpe.typeSymbol :: _.baseClasses.tail)
-        } finally {
+          tpe.baseClassesCache = tpe.memo(computeBaseClasses(tpe))(tpe.typeSymbol :: _.baseClasses.tail)
+        }
+        finally {
           if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
         }
       }
diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
index 459326e96f..844ecf908a 100644
--- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
+++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
@@ -47,4 +47,5 @@ abstract class MutableSettings extends AbsSettings {
   def XoldPatmat: BooleanSetting
   def XnoPatmatAnalysis: BooleanSetting
   def XfullLubs: BooleanSetting
+  def breakCycles: BooleanSetting
 }
diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala
index da4f4fbda1..08d58aaadc 100644
--- a/src/reflect/scala/reflect/runtime/Settings.scala
+++ b/src/reflect/scala/reflect/runtime/Settings.scala
@@ -43,6 +43,7 @@ class Settings extends MutableSettings {
   val printtypes        = new BooleanSetting(false)
   val uniqid            = new BooleanSetting(false)
   val verbose           = new BooleanSetting(false)
+  val breakCycles       = new BooleanSetting(false)
 
   val Yrecursion        = new IntSetting(0)
   val maxClassfileName  = new IntSetting(255)
diff --git a/test/files/lib/jsoup-1.3.1.jar.desired.sha1 b/test/files/lib/jsoup-1.3.1.jar.desired.sha1
new file mode 100644
index 0000000000..46fa3dae9d
--- /dev/null
+++ b/test/files/lib/jsoup-1.3.1.jar.desired.sha1
@@ -0,0 +1 @@
+346d3dff4088839d6b4d163efa2892124039d216 ?jsoup-1.3.1.jar
diff --git a/test/files/pos/cycle-bounds.scala b/test/files/pos/cycle-bounds.scala
new file mode 100644
index 0000000000..0aa7aa552b
--- /dev/null
+++ b/test/files/pos/cycle-bounds.scala
@@ -0,0 +1 @@
+class Foo[T <: Comparable[_ >: T]]
diff --git a/test/files/pos/cycle-jsoup.flags b/test/files/pos/cycle-jsoup.flags
new file mode 100644
index 0000000000..ca20f55172
--- /dev/null
+++ b/test/files/pos/cycle-jsoup.flags
@@ -0,0 +1 @@
+-Ybreak-cycles
diff --git a/test/files/pos/cycle-jsoup.scala b/test/files/pos/cycle-jsoup.scala
new file mode 100644
index 0000000000..879e693537
--- /dev/null
+++ b/test/files/pos/cycle-jsoup.scala
@@ -0,0 +1,5 @@
+object Test {
+  def main(args : Array[String]) {
+    org.jsoup.Jsoup.parse(null: java.net.URL, 3000)
+  }
+}
diff --git a/test/files/pos/cycle.flags b/test/files/pos/cycle.flags
new file mode 100644
index 0000000000..ca20f55172
--- /dev/null
+++ b/test/files/pos/cycle.flags
@@ -0,0 +1 @@
+-Ybreak-cycles
diff --git a/test/files/pos/cycle/J_1.java b/test/files/pos/cycle/J_1.java
new file mode 100644
index 0000000000..0cc218eebe
--- /dev/null
+++ b/test/files/pos/cycle/J_1.java
@@ -0,0 +1,16 @@
+package bar;
+
+public class J_1 {
+  public void f(C.D arg) {
+  }
+}
+
+class B extends J_1 {
+  public void g(C.D arg) {
+  }
+}
+
+class C extends B {
+  public class D {
+  }
+}
diff --git a/test/files/pos/cycle/X_2.scala b/test/files/pos/cycle/X_2.scala
new file mode 100644
index 0000000000..c1840f3b99
--- /dev/null
+++ b/test/files/pos/cycle/X_2.scala
@@ -0,0 +1,3 @@
+import bar.J_1._ //<--- illegal cyclic reference involving
+
+class X
diff --git a/test/pending/pos/t4612.scala b/test/pending/pos/t4612.scala
new file mode 100644
index 0000000000..a93c12ef01
--- /dev/null
+++ b/test/pending/pos/t4612.scala
@@ -0,0 +1,15 @@
+class CyclicReferenceCompilerBug {
+  trait Trait[A] {
+    def foo: A
+  }
+
+  class Class extends Trait[Class] {
+    def foo = new Class
+
+    trait OtherTrait extends Trait[OtherTrait] {
+      self: Class =>
+
+      def foo = new Class
+    }
+  }
+}
diff --git a/test/pending/pos/t4744/Bar.scala b/test/pending/pos/t4744/Bar.scala
new file mode 100644
index 0000000000..1fb6d78973
--- /dev/null
+++ b/test/pending/pos/t4744/Bar.scala
@@ -0,0 +1 @@
+class Bar { val quux = new Foo[java.lang.Integer]() }
diff --git a/test/pending/pos/t4744/Foo.java b/test/pending/pos/t4744/Foo.java
new file mode 100644
index 0000000000..6c764d0470
--- /dev/null
+++ b/test/pending/pos/t4744/Foo.java
@@ -0,0 +1 @@
+public class Foo<T extends Comparable<? super T>> {}
diff --git a/test/pending/pos/t5082.scala b/test/pending/pos/t5082.scala
new file mode 100644
index 0000000000..20a6cfc55f
--- /dev/null
+++ b/test/pending/pos/t5082.scala
@@ -0,0 +1,8 @@
+object Test {
+  sealed trait A
+  case object A1 extends A
+}
+
+trait Something[T]
+
+case class Test() extends Something[Test.A]