Added sanity check to lub calculation to preven...

Added sanity check to lub calculation to prevent invalid lubs from
emerging. The underlying cause of said lubs is that higher-order
type parameters are not handled correctly: this is why the issue
is seen so frequently in the collections. See pending test
pending/pos/those-kinds-are-high.scala for a demonstration. Until that's
fixed, we can at least raise the bar a bit.

Closes #2094, #2322, #4501. Also, some test cases in neg have been
promoted into working programs: #2179, #3774. (They're not in neg for
the "shouldn't work" reason, but out of despair.)

In some cases, such as the original reported ticket in #3528, this
only pushes the problem downfield: it still fails due to inferred type
parameters not conforming to bounds. I believe a similar issue with
higher-order type parameters underlies that.

Look at how far this takes us though. All kinds of stuff which did not
work, now works. None of these even compiled until now:

  scala> :type List(mutable.Map(1 -> 1), immutable.Map(1 -> 1))
  List[scala.collection.Map[Int,Int]]

  scala> :type Set(List(1), mutable.Map(1 -> 1))
  scala.collection.Set[Iterable[Any] with PartialFunction[Int,Int]]

  scala> :type Stream(List(1), Set(1), 1 to 5)
  Stream[Iterable[Int] with Int => AnyVal{def getClass(): Class[_ >: Int with Boolean <: AnyVal]}]

  scala> :type Map(1 -> (1 to 10), 2 -> (1 to 10).toList)
  scala.collection.immutable.Map[Int,scala.collection.immutable.Seq[Int]
  ]

PERFORMANCE: compiling quick.lib and quick.comp, this patch results in
an extra 27 subtype tests. Total. Time difference too small to measure.
However to be on the safe side I made it really easy to disable.

  private final val verifyLubs = true // set to false

Review by moors, odersky.

8 files changed, 90 insertions, 16 deletions

diff --git a/test/files/neg/t2179.check b/test/files/neg/t2179.check
deleted file mode 100644
index aa94fabe1f..0000000000
--- a/test/files/neg/t2179.check
+++ /dev/null
@@ -1,9 +0,0 @@
-t2179.scala:2: error: inferred type arguments [scala.collection.immutable.Seq[Double]{def companion: scala.collection.generic.GenericCompanion[scala.collection.immutable.Seq[Any]]; protected def thisCollection: Seq[Double]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}}] do not conform to method reduceLeft's type parameter bounds [B >: List[Double]]
-  (Nil:List[List[Double]]).reduceLeft((_: Any, _: Any) => Nil.indices.map(_ => 0d))
-                           ^
-t2179.scala:2: error: type mismatch;
- found   : (Any, Any) => scala.collection.immutable.IndexedSeq[Double]
- required: (scala.collection.immutable.Seq[Double]{def companion: scala.collection.generic.GenericCompanion[scala.collection.immutable.Seq[Any]]; protected def thisCollection: Seq[Double]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}}, List[Double]) => scala.collection.immutable.Seq[Double]{def companion: scala.collection.generic.GenericCompanion[scala.collection.immutable.Seq[Any]]; protected def thisCollection: Seq[Double]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}}
-  (Nil:List[List[Double]]).reduceLeft((_: Any, _: Any) => Nil.indices.map(_ => 0d))
-                                                       ^
-two errors found
diff --git a/test/files/neg/t3774.check b/test/files/neg/t3774.check
deleted file mode 100644
index cce2d7076c..0000000000
--- a/test/files/neg/t3774.check
+++ /dev/null
@@ -1,7 +0,0 @@
-t3774.scala:4: error: overloaded method value ++ with alternatives:
-  [B1 >: List[Int]](xs: scala.collection.GenTraversableOnce[((Int, Int), B1)])scala.collection.immutable.Map[(Int, Int),B1] <and>
-  [B >: ((Int, Int), List[Int]), That](that: scala.collection.GenTraversableOnce[B])(implicit bf: scala.collection.generic.CanBuildFrom[scala.collection.immutable.Map[(Int, Int),List[Int]],B,That])That
- cannot be applied to (scala.collection.immutable.IndexedSeq[((Int, Int), scala.collection.immutable.Range.Inclusive)])
-  Map[(Int,Int),List[Int]]() ++ (for(x <- 0 to 1 ; y <- 0 to 1) yield {(x,y)-> (0 to 1)})
-                             ^
-one error found
diff --git a/test/files/pos/bug2094.scala b/test/files/pos/bug2094.scala
new file mode 100644
index 0000000000..ff142117b2
--- /dev/null
+++ b/test/files/pos/bug2094.scala
@@ -0,0 +1,31 @@
+object Test extends App {
+  // compiles:
+  Map[Int, Value](
+    0 -> KnownType(classOf[Object]),
+    1 -> UnknownValue())
+
+  // does not compile:
+  Map(
+    0 -> KnownType(classOf[Object]),
+    1 -> UnknownValue())
+
+  // Experiment.scala:10: error: type mismatch;
+  //  found   : (Int, KnownType)
+  //  required: (Int, Product with Value{def getType: Option[java.lang.Class[_$$2]]}) where type _$$2
+  //     0 -> KnownType(classOf[Object]),
+  //       ^
+  // one error found
+}
+sealed trait Value {
+  def getType: Option[Class[_]]
+}
+
+case class UnknownValue() extends Value {
+  def getType = None
+  // compiles if changed to:
+  // def getType: Option[Class[_]] = None
+}
+
+case class KnownType(typ: Class[_]) extends Value {
+  def getType = Some(typ)
+}
\ No newline at end of file
diff --git a/test/files/pos/bug3528.scala b/test/files/pos/bug3528.scala
new file mode 100644
index 0000000000..ff49b3e929
--- /dev/null
+++ b/test/files/pos/bug3528.scala
@@ -0,0 +1,8 @@
+class A {
+  // 3528 - not fixed
+  // def f1 = List(List(1), Stream(1))
+  // 3528 comments
+  def f2 = List(Set(1,2,3), List(1,2,3))
+  // 2322
+  def f3 = List(null: Range, null: List[Int])
+}
diff --git a/test/files/pos/bug4501.scala b/test/files/pos/bug4501.scala
new file mode 100644
index 0000000000..40628f1a4b
--- /dev/null
+++ b/test/files/pos/bug4501.scala
@@ -0,0 +1,14 @@
+// After lub modification
+import scala.collection.mutable.ListBuffer
+
+class A {
+  def foo[T](a:T, b:T):T = a
+  def f1 = foo(ListBuffer(), List())
+  def f2 = foo(ListBuffer(), ListBuffer())
+  def f3 = foo(List(), List())
+
+  // scalap
+  // def f1 : scala.collection.Seq[scala.Nothing] = { /* compiled code */ }
+  // def f2 : scala.collection.mutable.ListBuffer[scala.Nothing] = { /* compiled code */ }
+  // def f3 : scala.collection.immutable.List[scala.Nothing] = { /* compiled code */ }
+}
\ No newline at end of file
diff --git a/test/files/neg/t2179.scala b/test/files/pos/t2179.scala
index 89e22b6e2a..89e22b6e2a 100755
--- a/test/files/neg/t2179.scala
+++ b/test/files/pos/t2179.scala
diff --git a/test/files/neg/t3774.scala b/test/files/pos/t3774.scala
index 2869925b01..2869925b01 100644
--- a/test/files/neg/t3774.scala
+++ b/test/files/pos/t3774.scala
diff --git a/test/pending/pos/those-kinds-are-high.scala b/test/pending/pos/those-kinds-are-high.scala
new file mode 100644
index 0000000000..d3ee2bf308
--- /dev/null
+++ b/test/pending/pos/those-kinds-are-high.scala
@@ -0,0 +1,37 @@
+class A {
+  trait Container[+T]
+  trait Template[+CC[X] <: Container[X]]
+
+  class C1[T] extends Template[C1] with Container[T]
+  class C2[T] extends Template[C2] with Container[T]
+
+  /** Target expression:
+   *    List(new C1[String], new C2[String])
+   */
+
+  // Here's what would ideally be inferred.
+  //
+  // scala> :type List[Template[Container] with Container[String]](new C1[String], new C2[String])
+  // List[Template[Container] with Container[java.lang.String]]
+  //
+  // Here's what it does infer.
+  //
+  // scala> :type List(new C1[String], new C2[String])
+  // <console>:8: error: type mismatch;
+  //  found   : C1[String]
+  //  required: Container[String] with Template[Container[Any] with Template[Container[Any] with Template[Any] with ScalaObject] with ScalaObject] with ScalaObject
+  //        List(new C1[String], new C2[String])
+  //             ^
+  //
+  // Simplified, the inferred type is:
+  //
+  //   List[Container[String] with Template[Container[Any] with Template[Container[Any] with Template[Any]]]
+  //
+
+  /** Working version explicitly typed.
+   */
+  def fExplicit = List[Template[Container] with Container[String]](new C1[String], new C2[String])
+
+  // nope
+  // def fFail = List(new C1[String], new C2[String])
+}