例外安全性

プログラム内では巻き戻しを注意深く使用するべきですが、パニックし得るコードがたくさんあります。もし None をアンラップしたり、境界外のインデックスを指定したり、 0 で除算したりしたら、プログラムはパニックするでしょう。デバッグビルドでは、全ての算術演算は、オーバーフロー時にパニックします。非常に注意深く、そしてどのコードを実行するかを厳しくコントロールしない限り、ほとんどすべてのコードが巻き戻しをする可能性があり、これに対して準備をする必要があります。

巻き戻しに対して準備が出来ていることは、もっと広いプログラミングの世界において、しばしば例外安全と呼ばれています。 Rust では、プログラムが関わる可能性のある、 2 つの例外安全のレベルがあります。

アンセーフなコードでは、メモリ安全性を侵害しないという点において、例外安全でなければなりません。これを、最小限の例外安全と呼びます。
安全なコードでは、プログラムが正しいことを行なうという点において、例外安全であると良いです。これを最大限の例外安全と呼びます。

Rust の多くの場において事実なのですが、巻き戻しとなると、アンセーフなコードは、悪い安全なコードに対処する準備をしなければなりません。一時的に健全ではない状態を生むコードは、パニックによってその状態が使用されないよう、注意深く扱わなければなりません。通常これは、このような健全でない状態が存在する間、パニックを起こさないコードのみを確実に実行させることを意味するか、あるいはパニックの際、その状態を片付けるガードを生成することを意味します。これは必ずしも、パニックが起きているときの状態が、完全に一貫した状態であるということを意味しません。安全な状態であると保証されていることだけが必要なのです。

ほとんどのアンセーフなコードは葉のようなもの (訳注: それ以上別の関数を呼ぶことがない) で、それ故に割と簡単に例外安全に出来ます。実行するコードは完全に制御されていて、そしてほとんどのコードはパニックしません。しかし、アンセーフなコードが繰り返し呼び出し側のコードを実行している間に、部分的に初期化されていない配列を扱うことはよくあります。このようなコードは注意深く扱い、例外安全を考える必要があるのです。

Vec::push_all

Vec::push_all は、特殊化なしに、スライスが確実に効率的であることを利用した、 Vec を伸ばす一時的なハックです。これは単純な実装です。

impl<T: Clone> Vec<T> {
    fn push_all(&mut self, to_push: &[T]) {
        self.reserve(to_push.len());
        unsafe {
            // 今さっき reserve をしたので、オーバーフローするはずがありません
            self.set_len(self.len() + to_push.len());

            for (i, x) in to_push.iter().enumerate() {
                self.ptr().offset(i as isize).write(x.clone());
            }
        }
    }
}

絶対にキャパシティがあると分かっている Vec の capacity と len の余分なチェックを回避するため、 push を使用していません。論理は完全に正しいです。但し、このコードに微妙な問題が含まれていることを除く。すなわち、このコードは例外安全ではないのです! set_len と offset と write は全部問題ありません。 clone は、我々が見落としていたパニックの起爆装置です。

Clone は全く制御不能で、全く自由にパニックしてしまいます。もしパニックしてしまえば、この関数は、 Vec の長さが大きすぎる値に設定されたまま、早期に終了してしまいます。もし Vec が読み出されたりドロップされたりすると、未初期化のメモリが読み出されてしまいます!

この場合、修正は割と簡単です。もし本当に、クローンした値がドロップされたということを保証したいのなら、全てのループのイテレーションにおいて、 len を設定することが出来ます。もし単に、未初期化のメモリが読まれないようにしたいのなら、ループの後に len を設定することが出来ます。

BinaryHeap::sift_up

ヒープにおけるアップヒープは Vec を伸ばすことよりちょっと複雑です。擬似コードはこんな感じです。

bubble_up(heap, index):
    while index != 0 && heap[index] < heap[parent(index)]:
        heap.swap(index, parent(index))
        index = parent(index)

このコードを Rust に直訳するのは全く問題ありません。ですが、嫌になるようなパフォーマンスです。すなわち、 self の要素が無駄に交換され続けます。それならむしろ、以下のコードの方が良いでしょう。

bubble_up(heap, index):
    let elem = heap[index]
    while index != 0 && elem < heap[parent(index)]:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

このコードでは確実に、それぞれの要素ができるだけ少ない回数でコピーされます (実は一般的に、要素を 2 回コピーすることが必要なのです) 。しかし、これによって、いくつか例外安全性の問題が露見しました! 毎回、ある値に対する 2 つのコピーが存在します。もしこの関数内でパニックしたら、何かが 2 回ドロップされてしまいます。残念ながら、このコードに関しても、完全にコントロールすることは出来ません。比較がユーザ定義されているのです!

Vec とは違い、これを直すのは簡単ではありません。一つの選択肢として、ユーザ定義のコードとアンセーフなコードを、 2 つの段階に分割することです。

bubble_up(heap, index):
    let end_index = index;
    while end_index != 0 && heap[end_index] < heap[parent(end_index)]:
        end_index = parent(end_index)

    let elem = heap[index]
    while index != end_index:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

もしユーザ定義のコードでトラブっても、もう問題ありません。なぜなら、ヒープの状態にはまだ触れていないからです。ヒープを実際に弄るとき、信用しているデータや関数のみを扱っています。ですからもうパニックの心配はありません。

多分、この設計を嬉しく思わないでしょう。明らかに騙している! そして複雑なヒープのトラバーサルを 2 回 行わなければならない! 分かった、我慢しよう。信用していないコードやアンセーフなコードを本気で混ぜてみよう。

もし Rust に Java のような try と finally があったら、コードはこんな感じだったでしょう。

bubble_up(heap, index):
    let elem = heap[index]
    try:
        while index != 0 && element < heap[parent(index)]:
            heap[index] = heap[parent(index)]
            index = parent(index)
    finally:
        heap[index] = elem

基本的な考えは単純です。すなわち、もし比較においてパニックしたのなら、単に要素を論理的に未初期化のインデックスの位置に保存し、脱出します。このヒープを観察する誰もが、潜在的には一貫性のないヒープを目にするでしょうが、少なくともこのコードは二重ドロップを起こしません! もしアルゴリズムが通常通り終了すれば、この操作はコードがどのように終了するかに関わらず、結果を正確に一致させるために実行されます。

悲しいことに、 Rust にはそのような構造が存在しません。ですので、自分たちで退避させなければならないようです! これを行なうには、 "finally" の論理を構成するため、デストラクタと共にアルゴリズムの状態を、別の構造体に保存します。パニックしようがしまいが、デストラクタは実行され、状態を綺麗にします。

struct Hole<'a, T: 'a> {
    data: &'a mut [T],
    /// `elt` は new で生成されたときからドロップまで、常に Some です
    elt: Option<T>,
    pos: usize,
}

impl<'a, T> Hole<'a, T> {
    fn new(data: &'a mut [T], pos: usize) -> Self {
        unsafe {
            let elt = ptr::read(&data[pos]);
            Hole {
                data: data,
                elt: Some(elt),
                pos: pos,
            }
        }
    }

    fn pos(&self) -> usize { self.pos }

    fn removed(&self) -> &T { self.elt.as_ref().unwrap() }

    unsafe fn get(&self, index: usize) -> &T { &self.data[index] }

    unsafe fn move_to(&mut self, index: usize) {
        let index_ptr: *const _ = &self.data[index];
        let hole_ptr = &mut self.data[self.pos];
        ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
        self.pos = index;
    }
}

impl<'a, T> Drop for Hole<'a, T> {
    fn drop(&mut self) {
        // 穴を再び埋めます
        unsafe {
            let pos = self.pos;
            ptr::write(&mut self.data[pos], self.elt.take().unwrap());
        }
    }
}

impl<T: Ord> BinaryHeap<T> {
    fn sift_up(&mut self, pos: usize) {
        unsafe {
            // `pos` にある値を受け取り、穴を作ります。
            let mut hole = Hole::new(&mut self.data, pos);

            while hole.pos() != 0 {
                let parent = parent(hole.pos());
                if hole.removed() <= hole.get(parent) { break }
                hole.move_to(parent);
            }
            // 状況に関わらず、穴はここで埋まります。パニックしてもしなくても!
        }
    }
}