前回までのあらすじ

Guide to Rustc Developmentという便利なガイドに沿って、Rustの本家コンパイラであるrust-lang/rustのソースコードを読んでみようという試み。今回は「Source Code Representations」のHIRのあたりから。

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

目次（初回）

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

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

2020/8/31あたりにソースのディレクトリ構成が大きく変更されたようだ。これまでコンパイラに関係する多くのクレートはrust/src/librustc_xxxというディレクトリに存在していたが、rust/compiler/rustc_xxxというディレクトリに移動したようだ。関係する議論はこのPRと思われる。大きくはディレクトリが移動しただけで、ディレクトリの名前も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()に進んでいく。

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のリファレンスを見ると、AST walkerと書いてある。つまりはどういうことか？少しソースを追ってみよう。

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に続いているようだ。

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の細かい処理はとりあえず興味がないので、ここではメソッドの先頭コメントのみ載せておく。

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）←次回

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

前回までのあらすじ

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

Source Code Representations

ASTからHIR

つづく