diverging implicit expansion, regression between 2.13.0-M5 and RC1

[lrytz]

Minimized from https://github.com/akka/akka-http/issues/2515

package scala.io

import scala.annotation.unchecked.uncheckedVariance

sealed trait HList
final case class ::[+H, +T <: HList](head: H, tail: T) extends HList
sealed trait HNil extends HList {
  def ::[H](h: H) = new ::(h, this)
}
case object HNil extends HNil

trait CommonRules { this: Parser =>
  def day: Rule[HNil, Int :: HNil]
  def month: Rule[HNil, Int :: HNil]
  def digit2: Rule[HNil, Int :: HNil]

  def date2a = rule { day ~ '-' ~ month ~ '-' ~ digit2 ~> (y ⇒ if (y <= 69) y + 2000 else y + 1900) }
  def date2b = rule { day ~ '-' ~ month ~ '-' ~ (digit2 ~> (y ⇒ if (y <= 69) y + 2000 else y + 1900)) }
}

abstract class Parser {
  def rule[I <: HList, O <: HList](r: Rule[I, O]): Rule[I, O]
  type Rule0 = RuleN[HNil]
  type RuleN[+L <: HList] = Rule[HNil, L]

  implicit def ch(c: Char): Rule0 = ???

  implicit def rule2ActionOperator[I <: HList, O <: HList](r: Rule[I, O])(implicit ops: ActionOps[I, O]): ActionOperator[I, O, ops.Out] = ???
  sealed trait ActionOperator[I <: HList, O <: HList, Ops] {
    def ~> : Ops
  }
}

sealed trait TailSwitch[L <: HList, T <: HList, R <: HList] {
  type Out <: HList
}
object TailSwitch {
  implicit def tailSwitch[L <: HList, T <: HList, R <: HList, Out0 <: HList]
  (implicit ts: Aux[L, L, T, T, R, HNil, Out0]): TailSwitch[L, T, R] { type Out = Out0 } = ???

  sealed trait Aux[L <: HList, LI <: HList, T <: HList, TI <: HList, R <: HList, RI <: HList, Out <: HList]

  object Aux extends Aux1 {
    // if TI <: L then Out = R
    implicit def terminate1[L <: HList, LI <: HList, T <: HList, TI <: L, R <: HList, RI <: HList]:
    Aux[L, LI, T, TI, R, RI, R] = ???
  }

  abstract class Aux1 extends Aux2 {
    // if LI <: T then Out = RI.reverse ::: R
    implicit def terminate2[T <: HList, TI <: HList, L <: HList, LI <: T, R <: HList, RI <: HList, Out <: HList]
    (implicit rp: ReversePrepend.Aux[RI, R, Out]): Aux[L, LI, T, TI, R, RI, Out] = ???
  }

  abstract class Aux2 {
    implicit def iter1[L <: HList, T <: HList, TH, TT <: HList, R <: HList, RI <: HList, Out <: HList]
    (implicit next: Aux[L, HNil, T, TT, R, RI, Out]): Aux[L, HNil, T, TH :: TT, R, RI, Out] = ???

    implicit def iter2[L <: HList, LH, LT <: HList, T <: HList, R <: HList, RI <: HList, Out <: HList]
    (implicit next: Aux[L, LT, T, HNil, R, LH :: RI, Out]): Aux[L, LH :: LT, T, HNil, R, RI, Out] = ???
  }
}

trait DepFn1[T] {
  type Out
  def apply(t: T): Out
}

trait DepFn2[T, U] {
  type Out
  def apply(t: T, u: U): Out
}

trait Reverse[L <: HList] extends DepFn1[L] { type Out <: HList }

trait ReversePrepend[P <: HList, S <: HList] extends DepFn2[P, S] { type Out <: HList }

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

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] =
    new ReversePrepend[P, S] {
      type Out = S
      def apply(prefix: P, suffix: S) = suffix
    }

  implicit def hlistReversePrepend[PH, PT <: HList, S <: HList](implicit rpt: ReversePrepend[PT, PH :: S]): Aux[PH :: PT, S, rpt.Out] =
    new ReversePrepend[PH :: PT, S] {
      type Out = rpt.Out
      def apply(prefix: PH :: PT, suffix: S): Out = ???
    }
}

sealed class Rule[-I <: HList, +O <: HList] {
  def ~[I2 <: HList, O2 <: HList](that: Rule[I2, O2])(implicit
      i: TailSwitch[I2, O @uncheckedVariance, I @uncheckedVariance],
      o: TailSwitch[O @uncheckedVariance, I2, O2]): Rule[i.Out, o.Out] = ???
}

sealed trait ActionOps[I <: HList, O <: HList] { type Out }
object ActionOps {
  private type SJoin[I <: HList, O <: HList, R] = Join[I, HNil, O, R]

  implicit def ops1[II <: HList, A]: ActionOps[II, A :: HNil] { type Out = Ops1[II, A] } = ???
  sealed trait Ops1[II <: HList, A] {
    def apply[RR](f: (A) ⇒ RR)(implicit j: SJoin[II, HNil, RR], c: FCapture[(A) ⇒ RR]): Rule[j.In, j.Out]
  }

  implicit def ops3[II <: HList, A, B, C]: ActionOps[II, A :: B :: C :: HNil] { type Out = Ops3[II, A, B, C] } = ???
  sealed trait Ops3[II <: HList, A, B, C] {
    def apply[RR](f: (C) ⇒ RR)
      (implicit j: SJoin[II, A :: B :: HNil, RR],
          c: FCapture[(C) ⇒ RR]): Rule[j.In, j.Out]
  }
}

sealed trait FCapture[T]
object FCapture {
  implicit def apply[T]: FCapture[T] = ???
}

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 } = ???

  sealed trait Aux[I <: HList, L1 <: HList, L2 <: HList, R, Acc <: HList, In <: HList, Out <: HList]
  object Aux extends Aux1 {
    // 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] = ???

    // 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] = ???
  }
  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] = ???
  }
}

Compiles with 2.13.0-M5 (and 2.12), fails with RC1

../test/junit/scala/io/Pug.scala:18: error: diverging implicit expansion for type scala.io.ActionOps.SJoin[scala.io.HNil,Int :: Int :: scala.io.HNil,Int]
starting with method terminate in object Aux
  def date2a = rule { day ~ '-' ~ month ~ '-' ~ digit2 ~> (y ⇒ if (y <= 69) y + 2000 else y + 1900) }
                                                       ^
one error found

[lrytz]

Assigned to RC2, but can probably be done in 2.13.N? cc @adriaanm

[adriaanm]

Great, thanks for minimizing. I’ll bisect on Monday.

[adriaanm]

git bisect blames scala/scala@ae244bc6136f06d0c2b7f7592a2233b98c378a51

[adriaanm]

Hmm, this is a merge from 2.12 to 2.13, so it should also fail on latest 2.12. The change that triggers the error is a bugfix, so we can close this ticket I think.

Relevant part of the diff:

--- i/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ w/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -762,7 +762,8 @@ trait Implicits {
             case TypeRef(_, sym2, args2) if sym2 ne SingletonClass =>
               // The order of these two checks can be material for performance (scala/bug#8478)
               def isSubArg(tparam: Symbol, t1: Type, t2: Type) =
-                if (tparam.isCovariant) isPlausiblySubType(t1, t2) else isPlausiblySubType(t2, t1)
+                (!tparam.isContravariant || isPlausiblySubType(t2, t1)) &&
+                (!tparam.isCovariant || isPlausiblySubType(t1, t2))

[jrudolph]

so it should also fail on latest 2.12

FWIW, it doesn't fail on Scala 2.12.8, so it's still a change in behavior in 2.13.

Here's an even shorter minimization. It needs the rule wrapper (or the type ascription) in 2.12.8 to make it work. Otherwise, it fails with ~the same error~ a similar but not the same error as in 2.13.0-RC1.

object Test {
  def rule[I <: HList, O <: HList](r: (I, O)): (I, O) = ???

  val f: Ops3[HNil, Int, Int, Int] = null
  //f.apply[Int](identity): (HNil, Int :: Int :: Int :: HNil)
  rule { f(identity) }
}

sealed trait HList
final case class ::[+H, +T <: HList](head: H, tail: T) extends HList
sealed trait HNil extends HList {
  def ::[H](h: H) = new ::(h, this)
}
case object HNil extends HNil

sealed trait Ops3[II <: HList, A, B, C] {
  def apply[RR](f: (C) ⇒ RR)
               (implicit j: Join[II, HNil, A :: B :: HNil, RR]): (j.In, j.Out)
}

trait ReversePrepend[P <: HList, S <: HList] extends DepFn2[P, S] { type Out <: HList }

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

trait DepFn2[T, U] {
  type Out
  def apply(t: T, u: U): 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] =
    new ReversePrepend[P, S] {
      type Out = S
      def apply(prefix: P, suffix: S) = suffix
    }

  implicit def hlistReversePrepend[PH, PT <: HList, S <: HList](implicit rpt: ReversePrepend[PT, PH :: S]): Aux[PH :: PT, S, rpt.Out] =
    new ReversePrepend[PH :: PT, S] {
      type Out = rpt.Out
      def apply(prefix: PH :: PT, suffix: S): Out = ???
    }
}

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 } = ???

  sealed trait Aux[I <: HList, L1 <: HList, L2 <: HList, R, Acc <: HList, In <: HList, Out <: HList]
  object Aux extends Aux1 {
    // 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] = ???

    // 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] = ???
  }
  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] = ???
  }
}

[jrudolph]

so it should also fail on latest 2.12

FWIW, it doesn't fail on Scala 2.12.8, so it's still a change in behavior in 2.13.

git bisect blames scala/scala@ae244bc

Just to be clear, the change that was merged into 2.13 seems to be https://github.com/scala/scala/commit/014facccbef9127f0170910b71280064ac308a65 which has already been in Scala 2.12.7.

Anyway, it seems even the working case in 2.12 is already super brittle when you play around with the reproducer you can easily get into similar issue with seemingly insignificant changes. So, I'd say this seems to be rather an edge case that maybe doesn't need further investigation if this is the only occurrence so far.

[adriaanm]

Thanks. Sounds like it's some kind of multiple issues coming together. So, it still compiles under 2.13.x scalac -Xsource:2.12, but the bug doesn't repro on 2.12.x scalac -Xsource:2.13.

[joroKr21]

It would be nice to explain what Join is supposed to do. Trying to manually convince oneself whether the example should compile or not is very difficult :smile:

[jrudolph]

It would be nice to explain what Join is supposed to do. Trying to manually convince oneself whether the example should compile or not is very difficult

Join is type-class machinery to join to HLists. In that example, the idea is that day ~ '-' ~ month ~ '-' ~ digit2 is a Rule[Int :: Int :: Int :: HNil] and ~> transforms the last of those values to a potentially new HList which then needs to be appended to the remaining front part of the HList. The intention is that it should compile (and that example is only a minimization of a whole set of like-wise parsers which still compile correctly).

Checking if the definition of Join itself is correct or just finding an example where Join fails in an isolated fashion would probably help :)

[joroKr21]

Do you mean relational Join? Shapeless already has a typeclass to prepend to an HList. It's also unclear why In is a type member. Usually dependent functions take the the arguments as type parameters and the output type is a type member.

[jrudolph]

The type-classes are part of parboiled2, you can look at the original code that has a bit more documentation here:

https://github.com/akka/akka-http/blob/df401f15b114919b53b5b0f0d6b6a52a0eb9d7d6/akka-parsing/src/main/scala/akka/parboiled2/support/ActionOpsSupport.scala#L36-L79

Anyway, it's pretty unlikely that it's completely wrong because it works in general (and afaik so far we haven't found a reproducer that fails on Join in isolation).