Typeclass derivation from docs example results in stack overflow

[scalavision]

Minimized code

This is crashing in both 0.27 nightly and 0.26.1-RC. This seems to be because I've tested it using recursive types, i.e. the Tree example in the docs. The Opt example does not crash.

I tested the example explained here:

• https://dotty.epfl.ch/docs/reference/contextual/derivation.html

Test case that makes code crash in stack overflow:

val t1 = Branch(
     Leaf(1),
     Leaf(1)
    )
assert(eqTree.eqv(t1,t1))

copy / paste from the docs of Eq class for convienence:

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] {
    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]) as 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)
    }
  }
  
}

Output

This continues forever until it crash.

[error] (run-main-1) java.lang.StackOverflowError
[error] java.lang.StackOverflowError
[error]         at helpers.Tree$.derived$Eq(EqTest.scala:8)
[error]         at helpers.Tree$.derived$Eq(EqTest.scala:8)
[error]         at helpers.Tree$.derived$Eq(EqTest.scala:8)

In my own examples based on the docs also enters this kind of eternal loop.

Expectation

Should just work. I wonder if this is what makes the eternal loop?

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

So it might be that the docs are wrong. Is there another way of avoiding this ?

[liufengyun]

Thanks for the report @scalavision .

I played with the example, it seems we need some lazy & by-name tweaks to make it work:

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] {
    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]) as 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)
    }
  }
}

enum Tree[T] derives Eq {
  case Branch(left: Tree[T], right: Tree[T])
  case Leaf(elem: T)
}

@main
def Test = {
  import Tree._

  val t1 = Branch(Leaf(1), Leaf(1))
  assert(summon[Eq[Tree[Int]]].eqv(t1, t1))
}

Maybe Miles @milessabin knows better ways to do it?

[scalavision]

Thanks a lot :-) Should have thought about this, it's a lot to take in I guess. I'd like to add that I love the way scala 3 is evolving. It is already amazing to use!