RustのジョークRFC

Rustでは言語仕様に対する大きな変更はまずRFCという形で投稿し、十分に検討をしながらコンパイラに組み込むことになっている。(これはIETF RFCとは同名だが別のもので、 Rust RFCsで管理されている。Python PEPsと似たような仕組みといえる。)

先日、Rust RFCsに不可解なRFCが投稿されており、大変不思議に思っていたら、エイプリルフールのジョークだったようだ。調べてみたところ、少なくとも去年と今年はジョークRFCが投稿されているようだ。

• 2017年 Rust RFC 1963: Higher and Lower Types (“Omega Types”)
• 2016年 Rust RFC 1565: Emoji Based Error Handling

ハッシュベースの署名(公開鍵署名)を書いてみた

Post-Quantum Cryptography, Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Springer-Verlag Berlin Heidelberg, 2009の冒頭部で、ごく簡単なハッシュベースの署名アルゴリズムが紹介されていて感動したのを思い出したので書いてみた。

コードは長いので一番下に載せる。

概要

これは、堅牢なハッシュ関数を用いて、整数論的な何かに頼らなくても、署名を実現できるというものである。

ハッシュで署名というと、HMACが連想されるが、MACと署名は微妙に異なる。簡単に言うとMACが共通鍵で署名が公開鍵のものを指す。

仕組み

Lamport–Diffieのワンタイム署名という部品をベースにしている。これは、大量のハッシュ値を公開鍵として渡しておき、署名をするときは、その一部の元データを開示するというものである。元データを知っているのは自分だけだから、「どのデータを開示するか」は自分にしか決定できないことであり、この選択とメッセージのダイジェストを対応づけることでメッセージに署名をしたことにする。

この方法は明らかに、同じ鍵で2つ以上のメッセージに署名をすると破綻するという欠点がある。それがワンタイム署名と呼ばれる所以である。そこで、署名をチェインさせることで複数回の署名をできるようにするというのがこのハッシュベース署名の考え方である。

「署名をチェインさせる」と聞いた時点で「多分こんなんだろう」と思って実装したのが以下にある(あとから考えると、ちゃんと最後まで読んでから考えるべきであった)。そういうわけなのでこのプロトコルが本当に安全かはよくわからない。

今回は、各ワンタイム鍵は、「別のワンタイム公開鍵2つ」を署名するか、または実際のメッセージを署名するものとして、ワンタイム鍵からなる二分木を動的に生成するようにしてみた。チェインの長さは32で固定にしたので、最大2³²個のメッセージを署名できる。

二分木にするというアイデア自体は当然既存のもののようで、Merkle Treeなどがあるようだ。ただMerkle Treeはパッと説明を見た限り、2^H個のデータブロックを最初に生成するようなので、少し違うものという気がする。この辺りはもう少し調べる必要がありそうだ。

欠点

プロトコル部分は筆者の想像で書かれたものなので、筆者が気付いていない問題があるかもしれない。

それ以外の問題点としては、

• 鍵がとても大きい。 (これは、より効率的なワンタイム署名を使えば改善されるのかもしれない)
  • これは木をランダムに掘っていることにも由来している。左から順番に掘れば、秘密鍵の膨張は抑えられるが、何回署名をしたかがわかってしまう。
• 秘密鍵を丸ごとコピーするなどして、別々のコンピューターで独立して運用すると、安全でなくなる。

以下に示す実装の利用例

$ ls
hashsign.py lipsum2.txt lipsum.txt
$ python3 hashsign.py keygen
$ ls
hashsign.py id_hash id_hash.pub lipsum2.txt lipsum.txt
$ python3 hashsign.py sign < lipsum.txt > lipsum.txt.asc
$ ls
hashsign.py id_hash id_hash.pub lipsum2.txt lipsum.txt lipsum.txt.asc
$ python3 hashsign.py verify -s lipsum.txt.asc < lipsum.txt
Verification succeeded
$ python3 hashsign.py verify -s lipsum.txt.asc < lipsum2.txt
Verification failed

実装

Python3で書かれている。

gist.github.com

Rustの単一実装トレイトパターン

概要: ただ一つの実装をもつトレイトを定義するデザインパターンでできることとデメリットを紹介する。「単一実装トレイトパターン」という名前は今考えたもので、他に名前があるかもしれない。

既存の型や既存のトレイトにメソッドを追加する

Rubyというプログラミング言語では、既存のクラスにメソッドを追加できる。InfoQの2008年の記事がわかりやすい。

単一実装トレイトパターンを使うと、Rustで同じことができる。

// 文字列にfooメソッドを追加する
pub trait FooMixin {
    fn foo(&self);
}
impl FooMixin for str {
    fn foo(&self) {
        println!("foo {}", self);
    }
}
fn main() {
    "hoge".foo();
}

Rubyのオープンクラスと異なり、Rustのこれは非常に保守的である。

• メソッドの追加はできても、既存のメソッドの置き換え(モンキーパッチ)はできない。
• この方法で追加したメソッドを使うには、 FooMixin がuseされた状態でないといけない。

このため、既存のプログラムの動作に遡って影響を与えることはないし、名前の衝突も回避しやすい。

特定の型だけではなく、トレイトに対してメソッドを追加することもできる。後出しのmixinのようなことができる。

// AsRef<str>にfooメソッドを追加する
pub trait FooMixin : AsRef<str> {
    fn foo(&self);
}
impl<T: AsRef<str>> FooMixin for T {
    fn foo(&self) {
        println!("foo {}", self.as_ref());
    }
}
fn main() {
    "hoge".foo();
}

これに関してもRustは保守的に振る舞うため、モンキーパッチの恐怖に怯える必要がない。

既存の型や既存のトレイトにメソッドを追加する の問題点

上記コードは、以下のコードをメソッドチェインで書けるようにしたに過ぎない。

// 文字列にfooメソッドを追加する(メソッドチェインしない版)
pub fn foo(this: &str) {
    println!("foo {}", this);
}
fn main() {
    foo("hoge");
}

ドット記号でメソッドチェインできなくなるが、それを除けば、普通の関数として実装するほうが手間もかからず、余計なトレイトと謎のデザインパターンを導入せずにすむ。

final methodを定義する

Rustのトレイトはデフォルト実装をもつことができる。Javaで例えるなら、多重実装できるという点ではinterfaceに近く、デフォルト実装をもつことができるという点ではabstract classに近い。

pub trait Order {
    fn unit_price(&self) -> u32;
    fn number(&self) -> u32;
    fn total_price(&self) -> u32 {
        self.unit_price() * self.number()
    }
}

pub struct DiscountedApple;
impl Order for DiscountedApple {
    fn unit_price(&self) -> u32 { 30 }
    fn number(&self) -> u32 { 3 }
    fn total_price(&self) -> u32 { 80 }
}

ただし、デフォルト実装は上記のように上書きできてしまう。Javaでいうところのfinal methodのように、上書きできない実装を提供するなら、次のようにすればよい。

pub trait Order {
    fn unit_price(&self) -> u32;
    fn number(&self) -> u32;
}
pub trait OrderExt : Order {
    fn total_price(&self) -> u32;
}
impl<T: Order> OrderExt for T {
    fn total_price(&self) -> u32 {
        self.unit_price() * self.number()
    }
}

struct DiscountedApple;
impl Order for DiscountedApple {
    fn unit_price(&self) -> u32 { 30 }
    fn number(&self) -> u32 { 3 }
    // fn total_price(&self) -> u32 { 80 } // Error
}

上のように書いて、 OrderExt をuseしておくと、 total_price が使える。

final methodを定義する の問題点

「既存の型や既存のトレイトにメソッドを追加する」と同様、ドット記号でのメソッドチェインが不要なら、関数で同じことができる。もちろん、トレイトを増やすこと自体が無駄な複雑性といえる。

そもそも、デフォルト実装の上書きをどうしても禁止したい理由があまりない。以下のように、パフォーマンス上の利点もおそらくない。

まず、トレイトを静的ディスパッチで使う場合。この場合、どちらの方法を使っても、 total_price に対応するコードが別途生成される(または、インライン化される)という点は変わらない。どの実装が使われるかは全てコンパイル時に解決されるから、最適化の妨げになるとも思えない。

次に、トレイトを動的ディスパッチで(つまり、trait objectとして)使う場合。この場合、まずvtableの大きさの違いがある。しかしvtableはコンパイル時に生成されるし、ちょっと長いからといって急激にアクセス効率が悪くなるとはあまり思えない。次に、関数ポインタによる間接呼び出しの回数が増えるというのが考えられる。それによる効率定価は実際にありえる。しかしその程度の難しい差が重要なら、そもそも間接呼び出しをなくすという方向で考えたほうがいいかもしれない。

まとめ

上記コードは、以下のコードをメソッドチェインで書けるようにしたに過ぎない。

// 文字列にfooメソッドを追加する(メソッドチェインしない版)
pub fn foo(this: &str) {
    println!("foo {}", this);
}
fn main() {
    foo("hoge");
}

ドット記号でメソッドチェインできなくなるが、それを除けば、普通の関数として実装するほうが手間もかからず、余計なトレイトと謎のデザインパターンを導入せずにすむ。

Rustの名前解決(5/5) 可視性判定

概要: Rustの名前解決の詳細について解説する。本記事では、解決された名前の可視性判定について説明する。

1. 名前解決にかかわる構文
2. インポート解決
3. パス解決
4. メソッド記法とメンバ変数と関連アイテムの解決
5. 可視性判定

可視性

Rustの可視性は ast::Visibility, hir::Visibility, ty::Visibility で管理される。 ty::Visibility が最終なのでこれを見ると、次のようになっている。

#[derive(Clone, Debug, PartialEq, Eq, Copy, RustcEncodable, RustcDecodable)]
pub enum Visibility {
    /// Visible everywhere (including in other crates).
    Public,
    /// Visible only in the given crate-local module.
    Restricted(DefId),
    /// Not visible anywhere in the local crate. This is the visibility of private external items.
    Invisible,
}

これらはASTからHIRに変換されたあと、HIRからTyに変換されるが、インポート解決の段階ではHIRをバイパスして直接Tyに変換する。

特に、ソースコード中に書いた可視性指定は以下のように変換される。

• pub と書いた場合、 Public になる。
• 何も指定しなかった場合、そのアイテムの親モジュールの子孫に制限される。 (Restricted)
• pub(in path::to::module) の場合、指定したモジュールの子孫に制限される。 (Restricted)
• pub(self) と pub(super) は pub(in self), pub(in super) と同じ。 (Restricted)
• pub(crate) は、そのアイテムが所属するcrateのトップレベルモジュールの子孫に制限される。 (Restricted)

Invisible は内部的に利用される。

可視性の2つのプリミティブ

ty::Visibility には is_accessible_from と is_at_least という2つのメソッドが定義されている。

• vis.is_accessible_from(module, tree) は、 module にあるアイテムから可視性 vis のアイテムが見えるかどうかを返す。
• vis1.is_at_least(vis2, tree) は、 vis1 の可視範囲が vis2 を含んでいるかどうかを返す。

tree には、モジュールのなす木構造データを渡す。これは、コンパイルの段階に応じて使い分けるために、 DefIdTree というトレイトで抽象化されている。

可視性は木構造をもとに判定される。つまり、useの有無自体は可視性の範囲には関係なく、もともとのモジュールの親子関係により、可視性が判定される。

この2つのプリミティブを組み合わせて、プログラムが可視性を守っているかを以下のように調べる。

可視性に関する5つの判定

可視性判定は大きく5つに分類できる。

• アイテム参照の可視性判定
• 自分を含んでいるかどうか
• glob importの判定
• 再エクスポートの可視性判定
• 「公開インターフェース中の非公開型」の判定

アイテム参照の可視性判定

最も基本となる判定である。使おうとしたアイテムが、自分のいるモジュールから見えないアイテムだった場合には、エラーになる。これは型や関数などだけではなく、パスの途中に出現するモジュール名に対しても個別に判定される。

この処理は主に resolve_ident_in_module で行われている。参照しようとした名前が is_accessible でなければ、エラーになる。

inherent implのメソッド構文、inherent implのUFCS構文、トレイトメソッド呼び出し、構造体のメンバ参照、タプル構造体のメンバ参照、構造体またはタプル構造体の初期化とパタンーマッチにおけるメンバの可視性はそれぞれ別の場所で処理されている。

自分を含んでいるかどうか

pub(..) を使うと、自分自身から不可視なアイテムが構文上定義できるが、これは resolve_visibility 内で禁止されている。

glob importの判定

use foo::*; のようなglob importでは、インポート側モジュールから不可視なアイテムはインポートされない(したがって、他に同じ名前がインポートされていた場合、それがglob importであっても、衝突しない)。

resolve_glob_import と update_resolution 内で、この判定が行われている。

再エクスポートの可視性判定

可視性が指定された use は「再エクスポート」と呼ばれる。再エクスポートで、元のアイテムに指定されていた可視性を広げることはできない。これはfinalize_import内でチェックされている。

enumのバリアントの再エクスポートについては別途 finalize_resolutions_in でチェックされている。

また、追加の制約として、glob reexportでは、reexport自体の可視性が、実際にreexportされたアイテムの可視性の最大値と一致しないといけない。ただしこの制約は、glob reexportが実際には1つもexportできなかった場合には適用されない。

「公開インターフェース中の非公開型」の判定

“PRIVATE IN PUBLIC” とも呼ばれる。各種アイテムのインターフェース部分に、そのアイテム自身の可視性より狭い型などが出現してはいけない。例えば、公開されている関数の戻り値型が非公開な型を使っていたら、エラーになる。これを調べているのがPrivateItemsInPublicInterfacesVisitor である。

アイテムのどの部分が「インターフェース」とみなされるかは、個別的に指定されている。

• const, static, fn, type は、そのジェネリックス束縛、 where 束縛、その型や戻り値型が「インターフェース」とみなされる。
  • ただし、 impl Trait が出現する場合、その impl Trait 自身の実体の可視性は検査されないが、 Trait の可視性は検査される。
• trait はジェネリックス束縛と where 束縛が検査される。
• enum はそのジェネリックス束縛と where 束縛と各バリアントの各フィールドの型が検査される。
• struct, union は、そのジェネリックス束縛と各フィールドの型が検査される。
  • ただし、フィールドごとの可視性が考慮される。
• impl T { .. } は、そのジェネリックス束縛と where 束縛とimpl内の各アイテムが検査される。
  • ただし、 impl 自身の可視性は、中に含まれているアイテムの可視性のうち最小のものとして定義される。
• impl Trait for T { .. } は、そのジェネリックス束縛と where 束縛とimpl内の各アイテムが検査される。
  • ただし、 impl 自身の可視性は、中に含まれているアイテムの可視性と実装対象のトレイトの可視性のうち最小のものとして定義される。

まとめ

Rustの可視性は一見すると不可解な挙動をすると感じられるかもしれないが、この5回で見てきたように名前解決の仕組みから順番に紐解いていけば、それなりにきちんと把握できる範囲におさまる。とはいうものの規則自体が単純ではないため、知らない規則に振り回されないようにするには、このように可能な限り網羅的に調べあげるほかない場合もある。

Rustの名前解決(4/5) メソッド記法とメンバ変数と関連アイテムの解決

概要: Rustの名前解決の詳細について解説する。本記事では、型情報を必要とする名前の解決を説明する。

1. 名前解決にかかわる構文
2. インポート解決
3. パス解決
4. メソッド記法とメンバ変数と関連アイテムの解決
5. 可視性判定

曖昧性が生じる例

この記事で扱うのは、型情報がないと曖昧性があるような名前の解決である。まずは例を挙げる。

メソッド記法は以下のような曖昧性がある。

trait Foo {
    fn f(&self) { println!("Foo"); }
}
trait Bar {
    fn f(&self) { println!("Bar"); }
}
struct A;
impl Foo for A {}

fn main() {
    let x = A;
    x.f();
}

この例では、 A::f() が Foo::f と Bar::f のいずれを指しているかを決定するために、 x の型を決定した上でトレイト実装を検索する必要がある。

メンバ変数は以下のような曖昧性がある。

struct A {
    m: u32,
}
struct B {
    m: u16,
}

fn main() {
    let x = A { m: 0 };
    println!("{}", std::mem::size_of_val(&x.m));
}

この例では、 x.m が A と B のどちらのメンバ変数 m であるかを決定するために、 x の型を決定する必要がある。

関連型(関連アイテムの一種)は以下のような曖昧性がある。

trait Foo {
    type X;
}
trait Bar {
    type X;
}

fn f<T:Foo>() { println!("{}", std::mem::size_of::<T::X>()); }
fn g<T:Bar>() { println!("{}", std::mem::size_of::<T::X>()); }

struct A;
impl Foo for A {
    type X = u16;
}
impl Bar for A {
    type X = u32;
}

fn main() {
    f::<A>();
}

この例では、 T::X が <T as Foo>::X なのか <T as Bar>::X なのかを決定するために、 T のtrait boundを参照する必要がある。

メソッド(関連アイテムの一種)は以下のような曖昧性がある。

trait Foo {
    fn f() { println!("Foo"); }
}
trait Bar {
    fn f() { println!("Bar"); }
}
struct A;
impl Foo for A {}

fn main() {
    A::f();
}

この例では、 A::f() が Foo::f と Bar::f のいずれを指しているかを決定するために、トレイト実装を検索する必要がある。

トレイトの列挙

以下に挙げる名前解決のうちの一部では、「スコープ内にある利用可能なトレイト」の一覧を出す必要のあるものがある。この処理は、assemble_extension_candidates_for_traits_in_scopeで行われている。この一覧は、 def_map と同様の trait_map という変数に計算済みのものがあり、これを取り出している。

trait_map の計算は rustc_resolve::Resolver::get_traits_containing_item で行われている。これによると、検索範囲は

• 自身のいるモジュール
• 自身のいるモジュールの祖先
• prelude (明示的に除外しない限り)

であることがわかる。

この中で、 所望の識別子を含んでいるトレイトのみが、 trait_map に追加されている。

所望の識別子を含んでいても、もとの型がそのトレイトを実装していなければ採択されない。この処理は consider_candidates 内の consider_probe で行われている。

pick_methodによると、上記の条件を満たしたトレイトが複数あると基本的にエラーになる。ただし、inherent implとtrait implで衝突した場合は、inherent implが優先される。

メソッド記法の解決

メソッド記法の解決はやや複雑であり、「名前解決」から離れる面もあるためこの記事では深入りしない。メソッド記法を処理する部分のREADME にそれなりに説明がある。

要点は、自動デリファレンスと自動リファレンスやunsizingなどの自動変換によりいくつかの候補となる型が生成され、それらに優先順位がつけられる。それぞれの型について、上に挙げたようなトレイトの検索が行われる。

メンバ変数の解決

rustc_typeck::check の check_field で解決される。これが呼ばれた時点で、もとの構造体の型が判明していると仮定している。

関連型の解決

関連型の解決はrustc_typeck::astconv::AstConv::ast_ty_to_tyで行われる。ここではまず、 <QSelf>::AssocTyp における <QSelf> が、解決済みのパスであることをチェックしている。解決済みのパスならば、紐づけられた Def を取得する。

その後、 rustc_typeck::astconv::AstConv::associated_path_def_to_ty に処理がうつる。ここでは、得られた <QSelf> のDefによりさらに条件分岐している。コメントにある通り、ここで出てくる <QSelf> は実は Self か型パラメーターでなければならない。

Self や型パラメーターの場合は、このパラメーターが導入された箇所で、 where 等によるtrait boundが与えられているはずなので、そこからtraitを検索する。所望の関連型を所有しているトレイトがちょうど1つあれば、それを答えとする。

メソッドの解決

型以外の関連ジャイテムの解決は rustc_typeck::check::resolve_ty_and_def_ufcs で行われる。この処理はさらに rustc_typeck::check::method::probeのprobe_for_name に移譲される。あとは上で説明したように、該当する実装が1つあったときだけ採用される。

まとめ

Rustの識別子の中には、型に依存して解決されるものがある。これらは比較的アドホックな方法で解決されており、型の明示が必要な原因のひとつになっていると思われる。

Rustの名前解決(3/5) パス解決

概要: Rustの名前解決の詳細について解説する。本記事では、パス解決について説明する。

1. 名前解決にかかわる構文
2. インポート解決
3. パス解決
4. メソッド記法とメンバ変数と関連アイテムの解決
5. 可視性判定

パス解決とは

Rustで foo::bar のようにパスを書いたとき、これが具体的にどこで定義されているどのアイテムの、どの特殊化を指すのかは、自明ではない。これを確定させるのがパス解決である。パス解決が行われると、パスは Def や Ty に紐付けられる。これにより、インポートによる曖昧性がなくなる。

PathとQPath

パスはhirの Path または QPath に解決される。

Path は例えば、 std::vec::Vec<T> のような通常のパス(型パラメーターを含んでもよい)である。一方 QPath はこれに加えて、 <BufReader<R> as Read>::read のように、Selfが関係するアイテムも含んでいる。

特に、型に関連づけられているがトレイト情報のないアイテムはlowering時点のパス解決では完全には解決できず、型検査の後に解決される。

パス解決のタイミング

次のような順番でパスが解決される。

• use は、インポート解決中に同時に解決される。
• loweringの前に、アイテム定義(関連アイテム以外)までのパスの解決が行われ、def_mapが構築される。
• lowering時に、パスが定義部分と関連アイテム部分に分割され、 Path または QPath に解決される。
• 型検査後に、関連アイテムが解決される。

use の解決

インポート解決中に、resolve_import が resolve_path を呼び出している。これにより、 use のパスが解決される。

def_map の作成

lowering前に、rustc_resolveのビジター がAST中に出現するパスを走査し、定義までのパスの解決を行う。

パスの解決結果は、 Def と非負整数の組である。例えば、以下のようなコードを考える。

fn main() {
    use std::fs;
    let f = fs::File::open("hoge.txt").unwrap();
}

ここで fs::File::open は、 ::std::fs::File に対応するDefと、非負整数1で表される。この1は、関連アイテム部分の流さが1 (openで1個)であることをあらわしている。

この解決結果を、NodeId から引けるHashMapに保存する。この NodeId は、このパスのAST上の出現に対して割り当てられているものを使う。上の例では、

    let f = fs::File::open("hoge.txt").unwrap();
            ^^^^^^^^^^^^^^ この部分

のノードに割り当てられているNodeIdが使われる。

lowering中のパス解決

lowering中のパス解決はlower_qpathで行われる。 def_map の情報をもとにパスの前半を切り出し、パスの後半(関連アイテム部分)をさらに解析する。例えば、 std::vec::Vec::<T>::IntoIter::Item::clone の場合、前半は std::vec::Vec<T> で、後半は IntoIter, Item, clone となっている。これらはすべて直前の型に関連づけられたアイテム(それぞれ、関連型、関連型、メソッド)であるから、 <<<std::vec::Vec<T>>::IntoIter>::Item>::clone と解釈される。

パス解決関数

パス解決に用いられる関数は場所により異なる。 def_map への記録は record_def 関数 により行われるが、その引数の多くは resolve_qpath で解決される。

QSelfとQPath処理

パス解決前のQPathは、QSelfという追加情報を持つパスとして表されている。 syntax::ast::QSelfは以下のように定義されている。

/// The explicit Self type in a "qualified path". The actual
/// path, including the trait and the associated item, is stored
/// separately. `position` represents the index of the associated
/// item qualified with this Self type.
///
/// ```rust,ignore
/// <Vec<T> as a::b::Trait>::AssociatedItem
///  ^~~~~     ~~~~~~~~~~~~~~^
///  ty        position = 3
///
/// <Vec<T>>::AssociatedItem
///  ^~~~~    ^
///  ty       position = 0
/// ```
#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
pub struct QSelf {
    pub ty: P<Ty>,
    pub position: usize
}

ここの説明にあるように、 <A as T>::Fooのような式を書いたとき、ASTでは T::Foo に追加情報として (A, 1) という情報が与えられたものと考える。positionが 0 の場合は特殊で、トレイトが省略されたものとみなす。

QSelfを含むパスのパス解決を担当するのが resolve_qpath である。 resolve_qpath の基本動作は、 QSelf があるならばそこの情報をもとにし、なけれba resolve_path に移譲する、というものである。

u32 や f64 などのプリミティブ型は、 std::u32 のように同名のモジュールを持つ。この処理もここで行われる。

パス解決

パス解決の本体は、その次の resolve_path にある。これはざっくり言うと左側のパス要素から順に処理して進んでいくというものである。

具体的には以下のことが読み取れる。

• 最初が self や super で開始されるときは、識別子のある字句上のモジュールのnormal ancestorから開始する。
• super がパスの冒頭部に連続して現れるときは、出現回数だけ(normal ancestorの)親モジュールに移動する。
• :: から始まるときは、ルートから開始する。マクロ変数 $crate から始まるときは、 $crateが元々あった位置のcrateのルートモジュールが使われる。
• 最後の要素の名前空間は原則として指定できる。途中の要素(モジュール例)は型名前空間に属する。

normal ancestor

各モジュールにはnormal ancestorと呼ばれる、他のモジュールへのリンクが存在する。これは、主に次のような特殊なモジュールで使われる。

fn f() -> u32 { 2 }

fn main() {
    {
        println!("{}", self::f());
    }
}

ここで、 println! のすぐ外側の {} はパス解決時にはモジュールの一種と見なされている。しかし、ここで self::f の self が指しているのは、 f と main の両方を含むルートモジュールである。このギャップを埋めるのがnormal ancestorである。

明示的な mod 以外のmodでは、大抵、normal ancestorは親のnormal ancestorをそのまま使う。例えば、 build_reduced_graph_for_block を見ると、以下のようになっている。

            let module =
                self.new_module(parent, ModuleKind::Block(block.id), parent.normal_ancestor_id);

まとめ

Rustのパス解決は簡単なようで、実際にはいくつかの理由で複雑になっている。1つは名前空間、1つは相対パスと絶対パス、1つはSelfの指定である。

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

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

1. 名前解決にかかわる構文
2. インポート解決
3. パス解決
4. メソッド記法とメンバ変数と関連アイテムの解決
5. 可視性判定

名前解決のタイミング

コンパイラの名前解決に関するコードを探す上で重要な点のひとつは、「 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のどのモジュールに何があるかがわかるようになった。