Deriving Ordering in Scala 3, slow and fast versions

deriving-order.scala

//> using scala 3.4.0

package bla

import scala.deriving.*, scala.compiletime.*

// change this to FASTER to go brrr
import EVEN_FASTER_SOMETIMES.*

// MAGIC
case class Date(year: Int, month: Int, day: Int) derives Ordering
case class Yo(x: String, o: Option[Int]) derives Ordering

@main def hello =
  println(List(Date(2024, 1, 1), Date(2021, 12, 1)).sorted)
  println(List(Yo("hello", None), Yo("a", Some(25)), Yo("a", Some(10))).sorted)

// THE DIRT THAT POWERS THE MAGIC

object SLOW:
  inline def tuplify[Cur <: Tuple](inline x: Product, n: Int): Tuple =
    inline erasedValue[Cur] match
      case _: EmptyTuple => Tuple()
      case _: (tpe *: rest) =>
        x.productElement(n) *: tuplify[rest](x, n + 1)

  private inline def deriveProduct[T](p: Mirror.ProductOf[T]): Ordering[T] =
    val tupleOrdering = summonInline[Ordering[p.MirroredElemTypes]]

    scala.math.Ordering.by[T, p.MirroredElemTypes](cls =>
      tuplify[p.MirroredElemTypes](cls.asInstanceOf[Product], 0).asInstanceOf
    )(using tupleOrdering)

  extension (o: Ordering.type)
    inline def derived[T](using m: Mirror.Of[T]): Ordering[T] =
      inline m match
        case p: Mirror.ProductOf[T] => deriveProduct(p)

// MORE EFFICIENT IMPLEMENTATION
object FASTER:
  private inline def lessThan[Cur <: Tuple](
      inline x: Product,
      inline y: Product,
      n: Int
  ): Boolean =
    inline erasedValue[Cur] match
      case _: EmptyTuple => false
      case _: (tpe *: rest) =>
        summonInline[Ordering[tpe]]
          .asInstanceOf[Ordering[Any]]
          .lt(x.productElement(n), y.productElement(n)) ||
        lessThan[rest](
          x,
          y,
          n + 1
        )
  end lessThan

  private inline def deriveProduct[T](
      p: Mirror.ProductOf[T]
  ): Ordering[T] =
    Ordering
      .fromLessThan((x, y) =>
        lessThan[p.MirroredElemTypes](
          x.asInstanceOf[Product],
          y.asInstanceOf[Product],
          0
        )
      )
      .asInstanceOf

  extension (o: Ordering.type)
    inline def derived[T](using m: Mirror.Of[T]): Ordering[T] =
      inline m match
        case p: Mirror.ProductOf[T] => deriveProduct(p)

object EVEN_FASTER_SOMETIMES:
  private inline def lessThan[Cur <: Tuple](
      inline x: Product,
      inline y: Product,
      n: Int
  ): Boolean =
    inline erasedValue[Cur] match
      case _: EmptyTuple => false

      case _: (Int *: rest) =>
        x.productElement(n).asInstanceOf[Int] < y
          .productElement(n)
          .asInstanceOf[Int] ||
        lessThan[rest](x, y, n + 1)

      case _: (Double *: rest) =>
        x.productElement(n).asInstanceOf[Double] < y
          .productElement(n)
          .asInstanceOf[Double] ||
        lessThan[rest](x, y, n + 1)

      case _: (tpe *: rest) =>
        summonInline[Ordering[tpe]]
          .asInstanceOf[Ordering[Any]]
          .lt(x.productElement(n), y.productElement(n)) ||
        lessThan[rest](
          x,
          y,
          n + 1
        )
  end lessThan

  private inline def deriveProduct[T](
      p: Mirror.ProductOf[T]
  ): Ordering[T] =
    Ordering
      .fromLessThan((x, y) =>
        lessThan[p.MirroredElemTypes](
          x.asInstanceOf[Product],
          y.asInstanceOf[Product],
          0
        )
      )
      .asInstanceOf

  extension (o: Ordering.type)
    inline def derived[T](using m: Mirror.Of[T]): Ordering[T] =
      inline m match
        case p: Mirror.ProductOf[T] => deriveProduct(p)