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