Rustのモジュールを詳細に理解する(4) インポート解決

概要: Rust2018以降、Rustのモジュールシステムは入門しやすく、かつマスターしにくくなりました。そこで本記事では、その両方を達成することを目指しました。

本記事は2017年に書いた記事 (https://qnighy.hatenablog.com/entry/2017/03/27/070000, https://qnighy.hatenablog.com/entry/2017/04/24/070000 ) と同じテーマで、Rust2018を考慮して改めてまとめ直したものです。

注意: 本記事中のサンプルコードの多くは、Rustの細かい仕様や実装を調べるためのものであり、実際に有用なプログラミングパターンであるとは限りません。また、実質的にバグに近い挙動を説明しているものもあるため、将来にわたって同じ動作であることはあまり保証できません。

インポート解決とパス解決

名前解決の目標は foo::bar::baz を解決することですが、その途中でまずインポート (use) を解決する必要があります。これをインポート解決といいます。

インポート解決の中でもパスを解決する必要がありますが、この時点では use および pub(in) 内のパスだけ解決すればよいことに注意しましょう。それ以外のさまざまなパスはインポートのあとに解決されます。

use tree

use の構文は何段階かに分けて進化してきましたが、本質的には昔から変化しておらず、以下の2つしかありません。

単独別名インポート use foo::bar as baz;
- ただし、やや特殊な仕様として as _ がある (前述)
- また ::{self} がある場合は名前空間を制限する規則がある
globインポート use foo::bar::*;

たとえば、以下のuseは

use std::{
    self, fmt,
    io::{self, Read, Write as IoWrite},
    ops::*,
};

……以下のように分解することができます。 (build_reduced_graph_for_use_tree)

use std as std; // ただし、型名前空間しかインポートしない
use std::fmt as fmt;
use std::io as io; // ただし、型名前空間しかインポートしない
use std::io::Read as Read;
use std::io::Write as IoWrite;
use std::ops::*;

ただし、この展開では以下のようなケースに注意が必要です。

// 素直に展開すると無が生成され、コンパイルが通ってしまう
// unstable moduleを参照しているのでコンパイルを弾いてほしい
use std::intrinsics::{};

このようなケースではダミーインポートが生成され、それによって当該モジュールにアクセス権があることを担保しています。

禁止されるインポート形式

以下のようなインポートは形式的に禁止されています。

// 0セグメントインポートの禁止
use {self}; // error
use ::{self}; // error

// selfまたはsuperで終わるパスのインポートの禁止
use self; // error
use self as s; // error
use super; // error
use super as s; // error

// $crate自体のインポートは可能だが廃止予定
macro_rules! foo {
    () => {
        use $crate; // warning
        use $crate as s; // warning
    }
}
foo!();

// 特殊な名前のままのインポートの禁止
use crate; // error
// use crate as s; // これはOK

// 0セグメントglobインポートの禁止 (prelude glob importになるため)
use *; // error
use ::*; // error

また、trait itemのインポートと自分自身からのglobインポートは意味的に弾かれます。

trait Foo {
    fn foo();
}
use Foo::foo; // error

trait Bar {}
use Bar::*; // error

use self::*; // error

Rust2015モード

Rust2015の use ではデフォルトで絶対パスが用いられていました。この互換性の確保のために、以下の条件で :: が先頭に付与されたかのように扱われます。

グローバル2015モードである。
当該 use パスの先頭セグメントがRust2015モードのクレート由来である。
当該 use パスの先頭セグメントがキーワードではない。 (たとえば、 self:: や crate:: ではない。すでに :: で始まっている場合も除外する)

グループインポートの場合は、 {} を個別のuseに分解した状態で上の規則が適用されます。

`extern crate` の処理

extern crate の処理は簡単で、指定したクレートのルートを指定した場所に継ぎ木するだけです。

// failureクレートのルートを crate::f として継ぎ木する。
extern crate failure as f;

`use` の処理は最小不動点

extern crate に比べて、 use の処理は簡単ではありません。 use は順序よく解決されるとは限らないからです。

そのため、最初の処理ではどこにどういう use 指令があったかだけ覚えておいて、最小不動点アルゴリズムにより可能な部分から解決していきます。

// (2)→(1) の順で解決する必要がある

use m1::A; // (1)
mod m1 {
    pub use crate::m2::A; // (2)
}
mod m2 {
    pub struct A;
}

以下では、このことを念頭に置きつつ話を進めていきます。

単独別名インポートの解決

単独別名インポートの規則は比較的簡単ですが、名前空間についてだけ気をつけることがあります。 use A as B は、

それぞれの名前空間で A が利用可能か調べ、利用可能だったら B として継ぎ木する。
- ただし例外として、 use foo::bar::{self}; 形式のインポートの場合は foo::bar の型名前空間しかインポートしない。
どの名前空間でも利用不可能だったらエラー。

このような仕様のため、 use を単に使うだけでは特定の名前空間をインポートするのは不可能です (トリッキーな方法で実現可能)

// 型としてのSerializeとderiveマクロとしてのSerializeを両方インポートする
use serde::Serialize;

// モジュールとしてのenvとマクロとしてのenvを両方インポートする
use std::env;

また、 use foo::bar as baz; という指定があったとしても、各名前空間で self::baz が利用可能になるかどうかはこの時点では確定していないことになります。「あとでなかったらエラーにするから」という理由で、先行して self::baz が存在することを仮定して処理を進めることはできないというわけです。

globインポートの解決

globインポートはより複雑な仕様を持っています。(RFC1560にその経緯などが書いてあります。) use A::*; は以下のように処理されます。

A 直下にある利用可能な全ての名前空間・名前をインポートする。
ただし、globインポート以外の定義がすでに存在したら、そちらが優先される。
globインポート同士で衝突した場合は、個別に以下のルールで仲裁される。
- 同じDefを指していたら両方有効 (より可視性の広いほうが採用される)
- 違うDefを指していた場合は「曖昧」という特別な状態になる
  - 曖昧状態になったバインディングは、それを使おうとしたときにエラーになる
  - 曖昧状態はさらなるglob importによって引き継がれる
該当がなかった場合 (e.g. 空モジュールのインポート) でもエラーにはならない

fn main() {
    {
        // glob importは優先度が低い
        use std::sync::*;
        use std::rc::{Rc, Weak};
        let x: Weak<i32>; // OK
    }
    {
        // glob import同士は競合する
        use std::sync::*;
        use std::rc::*;
        let x: Weak<i32>; // ERROR
    }
    {
        // 複数のglob importが同じDefに解決される場合はOK
        use core::cell::*;
        use std::cell::*;
        let x: Cell<i32>; // OK
    }
}

最小不動点 アルゴリズム

これらの条件を踏まえつつ、実際には解決途中の状態も考慮に入れながら処理しています。たとえば、以下のようなコードを考えます。

use crate::m1::f::X;

fn main() {
    dbg!(X);
}
pub fn f() {}

mod m1 {
    pub use crate::m2::f;
    pub use crate::m3::*;
}
mod m2 {
    pub use crate::f;
}
mod m3 {
    pub mod f {
        pub const X: i32 = 42;
    }
}

最初の行の crate::m1::f::X を解決するためには、型名前空間で crate::m1::f を解決する必要があります。これの候補は2つあります。

m1 内の pub use crate::m2::f;
m1 内の pub use crate::m3::*;

この2つのうちどちらに解決されるかは、前者がどの名前空間でインポートされるかに依存します。 m2 の中身を見ても pub use crate::f; としか書いていないので、そのためにはさらに遡って crate 直下の f がどの名前空間に存在するかを知る必要があります。

このように、インポートの解決順序はあまり自明ではありません。そこで、名前解決のさいは「現状どこまで判明しているのか」を正確に表現しつつ、次に確実にわかることを順番に探していきます (最小不動点)。

モジュール木の構築とインポート文の管理

前述のように、名前解決の最初の処理はモジュール木の構築です。これのメインの処理は build_reduced_graph_for_item です。

たとえば、定数 const X: i32 = 42; の処理は比較的簡単です。これは define メソッドを呼ぶことでモジュールにDefを紐付けることができます。

これによって Module が作られます。Moduleの主要なデータは以下の通りです。

親リンク (parent), 子リンク (resolutions), 正規祖先リンク (normal_ancestor_id)
- 匿名モジュールは親リンクを持つが、親からの子リンクを持たない
このモジュールを入力とするglobインポートの一覧 (glob_importers)
このモジュールを出力とするglobインポートの一覧 (globs)

build_reduced_graph_for_item によって、

通常の定義はそのまま resolutions に紐付けられます。
use foo::bar; や extern crate も resolutions に紐付けられます。
use foo::*; は globs に紐付けられます。

use foo::bar; をこの時点で resolutions に紐付けていいのは NameResolution にそれを表現するための仕組みがあるからです。 resolutions 自体は識別子と名前空間からNameResolutionを引くマップですが、そのNameResolutionは以下のような定義になっています。

#[derive(Clone, Default, Debug)]
/// Records information about the resolution of a name in a namespace of a module.
pub struct NameResolution<'a> {
    /// Single imports that may define the name in the namespace.
    /// Import directives are arena-allocated, so it's ok to use pointers as keys.
    single_imports: FxHashSet<PtrKey<'a, ImportDirective<'a>>>,
    /// The least shadowable known binding for this name, or None if there are no known bindings.
    pub binding: Option<&'a NameBinding<'a>>,
    shadowed_glob: Option<&'a NameBinding<'a>>,
}

つまり、 NameResolution は単に最終的な解決結果ではなく、「暫定2位までの解決結果」と「この名前を定義しうる単独別名インポートの一覧」を保持しています。なので、 binding が存在していても、これがglobインポート由来かつ他に単独インポートが存在するかもしれない場合はこの結果は確定ではないということになります。

最小不動点ループ

最小不動点処理のエントリーポイントは ImportResolver::resolve_imports にあります。ここでは以下のような処理をしているわけです。

上に挙げたデータ構造とは別に、解決済みインポートの一覧と未解決インポートのキューをグローバルに保持しておく。はじめは全て未解決扱いである。
一回のループで、未解決インポートの解決を順番に試みる。
未解決インポートの個数が減ったらループを継続し、減らなかったら収束とみなして停止する。

では、インポートが未解決というのはどういう状態でしょうか。

まず第一に、インポート元のモジュールがそもそも確定していない場合があります。たとえば、 use foo::bar::baz as hoo; を処理するためにはまず foo::bar が何であるかが確定している必要がありますが、この foo や bar 自体が use 由来かもしれず、その場合は手のつけようがありません。これが確定すると imported_modules というフィールドに保存されます。

globインポートの場合、この時点でglobインポート自体は必ず「解決」扱いになります。というのも、globインポート自体の「解決」は基本的には以下の2つの処理を(この順番で)するだけだからです。

インポート元モジュールの glob_importers に当該インポート指令を追加する。 (→今後同期されることを保証)
インポート元モジュールでこの時点で解決済みになっているDefを列挙し、インポート先に継ぎ木する。 (→過去分の同期を完了させる)

その後の処理はインポート元モジュールが変化したタイミングでの glob_importers によるフックに移譲されます。

一方、単独別名インポートの場合は、3つの名前空間それぞれでインポートの可否を調べ、3つの結果がすべて確定した時点で解決済みになります。「この名前空間ではインポートできるかもしれないし、できないかもしれない」というものが残っているうちは未解決です。

また、マクロ展開に由来する未解決状態も考えられますが、これはまた話がややこしくなるので別途説明します。

通常の `use` 以外のインポート指令

上のアルゴリズムで、インポート解決の単位となっていたインポート指令は ImportDirective および ImportDirectiveSubclass として定義されています。これを見ると通常の use も含めてインポート解決によって解決されるものは以下のものがあることがわかります。

通常の単独別名インポート (use foo::bar as baz;)
::{self} 形式の単独別名インポート (use foo::bar::{self} as baz;)
- この場合は、型名前空間のみがインポートされる。
通常のglobインポート (use foo::* as baz;)
prelude用のglobインポート
- モジュールに #![no_prelude] がない場合は #[prelude_import] use std::prelude::v1::*; が追加される。
- この形のインポートは実際にはインポート解決されず、かわりにパス解決で処理するためにモジュールをメモしておく。
extern crate によるインポート
- インポート解決では使われない。
- rustfix用？
#[macro_use] extern crate によるインポートのマクロ部分
- インポート解決では使われない。
- rustfix用？

モジュール解決のファイナライズ

最小不動点アルゴリズムは、解決可能なものを処理した時点で停止します。この時点では必要なものがすべて解決されたかはわからないので、finalize_imports メソッドでそれを確認しています。

まとめ

use 自体の仕様が、グロブのシャドウイングや名前空間の違いに由来する複雑さを抱えています。その上、インポート解決はuse の解決を順序不定で行う必要があり、そのためにRustコンパイラは、「どこまでが既に判明しているのか」という状態を慎重に更新しながら適切に状態を更新し続けるという難しい処理を実装しています。

次回は可視性について扱います。可視性はインポート解決の動作にかかわっているものの、いったん可視性抜きで説明できることが多かったので分割しました。