Dotty: Typeclass derivation of recursive types

[mpilquist]

The example Eq typeclass derivation fails on recursive types -- either in trying to reacquire a lazy val for directly recursive types (Rec below) or with a StackOverflow on mutual recursive types (Tree below).

minimized code

import scala.deriving._
import scala.compiletime._

inline def summon[T]: T = summonFrom { case t: T => t }

inline def summonAll[T <: Tuple]: List[Eq[_]] = inline erasedValue[T] match {
  case _: Unit => Nil
  case _: (t *: ts) => summon[Eq[t]] :: summonAll[ts]
}

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

object Eq {
  given Eq[Int] {
    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](given m: Mirror.Of[T]): Eq[T] = {
    val elemInstances = summonAll[m.MirroredElemTypes]
    inline m match {
      case s: Mirror.SumOf[T]     => eqSum(s, elemInstances)
      case p: Mirror.ProductOf[T] => eqProduct(p, elemInstances)
    }
  }
}

object Main extends App {

  case class Rec(x: Int, y: Option[Rec]) derives Eq
  println(summon[Eq[Rec]])
  /* Deriving Eq[Rec] hangs with stack like:
     java.lang.Thread.State: WAITING (on object monitor)
        at java.lang.Object.wait([email protected]/Native Method)
        - waiting on <0x00000007fd82c240> (a java.lang.Object)
        at java.lang.Object.wait([email protected]/Object.java:328)
        at dotty.runtime.LazyVals$.wait4Notification(LazyVals.scala:89)
        - waiting to re-lock in wait() <0x00000007fd82c240> (a java.lang.Object)
        at rs$line$1$Main$Rec$.derived$Eq(rs$line$1:59)
        at rs$line$1$Main$Rec$.derived$Eq(rs$line$1:8)
    */

  enum Tree[A] derives Eq {
    case Node[A](l: Tree[A], r: Tree[A]) extends Tree[A]
    case Leaf[A](value: A) extends Tree[A]
  }
  // Deriving Eq[Tree[Int]] throws SOE
  println(summon[Eq[Tree[Int]]])
}

Aside: the example defines derived as a given instead of a def but doing so seems to make the derives clause redundant / unnecessary.

[mpilquist]

Note: the implementation of Eq in typeclass-derivation3.scala works fine for recursive types. Maybe close this as won't fix and update the docs to use that implementation, along with a warning about directly summoning recursive instances?

[biboudis]

I will keep it a bit more open as I am currently investigating this. I think your original post reports a legit bug but thanks for reporting back Michael.

[kubukoz]

I have an example for a bit simpler type, hanging in runtime:

import scala.deriving.Mirror
import scala.compiletime.erasedValue
import scala.compiletime.summonInline
import scala.compiletime.summonFrom

object Derivations {
  inline def summonAll[T <: Tuple]: List[Print[_]] = inline erasedValue[T] match {
    case _: Unit => Nil
    case _: (t *: ts) => summonInline[Print[t]] :: summonAll[ts]
  }

  inline def gen[T](using m: Mirror.Of[T]): Print[T] = {
    val elems = summonAll[m.MirroredElemTypes]
    println("foo")

    _ => "bar"
  }
}

trait Print[T] {
  def (t: T).print: String
}

object Print {
  inline implicit def derived[T: Mirror.Of]: Print[T] = Derivations.gen[T]

  given Print[Int] = _.toString
}

enum MyList derives Print {
  case Cons(h: Int, t: MyList)
  case End
}

import Print.{given _}
@main
def run = println(MyList.Cons(1, MyList.Cons(2, MyList.End)).print)

(hangs between printing foo and printing bar)

[cb372]

Can anyone explain why the implementation @mpilquist linked does work for recursive types? It looks pretty similar to the example in the documentation, which doesn't work.

By the way, I worked around the problem by introducing a wrapper type so I could defer implicit resolution using =>. I'll leave it here just in case it helps anyone: https://github.com/cb372/type-class-derivation-in-scala-3/blob/1fe166ea13ce6ff09740311e47f72b655ca9b373/src/main/scala/mylibrary/Functor.scala#L67-L80

[dwijnand]

Can anyone explain why the implementation @mpilquist linked _does_ work for recursive types? It looks pretty similar to the example in the documentation, which doesn't work.

I think it's the summonFrom block that adds a level of delay/deferred-ness (by being a compile-time conditional I think). Replacing it with summonInline breaks things:

        if (ord == n) {
          val m = summonInline[Mirror.ProductOf[t]]
          eqlElems[m.MirroredElemTypes](0)(x.asInstanceOf[Product], y.asInstanceOf[Product])
          //summonFrom {
          //  case m: Mirror.ProductOf[`t`] => eqlElems[m.MirroredElemTypes](0)(x.asInstanceOf[Product], y.asInstanceOf[Product])
          //}
        } else eqlCases[ts](n + 1)(x, y, ord)

[error] -- Error: /d/play-json/play-json/shared/src/main/scala-3/play/api/libs/json/JsMacroImpl.scala:14:23
[error] 14 |  enum Lst[+T] derives Eq {
[error]    |                       ^
[error]    |cannot reduce inline match with
[error]    | scrutinee:  scala.compiletime.erasedValue[m.MirroredElemTypes] : m.MirroredElemTypes
[error]    | patterns :  case _:*:[t @ _, ts @ _]
[error]    |             case _:EmptyTuple
[error]    | This location contains code that was inlined from JsMacroImpl.scala:30
[error]    | This location contains code that was inlined from JsMacroImpl.scala:40
[error]    | This location contains code that was inlined from JsMacroImpl.scala:49