概要: Rustの名前解決の詳細について解説する。本記事では、インポート解決について説明する。

名前解決のタイミング

コンパイラの名前解決に関するコードを探す上で重要な点のひとつは、「 use や extern crate などの主要な構文要素は対応するHIRの要素をもつにもかかわらず、これらはloweringの前に解釈される」という点である。ASTからHIRへの変換で最も大きな仕事の一つが名前解決だから、ASTの時点で use が解釈させることは当たり前なのだが、それにもかかわらず use に対応するHIRの要素があるのは、おそらくdocの生成などで用いられるためである。

モジュール構造

Rustの名前解決において最も中心的な役割を果たすデータ構造はモジュール構造である。これは rustc_resolve::ModuleData で定義されている。

/// One node in the tree of modules.
pub struct ModuleData<'a> {
    parent: Option<Module<'a>>,
    kind: ModuleKind,
    ...
    resolutions: RefCell<FxHashMap<(Ident, Namespace), &'a RefCell<NameResolution<'a>>>>,
    ...
    glob_importers: RefCell<Vec<&'a ImportDirective<'a>>>,
    globs: RefCell<Vec<&'a ImportDirective<'a>>>,
    ...
}

ModuleData に含まれる rustc_resolve::resolve_imports::NameResolution と rustc_resolve::NameBinding と rustc_resolve::resolve_imports::ImportDirective も重要である。

pub struct NameResolution<'a> {
    /// The single imports that define the name in the namespace.
    single_imports: SingleImports<'a>,
    /// The least shadowable known binding for this name, or None if there are no known bindings.
    pub binding: Option<&'a NameBinding<'a>>,
    shadows_glob: Option<&'a NameBinding<'a>>,
}

pub struct NameBinding<'a> {
    kind: NameBindingKind<'a>,
    ...
    vis: ty::Visibility,
}
...
enum NameBindingKind<'a> {
    Def(Def),
    Module(Module<'a>),
    Import {
        binding: &'a NameBinding<'a>,
        directive: &'a ImportDirective<'a>,
        used: Cell<bool>,
        legacy_self_import: bool,
    },
    Ambiguity {
        b1: &'a NameBinding<'a>,
        b2: &'a NameBinding<'a>,
        legacy: bool,
    }
}

pub struct ImportDirective<'a> {
    ...
    pub subclass: ImportDirectiveSubclass<'a>,
    ...
    pub vis: Cell<ty::Visibility>,
    ...
}

...

pub enum ImportDirectiveSubclass<'a> {
    SingleImport {
        target: Ident,
        source: Ident,
        result: PerNS<Cell<Result<&'a NameBinding<'a>, Determinacy>>>,
        type_ns_only: bool,
    },
    GlobImport {
        is_prelude: bool,
        max_vis: Cell<ty::Visibility>, // The visibility of the greatest reexport.
        // n.b. `max_vis` is only used in `finalize_import` to check for reexport errors.
    },
    ExternCrate,
    MacroUse,
}

以上をまとめると以下のようになる。

use/extern crate を無視すると、モジュールは森構造をなす。 use/extern crate を考慮するとグラフ構造になる。
各モジュールは、そのモジュールから辿れる名前の一覧を所有している。これは以下の4種類のうちのいずれかである。
- 通常の定義 (fn, static, const, struct, enum など)
- mod で定義された子モジュール
- use によるインポート
- 複数の候補がありうる場合
* によるインポートははじめそのままの形で管理されており、インポート解決が進行するにつれて binding として解決されていく。

インポート解決の仕事

インポート解決の目的は、以下の内容を把握することである。

各モジュールが、どのような名前を子供として持っているか。
それが定義ではなくインポートだった場合は、その参照先。

これらの困難は基本的に * によるglob importに由来する。これのせいで、子供の一覧を一発で収集することができないのである。

例えば、以下のように、 2段階のglob importで間接的にインポートされる場合がある。

mod m1 {
    pub use m2::*;
}
mod m2 {
    pub use m3::*;
}
mod m3 {
    pub const X : u32 = 0;
}

fn main() {
    println!("{}", m1::X);
}

また以下の例では、 use m2::* が解決されるまでは、 self::m4 の実体がどこにあるのかわからない。

mod m1 {
    pub use self::m4::X;
    pub use m2::*;
    pub use m3::*;
}
mod m2 {
    pub mod m4 {
        pub const X : u32 = 0;
    }
}
mod m3 {
    pub mod m5 {
        pub const X : u32 = 1;
    }
}

fn main() {
    println!("{}", m1::X);
}

このようにちょっとだけ複雑なglob importを解決するのが、インポート解決の主な仕事である。

インポート解決のメインループ

Rustコンパイラのインポート解決のアルゴリズムは単純で、「できるところから解決していって、何もできなくなったら停止する」である。 (rustc_resolve::resolve_imports::ImportResolver::resolve_imports)

    /// Resolves all imports for the crate. This method performs the fixed-
    /// point iteration.
    pub fn resolve_imports(&mut self) {
        let mut prev_num_indeterminates = self.indeterminate_imports.len() + 1;
        while self.indeterminate_imports.len() < prev_num_indeterminates {
            prev_num_indeterminates = self.indeterminate_imports.len();
            for import in mem::replace(&mut self.indeterminate_imports, Vec::new()) {
                match self.resolve_import(&import) {
                    true => self.determined_imports.push(import),
                    false => self.indeterminate_imports.push(import),
                }
            }
        }
    }

典型的な不動点計算アルゴリズムといってもよい。

ここで中心的な役割を果たす変数は以下の4つである。

globs … ソースコード中に実際に書かれているglob import命令の一覧である。
determined_imports … glob import命令のうち、解決済みのもの(これ以上処理しなくてよいもの)の一覧である。
indeterminate_imports … glob import命令のうち、未解決のもの(まだ処理が必要なもの)の一覧である。これはさらに二種類に分けられる。
- インポート元のモジュールがどこか判明していないもの。
- インポート元のモジュールは判明しているが、そのモジュールにある名前がまだ増えるかもしれないもの。
glob_importers … glob import命令のうち、インポート元までは判明しているもの。

resolve_imports は、 indeterminate_imports に入っているglob importを一つずつ取り出して、 resolve_import を試す。これは以下の処理を行う。

まず、そのglob importのインポート元のモジュールの解決を試みる。
成功したら、 glob_importers にそれを追加する。さらに、インポート元の全ての名前が列挙済みかを調べる。
列挙済みなら、それらを全てインポート先にも束縛して、成功とする。そうでなければ失敗する。(失敗でも、列挙できた名前はすべて追加する)

この処理が進むにつれて、 indeterminate_imports が減っていく。これが減らなくなった時点で終了とする。もちろん、未解決のインポートが残っている場合はどこかにエラーがある。

インポートの優先度

glob importは他の定義と比べて優先度が低く、特定のルールでシャドウされる。(rustc_resolve::resolve_imports::ImportResolver::try_define)

glob importと、glob import以外の定義がある場合、glob import以外の定義が優先される。
- マクロ名前空間についてはこの優先規則が適用されない場合がある。
glob import以外の定義が2つあるときは、エラーになる。
glob import由来の同名の定義が2つあるときは、それぞれのimportを辿ったときのDefIdが比較される。等しければ特に問題はない。等しくない場合はambiguousとなり、使った時点でエラーになる。DefIdはNodeIdに由来するので、だいたい「同じ定義ならglobで二重importしてOK」と思えばよい。
- DefIdが等しいが、2つのglob importの可視性が異なる場合は、可視性の高いほうが優先される。

まとめ

ここまでで、Rustのどのモジュールに何があるかがわかるようになった。

簡潔なQ

Rustの名前解決(2/5) インポート解決

名前解決のタイミング

モジュール構造

インポート解決の仕事

インポート解決のメインループ

インポートの優先度

まとめ