Rustコンパイラのコンパイルの流れ
Rustコンパイラは同梱のrustbuildというツールでビルドされる。これはRustとPython2で書かれている。 README.md
にも説明が書かれているが、ここで改めて説明をしてみる。
./x.py
は src/bootstrap/bootstrap.py
にリンクされている。これは次のような動作をする。
- 設定ファイル (
config.mk
またはconfig.toml
) を読む。bootstrap.py
はTOMLパーサーを持たないため、この時点ではconfig.toml
はアドホックな方法で解析される。したがって、vendor
,locked-deps
,cargo
,rustc
,build
キーの記述には気をつける必要がある。例えばcargo = ".."
をcargo=".."
と書くと認識されない。
- 必要なら、
src/stage0.txt
を読み、インターネットからstage0コンパイラ(ビルド済みのRustコンパイラ)を取得する。 - 必要なら、rustbuild自身をビルドする。
cargo build --manifest-path src/bootstrap/Cargo.toml
が実行される。 - rustbuildを呼び出す。
build/bootstrap/debug/bootstrap "$@"
が実行される。
rustbuildの本体はRustで書かれている。特に重要なのが step.rs
である。ここにMakefileのような依存関係が記述されている。
./x.py build
をしたときのrustbuildの手順は大雑把にいうと次の通りである。
- stage0コンパイラを用いて、stage1コンパイラをビルドする。(stage0標準ライブラリにリンクされる)
- stage1コンパイラを用いて、stage1標準ライブラリをビルドする。
- stage1コンパイラを用いて、stage2コンパイラをビルドする。(stage1標準ライブラリにリンクされる)
- stage1標準ライブラリはそのままstage2標準ライブラリとして用いられる。
このように2回コンパイルが必要なのは、Rustがバージョン間でABI互換性を保たないことに由来する。
ここでstage0コンパイラのバージョンをV0とし、現在作ろうとしているコンパイラのバージョンをV1とする。すると、各ステージのコンパイラと標準ライブラリのバージョンは以下のようになる。
- stage0コンパイラ: V0 ABIでコンパイルされているV0のコンパイラ
- stage0標準ライブラリ: V0 ABIでコンパイルされているライブラリ
- stage1コンパイラ: V0 ABIでコンパイルされているV1のコンパイラ
- stage1標準ライブラリ: V1 ABIでコンパイルされているライブラリ (=stage2標準ライブラリ)
- stage2コンパイラ: V1 ABIでコンパイルされているV1のコンパイラ
stage0やstage2のように、自身と互換なABIでコンパイルされているコンパイラをfull host compilerという。
full host compilerが必要なのは、しばしばコンパイラプラグインのビルドが必要なためである。コンパイラプラグインはコンパイラ自身にリンクされるプログラムだから、stage1コンパイラはコンパイラプラグインを正しく扱うことができない。
なお、Rustで最もよく使われるコンパイラプラグインの形式はおそらく手続きマクロ(proc-macro)である。
まとめ
Rustコンパイラの自前ビルド
コンパイラの動作を調べるにあたって、いちいちmasterをビルドするのは不便なので、安定版の自前ビルドを作成することにした。
$ wget https://static.rust-lang.org/dist/rustc-1.18.0-src.tar.gz $ tar xvf rustc-1.18.0-src.tar.gz $ cd rustc-1.18.0-src $ cp src/bootstrap/config.toml.example config.toml
config.toml
を編集する。今回変更したのは以下の点
[llvm] [build] # コンパイラ内部の関数等のドキュメントも生成する compiler-docs = true # cargo/rlsも一緒にビルドする extended = true [install] prefix = "/home/username/rust-custom/1.18.0" [rust] # デバッグアサートを有効にする。特にdebug!()によるログを有効にする debug-assertions = true debuginfo = true debuginfo-lines = true [target.x86_64-unknown-linux-gnu] [dist]
ビルド・インストールする。適当にYouTubeを鑑賞するなどしながら待つ
$ python2 x.py build && python2 x.py doc && python2 x.py dist --install
作成したツールチェインをrustupに登録する。
$ rustup toolchain link custom-1.18.0 ~/rust-custom/1.18.0
これで必要なときだけ自前バージョンを呼び出せるようになる。
$ rustup run custom-1.18.0 rustc --version rustc 1.18.0-dev $ rustc +custom-1.18.0 --version rustc 1.18.0-dev
debug-assertions
を有効にしたので、以前の記事で書いたように、デバッグ出力を見ることができるようになる。
プロジェクトごとに使うバージョンを変えるには rustup override
をするとよい。
$ rustup override set custom-1.18.0
pyenvはバージョン設定をローカルの .python-version
に置くが、rustup overrideの設定は ~/.rustup/settings.toml
にまとめられている。
生成したドキュメントは $prefix/share/doc/rust/html/index.html
にある。ここにあるAPIドキュメントは通常 core
やstd
などのみ掲載されているが、compiler-docs
オプションを有効にしたのでコンパイラドキュメントが同梱されている。
LLVMを指定する場合
Rustの配布物にはLLVMが同梱されているが、OSに入っているLLVMを使うこともできる。思いつく利点と欠点は以下の通り
- 利点: 初手コンパイル時間の短縮
- 欠点: RustはLLVMのバグをよく踏んでいるので古いバージョンだと困ることがあるかも
- 欠点: バージョン違いにより生成されるコードが微妙に異なり、codegenのテストに落ちることがある。テストを実行しないなら特に問題ない
- 欠点: LLVM4.0は
-lffi
を手動で指定しないといけないので対処が必要
以下ではUbuntu 16.04.2 LTSを例にする。
まずLLVMを入れる。Ubuntuの公式リポジトリには3.7がある。 *-tools
が必要なので注意
$ sudo apt install llvm-3.7-tools
LLVM側のUbuntu用リポジトリでは4.0も提供されているのでそれでもよい。
続いて、このLLVMを使うように config.toml
を書き換える
[llvm] [build] [install] [rust] [target.x86_64-unknown-linux-gnu] llvm-config = "/usr/bin/llvm-config-3.7" [dist]
llvm-4.0を使うとリンクに失敗するかもしれない。その場合は-lffi
を強制的に指定するようなパッチを当てればよい。
RustでOptionやResultの配列ができてしまったときの一般的なテク4つ
Vec<Result<_>>
ではなく Result<Vec<_>>
を得る
collect()
関数を使うと、 Vec<Result<_>>
を得ることもできるし、 Result<Vec<_>>
を得ることもできる。変換先の型を明示することで区別する。
fn main() { // 全てSomeならSome(配列)を返し、どれかがNoneなら全体もNoneになる assert_eq!([Some(1), Some(2)].iter().cloned().collect::<Option<Vec<_>>>(), Some(vec![1, 2])); assert_eq!([None, Some(2)].iter().cloned().collect::<Option<Vec<_>>>(), None); }
これができるのは以下の理由による。
FromIterator
は多対多である。つまり、ひとつの変換元に対して複数の変換先を定義できるようになっている。Option
とResult
は以下のFromIterator
を定義している。
impl<A, E, V: FromIterator<A>> FromIterator<Result<A, E>> for Result<V, E> { .. } impl<A, V: FromIterator<A>> FromIterator<Option<A>> for Option<V> { .. }
Some
/Ok
なものだけ抜き出す
flat_map
を使う。
fn main() { // 25を引き、引けなかったものは取り除く let v = [30u8, 40, 17, 80].iter() .flat_map(|&x| x.checked_sub(25u8)) .collect::<Vec<_>>(); assert_eq!(&v, &[5, 15, 55]); }
Result
と Option
はそれ自体が IntoIterator
である。(Ok
/Some
なら1要素、それ以外なら0要素として振る舞う。) そのため flat_map
が使える。
和や積を求める
Result
限定で Option
にはない。 Result<>
型のイテレーターに対して直接 sum
/product
を使うことができる。
fn main() { // 配列内の文字列をパースして、全て成功したらOk(和)、どれかが失敗したらErr let s = ["10", "20", "30"].iter() .map(|&s| s.parse::<i32>()) .sum::<Result<i32, _>>(); assert_eq!(s, Ok(60)); let s = ["10", "2o", "30"].iter() .map(|&s| s.parse::<i32>()) .sum::<Result<i32, _>>(); assert!(s.is_err()); }
これは Result
が以下のような Sum
/Product
の実装を持っているからである。
impl<T, U, E> Sum<Result<U, E>> for Result<T, E> where T: Sum<U> { .. } impl<T, U, E> Product<Result<U, E>> for Result<T, E> where T: Product<U> { .. }
失敗したらデフォルト値を入れる
単に要素ごとに unwrap_or
系関数を呼べばよい。
fn main() { // パースして失敗したら0にする let v = ["10", "2o", "30"].iter() .map(|&s| s.parse::<i32>()) .map(|r| r.unwrap_or(0)) .collect::<Vec<_>>(); assert_eq!(&v, &[10, 0, 30]); }
Rust パターンマッチの網羅性
Rustのパターンマッチは網羅性が検査され、網羅的でない場合はコンパイルエラーになる。網羅性は以下のように検証される。
型の分類
パターンマッチの網羅性をするときには、全ての型がADTのように扱われる。つまり、有限個の引数をとるコンストラクタが有限個あり、そのいずれかにより生成されていると仮定して、網羅性が判定される。
constructor_arity
あたりを読むとわかるが、例えば、
- 通常のADTは、そのままその意味でADTとみなされる。
- ただし、空なADTであっても、空であることが今いるモジュールからわからない場合は、余分なコンストラクタを持っているとみなされる。
bool
はtrue
とfalse
の2つのコンストラクタからなるとみなされる。u8
やi32
などはオープンな型とみなされ、全ての定数を網羅しても網羅的とはみなされない。これを修正する提案がある。- 参照は単一のコンストラクタを持つものとみなされる。
- 固定長配列は単一のコンストラクタを持つものとみなされる。
- スライスは長さごとに別々のコンストラクタを持つものとみなされる。ただし、計算の都合上、ある長さより長いものはまとめて扱われる。
パターンは以下のどれかに分類される。
- ワイルドカードに相当するパターン (
_
や識別子への束縛) - 単一のコンストラクタに対応するパターン (
&p
や(p1, p2)
など) - 複数のコンストラクタに対応するパターン (スライスパターンの一部)
複数のコンストラクタに対応するパターンはあまり多くないので、簡単のため以下ではなかったことにする。
アルゴリズム
Rustのパターンマッチの網羅性は is_useful
関数に帰着される。 is_useful
関数は以下の問題を解く。
入力:
- パターンからなる n×m行列 M
- パターンからなる 1×mベクトル v
出力:
- m個の値の組で、Mにマッチせずvにマッチするものがあるか否か
この関数は、マッチの各腕の到達可能性にも使われるし、網羅性検証にも使われる。到達可能性ならば
- m = 1
- M = ある腕より前にある腕のうち、ガードのないもの
- v = 該当の腕
とし、網羅性検証ならば
- m = 1
- M = 全ての腕のうち、ガードのないもの
- v = ワイルドカード
とおけばよい。
is_useful
は以下のように解かれる。
- m = 0, n = 0 のとき、true
- m = 0, n > 0 のとき、false
- m > 0 のときは、最初の列に注目して処理をする。
- v0がコンストラクタならば、これに基づいて以下の処理をする。
- Mの各行を、v0のコンストラクタにより特殊化する。v0のコンストラクタのarityをkとすると、新しい行列は(m-1+k)列になる。行数はn以下になる。
- v自身も同様に特殊化する。
- 特殊化したMとvに対して、
is_useful
を実行する。
- v0がワイルドカード相当ならば、
- v0の型から考えられるコンストラクタと、Mの左端の列に出現するコンストラクタを比較する。
- 網羅されていないコンストラクタがある場合は、true
- 全てのコンストラクタが網羅されている場合は、v0の全てのコンストラクタについて、特殊化した
is_useful
を試す。
空な型への対応
空(uninhabited)な型とは、値を作ることができないことがわかる型である。
空な型は #![feature(never_type)]
の有無により挙動が異なる。
#![feature(never_type)]
がない場合
原則として、型は非空なものとして扱われる。ただし、マッチの腕が0個の場合は、以下のいずれかの場合に網羅的とみなされる。
- マッチ対象の型が
!
である。 - マッチ対象の型が列挙型で、その列挙型がバリアントをひとつも持っていない。
例えば、以下の例では #![feature(never_type)]
を外すとコンパイルが通らない。
#![feature(never_type)] enum Empty {} fn f(x: (Empty,)) { match x {}; } fn main() {}
#![feature(never_type)] enum Empty {} fn f(x: Option<Empty>) { match x { None => {}, } } fn main() { }
#![feature(never_type)]
がある場合
#![feature(never_type)]
がある場合、空な型は以下のいずれかである。
!
- 空なフィールドを持つタプルや構造体
- 空なフィールドからなる共用体
- 全てのバリアントが空なフィールドを持つような列挙型
- 空な要素型を持つ要素数1以上の配列
- 空な型への参照
例外として、フィールドや型がmatchのあるモジュールから不可視の場合は、その構造体は非空と仮定される。
まとめ
- パターンマッチの網羅性は、およそ期待された通りにチェックされる。ただし、以下の例外がある。
- 整数型の網羅性は適切にチェックされない。
- 空な型のパターンマッチングは現在のところかなり保守的に検査される。ただし、
#![feature(never_type)]
を使うと、より意味的に正しい方法で検査されることになる。
Rustのmatchにおけるカンマの省略
Rustの match
の腕はカンマで区切られるが、これが省略できる場合が2つある。
- 末尾のカンマ
=> { .. }
の直後のカンマ
fn main() { match Some(1) { Some(x) => { } // => { .. } の直後にはカンマは省略可能 None => () // 末尾のカンマは省略可能 } }
この2の規則のために、matchの腕では以前の記事で説明したのと同じ打ち切り規則が適用されている。すなわち、
if (else)
,if let (else)
,match
,{}
,while
,while let
,loop
,for in
のいずれかの式である。.
(メソッド呼び出し) や?
(try構文) が後続しない。
が満たされるとき、その位置でパースが打ち切られる。
そのため以下のようなソースは正しくパースされる。
fn main() { match Some(1) { Some(x) => {10}.to_string(), None => "".to_string(), }; }
なお、上の条件にあるように、 {}
以外にも if
式などでパースが打ち切られることがあるが、式文のパースとは異なり、これらの式でコンマが省略された場合はパースエラーになる。これが意図した挙動かどうかはよくわからない。
fn main() { match Some(1) { Some(x) => if true { 10 } else { 20 } + 30 None => 40 }; }
Rustの構造体/列挙型フィールドの並べ替え
現在の安定版では無効化されているが、Rustのbeta/nightlyには構造体/列挙型フィールドの自動並べ替えが実装されている。この動作を説明する。
例
以下のようなプログラムを書くと、現在の安定版では6が表示され、beta/nightlyでは4が表示される。
use std::mem::size_of; struct A(u8, u16, u8); fn main() { println!("{}", size_of::<A>()); // 6 or 4 }
これはアラインメントと関係がある。通常 u8
は1バイト、 u16
は2バイトの境界に揃えられている必要がある。そのためこの構造体/列挙型のフィールドを宣言順に並べると、
u8
, 1バイトパディング、u16
,u8
, 1バイトパディング
となる。 (配列として並べることもあるため、最後にもパディングが必要である。)
一方、これを並び替えると、
u16
,u8
,u8
となり、アラインメントの制約を満たしつつよりコンパクトに構造体を表現することができる。
構造体/列挙型フィールドの並べ替えが発生する条件
並べ替え処理は rustc::ty::layout
に書いてあるのでここを読むとわかる。
#[repr(C)]
,#[repr(packed)]
,#[repr(simd)]
,#[repr(linear)]
のいずれでもない。- 以下のいずれかである。
構造体/列挙型フィールドの最適性条件
まず、フィールドのアラインメントが小→大→小のときのみ無駄が発生する、という性質を把握しておくとよい。例えば上の例でも u8
→u16
→u8
の順になっている。対偶をとると以下のことが言える。
フィールドのアラインメントの前半が降順、後半が昇順に並んでいるとき、最小バイト数(フィールドのサイズの和を、アラインメントの倍数になるように切り上げた値)を達成する。
証明: まずは、全体が降順に並んでいる場合を考える。このときはパディングは構造体の末尾にしか存在しない。最後のパディングはちょうど、構造体全体が構造体のアラインメントの倍数になるように切り上げる最小限のサイズになるから、最小バイト数が達成される。
次に、一般に全体が降順→昇順の場合に、全体が降順の場合と同じサイズが達成されることを、フィールド数に関する帰納法で示す。まずフィールド数が0のときは明らかである。1つ以上のフィールドがあるとき、最初のフィールドと最後のフィールドのうち少なくとも一方が、アラインメント最大のフィールドである。
- アラインメント最大のフィールド + 残り+パディング のとき: 「残り」の開始位置は「残り」の要求するアラインメントに沿っているため、この部分単体で考えたときの配置と一致する。帰納法の仮定よりこの部分を降順に並べ替えても同じサイズとなる。このとき全体でみても降順である。
- 残り+パディング + アラインメント最大のフィールド のとき: これを アラインメント最大のフィールド + 残り+パディング と入れ替えてもアラインメントの制約に反しない。これにより上に帰着される。
構造体/列挙型フィールドの並べ替え順
さて、現在のbeta/nightly Rustでは先ほどの条件を満たすとき、以下のようにフィールドが並べ替えられる。
- univariantなデータ型では、「最後の要素が
!Sized
になり得るかどうか」により異なる動作をする。- 最後の要素も必ず
Sized
である場合は、全ての要素が降順に並べ替えられる。 - 最後の要素が
!Sized
になりえる場合は、最後以外の全ての要素が降順に並べ替えられる。
- 最後の要素も必ず
- 判別子をもつ列挙型では、判別子を除く全ての要素が昇順に並べ替えられる。
このように、並び替えてはまずいケースが考慮されている。例えば、以下のように動作する。
macro_rules! offset_of { ($x:expr, $field: tt) => ( (&$x.$field as *const _ as usize - &$x as *const _ as usize) ) } struct A<X>(i8, i8, X); struct B<X: ?Sized>(i8, i8, X); fn main() { let x = A(0, 0, 0i32); let y = B(0, 0, 0i32); let z = B(0, 0, 0i16); // 4, 5, 0 println!("{}, {}, {}", offset_of!(x, 0), offset_of!(x, 1), offset_of!(x, 2)); // 0, 1, 4 println!("{}, {}, {}", offset_of!(y, 0), offset_of!(y, 1), offset_of!(y, 2)); // 0, 1, 2 println!("{}, {}, {}", offset_of!(z, 0), offset_of!(z, 1), offset_of!(z, 2)); }
このように、同じような構造体でも、 X: Sized
の有無によって配置が異なることがあり得る。
理由はもちろん、型強制やキャストによりこれを別の型に読み替える可能性があるからである。例えば上の &y
や &z
は、 &B<Debug>
という型に変換することができる。このとき最後以外の要素は一定の位置にあってほしいから、可変長である最後の要素が途中に来るのは好ましくない。
なお、 y
と z
で最後の要素の位置は異なるから、この要素に統一的にアクセスするのは簡単ではない。vtableの中にサイズとアラインメントの情報があり、これを使うことでこの要素にうまくアクセスするようになっている。
列挙型ではフィールドは降順ではなく昇順に並べ替えられる。これは、構造体とは反対に、列挙型では先頭にある判別子を動かせないからである。そこで判別子以外を昇順にすることで必ず降順→昇順となり、同じく最適性が保証される。
まとめ
- Rustの構造体/列挙型のメンバは動作や互換性に影響のない範囲内で並べ替えられることがある。
- 現在のbeta/nightlyで採用されているアルゴリズムは最適である。アラインメントを守る配列のうちパディングが最も少なくする配置のうちの1つが得られる。
Rustの配置構文とbox構文
概要: Rustの不安定機能である配置構文とbox構文の仕組みを説明する。
配置構文の動機
Rustの値渡しはデフォルトでムーブであり、コピーコンストラクターのような重い処理が勝手に実行されることはないから、多くの場面では値渡しのコストはそれほど高くない。それでも、大きな構造体を受け渡すと memmove
のコストが高くつく場合がある。
とりわけ、データ構造に値を追加する場面では、無駄なムーブが発生している可能性が高い。これを最適化するために、ライブラリのインターフェースに工夫を加えるのが、Rustの配置構文である。C++の emplace_back
と似ていると考えてよいだろう。
配置構文の使い方
配置構文の具体的な構文は、以下の2種類が提案されており、今のところは確定していない。
in PLACE { EXPR }
構文PLACE <- EXPR
構文
PLACE
の部分は、配置構文のための専用の関数を使う。例えば Vec
の末尾に値を配置するには以下のようにする。
let mut v = vec![1, 2, 3]; v.place_back() <- 4; // v.push(4); とほぼ同義
配置構文は値をもつ。上の場合は末尾の要素への &mut
参照が返される。
let mut v = vec![1, 2, 3]; *(v.place_back() <- 4) = 5;
配置構文を使うと、次のような巨大なデータの追加でスタックオーバーフローが回避される可能性がある。
#![feature(collection_placement)] #![feature(placement_in_syntax)] fn main() { let mut vec = vec![]; vec.place_back() <- [0; 16*1024*1024]; // vec.push([0; 16*1024*1024]); println!("foo\n"); }
配置できるデータ構造
#![feature(collection_placement)] #![feature(placement_in_syntax)] use std::collections::{VecDeque, LinkedList, BinaryHeap, HashMap}; fn main() { // Vec の末尾 let mut vec = vec![]; vec.place_back() <- 1; // VecDeque の先頭と末尾 let mut list = VecDeque::new(); list.place_front() <- 1; list.place_back() <- 2; // LinkedList の先頭と末尾 let mut list = LinkedList::new(); list.front_place() <- 1; list.back_place() <- 2; // BinaryHeapへの追加 let mut h = BinaryHeap::new(); &mut h <- 1; // HashMapへの追加 let mut h = HashMap::new(); h.entry("foo") <- 3; }
配置構文の仕組み
配置構文は、次の2つの値の組み合わせで実現される。
これを使って、配置構文は以下の処理をする。
Placer::make_place
により、領域を確保する。- これが完了した時点で、配置先のメモリは書き込み可能になっていなければならない。
make_place
は領域不足などの理由で失敗してもよい。
- これが完了した時点で、配置先のメモリは書き込み可能になっていなければならない。
Place::pointer
により、配置先を確認し、ここに出力するようにEXPR
を実行する。- もし
EXPR
が失敗したら、InPlace::finalize
が呼ばれないままInPlace
がdropされる。このタイミングで、必要に応じて領域の巻き戻しを行う。
- もし
InPlace::finalize
により配置の完了を通知する。
例えば、 Vec
の場合、「領域の確保」は十分な容量を確保するだけの操作になる。この場合、 EXPR
に失敗しても不整合な状態にはなっていないから、 PlaceBack
は drop
を実装する必要はない。かわりに、成功時には finalize
でサイズを1増やすことになる。
一方、ツリーマップのようにノードごとに malloc
で要素を確保するデータ構造では、要素の追加に失敗したら巻き戻し処理が必要になるかもしれない。その場合は finalize
よりも drop
のほうに重要なコードが集中することになるだろう。
PLACE <- EXPR
はおよそ以下のように脱糖される。ただし、 EXPR
は unsafe
で囲まれていないかのように扱われる。
{ let p = PLACE; let mut place = ::std::ops::Placer::make_place(p); let raw_place = ::std::ops::Place::pointer(&mut place); unsafe { ::std::intrinsics::move_val_init(raw_place, EXPR); ::std::ops::InPlace::finalize(place) } }
Box
に対する配置
HEAP
を使うと、 Box::new
を配置構文で行うことができる。
#![feature(placement_in_syntax)] #![feature(box_heap)] use std::boxed::HEAP; fn main() { let x: Box<_> = HEAP <- 1; }
box構文
現在の box x
は単に Box::new(x)
の構文糖衣である。しかし、もともと box
が配置のための構文として考えられていたこともあり、これを一般の配置newとして使うことが提案されている。
これによると、 box EXPR
は以下のように脱糖される。ただし、 EXPR
は unsafe
で囲まれていないかのように扱われる。
{ let mut place = ::std::ops::BoxPlace::make_place(); let raw_place = ::std::ops::Place::pointer(&mut place); unsafe { ::std::intrinsics::move_val_init(raw_place, EXPR); ::std::ops::Boxed::finalize(place) } }
これは PLACE <- EXPR
とよく似ているが、 PLACE
がなく BoxPlace
トレイトによりシングルトンとして生成されているという違いがある。
なお、現在はこれは実装されていない。型推論まわりの問題があるからである。