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.

1 files changed, 20 insertions, 2 deletions

diff --git a/src/compiler/scala/reflect/internal/Types.scala b/src/compiler/scala/reflect/internal/Types.scala
index e8b9dc0865..b5777c099f 100644
--- a/src/compiler/scala/reflect/internal/Types.scala
+++ b/src/compiler/scala/reflect/internal/Types.scala
@@ -90,6 +90,8 @@ trait Types /*extends reflect.generic.Types*/ { self: SymbolTable =>
   private final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1
 
   private final val printLubs = false
+  /** In case anyone wants to turn off lub verification without reverting anything. */
+  private final val verifyLubs = true
 
   /** The current skolemization level, needed for the algorithms
    *  in isSameType, isSubType that do constraint solving under a prefix.
@@ -5310,9 +5312,25 @@ A type's typeSymbol should never be inspected directly.
               }
           }
           if (lubRefined.decls.isEmpty) lubBase
+          else if (!verifyLubs) lubRefined
           else {
-//            println("refined lub of "+ts+"/"+narrowts+" is "+lubRefined+", baseclasses = "+(ts map (_.baseTypeSeq) map (_.toList)))
-            lubRefined
+            // Verify that every given type conforms to the calculated lub.
+            // In theory this should not be necessary, but higher-order type
+            // parameters are not handled correctly.
+            val ok = ts forall { t =>
+              (t <:< lubRefined) || {
+                if (settings.debug.value) {
+                  Console.println(
+                    "Malformed lub: " + lubRefined + "\n" +
+                    "Argument " + t + " does not conform.  Falling back to " + lubBase
+                  )
+                }
+                false
+              }
+            }
+            // If not, fall back on the more conservative calculation.
+            if (ok) lubRefined
+            else lubBase
           }
         }
       existentialAbstraction(tparams, lubType)