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

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

• 以下のように、構文的にパスであるとわかる場合は、常にコンストラクタ/定数とみなす。
  • :: を含んでいる場合。 (::A, self::A, <T as Trait>::X など)
  • {} を後続する場合。 (A {} など)
  • () を後続する場合。 (A() など)
  • ../.../..= などの一部である場合。 (FOO_MIN .. FOO_MAX など)
  • ! を後続する場合。 (your_macro_expanding_to_a_pattern!() など)
• 反駁不可文脈では常に変数束縛とみなす。反駁不可文脈かどうかは以下のように定義される。
  • match, if let, while let のパターンは反駁可能でもよい。
  • let, for, 関数の引数部のパターンは反駁不可でなければならない。
• asパターン (ident @ pat) の左辺は常に変数束縛とみなす。
• ref ident や mut ident のように束縛モードが指定されていれば常に変数束縛とみなす。
• 上記以外で、スコープ内のアイテム名と一致し、それらが以下のいずれかだった場合はコンストラクタ/定数とみなす。
  • const 定数
  • static 静的変数
  • ユニット形式の struct (struct A; のように宣言されるもの)
  • enum のバリアントでユニット形式のもの (例: use E::A; enum E { A; })
• 上記以外では、変数束縛とみなす。

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

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

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

unsafe の表明

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

• unsafe ブロック
• unsafe impl

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

unsafe の要求

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

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

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

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

• 関数シグネチャの unsafe
• unsafe trait

なお、関数定義の 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コンパイラは同梱の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コンパイラは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を強制的に指定するようなパッチを当てればよい。

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)] を使うと、より意味的に正しい方法で検査されることになる。