Improved refinement type and existential type handling

Lazy base type seq elements are encoded as a refined type with
an empty scope and a list of type refs over some common type
symbol that will be merged when `BaseTypeSeq#apply` is called.

The first change in this commit is to mark the creation and consumption
of such elements with calls to `[is]IntersectionTypeForBaseTypeSeq`. They
are distinguished by using the actual type symbol rather than a refinement
class symbol, which in turn simplifies the code in
`BaseTypeSeq#typeSymbol`.

I have also made `lub` aware of this encoding: it is now able to "see through"
to the parents of such refined types and merge them with other base types
of the same class symbol (even other refined types representing lazy BTS
elements.)

To make this fix work, I also had to fix a bug in LUBs of multiple with
existential types. Because of the way the recursion was structured in
`mergePrefixAndArgs`, the order of list of types being merged changed
behaviour: quantified varialbles of existential types were being rewrapped
around the resultting type, but only if we hadn't encountered the first
regular `TypeRef`.

This can be seen with the following before/after shot:

```
// 2.11.8
scala> val ts = typeOf[Set[Any]] :: typeOf[Set[X] forSome { type X <: Y; type Y <: Int}] :: Nil; def merge(ts: List[Type]) = mergePrefixAndArgs(ts, Variance.Contravariant, lubDepth(ts)); val merged1 = merge(ts); val merged2 = merge(ts.reverse); (ts.forall(_ <:< merged1), ts.forall(_ <:< merged2))
ts: List[$r.intp.global.Type] = List(Set[Any], Set[_ <: Int])
merge: (ts: List[$r.intp.global.Type])$r.intp.global.Type
merged1: $r.intp.global.Type = scala.collection.immutable.Set[_ >: Int]
merged2: $r.intp.global.Type = scala.collection.immutable.Set[_53] forSome { type X <: Int; type _53 >: X }
res0: (Boolean, Boolean) = (false,true)

// HEAD
...
merged1: $r.intp.global.Type = scala.collection.immutable.Set[_10] forSome { type X <: Int; type _10 >: X }
merged2: $r.intp.global.Type = scala.collection.immutable.Set[_11] forSome { type X <: Int; type _11 >: X }
res0: (Boolean, Boolean) = (true,true)
```

Furthermore, I have fixed the computation of the base type sequences of
existential types over refinement types, in order to maintain the invariant
that each slot of the base type sequence of a existential has the same
type symbol as that of its underlying type. Before, what I've now called
a `RefinementTypeRef` was transformed into a `RefinedType` during
rewrapping in the existential, which led to it being wrongly considered as
a lazy element of the base type sequence. The first change above should
also be sufficient to avoid the bug, but I felt it was worth cleaning up
`maybeRewrap` as an extra line of defence.

Finally, I have added another special case to `BaseTypeSeq#apply` to
be able to lazily compute elements that have been wrapped in an existential.

The unit test cases in `TypesTest` rely on these changes. A subsequent commit
will build on this foundation to make a fix to `asSeenFrom`.

1 files changed, 94 insertions, 72 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index 7dda805378..523cb968e7 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -174,8 +174,10 @@ trait Types
       if (newtp eq underlying) this
       // BoundedWildcardTypes reach here during erroneous compilation: neg/t6258
       // Higher-kinded exclusion is because [x]CC[x] compares =:= to CC: pos/t3800
+      // Avoid reusing the existing Wrapped(RefinedType) when we've be asked to wrap an =:= RefinementTypeRef, the
+      // distinction is important in base type sequences.
       // Otherwise, if newtp =:= underlying, don't rewrap it.
-      else if (!newtp.isWildcard && !newtp.isHigherKinded && (newtp =:= underlying)) this
+      else if (!newtp.isWildcard && !newtp.isHigherKinded && !newtp.isInstanceOf[RefinementTypeRef] && (newtp =:= underlying)) this
       else rewrap(newtp)
     )
     protected def rewrap(newtp: Type): Type
@@ -1589,7 +1591,6 @@ trait Types
    */
   case class RefinedType(override val parents: List[Type],
                          override val decls: Scope) extends CompoundType with RefinedTypeApi {
-
     override def isHigherKinded = (
       parents.nonEmpty &&
       (parents forall typeIsHigherKinded) &&
@@ -2704,6 +2705,7 @@ trait Types
     def isRepresentableWithWildcards = {
       val qset = quantified.toSet
       underlying match {
+        case _: RefinementTypeRef => false
         case TypeRef(pre, sym, args) =>
           def isQuantified(tpe: Type): Boolean = {
             (tpe exists (t => qset contains t.typeSymbol)) ||
@@ -3521,7 +3523,9 @@ trait Types
     if ((parents eq original.parents) && (decls eq original.decls)) original
     else {
       val owner = original.typeSymbol.owner
-      val result = refinedType(parents, owner)
+      val result =
+        if (isIntersectionTypeForLazyBaseType(original)) intersectionTypeForLazyBaseType(parents)
+        else refinedType(parents, owner)
       val syms1 = decls.toList
       for (sym <- syms1)
         result.decls.enter(sym.cloneSymbol(result.typeSymbol))
@@ -3596,6 +3600,14 @@ trait Types
     case tp :: Nil  => tp
     case _          => refinedType(tps, commonOwner(tps))
   }
+  def intersectionTypeForLazyBaseType(tps: List[Type]) = tps match {
+    case tp :: Nil  => tp
+    case _          => RefinedType(tps, newScope, tps.head.typeSymbolDirect)
+  }
+  def isIntersectionTypeForLazyBaseType(tp: RefinedType) = tp.parents match {
+    case head :: _ => tp.typeSymbolDirect eq head.typeSymbolDirect
+    case _ => false
+  }
 
 /**** This implementation to merge parents was checked in in commented-out
       form and has languished unaltered for five years.  I think we should
@@ -4409,83 +4421,93 @@ trait Types
    *  Return `x` if the computation succeeds with result `x`.
    *  Return `NoType` if the computation fails.
    */
-  def mergePrefixAndArgs(tps: List[Type], variance: Variance, depth: Depth): Type = tps match {
-    case tp :: Nil => tp
-    case TypeRef(_, sym, _) :: rest =>
-      val pres = tps map (_.prefix) // prefix normalizes automatically
+  def mergePrefixAndArgs(tps0: List[Type], variance: Variance, depth: Depth): Type = {
+    var tparams = mutable.ListBuffer[Symbol]()
+    val tps = tps0.flatMap {
+      case rt: RefinedType if isIntersectionTypeForLazyBaseType(rt) => rt.parents
+      case ExistentialType(qs, underlying) =>
+        tparams ++= qs
+        underlying match {
+          case rt: RefinedType if isIntersectionTypeForLazyBaseType(rt) => rt.parents
+          case tp => tp :: Nil
+        }
+      case tp => tp :: Nil
+    }
+
+    val merged = tps match {
+      case tp :: Nil => tp
+      case TypeRef(_, sym, _) :: rest =>
+        val pres = tps map (_.prefix) // prefix normalizes automatically
       val pre = if (variance.isPositive) lub(pres, depth) else glb(pres, depth)
-      val argss = tps map (_.normalize.typeArgs) // symbol equality (of the tp in tps) was checked using typeSymbol, which normalizes, so should normalize before retrieving arguments
+        val argss = tps map (_.normalize.typeArgs) // symbol equality (of the tp in tps) was checked using typeSymbol, which normalizes, so should normalize before retrieving arguments
       val capturedParams = new ListBuffer[Symbol]
-      try {
-        if (sym == ArrayClass && phase.erasedTypes) {
-          // special treatment for lubs of array types after erasure:
-          // if argss contain one value type and some other type, the lub is Object
-          // if argss contain several reference types, the lub is an array over lub of argtypes
-          if (argss exists typeListIsEmpty) {
-            NoType  // something is wrong: an array without a type arg.
-          }
-          else {
-            val args = argss map (_.head)
-            if (args.tail forall (_ =:= args.head)) typeRef(pre, sym, List(args.head))
-            else if (args exists (arg => isPrimitiveValueClass(arg.typeSymbol))) ObjectTpe
-            else typeRef(pre, sym, List(lub(args)))
+        try {
+          if (sym == ArrayClass && phase.erasedTypes) {
+            // special treatment for lubs of array types after erasure:
+            // if argss contain one value type and some other type, the lub is Object
+            // if argss contain several reference types, the lub is an array over lub of argtypes
+            if (argss exists typeListIsEmpty) {
+              NoType  // something is wrong: an array without a type arg.
+            }
+            else {
+              val args = argss map (_.head)
+              if (args.tail forall (_ =:= args.head)) typeRef(pre, sym, List(args.head))
+              else if (args exists (arg => isPrimitiveValueClass(arg.typeSymbol))) ObjectTpe
+              else typeRef(pre, sym, List(lub(args)))
+            }
           }
-        }
-        else transposeSafe(argss) match {
-          case None =>
-            // transpose freaked out because of irregular argss
-            // catching just in case (shouldn't happen, but also doesn't cost us)
-            // [JZ] It happens: see SI-5683.
-            debuglog(s"transposed irregular matrix!? tps=$tps argss=$argss")
-            NoType
-          case Some(argsst) =>
-            val args = map2(sym.typeParams, argsst) { (tparam, as0) =>
-              val as = as0.distinct
-              if (as.size == 1) as.head
-              else if (depth.isZero) {
-                log("Giving up merging args: can't unify %s under %s".format(as.mkString(", "), tparam.fullLocationString))
-                // Don't return "Any" (or "Nothing") when we have to give up due to
-                // recursion depth. Return NoType, which prevents us from poisoning
-                // lublist's results. It can recognize the recursion and deal with it, but
-                // only if we aren't returning invalid types.
-                NoType
-              }
-              else {
-                if (tparam.variance == variance) lub(as, depth.decr)
-                else if (tparam.variance == variance.flip) glb(as, depth.decr)
+          else transposeSafe(argss) match {
+            case None =>
+              // transpose freaked out because of irregular argss
+              // catching just in case (shouldn't happen, but also doesn't cost us)
+              // [JZ] It happens: see SI-5683.
+              debuglog(s"transposed irregular matrix!? tps=$tps argss=$argss")
+              NoType
+            case Some(argsst) =>
+              val args = map2(sym.typeParams, argsst) { (tparam, as0) =>
+                val as = as0.distinct
+                if (as.size == 1) as.head
+                else if (depth.isZero) {
+                  log("Giving up merging args: can't unify %s under %s".format(as.mkString(", "), tparam.fullLocationString))
+                  // Don't return "Any" (or "Nothing") when we have to give up due to
+                  // recursion depth. Return NoType, which prevents us from poisoning
+                  // lublist's results. It can recognize the recursion and deal with it, but
+                  // only if we aren't returning invalid types.
+                  NoType
+                }
                 else {
-                  val l = lub(as, depth.decr)
-                  val g = glb(as, depth.decr)
-                  if (l <:< g) l
-                  else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we
-                       // just err on the conservative side, i.e. with a bound that is too high.
-                       // if(!(tparam.info.bounds contains tparam))   //@M can't deal with f-bounds, see #2251
-
-                    val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l)
-                    capturedParams += qvar
-                    qvar.tpe
+                  if (tparam.variance == variance) lub(as, depth.decr)
+                  else if (tparam.variance == variance.flip) glb(as, depth.decr)
+                  else {
+                    val l = lub(as, depth.decr)
+                    val g = glb(as, depth.decr)
+                    if (l <:< g) l
+                    else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we
+                      // just err on the conservative side, i.e. with a bound that is too high.
+                      // if(!(tparam.info.bounds contains tparam))   //@M can't deal with f-bounds, see #2251
+
+                      val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l)
+                      capturedParams += qvar
+                      qvar.tpe
+                    }
                   }
                 }
               }
-            }
-            if (args contains NoType) NoType
-            else existentialAbstraction(capturedParams.toList, typeRef(pre, sym, args))
+              if (args contains NoType) NoType
+              else existentialAbstraction(capturedParams.toList, typeRef(pre, sym, args))
+          }
+        } catch {
+          case ex: MalformedType => NoType
         }
-      } catch {
-        case ex: MalformedType => NoType
-      }
-    case SingleType(_, sym) :: rest =>
-      val pres = tps map (_.prefix)
-      val pre = if (variance.isPositive) lub(pres, depth) else glb(pres, depth)
-      try singleType(pre, sym)
-      catch { case ex: MalformedType => NoType }
-    case ExistentialType(tparams, quantified) :: rest =>
-      mergePrefixAndArgs(quantified :: rest, variance, depth) match {
-        case NoType => NoType
-        case tpe    => existentialAbstraction(tparams, tpe)
-      }
-    case _ =>
-      abort(s"mergePrefixAndArgs($tps, $variance, $depth): unsupported tps")
+      case SingleType(_, sym) :: rest =>
+        val pres = tps map (_.prefix)
+        val pre = if (variance.isPositive) lub(pres, depth) else glb(pres, depth)
+        try singleType(pre, sym)
+        catch { case ex: MalformedType => NoType }
+      case _ =>
+        abort(s"mergePrefixAndArgs($tps, $variance, $depth): unsupported tps")
+    }
+    existentialAbstraction(tparams.toList, merged)
   }
 
   def addMember(thistp: Type, tp: Type, sym: Symbol): Unit = addMember(thistp, tp, sym, AnyDepth)