scala/scala — pull request #2294 by retronym (2013-03-23 14:37:03+00:00)
Title: SI-7289 Discard ill-kinded type constraints during inference

Let's disect the reported test case.

Define the first implicit:

scala> trait Schtroumpf[T]
defined trait Schtroumpf

scala> implicit def schtroumpf[T, U <: Coll[T], Coll[X] <: Traversable[X]]
| (implicit minorSchtroumpf: Schtroumpf[T]): Schtroumpf[U] = ???
schtroumpf: [T, U <: Coll[T], Coll[X] <: Traversable[X]](implicit minorSchtroumpf: Schtroumpf[T])Schtroumpf[U]

Call it explicitly => kind error during type inference reported.

scala> schtroumpf(null): Schtroumpf[Int]
:10: error: inferred kinds of the type arguments (Nothing,Int,Int) do not conform to the expected kinds of the type parameters (type T,type U,type Coll).
Int's type parameters do not match type Coll's expected parameters:
class Int has no type parameters, but type Coll has one
schtroumpf(null): Schtroumpf[Int]
^
:10: error: type mismatch;
found : Schtroumpf[U]
required: Schtroumpf[Int]
schtroumpf(null): Schtroumpf[Int]
^

Add another implicit, and let implicit search weigh them up.

scala> implicitly[Schtroumpf[Int]]
:10: error: diverging implicit expansion for type Schtroumpf[Int]
starting with method schtroumpf
implicitly[Schtroumpf[Int]]
^

scala> implicit val qoo = new Schtroumpf[Int]{}
qoo: Schtroumpf[Int] = $anon$1@c1b9b03

scala> implicitly[Schtroumpf[Int]]

Implicit search compares the two in-scope implicits in `isStrictlyMoreSpecific`,
which constructs an existential type:

type ET = Schtroumpf[U] forSome { type T; type U <: Coll[T]; type Coll[_] <: Traversable[_] }

A subsequent subtype check `ET <:< Schtroumpf[Int]` gets to `withTypeVars`, which
replaces the quantified types with type variables, checks conformance of that
substitued underlying type against `Schtroumpf[Int]`, and then tries to solve
the collected type constraints. The type var trace looks like:

[ create] ?T ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ create] ?U ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ create] ?Coll ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ setInst] Nothing ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], T=Nothing )
[ setInst] scala.collection.immutable.Nil.type( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], U=scala.collection.immutable.Nil.type )
[ setInst] =?scala.collection.immutable.Nil.type( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], Coll==?scala.collection.immutable.Nil.type )
[ create] ?T ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ setInst] Int ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], T=Int )
[ create] ?T ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ create] ?U ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ create] ?Coll ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]] )
[ setInst] Nothing ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], T=Nothing )
[ setInst] Int ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], U=Int )
[ setInst] =?Int ( In Test#schtroumpf[T,U <: Coll[T],Coll[_] <: Traversable[_]], Coll==?Int )

The problematic part is when `?Int` (the type var originated from `U`) is registered
as a lower bound for `Coll`. That happens in `solveOne`:

for (tparam2 <- tparams)
tparam2.info.bounds.hi.dealias match {
case TypeRef(_, `tparam`, _) =>
log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
tvar addLoBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
case _ =>
}

This commit changes `addHiBound` and `addLoBound` to discard non higher-kinded
bounds for higher-kinded type variables.

Review by @adriaanm

This is more of a review request than a pull request, I think more test cases are needed, and would appreciate your ideas there.

This didn't crash prior to c800d1fec (implicit search failure was correctly reported), but I don't know exactly why.