made subtyping decidable.

8 files changed, 190 insertions, 23 deletions

diff --git a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
index 557f4376a0..fd0c5269bb 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/Parsers.scala
@@ -225,7 +225,7 @@ trait Parsers requires SyntaxAnalyzer {
     def isExprIntro: boolean = isExprIntroToken(in.token)
 
     def isTypeIntroToken(token: int): boolean = token match {
-      case IDENTIFIER | BACKQUOTED_IDENT | THIS | SUPER | USCORE | LPAREN => true
+      case IDENTIFIER | BACKQUOTED_IDENT | THIS | SUPER | USCORE | LPAREN | AT => true
       case _ => false
     }
 
@@ -1619,8 +1619,9 @@ trait Parsers requires SyntaxAnalyzer {
             mods = mods | Flags.CONTRAVARIANT
           }
         }
+        val pos = in.currentPos
         val pname = ident()
-        val param = atPos(in.currentPos) { typeBounds(mods, pname) }
+        val param = atPos(pos) { typeBounds(mods, pname) }
         if (in.token == VIEWBOUND && (implicitViewBuf ne null))
           implicitViewBuf += atPos(in.skipToken()) {
             makeFunctionTypeTree(List(Ident(pname.toTypeName)), typ())
diff --git a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
index cf6faf7e41..4ee8350cdb 100644
--- a/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
+++ b/src/compiler/scala/tools/nsc/ast/parser/TreeBuilder.scala
@@ -367,9 +367,6 @@ abstract class TreeBuilder {
   private def makeUnsealed(expr: Tree): Tree =
     Attributed(New(scalaDot(definitions.UnsealedClass.name), List(List())), List(), expr)
 
-  private def checkAttr(expr: Tree, check: boolean) =
-    if (check) expr else makeUnsealed(expr)
-
   /** Create visitor <x => x match cases> */
   def makeVisitor(cases: List[CaseDef], checkExhaustive: boolean, prefix: String): Tree = {
     val x = freshName(prefix)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index f1825e2b6e..c42157cf94 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -62,14 +62,17 @@ abstract class GenJVM extends SubComponent {
     val stringBufferType = new JObjectType(JAVA_LANG_STRINGBUFFER)
     val toStringType = new JMethodType(JObjectType.JAVA_LANG_STRING, JType.EMPTY_ARRAY)
 
+    def attributeType(name: String) =
+      atPhase(currentRun.typerPhase)(definitions.getClass(name).tpe)
+
     // Scala attributes
-    val SerializableAttr = definitions.SerializableAttr.tpe
-    val SerialVersionUID = definitions.getClass("scala.SerialVersionUID").tpe
-    val CloneableAttr    = definitions.getClass("scala.cloneable").tpe
-    val TransientAtt     = definitions.getClass("scala.transient").tpe
-    val VolatileAttr     = definitions.getClass("scala.volatile").tpe
-    val RemoteAttr       = definitions.getClass("scala.remote").tpe
-    val ThrowsAttr       = definitions.getClass("scala.throws").tpe
+    val SerializableAttr = atPhase(currentRun.typerPhase)(definitions.SerializableAttr.tpe)
+    val SerialVersionUID = attributeType("scala.SerialVersionUID")
+    val CloneableAttr    = attributeType("scala.cloneable")
+    val TransientAtt     = attributeType("scala.transient")
+    val VolatileAttr     = attributeType("scala.volatile")
+    val RemoteAttr       = attributeType("scala.remote")
+    val ThrowsAttr       = attributeType("scala.throws")
 
     val CloneableClass   =
       if (forCLDC) null else definitions.getClass("java.lang.Cloneable")
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index 7ee6d667e7..348f9c2f77 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -51,6 +51,7 @@ trait Types requires SymbolTable {
   private var globalVariance = 1//only necessary if healTypes = true?
   private final val healTypes = false
   private final val LubGlbMargin = 0
+  private final val LogPendingSubTypesThreshold = 50
 
   val emptyTypeArray = new Array[Type](0)
 
@@ -818,11 +819,10 @@ trait Types requires SymbolTable {
     // override def isNullable: boolean =
     // parents forall (p => p.isNullable && !p.symbol.isAbstractType);
 
-    override def toString(): String = (
+    override def toString(): String =
       parents.mkString("", " with ", "") +
       (if (settings.debug.value || parents.isEmpty || (decls.elems ne null))
         decls.mkString("{", "; ", "}") else "")
-    );
   }
 
   /** A class representing intersection types with refinements of the form
@@ -838,7 +838,129 @@ trait Types requires SymbolTable {
   case class ClassInfoType(
     override val parents: List[Type],
     override val decls: Scope,
-    override val symbol: Symbol) extends CompoundType {
+    override val symbol: Symbol) extends CompoundType
+  {
+    /** refs indices */
+    private final val NonExpansive = 0
+    private final val Expansive = 1
+
+    /** initialization states */
+    private final val UnInitialized = 0
+    private final val Initializing = 1
+    private final val Initialized = 2
+
+    private type RefMap = Map[Symbol, collection.immutable.Set[Symbol]]
+
+    /** All type parameters reachable from given type parameter
+     *  by a path which contains at least one expansive reference.
+     *  @See Kennedy, Pierce: On Decidability of Nominal Subtyping with Variance
+     */
+    def expansiveRefs(tparam: Symbol) = {
+      if (state == UnInitialized) {
+        computeRefs()
+        while (state != Initialized) propagate()
+      }
+      getRefs(Expansive, tparam)
+    }
+
+    /* The rest of this class is auxiliary code for <code>expansiveRefs</code>
+     */
+
+    /** The type parameters which are referenced type parameters of this class.
+     *  Two entries: refs(0): Non-expansive references
+     *               refs(1): Expansive references
+     */
+    private var refs: Array[RefMap] = _
+
+    /** The initialization state of the class: UnInialized --> Initializing --> Initialized
+     */
+    private var state = UnInitialized
+
+    /** Get references for given type parameter
+     *  @param  which in {NonExpansive, Expansive}
+     *  @param  from  The type parameter from which references originate.
+     */
+    private def getRefs(which: int, from: Symbol): Set[Symbol] = refs(which) get from match {
+      case Some(set) => set
+      case None => Set()
+    }
+
+    /** Augment existing refs map with reference <pre>from -> to</pre>
+     *  @param  which <- {NonExpansive, Expansive}
+     */
+    private def addRef(which: int, from: Symbol, to: Symbol) {
+      refs(which) = refs(which) + (from -> (getRefs(which, from) + to))
+    }
+
+    /** Augment existing refs map with references <pre>from -> sym</pre>, for
+     *  all elements <pre>sym</pre> of set <code>to</code>.
+     *  @param  which <- {NonExpansive, Expansive}
+     */
+    private def addRefs(which: int, from: Symbol, to: Set[Symbol]) {
+      refs(which) = refs(which) + (from -> (getRefs(which, from) ++ to))
+    }
+
+    /** The ClassInfoType which belongs to the class containing given type parameter
+     */
+    private def classInfo(tparam: Symbol): ClassInfoType =
+      tparam.owner.info.resultType match {
+        case ci: ClassInfoType => ci
+        case _ => classInfo(ObjectClass) // something's wrong; fall back to safe value
+                                         // (this can happen only for erroneous programs).
+      }
+
+    /** Compute initial (one-step) references and set state to <code>Initializing</code>.
+     */
+    private def computeRefs() {
+      refs = Array(Map(), Map())
+      for (val tparam <- symbol.typeParams) {
+        val enterRefs = new TypeMap {
+          def apply(tp: Type): Type = {
+            tp match {
+              case TypeRef(_, sym, args) =>
+                for (val {tparam1, arg} <- sym.info.typeParams zip args)
+                  if (arg contains tparam) {
+                    addRef(NonExpansive, tparam, tparam1)
+                    if (arg.symbol != tparam) addRef(Expansive, tparam, tparam1)
+                  }
+              case _ =>
+            }
+            mapOver(tp)
+          }
+        }
+        for (val p <- parents) enterRefs(p)
+      }
+      state = Initializing
+    }
+
+    /** Propagate to form transitive closure.
+     *  Set state to Initialized if no change resulted from propagation.
+     *  @return   true iff there as a change in last iteration
+     */
+    private def propagate(): boolean = {
+      if (state == UnInitialized) computeRefs()
+      //Console.println("Propagate "+symbol+", initial expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
+      val lastRefs = Array(refs(0), refs(1))
+      state = Initialized
+      var change = false
+      for (val {from, targets} <- refs(NonExpansive).elements)
+        for (val target <- targets) {
+          var thatInfo = classInfo(target)
+          if (thatInfo.state != Initialized)
+            change = change | thatInfo.propagate()
+          addRefs(NonExpansive, from, thatInfo.getRefs(NonExpansive, target))
+          addRefs(Expansive, from, thatInfo.getRefs(Expansive, target))
+        }
+      for (val {from, targets} <- refs(Expansive).elements)
+        for (val target <- targets) {
+          var thatInfo = classInfo(target)
+          addRefs(Expansive, from, thatInfo.getRefs(NonExpansive, target))
+        }
+      change = change || refs(0) != lastRefs(0) || refs(1) != lastRefs(1)
+      if (change) state = Initializing
+      //else Console.println("Propagate "+symbol+", final expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
+      change
+    }
 
     // override def isNullable: boolean =
     // symbol == AnyClass ||
@@ -1818,6 +1940,17 @@ trait Types requires SymbolTable {
     }
   }
 
+  class SubTypePair(val tp1: Type, val tp2: Type) {
+    override def hashCode = tp1.hashCode * 41 + tp2.hashCode
+    override def equals(other: Any) = other match {
+      case stp: SubTypePair =>
+        (tp1 =:= stp.tp1) && (tp2 =:= stp.tp2)
+      case _ =>
+        false
+    }
+    override def toString = tp1+" <:<? "+tp2
+  }
+
 // Helper Methods  -------------------------------------------------------------
 
   import Math.max
@@ -1965,12 +2098,24 @@ trait Types requires SymbolTable {
     tps1.length == tps2.length &&
     List.forall2(tps1, tps2)((tp1, tp2) => tp1 =:= tp2)
 
-  private var stc = 0
+  var stc: int = 0
+  private var pendingSubTypes = new collection.mutable.HashSet[SubTypePair]
+
   def isSubType(tp1: Type, tp2: Type): boolean =
     try {
       stc = stc + 1
-      if (stc == 100) throw new Error("recursive <:<")
-      isSubType0(tp1, tp2)
+      if (stc >= LogPendingSubTypesThreshold) {
+        val p = new SubTypePair(tp1, tp2)
+        if (pendingSubTypes contains p)
+          false
+        else
+          try {
+            pendingSubTypes += p
+            isSubType0(tp1, tp2)
+          } finally {
+            pendingSubTypes -= p
+          }
+      } else isSubType0(tp1, tp2)
     } finally {
       stc = stc - 1
     }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index dff9b8d6c2..18c9adda86 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -809,6 +809,25 @@ trait Typers requires Analyzer {
         for (val p <- parents) validateParentClass(p, parents.head.tpe.symbol)
     }
 
+    def checkFinitary(classinfo: ClassInfoType) {
+      val clazz = classinfo.symbol
+      for (val tparam <- clazz.typeParams) {
+        if (classinfo.expansiveRefs(tparam) contains tparam) {
+          error(tparam.pos, "class graph is not finitary because type parameter "+tparam.name+" is expansively recursive")
+          val newinfo = ClassInfoType(
+            classinfo.parents map (.subst(List(tparam), List(AnyRefClass.tpe))),
+            classinfo.decls,
+            clazz)
+          clazz.setInfo {
+            clazz.info match {
+              case PolyType(tparams, _) => PolyType(tparams, newinfo)
+              case _ => newinfo
+            }
+          }
+        }
+      }
+    }
+
     /**
      *  @param cdef ...
      *  @return     ...
@@ -914,6 +933,8 @@ trait Typers requires Analyzer {
       // the following is necessary for templates generated later
       enterSyms(context.outer.make(templ, clazz, clazz.info.decls), templ.body)
       validateParentClasses(parents1, selfType)
+      if (!phase.erasedTypes)
+        checkFinitary(clazz.info.resultType.asInstanceOf[ClassInfoType])
       val body =
         if (phase.id <= currentRun.typerPhase.id && !reporter.hasErrors)
           templ.body flatMap addGetterSetter
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index 65fd32379f..5cc326c031 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -192,7 +192,7 @@ trait Map[A, +B] extends collection.Map[A, B] {
     var res: Map[A, B1] = this
     while (iter.hasNext) {
       val {key, value} = iter.next
-      res = res.update(key, value);
+      res = res.update(key, value)
     }
     res
   }
diff --git a/test/files/neg/bug692.check b/test/files/neg/bug692.check
index 844b63827b..6eb9f7d8af 100644
--- a/test/files/neg/bug692.check
+++ b/test/files/neg/bug692.check
@@ -10,10 +10,10 @@ bug692.scala:13: error: class Foo takes type parameters
 bug692.scala:13: error: class Foo takes type parameters
   case class BarType[T3 <: Foo](tpeT : RefType[T3]) extends ClassType[Bar[T3],Foo](FooType);
                            ^
-bug692.scala:14: error: class Foo takes type parameters
-  implicit def typeOfBar[T4 <: Foo](implicit elem : RefType[T4]) : RefType[Bar[T4]] = 
-                               ^
 bug692.scala:19: error: class Foo takes type parameters
   class Bar[A <: Foo](implicit tpeA : Type[A]) extends Foo;
                  ^
+bug692.scala:14: error: class Foo takes type parameters
+  implicit def typeOfBar[T4 <: Foo](implicit elem : RefType[T4]) : RefType[Bar[T4]] = 
+                               ^
 6 errors found
diff --git a/test/files/neg/bug798.check b/test/files/neg/bug798.check
index a740f933a2..5859e1e769 100644
--- a/test/files/neg/bug798.check
+++ b/test/files/neg/bug798.check
@@ -1,4 +1,4 @@
 bug798.scala:2: error: cyclic aliasing or subtyping involving type Bracks
 trait Test[Bracks <: Bracks] {
-                  ^
+           ^
 one error found