Imported From: https://issues.scala-lang.org/browse/SI-2251?orig=1
Reporter: @adriaanm

@adriaanm said:
should be fixed in r18475 (Martin, please check!)

@odersky said:
That's a partial fix at best, because it does not detect mutually recursive f-bounds, and is also not stable under aliasing.

The current way to treat F-bounds is to ignore them totally when forming lubs and when doing type inference, and then checking after the fact that inferred types satisy the bounds.

How did bug1001 fail?

I think we need to dig a bit deeper here.

@adriaanm said:
bug1001 failed because the existential type that's constructed by mergePrefixAndArgs does not meet the f-bounds.

Compiler output (edited to remove irrelevant stuff -- with printLubs enabled and some diagnostics in mergePrefixAndArgs):

lub of List(D, C) at depth 2
  lub of List(D, C) at depth 1
    lub of List(D, C) at depth 0
    lub of List(D, C) is A
MPAA of: List(B[D], B[C])
MPAA(params, sym, args) = (List(type _1 >: D with C <: A),trait B,List(_1))
  lub of List(D, C) is B[_ >: D with C <: A]
MPAA of: List(B[D], B[C])
MPAA(params, sym, args) = (List(type _2 >: D with C <: B[_ >: D with C <: A]),trait B,List(_2))
lub of List(D, C) is B[_ >: D with C <: B[_ >: D with C <: A]]

/Users/adriaan/git/scala/test/files/pos/ticket2251.scala:22: error: type arguments [_1] do not conform to trait B's type parameter bounds [T <: B[T]]
  val data: List[A] = List(new C, new D)
                      ^
one error found

Maybe this is the expected behaviour then? Should we focus on providing a better error message and leave mergePrefixAndArgs as it was?

Anyway, the inferred type is:

B[_2] forSome { type _2 >: D with C{} <: B[_1] forSome { type _1 >: D with C{} <: A } } (not well-formed)

instead of the well-formed:

B[_2] forSome { type _2 <: B[_2]}

it's interesting that this first type is the unrolling (up to a certain depth) of the second one -- there's probably no complete algorithm to detect this and "roll the type back up", though... (is there?)

I'm not sure whether this could work, but maybe we could improve mergePrefixAndArgs so that it detects f-bounds (with a more robust check) and then takes the type schema and replaces the type parameters by existentials?

E.g., Foo[T <: Foo[U, U], U <: T] would become Foo[A, B] forSome {type A <: Foo[B, B]; type B <: A}. As a further refinement, we could take the lub and glb of the type arguments that Foo was applied to and add them to the bounds of the type variables of the existential.

@paulp said:
You can reclose this if you want, but I thought this was interesting enough.

class A 
trait B[T <: B[T]] extends A
class C extends B[C]
class D extends B[D]

class E {
  val ys = List(List(new C), Stream(new D))
}

If you compile with -Ydebug you can watch the malformed lubs as they are discarded. Eventually it admits defeat:

./a.scala:10: error: type arguments [B[_ >: D with C <: B[_ >: D with C <: A]],scala.collection.immutable.LinearSeq[B[_ >: D with C <: A]] with scala.collection.LinearSeqOptimized[B[_ >: D with C <: A],scala.collection.immutable.LinearSeq[A] with scala.collection.LinearSeqOptimized[A,scala.collection.immutable.LinearSeq[Any] with scala.collection.LinearSeqOptimized[Any,Any]]]] do not conform to trait LinearSeqOptimized's type parameter bounds [+A,+Repr <: scala.collection.LinearSeqOptimized[A,Repr]]
  val ys = List(List(new C), Stream(new D))
      ^

@paulp said:
I forgot to link to this: scala/scala@db46c71e

@adriaanm said:
Unassigning and rescheduling to M6 as previous deadline was missed.

@adriaanm said:
As close to fixed as it'll get in Scala 2, I'm afraid.