SI-5189 fixed: safe type infer for constr pattern

several fixes to the standard library due to
 - the safer type checker this fix gives us (thus, some casts had to be inserted)
 - SI-5548
 - type inference gets a bit more complicated, it needs help (chainl1 in combinator.Parsers)

To deal with the type slack between actual (run-time) types and statically known
types, for each abstract type T, reflect its variance as a skolem that is
upper-bounded by T (covariant position), or lower-bounded by T (contravariant).

Consider the following example:

 class AbsWrapperCov[+A]
 case class Wrapper[B](x: Wrapped[B]) extends AbsWrapperCov[B]

 def unwrap[T](x: AbsWrapperCov[T]): Wrapped[T] = x match {
   case Wrapper(wrapped) =>
     // Wrapper's type parameter must not be assumed to be equal to T,
     // it's *upper-bounded* by it
     wrapped // : Wrapped[_ <: T]
 }

this  method should  type check  if and  only if  Wrapped is  covariant in  its type
parameter

before inferring Wrapper's type parameter B from x's type AbsWrapperCov[T], we must
take into account that x's actual type is:
AbsWrapperCov[Tactual] forSome {type Tactual <: T}
since AbsWrapperCov is covariant in A -- in other words, we must not assume we know
T exactly, all we know is its upper bound

since method application is the only way to generate this slack between run-time and
compile-time types (TODO: right!?), we can simply replace skolems that represent
method type parameters as seen from the method's body by other skolems that are
(upper/lower)-bounded by that type-parameter skolem (depending on the variance
position of the skolem in the statically assumed type of the scrutinee, pt)

this type slack is introduced by adaptConstrPattern: before it calls
inferConstructorInstance, it creates a new context that holds the new existential
skolems

the context created by adaptConstrPattern must not be a CaseDef, since that
confuses instantiateTypeVar and the whole pushTypeBounds/restoreTypeBounds dance
(CaseDef contexts remember the bounds of the type params that we clobbered
during GADT typing)

typedCase deskolemizes the existential skolems back to the method skolems,
since they don't serve any further purpose (except confusing the old pattern
matcher)

typedCase is now better at finding that context (using nextEnclosing)

4 files changed, 92 insertions, 12 deletions

diff --git a/src/compiler/scala/reflect/internal/Symbols.scala b/src/compiler/scala/reflect/internal/Symbols.scala
index 62b0206c28..446dbad03f 100644
--- a/src/compiler/scala/reflect/internal/Symbols.scala
+++ b/src/compiler/scala/reflect/internal/Symbols.scala
@@ -269,9 +269,9 @@ trait Symbols extends api.Symbols { self: SymbolTable =>
     /** Create a new existential type skolem with this symbol its owner,
      *  based on the given symbol and origin.
      */
-    def newExistentialSkolem(basis: Symbol, origin: AnyRef): TypeSkolem = {
-      val skolem = newTypeSkolemSymbol(basis.name.toTypeName, origin, basis.pos, (basis.flags | EXISTENTIAL) & ~PARAM)
-      skolem setInfo (basis.info cloneInfo skolem)
+    def newExistentialSkolem(basis: Symbol, origin: AnyRef, name: TypeName = null, info: Type = null): TypeSkolem = {
+      val skolem = newTypeSkolemSymbol(if (name eq null) basis.name.toTypeName else name, origin, basis.pos, (basis.flags | EXISTENTIAL) & ~PARAM)
+      skolem setInfo (if (info eq null) basis.info cloneInfo skolem else info)
     }
 
     final def newExistential(name: TypeName, pos: Position = NoPosition, newFlags: Long = 0L): Symbol =
diff --git a/src/compiler/scala/tools/nsc/io/Pickler.scala b/src/compiler/scala/tools/nsc/io/Pickler.scala
index 5bb8bdda35..80b6e086da 100644
--- a/src/compiler/scala/tools/nsc/io/Pickler.scala
+++ b/src/compiler/scala/tools/nsc/io/Pickler.scala
@@ -165,7 +165,7 @@ object Pickler {
   def pkl[T: Pickler] = implicitly[Pickler[T]]
 
   /** A class represenenting `~`-pairs */
-  case class ~[S, T](fst: S, snd: T)
+  case class ~[+S, +T](fst: S, snd: T)
 
   /** A wrapper class to be able to use `~` s an infix method */
   class TildeDecorator[S](x: S) {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
index 7b72169ba9..50c45a2dc0 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala
@@ -1090,7 +1090,15 @@ trait Infer {
           inferFor(pt.instantiateTypeParams(ptparams, ptparams map (x => WildcardType))) flatMap { targs =>
             val ctorTpInst = tree.tpe.instantiateTypeParams(undetparams, targs)
             val resTpInst  = skipImplicit(ctorTpInst.finalResultType)
-            val ptvars     = ptparams map freshVar
+            val ptvars     =
+              ptparams map {
+                // since instantiateTypeVar wants to modify the skolem that corresponds to the method's type parameter,
+                // and it uses the TypeVar's origin to locate it, deskolemize the existential skolem to the method tparam skolem
+                // (the existential skolem was created by adaptConstrPattern to introduce the type slack necessary to soundly deal with variant type parameters)
+                case skolem if skolem.isExistentialSkolem => freshVar(skolem.deSkolemize.asInstanceOf[TypeSymbol])
+                case p => freshVar(p)
+              }
+
             val ptV        = pt.instantiateTypeParams(ptparams, ptvars)
 
             if (isPopulated(resTpInst, ptV)) {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 556c680cda..e300fdacf9 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -852,6 +852,33 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
         }
       }
 
+      /**
+       * To deal with the type slack between actual (run-time) types and statically known types, for each abstract type T,
+       * reflect its variance as a skolem that is upper-bounded by T (covariant position), or lower-bounded by T (contravariant).
+       *
+       * Consider the following example:
+       *
+       *  class AbsWrapperCov[+A]
+       *  case class Wrapper[B](x: Wrapped[B]) extends AbsWrapperCov[B]
+       *
+       *  def unwrap[T](x: AbsWrapperCov[T]): Wrapped[T] = x match {
+       *    case Wrapper(wrapped) => // Wrapper's type parameter must not be assumed to be equal to T, it's *upper-bounded* by it
+       *      wrapped // : Wrapped[_ <: T]
+       *  }
+       *
+       * this method should type check if and only if Wrapped is covariant in its type parameter
+       *
+       * when inferring Wrapper's type parameter B from x's type AbsWrapperCov[T],
+       * we must take into account that x's actual type is AbsWrapperCov[Tactual] forSome {type Tactual <: T}
+       * as AbsWrapperCov is covariant in A -- in other words, we must not assume we know T exactly, all we know is its upper bound
+       *
+       * since method application is the only way to generate this slack between run-time and compile-time types (TODO: right!?),
+       * we can simply replace skolems that represent method type parameters as seen from the method's body
+       * by other skolems that are (upper/lower)-bounded by that type-parameter skolem
+       * (depending on the variance position of the skolem in the statically assumed type of the scrutinee, pt)
+       *
+       * see test/files/../t5189*.scala
+       */
       def adaptConstrPattern(): Tree = { // (5)
         val extractor = tree.symbol.filter(sym => reallyExists(unapplyMember(sym.tpe)))
         if (extractor != NoSymbol) {
@@ -865,7 +892,32 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
             val tree1 = TypeTree(clazz.primaryConstructor.tpe.asSeenFrom(prefix, clazz.owner))
               .setOriginal(tree)
 
-            inferConstructorInstance(tree1, clazz.typeParams, pt)
+            val skolems = new mutable.ListBuffer[TypeSymbol]
+            object variantToSkolem extends VariantTypeMap {
+              def apply(tp: Type) = mapOver(tp) match {
+                case TypeRef(NoPrefix, tpSym, Nil) if variance != 0 && tpSym.isTypeParameterOrSkolem && tpSym.owner.isTerm =>
+                  val bounds = if (variance == 1) TypeBounds.upper(tpSym.tpe) else TypeBounds.lower(tpSym.tpe)
+                  val skolem = context.owner.newExistentialSkolem(tpSym, tpSym, unit.freshTypeName("?"+tpSym.name), bounds)
+                  // println("mapping "+ tpSym +" to "+ skolem + " : "+ bounds +" -- pt= "+ pt)
+                  skolems += skolem
+                  skolem.tpe
+                case tp1 => tp1
+              }
+            }
+
+            // have to open up the existential and put the skolems in scope
+            // can't simply package up pt in an ExistentialType, because that takes us back to square one (List[_ <: T] == List[T] due to covariance)
+            val ptSafe   = variantToSkolem(pt) // TODO: pt.skolemizeExistential(context.owner, tree) ?
+            val freeVars = skolems.toList
+
+            // use "tree" for the context, not context.tree: don't make another CaseDef context,
+            // as instantiateTypeVar's bounds would end up there
+            val ctorContext = context.makeNewScope(tree, context.owner)
+            freeVars foreach ctorContext.scope.enter
+            newTyper(ctorContext).infer.inferConstructorInstance(tree1, clazz.typeParams, ptSafe)
+
+            // tree1's type-slack skolems will be deskolemized (to the method type parameter skolems)
+            // once the containing CaseDef has been type checked (see typedCase)
             tree1
           } else {
             tree
@@ -1986,15 +2038,35 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
       val guard1: Tree = if (cdef.guard == EmptyTree) EmptyTree
                          else typed(cdef.guard, BooleanClass.tpe)
       var body1: Tree = typed(cdef.body, pt)
-      if (!context.savedTypeBounds.isEmpty) {
-        body1.tpe = context.restoreTypeBounds(body1.tpe)
-        if (isFullyDefined(pt) && !(body1.tpe <:< pt)) {
-          // @M no need for pt.normalize here, is done in erasure
+
+      val contextWithTypeBounds = context.nextEnclosing(_.tree.isInstanceOf[CaseDef])
+      if (contextWithTypeBounds.savedTypeBounds nonEmpty) {
+        body1.tpe = contextWithTypeBounds restoreTypeBounds body1.tpe
+
+        // insert a cast if something typechecked under the GADT constraints,
+        // but not in real life (i.e., now that's we've reset the method's type skolems'
+        //   infos back to their pre-GADT-constraint state)
+        if (isFullyDefined(pt) && !(body1.tpe <:< pt))
           body1 = typedPos(body1.pos)(gen.mkCast(body1, pt))
-        }
+
       }
+
 //    body1 = checkNoEscaping.locals(context.scope, pt, body1)
-      treeCopy.CaseDef(cdef, pat1, guard1, body1) setType body1.tpe
+      val treeWithSkolems = treeCopy.CaseDef(cdef, pat1, guard1, body1) setType body1.tpe
+
+      // undo adaptConstrPattern's evil deeds, as they confuse the old pattern matcher
+      // TODO: Paul, can we do the deskolemization lazily in the old pattern matcher
+      object deskolemizeOnce extends TypeMap {
+        def apply(tp: Type): Type = mapOver(tp) match {
+          case TypeRef(pre, sym, args) if sym.isExistentialSkolem && sym.deSkolemize.isSkolem && sym.deSkolemize.owner.isTerm =>
+            typeRef(NoPrefix, sym.deSkolemize, args)
+          case tp1 => tp1
+        }
+      }
+
+      new TypeMapTreeSubstituter(deskolemizeOnce).traverse(treeWithSkolems)
+
+      treeWithSkolems // now without skolems, actually
     }
 
     def typedCases(cases: List[CaseDef], pattp: Type, pt: Type): List[CaseDef] =