From 04c38829b6fdb03ab62ee20ebff6a56c519bb358 Mon Sep 17 00:00:00 2001
From: Adriaan Moors <adriaan.moors@epfl.ch>
Date: Tue, 10 Aug 2010 21:06:00 +0000
Subject: closes #3676: cycle detection logic in BaseType...

closes #3676: cycle detection logic in BaseTypeSeq's should not
overwrite elements in the BTS for cycle detection as these markers may
be witnessed by callbacks in mergePrefixAndArgs

now using a mutable bitset to keep track of which computations are pending -- benchmarked for speed, memory consumption not checked

review by odersky
---
 .../scala/tools/nsc/symtab/BaseTypeSeqs.scala      | 76 ++++++++++------------
 test/files/pos/t3676.scala                         |  5 ++
 2 files changed, 40 insertions(+), 41 deletions(-)
 create mode 100644 test/files/pos/t3676.scala

diff --git a/src/compiler/scala/tools/nsc/symtab/BaseTypeSeqs.scala b/src/compiler/scala/tools/nsc/symtab/BaseTypeSeqs.scala
index c83138e9bc..c230533765 100644
--- a/src/compiler/scala/tools/nsc/symtab/BaseTypeSeqs.scala
+++ b/src/compiler/scala/tools/nsc/symtab/BaseTypeSeqs.scala
@@ -6,8 +6,7 @@ package scala.tools.nsc
 package symtab
 
 // todo implement in terms of BitSet
-import scala.collection.mutable.ListBuffer
-import scala.collection.immutable.Map
+import scala.collection.mutable.{ListBuffer, BitSet}
 import math.max
 import util.Statistics._
 
@@ -32,45 +31,48 @@ trait BaseTypeSeqs {
 
   class BaseTypeSeq(parents: List[Type], elems: Array[Type]) {
   self =>
-
     incCounter(baseTypeSeqCount)
     incCounter(baseTypeSeqLenTotal, elems.length)
 
     /** The number of types in the sequence */
     def length: Int = elems.length
 
-    var pending: Map[Int, Type] = Map()
+    // #3676 shows why we can't store NoType in elems to mark cycles
+    // (while NoType is in there to indicate a cycle in this BTS, during the execution of
+    //  the mergePrefixAndArgs below, the elems get copied without the pending map,
+    //  so that NoType's are seen instead of the original type --> spurious compile error)
+    val pending = new BitSet(length)
 
     /** The type at i'th position in this sequence; lazy types are returned evaluated. */
-    def apply(i: Int): Type = elems(i) match {
-      case NoType =>
-        pending = Map()
-        elems(i) = AnyClass.tpe
+    def apply(i: Int): Type =
+      if(pending contains i) {
+        pending.clear()
         throw CyclicInheritance
-      case rtp @ RefinedType(variants, decls) =>
-        // can't assert decls.isEmpty; see t0764
-        //if (!decls.isEmpty) assert(false, "computing closure of "+this+":"+this.isInstanceOf[RefinedType]+"/"+closureCache(j))
-        //Console.println("compute closure of "+this+" => glb("+variants+")")
-        pending += (i -> rtp)
-        elems(i) = NoType
-        try {
-          mergePrefixAndArgs(variants, -1, lubDepth(variants)) match {
-            case Some(tp0) =>
-              pending -= i
-              elems(i) = tp0
-              tp0
-            case None =>
-              typeError(
-                "no common type instance of base types "+(variants mkString ", and ")+" exists.")
-          }
-        } catch {
-          case CyclicInheritance =>
-            typeError(
-              "computing the common type instance of base types "+(variants mkString ", and ")+" leads to a cycle.")
+      } else
+        elems(i) match {
+          case rtp @ RefinedType(variants, decls) =>
+            // can't assert decls.isEmpty; see t0764
+            //if (!decls.isEmpty) assert(false, "computing closure of "+this+":"+this.isInstanceOf[RefinedType]+"/"+closureCache(j))
+            //Console.println("compute closure of "+this+" => glb("+variants+")")
+            pending += i
+            try {
+              mergePrefixAndArgs(variants, -1, lubDepth(variants)) match {
+                case Some(tp0) =>
+                  pending(i) = false
+                  elems(i) = tp0
+                  tp0
+                case None =>
+                  typeError(
+                    "no common type instance of base types "+(variants mkString ", and ")+" exists.")
+              }
+            } catch {
+              case CyclicInheritance =>
+                typeError(
+                  "computing the common type instance of base types "+(variants mkString ", and ")+" leads to a cycle.")
+            }
+          case tp =>
+            tp
         }
-      case tp =>
-        tp
-    }
 
     def rawElem(i: Int) = elems(i)
 
@@ -78,17 +80,9 @@ trait BaseTypeSeqs {
      *  no evaluation needed.
      */
     def typeSymbol(i: Int): Symbol = {
-      def tsym(tp: Type) = tp match {
-        case RefinedType(v :: vs, _) => v.typeSymbol
-        case _ => tp.typeSymbol
-      }
       elems(i) match {
-        case NoType =>
-          pending get i match {
-            case Some(tp) => tsym(tp)
-            case _ => NoType.typeSymbol
-          }
-        case tp => tsym(tp)
+        case RefinedType(v :: vs, _) => v.typeSymbol
+        case tp => tp.typeSymbol
       }
     }
 
diff --git a/test/files/pos/t3676.scala b/test/files/pos/t3676.scala
new file mode 100644
index 0000000000..60c0ceaec8
--- /dev/null
+++ b/test/files/pos/t3676.scala
@@ -0,0 +1,5 @@
+trait SeqLike[+Repr]
+trait Seq extends SeqLike[Seq]
+
+trait MySeq extends Seq with SeqLike[MySub]
+trait MySub extends MySeq
-- 
cgit v1.2.3