binfmt_miscの力でBOM shebangをサポートする
概要: binfmt_miscを使うとBOM shebangを擬似的にサポートできる。ただしインタプリタ側がサポートしてないと意味がない。
事の発端
Windowsのメモ帳がLF改行をサポート→でもUTF-8で保存しようとするとBOMがついて悲しい→shebangにBOMがつくと動かないのが悲しい
やったこと
Linuxのbinfmt_miscという機能を使って、BOMのついたshebangを動くようにしてみました。
binfmt_miscはLinux固有の仕組みで、ELFとshebang以外の通常ファイルを実行しようとしたときに、/proc/sys/fs/binfmt_misc
内の一覧にしたがって、ファイルのヘッダまたは拡張子によってインタプリタを選択するというものです。今回は "\xEF\xBB\xBF#!"
が来たときにあらかじめ用意しておいた /usr/local/bin/bomshebang
というプログラムを起動するように設定しました。このbomshebangはOSの挙動をまねてshebangを解析し、本来のインタプリタを呼び出します。
できたこと
たとえばPerlのスクリプトにBOMがついても動くようになります。
Bashはインタプリタ側がサポートしていないので駄目みたいです。bomshebang側でソースを書き換えるなどの工夫をすればいけるかもしれませんが、そうするとソースを汚してしまうし、書き込めない可能性もあるので、/tmpに移動する必要がありそうですが、インタプリタによってはソースの位置や名前が重要かもしれないため、この方法では予期しない非互換性が発生しそうです。
まとめ
Linux自体をBOM shebangに対応させるのは簡単でした。しかし、インタプリタ側が対応していないとOS側だけでうまくやるのは難しそうです。
SATySFi for Windows を作った
SATySFiはOCamlのような関数型言語とLaTeXのようなマークアップ言語をベースとする新しい組版システムです。
最近SATySFi for Windowsを作ったので紹介します。
SATySFi for Windowsとは
今まではSATySFiを試すにはLinuxかMac環境が必要で、Windowsを持っている人はVMかWSLを使って試すのが一般的のようでした。
今回Windows用ビルドを整備したので、これからはWindowsネイティブ環境へのSATySFiの導入が簡単になります。
仕組み
OCamlはWindowsとの相性が悪いですが、今回はMinGWターゲットでOPAMを使いたいということで、Linuxからのクロスコンパイルを用いました。
幸いopam-cross-windowsというプロジェクトが既にあったので、これのコンパイラバージョンを上げて、必要なパッケージを追加する作業をするだけで済みました。いくつかPRを出したところwrite権限を貰えたので今後も少しずつ充実させていこうと思っています。
OCamlはコンパイラがデフォルトでブートストラップするなど、自己コンパイル大好き言語なので、クロスコンパイラの敵みたいな設計になっていることが多く、そのあたりに対処するのが大変でした。
インストーラー
NSISという有名なインストーラー言語を使いました。NSISはLinuxからのクロスコンパイルが可能で、Ubuntuにもパッケージがあるため便利です。
ただ言語としては微妙で、スタック+レジスタベースの言語をマクロで覆ったような構成なのでマクロ呼び出しの嵐であまり心地良いとは言えません。扱える文字列が最大1024文字でPATHの書き換えに注意が必要など罠も多い感じでした。
SATySFi用Vimプラグインを作った
タイトルの通りふと思い立ってSATySFi用のVimプラグインを作ったので紹介します。 https://github.com/qnighy/satysfi.vim
SATySFi とは
SATySFiはgfn氏が未踏プロジェクトとして開発している組版システムです。LaTeXのような美しい組版を、一から設計しなおしたまともな言語で行うことができるのが特徴です。
SATySFiはプログラムパートにOCaml風の関数型言語、組版パートにLaTeX風のマークアップ言語を使い、準クオートのような構文で両者を切り替えながら文書を記述します。組版結果はPDFとして直接出力されます。
satysfi.vim
の機能
satysfi.vim
は現在、シンタックスハイライトと自動インデントを提供します。
- SATySFiの持つモードを正しく識別してハイライトします。例えば
let
はプログラムモードではハイライトされますが水平モードではハイライトされません。 - 字句エラーをエラーとしてハイライトします。
- SATySFiの構文に沿ってインデントします。例えば
ちなみに
書いてから調べてみたら同名のVimプラグインを既に書いている人がいました。
Rustのパニック機構
概要: Rustのパニック機構は異常終了の処理を安全に行うためにある。この動作を詳しくみていく。
パニックとは何か
Rustには2つの異なる例外処理機構があります。
発生源 | 対処方法 | 例 | |
---|---|---|---|
パニック | プログラミングエラー | 原則として捕捉しない | assert!() 境界外参照 |
Result |
例外的な入力 | 必要に応じて捕捉 | I/Oエラー (File::read ) パースエラー ( str::parse ) |
パニックとResult
の関係についてはTRPL第2版第9章、未定義動作とパニックの関係についてはRustonomiconのUnwindingの章などが参考になります。
パニックを想定した安全性
Rustではたとえパニック状態でも未定義動作だけは絶対に避ける必要があります。そのため以下の関数は不健全 (unsound)です。
use std::ptr; // この関数はRustではunsound (やってはいけない) pub fn replace_with<T, F>(x: &mut T, f: F) where F: FnOnce(T) -> T { unsafe { ptr::write(x, f(ptr::read(x))); } }
このコードは x
から一時的に所有権を取り出し、 f
にかけてから x
に書き戻します。これは一見すると安全ですが、 f
がパニックしたときに x
が無効な値を指した状態で返されてしまいます。どうしてもこのような関数を用意したい場合には、関数自体をunsafeにして、規約を明記する必要があります。
use std::ptr; /// `x` の値を `f` で変換します。 /// /// # 安全性 /// /// `f` がパニックした場合、 `x` の指すメモリ領域は未定義になります。 /// /// 呼び出し元は、 `f` がパニックしないよう担保するか、 `f` がパニックした /// 場合に二重dropが発生しないように追加の処理をする必要があります。 pub unsafe fn replace_with<T, F>(x: &mut T, f: F) where F: FnOnce(T) -> T { ptr::write(x, f(ptr::read(x))); }
二重パニックの抑止
Rustでは二重パニックは特に気をつけて避ける必要があります。Rustのパニックは「原則として捕捉しない」だけで実際には捕捉可能ですが、二重パニックの捕捉はできません。そのため二重パニックは通常のパニックに比べてデバッグが難しくなる可能性があります。
二重パニックは主に誤った drop
実装によって発生しえます。単純化された例では次のようなものが考えられます。
use std::ops::Drop; struct A; impl Drop for A { fn drop(&mut self) { println!("drop(A)"); panic!("drop(A)"); } } fn main() { let _x = A; assert_eq!(0, 1); }
このように Drop::drop
内ではパニックを使うことができませんが、戻り値が ()
であることから Result
を用いたエラー通知もできません。つまり、 Drop::drop
内で発生したエラーを適切に通知する手段はありません。これが困る例として BufWriter
があります。
#![feature(termination_trait)] // `io::Result` を main の戻り値として使う use std::io::{self, BufWriter, Write}; use std::fs::File; fn main() -> io::Result<()> { let mut f = BufWriter::new(File::create("foo.txt")?); writeln!(f, "hoge")?; f.flush()?; // 明示的にflushしないとエラーを捕捉できない Ok(()) }
BufWriter
はデータをすぐに書き込まずバッファに蓄えるため、dropされた時点で自動的に残りを書き込みます。しかしこのとき発生したエラーを通知する手段はありません。たとえば、上の例でファイル名を /dev/full
にして実行するとエラーが表示されますが、 f.flush()?
を消すとエラーは握り潰されてしまいます。
不変条件に気をつける
データに対して、常に保たれていてほしい性質のことを不変条件といいます。たとえば、何らかの理由で単調増加な配列を扱いたい場合、この「単調である」という性質は不変条件の一種です。
ところで不変条件はプログラムの実行中に一時的に壊れる場合があります。たとえば以下の処理を考えます。
// 単調増加な配列に2を足す fn plus2(a: &mut [i32]) { for x in a { *x += 2; } } fn main() { let mut a = [3, 5, 6]; plus2(&mut a); assert_eq!(&a[..], &[5, 7, 8]); }
この plus2
の前後で「単調増加である」という性質は保たれます。ところが、この plus2
の実行中にはこの不変条件は一時的に壊れています。2項目目まで処理し終えたときの配列は [5, 7, 6]
ですから単調増加ではありません。
Rustのパニック機構では、このような論理的な不変条件が壊れる可能性がありますが、その影響が極力波及しないような工夫があります。例えば、先ほどの「単調増加である」という性質を再び考え、以下のようなプログラムを考えます。
// 単調増加な配列を三乗する fn cube(a: &mut [i32]) { for x in a { *x = x.pow(3); } } fn main() { let mut a = [3, 5, 6]; cube(&mut a); assert_eq!(&a[..], &[27, 125, 216]); }
このプログラムに [1290, 1291, 1292]
という配列を渡すと、2番目の処理中にオーバーフローでパニックが発生します(デバッグビルドの場合)。このパニック発生時点での配列の中身は [2146689000, 1291, 1292]
なので、不変条件が壊れています。しかしこの場合は、パニックを捕捉していないので、不変条件が壊れたデータをユーザープログラムが目にすることはありません。
不変条件が壊れたデータをプログラムが目にする機会には次の2つがあり、どちらも防止策があります。
- スレッド内でパニックが捕捉された場合。これは
UnwindSafe
トレイトによって抑止されている。 - 他のスレッドがデータを参照した場合。これは
Mutex
/RwLock がもつpoisoningの仕組みによって抑止されている。
なお、どちらの仕組みも転落防止柵くらいの簡易なもので、簡単にオプトアウトできるようになっています。Rustでは論理不変条件の保護を徹底する気はなく、たとえ論理不変条件が壊れていても安全性不変条件さえ守られていれば未定義動作が起こらないようにしなければなりません。
UnwindSafe
トレイト
UnwindSafe
トレイトは、後述する catch_unwind
を使うさいに、不変条件が壊れたデータが漏れないようにする仕組みです。
たとえば、次のように catch_unwind
を使うとpanicの巻き戻し処理を一時中断することができます。
use std::panic::{catch_unwind, resume_unwind}; // 単調増加な配列を三乗する fn cube(a: &mut [i32]) { for x in a { *x = x.pow(3); } } fn main() { let result = catch_unwind(|| { let mut a = [1290, 1291, 1292]; cube(&mut a); }); // 上の処理がpanicしても実行される println!("do something"); // panic処理をレジュームする result.unwrap_or_else(|e| resume_unwind(e)); }
ここで a
をクロージャの外に出せば、壊れた a
を観測できそうですが、 &mut T: !UnwindSafe
であることからコンパイルエラーになります。
use std::panic::{catch_unwind, resume_unwind}; // 単調増加な配列を三乗する fn cube(a: &mut [i32]) { for x in a { *x = x.pow(3); } } fn main() { let mut a = [1290, 1291, 1292]; // ここでコンパイルエラーになる let result = catch_unwind(|| { cube(&mut a); }); // 上の処理がpanicしても実行される println!("a = {:?}", a); // panic処理をレジュームする result.unwrap_or_else(|e| resume_unwind(e)); }
かわりに AssertUnwindSafe(&mut a)
をキャプチャーするようにすればこの仕組みをオプトアウトできます。
use std::panic::{AssertUnwindSafe, catch_unwind, resume_unwind}; // 単調増加な配列を三乗する fn cube(a: &mut [i32]) { for x in a { *x = x.pow(3); } } fn main() { let mut a = [1290, 1291, 1292]; let result = { // &mut a の壊れた値を観測するためにAssertUnwindSafeする let aref = AssertUnwindSafe(&mut a); catch_unwind(move || { cube(aref.0); }) }; // 上の処理がpanicしても実行される (a = [2146689000, 1291, 1292]) println!("a = {:?}", a); // panic処理をレジュームする result.unwrap_or_else(|e| resume_unwind(e)); }
Mutex
, RwLock
のpoisoning
Mutex
のロックや RwLock
の書き込みロックを持ったスレッドがパニックすると、その途中の値は不変条件が壊れている可能性があります。これを他のスレッドが間違って読まないようにするため、 Mutex
と RwLock
はロック(書き込みロック)を持ったスレッドがパニックした場合、poisonedフラグが立てられ、次回以降のロックが失敗するようになります。
poisonedフラグを元に戻す方法はないようですが(多分)、poisonedフラグによりエラーになった場合、返されたエラーから強制的に壊れた値を読みに行くことはできるようになっています。
パニックの流れ
ここまで、パニックに関連する基本的な注意事項をまとめました。ここからはパニックの仕組みを調べていきます。
まず、ユーザープログラムから見たパニックの流れを説明します。パニックはスレッドごとに処理されます。各スレッドの正常系をここでは次のような図であらわすことにします:
パニック処理の基本的な流れ (-C panic=unwind
) は以下のようになります。
ただし、 -C panic=abort
が指定されているときは以下のようになります。
パニックハンドラ
パニックハンドラはパニック時にまず呼ばれる処理で、主にスタックトレースの表示などを担当します。デフォルトの処理は以下のようになっています。
- もしパニックカウントが2なら、常にフルのバックトレースを表示する。
- パニックカウントが1なら、
RUST_BACKTRACE
の値に応じて以下の処理をする。0
または定義されていないならバックトレースを表示しない。full
ならばフルのバックトレースを表示する。- それ以外(
1
など)ならシンプルなバックトレースを表示する。
Box<Any + Send>
が&'static str
もしくはString
だったときは、これをエラーメッセージとして表示する。それ以外のオブジェクトだったときは、"Box<Any>"
とだけ表示する。
std::panic::set_hook
を用いてパニックハンドラを設定できます。なお、パニックハンドラ自体は全スレッドで共通です。
巻き戻し
巻き戻しはLLVMの例外機構 (C++の例外にも使われている) を用いて実装されています。プラットフォームごとにGCC互換やSEHなどとして実装されるようです。
巻き戻しでは基本的にスタックトレースに沿って drop
が呼ばれていきます。したがって最終的に以下のいずれかになります。
- スレッドの先頭まで巻き戻る
catch_unwind
の呼び出しにぶつかるdrop
が再びパニックする (二重パニック)
スレッドの先頭まで巻き戻った場合、そのスレッドだけが異常終了したとみなされ、呼び出し元スレッドからの JoinHandle::join
呼び出しに対して Err
として報告されます。
catch_unwind
の呼び出しにぶつかった場合、通常処理に復帰したとみなされます。しかし前述のように、パニックハンドラによって既にエラーメッセージが表示されてしまっているので、これはエラーを握り潰すのには向いていません。想定されている用途はFFIバウンダリなどで一時的に巻き戻しを止める等で、基本的に resume_unwind
と対にして使います。
drop
が再びパニックした場合、二重パニックになります。二重パニックの場合はパニックハンドラ呼び出し後にプロセス全体が強制終了になります。
図を見てわかるように、パニックハンドラでパニックが起こる可能性もあり、この場合は三重パニックの可能性があります。
巻き戻さない
-C panic=abort
を指定すると巻き戻さずに常にプロセスを強制終了するようになります。RFC 1513に動機が説明されています。
パニック処理の場所
パニックの処理は標準ライブラリとコンパイラの複数の箇所に分散しており追跡が困難です。ここに概要をまとめておきます。
- パニックの主な処理は
libstd
にあります。#[no_std]
なバイナリを作る方法の説明にパニック処理が入ってしまうのはそのためです。 std::panic
に公開APIがありますが、非公開のルーチンはstd::panicking
という別のモジュールに記載されています。これがパニック処理の本体です。libcore
の一部の処理はそれ自体がパニックする必要があり、std
への逆依存の関係になってしまいます。そこでまずstd::panicking::rust_begin_panic
はextern "C"
であり、#[lang = "panic_fmt"]
という印がつけられています。libcoreのcore::panicking::panic_fmt
はこの#[lang = "panic_fmt"]
を目印にして、std
のそれとリンクされるようになっています。std::panicking
の巻き戻し処理は__rust_maybe_catch_panic
と__rust_start_panic
という2つの関数に移譲されています。これは-C panic=
フラグに応じてpanic_unwind
またはpanic_abort
のどちらかにリンクされます。panic_abort
は簡単で、巻き戻さずに常にプロセスを強制終了します。panic_unwind
はLLVMの例外機構を用いてプロセスの巻き戻しのための関数を提供しています。ここで利用されているcore::intrinsics::try
はcatch_unwind
の実体です。 コンパイラのrustc_trans::intrinsics::try_intrinsic
がこれを生成しています。- また、
-C panic=unwind
の場合は関数にuwtable
属性が付与されます。
まとめ
パニック機構について説明しました。前半ではパニック機構の注意事項(Result
との比較、安全性、二重パニック、不変条件)について説明し、後半ではパニック機構の内部構造を説明しました。
Rustの関数ポインタの落とし穴
概要: Rustの関数ポインタの落とし穴について
その1: 関数ポインタはクロージャとは異なる
これはC/C++に慣れている人には当たり前ですが、関数ポインタ型 (fn()
) とクロージャ型 (Fn()
) には重大な違いがあります。それは、関数ポインタは環境をキャプチャーしないということです。大雑把にいうと、
なので、関数ポインタは、ひとつのプログラムにつき原則として有限個しかないのに対し、クロージャは、キャプチャーする環境によって無限にたくさんのクロージャを作ることができます。例えば、
fn main() { let closures = [3, 7, 1, 5, 8, 9, 2].iter().map(|&i| { move |j| i + j }).collect::<Vec<_>>(); println!("{}", closures[3](14)); }
というコードでは、「3を足す関数」「7を足す関数」「1を足す関数」「5を足す関数」…… のようにたくさんの「関数」を動的に生成していますが、こういうのはクロージャでないとできません。
関数ポインタは基本的には fn
で定義した関数からしか作ることができません。例外として、キャプチャーしていないクロージャは関数ポインタとして使うことができます。
fn main() { let f : fn(i32) -> i32 = |x| x + 1; println!("{}", f(3)); }
その2: fn
と書いたらそれ自体がポインタ型
C言語では
int (*f)(void) = getchar;
のように、関数ポインタ型には最低1個の *
がつきますが、対応するRustの記法では
let f : fn() -> i32 = i32::max_value;
のように、 *
が0個で関数ポインタです。したがって、
let f : *const fn() -> i32; // 二重ポインタ!
は、関数ポインタへのポインタになってしまいます。ここを間違えるとFFIで未知のsegfaultに悩まされる可能性があります。
その3: 関数の型は関数ポインタ型ではない
例えば、以下のコードはコンパイルエラーになります。
fn foo() { println!("foo"); } fn bar() { println!("bar"); } fn main() { let mut f = foo; if true { f = bar; } f(); }
Compiling playground v0.0.1 (file:///playground) error[E0308]: mismatched types --> src/main.rs:7:13 | 7 | f = bar; | ^^^ expected fn item, found a different fn item | = note: expected type `fn() {foo}` found type `fn() {bar}` error: aborting due to previous error error: Could not compile `playground`.
ここでは fn()
ではなく、 fn() {foo}
や fn() {bar}
という型が表示されています。これは関数定義型とよばれ、関数ポインタ型とは異なります。
関数ポインタ型と関数定義型のわかりやすい違いとしてバイト数が挙げられます。以下でわかるように、関数定義型は実は0バイトです。
use std::mem; fn main() { println!("{}", mem::size_of_val(&main)); // 0 println!("{}", mem::size_of_val(&(main as fn()))); // 8 }
関数定義型は、関数ごとに異なる型がついているので、それ自体は情報を持っていなくても呼び出せるようになっています。C++でいえば、各関数ごとにファンクタオブジェクトが一個割り当てられている、以下のような状態とみることができます。
void foo_funptr() { printf("foo!\n"); } struct foo { int dummy; //C++にはZSTがないので // 直接呼び出し void operator()() const { printf("foo!\n"); } // 関数ポインタへの変換 void (*to_funptr())() const { return foo_funptr; } };
関数がジェネリクスを持っている場合は、関数定義型にも対応するジェネリクスが与えられます。なお、コンパイラは便宜上 fn() {foo}
のような表示をしますが、関数定義型を名指しで指定することはできません。これはクロージャ型 ([closure@src/main.rs:3:20: 3:25]
などと表示される) と同様です。
いずれにせよ、通常は必要なタイミングで関数ポインタ型に自動で変換されるので、変なコンパイルエラーなどに遭遇しない限り気にする必要はないでしょう。
その4: 関数ポインタ型にはABIと安全性フラグがつけられる
特に、C/C++とのFFIをするときは、ABIを間違えないように注意が必要です。通常のRust関数は extern "Rust" fn()
なのに対して、C/C++と相互呼び出しする関数は extern "C" fn()
です。それぞれ fn()
, extern fn()
と省略できます。また unsafe
をつけて unsafe fn()
のようにもできます。
なお、 C++の extern "C"
とは異なり、Rustの extern "C"
はABIを指定するだけで、マングリング規則を変更しません。マングリングを無効化するには別途 #[no_mangle]
をつけます。
また、これまたC++に慣れているとわかりづらいですが、
extern "C" fn foo() {} // ここに実体がある
と
extern "C" { fn foo(); // 別の場所にある実体とリンクする }
は意味が異なります。 extern { .. }
は、実体が他の場所にあるときに使います。
NonNull安定化記念にInternerを書いてみる
概要: NonNull
が安定化され、1.25.0から使えるようになる。そこでNonNull
の利用例としてInternerを実装してみた。
NonNull
とは
NonNull
はRustにある生ポインタ型のひとつです。元々 Unique
, Shared
という2つの生ポインタ型でしたが、安定化を機に統合・仕様変更が行われ、 NonNull
という名前になりました。 (Unique
は libcore
内部には残っていますが、安定化の予定はなくなりました。) 予定通りに進めば、 Rust 1.25.0 から使えるようになるはずです。
Rustのポインタ関連型は仕様の微妙な違いを意識して使い分ける必要があります。以下にそれを列挙しました。
分類 | エイリアス | 変性 | 所有 | 非0 | Send | Sync | |
---|---|---|---|---|---|---|---|
&T |
参照 | なし※1 | 共変 | × | ○ | 継承※2 | 継承 |
&mut T |
参照 | なし | 非変 | × | ○ | 継承 | 継承 |
&Cell<T> |
参照 | あり | 非変 | × | ○ | × | × |
Box<T> |
スマート ポインタ |
なし | 共変 | ○ | ○ | 継承 | 継承 |
*const T |
生ポインタ | - | 共変 | × | × | × | × |
*mut T |
生ポインタ | - | 非変 | × | × | × | × |
NonNull<T> |
生ポインタ | - | 共変 | × | ○ | × | × |
- ※1
&T
はT
がUnsafeCell
を含まないときだけエイリアスなしと仮定される - ※2
&T: Send
はT: Sync
のときに成立
特に参照型はエイリアスに関する仮定があることに注意してください。ここでの「エイリアス: なし」の意味は、その参照の指すメモリには他からの干渉はないとして最適化してよいという意味で、関数の引数が参照だった場合に適用されます。 Box<T>
も特別に、引数や戻り値で渡されたときにエイリアスなしと仮定されます。
NonNull<T>
はどんなときに便利か
Rustの型システムでうまく表現できない種類の参照を表す必要がある場合に、自分で不変条件を保ちながら unsafe
なコードを書くときは、「ライフタイムがついていないけど、真正な参照」というのを表現する必要がある場合があります。この手のことをするときにはNULLかもしれない *const T
よりも NonNull<T>
を使うほうが適切です。
Rustの型システムでうまく表現できない参照としては、双方向連結リストがよく知られています。ここでは別の例として、internerと呼ばれるデータ構造を書いてみます。これは以下のようなAPIを備えたデータ構造です。
struct Interner { .. } impl Interner { pub fn new() -> Self { .. } // 文字列に対して一意な整数を0から順に振って返す。 pub fn intern(&mut self, s: &str) -> usize { .. } // 振られた番号から文字列を復元する。なかったらpanic。 pub fn get(&self, idx: usize) -> &str { .. } }
Internerの設計
Internerは正引きと逆引きのためのデータ構造が必要なので、素朴に書くと次のようになります。
use std::collections::HashMap; pub struct Interner { strings: Vec<String>, rev_map: HashMap<String, usize>, }
しかしこの場合同じ文字列を二重に格納するので無駄があります。そこで今回は危険を承知で、 strings
側で所有しているポインタを rev_map
で使い回すことにします。概念的には次のようなものを考えます。
use std::collections::HashMap; pub struct Interner { strings: Vec<String>, rev_map: HashMap<&'strings str, usize>, }
ちなみにこのコードは以前の記事で説明した rental
crateのマクロに通すとコンパイルはできますが、 strings
に対する変更ができないので意図した通りにはなりません。
ライフタイム問題を回避する
そういうわけなので rev_map
のキーを生ポインタで保持することを考えます。つまり以下のようにすることを考えます。
use std::collections::HashMap; pub struct Interner { strings: Vec<String>, rev_map: HashMap<*const str, usize>, }
その上で、このデータ構造は以下の不変条件を満たすようにします。
rev_map
のキーに使われているポインタは常にstrings
の要素である。
非ゼロ制約をつける
HashMap
がどのような構造になっているかわからないので、パフォーマンス上の利点があると断言はできませんが、非ゼロであるとわかっているものは非ゼロにしたほうがいいはずです。そこで *const str
ではなく NonNull
を使います。
use std::collections::HashMap; use std::ptr::NonNull; pub struct Interner { strings: Vec<String>, rev_map: HashMap<NonNull<str>, usize>, }
変性を考える
今回作っている Interner
は型パラメータを持たないので、変性については特に考える必要はありません。一般論としては、 NonNull<T>
は共変なので注意が必要ですが、Cellのように特殊なことをやっていなければ共変で問題ないことが多いです。
所有を考える
今回作っている Interner
は型パラメータを持たないので、所有については特に考える必要はありません。一般論としては、自作の Drop::drop
中で drop_in_place
を呼ぶ場合には、 #[may_dangle]
と PhantomData<T>
を組み合わせて使う必要があるかもしれません。これらはdrop checkerを宥めるためのものなので、特に困っていなければ保守的に「 #[may_dangle]
をつけない」としてもたいてい安全です。
Send
, Sync
を実装する
生ポインタはデフォルトでは Send
でも Sync
でもありません。しかし、今回は他のスレッドに転送したり、複数スレッドから共有参照しても特に問題なさそうなので、 Send
と Sync
を明示的に実装します。
unsafe impl Send for Interner {} unsafe impl Sync for Interner {}
Eq
, Hash
, Borrow<str>
を実装する
おおよそ適切なデータ構造になってきましたが、 HashMap
を動作させるにはキーが Eq + Hash
を実装している必要があります。また、 &str
で検索するには、キーが Borrow<str>
を実装している必要があります。
そこで、 NonNull<T>
のラッパーを書きます。このラッパーは大変危険なことをしているので、 Interner
内部以外で使わないよう細心の注意を払う必要があります。
pub struct Interner { ... rev_map: HashMap<StrPtr, usize>, }
use std::hash::{Hash, Hasher}; use std::borrow::Borrow; struct StrPtr(NonNull<str>); impl Borrow<str> for StrPtr { fn borrow(&self) -> &str { unsafe { self.0.as_ref() } } } impl Eq for StrPtr {} impl PartialEq for StrPtr { fn eq(&self, rhs: &Self) -> bool { unsafe { str::eq(self.0.as_ref(), rhs.0.as_ref()) } } } impl Hash for StrPtr { fn hash<H: Hasher>(&self, hasher: &mut H) { unsafe { str::hash(self.0.as_ref(), hasher) } } }
実装を書く
最後に intern
の実装を書きます。順番に細心の注意を払います。まずハッシュから検索して、あったらそれを返します。そうでなかったら追加する必要があるので &str
を String
にします。ポインタの値を覚えておいて、 String
は正引き用のVecに突っ込んでしまいます。覚えておいたポインタを NonNull
で包んで、逆引き用のHashMapに追加します。 Entry
を使うと検索と追加の二度手間を短縮できるのですが、 &str
で検索しつつ String
で追加するという手順では Entry
が使えないのでここでは使っていません。
impl Interner { pub fn new() -> Self { Interner { strings: Vec::new(), rev_map: HashMap::new(), } } pub fn intern(&mut self, s: &str) -> usize { if let Some(&idx) = self.rev_map.get(s) { return idx; } let idx = self.strings.len(); let s = s.to_string(); let s_ptr = unsafe { StrPtr(NonNull::new_unchecked(s.as_str() as *const str as *mut str)) }; self.strings.push(s); self.rev_map.insert(s_ptr, idx); return idx; } pub fn get(&self, idx: usize) -> &str { &self.strings[idx] } }
完成
これでできました。確かに動いていることを確認しました。
use std::hash::{Hash, Hasher}; use std::collections::HashMap; use std::ptr::NonNull; use std::borrow::Borrow; pub struct Interner { strings: Vec<String>, rev_map: HashMap<StrPtr, usize>, } unsafe impl Send for Interner {} unsafe impl Sync for Interner {} impl Interner { pub fn new() -> Self { Interner { strings: Vec::new(), rev_map: HashMap::new(), } } pub fn intern(&mut self, s: &str) -> usize { if let Some(&idx) = self.rev_map.get(s) { return idx; } let idx = self.strings.len(); let s = s.to_string(); let s_ptr = unsafe { StrPtr(NonNull::new_unchecked(s.as_str() as *const str as *mut str)) }; self.strings.push(s); self.rev_map.insert(s_ptr, idx); return idx; } pub fn get(&self, idx: usize) -> &str { &self.strings[idx] } } struct StrPtr(NonNull<str>); impl Borrow<str> for StrPtr { fn borrow(&self) -> &str { unsafe { self.0.as_ref() } } } impl Eq for StrPtr {} impl PartialEq for StrPtr { fn eq(&self, rhs: &Self) -> bool { unsafe { str::eq(self.0.as_ref(), rhs.0.as_ref()) } } } impl Hash for StrPtr { fn hash<H: Hasher>(&self, hasher: &mut H) { unsafe { str::hash(self.0.as_ref(), hasher) } } } fn main() { let mut i = Interner::new(); for s in ["a", "c", "a", "b", "b", "c", "d", "a"].into_iter() { println!("intern({:?}) = {:?}", s, i.intern(s)); } }
最後にもう一押し: drop
の順番
おそらく今回は問題ないですが、このようなコードを書くときには drop
の順番にも気をつかう必要があります。この場合は rev_map
が先にdropされたほうが安心なので、 rev_map
に ManuallyDrop
を使います。
pub struct Interner { ... rev_map: ManuallyDrop<HashMap<StrPtr, usize>>, }
impl Drop for Interner { fn drop(&mut self) { unsafe { ManuallyDrop::drop(&mut self.rev_map); } } }
まとめ
NonNull
が安定化したので、ライフタイムではちょっと痒いところに手が届かない……というときに生ポインタを使ったコードを書きやすくなりましたが、そういったコードを書くにあたっては細心の注意が必要になります。そこで実際に生ポインタを使ったコードを書きながら、どのような点に注意をしないといけないかを復習してみました。(何か他に見落としている点があったらご指摘ください。)
2018/02/08 追記: NonNull
のsinceアトリビュートが1.24から1.25.0に修正されたのを記事に反映した。
安定化間近!Rustのimpl Traitを今こそ理解する
概要: impl Trait
が安定化間近である。これはトレイトオブジェクトと似た用途を持つが、静的ディスパッチされSized
のまま使えるため効率的である。
impl Trait
が安定化間近
Rustでは新規の機能はまずnightlyバージョンに「不安定機能 (unstable feature)」として取り入れられます。そこでの実験を経て、プログラミング言語Rustに半恒久的に導入してもよいと合意されたものだけが「安定化 (stabilize)」され、betaやstableバージョンのコンパイラでも使用できるようになります。
さて、現在 「impl Trait
」と呼ばれる機能の安定化のめどがたったというアナウンスがありました。この機能は2016年夏ごろに実装され、長い間待ち望まれてきた目玉機能のひとつでしたが、ここにきてようやっと、という感じです。そこで、 impl Trait
について今一度このブログで解説してみたいと思います。
impl Trait
が使えると何が嬉しいのか
impl Trait
は、戻り値型を隠蔽する(トレイトオブジェクトに代わる)手段を提供します。特に、クロージャやイテレータ、パーサコンビネータなど、型が煩雑になりがちなものを返したいときに有効です。 impl Trait
を使うことで、
- クロージャのようにトレイトオブジェクトにより隠蔽するしかなかったケースでは、より効率的なコードを書ける可能性があります。
- イテレータやパーサコンビネータのように隠蔽せず型を書き下しているケースでは、煩雑な型を明示しなくてよくなる可能性があります。
impl Trait
を今すぐ試すには
Rust Playgroundを使う場合は、以下の手順で試すことができます。
- Rust Playgroundの右上にある "Nightly" を選択する。
- コードの先頭に
#![feature(conservative_impl_trait, universal_impl_trait)]
を挿入する。 - 以下にあるような例を書いて試す。
手元のRustで試す場合は、以下の手順が必要です。
rustup install nightly
でnightlyをインストールする。- 以下のどちらかの方法でnightlyを有効にする。
- コードの先頭に
#![feature(conservative_impl_trait, universal_impl_trait)]
を挿入する。 - 以下にあるような例を書いて試す。
例1: クロージャを返す
与えられたクロージャを二回適用する別のクロージャを返すプログラムは、トレイトオブジェクトを使って例えば以下のように書けます。(Box<dyn Trait>
は Box<Trait>
の新しい記法です)
#![feature(dyn_trait)] pub fn twice<'a, T: 'a>(f: Box<dyn Fn(T) -> T + 'a>) -> Box<dyn Fn(T) -> T + 'a> { Box::new(move |x| f(f(x))) } // もう少し使いやすいバージョン pub fn twice<'a, T: 'a, F: Fn(T) -> T + 'a>(f: F) -> Box<dyn Fn(T) -> T + 'a> { Box::new(move |x| f(f(x))) }
これは、 impl Trait
を使うと以下のように書けます。
#![feature(conservative_impl_trait, universal_impl_trait)] pub fn twice<T>(f: impl Fn(T) -> T) -> impl Fn(T) -> T { move |x| f(f(x)) }
これで無駄な Box
とおさらばすることができます。
例2: イテレータを返す
イテレータを返す関数も、以下のように簡単に書くことができます。
#![feature(conservative_impl_trait, universal_impl_trait)] // 奇数を列挙するイテレータ fn odds() -> impl Iterator<Item=i32> { (0..).map(|x| x * 2 + 1) } fn main() { println!("{:?}", odds().take(10).collect::<Vec<_>>()) }
例3: パーサーコンビネータを返す
以前の記事でも紹介したパーサーコンビネーターライブラリcombineの場合、以下のようにBox
やparser!
を使わずに部品化することは以前から(場合によっては)可能でしたが、コンビネーターの構造が関数のシグネチャに反映されてしまうという問題がありました。
extern crate combine; use combine::{Parser, Stream, many1}; use combine::char::{letter, spaces, Letter, Spaces}; use combine::combinator::{Many1, Skip}; fn word<I: Stream<Item = char>>() -> Skip<Many1<String, Letter<I>>, Spaces<I>> { many1(letter()).skip(spaces()) } fn main() { println!("{:?}", word().parse("foo bar baz")); println!("{:?}", word().parse("012 foo bar baz")); }
これは以下のように impl Trait
を使うとすっきり抽象化することができます。
#![feature(conservative_impl_trait, universal_impl_trait)] extern crate combine; use combine::{Parser, Stream, many1}; use combine::char::{letter, spaces}; pub fn word<I: Stream<Item = char>>() -> impl Parser<Input = I, Output = String> { many1(letter()).skip(spaces()) } fn main() { println!("{:?}", word().parse("foo bar baz")); println!("{:?}", word().parse("012 foo bar baz")); }
impl Trait
とは何か
以下、 impl Trait
について詳しく説明していきます
型とトレイトは本来別物
Rustのトレイトは、C++のコンセプトやHaskellの型クラスに近いものです。型が値を分類するのに対し、トレイトは型自体を分類します。この点でJavaのインターフェースとは少し違います。(Default
やEq
などがその例です。)
しかし、トレイトから型を作る構文が2つあります。それが dyn Trait
と impl Trait
です。(dyn Trait
の dyn
は省略可能) これらはどちらも、具体的な型を隠蔽して、実装しているトレイトにだけ注目するときに使いますが、dyn Trait
は動的に、impl Trait
は静的に解決されるという違いがあります。
dyn Trait
の仕組みとデメリット
まずは見慣れた dyn Trait
から説明します。 dyn Trait
なんて見たことない、と思われるかもしれませんがそれもそのはず、この構文はRFC2113で変更されたばかりでまだ安定化されていません。Box<Trait>
とか、トレイトオブジェクトといえば通じると思います。型とトレイトは本来別物なのに、構文からそれが見えないことが混乱のもとになっていたため、トレイトオブジェクトであることを明示するために dyn
が導入されました。そのため、本記事では dyn Trait
構文を一貫して使うことにします。
dyn Trait
の仕組みは、仮想関数テーブルを用いた動的ディスパッチです。 Box<T>
を Box<dyn Trait>
に変換するとき、元の型は忘れられてしまいますが、かわりにこのポインタがfatポインタになります。つまり、 T
自体へのポインタに加えて T
の仮想関数テーブルへのポインタを保持するようになります。x86-64環境なら、 Box<T>
は8byteなのに対して、 Box<dyn Trait>
は16byteです。データ本体に仮想関数テーブルへのポインタを置くC++とは異なり、Rustではこのようにfatポインタ内仮想関数テーブルへのポインタを置きます。
この仕組みのため、dyn Trait
にはいくつかのデメリットが存在します。まず、使えるトレイトが限定されます。 dyn Trait
ではfatポインタから元の型由来の情報を復元するため、&self
引数が1個もなかったり、逆に複数ある場合には呼び出せなくなってしまいます。またfatポインタを使う都合上、self
のムーブ渡しはできません。これらの条件をオブジェクト安全性といいます。
また、必ずポインタ経由になるのと、間接コール命令になるため、実行効率が悪くなる可能性があります。
impl Trait
の仕組みとデメリット
dyn Trait
が dyn Trait
という1つの型であったのに対して、 impl Trait
は実はそういう型があるわけではありません。これらは匿名の型を表すためのシンタックスシュガーで、 impl Trait
と書くたびに別の型に翻訳されます。そのため、構文上の使える場所が限られます。
実は、この impl Trait
は、場所によって2通りに翻訳されます。
引数で使われた場合 (RFC 1591)
引数位置の impl Trait
は、匿名の型引数に翻訳されます。頻出例は以下のようにコールバック関数を使う場合です。例えば、
#![feature(conservative_impl_trait, universal_impl_trait)] // コールバックに42を渡すだけの関数 fn give_42_to_callback(callback: impl Fn(i32)) { callback(42) }
という関数があった場合、これは以下のように翻訳されます。
// コールバックに42を渡すだけの関数 fn give_42_to_callback<F: Fn(i32)>(callback: F) { callback(42) }
このように、 impl Trait
が引数で使われた場合は、 Trait
を実装する匿名の型引数に置き換えられます。したがって、引数位置の impl Trait
は単なるシンタックスシュガーですが、これは戻り値位置の impl Trait
を理解する上でも重要な点を含んでいます。つまり、
- 引数位置の
impl Trait
の型は、呼び出し側によって静的に決定される
ということです。
戻り値で使われた場合 (RFC 1522)
上に書いたことを戻り値で置き換えたものがそのまま成り立ちます。つまり、
- 戻り値位置の
impl Trait
の型は、呼び出された側によって静的に決定される
ということです。この「呼び出された側によって決まる型」は存在型といいますが、このための構文はまだRustには実装されていません。ここでは、将来実装されるであろうRFC2071から記法を借用することとすると、
#![feature(conservative_impl_trait, universal_impl_trait)] // 42を返すクロージャを返す fn defer_42() -> (impl Fn() -> i32) { || 42 }
は、以下のように匿名の存在型に置き換えられると考えることができます。
#![feature(???)] // 42を返すクロージャを返す fn defer_42() -> Anon1 { || 42 } existential type Anon1: Fn() -> i32;
Fn() -> i32
を実装する特定の型だが、その中身が何なのかは明かされないのがポイントです。このexistential typeはnewtypeパターンとも似ていますが、クロージャのような特殊な型も含められることと、手動で Fn() -> i32
を実装しなくてもよいところが特徴です。
デメリット
されこの impl Trait
ですが、まず使える場所が限られるのが一つ目のデメリットです。いくつか拡張案がありますが、今回安定化される conservative_impl_trait
と universal_impl_trait
では、関数/メソッドでしか使うことができません。また、トレイトメソッドの戻り値には使用できません。
もう一つのデメリットとして、あくまで元の型を型システム上隠蔽しているだけなので、動的に内容を切り替えることはできません。例えば、以下のように条件に応じて異なる型のイテレータを返すコードは、 impl Trait
では実現できません。
#![feature(conservative_impl_trait, universal_impl_trait)] use std::iter; // nの倍数を列挙 (コンパイルエラー) fn multiples_of(n: i32) -> impl Iterator<Item=i32> { if n == 0 { //~ERROR if and else have incompatible types iter::once(0) } else { (0..).map(move |m| n * m) } }
ifを動かすなどして型を揃えるか、あきらめて dyn Trait
を使うのが正解です。
#![feature(dyn_trait)] use std::iter; // nの倍数を列挙 fn multiples_of(n: i32) -> Box<dyn Iterator<Item=i32>> { if n == 0 { Box::new(iter::once(0)) } else { Box::new((0..).map(move |m| n * m)) } }
ただし、上の例のような単純なケースであればeither
クレイトで解決できる場合もあります。(Either
はIterator
を透過する実装になっているため)
#![feature(conservative_impl_trait, universal_impl_trait)] extern crate either; use std::iter; use either::{Left, Right}; // nの倍数を列挙 fn multiples_of(n: i32) -> impl Iterator<Item=i32> { if n == 0 { Left(iter::once(0)) } else { Right((0..).map(move |m| n * m)) } }
より詳しい比較
ここから先は、 dyn Trait
と impl Trait
について、より詳しく比較しながら説明していきます。
書ける場所
dyn Trait
は普通の型なので、型の出現する場所ならどこでも使えます。 (ただし、 Sized
でないために限定される)
impl Trait
は、今回安定化される範囲内では、以下の位置に出現できます。
- 関数(通常の関数、固有実装のメソッド、トレイトのメソッド、トレイト実装のメソッド) の引数と境界の中。 (
#![feature(universal_impl_trait)]
) - 関数のうち、「通常の関数」と「固有実装のメソッド」の戻り値。 (
#![feature(conservative_impl_trait)]
)
ただし、丸括弧記法 (Fn(T) -> U
の T
と U
の位置) には出現できません。また、 impl Trait
の中に impl Trait
をネストさせることもできません。
括弧の位置
dyn Trait
と impl Trait
の括弧の位置について、mini-RFC 2250 で議論中です。 &(x + y)
や &(Trait + Send)
との一貫性を保ちつつ、使いやすく間違いにくい構文が望まれていますが、残念ながら万能な方法はなさそうです。細かい論点があって整理するのが大変ですが、結論としては以下のような妥協点で落ち着きそうです。
+
は&
より弱い。つまり、+
を使うときは&(dyn Error + Send)
のように括弧を入れる必要がある。- 同様に、
fn foo() -> impl Fn() -> (dyn Error + Send)
のようにFn() ->
の直後で+
を使う場合も括弧が必要。 - 上との一貫性を保つため、
fn foo() -> (impl Error + Send)
の位置にも(+
を使う場合は)括弧が必要。
いずれにせよ、 dyn Trait
と impl Trait
はどちらも新規構文で、特に構文を分ける必要はないため、この2つの間の差異はなさそうです。
トレイト境界とライフタイム境界
dyn Trait
と impl Trait
では、書ける境界の種類が異なります。
dyn Trait
に書けるもの- ちょうど1個の主トレイト。object-safeでなければならない。必ず最初に書く。
- 0個以上の追加トレイト。auto traitでなければならない。
- 高々1個のライフタイム。0個の場合は省略されたとみなされる(推論方法は後述)。
impl Trait
に書けるもの- 1個以上のトレイト。順番に意味はないが、最初はトレイトでなければならない。
- 0個以上のライフタイム。
トレイトがobject-safeであるとは、以下の条件を満たしていることをいいます。
- 直接的または間接的な出力が全て埋められている (e.g.
dyn Iterator<Item=char>
はOK,dyn Iterator
はダメ) - 直接的または間接的に
Self: Sized
を含意していない。 (e.g.dyn Default
はダメ) - 祖先トレイトを含む全てのメソッドがobject-safeである。メソッドがobject-safeであるとは、そのメソッドが
Self: Sized
を含意しているか、または以下の条件を満たしていることをいう。- 型パラメーターを持たない。
- 第一引数が
&self
,&mut self
,self: Box<Self>
のいずれかである。 - 他に
Self
が出現しない。 (Self::Item
とかはOK)
auto trait は、名前通り auto trait
で宣言されているトレイトで、 Send
, Sync
, UnwindSafe
, RefUnwindSafe
などがそれに当たります。
dyn Trait
のライフタイムは大まかにいうと次のように推論されます。
- 明示されているときはそれが使われる。
- そうでないとき、
Trait
に適切なSelf: 'a
境界があればそれが使われる。例えば、Box<dyn Any>
はBox<dyn Any + 'static>
である。 (RFC 0192) - そうでないとき、
dyn Trait
が構文上参照で囲まれていればそれが使われる。例えば、&'a dyn Fn()
は&'a (dyn Fn() + 'a)
である。 (RFC 0599) - そうでないとき、関数内の場合は匿名のライフタイムが割り当てられ、関数外のときは
'static
が採用される。例えば、Box<Fn()>
を返す関数の戻り値はBox<Fn() + 'static>
である。 (RFC 1156)
ライフタイムに関する仮定
dyn Trait
と impl Trait
では、ライフタイムに対する仮定は大きく異なります。
dyn Trait
の値は全く未知の型に由来する可能性があり、ライフタイムについては書かれている境界からしか推測できません。ライフタイムを省略した場合に上記のように推論されるのはそのためです。(0個=どのような生存期間も仮定できない、となってしまうため)impl Trait
は「関数の型引数」と「関数のライフタイム引数のうち、impl Trait
内に構文的に出現するもの」でパラメーター化されたnewtypeに過ぎないため、これらのパラメーターが生きていれば生きていることがわかります。
後者はわかりにくいので補足します。例えば、
fn foo<T, U>() -> impl Fn() { .. }
というシグネチャの場合、 impl Fn()
にはライフタイム境界がついていません(dyn Trait
と異なり、推論されているわけでもありません)。しかし、 dyn Trait
とは異なり、この場合は impl Fn(): 'a
となる十分条件が残されています。それは、 T: 'a, U: 'a
となることです。(impl Fn()
の中身は Anon1<T, U>
のような型であるため)
同一性
上述のように、 dyn Trait
は構文的に同じなら全て同じ型なのに対し、 impl Trait
は出現ごとに全く異なる型になります。つまり、
fn foo1() -> Box<dyn Trait> { .. } fn foo2() -> Box<dyn Trait> { .. } fn foo3() -> impl Trait { .. } fn foo4() -> impl Trait { .. }
に対して、 if true { foo1() } else { foo2() }
は通りますが、 if true { foo3() } else { foo4() }
はコンパイルエラーになります。
impl Trait
の実際の型は位置だけではなくて、その関数のジェネリクス引数にも依存します。具体的には以下のジェネリクス引数に依存します。
- その関数の全ての型引数。
- その関数のライフタイム引数のうち、
impl Trait
の境界部分に構文的に出現するもの。
以下の例を参照してください。
#![feature(conservative_impl_trait, universal_impl_trait)] use std::fmt; // T に依存したものは常に返せる fn foo1<T: fmt::Debug>(x: T) -> impl fmt::Debug { x } // 'a に依存したものは返せない fn foo2<'a>(x: &'a i32) -> impl fmt::Debug { x // ERROR } // 'a は明示的に含まれるため、 'a に依存したものも返せる fn foo3<'a>(x: &'a i32) -> (impl fmt::Debug + 'a) { x }
トレイトの透過性
dyn Trait
も impl Trait
も、基本的にその境界に書かれているトレイトのみを仮定できます。しかしたとえば以下のような例外があります。
dyn Trait: !Sized
である。impl Trait: Sized
である。dyn Trait: Drop
である。impl Trait: !Drop
である。dyn Trait
は、境界に書かれていない限り、auto trait (Send
やSync
など)を自動で導出することはない。一方、impl Trait
は、もとの型のauto traitを継承する。
まとめ
以下の内容を説明しました。
impl Trait
が安定化されると何が嬉しいのか?→クロージャなど特殊な型を使うコードが効率的・簡潔に書けるようになる。それがstableバージョンのコンパイラで使えるようになるimpl Trait
の試しかたdyn Trait
とimpl Trait
の違い: どちらも型の素性を隠して「特定のトレイトを実装している」という風に抽象化するが、dyn Trait
は動的、impl Trait
は静的な抽象化をするため、使える場面に違いがある。- より詳しい挙動の説明
追記 (2018/02/04): either
クレイトを使った方法について説明しました。