Implicit search breaking with covariant/contravariant parameters

[OlivierBlanvillain]

Edit: The last test case still breaks with covariant type parameter (but passes without)

---

Below are 3 test cases showing the implicit search breaking at a certain depth. The first is non recursive:

trait Step0
trait Step1
trait Step2
trait Step3
trait Step4
trait Step5

object Steps {
  implicit val Step0: Step0 = new Step0 {}
  implicit def Step1(implicit p: Step0): Step1 = new Step1 {}
  implicit def Step2(implicit p: Step1): Step2 = new Step2 {}
  implicit def Step3(implicit p: Step2): Step3 = new Step3 {}
  implicit def Step4(implicit p: Step3): Step4 = new Step4 {}
  implicit def Step5(implicit p: Step4): Step5 = new Step5 {}
}

object StepsTest {
  import Steps._

  implicitly[Step0]
  implicitly[Step1]
  implicitly[Step2]
  implicitly[Step3]
  implicitly[Step4]
  // Breaks here
  // implicitly[Step5]
}

Similar example with Nats:

sealed trait Nat
sealed trait Succ[P <: Nat] extends Nat
sealed trait Zero extends Nat

case class ToInt[N <: Nat](value: Int)

object ToInt {
  implicit val caseZero: ToInt[Zero] = ToInt(0)
  implicit def caseSucc[P <: Nat](implicit e: ToInt[P]): ToInt[Succ[P]] = ToInt(e.value + 1)
}

object NatTest {
  def main(args: Array[String]): Unit = {
    assert(implicitly[ToInt[Zero]].value == 0)
    assert(implicitly[ToInt[Succ[Zero]]].value == 1)
    assert(implicitly[ToInt[Succ[Succ[Zero]]]].value == 2)
    assert(implicitly[ToInt[Succ[Succ[Succ[Zero]]]]].value == 3)
    assert(implicitly[ToInt[Succ[Succ[Succ[Succ[Zero]]]]]].value == 4)
    // Breaks here
    // assert(implicitly[ToInt[Succ[Succ[Succ[Succ[Succ[Zero]]]]]]].value == 5)
  }
}

Seams to happen sooner with HLists:

sealed trait HList
sealed trait HNil extends HList
sealed trait ::[+H, +T <: HList] extends HList

case class Size[L <: HList](value: Int)

object Size {
  implicit val caseHNil: Size[HNil] = Size(0)
  implicit def caseHCons[H, T <: HList](implicit e: Size[T]): Size[H :: T] = Size(e.value + 1)
}

object HListTest {
  def main(args: Array[String]): Unit = {
    assert(implicitly[Size[HNil]].value == 0)
    assert(implicitly[Size[Int :: HNil]].value == 1)
    assert(implicitly[Size[Int :: Int :: HNil]].value == 2)
    // Breaks here
    // assert(implicitly[Size[Int :: Int :: Int :: HNil]].value == 3)
  }
}

[felixmulder]

Only partially fixed by fe09615