Type Class Derivation Does Not Work With Contravariant Types

[adamgfraser]

Compiler version

3.0.1

Minimized code

import scala.deriving.*
import scala.compiletime.{erasedValue, summonInline}

inline def summonAll[T <: Tuple]: List[Eq[_]] =
  inline erasedValue[T] match
    case _: EmptyTuple => Nil
    case _: (t *: ts) => summonInline[Eq[t]] :: summonAll[ts]

trait Eq[-T]:
  def eqv(x: T, y: T): Boolean

object Eq:
  given Eq[Int] with
    def eqv(x: Int, y: Int) = x == y

  def check(elem: Eq[_])(x: Any, y: Any): Boolean =
    elem.asInstanceOf[Eq[Any]].eqv(x, y)

  def iterator[T](p: T) = p.asInstanceOf[Product].productIterator

  def eqSum[T](s: Mirror.SumOf[T], elems: => List[Eq[_]]): Eq[T] =
    new Eq[T]:
      def eqv(x: T, y: T): Boolean =
        val ordx = s.ordinal(x)
        (s.ordinal(y) == ordx) && check(elems(ordx))(x, y)

  def eqProduct[T](p: Mirror.ProductOf[T], elems: => List[Eq[_]]): Eq[T] =
    new Eq[T]:
      def eqv(x: T, y: T): Boolean =
        iterator(x).zip(iterator(y)).zip(elems.iterator).forall {
          case ((x, y), elem) => check(elem)(x, y)
        }

  inline given derived[T](using m: Mirror.Of[T]): Eq[T] =
    lazy val elemInstances = summonAll[m.MirroredElemTypes]
    inline m match
      case s: Mirror.SumOf[T]     => eqSum(s, elemInstances)
      case p: Mirror.ProductOf[T] => eqProduct(p, elemInstances)
end Eq

enum Opt[+T] derives Eq:
  case Sm(t: T)
  case Nn

@main def test(): Unit =
  import Opt.*
  val eqoi = summon[Eq[Opt[Int]]]
  assert(eqoi.eqv(Sm(23), Sm(23)))
  assert(!eqoi.eqv(Sm(23), Sm(13)))
  assert(!eqoi.eqv(Sm(23), Nn))

Output

no implicit argument of type deriving.Mirror.Of[T] was found for parameter m of given instance derived in object Eq

where:    T is a type variable with constraint >: Opt[T]

Expectation

This example from the documentation does not work when Eq is contravariant instead of invariant.

[dwijnand]

Looks like (sadly) all of the various test variants for type class derivation all have their Eq as invariant. 😞 And they all fail when I changed them. But I did get run/typeclass-derivation1 passing with either of these fixes to LstEq:

@@ -28,12 +28,13 @@ object Deriving {
       def fromProduct(xs: EmptyTuple) = Lst.Nil
     }

-    implicit def LstEq[T: Eq]: Eq[Lst[T]] = Eq.derivedForSum
+  //implicit def LstEq[T: Eq]: Eq[Lst[T]] = Eq.derivedForSum[Lst[T], (Cons[T], Nil.type)]
+    implicit def LstEq[T: Eq]: Eq[Lst[T]] = Eq.derivedForSum(lstShape[T])
     implicit def ConsEq[T: Eq]: Eq[Cons[T]] = Eq.derivedForProduct
     implicit def NilEq[T]: Eq[Nil.type] = Eq.derivedForProduct
   }

-  trait Eq[T] {
+  trait Eq[-T] {
     def equals(x: T, y: T): Boolean
   }

Otherwise you get

32 |    implicit def LstEq[T: Eq]: Eq[Lst[T]] = Eq.derivedForSum(using lstShape)
   |                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                                     no implicit argument of type Deriving.Eq[Deriving.Lst.Cons[Any]] was found.
   |                                     I found:
   |
   |                                         Deriving.Lst.ConsEq[Any](/* missing */summon[Deriving.Eq[Any]])
   |
   |                                     But no implicit values were found that match type Deriving.Eq[Any].

So, at least for that test case, it seem seems a case of widening the type bound prematurely?

[soronpo]

Could it be the same incremental compilation widening bug that plagues opaque types #13128 ?

[nicolasstucki]

Minimized

trait Eq[-T]

object Eq:
  def derived[T](using m: scala.deriving.Mirror.Of[T]): Eq[T] = ???

enum Opt derives Eq:
  case Nn

or

...

enum Opt:
  case Nn
  def eq: Eq[Opt] = Eq.derived

Workarround

...

enum Opt:
  case Nn
  def eq: Eq[Opt] = Eq.derived[Opt]

[nicolasstucki]

This seems to be a limitation with type inference

[odersky]

I am not sure this is a bug. Eq is invariant anyway. If it does not work for contravariant then that could be just a limitation for type inference. If somebody has the time to work this out that would be great. But let's not spend bug fixing cycles on this.

[adamgfraser]

@odersky I'm not sure what you mean when you say "Eq is invariant anyway". Eq is not defined in the Scala standard library. It is defined as invariant in some libraries and is defined as contravariant in other libraries, for example here, along with a variety of other functional abstractions.

Furthermore, I would argue that this reflects the natural variance of this data type. It only accepts A values as inputs and never produces them. Covariance and contravariance are two sides of the same coin so seems like a significant limitation that it would work for one and not the other.

Would love to use this feature to support derivation of functional abstractions in ZIO Prelude if we can fix this.

[adamw]

@ghostbuster91 has the same problem with the Diff typeclass in diffx: https://github.com/softwaremill/diffx/blob/master/core/src/main/scala/com/softwaremill/diffx/Diff.scala

I think Eq is just an incidental example, not the motivating one :)

[adamgfraser]

That's a great point. Equal was the first one I ran into when I tried to implement derivation and I thought it would be a good motivating example because it was featured in the documentation so it was already relatively minimized. But this applies to any contravariant type class. So this would include Equal, Ord, Debug, Diff, JsonEncoder and encoders for any other data type.

[bertlebee]

In the docs here: https://docs.scala-lang.org/scala3/reference/contextual/derivation.html
A type class in this sense is any trait or class with a type parameter determining the type being operated on.

There's no mention of variance limitations in the documentation and I think @adamgfraser raises a great point about Eq being naturally contravariant.

From @dwijnand 's comments and lack of noting limitation (due to in the documentation, this looks like an accidental oversight, not a deliberate decision, so I'm pretty disappointed to see this changed to an "enhancement" rather than the bug that it very much seems to be.

[bishabosha]

This does not work if it is covariant either -

trait TC[+T]

object TC:
  def derived[T](using m: scala.deriving.Mirror.Of[T]): TC[T] = ???

enum Opt:
  case N

object Opt:
  def derived_TC: TC[Opt] = TC.derived

-- Error: ----------------------------------------------------------------------
9 |  def derived_TC: TC[Opt] = TC.derived
  |                                      ^
  |No given instance of type deriving.Mirror.Of[T] was found for parameter m of method derived in object TC
  |
  |where:    T is a type variable with constraint <: Opt
  |. Failed to synthesize an instance of type deriving.Mirror.Of[T]: 
  |	* class Any is not a generic product because it is not a case class
  |	* class Any is not a generic sum because it is not a sealed class
1 error found

you can trace the problem to Synthesizer which calls stripTypeVars on the mirrored type which fails because T is still uninstantiated.

If you avoid the need for synthesis then it works:

 trait TC[+T]

 object TC:
   def derived[T](using m: scala.deriving.Mirror.Of[T]): TC[T] = ???

 enum Opt:
   case N

 object Opt:
+  given [T]: scala.deriving.Mirror.Of[T] = ???
   def derived_TC: TC[Opt] = TC.derived

The problem seems to go away if we replace stripTypeVars with fullyDefinedType as all other synthesised type classes use - still to determine if this breaks other code.

---

Edit: on first try using fullyDefinedType the recursive invocation of summonAll seems to produce the same Eq.eqSum instance, causing an infinite loop in the generated eqv at runtime.

However this seems to be because in the recursive case Opt.derived$Eq is ok to reuse as an Eq[Opt.Sm[Int]] (due to the contravariance):

scala> summon[Eq[Opt[Int]] <:< Eq[Opt.Sm[Int]]]
val res0: Eq[Opt[Int]] =:= Eq[Opt[Int]] = generalized constraint

[bishabosha]

after a lot of experimentation I have come up with a good way to break the recursive implicit search, while being efficient with generated code:

/** `P` is supplied from `Eq.derived`, it is the outer sum/product */
inline def summonAll[P, T <: Tuple]: List[Eq[_]] =
  inline erasedValue[T] match
    case _: EmptyTuple => Nil
    case _: (t *: ts) => loopBreaker[P, t] :: summonAll[P, ts]

/** loopBreaker stops summoning a derived typeclass instance from inside its own definition
 *  @note aparently it needs to be defined separately from `summonAll` to avoid an infinite loop
 *  in inlining.
 */
inline def loopBreaker[P, T]: Eq[T] = compiletime.summonFrom {
  case infiniteRecursion: (T =:= P) => compiletime.error("cannot derive Eq, it will cause an infinite loop")
  case recursiveEvidence: (T <:< P) =>
    // summonInline will work because to get here `P` must also have a Mirror instance
    Eq.derived[T](using summonInline[Mirror.Of[T]])

  case existing: Eq[T] => existing
}

This means I can go ahead with a PR to fix the mirror synthesis