Scala 3 のマクロを使って Minecraft のプロトコルデコーダを自動導出する

諸事情により急に Minecraft のプロトコルを喋る Scala ライブラリが欲しくなった僕は、要求[^1]に合いそうなライブラリが見当たらなかったため仕方なく作ることにしました。

[^1]: パケットデータが不変、パケット名が文字列解決だったりせず全てに型が付いている、複数バージョン対応等。

Scala / sbt はそれぞれ 3.0.1 / 1.5.5 を利用します。

今回書いたコードは[ここ](https://github.com/kory33/s2mc-test/blob/a509c7f158b72fe316c8bac6d25ef04b23b537be/src/main/scala/macros/GenByteDecode.scala)に置いています。

## Scala 3 のマクロについて

Scala 3 でのメタプログラミングで提供されている機構を知らない方は、公式ドキュメントの [macro tutorial](https://docs.scala-lang.org/scala3/guides/macros/index.html) に目を通すことを推奨します。必要に応じて [language reference](https://docs.scala-lang.org/scala3/reference/metaprogramming.html) を参照してください。

この記事で解説するコンパイル時リフレクションは、必要でなければ書かない方が望ましいです。書くことが避けられなさそうな場合は、公式ドキュメントで説明されていないマクロ開発テクニック等を解説している [SoftwareMill による記事](https://softwaremill.com/scala-3-macros-tips-and-tricks)に目を通すことを推奨します。

### Scala 3 のメタプログラミングAPIの階層について

Scala 3 は、メタプログラミングをサポートする機能をいくつかの階層にて提供しており(macro tutorial参照)、

 - 関数定義を呼び出し元に埋め込むことをコンパイラに保証させる `inline` 修飾子[^2]や、コンパイル時に計算を行うための [scala.compiletime パッケージ](https://docs.scala-lang.org/scala3/reference/metaprogramming/compiletime-ops.html)
 - 型付き構文木である `Expr[T]` を `inline` パラメータで受け取り、それに対する単純なパターンマッチや操作を行うための Quotes API
 - コンパイル済みの任意の場所から型付き構文木(Typed Abstract Syntax Trees, TASTy)を引っこ抜き、プログラムに対する自由な操作を行うためのコンパイル時リフレクションAPI
 - バイナリに埋め込まれたTASTyを読み出し、実行時に構文木を操作する TASTy inspection API

などがあります。上のリストでは下に行くほど複雑なことが可能となり、それに伴いコンパイラが保証してくれる範囲が減っていきます。例えば Quotes API でできることを TASTy inspection API で行うのはかなりつらい(安全でない)ため、どの機能が大体どの程度のことをできるのかを macro tutorial などで確認することをお勧めします。

[^2]: 場合によるがパフォーマンス向上が見込める時がある。詳細については [macro tutorial](https://docs.scala-lang.org/scala3/guides/macros/inline.html) を参照のこと。[JITによる最適化を阻害する可能性がある](https://docs.scala-lang.org/scala3/guides/macros/best-practices.html#be-careful-when-inlining-for-performance)らしく、濫用には注意。

## 背景

マクロを使うことになった背景をご紹介します。興味がない方は[今回の課題](#今回の課題)まで読み飛ばしてください。

### パケット定義

とりあえず既存の Minecraft プロトコルラッパーを調べてみます。[有志が纏めてくれていた](https://wiki.vg/Client_List)ので一通り確認しましたが、Rust 製のライブラリである [Stevenarella](https://github.com/iceiix/stevenarella) がとても良さそうです。

しかし、欲しいのは Scala から楽に呼び出せるライブラリです。

Minecraft はクライアントとサーバーの同期に「パケット」と呼ばれる単位[^3]を利用しており、ここの定義さえ別ライブラリから引っ張ってくれば他の記述量はそこまで多くはありません。

というわけで、Rust の `macro_rules!` で書かれている[パケットの型定義](https://github.com/iceiix/stevenarella/blob/755aaf9ede07423f2baef3f5930dbe75524c6d24/protocol/src/protocol/packet.rs#L17)を Scala 向けの型定義に変換するパーサ/AST変換器/プリンタの組を[書きました](https://github.com/kory33/steven-protocol-to-s2mc-protocol/tree/be785977b7a477c14d0c28c3f25e7298442001f9)。[こんな感じ](https://github.com/kory33/s2mc-test/blob/a509c7f158b72fe316c8bac6d25ef04b23b537be/src/main/scala/connection/protocol/packets/PacketIntent.scala)の型定義が自動で出てきます。

[^3]: TCP上で通信されるものの、Minecraftの「パケット」はTCPパケットよりも随分大きい。

### パケットの仕様

さて、型定義だけがあってもそれをどのように送受信すれば良いかがわかりません。幸いこれも[有志が纏めてくれて](https://wiki.vg/index.php?title=Protocol&oldid=16907)おり、

 - パケットIDに続いてパケットの中身が送られる
 - 送信時には、パケットの各フィールドを順にバイト列に書いていけば良い

ということが分かります。

ところで、 `Data types` の `Optional X` の項を見に行くと、

> Whether or not the field is present must be known from the context.

と書いてあります。

どういう意味だろうと思い、 Stevenarella の[読み込み実装](https://github.com/iceiix/stevenarella/blob/755aaf9ede07423f2baef3f5930dbe75524c6d24/protocol/src/protocol/mod.rs#L151-L156) を見に行くと、それまでにパースしたデータによってフィールドを読み飛ばすかどうかを決定しています。例えば、[Face Player](https://wiki.vg/index.php?title=Protocol&oldid=16907#Face_Player)パケットでは `Entity ID` フィールドがあるかどうかは `Is entity` フィールドの値に依存します。ですから、`Is entity` が `false` だった場合、一バイトたりとも追加で読み飛ばしてはなりません。なるほど、この方式だと `case class` とは少し相性が良くなさそうです。

しかし、先程のAST変換器を使ってデコーダのコードまで生成すると、コードが2から3倍にまで膨らむこととなり、パケット定義ファイルが非常に見通しの悪いものとなってしまいます。

そこで、 Scala 3 で stable な機能になったメタプログラミング機能でデコーダを自動生成することにしました。

## 今回の課題

与えられた `case class A` に対して、後述の `ByteDecode[A]` の値を作成するのが目標です。

### ByteDecodeとは

`A` の「デコーダ」である `ByteDecode[A]` の値は、バイト列を消費することによって `A` の値を復元する能力があります。

`ByteDecode[_]` の定義は詳細には述べません。代わりに、 `cats.Monad[ByteDecode]` の値が `given` で与えられており、それが

```Scala
// 一切バイト列を読まず、x を結果として報告するデコーダを作る
def pure[A](x: A): ByteDecode[A]

// decoder でバイト列を読み、
// そこから出てきた値を f に通して結果として報告するデコーダを作る
def map[A, B](decoder: ByteDecode[A])(f: A => B): ByteDecode[B]

// decoder でバイト列を読み、
// そこから出てきた値を f に通して新たなデコーダ decoder' を得て、
// decoder' でバイト列を読んだ結果を報告するデコーダを作る
def flatMap[A, B](decoder: ByteDecode[A])(f: A => ByteDecode[B]): ByteDecode[B]
```

の三つのメソッドを提供していることを前提とします。`ByteDecode[A]` の値を既存の `ByteDecode` から組み立てる時には、 `ByteDecode` の定義ではなく上にある三つの関数を使って組み立てることとします。

### 達成したい変換

例えば、次のようなパケットクラスを考えます。

```Scala
case class StopSound(
                      flags: UByte,
                      source: Option[VarInt],
                      sound: Option[String],
                    ) {
  require(source.nonEmpty == ((flags & 0x01) != UByte(0)))
  require(sound.nonEmpty == ((flags & 0x02) != UByte(0)))
}
```

[wiki.vg](https://wiki.vg/index.php?title=Protocol&oldid=16907#Stop_Sound) を見ると、このパケットはサーバーからクライアントへ鳴っている音を止めたということを通知するパケットであり、 `flags` によって止めた音の範囲指定(`source`や`sound`)があるかがコントロールされていることがわかります。例えば、 `flags` が `UByte(0)` だった場合、任意の音源からの任意の音が停止したという通知になります。

不正なパケットデータを実行時に排除したいので、クラスボディ内に `require` が書かれています。このようなクラス定義から、次のようなデコーダ定義を自動生成することが目的です。

<details><summary>`for` + `cats.implicits.given` + ラムダ式</summary><div>

```Scala
// inline メソッド GenByteDecode.gen[A] を呼び出すと、次のブロックが返ってきてほしい
{
  // この import により、 ByteDecode[A]に対して .flatMap、.map が呼べるようになる
  import cats.implicits.given

  for {
    flags <- summon[ByteDecode[UByte]]
    source <-
      if ((flags & 0x01) != UByte(0)) then
        Monad[ByteDecode].map(summon[ByteDecode[VarInt]])(value => Some(value))
      else
        Monad[ByteDecode].pure(None)
    sound <-
      if ((flags & 0x02) != UByte(0)) then
        Monad[ByteDecode].map(summon[ByteDecode[String]])(value => Some(value))
      else
        Monad[ByteDecode].pure(None)
  } yield StopSound(flags, source, sound)
}
```
</div></details>

ここで、Scala の `for` 式は糖衣構文ですので、上のブロックは

<details><summary>`map` + `flatMap` + `cats.implicits.given` + ラムダ式</summary><div>

```Scala
{
  import cats.implicits.given

  summon[ByteDecode[UByte]].flatMap { flags => 
    {
      if ((flags & 0x01) != UByte(0)) then
        Monad[ByteDecode].map(summon[ByteDecode[VarInt]])(value => Some(value))
      else
        Monad[ByteDecode].pure(None)
    }.flatMap { source =>
      {
        if ((flags & 0x02) != UByte(0)) then
          Monad[ByteDecode].map(summon[ByteDecode[String]])(value => Some(value))
        else
          Monad[ByteDecode].pure(None)
      }.map { sound =>
        StopSound(flags, source, sound)
      }
    }
  }
}
```
</div></details>

と等価です。最後のみ `map` になっているのはコード生成する上では都合が悪いため、[モナド則の map / flatMap の規則](https://github.com/typelevel/cats/blob/62801f971083b117aaa30754c72a0c5968fbb812/laws/src/main/scala/cats/laws/MonadLaws.scala#L33-L37)により、以下のように変形できます。

<details><summary>`flatMap` + `pure` + `cats.implicits.given` + ラムダ式</summary><div>

```Scala
{
  import cats.implicits.given

  summon[ByteDecode[UByte]].flatMap { flags => 
    {
      if ((flags & 0x01) != UByte(0)) then
        Monad[ByteDecode].map(summon[ByteDecode[VarInt]])(value => Some(value))
      else
        Monad[ByteDecode].pure(None)
    }.flatMap { source =>
      {
        if ((flags & 0x02) != UByte(0)) then
          Monad[ByteDecode].map(summon[ByteDecode[String]])(value => Some(value))
        else
          Monad[ByteDecode].pure(None)
      }.flatMap { sound =>
        Monad[ByteDecode].pure(StopSound(flags, source, sound))
      }
    }
  }
}
```
</div></details>

最後に、拡張メソッドや `summon` を参照先の実装で置き換えて以下を得ます。これがマクロによって得たいコードブロックです。

<details><summary>`flatMap` + `pure` + ラムダ式</summary><div>

```Scala
// m: Monad[ByteDecode]
// dUByte: ByteDecode[UByte]
// dVarInt: ByteDecode[VarInt]
// dString: ByteDecode[String]
// が全て given されているとする
{
  m.flatMap(dUByte) { flags => 
    m.flatMap {
      if ((flags & 0x01) != UByte(0)) then
        m.map(dVarInt)(value => Some(value))
      else
        m.pure(None)
    } { source =>
      m.flatMap {
        if ((flags & 0x02) != UByte(0)) then
          m.map(dString)(value => Some(value))
        else
          m.pure(None)
      } { sound =>
        m.pure(StopSound(flags, source, sound))
      }
    }
  }
}
```

</div></details>

ところで、ラムダ式は内部的(マクロ生成が行われるcompiler phase)には(lambda liftingがされていない、ローカルな)メソッド参照に置き換わっています。ですから、

<details><summary>`flatMap` + `pure` + ローカル `def`</summary><div>

```Scala
// m: Monad[ByteDecode]
// dUByte: ByteDecode[UByte]
// dVarInt: ByteDecode[VarInt]
// dString: ByteDecode[String]
// が全て given されているとする
{
  // anonfunの命名は雰囲気onlyです　似たような名前がコンパイラによって自動生成されます
  def $anonfun(flags: UByte): ByteDecode[A] = {
    def $_$anonfun(source: Option[VarInt]): ByteDecode[A] = {
      def $_$_$anonfun(sound: Option[String]): ByteDecode[A] = {
        m.pure(StopSound(flags, source, sound))
      }

      m.flatMap {
        if ((flags & 0x02) != UByte(0)) then
          m.map(dString)(Some.apply)
        else
          m.pure(None)
      }($_$_$anonfun)
    }

    m.flatMap {
      if ((flags & 0x01) != UByte(0)) then
        m.map(dVarInt)(Some.apply)
      else
        m.pure(None)
    }($_$anonfun)
  }

  m.flatMap(dUByte)($anonfun)
}
```

</div></summary>

が最終的に構築するASTに近いものとなります。

## 実装

コード全文は[ここ](https://github.com/kory33/s2mc-test/blob/a509c7f158b72fe316c8bac6d25ef04b23b537be/src/main/scala/macros/GenByteDecode.scala)に置いています。エントリポイントから順に見ていきます。

### エントリポイント (L16)

まず、

```Scala
  inline def gen[A]: ByteDecode[A] =
    ${ genImpl[A] }
```

によりマクロのエントリポイントが定義されています。今回の方式ではマクロ呼び出し箇所に `BydeDecode[A]` 型の式を展開することが分かっているため、 `transparent` 修飾子は不要です。 `genImpl` 以外の残りのメソッドはヘルパーメソッドなので、 [73行目](https://github.com/kory33/s2mc-test/blob/a509c7f158b72fe316c8bac6d25ef04b23b537be/src/main/scala/macros/GenByteDecode.scala#L73) まで飛びます。

### マクロ実装のエントリポイント (L73-L77)

```Scala
  private def genImpl[A: Type](using quotes: Quotes): Expr[ByteDecode[A]] = {
    import quotes.reflect.*

    // this instance is provided in `ByteDecode`'s companion
    val byteDecodeMonad: Expr[cats.Monad[ByteDecode]] = Expr.summon[cats.Monad[ByteDecode]].get
```

`genImpl` は型 `A` 、 `Type[A]` (Aの型情報) と `Quotes` を(コンテキスト)パラメータとし、目的である `ByteDecode[A]` を吐き出す関数です。 `Quotes` はマクロ呼び出し元の情報を含んでいるリフレクション用のオブジェクトで、 `quotes.reflect.*` を `import` することで様々なリフレクション用の機能が使えるようになります。

`Expr.summon[A]` により、マクロ展開元の箇所から見える `given` された項を引っ張ってくることができます。 `byteDecodeMonad` は後々利用しますが、 [達成したい変換](#達成したい変換)で書いた `m` への参照がこれで手に入りました。

### マクロの実装のエントリポイント (L79-L87)、

```Scala
    sealed trait ClassField {
      val fieldType: TypeRepr
      val fieldName: String
    }
    case class OptionalField(fieldName: String, underlyingType: TypeRepr, nonEmptyIff: Expr[Boolean]) extends ClassField {
      override val fieldType = underlyingType.asType match
        case '[u] => TypeRepr.of[Option[u]]
    }
    case class RequiredField(fieldName: String, fieldType: TypeRepr) extends ClassField
```

は、フィールド情報に関するデータを定義しています。例えば `StopSound` クラスの例に戻れば、フィールド情報を

```Scala
RequiredField("flags", TypeRepr.of[UByte])
OptionalField("source", TypeRepr.of[VarInt], '{ ... })
OptionalField("sound", TypeRepr.of[String], '{ ... })
```

の三つの値で表現します。 `'{ ... }` は条件式のASTを指し示しており、デコーダの定義式に後々埋め込む必要があります。

### クラスシンボルの解決及び条件検査(L89-L95)

```Scala
    val typeSymbol = TypeRepr.of[A].typeSymbol

    if !typeSymbol.flags.is(Flags.Case) then
      report.throwError(s"Expected a case class but found ${typeSymbol}")

    if primaryConstructorHasTypeParameter[A] then
      report.throwError(s"Classes with type parameters not supported, found ${typeSymbol}")
```

は、型 `A` が参照するシンボルを得て、それらに対する二つの条件(`case class` であり、型パラメータを一つも持たないこと)をコンパイル時に検査しています。`A` に `Option[String]` などを渡してこの検査に通らなかった場合、コンパイラは「マクロ展開時にエラーが起こった」としてコンパイルエラーにします。

> ```
[error] -- Error: *:\*****************\src\main\scala\App.scala:26:23 -----
[error] 26 |      GenByteDecode.gen[Option[Int]].readOne(fs2.Chunk.empty)
[error]    |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[error]    |      Expected a case class but found class Option
[error]    | This location contains code that was inlined from App.scala:26
```

マクロが扱える型の範囲を制限したい場合には、このように `report.throwError` を呼び出すことでコンパイラに意図を伝えることができます。

### クラス定義からの情報収集(L97-L129)

```Scala
    typeSymbol.tree match {
      case d @ ClassDef(className, DefDef(_, params, _, _), _, _, body) =>
        // list of conditions specifying that the field (_1) is nonEmpty precisely when condition (_2) is true
        val conditions: List[OptionalFieldCondition] = {
          body
            .flatMap {
              case a: Term => Some(a.asExpr)
              case _ => None
            }.flatMap {
              case '{ scala.Predef.require((${ident}: Option[Any]).nonEmpty == (${cond}: Boolean)) } =>
                OptionalFieldCondition.fromOptionExpr(ident, cond)
              case _ => None
            }
        }

        val fields: List[ClassField] =
          params.map(_.params).flatten.flatMap {
            case ValDef(fieldName, typeTree, _) => typeTree.tpe.asType match
              case '[scala.Option[ut]] =>
                val condition =
                  conjunctNonzeroClauses(conditions.conditionOn(fieldName))
                    .getOrElse(report.throwError {
                      s"\tExpected nonemptyness test for the optional field $fieldName.\n" +
                       "\tIt is possible that the macro could not inspect the class definition body.\n" +
                       "\tMake sure to:\n" +
                       "\t - add -Yretain-trees compiler flag" +
                       "\t - locate the target class in a file different from the expansion site"
                    })
                Some(OptionalField(fieldName, TypeRepr.of[ut], condition))
              case '[t] =>
                Some(RequiredField(fieldName, TypeRepr.of[t]))
            case _ => None
          }
```

`A` のクラス定義から必要な情報を集めています。このセクションで注目すべきはパターンマッチです。

Scala 3 は、 `Type[?]` の値と `Expr[A]` の値に対する**非常に強力**なパターンマッチ機構(quoted patterns)を提供しています。

106 行

```Scala
case '{ scala.Predef.require((${ident}: Option[Any]).nonEmpty == (${cond}: Boolean)) }
```

では、クラスボディに書かれている項のうち `require(${ident}.nonEmpty == ${cond})` (ここで、 `ident` と `cond` はそれぞれ `Expr[Option[Any]]` と `Expr[Boolean]` の値が束縛されている) の形をしている箇所のみを取り出し、 `OptionalFieldcondition` として記録しています。

また、 114-115 行

```Scala
case ValDef(fieldName, typeTree, _) => typeTree.tpe.asType match
  case '[scala.Option[ut]] =>
```

では、コンストラクタパラメータのうち型宣言が `scala.Option[ut]` (`ut` は普通の型として扱える) の形をしているものにマッチし、 `OptionalField` として記録しています。 `ut` のような型にマッチした際には `Type[ut]` が得られるようで、 `TypeRepr.of[ut]` で `TypeRepr` を得ることにより `match` 式の外にまで `ut` の型情報を持ち出すことができます。

Quoted patterns の詳細は [Scala 3 Macro tutorial](https://docs.scala-lang.org/scala3/guides/macros/quotes.html#quoted-patterns) を参照してください。

#### `-Yretain-trees` コンパイラオプションについて

`typeSymbol.tree` にてクラス定義の構文木が得られますが、一つ注意点として、 `-Yretain-trees` コンパイラオプションを付けないと**空のクラスボディが渡ってきて**しまいます。今回のようにクラス定義の詳細な情報を利用する場合これでは困るため、 `build.sbt` に

```Scala
scalacOptions ++= Seq("-Yretain-trees", "-Xcheck-macros")
```

と書いています。

また、 L119-L123 にあるメッセージの通り、クラス定義がマクロ呼び出し元と**同じファイルで行われていた場合** `ClassDef` によって得られる情報が制限[^4]されますので注意が必要です。

### 再帰的に構文木を組み立て上げる (L131-L191)

L131-L191 では、

 - `replaceFieldReferencesWithParameters` (後述)
 - `mapConstructorParamsToPureDecoder` (フィールドに対応する変数の `Queue` から `ByteDecode[A]` を作成する)
 - `recurse` (構文木を再帰的に組み上げる)

の三つの関数を定義して、

```Scala
recurse(Symbol.spliceOwner, Queue.empty, fields)
```

をマクロの生成結果としています(`fields` は先程クラス定義から得た `List[ClassField]`)。

`recurse` は

 - `currentOwner` (生成するシンボルの Owner である `Symbol`)
 - `remainingFields` (未処理のクラスフィールドのリスト)
 - `parametersSoFar` (処理済みの、すでに束縛されている(クラスフィールドと同名かつ同順の)変数の `Queue`)

を引数に取り、 `remainingFields` が空ならば

```Scala
mapConstructorParamsToPureDecoder(parametersSoFar) // : Expr[ByteDecode[A]]
```

を、そうでなければ

```Scala
'{ ${byteDecodeMonad}.flatMap(${fieldDecoder})(${continuation}) }
```

の形の構文木を生成します。`remainingFields` が空であるケースの実装は単純なので、 `remainingFields = next :: rest` で、 `next` に対応するフィールドの型が `ft` だった場合の `fieldDecoder` と `continuation` の実装についてそれぞれ見ていきます。

#### `fieldDecoder` (L160-172)

```Scala
val fieldDecoder: Expr[ByteDecode[ft]] = {
  next match {
    case OptionalField(_, uType, cond) => uType.asType match
      // ut is a type such that Option[ut] =:= ft
      case '[ut] => '{
        if (${replaceFieldReferencesWithParameters(parametersSoFar)(cond)}) then
          ${byteDecodeMonad}.map(${summonDecoderExpr[ut]})(Some(_))
        else
          ${byteDecodeMonad}.pure(None)
      } // Expr of type ByteDecode[Option[ut]]
    case RequiredField(_, fieldType) => summonDecoderExpr[ft]
  }
}.asExprOf[ByteDecode[ft]]
```

`RequiredField` の節は簡単なので、 `next` が `OptionalField` だった場合を考えます。例えば `source` は

```Scala
require(source.nonEmpty == ((flags & 0x01) != UByte(0)))
```

という制約のあるフィールドでした。`next` が `source` だった場合、 `fieldDecoder` には

```Scala
if ((flags & 0x01) != UByte(0)) then
  m.map(dVarInt)(Some.apply)
else
  m.pure(None)
```

のような AST を生成してあげる必要があります。

ところで、 `cond` には

```Scala
((StopSound.this.flags & 0x01) != UByte(0))
```

のような構文木が入っています。ここで

```Scala
'{
  if (${cond}) then
    ${byteDecodeMonad}.map(${summonDecoderExpr[ut]})(Some(_))
  else
    ${byteDecodeMonad}.pure(None)
}
``` 

を `fieldDecoder` としてしまうと、 `StopSound.this.flags` という存在しない識別子を参照するコードが生成されてしまうことになります。これを解決するため、 `replaceFieldReferencesWithParameters(parametersSoFar)` によって `flags` のような識別子を `parametersSoFar` の中にある同名の識別子によって置き換えるという操作を行います。

L131-L146の `replaceFieldReferencesWithParameters` は

```Scala
def replaceFieldReferencesWithParameters(params: Queue[Term])(expr: Expr[Boolean]): Expr[Boolean] =
  val mapper: TreeMap = new TreeMap:
    override def transformTerm(tree: Term)(/* virtually unused */ _owner: Symbol): Term = tree match
      case Ident(name) =>
        if (fields.exists(_.fieldName == name))
          params.find {
            case t @ Ident(paramName) if paramName == name => true
            case _ => false
          }.getOrElse(report.throwError {
              s"\tReference to an identifier \"$name\" in the expression ${expr.show} is invalid.\n" +
              s"\tNote that a nonemptiness condition of an optional field can only refer to class fields declared before the optional field."
          })
        else
          tree
      case _ => super.transformTerm(tree)(_owner)
  mapper.transformTerm(expr.asTerm)(Symbol.spliceOwner).asExprOf[Boolean]
```

と定義されており、 AST の再帰的置き換えを楽に行うためにReflection API が提供している `TreeMap` を利用して構文木の再構築を行っています。

#### `continuation` (L174-185)

`coninuation` は、

```Scala
val continuation: Expr[ft => ByteDecode[A]] =
  Lambda(
    currentOwner,
    MethodType(List(next.fieldName))(_ => List(next.fieldType), _ => TypeRepr.of[ByteDecode[A]]),
    (innerOwner, params) => params.head match {
      case p: Term => recurse(innerOwner, parametersSoFar.enqueue(p), rest).asTerm
        // we need explicit owner conversion
        // see https://github.com/lampepfl/dotty/issues/12309#issuecomment-831240766 for details
        .changeOwner(innerOwner)
      case p => report.throwError(s"Expected an identifier, got unexpected $p")
    }
  ).asExprOf[ft => ByteDecode[A]]
```

と定義されています。ここに来て初めて `currentOwner` が利用されていますが、 `currentOwner` は「新しく生成する Symbol をどこにぶら下げればよいか」を指すオブジェクトです。

Symbol は変数、型、型変数などの定義そのものを参照するオブジェクトで、 Owner は Symbol がどこで定義されているかを指し示す別の Symbolです。

> Ownerとはそのsymbolがどの文脈に出てくるかを示すものであり、他のsymbolへの参照で表されます。例えば以下のようなプログラムを考えます。

> ```Scala
class Hoge {
  def piyo(): Unit = {
    val fuga = 10
  }
}
```

> このときfugaに対応するsymbol(面倒なので以下fugaと同一視します)のownerは、piyoのローカル変数なのでpiyoとなります。また、piyoのownerはHogeです。
> 
> 引用元[^5]: [Scala macros中級者の壁: symbolとowner](https://qiita.com/hiroshi-cl/items/4696e1a7c5a72067114a)

`Lambda` はラムダ式の項を生成するための smart constructor で、以下のような動作をします。

 1. 第一引数に渡ってくる `Symbol` の中に、第二引数の `MethodType` [^6] によって指定されるシグネチャを持つ関数を `$anonfun` のようなfreshな名前で生成する (このシンボルを `meth` と呼ぶ)
 1. 第三引数に渡ってくる `(Symbol, List[Tree]) => Tree` の形をした関数に `(meth, methの引数として宣言された変数の Term のリスト)` の組を渡して構文木を取得し、これを `meth` の右辺に設定する
 1. `meth` を指し示す `Closure` が最後に置いてある `Block` を返す

今回生成するコードはラムダ式の中にラムダ式が入っているものですので、 `Lambda` の第三引数の中で再帰的に `recurse` を呼び出しています。注意点として、 `Lambda` の第三引数は、直下の Symbol の Owner が `innerOwner` に設定された AST を返す必要があるため、 `recurse` が返してきた構文木に対して明示的に `changeOwner` する必要があります。

(`Lambda` / Symbol / Owner 周りの挙動に関しては僕もあまり自信がありません。もし誤った記述やベターな説明がありましたらご指摘ください。)

これで `genImpl` の実装の主要な箇所を読み終わりました。お疲れ様でした。

[^4]: メソッド定義は得られるが、 `require(...)` 等の式が得られない。コンパイラの仕様かもしれないしバグなのかもしれない（よくわかりませんでした）
[^5]: この記事は Scala 2 の experimental なマクロに関するもので、Scala 3 とはいくらか事情が異なる部分があるが、 Symbol と Owner の概念は大きくは変わっていなさそう
[^6]: `MethodType` の第二、第三引数にはそれぞれ(型)変数の情報のListと結果型の情報を渡すようなのですが、ドキュメントがどこにも見つからず、引数に入ってくる `MethodType` が何なのかよくわかりませんでした…　少なくとも、今回のように単相的(型引数を持たない)かつpath-dependentでない場合は、引数を無視して `List[TypeTree]` と `TypeTree` を返す関数を第二、第三引数に渡して良さそうです。

## まとめ

 - Scala 3 でメタプログラミングをする時には、可能な限り表層にある API で済ませる
 - Quotes pattern を用いると、構文木のマッチングがとても楽に行える
 - 生の構文木を操作する際には `-Yretain-trees` フラグが必要となるケースがある
 - 全く別の場所から持ってきた `Expr` をマクロの結果に埋め込むときは、識別子への参照を書き換える必要がある
 - 変数や関数をマクロ内で生成する時には owner の変更が必要

## 参考文献

 - [Scala 3 Docs / Macro tutorial](https://docs.scala-lang.org/scala3/guides/macros/index.html)
 - [Scala 3 Language reference / metaprogramming](https://docs.scala-lang.org/scala3/reference/metaprogramming.html)
 - [SoftwareMill / Scala 3 macros tips & tricks](https://softwaremill.com/scala-3-macros-tips-and-tricks)
 - [wiki.vg / Protocol](https://wiki.vg/index.php?title=Protocol&oldid=16907)
 - [今回書いたコード](https://github.com/kory33/s2mc-test/blob/a509c7f158b72fe316c8bac6d25ef04b23b537be/src/main/scala/macros/GenByteDecode.scala)