msgpack4zのcodecを自動導出する

個人的に作っているWebアプリで、せっかくなのであまり例のない「REST APIでメッセージ交換にmsgpackつかってみるやつ」をやっています。
軽く全体像を説明すると、サーバ側がRust、Webフロント側がScala.jsという趣味全開の構成をしたものになっています。

どちらの言語にもmsgpackのライブラリが存在するのでmsgpack自体を扱うことにそこまで苦労はないのですが、Rust側で使用している[rmp-serde](https://crates.io/crates/rmp-serde)のフォーマットとScala側で使用している[msgpack4z-core](https://github.com/msgpack4z/msgpack4z-core)で用意されているフォーマット（Codec）がいくつか違っていたりしてそのまま使用することができないという問題にぶち当たりました。
また、msgpack4z-coreにはいくつか標準的な型向けのCodecは存在しますが、自前で用意した型向けには都度型の構造に合わせたCodecインスタンスを用意する必要があります。さらに、Scala3以降のenum型（ADT）をそのまま扱えるCodecはライブラリには存在しません（見た限りでは）。

というわけで、Scala3のType Class Derivationの機能を活用して、rmp互換のCodecを`case class`および`enum`から自動導出するということをやりました。

:::note info

対象読者について

Scala 3で新たに導入されたusing/givenに関する話なので、これらのキーワードが前提知識となります。
ちょっとだけ他の言語がわかる人に平たく言うと、型クラスの使用およびインスタンス定義です。詳しくは[公式ドキュメント](https://docs.scala-lang.org/scala3/reference/contextual/index.html)などを読んで下さい。

:::

## rmpとmsgpack4zのフォーマットの違い

rmp（Rust MessagePack）とmsgpack4zはいくつか標準で提供しているフォーマットが異なります。

例えば、`Option<i32>`（`Option[Int]`）は以下のように異なるエンコーディング結果となります。

| 値 | rmp(json等価表記) | msgpack4z(json等価表記) |
|----|----|----|
| `None` | `null` | `{ "None": null }` |
| `Some(x)` | `x` | `{ "Some": x }` |

また、rmpではデフォルトでコンパクトなCodecを採用しています。これはどういうことかというと、構造体のフィールド名がなくなりタプルと等価の表現になったり、パラメータなしのenum variant（`enum case`）が単一の文字列と等価になったりします[^serde-enum-exttagged]。更に細かい話として、タプル構造体と通常の構造体でフィールドが1つ以下の場合のエンコーディングが**異なります**。
具体的にどう変化するかは次の表を参考にしてください。

```rust
#[derive(Serialize)]
pub struct Identified(i32);

#[derive(Serialize)]
pub struct Identified2 { pub id: i32 }

#[derive(Serialize)]
pub struct Template {
    pub a: i32,
    pub b: &'static str
}

#[derive(Serialize)]
pub enum Command {
    NoAction,
    Push(i32),
    Update(i32, i32)
}
```

| 値 | rmp(json等価表記) |
|----|----|
| `Identified(2)` | `2` |
| `Identified2 { id: 2 }` | `[2]` |
| `Template { a: 1, b: "test" }` | `[1, "test"]` |
| `Command::NoAction` | `"NoAction"` |
| `Command::Push(3)` | `{ "Push": 3 }` |
| `Command::Update(1, 2)` | `{ "Update": [1, 2] }` |

msgpack4zではどちらのフォーマットを採用するかが選べるので（Mapでしっかりやるなら`CaseMapCodec`、Arrayでいいなら`CaseCodec`）、どちらにするかは通信先と予め決めておく必要があります。

:::note info

例えば、rmp側は前述の通りArrayでエンコーディングしてくるので通信先がrmpを使っている場合は`CaseCodec`を使うことになります。

:::

## 目標とする形

最終的には次のような記述でmsgpackのエンコーディング（パッキング）/デコーディング（アンパッキング）を行えるようにすることを目指します。

```scala
final case class Template(
  val a: Int,
  val b: String
) derives MsgpackCodec

enum Command derives MsgpackCodec:
  case NoAction
  case Push(val value: Int)
  case Update(val index: Int, val newValue: Int)
```

## Scala 3のメタプログラミング

### givenインスタンスの自動生成（Type Class Derivation）

https://docs.scala-lang.org/scala3/reference/contextual/derivation.html

Scala 3では、型定義に`derives Trait`をつけることによってトレイト（型クラス）のgivenインスタンスを自動生成することができます。
内部仕様としては`Trait.derived`が呼び出されており、`derived`をトレイトのcompanion objectもしくは`Trait.type`のextensionに定義することで自作トレイトでも同じことができるようになります。

:::note warn

`derived`は`given`でも`inline def`でも定義できますが、`given`の場合は意図していないgivenインスタンスも生えることになってちょっとややこしいことになるので個人的には`inline def`での定義をおすすめします。

:::

`derived`の実装方法にはMirrorを使う方法とマクロを使う方法があります。今回はMirrorを使う方法で実装します。

### `inline def`と`inline match`

https://docs.scala-lang.org/scala3/reference/metaprogramming/inline.html

Scala 3には`inline`というキーワードがあり、D言語の`static if` `static foreach`みたいな感じでコンパイル時に計算される処理を記述できます。
たとえばジェネリック型に対する処理などは、コンパイル後には型変数は消去されてしまうので通常は記述できませんが、コンパイル時であればそのあたりの情報は残ったままなのでその情報を使った処理を記述することができます。

### Mirror

Scala 3には代数的データ型（`enum`および`case class`）の構造を表す情報として[`scala.deriving.Mirror`](https://dotty.epfl.ch/api/scala/deriving/Mirror.html)があり、これを使うことでコンパイル時に型の構造を得ることができます。

Scalaにおける、というより似たような型の概念を持つ言語であれば大半同じような話ですが、代数的データ型は大きく「**直積型**（Product）」と「**直和型**（Sum）」の2種類に分類されます。
直積型は平たく言うと構造体やタプルのことで、純粋にひとつの型で複数の値を同時に持つものです。
直和型は直積型が集合したような形をしていて、ひとつの型で複数の直積型データを並行して表現することができます。

```scala
// 直積型 ProductTypeという型でxとyのふたつの数値を保持できる
case class ProductType(val x: Int, val y: Int)
// 直和型 SumType型の値はSumType.Product1かSumType.Product2のどちらかになる
enum SumType:
  case Product1(x: Int, y: Int)
  case Product2(z: Int)
```

Scala 3ではコンパイル時にこういった型の構造を取得していろいろなことを行うことができて、今回のType Class Derivationもこの機能をつかうもののひとつになります。
`scala.deriving.Mirror`は`case class` `enum`および`enum case`のそれぞれひとつずつに対してコンパイラが自動で定義し、`Mirror.Of[T]`を`summonInline`するか`using`経由で取得できます。

## 実際にType Class Derivationを書いて自動導出する

ここまでで前提知識は揃ったので実際に`derived`を書いていきます。
中身はこれから作るとして、ひとまず全体像を把握するため外側の`derived`を仮定義します。対象型のMirrorを`using`で受け取り、`inline match`でProductの場合とSumの場合で分岐してそれぞれの構造用のCodecを生成するコードを書いていきます。

```scala
extension (c: MsgpackCodec.type)
  inline def derived[T](using m: Mirror.Of[T]): MsgpackCodec[T] = inline m match
    case p: Mirror.ProductOf[T] => ???
    case s: Mirror.SumOf[T] => ???
```

### 直積型のCodecを導出する

まずは簡単な直積型（Product）のcodecを導出してみます。今回はタプル構造体については考えずに通常の構造体の場合のみを考えます（アプリで通信層にタプル構造体をつかってないためです）。
Scala 3ではMirrorによって任意の`case class`とタプルを相互に変換することが可能なため、タプルのCodecを利用して導出する方法を取ります。

```scala
final case class ProductClass(
  val x: Int,
  val y: Double,
  val name: String
)

// ProductClassは以下のタプル型と相互変換できます
type ProductClassTuple = (Int, Double, String)
```

で、やることですが、「任意の型を別の型に変換することでmsgpackにできるCodec」がmsgpack4zにビルトインで提供されているので、直積型に関してはそれを使うだけで基本的におしまいです。

```scala
    case p: Mirror.ProductOf[T] =>
      MsgpackCodec.from[p.MirroredElemTypes, T](
        p fromProduct _.asInstanceOf[Product],
        x => Some(Tuple.fromProduct(x.asInstanceOf[Product]).asInstanceOf[p.MirroredElemTypes]),
      )
```

ここで、`Mirror.Product.MirroredElemTypes`が直積型の各フィールドの型のタプルとなっています。

変換できたのは良いのですが、msgpack4zにはジェネリックな`Tuple`の`CaseCodec`が存在しません。それは自前で用意します。

```scala
inline given [T <: Tuple]: MsgpackCodec[T] =
  val subcodecs = summonAll[Tuple.Map[T, MsgpackCodec]].toList.asInstanceOf[List[MsgpackCodec[?]]]
  MsgpackCodec.codecTry(
    (packer, x) =>
      packer packArrayHeader x.asInstanceOf[Product].productArity
      for (c, e) <- subcodecs zip x.asInstanceOf[Product].productIterator do c.pack(packer, e.asInstanceOf)
      packer.arrayEnd()
    ,
    unpacker =>
      val len = unpacker.unpackArrayHeader()
      val elements =
        if len >= subcodecs.length then for c <- subcodecs yield c.unpack(unpacker).throwLeft
        else throw NotEnoughArraySize(subcodecs.length, len)
      unpacker.arrayEnd()
      Tuple
        .fromProduct(new Product:
          def canEqual(that: Any): Boolean = true
          def productArity: Int = subcodecs.length
          def productElement(n: Int): Any = elements(n)
          override def productIterator: Iterator[Any] = elements.iterator
        )
        .asInstanceOf[T],
```

まず最初にタプルの要素のCodecをすべて用意します。タプルには型レベルMapが標準ライブラリで提供されているので、それを使って要素をそれぞれ`MsgpackCodec[T]`に変換して[`summonAll`](https://dotty.epfl.ch/api/scala/compiletime.html#summonAll-ffffff96)で一括でインスタンスを召喚します[^summon]。タプルのままでは取り回しづらいので`toList`でリストにします。
`MsgpackCodec.codecTry`はCodecをフルスクラッチで作成できるメソッドです。通常のCodecはアンパック時のエラーをscalazの`Either`（`\/`）型で返す必要がありますが、`MsgpackCodec.codecTry`はアンパック時の例外をうまくラップしてくれるので普通に例外が使えて便利です。
パッキングは今回は配列データとして行うので、配列ヘッダを出力→各要素を出力→配列フッタを出力、でOKです。タプルの各要素は`Product`を経由して[`Product.productIterator`](https://dotty.epfl.ch/api/scala/Product.html#productIterator-0)で取得できます。
アンパッキング時はデータの長さ判定が入っていますが概ねパッキング時の逆操作をしています。`for...yield`の出力は当たり前ですがタプルではないので、出力シーケンスを雑に`Product`に偽装して`Tuple.fromProduct`でタプル化します。

コード中にしれっと登場している`throwLeft`はいわゆる`Option.get`の`Either`版で、`Left`の場合は中身を例外として送出する補助関数です。
`.toEither.toTry.get`と書いても同じ挙動になりますが、2回変換が入るのとちょっと長ったらしいのでエイリアス的な形で用意しています。

```scala
extension [R, L <: Throwable](e: \/[L, R]) def throwLeft = e.fold(e => throw e, identity)
```

### 直和型のCodecを導出する

直積型のCodecは`MsgpackCodec.from`のおかげでほとんど説明することもないくらい簡単でしたが、直和型は少し厄介です。いきなり両方考えると大変なのでまずはパッキングの方から考えていきます。

#### パッキング処理

パッキングでは`enum case`の名前と内部の値を一要素のマップデータとしてパックします。ただし`enum case`がもつ値がない場合はただの文字列になります。これをそのまま実装しようとすると以下のようになります。

```scala
(packer, x) =>
  val name = ???
  val product = x.asInstanceOf[Product]
  if product.productArity == 0 then
    packer packString name
  else
    packer packMapHeader 1
    packer packString name
    ???
    packer.mapEnd()
```

:::note info

`enum case`は必ず`Product`のサブクラスになるので[^singleton-case]`asInstanceOf[Product]`キャストしてしまってOKです。

:::

さて、2つ未実装ポイントが残っています。

1. `x`はこの時点では`enum`型以外の何物でもなく、具体的にどの`enum case`が来るかは実行時にしかわからない。`enum case`の具体名を取得するにはMirrorが必要だが、`enum case`のMirrorをコンパイル時に召喚することができないので名前を取得することができない。
1. 上記と同じく、コンパイル時点では具体的な`enum case`がわからないのでCodecインスタンスを召喚することができず、パラメータのパッキング処理を書くことができない。

どちらも具体的な`enum case`のMirrorをコンパイル時に取得することができないことが原因となっています。
たしかに具体的な型をコンパイル時に取得することはできないわけですが、代わりに実行時には`enum case`の**序数**（ordinal）を入手することができます。そのため、コンパイル時にすべての`enum case`に対する各種情報をインデックス可能な形で生成しておくことで実行時に序数を使って具体的な`enum case`に合った各情報を利用することができます。

まず`enum case`の名前ですが、これは`enum case`自身のMirrorが持っているほか、親となる`enum`のMirrorがタプルとして持っています。この型`Mirror.Sum.MirroredElemLabels`は**依存型**とよばれるもので、型レベルで`enum case`のラベル名の文字列データをそのままもっています。

```scala
enum SumType:
  case Product1(x: Int, y: Int)
  case Product2(z: Int)
// これのMirrorは以下（一部）
new Mirror.Sum:
  type MirroredElemLabels = ("Product1", "Product2")
  ...
```

依存型のタプルから実際の値のタプルを生成するには[`scala.compiletime.constValueTuple`](https://dotty.epfl.ch/api/scala/compiletime.html#constValueTuple-ffffff96)を使います。また、本来はタプルに対して`apply`をすることでタプルの要素を取得することができるのですが、今回は文脈的にインライン展開されてしまうようで`constValueTuple`に対して引数適用しようとしてるとみなされてエラーになってしまうので`toList`でリストに変換します。ついでにうまく型計算を畳み込んでくれないので`List[String]`に型強制します。

```scala
val names = constValueTuple[s.MirroredElemLabels].toList.asInstanceOf[List[String]]
```

続いて`enum case`のCodecです。こちらは今回はタプル構造体の場合のみを考えます（例によってアプリ側でそれ以外使ってないからです）。
通常の構造体向けのCodecはそのまま使えないので別途Codecを用意します。

```scala
private inline def enumElementCodec[T](using p: Mirror.ProductOf[T]): MsgpackCodec[T] =
  inline erasedValue[p.MirroredElemTypes] match
    case _: EmptyTuple =>
      MsgpackCodec.codec(
        (_, _) => (),
        _ =>
          \/-(p.fromProduct(new Product:
            def canEqual(that: Any): Boolean = true
            def productArity: Int = 0
            def productElement(n: Int): Any = ???
          )),
      )
    case _: (t *: EmptyTuple) =>
      MsgpackCodec.from[t, T](
        x => p.fromProduct(Tuple1(x)),
        x => Some(x.asInstanceOf[Product].productElement(0).asInstanceOf[t]),
      )(
        summonInline[MsgpackCodec[t]]
      )
    case _: (t *: ts) =>
      MsgpackCodec.from[p.MirroredElemTypes, T](
        p fromProduct _,
        x => Some(Tuple.fromProduct(x.asInstanceOf[Product]).asInstanceOf[p.MirroredElemTypes]),
      )
```

それぞれ要素数が0, 1, 2以上の場合の処理になっています。
[`scala.compiletime.erasedValue`](https://dotty.epfl.ch/api/scala/compiletime.html#erasedValue-fffff7c4)は指定された型の消去された値を得る関数です。消去された値については詳しく説明ができないんですが、幽霊型の値版みたいな存在だと認識しています。実行時には存在せずコンパイル時にのみ存在する、かつ読み取りができない（具体的な値を持たない）値です。
`match`を使うには何かしらの値が必要があるので「値はつかわないけど型のマッチングだけしたい」場合に消去された値を仮の値として使うことができます。
要素数が0の場合はなにもしないCodecを、1の場合は最初の要素のCodecをそのまま使う形の定義を、2以上の場合は先に紹介したProductとおなじ定義となっています。

つづいてこれを`enum case`それぞれについて実体化させるのですが、ここでは地道に再帰関数を書いていきます。
本当は`Tuple`に`map`があるのでそれと`erasedValue`の組み合わせでいけるはず、つまり次のような形で書けるはずなんですが、謎のエラーが取れず[^any]安定しなかったので自前で書くことにしました。

```scala:ほんとうはうごくはず
inline def defineAllEnumElementCodecs[Ts <: Tuple]: List[MsgpackCodec[?]] =
  erasedValue[Ts].map { [t] => (_: t) => enumElementCodec[t](using summonInline[Mirror.ProductOf[t]]) }.toList.asInstanceOf
```

で、やりたいこととしては先のコードの通りただの`map`なのでそのままシンプルな再帰関数に分解します。

```scala
inline def defineAllEnumElementCodecs[Ts <: Tuple]: List[MsgpackCodec[?]] = inline erasedValue[Ts] match
  case _: EmptyTuple => Nil
  case _: (t *: ts)  => enumElementCodec(using summonInline[Mirror.ProductOf[t]]) :: defineAllEnumElementCodecs[ts]
```

ここまでくれば必要なものは揃ったので最初のコードの不足分を補ってパッキングは完成です。

```diff
+ val names = constValueTuple[s.MirroredElemLabels].toList.asInstanceOf[List[String]]
+ val allCodecs = defineAllEnumElementCodecs[s.MirroredElemTypes]
(packer, x) =>
-   val name = ???
+   val name = names(s ordinal x)
  val product = x.asInstanceOf[Product]
  if product.productArity == 0 then
    packer packString name
  else
    packer packMapHeader 1
    packer packString name
-     ???
+     allCodecs(s ordinal x).pack(packer, x.asInstanceOf)
    packer.mapEnd()
```

### アンパッキング処理

アンパッキングでは、`enum case`が持つ要素数が0かそうでないかで表現が変わるという点を考慮する必要がありますが、それ以外は現時点で揃っているもので簡単に構成できます。特に追加で説明するものもないのでコードから載せます。

```scala
unpacker =>
  unpacker.nextType() match
    case MsgType.STRING =>
      val name = unpacker.unpackString()
      val ordinal = names indexOf name
      if ordinal < 0 then throw Error(s"No variant named ${name} in enum")
      val e = allCodecs(ordinal).unpack(unpacker)
      e.throwLeft.asInstanceOf[T]
    case MsgType.MAP =>
      unpacker.unpackMapHeader()
      val name = unpacker.unpackString()
      val ordinal = names indexOf name
      if ordinal < 0 then throw Error(s"No variant named ${name} in enum")
      val et = allCodecs(ordinal).unpack(unpacker)
      val e = et.throwLeft
      unpacker.mapEnd()
      e.asInstanceOf[T]
    case _ => throw Error("invalid encoding of enum")
```

`unpacker.nextType()`で次に来る要素が何であるかを取得し、`String`（要素がない場合）か`Map`（要素がある場合）かで処理を分けています。
`enum case`の各要素は先のCodecを使ってそのままアンパッキングすればOKで、あとはそれをもとの`enum`型に強制しておしまいです。ただ先のコードで生成したCodecを使うには序数が必要なので`names`から探し出します。

:::note warn

今回は`enum case`の数が少ない（せいぜい20とか）ので雑に`indexOf`で線形検索していますが、50個とか100個とかになってきたら`Map`でインデックス作ったほうが良いかもしれないですね。

:::

これでSumに対するCodecを作ることができました。

### 全体

以上で当初の目的であった代数的データ型に対するCodecの自動導出プログラムができあがりました。
Mirrorを使うことでこうした型構造に依存したプログラムを書くことが可能になり、うまく使えば工数の大幅な節約ができます。
あとは型から値をつくるところなんかはちょっとしたパズルをやっている感覚で作っていてとても楽しかったです。
ただまあ一般的なコードとはちょっと違って、ありとあらゆる型の構造を考慮したりしないといけなくて若干複雑になるので何も考えず量産するとメンテ不能な怪物が出来上がる上に改修失敗するとプロジェクト全体に被害が及ぶのがこの手の自動生成プログラムの恐ろしいところでしょうか。まあでも適切な間隔で作ったりコメントや関数を駆使してメンテナンス性をある程度確保するようにすればよさそうですね（これは自動導出プログラムに限った話ではないですが）。

最後に全体を載せておしまいにします。

```scala
extension (c: MsgpackCodec.type)
  inline def derived[T](using m: Mirror.Of[T]): MsgpackCodec[T] = inline m match
    case p: Mirror.ProductOf[T] =>
      MsgpackCodec.from[p.MirroredElemTypes, T](
        p fromProduct _.asInstanceOf[Product],
        x => Some(Tuple.fromProduct(x.asInstanceOf[Product]).asInstanceOf[p.MirroredElemTypes]),
      )
    case s: Mirror.SumOf[T] =>
      val names = constValueTuple[s.MirroredElemLabels].toList.asInstanceOf[List[String]]
      val allCodecs = defineAllEnumElementCodecs[s.MirroredElemTypes]
      MsgpackCodec.codecTry(
        (packer, x) =>
          val name = names(s ordinal x)
          val product = x.asInstanceOf[Product]
          if product.productArity == 0 then
            packer packString name
          else
            packer packMapHeader 1
            packer packString name
            allCodecs(s ordinal x).pack(packer, x.asInstanceOf)
            packer.mapEnd()
        ,
        unpacker =>
          unpacker.nextType() match
            case MsgType.STRING =>
              val name = unpacker.unpackString()
              val ordinal = names indexOf name
              if ordinal < 0 then throw Error(s"No variant named ${name} in enum")
              val e = allCodecs(ordinal).unpack(unpacker)
              e.throwLeft.asInstanceOf[T]
            case MsgType.MAP =>
              unpacker.unpackMapHeader()
              val name = unpacker.unpackString()
              val ordinal = names indexOf name
              if ordinal < 0 then throw Error(s"No variant named ${name} in enum")
              val et = allCodecs(ordinal).unpack(unpacker)
              val e = et.throwLeft
              unpacker.mapEnd()
              e.asInstanceOf[T]
            case _ => throw Error("invalid encoding of enum"),
      )
```

[^serde-enum-exttagged]: ここではSerdeのデフォルト挙動である**Externally Tagged**を前提にして話します
[^singleton-case]: パラメータを持たない`enum case`は実は`Singleton`になるのですが、これは`Product`のサブトレイトなので同じように扱えます
[^any]: コンパイルメッセージいわく`t`が`Any`になっているようでした 推論がまだうまくいってない......？
[^summon]: これは完全に余談ですが、`given`インスタンスを取り出す操作を「召喚」って呼ぶのはだいぶ厨二心をくすぐられますね