Drop とパニック安全性

さて、このコメントに気づきましたか。

#![allow(unused)]
fn main() {
// もう `take` をあれこれ扱う必要はないことに注意
// すべてが Copy で、失敗しても実行される dtor は
// 存在しないから……ですよね？ :) ですよねぇ？ :)))
}

これは正しいでしょうか？

すみません、あなたはいま読んでいる本を忘れたんですか？もちろん間違っています！（ある意味では。）

pop_front の内部本体をもう一度見てみましょう。

// Box を復活させて、その値を move し、
// Drop できるようにする（Box はこのことを引き続き魔法のように理解してくれる）。
let boxed_node = Box::from_raw(node.as_ptr());
let result = boxed_node.elem;

// 次のノードを新しい front にする。
self.front = boxed_node.back;
if let Some(new) = self.front {
    // 削除されたノードへの参照をクリーンアップする
    (*new.as_ptr()).front = None;
} else {
    // front が null になったなら、このリストは空になった！
    debug_assert!(self.len == 1);
    self.back = None;
}

self.len -= 1;
result
// Box はここで暗黙的に解放され、T がないことを認識している。

バグが見えますか？恐ろしいことに、実はこの行です。

debug_assert!(self.len == 1);

本当に？テストのためのこの忌々しい整合性チェックがバグなんですか？？そうです！！！まあ、コレクションを正しく実装していれば、これはバグであるべきではありませんが、「ああ、len を最新に保つのが下手だね」くらいの無害なものを、悪用可能なメモリ安全性バグに変えてしまう可能性があります！なぜでしょう？パニックする可能性があるからです！たいていの場合、パニックについて考えたり心配したりする必要はありませんが、本当に unsafe なコードを書き始め、「不変条件」を軽々しく扱い始めたら、パニックに対して極度に警戒する必要があります！

例外安全性（別名パニック安全性、別名アンワインド安全性、……）について話さなければなりません。

要するに、デフォルトでは、パニックはアンワインドします。アンワインドとは、「すべての関数を即座に return させる」ことを気取って言っただけのものです。「まあ、全員が return するならプログラムは死ぬ寸前なんだから、なぜ気にする必要があるの？」と思うかもしれませんが、それは間違いです！

気にしなければならない理由は 2 つあります。関数が return するとデストラクタが実行されること、そしてアンワインドは捕捉できることです。どちらの場合も、パニック後にコードが実行され続ける可能性があるため、パニックが起こり得るあらゆる時点で、unsafe なコレクションが常に何らかの一貫した状態にあることを慎重に確認する必要があります。なぜなら、各パニックは暗黙の早期 return だからです！

その行に到達したとき、私たちのコレクションがどのような状態にあるか考えてみましょう。

スタック上には boxed_node があり、そこから要素を取り出しています。この時点で return した場合、Box は drop され、そのノードは解放されます。もうわかりましたか……？ self.back はまだその解放済みノードを指しています！コレクションの残りを実装して、self.back をいろいろな用途に使い始めると、これは use-after-free につながる可能性があります！うわっ！

興味深いことに、この行にも似た問題がありますが、ずっと安全です。

self.len -= 1;

デフォルトでは、Rust はデバッグビルドでアンダーフローとオーバーフローをチェックし、それらが発生するとパニックします。そうです、すべての算術演算はパニック安全性上の危険なのです！こちらのほうがましなのは、すべての不変条件を修復した後で発生するため、メモリ安全性の問題を引き起こさないからです……ただし、len が正しいと信じない限りは、ですが。とはいえ、アンダーフローするならそれは間違いなく誤っているので、どのみち詰んでいました！ debug assert は、ある意味ではより悪いです。些細な問題を致命的な問題へと悪化させ得るからです！

「不変条件」という用語を何度か持ち出してきましたが、それはパニック安全性にとって非常に有用な概念だからです！基本的には、コレクションの外部の観察者に対して、私たちが常に保っている特定の性質があります。LinkedList であれば、そのひとつは、リスト内で到達可能なノードはすべて、まだ割り当てられて初期化されている、というものです。

実装の内部では、誰かに気づかれる前に必ず修復する限り、不変条件を一時的に破る柔軟性が少しあります。これは実際、Rust の所有権と借用システムがコレクションにもたらす「キラーアプリ」のひとつです。操作が &mut Self を必要とするなら、私たちはそのコレクションへの排他的アクセスを持っていることが保証され、誰もこっそり干渉できないとわかっているので、一時的に不変条件を破っても構わないのです。

おそらくこれを最もよく表しているのが Vec::drain です。これは実際に、Vec の中核的な不変条件を完全にぶち壊し、Vec の先頭、あるいは中央から値を move し始めることさえ許します。これが健全である理由は、返す Drain イテレータが Vec への &mut を保持しているため、すべてのアクセスがそれを通して制御されるからです！ Drain イテレータがなくなるまで誰も Vec を観察できず、その後、そのデストラクタが誰かに気づかれる前に Vec を「修復」できるので、完璧で――

完璧ではありません。残念ながら、自分が制御していないコード内のデストラクタが実行されることには依存できません。そのため、Drain であっても、型の不変条件が常に保たれるように少し追加の作業が必要です。ただし、ちょっと間の抜けたやり方です。最初に Vec の len を 0 に設定するだけです。そうすれば、誰かが Drain をリークしても、安全な Vec は残ります……ただし、大量のデータも失うことになります。お前が俺をリークするなら、俺もお前をリークする！目には目を！真の正義です！

パニック安全性のために実際にデストラクタを使える状況については、BinaryHeap::sift_up のケーススタディを見てください。

ともあれ、私たちの LinkedList ではこうした凝った仕組みはすべて必要ありません。不変条件をどこで破るのか、何が正しいと信頼・要求するのかにもう少し注意し、厄介な作業の最中に不要なアンワインドを導入しないようにすればよいだけです。

この場合、コードをもう少し堅牢にする選択肢は 2 つあります。

Option::take のような操作をもっと積極的に使う。なぜなら、これらはより「トランザクショナル」で、不変条件を保つ傾向があるからです。
debug_assert を削除し、ユーザーコードでは決して実行されない専用の「整合性チェック」関数で、よりよいテストを書ける自分たちを信じる。

原則としては最初の選択肢が好きですが、二重リンクリストでは実際にはあまりうまく機能しません。なぜなら、すべてが二重に冗長にエンコードされているからです。ここでは Option::take は問題を解決しませんが、debug_assert を 1 行下に移動すれば解決します。とはいえ本当に、なぜ自分たちで難しくするのでしょう？その debug_assert は削除し、パニックし得るものはすべてメソッドの先頭か末尾に置くようにしましょう。そこでは不変条件が成り立っていることがわかっているはずです。

（このように考えると、それらを事前条件と事後条件と捉えるほうがより正確かもしれませんが、本当はできる限りそれらを不変条件として扱うよう努めるべきです！）

これが現在の完全な実装です。

#![allow(unused)]
fn main() {
use std::ptr::NonNull;
use std::marker::PhantomData;

pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
    _boo: PhantomData<T>,
}

type Link<T> = Option<NonNull<Node<T>>>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            front: None,
            back: None,
            len: 0,
            _boo: PhantomData,
        }
    }

    pub fn push_front(&mut self, elem: T) {
        // SAFETY: これは連結リストです。他に何を求めているんですか？
        unsafe {
            let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node {
                front: None,
                back: None,
                elem,
            })));
            if let Some(old) = self.front {
                // 新しい front を古いものの前に置く
                (*old.as_ptr()).front = Some(new);
                (*new.as_ptr()).back = Some(old);
            } else {
                // front がなければ、これは空のリストなので 
                // back も設定する必要がある。
                self.back = Some(new);
            }
            // これらは常に行われる！
            self.front = Some(new);
            self.len += 1;
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        unsafe {
            // pop する front ノードがある場合だけ処理を行う必要がある。
            self.front.map(|node| {
                // Box を蘇らせて、その値を move out し、
                // Drop できるようにする（Box は引き続きこれを魔法のように理解してくれる）。
                let boxed_node = Box::from_raw(node.as_ptr());
                let result = boxed_node.elem;

                // 次のノードを新しい front にする。
                self.front = boxed_node.back;
                if let Some(new) = self.front {
                    // 削除されたノードへの参照をクリーンアップする
                    (*new.as_ptr()).front = None;
                } else {
                    // front が null になったなら、このリストは空になった！
                    self.back = None;
                }

                self.len -= 1;
                result
                // Box はここで暗黙的に解放され、T がないことを知っている。
            })
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }
}
}

ここでは何が panic し得るのでしょうか？正直なところ、それを知るには Rust のかなりの専門家である必要がありますが、ありがたいことに、私はそうです！

このコードで 可能性として panic し得る箇所として私に見えるのは（誰かが debug_asserts を有効にして標準ライブラリを再コンパイルするような、とんでもない悪ふざけは除きますが、これは絶対にやるべきことではありません）、Box::new（メモリ不足条件の場合）と len の算術演算だけです。それらはすべて、メソッドの本当に末尾か本当に先頭にあるので、ええ、私たちはちゃんと安全にやれています！

……Box::new が panic し得ることに驚きましたか？ panic とはそういうものです！心配しなくて済むように、それらの不変条件を保つようにしましょう！

Keyboard shortcuts

Learning Rust With Entirely Too Many Linked Lists 日本語版

Drop とパニック安全性