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`.

4 files changed, 83 insertions, 0 deletions

diff --git a/test/files/neg/lub-from-hell-2.check b/test/files/neg/lub-from-hell-2.check
new file mode 100644
index 0000000000..3ef935f93b
--- /dev/null
+++ b/test/files/neg/lub-from-hell-2.check
@@ -0,0 +1,7 @@
+lub-from-hell-2.scala:3: error: type arguments [Any,Iterable[Any] with Int => Any with scala.collection.generic.Subtractable[Any,Iterable[Any] with Int => Any with scala.collection.generic.Subtractable[Any,Iterable[Any] with Int => Any]{def seq: Iterable[Any] with Int => Any}]{def seq: Iterable[Any] with Int => Any{def seq: Iterable[Any] with Int => Any}}] do not conform to trait Subtractable's type parameter bounds [A,+Repr <: scala.collection.generic.Subtractable[A,Repr]]
+  def foo(a: Boolean, b: collection.mutable.Set[Any], c: collection.mutable.ListBuffer[Any]) = if (a) b else c
+      ^
+lub-from-hell-2.scala:4: error: type arguments [Any,scala.collection.mutable.Iterable[Any] with scala.collection.mutable.Cloneable[scala.collection.mutable.Iterable[Any] with scala.collection.mutable.Cloneable[scala.collection.mutable.Iterable[Any] with Cloneable with Int => Any] with Int => Any{def seq: scala.collection.mutable.Iterable[Any] with Cloneable with Int => Any}] with scala.collection.generic.Growable[Any] with Int => Any with scala.collection.generic.Shrinkable[Any] with scala.collection.generic.Subtractable[Any,Iterable[Any] with Int => Any with scala.collection.generic.Subtractable[Any,Iterable[Any] with Int => Any]{def seq: Iterable[Any] with Int => Any}] with scala.collection.script.Scriptable[Any]] do not conform to trait Subtractable's type parameter bounds [A,+Repr <: scala.collection.generic.Subtractable[A,Repr]]
+  def bar(a: Boolean, b: scala.collection.mutable.SetLike[Any,scala.collection.mutable.Set[Any]], c: scala.collection.mutable.Buffer[Any]) = if (a) b else c
+      ^
+two errors found
diff --git a/test/files/neg/lub-from-hell-2.scala b/test/files/neg/lub-from-hell-2.scala
new file mode 100644
index 0000000000..96760c6edf
--- /dev/null
+++ b/test/files/neg/lub-from-hell-2.scala
@@ -0,0 +1,6 @@
+class Test {
+  trait Tree
+  def foo(a: Boolean, b: collection.mutable.Set[Any], c: collection.mutable.ListBuffer[Any]) = if (a) b else c
+  def bar(a: Boolean, b: scala.collection.mutable.SetLike[Any,scala.collection.mutable.Set[Any]], c: scala.collection.mutable.Buffer[Any]) = if (a) b else c
+  // bar produces an ill-bounded LUB in 2.11.8. After this commit, which fixes a bug in existential+refinement lubs, foo also fails.
+}
diff --git a/test/files/pos/lub-from-hell.scala b/test/files/pos/lub-from-hell.scala
new file mode 100644
index 0000000000..a7d2a99b08
--- /dev/null
+++ b/test/files/pos/lub-from-hell.scala
@@ -0,0 +1,11 @@
+class Test {
+  trait Tree
+  def foo(b: Boolean, buf: collection.mutable.ArrayBuffer[Any], acc: StringBuilder) = if (b) buf else acc
+
+  // def bar(b: Boolean,
+  //   buf: scala.collection.IndexedSeqLike[Any,Cloneable with Mutable with Equals], 
+  //   acc: scala.collection.IndexedSeqLike[_18,scala.collection.mutable.IndexedSeq[_18]] with scala.collection.IndexedSeqLike[_18,IndexedSeq[_18]] forSome { type _18 >: String with Char }
+  // ) = if (b) buf else acc
+
+
+}
diff --git a/test/junit/scala/reflect/internal/TypesTest.scala b/test/junit/scala/reflect/internal/TypesTest.scala
index 45a4369396..763fd73c8a 100644
--- a/test/junit/scala/reflect/internal/TypesTest.scala
+++ b/test/junit/scala/reflect/internal/TypesTest.scala
@@ -69,4 +69,63 @@ class TypesTest {
     assert(elem0.contains(IntClass))
   }
 
+  @Test
+  def testRefinedLubs(): Unit = {
+    // https://github.com/scala/scala-dev/issues/168
+    assertEquals(typeOf[Option[AnyVal]], lub(typeOf[Option[Int] with Option[Char]] :: typeOf[Option[Boolean] with Option[Short]] :: Nil))
+    assertEquals(typeOf[Option[AnyVal]], lub(typeOf[Option[Int] with Option[Char]] :: typeOf[Option[Boolean]] :: Nil))
+    assertEquals(typeOf[Option[AnyVal]], lub((typeOf[Option[Int] with Option[Char]] :: typeOf[Option[Boolean] with Option[Short]] :: Nil).reverse))
+    assertEquals(typeOf[Option[AnyVal]], lub((typeOf[Option[Int] with Option[Char]] :: typeOf[Option[Boolean]] :: Nil).reverse))
+  }
+
+  @Test
+  def testExistentialRefinement(): Unit = {
+    import rootMirror.EmptyPackageClass
+
+    // class M[A]
+    val MClass = EmptyPackageClass.newClass("M")
+    val A = MClass.newTypeParameter("A").setInfo(TypeBounds.empty)
+    MClass.setInfo(PolyType(A :: Nil, ClassInfoType(ObjectClass.tpeHK :: Nil, newScopeWith(), MClass)))
+
+    // (M[Int] with M[X] { def m: Any }) forSome { type X }
+    val X = NoSymbol.newExistential("X").setInfo(TypeBounds.empty)
+    val T: Type = {
+      val decls = newScopeWith(MClass.newMethod("m").setInfo(NullaryMethodType(AnyClass.tpeHK)))
+      val refined = refinedType(appliedType(MClass, IntClass.tpeHK) :: appliedType(MClass, X.tpeHK) :: Nil, NoSymbol, decls, NoPosition)
+      newExistentialType(X :: Nil, refined)
+    }
+
+    val RefinementClass = T.underlying.typeSymbol
+    assertTrue(RefinementClass.isRefinementClass)
+    TypeRef(NoPrefix, RefinementClass, Nil) match {
+      case rtr : RefinementTypeRef =>
+        // ContainsCollector needs to look inside the info of symbols of RefinementTypeRefs
+        assert(rtr.contains(X))
+    }
+
+    val underlying = T.underlying
+    val baseTypeSeqIndices = T.baseTypeSeq.toList.indices
+    for (i <- baseTypeSeqIndices) {
+      // Elements of the existential type should have the same type symbol as underlying
+      assertEquals(T.baseTypeSeq.typeSymbol(i), underlying.baseTypeSeq.typeSymbol(i))
+    }
+
+    // Type symbols should be distinct
+    def checkDistinctTypeSyms(bts: BaseTypeSeq): Unit = {
+      val syms = baseTypeSeqIndices.map(T.baseTypeSeq.typeSymbol)
+      assertEquals(syms, syms.distinct)
+    }
+    checkDistinctTypeSyms(T.baseTypeSeq)
+    checkDistinctTypeSyms(T.underlying.baseTypeSeq)
+
+    // This is the entry for the refinement class
+    assertTrue(T.baseTypeSeq.typeSymbol(0).isRefinementClass)
+    assertEquals("M[Int] with M[X]{def m: Any} forSome { type X }", T.baseTypeSeq.rawElem(0).toString)
+
+    // This is the entry for M. The raw entry is an existential over a RefinedType which encodes a lazily computed base type
+    assertEquals(T.baseTypeSeq.typeSymbol(1), MClass)
+    assertEquals("M[X] with M[Int] forSome { type X }", T.baseTypeSeq.rawElem(1).toString)
+    // calling `apply` merges the prefix/args of the elements ot the RefinedType and rewraps in the existential
+    assertEquals("M[_1] forSome { type X; type _1 >: X with Int }", T.baseTypeSeq.apply(1).toString)
+  }
 }