circeのgeneric encoderはどこからくるの？

とある人のとあるツイートが目に入り、twitterのリプライでは語りきれないと思ったのでQittaで説明記事を書いてみる
https://twitter.com/hakukotsu/status/1171469303247335429

## Circe
https://circe.github.io/circe/
scalaのJSONライブラリのひとつです
関数型のエッセンスを取り入れていたり、後述するジェネリックプログラミング(とマクロ)を利用したEncoder/Decoderの自動導出が特徴的です


## ジェネリックプログラミング
(僕自身この言葉についてあまり詳しくないので正しい説明はではないかもしれません、指摘頂ければ修正します)
プログラミングにおいて"ジェネリック"というとJavaやTypescriptにある型の抽象化機能が思い浮かびますよね、Scalaでは型クラスと呼ばれていますね
今回の文脈であげているジェネリックプログラミングも型を抽象化して扱う、という意味では同じです
ジェネリックスと大きく違うのは、ジェネリックスの場合はサブタイピングによって抽象型を表現します( `T <: SuperClass` のような)が
ジェネリックプログラミングでは型の特徴を元に抽象化します
例えば、以下の二つはFieldの型と定義順という特徴では同一と見なせます

```scala
case class Human(name: String, age: Int)
case class Apartment(address: String, age: Int)

// キー名やclass名は違うがどちらも [String, Int]の順で定義されている
```

### Shapeless
scalaでジェネリックプログラミングを行うためのライブラリです
詳しい扱い方については以下の記事が参考になりました
https://qiita.com/ryoppy/items/476467a4b709f011fb8f

この項目では説明に必要な部分のみ説明させていただきます

#### HList
型付きの値の列を表した型です
イメージとしては結合可能なTupleといった感じです
終端値として `HNil` が存在しており、`HNil` 自身も `HList` 型です
`Generic` を使うことで任意の `case class` を `HList` に変換できます

```scala
import shapeless._

Generic[Human].to(Human("moemoe", 12))
// => res1: String :: Int :: shapeless.HNil = moemoe :: 12 :: HNil

Generic[Apartment].to(Apartment("hdmr", 20))
// => res2: String :: Int :: shapeless.HNil = hdmr :: 20 :: HNil
```

同じ型になりましたね、これで二つの値はひとつの関数で扱うことができます

#### LabelledGeneric
また `LabelledGeneric` を使うことで型情報にキーを含んだHListに変換することができます
これもCirceのコード内で使用されています

```scala
scala> LabelledGeneric[Human].to(Human("moemoe", 12))
res1: String with shapeless.labelled.KeyTag[Symbol with shapeless.tag.Tagged[String("name")],String] :: Int with shapeless.labelled.KeyTag[Symbol with shapeless.tag.Tagged[String("age")],Int] :: shapeless.HNil = moemoe :: 12 :: HNil

```

### ジェネリックプログラミングについての補足

https://ja.wikipedia.org/wiki/%E3%82%B8%E3%82%A7%E3%83%8D%E3%83%AA%E3%83%83%E3%82%AF%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
wiki調べですがジェネリックスを使った言語機能もジェネリックプログラミングと呼んでも良さそうな感じがします、ただし、今回の文脈でジェネリックプログラミングと称したときはジェネリックスのことは含まない、とさせていただきます

## Auto Derivation
https://circe.github.io/circe/codecs/auto-derivation.html
circeは `implicit class`, `implicit parameter`, マクロ, ジェネリックプログラミングを使って未定義case classに対してJSON Encoder/Decoderを自動導出してくれます
具体的なフローは

(1). `case class` 定義
(2). shaplessのジェネリック型(HList)
(3). case classのFieldの値ごとのEncoder取得
(4). 取得したエンコーダとHListに含まれるField名の情報から `case class` のエンコーダを作成

といったような感じです、さぁ実際にコード追いながら見てみましょう

## コードリーディング
### [EncoderOps](https://github.com/circe/circe/blob/master/modules/core/shared/src/main/scala/io/circe/syntax/package.scala#L7-L11)
このコードリーディングの出発点です
ある任意の方 `A` をWrapし、JsonObject型へ変換する `asJsonObject` 型を持ちます
制限のない型 `A` に対する `implicit class` なので全ての型に対して適用することができます
`asJsonObject` は `implicit parameter`  `Encoder.AsObject[A]` を受け取ります

### [Encoder.AsObject[A]](https://github.com/circe/circe/blob/master/modules/core/shared/src/main/scala/io/circe/Encoder.scala#L843-L866) 
関数 `encodeObject(a: A): JsonObject` のみを未定義とした `trait` です
各型 `A` を `JsonObject` 型に変換するための責務を持ちます
最終的には定義した `case class X` に対する `Encoder.AsObject[X]` の具象型見つけるのが主目的となります（主題の `generic encoder` とはまさにこいつのことです）
最終的には `Encoder.AsObject[X]` の具象型はマクロによって生成されます
そのマクロを見つけるために `implicit` を追いましょう

### [Encoder.AsObject *companion](https://github.com/circe/circe/blob/dd346ae4d4f81e0472d6e2079c8e794a8cfd1e21/modules/core/shared/src/main/scala/io/circe/Encoder.scala#L882-L918)
[例のコード](https://circe.github.io/circe/codecs/auto-derivation.html)のimportでは `Encoder.AsObject[A]` のimplicit値は見つかりません
implicitの探査は対象 `implicit parameter` 型のコンパニオンオブジェンクトに及び、そのスーパークラスにてやっと見つかります
[importedAsObjectEncoder[A]](https://github.com/circe/circe/blob/dd346ae4d4f81e0472d6e2079c8e794a8cfd1e21/modules/core/shared/src/main/scala/io/circe/Encoder.scala#L913-L916) が `Exported[AsObject[A]]` を受け取り `AsObject[A]` を返す中継者として存在しておりimplicitの探査は `Exported[AsObject[A]]` へとバトンタッチされます
`Exported[AsObject[A]]` はimportされている [io.circe.generic.auto._](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/auto/package.scala) より [AutoDerivation](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/AutoDerivation.scala#L19) classにたどり着き、`exportEncoder[A]` 関数により `Exported[Encoder.AsObject[A]]` を得ることができます
`exportEncoder[A]` の実装はマクロになります
このとき、`ExportMacros.exportEncoder` には型引数 `DerivedAsObjectEncoder` を渡していることを記憶しておいてください、実はこの `DerivedAsObjectEncoder` の匿名サブクラスが `Encoder.AsObject[A]` の具象型となります

### [ExportMacros.exportEncoder[DerivedAsObjectEncoder, A]](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/ExportMacros.scala#L28-L43)
マクロ実装です、`E[_]` `A` ふたつの型情報を受け取り、[E[A]](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/ExportMacros.scala#L33) 型の[implicitパラメータ](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/ExportMacros.scala#L35-L41)を引っ張ってくる実装です、対象のimplicitパラメータが存在していない場合は `Context#typecheck` 関数にてEmptyTreeが帰り、エラーになります(詳細にいうと、型 `A` に対するジェネリック型 `R` が見つからない場合にエラーになります)

[shapeless.lazily](https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/lazy.scala#L141-L143)についてはimplicitをうまく解決してくれるためのWrapperのようなもの、だと認識していただければ十分です(僕も詳しくは理解してないので説明できない、というのが本音ですが)

実際に取ってくる `E[A]` 型について今回のコードでは型引数 `E` には `DerivedAsObjectEncoder` を渡しているので `DerivedAsObjectEncoder[A]` 型になります
`DerivedAsObjectEncoder[A]` のimplicit値はコンパニオンオブジェクト `DerivedAsObjectEncoder` にて定義されています

### [DerivedAsObjectEncoder *companion](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/encoding/DerivedAsObjectEncoder.scala#L9-L13)
implicit def `deriveEncoder` では２つのimplicitパラメータを受け取ります
`LabelledGeneric.Aux[A, R]` は対象の型 `A` にたいするジェネリック型(HList) `R` が存在する場合に取得できる型です、つまり `A` と `R` を紐付けます
`A` と `R` の関係性の例は

```scala
// A =
case class Human(name: String, age: Int)
//の場合
// R =
String with shapeless.labelled.KeyTag[Symbol with shapeless.tag.Tagged[String("name")],String] :: Int with shapeless.labelled.KeyTag[Symbol with shapeless.tag.Tagged[String("age")],Int] :: shapeless.HNil
// となります
```
`LabelledGeneric[A]` のサモナーで取ってきたインスタンスと同じ型ですね

`Lazy[ReprAsObjectEncoder[R]]`
[Lazy](https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/lazy.scala#L113-L139) は implicit解決のためのもの、今回のコードをコンパイラを意識しなければ `ReprAsObjectEncoder[R]` だと思って頂いて大丈夫だと思います
`ReprAsObjectEncoder[R]` コンパニオンオブジェクト `ReprAsObjectEncoder` より取得されます

関数bodyでは `DerivedAsObjectEncoder` の匿名サブクラスを作成しています
`DerivedAsObjectEncoder#encodeObject` の実装では２つのimplicitパラメータからJsonObjectを作成しています、具体的にいうとジェネリック型 `R` へ変換後、それのEncoderを介してJsonObjectを生成しています

### [ReprAsObjectEncoder * companion](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/encoding/ReprAsObjectEncoder.scala#L14-L16)
`deriveReprAsObjectEncoder` はジェネリック型 `R` のEncoderを取得するマクロ関数です

### Deriver.{ [deriveEncoder[R]](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/Deriver.scala#L21) | [constructEncoder[R]](https://github.com/circe/circe/blob/8a27b324d22978c133d0181ecc0f66d26520febd/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/DerivationMacros.scala#L335)}
マクロ実装
型 `R` は `HList` もしくは `CoproductType` である必要があります、`CoproductType` について説明はしてませんが `HList` と同じくShapelessの型で直和を表します、 `sealed trait` のジェネリック型となります
今回は型 `R` が `HList` であるという前提で進めます
`$instanceType` は `RE[R]` を表す構文木を生成しており、 `RE` 型は継承時に型引数としている `ReprAsObjectEncoder` 型です
`$encodeMethodName` は [継承先で定義しており](https://github.com/circe/circe/blob/master/modules/generic/shared/src/main/scala/io/circe/generic/Deriver.scala#L37)、`encodeObject` を表す構文木となります(これは `ReprAsObjectEncoder` のインスタンスを作るときのメソッド名として扱われます)
`$fullEncodeMethodArgs` は `a: R` という構文木と継承時にoverrideされていれば追加のメソッド引数の構文木を返します、今回はoverrideされていないので `encodeMethodArgs` はNil、つまりこの関数で返される構文木は `a: R` のみとなります
`$instanceDefs` `$instanceImpl` については `hlistEncoderParts` メソッドで作成するため、後述とさせて頂きます

最終的に関数内では

```scala
// Rは任意のジェネリック型(HList)
new ReprAsObjectEncoder[R] {
  ..$instanceDefs
  final def encodeObject(a: R): _root_.io.circe.JsonObject = $instanceImpl
}: ReprAsObjectEncoder[R]
```

となります
( `_root_` は絶対パス指定なだけで、仮にルートpackageで定義するのであれば `_root_.io.circe.JsonObject` `io.circe.JsonObject` は同一です)

### [Deriver.hlistEncoderParts](https://github.com/circe/circe/blob/8a27b324d22978c133d0181ecc0f66d26520febd/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/DerivationMacros.scala#L288-L311)
`encodeObject` の関数bodyと `ReprAsObjectEncoder` に定義する `instanceDefs ` の構文木を返す関数です
引数 `members` は型 `R` を元に作られた独自型 `Members` で大本となった `case class` 型 `A` のFieldの一覧を表す型です

### [Members#fold](https://github.com/circe/circe/blob/8a27b324d22978c133d0181ecc0f66d26520febd/modules/generic/shared/src/main/scala/io/circe/generic/util/macros/DerivationMacros.scala#L79-L100)
変数名とかコードの流れからList#foldだと勘違いしそうですが独自定義関数です
各Fieldに対するEncoderインスタンスを取得し、それらを `instanceDefs` という構文木のリストとして返すことと `HList` 分解用のパタンマッチ構文、そして `JsonObject.fromIterable` にわたすためのfieldに対応したエンコード適用Fieldの構文木を返します

引数について
`namePrefix` はEncoderインスタンスを変数に束縛する際のヘンス名です(理解する上で重要なものではないので無視しても構いません)
`resolver` はある型 `T` からエンコーダ `Encoder[T]` を導出するための無名関数です、詳しくは説明しないですが、implicitで導出しています(今更ですがプリミティブ型、及び基本的な型 `Option, Either, List, etc...` についてはライブラリ側でEncoderが定義されています)
`init` `f` はゼロ値と畳込み関数です、役割としては通常の `List#fold` と同じイメージで大丈夫です
戻り値は通常の `List#fold` と違い、畳み込み結果と一緒に `instanceDefs` が帰ります

`hlistEncoderParts` に帰ってくる値としては
`instanceDefs` は実際には以下のような構文になります

```scala
// case class Humanの場合
private[this] val circeGenericEncoderForName = io.circe.Encoder.encodeString
private[this] val circeGenericEncoderForAge = io.circe.Encoder.encodeInt
```

`pattern` については

```scala
// case class Humanの場合
_root_.shapeless.::(circeGenericHListBindingForName, _root_.shapeless.::(circeGenericHListBindingForAge, _root_.shapeless.HNil))
```

`fields` については

```scala
("name", circeGenericEncoderForName(circeGenericHListBindingForName)), ("age", circeGenericEncoderForAge(circeGenericHListBindingForAge))
```

となります

以上の構文木を組み合わせ `hlistEncoderParts` の戻り値としては

```scala
a match {
  case _root_.shapeless.::(circeGenericHListBindingForName, _root_.shapeless.::(circeGenericHListBindingForAge, _root_.shapeless.HNil)) =>
     _root_.io.circe.JsonObject.fromIterable(_root_.scala.collection.immutable.Vector(("name", circeGenericEncoderForName(circeGenericHListBindingForName)), ("age", circeGenericEncoderForAge(circeGenericHListBindingForAge))))
}
```

読みやすくすると

```scala
a match {
  case circeGenericHListBindingForName :: circeGenericHListBindingForAge :: HNil =>
     JsonObject.fromIterable(Vector(("name", circeGenericEncoderForName(circeGenericHListBindingForName)), ("age", circeGenericEncoderForAge(circeGenericHListBindingForAge))))
}
```
となります
(`instanceDefs` についてはそのまま返してます)

これを `constructEncoder` の構文木に組み込むと

```scala
```scala
// Rは任意のジェネリック型(HList)
new ReprAsObjectEncoder[R] {
  private[this] val circeGenericEncoderForName = io.circe.Encoder.encodeString
  private[this] val circeGenericEncoderForAge = io.circe.Encoder.encodeInt
  
  final def encodeObject(a: R): _root_.io.circe.JsonObject = a match {
    case _root_.shapeless.::(circeGenericHListBindingForName, _root_.shapeless.::(circeGenericHListBindingForAge, _root_.shapeless.HNil)) =>
       _root_.io.circe.JsonObject.fromIterable(_root_.scala.collection.immutable.Vector(("name", circeGenericEncoderForName(circeGenericHListBindingForName)), ("age", circeGenericEncoderForAge(circeGenericHListBindingForAge))))
  }
}: ReprAsObjectEncoder[R]
```

コンパイルの通る形になりました
これで任意のジェネリック型 `R` に対する `ReprAsObjectEncoder[R]` ができたので
`R` に対する具象型 `A` の `DerivedAsObjectEncoder[A]`、すなわちスーパークラスである `Encoder.AsObject[A]` が得られるということになります

---

今回はEncoderについて書きましたがDecoderについても同様にコードを追っていけば理解できると思います、scalaに置いて難しめの機能/ライブラリを使っていますが、その分コードを読むことでscalaの世界への理解が広まる良いコードでした
今回はShapelessの話ではないので省きましたが `Generics.Aux[A, R]` がなぜ `A` に対するGenerics型(HList)  `R` を導出できるかなども調べれば面白いかもしれませんね