binfmt_miscの力でBOM shebangをサポートする

概要: binfmt_miscを使うとBOM shebangを擬似的にサポートできる。ただしインタプリタ側がサポートしてないと意味がない。

事の発端

Windowsのメモ帳がLF改行をサポート→でもUTF-8で保存しようとするとBOMがついて悲しい→shebangにBOMがつくと動かないのが悲しい

やったこと

Linuxbinfmt_miscという機能を使って、BOMのついたshebangを動くようにしてみました。

github.com

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を試すにはLinuxMac環境が必要で、Windowsを持っている人はVMかWSLを使って試すのが一般的のようでした。

今回Windows用ビルドを整備したので、これからはWindowsネイティブ環境へのSATySFiの導入が簡単になります。

仕組み

OCamlWindowsとの相性が悪いですが、今回は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の構文に沿ってインデントします。例えば
    • | は対応する |, match, let-rec, type などにあわせてインデントされます。
    • let-rec は直前のトークンに応じて、 let-in式かトップレベル定義か判別され、トップレベル定義ならレベル0にインデントされます。
    • 水平モードでは、 ** のようなバレットを認識し、アスタリスクの個数に応じてインデントされます。

ちなみに

書いてから調べてみたら同名の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 の書き込みロックを持ったスレッドがパニックすると、その途中の値は不変条件が壊れている可能性があります。これを他のスレッドが間違って読まないようにするため、 MutexRwLock はロック(書き込みロック)を持ったスレッドがパニックした場合、poisonedフラグが立てられ、次回以降のロックが失敗するようになります。

poisonedフラグを元に戻す方法はないようですが(多分)、poisonedフラグによりエラーになった場合、返されたエラーから強制的に壊れた値を読みに行くことはできるようになっています。

パニックの流れ

ここまで、パニックに関連する基本的な注意事項をまとめました。ここからはパニックの仕組みを調べていきます。

まず、ユーザープログラムから見たパニックの流れを説明します。パニックはスレッドごとに処理されます。各スレッドの正常系をここでは次のような図であらわすことにします:

f:id:qnighy:20180218213528p:plain

パニック処理の基本的な流れ (-C panic=unwind) は以下のようになります。

f:id:qnighy:20180218213656p:plain

ただし、 -C panic=abort が指定されているときは以下のようになります。

f:id:qnighy:20180218213741p:plain

パニックハンドラ

パニックハンドラはパニック時にまず呼ばれる処理で、主にスタックトレースの表示などを担当します。デフォルトの処理は以下のようになっています。

  • もしパニックカウントが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に動機が説明されています。

パニック処理の場所

パニックの処理は標準ライブラリとコンパイラの複数の箇所に分散しており追跡が困難です。ここに概要をまとめておきます。

まとめ

パニック機構について説明しました。前半ではパニック機構の注意事項(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 という名前になりました。 (Uniquelibcore 内部には残っていますが、安定化の予定はなくなりました。) 予定通りに進めば、 Rust 1.25.0 から使えるようになるはずです。

Rustのポインタ関連型は仕様の微妙な違いを意識して使い分ける必要があります。以下にそれを列挙しました。

分類 エイリアス 変性 所有 非0 Send Sync
&T 参照 なし※1 共変 × 継承※2 継承
&mut T 参照 なし 非変 × 継承 継承
&Cell<T> 参照 あり 非変 × × ×
Box<T> スマート
ポインタ
なし 共変 継承 継承
*const T 生ポインタ 共変 × × × ×
*mut T 生ポインタ 非変 × × × ×
NonNull<T> 生ポインタ 共変 × × ×
  • ※1 &TTUnsafeCell を含まないときだけエイリアスなしと仮定される
  • ※2 &T: SendT: 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 でもありません。しかし、今回は他のスレッドに転送したり、複数スレッドから共有参照しても特に問題なさそうなので、 SendSync を明示的に実装します。

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 の実装を書きます。順番に細心の注意を払います。まずハッシュから検索して、あったらそれを返します。そうでなかったら追加する必要があるので &strString にします。ポインタの値を覚えておいて、 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_mapManuallyDrop を使います。

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を使う場合は、以下の手順で試すことができます。

  1. Rust Playgroundの右上にある "Nightly" を選択する。
  2. コードの先頭に #![feature(conservative_impl_trait, universal_impl_trait)] を挿入する。
  3. 以下にあるような例を書いて試す。

手元のRustで試す場合は、以下の手順が必要です。

  1. rustup install nightly でnightlyをインストールする。
  2. 以下のどちらかの方法でnightlyを有効にする。
    • cargo +nightly build のように、コマンドに毎回 +nightly をつけることで、一時的にnightlyを有効にできます。
    • 特定のディレクトリで rustup override set nightly を実行することで、そのディレクトリ内で半恒久的にnightlyを有効にできます。
  3. コードの先頭に #![feature(conservative_impl_trait, universal_impl_trait)] を挿入する。
  4. 以下にあるような例を書いて試す。

例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の場合、以下のようにBoxparser!を使わずに部品化することは以前から(場合によっては)可能でしたが、コンビネーターの構造が関数のシグネチャに反映されてしまうという問題がありました。

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のインターフェースとは少し違います。(DefaultEqなどがその例です。)

しかし、トレイトから型を作る構文が2つあります。それが dyn Traitimpl Trait です。(dyn Traitdyn は省略可能) これらはどちらも、具体的な型を隠蔽して、実装しているトレイトにだけ注目するときに使いますが、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 Traitdyn 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_traituniversal_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クレイトで解決できる場合もあります。(EitherIteratorを透過する実装になっているため)

#![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 Traitimpl Trait について、より詳しく比較しながら説明していきます。

書ける場所

dyn Trait は普通の型なので、型の出現する場所ならどこでも使えます。 (ただし、 Sized でないために限定される)

impl Trait は、今回安定化される範囲内では、以下の位置に出現できます。

  • 関数(通常の関数、固有実装のメソッド、トレイトのメソッド、トレイト実装のメソッド) の引数と境界の中。 (#![feature(universal_impl_trait)])
  • 関数のうち、「通常の関数」と「固有実装のメソッド」の戻り値。 (#![feature(conservative_impl_trait)])

ただし、丸括弧記法 (Fn(T) -> UTU の位置) には出現できません。また、 impl Trait の中に impl Trait をネストさせることもできません。

括弧の位置

dyn Traitimpl 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 Traitimpl Trait はどちらも新規構文で、特に構文を分ける必要はないため、この2つの間の差異はなさそうです。

トレイト境界とライフタイム境界

dyn Traitimpl 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 のライフタイムは大まかにいうと次のように推論されます。

  1. 明示されているときはそれが使われる。
  2. そうでないとき、 Trait に適切な Self: 'a 境界があればそれが使われる。例えば、 Box<dyn Any>Box<dyn Any + 'static> である。 (RFC 0192)
  3. そうでないとき、 dyn Trait が構文上参照で囲まれていればそれが使われる。例えば、 &'a dyn Fn()&'a (dyn Fn() + 'a) である。 (RFC 0599)
  4. そうでないとき、関数内の場合は匿名のライフタイムが割り当てられ、関数外のときは 'static が採用される。例えば、 Box<Fn()> を返す関数の戻り値は Box<Fn() + 'static> である。 (RFC 1156)

ライフタイムに関する仮定

dyn Traitimpl 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 Traitimpl Trait も、基本的にその境界に書かれているトレイトのみを仮定できます。しかしたとえば以下のような例外があります。

  • dyn Trait: !Sized である。 impl Trait: Sized である。
  • dyn Trait: Drop である。 impl Trait: !Drop である。
  • dyn Trait は、境界に書かれていない限り、auto trait (SendSyncなど)を自動で導出することはない。一方、 impl Trait は、もとの型のauto traitを継承する。

まとめ

以下の内容を説明しました。

  • impl Trait が安定化されると何が嬉しいのか?→クロージャなど特殊な型を使うコードが効率的・簡潔に書けるようになる。それがstableバージョンのコンパイラで使えるようになる
  • impl Trait の試しかた
  • dyn Traitimpl Trait の違い: どちらも型の素性を隠して「特定のトレイトを実装している」という風に抽象化するが、 dyn Trait は動的、 impl Trait は静的な抽象化をするため、使える場面に違いがある。
  • より詳しい挙動の説明

追記 (2018/02/04): eitherクレイトを使った方法について説明しました。