SI-8224 Fix regression in f-bound aware LUBs

Disable the heuristic approach to recursive bounds unless
the compiler is running under `-Xstrict-inference`.
[the above was not authored by the original author]

In db46c71e88, steps were taken to avoid blowing up in the
pathological LUB calculation needed for:

    def trav = List(List(), Stream())

This skipped a level in the base class sequence when f-bounds
were detected at the current level.

In that example, when `lublist` was about to:

    mergePrefixAndArgs(
      typeOf[LinearSeqOptimized[A, List[A]]],
      typeOf[LinearSeqOptimized[A, Stream[A]]],
    )

If it proceeded (as in 2.10.3), the LUB is invalid:

    error: type arguments [B[_ >: D with C <: B[_ >: D with C <: A]],s.c.immutable.LinearSeq[B[_ >: D with C <: A]] with s.c.AbstractSeq[B[_ >: D with C <: A]] with s.c.LinearSeqOptimized[B[_ >: D with C <: A],s.c.immutable.LinearSeq[A] with s.c.AbstractSeq[A] with s.c.LinearSeqOptimized[A,Immutable with Equals with java.io.Serializable] with java.io.Serializable] with java.io.Serializable] do not conform to trait LinearSeqOptimized's type parameter bounds [+A,+Repr <: s.c.LinearSeqOptimized[A,Repr]]

To avoid this, the added code would skip to the first non-F-bounded
base type of the same arity of each element in the list. This would
get to:

    LinearSeqLike[D, Stream[D]]
    LinearSeqLike[C, List[C]]

which are lubbable without violating the type constraints.

I don't think this was the right remedy. For starters, as seen in
this bug report, SI-8224, if the list of types are identical we
have let a perfectly good lub slip through our fingers, and end up
calculating too general a type.

More generally, if the type arguments in f-bounded positions coincide,
we don't risk calculating a ill-bounded LUB.

Furthermore, the code was widening each of the types separately;
this isn't something we want to do within `if (isUniformFrontier)`.
AFAICT this was just wasteful and as all `ts0` start with the same
type symbol, so `typeConstructorList` should be uniform.

This commit restricts this base-class skipping to situations where
the argument inferred for an type argument that is used as an f-bound
is not:

    a) an existential (as created by `mergePrefixAndArgs` in invariant
      positions.), or
    b) equivalent to one of the corresponding input type arguments
       (this is the case that fixes the regression in pos/8224.scala)

6 files changed, 48 insertions, 37 deletions

diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
index 048fe9ef37..a494c7f0d0 100644
--- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
+++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala
@@ -37,6 +37,7 @@ abstract class MutableSettings extends AbsSettings {
   def XfullLubs: BooleanSetting
   def XnoPatmatAnalysis: BooleanSetting
   def Xprintpos: BooleanSetting
+  def strictInference: BooleanSetting
   def Yposdebug: BooleanSetting
   def Yrangepos: BooleanSetting
   def Yshowsymowners: BooleanSetting
diff --git a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
index 1c4d05ae32..876685e24a 100644
--- a/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
+++ b/src/reflect/scala/reflect/internal/tpe/GlbLubs.scala
@@ -14,11 +14,11 @@ private[internal] trait GlbLubs {
   import TypesStats._
 
   private final val printLubs = scala.sys.props contains "scalac.debug.lub"
+  private final val strictInference = settings.strictInference
 
   /** In case anyone wants to turn off lub verification without reverting anything. */
   private final val verifyLubs = true
 
-
   private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Depth) {
     import util.TableDef
     import TableDef.Column
@@ -63,6 +63,26 @@ private[internal] trait GlbLubs {
     }
   }
 
+  // only called when strictInference
+  private def willViolateRecursiveBounds(tp: Type, ts: List[Type], tsElimSub: List[Type]) = {
+    val typeSym     = ts.head.typeSymbol // we're uniform, the `.head` is as good as any.
+    def fbounds     = findRecursiveBounds(ts) map (_._2)
+    def isRecursive = typeSym.typeParams exists fbounds.contains
+
+    isRecursive && (transposeSafe(tsElimSub map (_.normalize.typeArgs)) match {
+      case Some(arggsTransposed) =>
+        val mergedTypeArgs = (tp match { case et: ExistentialType => et.underlying; case _ => tp}).typeArgs
+        exists3(typeSym.typeParams, mergedTypeArgs, arggsTransposed) {
+          (param, arg, lubbedArgs) =>
+            val isExistential = arg.typeSymbol.isExistentiallyBound
+            val isInFBound    = fbounds contains param
+            val wasLubbed     = !lubbedArgs.exists(_ =:= arg)
+            (!isExistential && isInFBound && wasLubbed)
+        }
+      case None => false
+    })
+  }
+
   /** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix),
     * compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types:
     *
@@ -88,7 +108,8 @@ private[internal] trait GlbLubs {
       case _ => tp
     }
     // pretypes is a tail-recursion-preserving accumulator.
-    @tailrec def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = {
+    @tailrec
+    def loop(pretypes: List[Type], tsBts: List[List[Type]]): List[Type] = {
       lubListDepth = lubListDepth.incr
 
       if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) pretypes.reverse
@@ -110,28 +131,19 @@ private[internal] trait GlbLubs {
         // merging, strip targs that refer to bound tparams (when we're computing the lub of type
         // constructors.) Also filter out all types that are a subtype of some other type.
         if (isUniformFrontier) {
-          val fbounds     = findRecursiveBounds(ts0) map (_._2)
-          val tcLubList   = typeConstructorLubList(ts0)
-          def isRecursive(tp: Type) = tp.typeSymbol.typeParams exists fbounds.contains
-
-          val ts1 = ts0 map { t =>
-            if (isRecursive(t)) {
-              tcLubList map (t baseType _.typeSymbol) find (t => !isRecursive(t)) match {
-                case Some(tp) => logResult(s"Breaking recursion in lublist, substituting weaker type.\n  Was: $t\n  Now")(tp)
-                case _        => t
-              }
-            }
-            else t
-          }
           val tails = tsBts map (_.tail)
-          mergePrefixAndArgs(elimSub(ts1, depth) map elimHigherOrderTypeParam, Covariant, depth) match {
+          val ts1   = elimSub(ts0, depth) map elimHigherOrderTypeParam
+          mergePrefixAndArgs(ts1, Covariant, depth) match {
             case NoType => loop(pretypes, tails)
-            case tp     => loop(tp :: pretypes, tails)
+            case tp if strictInference && willViolateRecursiveBounds(tp, ts0, ts1) =>
+              log(s"Breaking recursion in lublist, advancing frontier and discaring merged prefix/args from $tp")
+              loop(pretypes, tails)
+            case tp =>
+              loop(tp :: pretypes, tails)
           }
-        }
-        else {
+        } else {
           // frontier is not uniform yet, move it beyond the current minimal symbol;
-          // lather, rinSe, repeat
+          // lather, rinse, repeat
           val sym    = minSym(ts0)
           val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts)
           if (printLubs) {
@@ -257,23 +269,6 @@ private[internal] trait GlbLubs {
   private val _glbResults = new mutable.HashMap[(Depth, List[Type]), Type]
   def glbResults = _glbResults
 
-  /** Given a list of types, finds all the base classes they have in
-    *  common, then returns a list of type constructors derived directly
-    *  from the symbols (so any more specific type information is ignored.)
-    *  The list is filtered such that every type constructor in the list
-    *  expects the same number of type arguments, which is chosen based
-    *  on the deepest class among the common baseclasses.
-    */
-  def typeConstructorLubList(ts: List[Type]): List[Type] = {
-    val bcs   = ts.flatMap(_.baseClasses).distinct sortWith (_ isLess _)
-    val tcons = bcs filter (clazz => ts forall (_.typeSymbol isSubClass clazz))
-
-    tcons map (_.typeConstructor) match {
-      case Nil      => Nil
-      case t :: ts  => t :: ts.filter(_.typeParams.size == t.typeParams.size)
-    }
-  }
-
   def lub(ts: List[Type]): Type = ts match {
     case Nil      => NothingTpe
     case t :: Nil => t
diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala
index d46846fc21..27d574b1de 100644
--- a/src/reflect/scala/reflect/runtime/Settings.scala
+++ b/src/reflect/scala/reflect/runtime/Settings.scala
@@ -33,6 +33,7 @@ private[reflect] class Settings extends MutableSettings {
   val Xexperimental     = new BooleanSetting(false)
   val XfullLubs         = new BooleanSetting(false)
   val XnoPatmatAnalysis = new BooleanSetting(false)
+  val strictInference   = new BooleanSetting(false)
   val Xprintpos         = new BooleanSetting(false)
   val Yposdebug         = new BooleanSetting(false)
   val Yrangepos         = new BooleanSetting(false)
diff --git a/test/files/pos/t8224.scala b/test/files/pos/t8224.scala
new file mode 100644
index 0000000000..2fae925df3
--- /dev/null
+++ b/test/files/pos/t8224.scala
@@ -0,0 +1,12 @@
+import language.higherKinds
+
+trait P  [N1, +E1[X <: N1]]
+trait PIn[N2, +E2[X <: N2]] extends P[Int,Any]
+
+trait EI extends PIn[Int, Nothing]
+trait NI extends PIn[Int, Nothing]
+
+object Test {
+  val lub = if (true) ??? : EI else ??? : NI
+  val pin: PIn[Int,Nothing] = lub
+}
diff --git a/test/files/run/t2251.flags b/test/files/run/t2251.flags
new file mode 100644
index 0000000000..19243266d1
--- /dev/null
+++ b/test/files/run/t2251.flags
@@ -0,0 +1 @@
+-Xstrict-inference
\ No newline at end of file
diff --git a/test/files/run/t2251b.flags b/test/files/run/t2251b.flags
new file mode 100644
index 0000000000..19243266d1
--- /dev/null
+++ b/test/files/run/t2251b.flags
@@ -0,0 +1 @@
+-Xstrict-inference
\ No newline at end of file