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を使うことができる。