TypeFoldable と TypeFolder

前の章では、バインダーのインスタンス化について説明しました。 これには、束縛された変数の使用箇所を見つけて置換するために、Early(Binder) の内部にあるすべてを調べることが含まれます。 バインダーは Ty だけでなく、任意の Rust 型 T をラップできます。 では、Early/Binder 型に対して instantiate メソッドをどのように実装するのでしょうか？

答えは、2つのトレイトです。 TypeFoldable と TypeFolder です。

• TypeFoldable は、型情報を埋め込む型によって実装されます。これにより、TypeFoldable の内容を再帰的に 処理し、それらに対して何かを行うことができます。
• TypeFolder は、TypeFoldable を処理している間に遭遇する型に対して何を行いたいかを定義します。

たとえば、TypeFolder トレイトには、型を入力として受け取り、結果として新しい型を返す fold_ty というメソッドがあります。 TypeFoldable は、自身に対して TypeFolder の fold_foo メソッドを呼び出し、 TypeFolder がその内容（内部に含まれる型、リージョンなど）にアクセスできるようにします。

これは、Rust で私たちが愛用しているイテレーターコンビネーターになぞらえて考えることができます。

vec.iter().map(|e1| foo(e2)).collect()
//             ^^^^^^^^^^^^ `TypeFolder` に相当
//         ^^^ `TypeFoldable` に相当

繰り返すと、次のようになります。

• TypeFolder は、“map” 操作を定義するトレイトです。
• TypeFoldable は、型を埋め込むものによって実装されるトレイトです。

subst の場合、それが TypeFolder として実装されていることがわかります: ArgFolder。 その実装を見ると、実際の置換が行われている箇所がわかります。

ただし、この実装が super_fold_with というメソッドを呼び出していることにも気づくかもしれません。これは 何でしょうか？これは TypeFoldable のメソッドです。次の TypeFoldable 型 MyFoldable を考えてみましょう。

struct MyFoldable<'tcx> {
  def_id: DefId,
  ty: Ty<'tcx>,
}

TypeFolder は、MyFoldable のフィールドの一部だけを新しい値に置き換えたい場合に、MyFoldable に対して super_fold_with を呼び出せます。 代わりに MyFoldable 全体を別のものに置き換えたい場合は、fold_with を呼び出します（これは TypeFoldable の別のメソッドです）。

ほとんどすべての場合、構造体全体を置き換えたいわけではありません。構造体内の ty::Ty だけを置き換えたいので、 通常は super_fold_with を呼び出します。MyFoldable が持ちうる典型的な実装は、次のようなものになるでしょう。

my_foldable: MyFoldable<'tcx>
my_foldable.subst(..., subst)

impl TypeFoldable for MyFoldable {
  fn super_fold_with(&self, folder: &mut impl TypeFolder<'tcx>) -> MyFoldable {
    MyFoldable {
      def_id: self.def_id.fold_with(folder),
      ty: self.ty.fold_with(folder),
    }
  }

  fn super_visit_with(..) { }
}

ここでは、super_fold_with を実装して MyFoldable のフィールドをたどり、それらに対して fold_with を呼び出していることに注目してください。つまり、folder は def_id と ty を置き換えることはできますが、 MyFoldable 構造体全体を置き換えることはできません。

物事をまとめるために、もう1つ例を見てみましょう。Vec<Vec<X>> のような型があるとします。 ty::Ty は Adt(Vec, &[Adt(Vec, &[Param(X)])]) のようになります。subst(X => u32) を行いたい場合、 まず型全体を見ます。外側のレベルでは行うべき置換がないことがわかるので、1レベル下に降りて Adt(Vec, &[Param(X)]) を見ます。ここでもまだ行うべき置換はないので、さらに下に降ります。 今度は Param(X) を見ており、これは置換できるので、u32 に置き換えます。これ以上下には降りられないので、 処理は完了し、全体の結果は Adt(Vec, &[Adt(Vec, &[u32])]) になります。

最後に1つ触れておくことがあります。TypeFoldable をフォールドするとき、多くの場合、ほとんどのものは変更したくありません。 型に到達したときだけ何かを行いたいのです。つまり、多くの TypeFoldable 型では、その実装が基本的に各フィールドの TypeFoldable 実装へ転送するだけになる場合があります。このような TypeFoldable の実装を手で書くのはかなり退屈になりがちです。 このため、#![derive(TypeFoldable)] を使えるようにする derive マクロがあります。これは ここで定義されています。

subst 置換の場合、実際の folder は、すでに述べたインデックス付けを行います。 そこでは Folder を定義し、TypeFoldable に対して fold_with を呼び出して自身を処理します。 次に、各型を処理するメソッドである fold_ty は ty::Param を探し、それらについては 置換のリストから得たものに置き換え、それ以外の場合は型を再帰的に処理します。 置き換えるために、ty_for_param を呼び出します。これは Param のインデックスを使って置換のリストにインデックスを付けるだけです。