TypeFoldable과 TypeFolder

이전 장에서 바인더를 인스턴스화하는 방법을 살펴보았습니다. 이를 위해서는 Early(Binder) 내부의 모든 것을 살펴보고 바운드 변수가 사용된 곳을 찾아 치환해야 합니다. 바인더는 Ty뿐만 아니라 임의의 Rust 타입 T를 감쌀 수 있습니다. 그렇다면 Early/Binder 타입의 instantiate 메서드는 어떻게 구현합니까?

답은 TypeFoldable과 TypeFolder라는 두 트레이트입니다.

• TypeFoldable은 타입 정보를 담고 있는 타입이 구현합니다. 이 트레이트를 사용하면 TypeFoldable의 내용을 재귀적으로 처리하고 그 내용에 원하는 작업을 수행할 수 있습니다.
• TypeFolder는 TypeFoldable을 처리하는 동안 마주치는 타입에 대해 무엇을 할지 정의합니다.

예를 들어 TypeFolder 트레이트에는 타입을 입력으로 받아 새로운 타입을 결과로 반환하는 fold_ty 메서드가 있습니다. TypeFoldable은 자기 자신에 대해 TypeFolder의 fold_foo 메서드를 호출하여 TypeFolder가 자신의 내용(내부에 포함된 타입, 리전 등)에 접근할 수 있게 합니다.

이는 Rust에서 우리가 즐겨 사용하게 된 이터레이터 콤비네이터에 빗대어 생각할 수 있습니다:

vec.iter().map(|e1| foo(e2)).collect()
//             ^^^^^^^^^^^^ analogous to `TypeFolder`
//         ^^^ analogous to `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를 호출하도록 구현했다는 점에 주목하십시오. 즉, 폴더는 def_id와 ty는 바꿀 수 있지만 MyFoldable 구조체 전체를 바꿀 수는 없습니다.

모든 내용을 종합하는 예를 하나 더 들어 보겠습니다. Vec<Vec<X>>와 같은 타입이 있다고 가정합시다. 이때 ty::Ty는 Adt(Vec, &[Adt(Vec, &[Param(X)])])와 같은 형태가 됩니다. subst(X => u32)를 수행하려면 먼저 전체 타입을 살펴봅니다. 가장 바깥 수준에서는 치환할 것이 없으므로 한 수준 내려가서 Adt(Vec, &[Param(X)])를 살펴봅니다. 여기에도 여전히 치환할 것이 없으므로 다시 한 수준 내려갑니다. 이제 살펴보는 것은 Param(X)이며, 이는 치환할 수 있으므로 u32로 대체합니다. 더 이상 내려갈 수 없으므로 작업이 끝나며, 전체 결과는 Adt(Vec, &[Adt(Vec, &[u32])])입니다.

마지막으로 언급할 점이 있습니다. TypeFoldable을 폴딩할 때는 대개 대부분의 것을 변경하고 싶지 않습니다. 타입에 도달했을 때에만 무언가를 하고 싶습니다. 이는 구현이 사실상 필드의 TypeFoldable 구현으로 그대로 전달하기만 하는 TypeFoldable 타입이 많을 수 있다는 뜻입니다. 이러한 TypeFoldable 구현은 직접 작성하기가 상당히 번거로운 경향이 있습니다. 이러한 이유로 #![derive(TypeFoldable)]를 사용할 수 있게 해 주는 derive 매크로가 있습니다. 이 매크로는 여기에 정의되어 있습니다.

subst 치환의 경우 실제 폴더가 앞서 언급한 인덱싱을 수행합니다. 그곳에서 Folder를 정의하고 TypeFoldable에 대해 fold_with를 호출하여 자기 자신을 처리하게 합니다. 그런 다음 각 타입을 처리하는 메서드인 fold_ty는 ty::Param을 찾아 치환 목록의 항목으로 대체하고, 그렇지 않은 타입은 재귀적으로 처리합니다. 대체할 때는 ty_for_param을 호출하는데, 이 함수가 하는 일은 Param의 인덱스로 치환 목록을 인덱싱하는 것뿐입니다.