Merge pull request #2298 from retronym/ticket/6900-3

SI-6900 Tail call elimination + dependent method type crasher

9 files changed, 222 insertions, 90 deletions

diff --git a/bincompat-backward.whitelist.conf b/bincompat-backward.whitelist.conf
index 4f627780e6..aa06e1d21c 100644
--- a/bincompat-backward.whitelist.conf
+++ b/bincompat-backward.whitelist.conf
@@ -160,6 +160,30 @@ filter {
             problemName=MissingFieldProblem
         },
         {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.existentialTransform$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.existentialTransform"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.packSymbols"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.packSymbols$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.isRawParameter"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.Trees.substituteInfoParamsIntoDefDef"
+            problemName=MissingMethodProblem
+        },
+        {
             matchName="scala.reflect.internal.ClassfileConstants.xxxunusedxxxx"
             problemName=MissingMethodProblem
         }
diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf
index 76e189653b..d0893c5a28 100644
--- a/bincompat-forward.whitelist.conf
+++ b/bincompat-forward.whitelist.conf
@@ -356,6 +356,54 @@ filter {
             problemName=MissingMethodProblem
         },
         {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.existentialTransform$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.existentialTransform"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.packSymbols"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.packSymbols$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.ExistentialsAndSkolems.isRawParameter"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.Trees.substituteInfoParamsIntoDefDef"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.existentialTransform$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.existentialTransform"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.substituteInfoParamsIntoDefDef"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.packSymbols"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.packSymbols$default$3"
+            problemName=MissingMethodProblem
+        },
+        {
+            matchName="scala.reflect.internal.SymbolTable.isRawParameter"
+            problemName=MissingMethodProblem
+        },
+        {
             matchName="scala.reflect.internal.ClassfileConstants.CONSTANT_INVOKEDYNAMIC"
             problemName=MissingMethodProblem
         },
diff --git a/src/compiler/scala/tools/nsc/transform/TailCalls.scala b/src/compiler/scala/tools/nsc/transform/TailCalls.scala
index a767850cba..938499261e 100644
--- a/src/compiler/scala/tools/nsc/transform/TailCalls.scala
+++ b/src/compiler/scala/tools/nsc/transform/TailCalls.scala
@@ -220,7 +220,10 @@ abstract class TailCalls extends Transform {
           debuglog("Rewriting tail recursive call:  " + fun.pos.lineContent.trim)
 
           accessed += ctx.label
-          typedPos(fun.pos)(Apply(Ident(ctx.label), noTailTransform(recv) :: transformArgs))
+          typedPos(fun.pos) {
+            val args = mapWithIndex(transformArgs)((arg, i) => mkAttributedCastHack(arg, ctx.label.info.params(i + 1).tpe))
+            Apply(Ident(ctx.label), noTailTransform(recv) :: args)
+          }
         }
 
         if (!ctx.isEligible)            fail("it is neither private nor final so can be overridden")
@@ -280,7 +283,7 @@ abstract class TailCalls extends Transform {
 
               typedPos(tree.pos)(Block(
                 List(ValDef(newThis, This(currentClass))),
-                LabelDef(newCtx.label, newThis :: vpSyms, newRHS)
+                LabelDef(newCtx.label, newThis :: vpSyms, mkAttributedCastHack(newRHS, newCtx.label.tpe.resultType))
               ))
             }
             else {
@@ -377,6 +380,13 @@ abstract class TailCalls extends Transform {
           super.transform(tree)
       }
     }
+
+    // Workaround for SI-6900. Uncurry installs an InfoTransformer and a tree Transformer.
+    // These leave us with conflicting view on method signatures; the parameter symbols in
+    // the MethodType can be clones of the ones originally found on the parameter ValDef, and
+    // consequently appearing in the typechecked RHS of the method.
+    private def mkAttributedCastHack(tree: Tree, tpe: Type) =
+      gen.mkAttributedCast(tree, tpe)
   }
 
   // collect the LabelDefs (generated by the pattern matcher) in a DefDef that are in tail position
diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
index 66328e23bb..2c191096d6 100644
--- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala
+++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
@@ -818,7 +818,8 @@ abstract class UnCurry extends InfoTransform
      *
      * This transformation erases the dependent method types by:
      *   - Widening the formal parameter type to existentially abstract
-     *     over the prior parameters (using `packSymbols`)
+     *     over the prior parameters (using `packSymbols`). This transformation
+     *     is performed in the the `InfoTransform`er [[scala.reflect.internal.transform.UnCurry]].
      *   - Inserting casts in the method body to cast to the original,
      *     precise type.
      *
@@ -846,15 +847,14 @@ abstract class UnCurry extends InfoTransform
        */
       def erase(dd: DefDef): (List[List[ValDef]], Tree) = {
         import dd.{ vparamss, rhs }
-        val vparamSyms = vparamss flatMap (_ map (_.symbol))
-
         val paramTransforms: List[ParamTransform] =
-          vparamss.flatten.map { p =>
-            val declaredType = p.symbol.info
-            // existentially abstract over value parameters
-            val packedType = typer.packSymbols(vparamSyms, declaredType)
-            if (packedType =:= declaredType) Identity(p)
+          map2(vparamss.flatten, dd.symbol.info.paramss.flatten) { (p, infoParam) =>
+            val packedType = infoParam.info
+            if (packedType =:= p.symbol.info) Identity(p)
             else {
+              // The Uncurry info transformer existentially abstracted over value parameters
+              // from the previous parameter lists.
+
               // Change the type of the param symbol
               p.symbol updateInfo packedType
 
@@ -866,8 +866,8 @@ abstract class UnCurry extends InfoTransform
               // the method body to refer to this, rather than the parameter.
               val tempVal: ValDef = {
                 val tempValName = unit freshTermName (p.name + "$")
-                val newSym = dd.symbol.newTermSymbol(tempValName, p.pos, SYNTHETIC).setInfo(declaredType)
-                atPos(p.pos)(ValDef(newSym, gen.mkAttributedCast(Ident(p.symbol), declaredType)))
+                val newSym = dd.symbol.newTermSymbol(tempValName, p.pos, SYNTHETIC).setInfo(p.symbol.info)
+                atPos(p.pos)(ValDef(newSym, gen.mkAttributedCast(Ident(p.symbol), p.symbol.info)))
               }
               Packed(newParam, tempVal)
             }
@@ -885,13 +885,6 @@ abstract class UnCurry extends InfoTransform
           Block(tempVals, rhsSubstituted)
         }
 
-        // update the type of the method after uncurry.
-        dd.symbol updateInfo {
-          val GenPolyType(tparams, tp) = dd.symbol.info
-          logResult("erased dependent param types for ${dd.symbol.info}") {
-            GenPolyType(tparams, MethodType(allParams map (_.symbol), tp.finalResultType))
-          }
-        }
         (allParams :: Nil, rhs1)
       }
     }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index a98f20a971..34ba8b46f9 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -3767,77 +3767,9 @@ trait Typers extends Modes with Adaptations with Tags {
       } else res
     }
 
-    def isRawParameter(sym: Symbol) = // is it a type parameter leaked by a raw type?
-      sym.isTypeParameter && sym.owner.isJavaDefined
-
-    /** If we map a set of hidden symbols to their existential bounds, we
-     *  have a problem: the bounds may themselves contain references to the
-     *  hidden symbols.  So this recursively calls existentialBound until
-     *  the typeSymbol is not amongst the symbols being hidden.
-     */
-    def existentialBoundsExcludingHidden(hidden: List[Symbol]): Map[Symbol, Type] = {
-      def safeBound(t: Type): Type =
-        if (hidden contains t.typeSymbol) safeBound(t.typeSymbol.existentialBound.bounds.hi) else t
-
-      def hiBound(s: Symbol): Type = safeBound(s.existentialBound.bounds.hi) match {
-        case tp @ RefinedType(parents, decls) =>
-          val parents1 = parents mapConserve safeBound
-          if (parents eq parents1) tp
-          else copyRefinedType(tp, parents1, decls)
-        case tp => tp
-      }
-
-      // Hanging onto lower bound in case anything interesting
-      // happens with it.
-      mapFrom(hidden)(s => s.existentialBound match {
-        case TypeBounds(lo, hi) => TypeBounds(lo, hiBound(s))
-        case _                  => hiBound(s)
-      })
-    }
-
-    /** Given a set `rawSyms` of term- and type-symbols, and a type
-     *  `tp`, produce a set of fresh type parameters and a type so that
-     *  it can be abstracted to an existential type. Every type symbol
-     *  `T` in `rawSyms` is mapped to a clone. Every term symbol `x` of
-     *  type `T` in `rawSyms` is given an associated type symbol of the
-     *  following form:
-     *
-     *    type x.type <: T with Singleton
-     *
-     *  The name of the type parameter is `x.type`, to produce nice
-     *  diagnostics. The Singleton parent ensures that the type
-     *  parameter is still seen as a stable type. Type symbols in
-     *  rawSyms are fully replaced by the new symbols. Term symbols are
-     *  also replaced, except for term symbols of an Ident tree, where
-     *  only the type of the Ident is changed.
-     */
-    protected def existentialTransform[T](rawSyms: List[Symbol], tp: Type)(creator: (List[Symbol], Type) => T): T = {
-      val allBounds = existentialBoundsExcludingHidden(rawSyms)
-      val typeParams: List[Symbol] = rawSyms map { sym =>
-        val name = sym.name match {
-          case x: TypeName  => x
-          case x            => tpnme.singletonName(x)
-        }
-        val bound      = allBounds(sym)
-        val sowner     = if (isRawParameter(sym)) context.owner else sym.owner
-        val quantified = sowner.newExistential(name, sym.pos)
-
-        quantified setInfo bound.cloneInfo(quantified)
-      }
-      // Higher-kinded existentials are not yet supported, but this is
-      // tpeHK for when they are: "if a type constructor is expected/allowed,
-      // tpeHK must be called instead of tpe."
-      val typeParamTypes = typeParams map (_.tpeHK)
-      def doSubst(info: Type) = info.subst(rawSyms, typeParamTypes)
-
-      creator(typeParams map (_ modifyInfo doSubst), doSubst(tp))
-    }
-
     /** Compute an existential type from raw hidden symbols `syms` and type `tp`
      */
-    def packSymbols(hidden: List[Symbol], tp: Type): Type =
-      if (hidden.isEmpty) tp
-      else existentialTransform(hidden, tp)(existentialAbstraction)
+    def packSymbols(hidden: List[Symbol], tp: Type): Type = global.packSymbols(hidden, tp, Some(context0.owner))
 
     def isReferencedFrom(ctx: Context, sym: Symbol): Boolean =
       ctx.owner.isTerm &&
diff --git a/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala b/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala
index 8b24678fd6..3bcb793926 100644
--- a/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala
+++ b/src/reflect/scala/reflect/internal/ExistentialsAndSkolems.scala
@@ -32,4 +32,81 @@ trait ExistentialsAndSkolems {
     }
     (new Deskolemizer).typeSkolems
   }
+
+  def isRawParameter(sym: Symbol) = // is it a type parameter leaked by a raw type?
+    sym.isTypeParameter && sym.owner.isJavaDefined
+
+  /** If we map a set of hidden symbols to their existential bounds, we
+   *  have a problem: the bounds may themselves contain references to the
+   *  hidden symbols.  So this recursively calls existentialBound until
+   *  the typeSymbol is not amongst the symbols being hidden.
+   */
+  private def existentialBoundsExcludingHidden(hidden: List[Symbol]): Map[Symbol, Type] = {
+    def safeBound(t: Type): Type =
+      if (hidden contains t.typeSymbol) safeBound(t.typeSymbol.existentialBound.bounds.hi) else t
+
+    def hiBound(s: Symbol): Type = safeBound(s.existentialBound.bounds.hi) match {
+      case tp @ RefinedType(parents, decls) =>
+        val parents1 = parents mapConserve safeBound
+        if (parents eq parents1) tp
+        else copyRefinedType(tp, parents1, decls)
+      case tp => tp
+    }
+
+    // Hanging onto lower bound in case anything interesting
+    // happens with it.
+    mapFrom(hidden)(s => s.existentialBound match {
+      case TypeBounds(lo, hi) => TypeBounds(lo, hiBound(s))
+      case _                  => hiBound(s)
+    })
+  }
+
+  /** Given a set `rawSyms` of term- and type-symbols, and a type
+   *  `tp`, produce a set of fresh type parameters and a type so that
+   *  it can be abstracted to an existential type. Every type symbol
+   *  `T` in `rawSyms` is mapped to a clone. Every term symbol `x` of
+   *  type `T` in `rawSyms` is given an associated type symbol of the
+   *  following form:
+   *
+   *    type x.type <: T with Singleton
+   *
+   *  The name of the type parameter is `x.type`, to produce nice
+   *  diagnostics. The Singleton parent ensures that the type
+   *  parameter is still seen as a stable type. Type symbols in
+   *  rawSyms are fully replaced by the new symbols. Term symbols are
+   *  also replaced, except for term symbols of an Ident tree, where
+   *  only the type of the Ident is changed.
+   */
+  final def existentialTransform[T](rawSyms: List[Symbol], tp: Type, rawOwner: Option[Symbol] = None)(creator: (List[Symbol], Type) => T): T = {
+    val allBounds = existentialBoundsExcludingHidden(rawSyms)
+    val typeParams: List[Symbol] = rawSyms map { sym =>
+      val name = sym.name match {
+        case x: TypeName  => x
+        case x            => tpnme.singletonName(x)
+      }
+      def rawOwner0  = rawOwner.getOrElse(abort(s"no owner provided for existential transform over raw parameter: $sym"))
+      val bound      = allBounds(sym)
+      val sowner     = if (isRawParameter(sym)) rawOwner0 else sym.owner
+      val quantified = sowner.newExistential(name, sym.pos)
+
+      quantified setInfo bound.cloneInfo(quantified)
+    }
+    // Higher-kinded existentials are not yet supported, but this is
+    // tpeHK for when they are: "if a type constructor is expected/allowed,
+    // tpeHK must be called instead of tpe."
+    val typeParamTypes = typeParams map (_.tpeHK)
+    def doSubst(info: Type) = info.subst(rawSyms, typeParamTypes)
+
+    creator(typeParams map (_ modifyInfo doSubst), doSubst(tp))
+  }
+
+  /**
+   * Compute an existential type from hidden symbols `hidden` and type `tp`.
+   * @param hidden   The symbols that will be existentially abstracted
+   * @param hidden   The original type
+   * @param rawOwner The owner for Java raw types.
+   */
+  final def packSymbols(hidden: List[Symbol], tp: Type, rawOwner: Option[Symbol] = None): Type =
+    if (hidden.isEmpty) tp
+    else existentialTransform(hidden, tp, rawOwner)(existentialAbstraction)
 }
diff --git a/src/reflect/scala/reflect/internal/Trees.scala b/src/reflect/scala/reflect/internal/Trees.scala
index 754adcb80d..2585b541ed 100644
--- a/src/reflect/scala/reflect/internal/Trees.scala
+++ b/src/reflect/scala/reflect/internal/Trees.scala
@@ -1434,6 +1434,11 @@ trait Trees extends api.Trees { self: SymbolTable =>
   /** Substitute symbols in `from` with symbols in `to`. Returns a new
    *  tree using the new symbols and whose Ident and Select nodes are
    *  name-consistent with the new symbols.
+   *
+   *  Note: This is currently a destructive operation on the original Tree.
+   *  Trees currently assigned a symbol in `from` will be assigned the new symbols
+   *  without copying, and trees that define symbols with an `info` that refer
+   *  a symbol in `from` will have a new type assigned.
    */
   class TreeSymSubstituter(from: List[Symbol], to: List[Symbol]) extends Transformer {
     val symSubst = new SubstSymMap(from, to)
diff --git a/src/reflect/scala/reflect/internal/transform/UnCurry.scala b/src/reflect/scala/reflect/internal/transform/UnCurry.scala
index 6dc6a0f7b8..00c7c3de9a 100644
--- a/src/reflect/scala/reflect/internal/transform/UnCurry.scala
+++ b/src/reflect/scala/reflect/internal/transform/UnCurry.scala
@@ -17,7 +17,14 @@ trait UnCurry {
       val tp = expandAlias(tp0)
       tp match {
         case MethodType(params, MethodType(params1, restpe)) =>
-          apply(MethodType(params ::: params1, restpe))
+          // This transformation is described in UnCurryTransformer.dependentParamTypeErasure
+          val packSymbolsMap = new TypeMap {
+            // Wrapping in a TypeMap to reuse the code that opts for a fast path if the function is an identity.
+            def apply(tp: Type): Type = packSymbols(params, tp)
+          }
+          val existentiallyAbstractedParam1s = packSymbolsMap.mapOver(params1)
+          val substitutedResult = restpe.substSym(params1, existentiallyAbstractedParam1s)
+          apply(MethodType(params ::: existentiallyAbstractedParam1s, substitutedResult))
         case MethodType(params, ExistentialType(tparams, restpe @ MethodType(_, _))) =>
           abort("unexpected curried method types with intervening existential")
         case MethodType(h :: t, restpe) if h.isImplicit =>
@@ -60,4 +67,4 @@ trait UnCurry {
    */
   def transformInfo(sym: Symbol, tp: Type): Type =
     if (sym.isType) uncurryType(tp) else uncurry(tp)
-}
\ No newline at end of file
+}
diff --git a/test/files/run/t6900.scala b/test/files/run/t6900.scala
new file mode 100644
index 0000000000..a29d388129
--- /dev/null
+++ b/test/files/run/t6900.scala
@@ -0,0 +1,36 @@
+import annotation.tailrec
+
+trait Universe {
+  type T <: AnyRef
+}
+
+final class Bug {
+  var i = 1
+  def stop() = { i -= 1; i < 0 }
+  // the alias bypasses the fast path in erasures InfoTransformer
+  // predicated on `TypeMap.noChangeToSymbols`
+  type Alias = Any
+
+  @tailrec
+  // So we get two symbols for `universe`, the original on the ValDef
+  // and a clone in the MethodType of `f`.
+  def f(universe: Universe, l: Alias): universe.T = {
+    if (stop()) null.asInstanceOf[universe.T] else f(universe, null)
+  }
+
+  @tailrec
+  def g(universe: Universe)(l: Alias): universe.T = {
+    if (stop()) null.asInstanceOf[universe.T] else g(universe)(l)
+  }
+
+  @tailrec
+  def h(universe: Universe)(l: List[universe.T]): List[universe.T] = {
+    if (stop()) Nil else h(universe)(l)
+  }
+}
+
+object Test extends App {
+  assert(new Bug().f(null, null) == null)
+  assert(new Bug().g(null)(null) == null)
+  assert(new Bug().h(null)(null) == Nil)
+}
\ No newline at end of file