Generic type inference for foo[T](a:T, b:T)

[scabug]

=== What steps will reproduce the problem (please be specific and use wikiformatting)? ===

def foo[T](a:T, b:T):T = a
def test = foo(ListBuffer(), List()) 

=== What is the expected behavior? ===

Type of test is Seq[Nothing]

=== What do you see instead? ===

type mismatch; found : scala.collection.mutable.ListBuffer[Nothing] required: Seq[Nothing]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]

=== Additional information ===

def test = foo(ListBuffer():Seq[Nothing], List()) 

Works as expected

def test = foo[Seq[Nothing]](List(), ListBuffer()) 

Works as expected

trait R[T]
class A[T] extends R[T]
class B[T] extends R[T]

def test = foo(new A(), new B()) 

Works as expected: type of test is R[Nothing] === What versions of the following are you using? ===

• Scala: 2.8.1

Vitalii Fedorenko

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4501?orig=1 Reporter: Vitalii Fedorenko (zhaber)

[scabug]

@soc said: Same with Scala 2.10.0.r24736-b20110412020139, but I'm not sure this is a bug.

I suspect the problem is that ListBuffer is invariant in T, while List is covariant in T.

[scabug]

@magarciaEPFL said: I guess we can agree that the pattern to infer can be expressed more succinctly:

scala> def foo2[T](a:Seq[T], b:Seq[T]):Seq[T] = a
foo2: [T](a: Seq[T],b: Seq[T])Seq[T]

scala> def test2 = foo2(List(), scala.collection.mutable.ListBuffer())
test2: Seq[Nothing]

[scabug]

@dragos said: For better or worse, now we get two type errors:

scala> def test = foo(ListBuffer(), List()) 
<console>:9: error: type mismatch;
 found   : scala.collection.mutable.ListBuffer[Nothing]
 required: Seq[Nothing]{def seq: Seq[Nothing]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}; def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}
       def test = foo(ListBuffer(), List()) 
                                ^
<console>:9: error: type mismatch;
 found   : List[Nothing]
 required: Seq[Nothing]{def seq: Seq[Nothing]{def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}; def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}
       def test = foo(ListBuffer(), List()) 
                                        ^

I don't know enough about what type inference should be able to do, Adriaan, can you please have a look?

[scabug]

@adriaanm said: I would say this is another duplicate of #1570, or at least closely related. From cursory inspection, I suspect variance indeed causes the problems.

There's a check in the inferencer (in adjustTypeArgs) to see whether Nothing indicates inference failure (in which case, it is rolled back) or is a valid instantiation. Nothing is assumed to be a failure if: "[the type parameter for which Nothing was inferred] occurs in an invariant/contravariant position in restpe".

[scabug]

@paulp said: Maybe you guys have some good reason to be focusing elsewhere, but naive old extempore here would say the problem is that the argument types are not subtypes of the calculated lub. If I modify the lub calculation to pick a lub which is lubby, everything is fine.

// 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 */ }
}

Tell me what I'm missing.

[scabug]

@adriaanm said: That sounds plausible, since the original lub included {def companion: scala.collection.generic.GenericCompanion[Seq[Any]]}, where the Any is surprising (variance flipping gone awry?), but I didn't look into why that is.

[scabug]

@paulp said: I did. Patch coming shortly. Get your review hat ready!

[scabug]

Commit Message Bot (anonymous) said: (extempore in https://github.com/scala/scala/commit/034489b501) 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.