本家Rustコンパイラのソースを読もうとしてみる（3）

# 前回までのあらすじ

[Guide to Rustc Development](https://rustc-dev-guide.rust-lang.org/about-this-guide.html)という便利なガイドに沿って、Rustの本家コンパイラである[rust-lang/rust](https://github.com/rust-lang/rust)のソースコードを読んでみようという試み。今回は「Source Code Representations」のHIRのあたりから。

MIRまで見てみようと思っていたが、MIR処理の解読に苦戦しているうちにソースのディレクトリ構成が大きく変わってしまった。ファイルの場所の記載がややこしくなってしまうので、少し短いがHIRのあたりだけ見ていこうと思う。

[目次（初回）](https://qiita.com/0yoyoyo/items/eba97a019d0e60324263)

# ソースディレクトリ構成の変更

この章の内容はガイドとは関係ありません。

2020/8/31あたりにソースのディレクトリ構成が大きく変更されたようだ。これまでコンパイラに関係する多くのクレートは`rust/src/librustc_xxx`というディレクトリに存在していたが、`rust/compiler/rustc_xxx`というディレクトリに移動したようだ。関係する議論は[このPR](https://github.com/rust-lang/rust/pull/74862)と思われる。大きくはディレクトリが移動しただけで、ディレクトリの名前も`lib`が取れただけっぽいので、これまで読んだところが無駄になることはなさそうな感じだ。

結果、前回の記事に載せたソースはパスが変わってしまった。そして今回もHIRのところまでは以前のパスでメモってしまっていたので、少し読みづらいかもですが旧ディレクトリ構成のまま記載させて頂こうと思います。


# Source Code Representations

前回はこの章のASTを生成するところまで確認したので、今回はその続きで、HIRの生成部分を見ていく。


### ASTからHIR

HIRは構造的にはASTと変わらないと思われるが、変換で主に2つの仕事がなされるようだ。

- **ソースの実体を識別子（ID）に変換する**。これを行う理由はいくつかありそうだが、IDをkeyとすることで繰り返し処理が行いやすくなると説明されている。IDには`DefID`、`HirID`、`BodyID`、`NodeID`とあり、このうち`NodeID`は今後除去されていく予定とのこと。
- **syntax sugarをdesugarする**。`for`や`if let`などは`match`を用いた表現のsyntax sugarとなっているため、そのような表現はdesugarされる。他にも`impl Trait`関連の処理が行われる他、木で構造は表現できているため括弧の除去なども行われる。

ではソースを見ていこう。`rustc_ast_lowering`の`lower_crate()`において、大きく`rustc_ast::ast::Crate`から`rustc_hir::Crate`に変換される。変換処理は`LoweringContext`という構造に変換されたのち、そのメソッドである同名の`lower_crate()`に進んでいく。

```rust:librustc_ast_lowering/lib.rs
pub fn lower_crate<'a, 'hir>(
    sess: &'a Session,
    krate: &'a Crate,
    resolver: &'a mut dyn ResolverAstLowering,
    nt_to_tokenstream: NtToTokenstream,
    arena: &'hir Arena<'hir>,
) -> hir::Crate<'hir> {
    let _prof_timer = sess.prof.verbose_generic_activity("hir_lowering");

    LoweringContext {
        crate_root: sess.parse_sess.injected_crate_name.get().copied(),
        sess,
        resolver,
        nt_to_tokenstream,
        arena,
        items: BTreeMap::new(),
        trait_items: BTreeMap::new(),
        impl_items: BTreeMap::new(),
        bodies: BTreeMap::new(),
        trait_impls: BTreeMap::new(),
        modules: BTreeMap::new(),
        exported_macros: Vec::new(),
        non_exported_macro_attrs: Vec::new(),
        catch_scopes: Vec::new(),
        loop_scopes: Vec::new(),
        is_in_loop_condition: false,
        is_in_trait_impl: false,
        is_in_dyn_type: false,
        anonymous_lifetime_mode: AnonymousLifetimeMode::PassThrough,
        type_def_lifetime_params: Default::default(),
        current_module: hir::CRATE_HIR_ID,
        current_hir_id_owner: vec![(LocalDefId { local_def_index: CRATE_DEF_INDEX }, 0
        item_local_id_counters: Default::default(),
        node_id_to_hir_id: IndexVec::new(),
        generator_kind: None,
        task_context: None,
        current_item: None,
        lifetimes_to_define: Vec::new(),
        is_collecting_in_band_lifetimes: false,      
        in_scope_lifetimes: Vec::new(),
        allow_try_trait: Some([sym::try_trait][..].into()),
        allow_gen_future: Some([sym::gen_future][..].into()),
    }
    .lower_crate(krate)
}
...
impl<'a, 'hir> LoweringContext<'a, 'hir> {
    fn lower_crate(mut self, c: &Crate) -> hir::Crate<'hir> {
...
        self.lower_node_id(CRATE_NODE_ID);
        debug_assert!(self.node_id_to_hir_id[CRATE_NODE_ID] == Some(hir::CRATE_HIR_ID));

        visit::walk_crate(&mut MiscCollector { lctx: &mut self, hir_id_owner: None }, c);
        visit::walk_crate(&mut item::ItemLowerer { lctx: &mut self }, c);

        let module = self.lower_mod(&c.module);
        let attrs = self.lower_attrs(&c.attrs);
        let body_ids = body_ids(&self.bodies);
        let proc_macros =
            c.proc_macros.iter().map(|id| self.node_id_to_hir_id[*id].unwrap()).collect();

        let trait_map = self
            .resolver
            .trait_map()
            .iter()
            .map(|(&k, v)| (self.node_id_to_hir_id[k].unwrap(), v.clone()))
            .collect();

        let mut def_id_to_hir_id = IndexVec::default();

        for (node_id, hir_id) in self.node_id_to_hir_id.into_iter_enumerated() {
            if let Some(def_id) = self.resolver.opt_local_def_id(node_id) {
                if def_id_to_hir_id.len() <= def_id.index() {
                    def_id_to_hir_id.resize(def_id.index() + 1, None);
                }
                def_id_to_hir_id[def_id] = hir_id;
            }
        }

        self.resolver.definitions().init_def_id_to_hir_id_mapping(def_id_to_hir_id);

        hir::Crate {
            item: hir::CrateItem { module, attrs, span: c.span },
            exported_macros: self.arena.alloc_from_iter(self.exported_macros),
            non_exported_macro_attrs: self.arena.alloc_from_iter(self.non_exported_macro_attrs),
            items: self.items,
            trait_items: self.trait_items,
            impl_items: self.impl_items,
            bodies: self.bodies,
            body_ids,
            trait_impls: self.trait_impls,
            modules: self.modules,
            proc_macros,
            trait_map,
        }
    }
...
}
```

この`lower_crate()`メソッドは、内部でさらに構造体やそのメソッドが定義されていて大きくなっているが、まずは`visit::walk_crate()`に注目しよう。

`rustc_ast::visit`の[リファレンス](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_ast/visit/index.html)を見ると、**AST walker**と書いてある。つまりはどういうことか？少しソースを追ってみよう。

```rust:librustc_ast/visit.rs
/// Each method of the `Visitor` trait is a hook to be potentially
/// overridden. Each method's default implementation recursively visits
/// the substructure of the input via the corresponding `walk` method;
/// e.g., the `visit_mod` method by default calls `visit::walk_mod`.
///
/// If you want to ensure that your code handles every variant
/// explicitly, you need to override each method. (And you also need
/// to monitor future changes to `Visitor` in case a new method with a
/// new default implementation gets introduced.)
pub trait Visitor<'ast>: Sized {
...
    fn visit_mod(&mut self, m: &'ast Mod, _s: Span, _attrs: &[Attribute], _n: NodeId) 
        walk_mod(self, m);
    }
...
    fn visit_item(&mut self, i: &'ast Item) {
        walk_item(self, i)
    }
...
}
...
#[macro_export]
macro_rules! walk_list {
    ($visitor: expr, $method: ident, $list: expr) => {
        for elem in $list {
            $visitor.$method(elem)
        }
    };
    ($visitor: expr, $method: ident, $list: expr, $($extra_args: expr),*) => {
        for elem in $list {
            $visitor.$method(elem, $($extra_args,)*)
        }
    }
}
...
pub fn walk_crate<'a, V: Visitor<'a>>(visitor: &mut V, krate: &'a Crate) {
    visitor.visit_mod(&krate.module, krate.span, &krate.attrs, CRATE_NODE_ID);
    walk_list!(visitor, visit_attribute, &krate.attrs);
}

pub fn walk_mod<'a, V: Visitor<'a>>(visitor: &mut V, module: &'a Mod) {
    walk_list!(visitor, visit_item, &module.items);
}
```

`walk_crate()`が呼ばれると、その中で`visit_mod()`を呼んでASTの階層をひとつ下ることになる。`visit_mod()`は`Visitor`トレイトの定義でデフォルト実装をもっており、その`walk_mod()`から`visit_item()`を呼んでさらにASTを下っていく。下るときには`walk_list!()`のマクロを使うことでリストを回す処理が簡単に書けるようになっている。このように`rustc_ast::visit`は、ASTのルートから`visit_xxx()`を経由してただひたすらにASTを下っていく。ここで、ただ下っていく`visit_xxx()`はデフォルト実装であり、`walk_xxx()`は引数としてジェネリクスである`visitor`を受け取って、そのメソッドである`visit_xxx()`を実際には呼んでいることに注意しよう。

改めて`lower_crate()`で`visit::walk_crate()`を呼んでいる箇所を見てみる。`MiscCollector`という型と`ItemLowerer`という型を`visitor`として与えており、（この記事には長くなってしまうので載せていないが、）それぞれ`impl`で`visit_xxx()`のメソッドをいくつか定義している。つまり、`rustc_ast::visit`のASTをただ下っていくデフォルト実装を使いながら、自分がカスタマイズしたいところだけ`visit_xxx()`の処理を上書きして、望むようなASTを再構築する、という使い方になっている。

さて、それを踏まえて`rustc_ast_lowering`における`visit_xxx()`の実装を読むと、AST->HIRの変換のための処理がいろいろと見て取れる。ここでは試しに、`for`をdesugarする処理を探してみよう。`ItemLowerer`の`visit_item()`から、`LoweringContext`の`lower_item()`が呼ばれ、さらに`lower_item_kind()`と呼ばれていく。ここではアイテムの種別ごとに処理が分岐していくが、`for`が使われるのは大抵の場合関数の本体内だろう。どうも`lower_maybe_async_body`に続いているようだ。

```rust:librustc_ast_lowering/item.rs
impl<'hir> LoweringContext<'_, 'hir> {
...
    fn lower_item_kind(
        &mut self,
        span: Span,
        id: NodeId,
        ident: &mut Ident,
        attrs: &'hir [Attribute],
        vis: &mut hir::Visibility<'hir>,
        i: &ItemKind,
    ) -> hir::ItemKind<'hir> {
        match *i {
...
            ItemKind::Fn(_, FnSig { ref decl, header }, ref generics, ref body) => {
                let fn_def_id = self.resolver.local_def_id(id);
                self.with_new_scopes(|this| {
                    this.current_item = Some(ident.span);

                    // Note: we don't need to change the return type from `T` to
                    // `impl Future<Output = T>` here because lower_body
                    // only cares about the input argument patterns in the function
                    // declaration (decl), not the return types.
                    let asyncness = header.asyncness;
                    let body_id =
                        this.lower_maybe_async_body(span, &decl, asyncness, body.as_deref());

                    let (generics, decl) = this.add_in_band_defs(
                        generics,
                        fn_def_id,
                        AnonymousLifetimeMode::PassThrough,
                        |this, idty| {
                            let ret_id = asyncness.opt_return_id();
                            this.lower_fn_decl(
                                &decl,
                                Some((fn_def_id.to_def_id(), idty)),
                                true,
                                ret_id,
                            )
                        },
                    );
                    let sig = hir::FnSig { decl, header: this.lower_fn_header(header) 
                    hir::ItemKind::Fn(sig, generics, body_id)
                })
            }
...
        }
    }
...
}
```

そこからいくつかの関数・メソッドを経て、`lower_expr_mut()`にたどり着く。ここで今度は、式（expression）の種別で場合分けが行われる。ソース内のコメントにもある通り`for`は当然`ForLoop`の条件に流れ着き、`lower_expr_for()`によって実際に処理されることになるようだ。各desugarの細かい処理はとりあえず興味がないので、ここではメソッドの先頭コメントのみ載せておく。

```rust:librustc_ast_lowering/expr.rs
impl<'hir> LoweringContext<'_, 'hir> {
...
    pub(super) fn lower_expr_mut(&mut self, e: &Expr) -> hir::Expr<'hir> {
        ensure_sufficient_stack(|| {
            let kind = match e.kind {
...
                // Desugar `ExprForLoop`
                // from: `[opt_ident]: for <pat> in <head> <body>`
                ExprKind::ForLoop(ref pat, ref head, ref body, opt_label) => {
                    return self.lower_expr_for(e, pat, head, body, opt_label);
                }
...
            };

            hir::Expr {
                hir_id: self.lower_node_id(e.id),
                kind,
                span: e.span,
                attrs: e.attrs.iter().map(|a| self.lower_attr(a)).collect::<Vec<_>>().
            }
        })
    }
...
    /// Desugar `ExprForLoop` from: `[opt_ident]: for <pat> in <head> <body>` into:
    /// ```rust
    /// {
    ///     let result = match ::std::iter::IntoIterator::into_iter(<head>) {
    ///         mut iter => {
    ///             [opt_ident]: loop {
    ///                 let mut __next;
    ///                 match ::std::iter::Iterator::next(&mut iter) {
    ///                     ::std::option::Option::Some(val) => __next = val,
    ///                     ::std::option::Option::None => break
    ///                 };
    ///                 let <pat> = __next;
    ///                 StmtKind::Expr(<body>);
    ///             }
    ///         }
    ///     };
    ///     result
    /// }
    /// ```
    fn lower_expr_for(
        &mut self,
        e: &Expr,
        pat: &Pat,
        head: &Expr,
        body: &Block,
        opt_label: Option<Label>,
    ) -> hir::Expr<'hir> {
...
    }
...
}
```

これでHIRへの変換まで大きな流れを追うことができた。


# つづく

ディレクトリの大幅変更というイレギュラーがあったので短くなってしまった。ただMIRの処理は難しくて苦戦しているのも事実なので、がんばります。

[本家Rustコンパイラのソースを読もうとしてみる（4）](https://qiita.com/0yoyoyo/items/752073b3b1c7e76bebb2)←次回