the essence of tcpoly inference + test cases

fixes to check files and removed nonapplicable test case Tuple2 impl,
but commented out so that we can bootstrap whitespace...

4 files changed, 111 insertions, 97 deletions

diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index cdb3a2eb8e..933c122d6b 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -1963,8 +1963,9 @@ A type's typeSymbol should never be inspected directly.
   // now, pattern-matching returns the most recent constr
   object TypeVar {
     def unapply(tv: TypeVar): Some[(Type, TypeConstraint)] = Some((tv.origin, tv.constr))
-    def apply(origin: Type, constr: TypeConstraint) = new TypeVar(origin, constr)
-    def apply(tparam: Symbol) = new TypeVar(tparam.tpeHK, new TypeConstraint(List(),List()))
+    def apply(origin: Type, constr: TypeConstraint) = new TypeVar(origin, constr, List(), List())
+    def apply(tparam: Symbol) = new TypeVar(tparam.tpeHK, new TypeConstraint(List(),List()), List(), tparam.typeParams)
+    def apply(origin: Type, constr: TypeConstraint, args: List[Type], params: List[Symbol]) = new TypeVar(origin, constr, args, params)
   }
 
   /** A class representing a type variable
@@ -1973,7 +1974,9 @@ A type's typeSymbol should never be inspected directly.
    * A TypeVar whose list of args is non-empty can only be instantiated by a higher-kinded type that can be applied to these args
    * NOTE:
    */
-  class TypeVar(val origin: Type, val constr0: TypeConstraint) extends Type {
+  class TypeVar(val origin: Type, val constr0: TypeConstraint, override val typeArgs: List[Type], override val params: List[Symbol]) extends Type {
+    // params are needed to keep track of variance (see mapOverArgs in SubstMap)
+    assert(typeArgs.isEmpty || typeArgs.length == params.length)
     // var tid = { tidCount += 1; tidCount } //DEBUG
 
     /** The constraint associated with the variable */
@@ -1983,6 +1986,24 @@ A type's typeSymbol should never be inspected directly.
     /** The variable's skolemizatuon level */
     val level = skolemizationLevel
 
+    /**
+     *  two occurrences of a higher-kinded typevar, e.g. ?CC[Int] and ?CC[String], correspond to
+     *  *two instances* of TypeVar that share the *same* TypeConstraint
+     *  constr for ?CC only tracks type constructors anyway, so when ?CC[Int] <:< List[Int] and ?CC[String] <:< Iterable[String]
+     *  ?CC's hibounds contains List and Iterable
+     */
+    def applyArgs(newArgs: List[Type]): TypeVar =
+      if(newArgs.isEmpty) this // SubstMap relies on this (though this check is redundant when called from appliedType...)
+      else TypeVar(origin, constr, newArgs, params) // @M TODO: interaction with undoLog??
+        // newArgs.length may differ from args.length (could've been empty before)
+      // OBSOLETE BEHAVIOUR: imperatively update args to new args
+      // this initialises a TypeVar's arguments to the arguments of the type
+      // example: when making new typevars, you start out with C[A], then you replace C by ?C, which should yield ?C[A], then A by ?A, ?C[?A]
+      // thus, we need to track a TypeVar's arguments, and map over them (see TypeMap::mapOver)
+      // OBSOLETE BECAUSE: can't update imperatively because TypeVars do get applied to different arguments over type (in asSeenFrom) -- see pos/tcpoly_infer_implicit_tuplewrapper.scala
+      // CONSEQUENCE: make new TypeVar's for every application of a TV to args,
+      //   inference may generate several TypeVar's for a single type parameter that must be inferred,
+      //   one of them is in the set of tvars that need to be solved, and they all share the same constr instance
 
 
     def setInst(tp: Type) {
@@ -2024,12 +2045,24 @@ A type's typeSymbol should never be inspected directly.
         else             constr.hibounds = tp :: constr.hibounds
         // println("addedBound: "+(this, tp)) // @MDEBUG
         }
+      def checkArgs(args1: List[Type], args2: List[Type], params: List[Symbol]) =
+        if(isLowerBound) isSubArgs(args1, args2, params)
+        else             isSubArgs(args2, args1, params)
 
       if (constr.instValid) // type var is already set
         checkSubtype(tp, constr.inst)
       else isRelatable(tp) && {
-        addBound(tp)
-        true
+        if(params.isEmpty) { // type var has kind *
+          addBound(tp)
+          true
+        } else // higher-kinded type var with same arity as tp
+          (typeArgs.length == tp.typeArgs.length) && {
+            // register type constructor (the type without its type arguments) as bound
+            addBound(tp.typeConstructor)
+            // check subtyping of higher-order type vars
+            // use variances as defined in the type parameter that we're trying to infer (the result is sanity-checked later)
+            checkArgs(tp.typeArgs, typeArgs, params)
+          }
       }
     }
 
@@ -2050,17 +2083,24 @@ A type's typeSymbol should never be inspected directly.
       }
     }
 
-    override val isHigherKinded = false
+    override val isHigherKinded = typeArgs.isEmpty && !params.isEmpty
 
     override def normalize: Type =
       if  (constr.instValid) constr.inst
-      else super.normalize
+      else if (isHigherKinded) {  // get here when checking higher-order subtyping of the typevar by itself (TODO: check whether this ever happens?)
+        // @M TODO: should not use PolyType, as that's the type of a polymorphic value -- we really want a type *function*
+        PolyType(params, applyArgs(params map (_.typeConstructor)))
+      } else {
+        super.normalize
+      }
 
     override def typeSymbol = origin.typeSymbol
     override def safeToString: String = {
-      def varString = "?"+(if (settings.explaintypes.value) level else "")+origin// +"#"+tid //DEBUG
+      def varString = "?"+(if (settings.explaintypes.value) level else "")+
+                          origin+
+                          (if(typeArgs.isEmpty) "" else (typeArgs map (_.safeToString)).mkString("[ ", ", ", " ]")) // +"#"+tid //DEBUG
       if (constr.inst eq null) "<null " + origin + ">"
-      else if (settings.debug.value) varString+constr.toString
+      else if (settings.debug.value) varString+"(@"+constr.hashCode+")"+constr.toString
       else if (constr.inst eq NoType) varString
       else constr.inst.toString
     }
@@ -2068,7 +2108,7 @@ A type's typeSymbol should never be inspected directly.
     override def isVolatile = origin.isVolatile
     override def kind = "TypeVar"
 
-    def cloneInternal = TypeVar(origin, constr cloneInternal)
+    def cloneInternal = TypeVar(origin, constr cloneInternal, typeArgs, params) // @M TODO: clone args/params?
   }
 
   /** A type carrying some annotations. Created by the typechecker
@@ -2385,7 +2425,7 @@ A type's typeSymbol should never be inspected directly.
       case st: SingletonType => appliedType(st.widen, args) // @M TODO: what to do? see bug1
       case RefinedType(parents, decls) => RefinedType(parents map (appliedType(_, args)), decls) // MO to AM: please check
       case TypeBounds(lo, hi) => TypeBounds(appliedType(lo, args), appliedType(hi, args))
-      case tv@TypeVar(_, _) => tv //@M: for tcpoly inference, this becomes: tv.applyArgs(args)
+      case tv@TypeVar(_, constr) => tv.applyArgs(args)
       case ErrorType => tycon
       case WildcardType => tycon // needed for neg/t0226
       case _ => throw new Error(debugString(tycon))
@@ -2678,7 +2718,7 @@ A type's typeSymbol should never be inspected directly.
         else AntiPolyType(pre1, args1)
       case tv@TypeVar(_, constr) =>
         if (constr.instValid) this(constr.inst)
-        else tv
+        else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params))  //@M !args.isEmpty implies !typeParams.isEmpty
       case NotNullType(tp) =>
         val tp1 = this(tp)
         if (tp1 eq tp) tp
@@ -4079,15 +4119,6 @@ A type's typeSymbol should never be inspected directly.
       case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2))
       if !(tp1.isHigherKinded || tp2.isHigherKinded) =>
         //Console.println("isSubType " + tp1 + " " + tp2);//DEBUG
-        def isSubArgs(tps1: List[Type], tps2: List[Type],
-                      tparams: List[Symbol]): Boolean = (
-          tps1.isEmpty && tps2.isEmpty
-          ||
-          !tps1.isEmpty && !tps2.isEmpty &&
-          (tparams.head.isCovariant || (tps2.head <:< tps1.head)) &&
-          (tparams.head.isContravariant || (tps1.head <:< tps2.head)) &&
-          isSubArgs(tps1.tail, tps2.tail, tparams.tail)
-        );
         ((if (sym1 == sym2) phase.erasedTypes || pre1 <:< pre2
           else (sym1.name == sym2.name) && isUnifiable(pre1, pre2)) &&
          (sym2 == AnyClass || isSubArgs(args1, args2, sym1.typeParams)) //@M: Any is kind-polymorphic
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index 637e0e3659..96dad06e0f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -583,7 +583,9 @@ trait Infer {
       List.map2(tparams, targs) {(tparam, targ) =>
         if (targ.typeSymbol == NothingClass && (restpe == WildcardType || (varianceInType(restpe)(tparam) & COVARIANT) == 0)) {
           uninstantiated += tparam
-          tparam.tpe
+          tparam.tpeHK  //@M tparam.tpe was wrong: we only want the type constructor,
+            // not the type constructor applied to dummy arguments
+            // see ticket 474 for an example that crashes if we use .tpe instead of .tpeHK)
         } else if (targ.typeSymbol == RepeatedParamClass) {
           targ.baseType(SeqClass)
         } else if (targ.typeSymbol == JavaRepeatedParamClass) {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 269e9ca938..5726e4be58 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -783,11 +783,12 @@ trait Typers { self: Analyzer =>
         val tparams1 = cloneSymbols(tparams)
         val tree1 = if (tree.isType) tree
                     else TypeApply(tree, tparams1 map (tparam =>
-                      TypeTree(tparam.tpe) setPos tree.pos.focus)) setPos tree.pos
+                      TypeTree(tparam.tpeHK) setPos tree.pos.focus)) setPos tree.pos //@M/tcpolyinfer: changed tparam.tpe to tparam.tpeHK
         context.undetparams = context.undetparams ::: tparams1
         adapt(tree1 setType restpe.substSym(tparams, tparams1), mode, pt, original)
       case mt: ImplicitMethodType if ((mode & (EXPRmode | FUNmode | LHSmode)) == EXPRmode) => // (4.1)
         if (!context.undetparams.isEmpty/* && (mode & POLYmode) == 0 disabled to make implicits in new collection work; we should revisit this. */) { // (9)
+          // println("adapt IMT: "+(context.undetparams, pt)) //@MDEBUG
           context.undetparams = inferExprInstance(
             tree, context.extractUndetparams(), pt, mt.paramTypes exists isManifest)
               // if we are looking for a manifest, instantiate type to Nothing anyway,
diff --git a/src/library/scala/Tuple2.scala b/src/library/scala/Tuple2.scala
index 7edea7db15..db499b3070 100644
--- a/src/library/scala/Tuple2.scala
+++ b/src/library/scala/Tuple2.scala
@@ -13,86 +13,15 @@
 package scala
 
 import annotation.unchecked.uncheckedVariance
-
-object Tuple2 {
-
-  import collection.generic._
-/* !!! todo: enable
-  class IterableOps[CC[+B] <: Iterable[B] with IterableTemplate[CC, B @uncheckedVariance], A1, A2](tuple: (CC[A1], Iterable[A2])) {
-    def zip: CC[(A1, A2)] = {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      val b = (tuple._1: IterableTemplate[CC, A1]).newBuilder[(A1, A2)]
-        // : needed because otherwise it picks Iterable's builder.
-      while (elems1.hasNext && elems2.hasNext)
-        b += ((elems1.next, elems2.next))
-      b.result
-    }
-    def map[B](f: (A1, A2) => B): CC[B] = {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      val b = (tuple._1: IterableTemplate[CC, A1]).newBuilder[B]
-      while (elems1.hasNext && elems2.hasNext)
-        b += f(elems1.next, elems2.next)
-      b.result
-    }
-    def flatMap[B](f: (A1, A2) => CC[B]): CC[B] = {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      val b = (tuple._1: IterableTemplate[CC, A1]).newBuilder[B]
-      while (elems1.hasNext && elems2.hasNext)
-        b ++= f(elems1.next, elems2.next)
-      b.result
-    }
-    def foreach[U](f: (A1, A2) => U) {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      while (elems1.hasNext && elems2.hasNext)
-        f(elems1.next, elems2.next)
-    }
-    def forall(p: (A1, A2) => Boolean): Boolean = {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      while (elems1.hasNext && elems2.hasNext)
-        if (!p(elems1.next, elems2.next)) return false
-      true
-    }
-    def exists(p: (A1, A2) => Boolean): Boolean = {
-      val elems1 = tuple._1.iterator
-      val elems2 = tuple._2.iterator
-      while (elems1.hasNext && elems2.hasNext)
-        if (p(elems1.next, elems2.next)) return true
-      false
-    }
-  }
-  implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2](tuple: (CC[A1], Iterable[A2])) =
-    new IterableOps[CC, A1, A2](tuple)
+import scala.collection.Traversable
+import scala.collection.generic.GenericTraversableTemplate
+import scala.collection.mutable.Builder
 
 
-/* A more general version which will probably not work.
-  implicit def tupleOfIterableWrapper[CC[+B] <: Iterable[B] with IterableTemplate[CC, B], A1, A2, B1 <: CC[A1]](tuple: B1, Iterable[A2]) =
-    new IterableOps[CC, A1, A2](tuple)
-*/
-
-  // Adriaan: If you drop the type parameters it will infer the wrong types.
-  tupleOfIterableWrapper[collection.immutable.List, Int, Int]((collection.immutable.Nil, collection.immutable.Nil)) forall (_ + _ < 10)
-*/
-}
-
 /** Tuple2 is the canonical representation of a @see Product2
  *
  */
 case class Tuple2[+T1, +T2](_1:T1, _2:T2) extends Product2[T1, T2]  {
-/*
-  def map[CC[X] <: Traversable[X], A1, A2, B](implicit fst: T1 => CC[A1], snd: T2 => Traversable[A2]) = (f: (A1, A2) => B) => {
-    val b = fst(_1).genericBuilder[B]
-    val it1 = _1.iterator
-    val it2 = _2.iterator
-    while (it1.hasNext && it2.hasNext)
-      b += f(it1.next, it2.next)
-    b.result
-  }
-*/
   override def toString() = {
      val sb = new StringBuilder
      sb.append('(').append(_1).append(',').append(_2).append(')')
@@ -102,4 +31,55 @@ case class Tuple2[+T1, +T2](_1:T1, _2:T2) extends Product2[T1, T2]  {
   /** Swap the elements of the tuple */
   def swap: Tuple2[T2,T1] = Tuple2(_2, _1)
 
+/*
+  type Traverserable[CC[X] <: Traversable[X], X] = GenericTraversableTemplate[X, CC] with Iterable[X]
+
+  // TODO: benchmark factored version vs inlining forall2 everywhere (specialisation?)
+  // factor further? (use fold2)
+  // must use <:< instead of =>, otherwise bogus any2stringadd conversion is also eligible (in case of type errors)
+
+
+  def forall2[CC[X] <: Traverserable[CC, X], A1, A2](f: (A1, A2) => Boolean)(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): Boolean = {
+    val it1 = _1.iterator
+    val it2 = _2.iterator
+    var res = true
+    while (res && it1.hasNext && it2.hasNext)
+      res = f(it1.next, it2.next)
+    res
+  }
+
+  def exists2[CC[X] <: Traverserable[CC, X], A1, A2](f: (A1, A2) => Boolean)(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): Boolean = {
+    val it1 = _1.iterator
+    val it2 = _2.iterator
+    var res = false
+    while (!res && it1.hasNext && it2.hasNext)
+      res = f(it1.next, it2.next)
+    res
+  }
+
+  def foreach2[CC[X] <: Traverserable[CC, X], A1, A2, U](f: (A1, A2) => U)(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): Unit
+    = forall2[CC, A1, A2]{(x, y) => f(x, y); true} // XXX: remove type args and fix crash in type infer
+
+  def build2[CC[X] <: Traverserable[CC, X], A1, A2, B](f: Builder[B, CC[B]] => (A1, A2) => Unit)(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): CC[B] = {
+    val b = _1.genericBuilder[B]
+      foreach2[CC, A1, A2, Unit](f(b)) // XXX: remove type args and fix crash in type infer
+    b.result
+  }
+
+  def zip2[CC[X] <: Traverserable[CC, X], A1, A2](implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): CC[(A1, A2)]
+    = build2[CC, A1, A2, (A1, A2)]{b => (x, y) =>  // XXX: remove type args and fix crash in type infer
+        b += Tuple2(x, y)
+      }
+
+  def map2[CC[X] <: Traverserable[CC, X], A1, A2, B](f: (A1, A2) => B)(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): CC[B]
+    = build2[CC, A1, A2, B]{b => (x, y) =>  // XXX: remove type args and fix crash in type infer
+        b += f(x, y)
+      }
+
+  def flatMap2[CC[X] <: Traverserable[CC, X], A1, A2, B](f: (A1, A2) => CC[B])(implicit fst: T1 <:< CC[A1], snd: T2 <:< Traverserable[Iterable, A2]/*CC[A2] does not work*/): CC[B]
+    = build2[CC, A1, A2, B]{b => (x, y) =>  // XXX: remove type args and fix crash in type infer
+        b ++= f(x, y)
+      }
+*/
+
 }