regression: implicit divergence reported for parboiled2 + shapeless: implicit search not pruned eagerly enough by bounds?

[scabug]

First pass at a minimization from 78974e6241b8f4498c7ae2669fc406947282a660 in https://github.com/sirthias/parboiled2/tree/wip/scala-2.11-possible-regression

object Test {
  import ParboiledLite._
  implicitly[RunResult[String => Unit]]
}

object ParboiledLite {
  trait HList
  final case class ::[+H, +T <: HList](head : H, tail : T) extends HList
  trait HNil extends HList
   trait ReversePrepend[P <: HList, S <: HList] extends DepFn2[P, S] { type Out <: HList }
  trait DepFn2[A, B]

  trait LowPriorityReversePrepend {
    type Aux[P <: HList, S <: HList, Out0 <: HList] = ReversePrepend[P, S] { type Out = Out0 }

    implicit def hnilReversePrepend0[P <: HList, S <: HNil]
      (implicit rv: Reverse[P]): Aux[P, S, rv.Out] = ???
  }
  trait Reverse[T] { type Out }
  object ReversePrepend extends LowPriorityReversePrepend {
    def apply[P <: HList, S <: HList](implicit prepend: ReversePrepend[P, S]): Aux[P, S, prepend.Out] = prepend

    implicit def hnilReversePrepend1[P <: HNil, S <: HList]: Aux[P, S, S] = ???

    implicit def hlistReversePrepend[PH, PT <: HList, S <: HList]
      (implicit rpt : ReversePrepend[PT, PH :: S]): Aux[PH :: PT, S, rpt.Out] = ???
  } 

  // import org.parboiled2.{Rule0, Rule, RuleX}
  sealed trait RuleX
  sealed class Rule[-I <: HList, +O <: HList] extends RuleX
  type RuleN[L <: HList] = Rule[HNil, L]
  type Rule0 = RuleN[HNil]

  def `n/a` = ???
  sealed trait RunResult[T] {
    type Out <: RuleX
  }

  object RunResult {
    implicit def fromAux[T, Out0 <: RuleX](implicit aux: Aux[T, Out0]): RunResult[T] { type Out = Out0 } = `n/a`

    sealed trait Aux[T, Out]
    object Aux extends Aux1 {
      implicit def forRule[R <: RuleX]: Aux[R, R] = `n/a`
      implicit def forFHList[I <: HList, R, In0 <: HList, Out0 <: HList](implicit x: JA[I, R, In0, Out0]): Aux[I ⇒ R, Rule[In0, Out0]] = `n/a`
    }
    abstract class Aux1 extends Aux2 {
      implicit def forF1[Z, R, In0 <: HList, Out0 <: HList](implicit x: JA[Z :: HNil, R, In0, Out0]): Aux[Z ⇒ R, Rule[In0, Out0]] = `n/a`
      implicit def forF2[Y, Z, R, In0 <: HList, Out0 <: HList](implicit x: JA[Y :: Z :: HNil, R, In0, Out0]): Aux[(Y, Z) ⇒ R, Rule[In0, Out0]] = `n/a`
      implicit def forF3[X, Y, Z, R, In0 <: HList, Out0 <: HList](implicit x: JA[X :: Y :: Z :: HNil, R, In0, Out0]): Aux[(X, Y, Z) ⇒ R, Rule[In0, Out0]] = `n/a`
      implicit def forF4[W, X, Y, Z, R, In0 <: HList, Out0 <: HList](implicit x: JA[W :: X :: Y :: Z :: HNil, R, In0, Out0]): Aux[(W, X, Y, Z) ⇒ R, Rule[In0, Out0]] = `n/a`
      implicit def forF5[V, W, X, Y, Z, R, In0 <: HList, Out0 <: HList](implicit x: JA[V :: W :: X :: Y :: Z :: HNil, R, In0, Out0]): Aux[(V, W, X, Y, Z) ⇒ R, Rule[In0, Out0]] = `n/a`
    }

    abstract class Aux2 {
      protected type JA[I <: HList, R, In0 <: HList, Out0 <: HList] = Join.Aux[I, HNil, HNil, R, HNil, In0, Out0]
      implicit def forAny[T]: Aux[T, Rule0] = `n/a`
    }
  }

  sealed trait Join[I <: HList, L1 <: HList, L2 <: HList, R] {
    type In <: HList
    type Out <: HList
  }
  object Join {
    implicit def join[I <: HList, L1 <: HList, L2 <: HList, R, In0 <: HList, Out0 <: HList]
    (implicit x: Aux[I, L1, L2, R, HNil, In0, Out0]): Join[I, L1, L2, R] { type In = In0; type Out = Out0 } = `n/a`
    
    sealed trait Aux[I <: HList, L1 <: HList, L2 <: HList, R, Acc <: HList, In <: HList, Out <: HList]
    object Aux extends Aux1 {
      // if R == Unit convert to HNil
      implicit def forUnit[I <: HList, L1 <: HList, L2 <: HList, Acc <: HList, Out <: HList]
      (implicit x: Aux[I, L1, L2, HNil, Acc, I, Out]): Aux[I, L1, L2, Unit, Acc, I, Out] = `n/a`

      // if R <: HList and L1 non-empty move head of L1 to Acc
      implicit def iter1[I <: HList, H, T <: HList, L2 <: HList, R <: HList, Acc <: HList, Out <: HList]
      (implicit x: Aux[I, T, L2, R, H :: Acc, I, Out]): Aux[I, H :: T, L2, R, Acc, I, Out] = `n/a`

      // if R <: HList and L1 empty and L2 non-empty move head of L2 to Acc
      implicit def iter2[I <: HList, H, T <: HList, R <: HList, Acc <: HList, Out <: HList]
      (implicit x: Aux[I, HNil, T, R, H :: Acc, I, Out]): Aux[I, HNil, H :: T, R, Acc, I, Out] = `n/a`

      // if R <: HList and L1 and L2 empty set Out = reversePrepend Acc before R
      implicit def terminate[I <: HList, R <: HList, Acc <: HList, Out <: HList](implicit x: ReversePrepend.Aux[Acc, R, Out]): Aux[I, HNil, HNil, R, Acc, I, Out] = `n/a`

      // if R <: Rule and L1 non-empty move head of L1 to Acc
      implicit def iterRule1[I <: HList, L2 <: HList, I2 <: HList, O2 <: HList, In0 <: HList, Acc <: HList, Out0 <: HList, H, T <: HList]
      (implicit x: Aux[I, T, L2, Rule[I2, O2], H :: Acc, In0, Out0]): Aux[I, H :: T, L2, Rule[I2, O2], HNil, In0, Out0] = `n/a`

      // if R <: Rule and L1 empty and Acc non-empty move head of Acc to L2
      implicit def iterRule2[I <: HList, L2 <: HList, I2 <: HList, O2 <: HList, In0 <: HList, Out0 <: HList, H, T <: HList]
      (implicit x: Aux[I, HNil, H :: L2, Rule[I2, O2], T, In0, Out0]): Aux[I, HNil, L2, Rule[I2, O2], H :: T, In0, Out0] = `n/a`
    }
    abstract class Aux1 {
      // convert R to R :: HNil
      implicit def forAny[I <: HList, L1 <: HList, L2 <: HList, R, Acc <: HList, Out <: HList](implicit x: Aux[I, L1, L2, R :: HNil, Acc, I, Out]): Aux[I, L1, L2, R, Acc, I, Out] = `n/a`
    }
  }
}

Compiles in 2.10.4 but reports divergence in 2.11.0. I think the root problem exists in both versions and was unmasked by Hubert's fix to implicit divergence suppression in 2.11.

I've got some WIP on the compiler side here: https://github.com/retronym/scala/tree/ticket/8460-3

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-8545?orig=1 Reporter: @retronym Affected Versions: 2.11.0

[scabug]

@adriaanm said: Labelling as "language-change" to indicate it could break source compatibility.

[SethTisue]

Scala 3.4.0-RC2 says

-- [E057] Type Mismatch Error: -------------------------------------------------
17 |      (implicit rv: Reverse[P]): Aux[P, S, rv.Out] = ???
   |                                              ^
   |Type argument rv.Out does not conform to upper bound ParboiledLite.HList

[joroKr21]

If you add the bound it works on Scala 3.1.1 - but of course there is no Shapeless 2 for Scala 3