Rust 関数呼び出しの期待型の伝搬

Rust

以前の記事で説明したように、Rustでは型強制や整数リテラルなどの特殊な型推論をシームレスに行うために期待型という概念を導入している。

この期待型はトップダウンに伝搬されるが、先ほどの記事で挙げた例

fn main() {
    let x : Box<[_]> = Box::new([1, 2, 3]);
    //                 ^^^^^^^^^^^^^^^^^^^ coercion site
    let y : Box<Box<[_]>> = Box::new(Box::new([1, 2, 3]));
    //                               ^^^^^^^^^^^^^^^^^^^ coercion site
}

では Box::new 関数の外側から内側に向けて期待型の伝搬が行われている。

これは Box::new に限ったことではなく、一般にどのような関数でもこのような伝搬が行われる。この計算をしているのが expected_inputs_for_expected_outputs メソッドである。

これは大まかに言うと次のようなことをしている。

  1. 関数の引数型と戻り値型を生成する。ジェネリクスにより未確定の部分には型推論変数を入れる。例えば、 Box::new の場合、引数型は ?T で戻り値型は Box<?T> である。
  2. 型推論環境のスナップショットを生成する。
  3. 関数の戻り値型と、関数呼び出しの期待型で、単一化を行う。例えば期待型が Box<Box<[?X]>> なら、単一化により ?T := Box<[?X]> が生成される。
  4. 引数型の型推論変数を展開する。今回は ?T := Box<[?X]> が判明しているため、引数型は ?T から Box<[?X]> にリファインされる。
  5. 展開結果を、引数の期待型として覚えておく。
  6. 型推論環境のスナップショットをロールバックする。

期待型はあくまでヒントであるため、期待型とは異なる型が推論されることはある。例えば、上の例ではまず Box::new([1, 2, 3]) に Box<[?X]> が期待されているという情報から [1, 2, 3] に [?X] が期待されているという情報が生成される。このような型強制はできないため失敗し、 Box::new([1, 2, 3]) の型は Box<[{integer}; 3]> になる。そこで翻ってこの期待型 Box<[?X]> と比較すると、この時点で型強制が可能であるため、強制後の型は Box<[{integer}]> となる。

このとき、期待型の伝搬のためにまず ?T := [?X] がユニフィケーションで生成されるが、これはロールバックにより消滅する。中の型が確定してからあらためてユニフィケーションが行われ、このときは ?T := [{integer}; 3] となる。

このように期待型の伝搬の過程では誤った単一化子が生成されることがあるが、期待型の処理ごとにロールバックすることで競合を回避している。

Rustにおける演算子の型推論の特殊ルール

Rust

概要: 原則として x + y は ::std::ops::Add(x, y) の構文糖衣であるが、型推論で特別扱いされる。

演算子の脱糖

演算子の脱糖は型推論の後、HIRからMIRへの変換のタイミングで行われる。原則として x + y は ::std::ops::Add(x, y) の構文糖衣である。これは *x/x[i] 以外の他の演算子についても同様である。しかし型推論では以下のような特殊扱いがある。

fn main() {
    use std::ops::Add;
    let x : i8 = 1 + 1; // OK
    let x : i8 = Add::add(1, 1); // Error
}

下側のコードがエラーになる理由

Rustの演算子はオーバーロード可能であり、型の制約が少ない。具体的には「左辺と右辺の型から、計算結果の型が一意に決まる」ということだけが要請される。そのため型 A と型 B の値を足して型 C の値ができることがありえる。例えば、以下のような足し算を定義することができる。

fn main() {
    use std::ops::Add;
    struct A;
    struct B;
    impl Add<B> for A {
        type Output = i8;
        fn add(self, other: B) -> Self::Output { 42 }
    }
    let x : i8 = 1i8 + 1i8; // OK
    let x : i8 = A + B; // OK
}

つまり、外側の型 i8 から、内側の型を決めることは基本的にできない。演算子に限らず、戻り値型が <A as Add<B>>::Output のような射影型になっているときは、型はボトムアップにしか伝搬しない。

つまり、 Add::add(1, 1) : i8 から 1 : i8 は推論されない。この型情報の不足から、 1: {integer} だけが判明する。これは後でデフォルトである i32 と推論されるが、すると Add::add(1i32, 1i32) : i32 であり型が一致しない。

上側のコードがエラーにならない理由

lhs + rhs で、 lhs, rhs がある特定の型の場合に、Rustは「lhs, rhs, lhs + rhs の型は全て同じ」という制約を追加する。これにより自動的に内側の 1 が i8 であることが判明する。

演算子ごとの動作の違い

二項演算子は以下の4種類に分類される。それぞれ、特定の条件下で型に対して追加の仮定をおく。

  • 短絡回路演算子: ||, &&
    • 常に、左辺/右辺/戻り値は bool である。
  • シフト演算子: <<, >>
    • 両辺がともに整数型であるとき、左辺の型と戻り値の型は等しい。
  • 数学演算子: +, -, *, /, %
    • 両辺がともに整数型であるか、両辺がともに浮動小数点数型であるとき、左辺の型と右辺の型と戻り値の型は等しい。
  • ビット演算子: |, &, ^
    • 両辺がともに整数型であるか、両辺がともに浮動小数点数型であるか、両辺がともに bool であるとき、左辺の型と右辺の型と戻り値の型は等しい。
  • 比較演算子: ==, !=, <, <=, >, >=
    • 両辺がともにスカラー型であるとき、左辺の型と右辺の型は等しく、戻り値の型は bool に等しい。

ただし、スカラー型とは、 bool/char/整数型/浮動小数点数型/関数定義/関数ポインタ/生ポインタ のいずれかである。

「整数型である」「浮動小数点数型である」というのは、 i32 や usize のような特定の型のほかに、 {integer} のような推論型も含む。

単項演算子の場合

3つある単項演算子 */!/- のうち、 !と-も似たような動作をする。ただし以下の違いがある:

  • これらの演算子に遭遇したタイミングで structurally_resolved_type が呼ばれる。そのため、被演算子の型がこの時点で全く判明していない場合は、エラーになる。

! は、被演算子が整数または bool のとき、 - は、被演算子が整数または浮動小数点数のときに、組込み演算子とみなされる。このとき戻り値の型は被演算子の型と等しいと仮定される。

まとめ

  • x + y はほぼ ::std::ops::Add(x, y) の構文糖衣であるが、型推論の動作が微妙に異なる。
  • x と y が特定の型のときは、型推論の時点で「組込み演算子である」と判定され、トップダウンな型推論が可能になる。

Rust パターンマッチの変数束縛とコンストラクタ/定数の区別

Rust

パターンマッチを持つ言語では、変数束縛とコンストラクタ/定数が構文上曖昧である場合がある。Rustでは以下の規則に従っている。

また、上記の条件で変数束縛とみなされたが、アイテム名と一致するときはエラーとなる。

例えば以下のようになる。

struct A;
fn main() {
    // let A = A; // Error
    let self::A = A; // OK
    match A { A => {}}; // OK
    // match A { ref A => {}}; // Error
    // match A { A @ A => {}}; // Error
}

Rustで use std; が必要なときとエラーになるときがあるのは何故か

Rust

Rustでは use std; や use rand; のようなインポートが必要な場合と、逆に書くとエラーになる場合がある。

簡単に言うと

  • トップレベルモジュールでは、書くとエラーになる(既にある名前と衝突する)。それ以外の場所では、必要な場合がある。
  • これは名前をローカルで使うための仕組みと、名前の別名を公開するための仕組みが同じ use により実現されていることと関係している。

そもそも use std; は何故必要なのか

例えば、あるモジュール m1.rs 内で以下のようなコードを書くとエラーになる。

fn foo() {
    let stderr = std::io::stderr();
}

rustc 1.18.0 (03fc9d622 2017-06-06)
error[E0433]: failed to resolve. Use of undeclared type or module `std`
 --> m1.rs:2:18
  |
2 |     let stderr = std::io::stderr();
  |                  ^^^^^^^^^^^^^^^ Use of undeclared type or module `std`

error: aborting due to previous error

呼ぼうとしているのは確かに std::io::stderr なのにこれが発見されないのは何故か。これは、この手のパスが文脈によって異なる解釈をされることに由来する。そもそもパス(::で区切られているやつ)は次の3種類に分けられる。

  • :: または $crate:: で始まるもの (例: ::std::default::Default)
  • self または super で始まるもの (例: self::MyTrait) (※単独の self は例外)
  • それ以外
    • use path; と pub(in path) では、絶対パスとして解釈される。
    • それ以外の文脈では、レキシカルスコープのパス (相対パスの亜種) として解釈される。

つまり、 std::io::stderr はここでは絶対パスではなく、相対パスのようなものとして扱われてしまっているのである。

絶対パスとして修正する場合

先ほどのコードで意図しているのは絶対パスだと考えられる。したがって次のようにすればエラーにはならない。

fn foo() {
    let stderr = ::std::io::stderr();
}

レキシカルスコープのパスとして修正する場合

もう一つの解釈として、レキシカルスコープのパスとしての使用を意図していた可能性も考えられる。例えば、以下のコードは正しい。

use std::io;
fn foo() {
    let stderr = io::stderr();
}

同じ要領で、 std をインポートすればよいという考えがありえる。これも正しい。

use std;
fn foo() {
    let stderr = std::io::stderr();
}

トップレベルモジュールでは不要なのはなぜか

トップレベルモジュールでは通常、 extern crate が多く行われている。例えば、 extern crate rand; と書いておくと、 rand のトップレベルモジュールが ::rand にリンクされる。

ここでもし m1 モジュール内で use rand; をすると、これがさらに ::m1::rand にリンクされることになる。これにより m1 の直下で rand を簡単に参照できるようになる。

同じ理屈で、トップレベルモジュールで use rand; をすると、 ::rand を ::rand にリンクしようとしていることになる。これはおかしいのでエラーになってしまうという寸法である。

こういった理屈のため、 use nalgebra as na; のような別名インポートはトップレベルモジュールでも必要である。例えば、

extern crate nalgebra;
use nalgebra as na;

..

mod m1 {
    use nalgebra as na;
}

のようになる。もちろん、以下のようにそもそも extern crate の時点で別名をつけてリンクすることもできる。(好ましい習慣かは別として)

extern crate nalgebra as na;
// use 不要

mod m1 {
    use na;
}

Rustの use の設計について

Rustの use は2つの目的を兼ねている。これは例えばこのNiko Matsakis氏のコメントでも確認できる。

  • ある定義(関数や型など)に別名をつける(別名をつけて公開する)こと。 (再エクスポート)
  • ある定義をローカルから使うためにスコープに入れること。 (インポート)

前者はモジュールグラフの切り貼り自体を目的にしているのに対して、後者は let などと同様にレキシカルスコープへの名前の導入ができればよく、グラフの切り貼りは意図していない。しかしRustでは両者を同じように、グラフの切り貼りで実現する仕組みになっている。このことは、 use の動作を理解するにあたって押さえておくとよいところかもしれない。

まとめ

  • トップレベルモジュールでは、 use std; を書くとエラーになる(既にある名前と衝突する)。それ以外の場所では、 use std; が必要な場合がある。
  • これは名前をローカルで使うための仕組みと、名前の別名を公開するための仕組みが同じ use により実現されていることと関係している。

Rustでunsafeが必要な操作

Rust

Rustでは unsafe の表明を行わない限り未定義動作が発生しない。コンパイラや言語仕様のミスにより未定義動作が発生しうる場合には優先的に修正される。(なお、整数オーバーフローのように特定条件下でエラーになるものであっても、正しくunwind/abortできるものは未定義動作とは呼ばない。)

unsafe の表明

unsafe の表明は、構文的には以下のいずれかである。

  • unsafe ブロック
  • unsafe impl

unsafe を表明した場合、その部分では「安全かどうかをコンパイラが保証できない操作」が行えるため、この部分が安全であるかどうかを検査するのはプログラマの責任であるということになる。それぞれの操作には、それが安全に実行できるための事前条件(safety precondition)が決められているから、これが成り立っていることをプログラマが自分で保証する、という算段である。

unsafe の要求

unsafe を用いたライブラリ関数の場合、「関数が何らかの性質を満たしているときは安全」という状況が考えられる。例えば、比較関数が正当であることを前提としたソートアルゴリズムの実装というのが考えられる。

Rustでは原則としてこれは許されない。ライブラリの呼び出し側が (unsafe だったり、可視性を破壊したりしていない範囲内で) どんな異常な引数で関数を呼んでも、その関数は安全に動作しないといけない。

どうしても呼び出し側に安全性の責任を転嫁したい場合は、関数シグネチャに unsafe をつける。これにより、そのライブラリ関数は、安全に使うための追加の事前条件(safety precondition)を要求していることになる。その事前条件はドキュメントに説明されるべきということになる。

このように unsafe を要求する構文には以下のものがある。

なお、関数定義の unsafe は要求と表明を兼ねている。

unsafe ブロック/関数内でないとできない操作の一覧

unsafeが適切に呼ばれているかどうかは rustc::middle::effectモジュール で検査されている。

以下では事前条件も書いてみるが、すべて筆者による推測である。

unsafe 関数/unsafe メソッドの呼び出し

unsafe のついている関数やメソッドを呼び出したときに発生する。関数を取り出して呼び出していない場合は発生しない。

事前条件: その関数/メソッドによって指定されている事前条件を守る。

生ポインタの参照外し

*const T や *mut T 型の値 p に対し、 *p を行う。 &*p のように左辺値の場合 (生ポインタを参照に昇格するのに使う) にも unsafe が必要である。

事前条件・不変条件: おそらく以下のような条件が必要とされている。

  • アラインメントが揃っている。
  • 有効な場所を指している。
  • 有効な値が格納されている。または、昇格した参照が使用されるまでに有効な値が格納される。
  • エイリアスを持たないか、これ自身を含む全てのエイリアスが読み取り専用として扱われている。

インラインアセンブリ

asm!() や global_asm!() によるインラインアセンブリの埋め込みは常に unsafe である。

事前条件・不変条件: Rustのもつ全ての不変条件を守ること。例えば、書き込み借用できるメモリ以外に書き込まない。不正な値を書き込まない。 Copy でない値をコピーした場合に元の位置のデストラクタを呼んではいけない。など。

static mut 変数へのアクセス

static mut で宣言された静的変数の読み取り/書き込みアクセスは unsafe である。

事前条件・不変条件: 書き込み参照するときは、他に誰かが参照していないこと。読み取り参照するときは、他に誰かが書き込み参照していないこと。(他スレッドからのアクセスも含む)

extern { static } 変数へのアクセス

extern { static X : u32; } のように、FFIで外部の静的変数を参照する変数への読み取り/書き込みアクセスは unsafe である。

事前条件: 値を取り出す場合は、不正な値が入っていないよう注意する。

なお、この条件は互換性のために現在は警告扱いになっている(warning cycle)。将来はエラーとなる予定である。

union 要素へのアクセス

union 要素へのアクセス (読み取り、代入、パターンマッチによる読み取り) は unsafe である。

事前条件・不変条件:

  • 読み取りでは、そのフィールドに有効な値が入っていること。
  • 書き込みでは、この union の何らかの不変条件を保ち、結果的に Drop が正常に動作すること。 (Drop を実装していなければ問題ない)

なお、最近の変更により、 Copy な union の要素への代入は unsafe ではなくなった。

Rustコンパイラのコンパイルの流れ

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やstage2のように、自身と互換なABIでコンパイルされているコンパイラをfull host compilerという。

full host compilerが必要なのは、しばしばコンパイラプラグインのビルドが必要なためである。コンパイラプラグインはコンパイラ自身にリンクされるプログラムだから、stage1コンパイラはコンパイラプラグインを正しく扱うことができない。

なお、Rustで最もよく使われるコンパイラプラグインの形式はおそらく手続きマクロ(proc-macro)である。

まとめ

  • RustコンパイラはRustで書かれている。最初のRustはstage0といい、既にあるバイナリをダウンロードする。
  • Rustコンパイラはデフォルトで2回ビルドされる。こうしないと手続きマクロが動かない。

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を強制的に指定するようなパッチを当てればよい。