Rustの身代わりパターン

Rust

概要: &mut 参照に対して所有権が必要な操作をするときは特定のパターンが用いられる。これを身代わりパターンとでも呼ぶことにする。

例: 単方向リンクリスト

またしても単方向リンクリストを考える。

struct List<T> {
    root: Option<Box<Node<T>>>,
}
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

これに対する push_front を実装してみる。ナイーブに書くと以下のような感じになる。

impl<T> List<T> {
    fn push_front(&mut self, value: T) {
        self.root = Some(Box::new(Node {
            value: value,
            next: self.root,
        }));
    }
}

ところがこれはエラーになる。

error[E0507]: cannot move out of borrowed content
  --> <anon>:13:19
   |
13 |             next: self.root,
   |                   ^^^^ cannot move out of borrowed content

身代わりパターン

最も重要な問題は、 push_front は self.root の所有権を持っていないということになる。このような場合は std::mem::replace を使って中身を取り出す。 replace は代わりの中身が必要なので、 None を入れることにする。

impl<T> List<T> {
    fn push_front(&mut self, value: T) {
        self.root = Some(Box::new(Node {
            value: value,
            next: ::std::mem::replace(&mut self.root, None),
        }));
    }
}

身代わりパターンの一般化

身代わりパターンを一般化すると以下のような関数になる。

fn owned_convert<T: Default, F: FnOnce(T) -> T>(this: &mut T, f: F) {
    *this = f(::std::mem::replace(this, T::default()));
}

このような場合には Default トレイト が使いやすい。

unsafeな身代わりパターン

もしデフォルト値がない場合に、以下のような処理をしたとすると、どうなるだろうか。例えば以下のような関数を書くことができる。

unsafe fn unsafe_owned_convert<T, F: FnOnce(T) -> T>(this: &mut T, f: F) {
    ::std::ptr::write(this, f(::std::ptr::read(this)));
}

ところがこの関数は使い方によってはunsafeな動作をする。つまり以下のように書いてはいけない。

// Unsound!
fn unsafe_owned_convert<T, F: FnOnce(T) -> T>(this: &mut T, f: F) {
    unsafe {
        ::std::ptr::write(this, f(::std::ptr::read(this)));
    }
}

一見すると、 this はエイリアスのない妥当なポインタだから、thisから中身を一度取り出して、また保存すれば問題なさそうに見える。

ところが、Rustのsafetyを議論するさいは、 panic! 等によるunwindの可能性も考慮しなければならない。上の例では、 f は任意のクロージャーのため、 panic! する可能性が残されている。 f が panic! すると、 this にはmoveされて無効になったはずの値が残っていることになる。 Box なら2重freeが発生することになる。

まとめ

Rustでは常にunwindされてもUBが発生しないようにしなければならない。そのため &mut 参照から所有権を取り出すには、何か代わりのものを置く必要がある。このような操作には std::mem::replace を使うことができる。身代わりを一般的な型に対して要求するときは std::default::Default traitを使うことができる。

Rustコンパイラのデバッグ出力を見る

Rust

Rustコンパイラの細かい挙動を追うには、コンパイラ内に設置してある debug!(..) の出力を追う手がある。

デバッグ出力を有効化してコンパイラをビルドする

まず手元のRustコンパイラのソースから、デバッグ出力を有効化したコンパイラを作成する必要がある。

それにはまず src/bootstrap/config.toml.example をコピーして config.toml を作成し、以下の設定をする。

[rust]
debug-assertions = true

この状態でビルドする。

$ ./x.py build

デバッグ出力を有効にしてコンパイラを起動する

RUST_LOG 環境変数によりログを制御することができる。

$ RUST_LOG=rustc_typeck,rustc_mir,rustc::ty build/x86_64-unknown-linux-gnu/stage1/bin/rustc test.rs

RUST_LOGのフォーマット

RUST_LOG は以下のフォーマットを持つ。

  • ログレベル指定
  • ログレベル指定/フィルター

ログレベル指定はモジュールごとにカンマ区切りで指定する。カンマで区切られた各要素は以下のフォーマットに従う。

  • ログレベル
  • モジュール
  • モジュール=
  • モジュール=ログレベル

ログレベルは以下のどちらかである。

  • 非負整数。
  • error, info, warn, debug, traceのいずれかの文字列。大文字小文字は区別しない。それぞれ1,2,3,4,5に対応する。

ログレベルを省略したときは最大(全てのレベルが出力される)の意味になる。

ログレベルのみを指定したときはモジュールとして空文字列を指定したのとほぼ同じ動作をする。

モジュール指定は、ログ出力命令のあるモジュールのパスに、文字列として先頭一致で判定される。複数の指令に該当する場合は最長一致で採用される。

フィルターを指定した場合は、それが部分文字列として含まれているログのみ出力される。

Rustの基本型のメソッドはどこで定義されているか

Rust

概要: Rustの基本型そのものはコンパイラで特別に定義されている。では型に関連づけられたメソッドはどこにあるのか。

固有メソッドのありか

固有メソッドは core の各所で定義されている。例えば i32 の固有実装は core::numに定義されている。

#[lang = "i32"]
impl i32 {
    ...
}

ここで、 #[lang = "i32"] に注意する必要がある。基本型の固有実装にはそれぞれlang item markerが割り当てられている。実際の固有メソッド解決はこのlang item marker経由で行われているようである。

なお、数値型以外の基本型の固有実装は以下の場所に定義されている。

トレイト実装のありか

トレイト実装は固有実装のような特別扱いを受けない。固有実装と同じように基本型ごとにまとめられたモジュールで定義されるか、各トレイトの近くで定義されることが多いようである。

演算子のありか

トレイト実装のなかでも、いくつかの演算子の実装は特別な扱いを受ける。というのも、標準ライブラリ内での基本型の演算子の実装はおおむね以下のような形になっているのである。

impl core::ops::Add<i32> for i32 {
    type Output = i32;
    fn add(self, other: i32) -> i32 {
        self + other
    }
}

これは一見すると循環論法であるが、そうではない。実は話が逆で、ユーザー定義型の場合は + は std::ops::Add の糖衣構文だが、基本型については + が組込みで、それを用いて std::ops::Add の実装が与えられているというわけである。

実は、Rust 1.17.0 では、上のような実装をそのまま用いて型検査を行う。つまりこの時点では実際に self + other は <i32 as core::ops::Add<i32>>::add(self, other) と認識されている。

もちろん、そのままコード生成に進むと無限ループが生成されてしまうので、型検査のあとに、メソッド解決の情報を削除することでワークアラウンドしている。ここで削除されるのは、スカラーに対する1項演算か、スカラー同士の2項演算である。ここでいうスカラーとは、 bool, char, 整数、浮動小数点数、関数ポインタ、生ポインタである。

演算子はどう変換されるか

続いて、スカラーに対する演算子は、HIRからHAIRへの変換時に組込みの演算子に変換される。

さらにHAIRはMIRに変換されるが、スカラーに対する基本演算はどれも右辺値を生成するため、最終的には as_rvalue のビルダーで処理される。

コードを見るとわかるように、スカラーに対する基本演算にオーバーフローチェックが入るのはこのタイミングである。オーバーフローチェックが生成されるかどうかは次の基準で決定されている。

  • コンパイラオプションでオーバーフローチェックを有効にするよう指定された。 または
  • 定数が要求されている文脈である。 または
  • #[rustc_inherit_overflow_checks] が指定された。

ただしコンパイラオプションは以下のように解釈される。

  • -C overflow-checks があれば、そのyesまたはnoが採用される。
  • 上が指定されておらず、 -Z force-overflow-checks が指定されていれば、そのyesまたはnoが採用される。
  • 上のいずれも指定されていない場合は、 -C debug-assertions の値が採用される。

まとめ

Rustの基本型のうち、固有実装はlang item経由で発見される。トレイト実装は一般的な仕組みを使っているが、演算子だけは例外で、HIR→MIRへの変換時に組込みの演算に変換される。

RustマクロでFizz Buzz

Rust

RustのマクロでFizz Buzzを書いてみた。

gist.github.com

このFizz Buzzは、ループと倍数判定をマクロで処理している。10進数として表示する部分はマクロではなくRust本体に任せていりう。

動作の説明

Rustの macro_rules! でメタプログラミングを行う場合、トークン単位での処理が基本となる。そのため使えるマッチャーは基本的に tt マッチャーだけである。 tt マッチャーは、トークンツリー(括弧以外のトークンか、括弧で囲まれた任意のトークン列)1個にマッチする。

他のマッチャーを使うと、その部分は構文解析されてASTに変換される。ASTに変換された部分は単一のトークンとみなされてしまい、 macro_rules! からは非透過的にしか扱えない。

    macro_rules! fizzbuzz_cond {
        ...
    }

このマクロは、特定の2進数に対するFizzBuzz判定を呼ぶ。引数は、

  • 入力した2進数の残り (0,1のトークン列で表現する。大きい桁から順番に消費する)
  • 消費した部分のmod 3 (1の個数で表現する)
  • 消費した部分のmod 5 (1の個数で表現する)
  • 消費した部分をあらわす整数型の式 (printするために使う)

である。このマクロは次のように動作する。

  • mod 3とmod 5をあらわす部分が大きすぎる場合は、削ってやり直す。
  • まだ入力が残っていれば、これを処理する。処理中の数を2倍するか、2倍して1を足す。
  • 入力が残っていなければ、printをするための文を出力する。このときmod 3とmod 5に応じて分岐する。
    macro_rules! fizzbuzz_rec {
        ...
    }

このマクロは、指定された範囲のFizzBuzzを実行する。引数は、

  • 開始位置と終了位置をあらわす、同じ桁数の2つの2進数。 (0 1 1 0), (1 0 1 1) のような別々の形ではなく、桁ごとにzipした ((0, 1) (1, 0) (1, 1) (0, 1)) のような形で持つ。これは桁数の不一致によるミスを防ぐほかに重要な意味がある。この方法だと、全ての桁を0で置きかえる操作がしやすい。
  • 確定した部分の2進数。

である。 fizzbuzz_rec! は、2進数の桁の構造にもとづいて再帰的に fizzbuzz_rec! を呼ぶ。このような仕組みにしているのは、こうすると再帰深度をlogに抑えることができるからである。

    macro_rules! fizzbuzz {
        ...
    }

このマクロは、単に fizzbuzz_rec! を呼び出すドライバである。

Rustにおけるマクロメタプログラミングの特徴

実用的には、Rustの宣言的マクロは、boilerplate的なコードを大量に作る必要があり、型多相性を駆使するよりも構文的に生成したほうがうまくいく場合に、強力な効果を発揮する。むろん、このFizz Buzzのような例は遊び以上の意味はない。

マクロメタプログラミングをしてみてわかった強い制約は、マクロ呼び出しの結果の再利用の難しさである。マクロの入力がトークン列であるのに対して、マクロの出力は抽象構文木である。抽象構文木はトークン列として再解釈できるものの、各抽象構文木は単一のトークンでラップされてしまい、宣言的マクロからは透過的にしか取り扱えない。これは実用上はほぼ問題ないが、マクロメタプログラミングにとっては重大な障壁となる。関数によるプログラムの構造化を妨げているからである。これにより、マクロメタプログラミングでは実質的に、末尾再帰的な方法でしかプログラムを構造化できないことになる。

それに加えて、Rustのマクロは厳しい展開深度制限がある(crateの属性で拡張できる)。展開深度制限は通常、今回実装したように再帰深度をlogに抑えるテクニックを用いて回避することが多い。しかし、Rustマクロメタプログラミングでは末尾再帰的な書き方しかできないから、このテクニックが一般的には使えないと考えられる。

Rustのマクロメタプログラミングは、Cのプリプロセッサメタプログラミングと比べても、決して自由度が高いとはいえないだろう。これはもちろん悪いことではない。メタプログラミングの容易さは、コンパイラやソースコード解析ツールなどにとっての扱いやすさとトレードオフの関係にあるからである。Rustのマクロメタプログラミングがこのように難しいのもまたこのトレードオフの結果だと考えられる。またそもそも、遊びとしてのメタプログラミングは、このように少し難しいくらいが面白い。

Typed Arenaとdropck

Rust

概要: Typed Arenaはdropckの目的を説明するよい例になっている。

Typed ArenaとDrop

以前 Typed Arenaの紹介記事 を書いたが、このソースコードに以下のように Drop の実装を足してみる。

extern crate typed_arena;

use std::cell::RefCell;
use typed_arena::Arena;

struct NodeData<'a> {
    references: RefCell<Vec<Node<'a>>>
}
type Node<'a> = &'a NodeData<'a>;

impl<'a> Drop<'a> for NodeData<'a> {
    fn drop(&mut self) {}
}

fn main() {
    let nodes = Arena::new(); // mut は不要
    let node0 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node0);
    let node1 = nodes.alloc(NodeData { references: RefCell::new(vec![]) });
    node0.references.borrow_mut().push(node1);
}

すると、Dropの実装を足しただけなのにコンパイルエラーになる。

これは以前の記事で説明したdropck規則によるものであるが、該当記事で説明した例よりもこちらの例のほうがわかりやすいかもしれない。

不健全性の説明

この例がコンパイルされると何が問題なのか？それは、 node0とnode1のデストラクタは、どちらかが先に呼び出される、という点が関係している。

仮にnode1がnode0よりも先にデストラクトされたとする。この場合node0のデストラクタが呼ばれた時点でnode1のデストラクト処理は完了している。しかしnode0はnode1へのポインタを握っているので、node0のデストラクタの中でnode1の廃墟を探索することができる。もちろんこれらの多くは無効なデータであり、触っただけで爆発するかもしれない、ということになる。

まとめ

Typed Arenaはdropckの目的を説明するよい例になっている。

RustのNULLポインタ最適化

Rust

概要: RustのNULLポインタ最適化について説明する。

NULLポインタ最適化とは

以下のようにポインタ型のOptionが、元のポインタと同じサイズになる最適化である。NULLをNoneに割り当てている。

fn main() {
    println!("{}", std::mem::size_of::<Box<u32>>()); // 8
    println!("{}", std::mem::size_of::<Option<Box<u32>>>()); // 8
}

non-zero typeの定義

NULLポインタ最適化は、non-zero typeをoption-like typeで包んだ場合に発生する。以下が1.17.0時点でのnon-zero typeの定義である。

  • 関数ポインタ
  • 参照 (fat pointerも含む)
  • Box<T> (fat pointerも含む)
  • NonZero<*mut T>, NonZero<*const T> (fat pointerも含む)
  • NonZero<i32> 他、組込み整数型を包んだもの
  • C-like enum であって、全てのバリアントのdiscriminantが非0であるもの
  • Univariant ADT (NonZero 以外) であって、1つ以上のフィールドがnon-zero typeをもつもの
  • サイズ1以上の固定長配列であって、要素型がnon-zero typeであるもの

ただし、

  • レイアウト決定の観点からいうC-like enumとは、1つ以上のバリアントからなり、各バリアントのフィールドの個数が0である列挙型である。discriminantはバリアントを区別するためのタグであり、構文上のC-like enum (全てのバリアントがユニットバリアントであるもの) であればdiscriminantを明示的に指定できる。
  • Univariant ADTとは、レイアウト上構造体と同様に扱われる型のことで、次のいずれかである。
    • 列挙型であって、高々1個のバリアントからなり、#[repr(C)] も #[repr(u8)] (あるいは他の整数型) も指定されていないもの。ただし、C-like enumに該当する場合はそれが優先されるバグがある。 (Rust Issue #37649)
    • 構造体 (NonZero, Box以外)。
    • タプル。
    • クロージャ。
  • Univariant ADTや固定長配列では、non-zero fieldの候補が複数ある場合がある。Univariant ADTでは、ソースコード順で最も若いフィールドが選択される。固定長配列では、0番目の要素が選択される。

なお、 core::nonzero::NonZero も alloc::boxed::Box もlang item (処理系により特別扱いされるアイテム) である。 NonZero のインターフェースはunstableである。

option-like typeの定義

option-like typeという用語があるわけではないが、わかりやすいのでこのように称する。option-like typeは以下のような型である。

  • 列挙型である。
  • ちょうど2個のバリアントからなる。
  • #[repr(C)] も #[repr(u8)] (あるいは他の整数型) も指定されていない。
  • 一方のバリアントのフィールドが全てzero-sizedである。

このoption-like typeがさらに以下の条件を満たすとき、NULLポインタ最適化が行われる。

  • もう一方のバリアントに、non-zero typeをもつフィールドがある。 (このときそのフィールドはzero-sizedでないことに注意)

NULLポインタ最適化の実装

NULLポインタ最適化の対象になった列挙型は、Univariant ADTでないにもかかわらずdiscriminantが削除される。かわりに、発見された最も若いnon-zero fieldを(再帰的に)探し、その部分がゼロかどうかで、どちらのバリアントであるかを判断する。

逆にバリアントを代入する際は、該当のフィールドにゼロを代入する。ただしARMアーキテクチャではLLVMのバグを踏まないために列挙型全体をゼロで初期化する。

まとめ

Rustには、参照を直接的または間接的に含む型など、全体がゼロにはなりえない型がいくつか存在する。これらの型に1つの特別な値を付与した列挙型は、もとの型と同じデータ長で表現される。

末尾再帰をループにできないRustプログラムの例

Rust

概要: 生存期間の関係で、ループでは書けないが末尾再帰では書けるアルゴリズムの例を挙げる。

単方向リンクリスト

次のような単純なリンクリストを考える。

struct List<T> {
    root: Option<Box<Node<T>>>,
}
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

backの実装

単方向リンクリストの末尾要素の取得は O(n) である。これは次のように書くことができる。

impl<T> List<T> {
    fn back(&self) -> Option<&T> {
        let mut node = if let Some(ref b) = self.root {
            b.as_ref()
        } else {
            return None;
        };
        while let Some(ref b) = node.next {
            node = b.as_ref();
        }
        Some(&node.value)
    }
}

これは末尾に到達するまでノードを操作し、最後のノードの値を取り出すだけのコードである。

push_backの実装

同じ要領でpush_backを書こうとすると以下のようになる。

impl<T> List<T> {
    fn push_back(&mut self, value: T) {
        let mut node : &mut Option<Box<Node<T>>> = &mut self.root;
        while let Some(ref mut b) = *node {
            node = &mut b.next;
        }
        *node = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
}

しかしこのコードは生存期間エラーが発生する。

rustc 1.17.0 (56124baa9 2017-04-24)
error[E0499]: cannot borrow `node.0` as mutable more than once at a time
  --> <anon>:23:24
   |
23 |         while let Some(ref mut b) = *node {
   |                        ^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
30 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> <anon>:24:13
   |
23 |         while let Some(ref mut b) = *node {
   |                        --------- borrow of `node` occurs here
24 |             node = &mut b.next;
   |             ^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `*node` because it is borrowed
  --> <anon>:26:9
   |
23 |           while let Some(ref mut b) = *node {
   |                          --------- borrow of `*node` occurs here
...
26 |           *node = Some(Box::new(Node {
   |  _________^ starting here...
27 | |             value: value,
28 | |             next: None,
29 | |         }));
   | |___________^ ...ending here: assignment to borrowed `*node` occurs here

error: aborting due to 3 previous errors

おそらく、このpush_back関数をループで書く方法は存在しない。これは生存期間のネストの深さを考察することで導くことができる。

生存期間のネスト

backもpush_backも、根ノードから順にノードを辿っていくという点は同様である。このとき、各ノードの参照は、直前のノードから借用した形になっている。したがって生存期間は以下のようにネストしていることになる。

f:id:qnighy:20170505221029p:plain

ところでbackのループではnodeは共有参照の形で持っている。したがって上の図でnode1が生存している間も、node0の参照は有効である。共有参照の借用では、node1の生存期間を延長して解釈しても、node0の有効期間に影響を与えないので、これらの生存期間を以下のように延長して解釈する。

f:id:qnighy:20170505221921p:plain

このように解釈すると、生存期間のネストを考えずにすむ。全てのノード参照が同じ生存期間を持つので、同じ変数に入れて管理することができる。

一方、push_backのループではnodeは排他参照の形で持っている。したがって上の図で実際にノードが有効な期間を図示すると以下のようになる。

f:id:qnighy:20170505222402p:plain

各ノードが有効な期間がない、ということはないので、これらの生存期間は真にネストしているとみなすしかない。当然、同じ変数に入れて管理することはできない。

ネストの深さ

さらに、このネストの深さを考えると、これはリストの長さに応じて非有界に増加しうることがわかる。

ところが、Rustでは単一の関数呼び出しの中だけでは生存期間のネストを非有界に増やすことはできない。生存期間をレキシカルに管理するためのリージョンは有限個しかなく、単一の関数呼び出しの中では各リージョンのインスタンスは同時には1個ずつしか存在しえないからである。

したがってpush_backはループをもつ単一の関数では書けないだろう、ということになる。

push_backを書くには

unsafeを使うか、以下のように末尾再帰で書けばよい。

impl<T> List<T> {
    fn push_back(&mut self, value: T) {
        fn findlast<T>(node: &mut Option<Box<Node<T>>>)
                -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut b) = *node {
                findlast(&mut b.next)
            } else {
                node
            }
        }
        let node = findlast(&mut self.root);
        *node = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
}

最適化をかけて試してみたところ、どうやら末尾呼び出し最適化は行われる場合があるようなので、unsafeをつけるほどでもないときはこのように末尾再帰でよいかもしれない。

まとめ

再帰的なデータ構造に対する処理で、根から葉へとノードを辿るような処理を考える。辿ったノードを &mut で持つときは、この処理をループで書けない場合がある。この場合でも末尾再帰を使えば書くことができるし、条件によっては末尾呼び出し最適化も行われる。