Rustで挿入ソート + 強制move outで高速化
挿入ソートは時間計算量 のソートアルゴリズムであるが、特に入力
の転倒数に対して
で抑えられること、また定数倍で高速なことから特定の場面で使われる場合がある。
Rustで挿入ソートを素朴に実装すると以下のようになる。
pub fn safe_insert_sort<T: Ord>(arr: &mut [T]) { for i in 1..arr.len() { let mut j = i; while 0 < j && arr[j-1] > arr[j] { arr.swap(j-1, j); j -= 1; } } }
しかし、 arr[i] をswapによっていちいち配列に書き戻していたり、配列の境界チェックをしていたりと、このコードには無駄がある。そこで unsafe を用いてより高速化することを考える。ここで参考になるのが std::mem::swapの実装である。
#[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn swap<T>(x: &mut T, y: &mut T) { unsafe { // Give ourselves some scratch space to work with let mut t: T = uninitialized(); // Perform the swap, `&mut` pointers never alias ptr::copy_nonoverlapping(&*x, &mut t, 1); ptr::copy_nonoverlapping(&*y, x, 1); ptr::copy_nonoverlapping(&t, y, 1); // y and t now point to the same thing, but we need to completely // forget `t` because we do not want to run the destructor for `T` // on its value, which is still owned somewhere outside this function. forget(t); } }
Rustでは通常、borrowされているメモリ領域を未初期化状態にする処理はできない。そのような処理は必ずしもUB(未定義動作)ではないが、自分で安全性を確認した上で unsafe をつけて書く必要がある。
上記の swap のソースコードには、これらを考慮した上で問題のないコードを書くのに必要な道具が揃っている。すなわち、
- 変数を初期化せずに使う
std::mem::uninitialized Copyでなくても強制的にコピーする (すなわち、borrowingを無視して強制的にmove outする)std::ptr::copy_nonoverlappingDrop::dropをせずに値を捨てる (すなわち、Drop::dropの二重呼び出しを抑止する)std::mem::forget
である。
これを使って、より効率的な挿入ソートを書いてみたものが以下である。
pub fn unsafe_insert_sort<T: Ord>(arr: &mut [T]) { let len = arr.len(); let ptr = arr.as_mut_ptr(); for i in 1..len { unsafe { let mut j = i; let mut t: T = std::mem::uninitialized(); std::ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1); while 0 < j && *(ptr.offset((j-1) as isize)) > t { std::ptr::copy_nonoverlapping(ptr.offset((j-1) as isize), ptr.offset(j as isize), 1); j -= 1; } std::ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1); std::mem::forget(t); } } }
これでだいたい3倍ほど速くなるようだ。(ベンチマーク結果は以下を参照)
コード全体とベンチマーク結果
#![cfg_attr(test, feature(test))] #[cfg(test)] extern crate test; #[cfg(test)] extern crate rand; pub fn safe_insert_sort<T: Ord>(arr: &mut [T]) { for i in 1..arr.len() { let mut j = i; while 0 < j && arr[j-1] > arr[j] { arr.swap(j-1, j); j -= 1; } } } pub fn unsafe_insert_sort<T: Ord>(arr: &mut [T]) { let len = arr.len(); let ptr = arr.as_mut_ptr(); for i in 1..len { unsafe { let mut j = i; let mut t: T = std::mem::uninitialized(); std::ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1); while 0 < j && *(ptr.offset((j-1) as isize)) > t { std::ptr::copy_nonoverlapping(ptr.offset((j-1) as isize), ptr.offset(j as isize), 1); j -= 1; } std::ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1); std::mem::forget(t); } } } #[cfg(test)] mod tests { use super::*; use std::fmt::Debug; use test::Bencher; use rand::{XorShiftRng, Rng, SeedableRng}; fn test_sort<T: Ord + Clone + Debug>(arr: &[T]) { let mut arr1 = arr.to_vec(); let mut arr2 = arr.to_vec(); let mut arr3 = arr.to_vec(); arr1.sort(); safe_insert_sort(&mut arr2); unsafe_insert_sort(&mut arr3); assert_eq!(arr1, arr2); assert_eq!(arr1, arr3); } #[test] fn test_sorts() { test_sort(&[1, 2, 3, 4]); test_sort(&[4, 2, 3, 1]); test_sort(&[3, 2, 3, 0]); test_sort(&[3, 3, 6, 2, 1, 5, 7, 3, 1, 2]); } #[bench] fn bench_safe_insert_sort_by_worst(b: &mut Bencher) { let v : Vec<u32> = (0..1000).rev().collect(); b.iter(|| { safe_insert_sort(&mut v.clone()); }) } #[bench] fn bench_unsafe_insert_sort_by_worst(b: &mut Bencher) { let v : Vec<u32> = (0..1000).rev().collect(); b.iter(|| { unsafe_insert_sort(&mut v.clone()); }) } #[bench] fn bench_safe_insert_sort_by_uniform_random(b: &mut Bencher) { let mut v : Vec<u32> = (0..1000).collect(); XorShiftRng::from_seed([189522394, 1694417663, 1363148323, 4087496301]).shuffle(&mut v); b.iter(|| { safe_insert_sort(&mut v.clone()); }) } #[bench] fn bench_unsafe_insert_sort_by_uniform_random(b: &mut Bencher) { let mut v : Vec<u32> = (0..1000).collect(); XorShiftRng::from_seed([189522394, 1694417663, 1363148323, 4087496301]).shuffle(&mut v); b.iter(|| { unsafe_insert_sort(&mut v.clone()); }) } }
[package] name = "insert-sort" version = "0.1.0" authors = ["Masaki Hara <ackie.h.gmai@gmail.com>"] [dependencies] rand = "0.3"
$ cargo bench
Compiling insert-sort v0.1.0
Finished release [optimized] target(s) in 1.75 secs
Running target/release/deps/insert_sort-0526ddc8d41f2829
running 5 tests
test tests::test_sorts ... ignored
test tests::bench_safe_insert_sort_by_uniform_random ... bench: 527,505 ns/iter (+/- 47,327)
test tests::bench_safe_insert_sort_by_worst ... bench: 985,459 ns/iter (+/- 65,682)
test tests::bench_unsafe_insert_sort_by_uniform_random ... bench: 176,659 ns/iter (+/- 25,409)
test tests::bench_unsafe_insert_sort_by_worst ... bench: 326,565 ns/iter (+/- 77,140)
test result: ok. 0 passed; 0 failed; 1 ignored; 4 measured
ベンチマーク環境は Rust nightly rustc 1.18.0-nightly (5309a3e31 2017-04-03), Ubuntu 16.04.1 over VirtualBox over Windows 10, Surface Pro 2
記事の更新頻度について
1日1回更新は一ヶ月続けることができた。ブログ駆動で色々調べる機会が得られたのはよかったが、さすがにこの頻度は大変なので、以降は2日に1回の更新にしようと思う。また、既存の記事の英訳をしてみるのもよいかもしれない。
RustのジョークRFC
ハッシュベースの署名(公開鍵署名)を書いてみた
Post-Quantum Cryptography, Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Springer-Verlag Berlin Heidelberg, 2009の冒頭部で、ごく簡単なハッシュベースの署名アルゴリズムが紹介されていて感動したのを思い出したので書いてみた。
コードは長いので一番下に載せる。
概要
これは、堅牢なハッシュ関数を用いて、整数論的な何かに頼らなくても、署名を実現できるというものである。
ハッシュで署名というと、HMACが連想されるが、MACと署名は微妙に異なる。簡単に言うとMACが共通鍵で署名が公開鍵のものを指す。
仕組み
Lamport–Diffieのワンタイム署名という部品をベースにしている。これは、大量のハッシュ値を公開鍵として渡しておき、署名をするときは、その一部の元データを開示するというものである。元データを知っているのは自分だけだから、「どのデータを開示するか」は自分にしか決定できないことであり、この選択とメッセージのダイジェストを対応づけることでメッセージに署名をしたことにする。
この方法は明らかに、同じ鍵で2つ以上のメッセージに署名をすると破綻するという欠点がある。それがワンタイム署名と呼ばれる所以である。そこで、署名をチェインさせることで複数回の署名をできるようにするというのがこのハッシュベース署名の考え方である。
「署名をチェインさせる」と聞いた時点で「多分こんなんだろう」と思って実装したのが以下にある(あとから考えると、ちゃんと最後まで読んでから考えるべきであった)。そういうわけなのでこのプロトコルが本当に安全かはよくわからない。
今回は、各ワンタイム鍵は、「別のワンタイム公開鍵2つ」を署名するか、または実際のメッセージを署名するものとして、ワンタイム鍵からなる二分木を動的に生成するようにしてみた。チェインの長さは32で固定にしたので、最大232個のメッセージを署名できる。
二分木にするというアイデア自体は当然既存のもののようで、Merkle Treeなどがあるようだ。ただMerkle Treeはパッと説明を見た限り、2H個のデータブロックを最初に生成するようなので、少し違うものという気がする。この辺りはもう少し調べる必要がありそうだ。
欠点
プロトコル部分は筆者の想像で書かれたものなので、筆者が気付いていない問題があるかもしれない。
それ以外の問題点としては、
- 鍵がとても大きい。 (これは、より効率的なワンタイム署名を使えば改善されるのかもしれない)
- これは木をランダムに掘っていることにも由来している。左から順番に掘れば、秘密鍵の膨張は抑えられるが、何回署名をしたかがわかってしまう。
- 秘密鍵を丸ごとコピーするなどして、別々のコンピューターで独立して運用すると、安全でなくなる。
以下に示す実装の利用例
$ 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で書かれている。
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の名前解決の詳細について解説する。本記事では、解決された名前の可視性判定について説明する。
可視性
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の名前解決の詳細について解説する。本記事では、型情報を必要とする名前の解決を説明する。
- 名前解決にかかわる構文
- インポート解決
- パス解決
- メソッド記法とメンバ変数と関連アイテムの解決
- 可視性判定
曖昧性が生じる例
この記事で扱うのは、型情報がないと曖昧性があるような名前の解決である。まずは例を挙げる。
メソッド記法は以下のような曖昧性がある。
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の識別子の中には、型に依存して解決されるものがある。これらは比較的アドホックな方法で解決されており、型の明示が必要な原因のひとつになっていると思われる。
