レイアウトと基本 2: 生でいこう
前の3つのセクションの要約:
&、&mut、Boxのような安全なポインターと、*mutや*constのような unsafe なポインターをでたらめに混ぜるのは未定義動作のもとです。なぜなら、安全なポインターは追加の制約を導入し、それを生ポインターで守れていないからです。
ああ神よ、また連結リストを書かなきゃいけないのか。わかった。わかったよ。大丈夫。僕らは大丈夫。
このセクションの大部分はかなり手早く片付けます。設計については最初の試みのあたりですでに議論しましたし、やったことは、安全なポインターと unsafe なポインターを混ぜ合わせた方法を除けば、基本的に正しかったからです。
レイアウト
なので新しいレイアウトでは生ポインターだけを使うことにします。そうすればすべてが完璧になり、二度と間違いを犯すことはありません。
これが古い壊れたレイアウトです。
#![allow(unused)]
fn main() {
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // 無実で親切
}
type Link<T> = Option<Box<Node<T>>>; // 本当の悪
struct Node<T> {
elem: T,
next: Link<T>,
}
}そしてこれが新しいレイアウトです。
#![allow(unused)]
fn main() {
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>,
}
type Link<T> = *mut Node<T>; // ずっと良い
struct Node<T> {
elem: T,
next: Link<T>,
}
}思い出してください。生ポインターを使っているとき、Option はそれほど素敵でも便利でもありません。なので、もう使いません。後のセクションでは NonNull 型を見ていきますが、今は気にしなくて大丈夫です。
基本
List::new は基本的に同じです。
use ptr;
impl<T> List<T> {
pub fn new() -> Self {
List { head: ptr::null_mut(), tail: ptr::null_mut() }
}
}Push も基本的におな-
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(待って、もう Box は使っていないんでした。Box なしでどうやってメモリを確保するのでしょうか？
まあ、std::alloc::alloc を使えば できる でしょうが、それは台所に刀を持ち込むようなものです。仕事はしてくれますが、ちょっと過剰で扱いづらいです。
Box を 持ちたい、でも、持ちたくない。完全にぶっ飛んでいるけど もしかすると 実行可能な選択肢の1つは、こんなことをすることでしょう。
struct Node<T> {
elem: T,
real_next: Option<Box<Node<T>>>,
next: *mut Node<T>,
}
考え方としては、Box を作ってそれをノードに格納しますが、その中への生ポインターを取り、Node を使い終えて破棄したくなるまでその生ポインターだけを使う、というものです。その後 real_next から Box を take して drop できます。これは、僕らのかなり単純化した stacked borrows モデルに適合するんじゃないかと 思います。
もしこれを作ってみたいなら、「楽しんで」ください。でも、ひどく見えますよね？ これは Rc と RefCell の章ではありません。僕らはもうこの ゲーム をするつもりはありません。単純できれいなものを作るだけです。
なので代わりに、とても素敵な Box::into_raw 関数を使います。
pub fn into_raw(b: Box<T>) -> *mut TBox を消費し、ラップされた生ポインターを返します。
ポインターは適切にアラインされ、null ではありません。
この関数を呼び出した後、Box が以前管理していたメモリについては呼び出し元が責任を負います。特に、呼び出し元は Box が使用するメモリレイアウトを考慮して、T を適切に破棄し、メモリを解放する必要があります。これを行う最も簡単な方法は、
Box::from_raw関数で生ポインターを Box に戻し、Box のデストラクターにクリーンアップを実行させることです。注: これは関連関数です。つまり、
b.into_raw()ではなくBox::into_raw(b)として呼び出す必要があります。これは、内部の型のメソッドと競合しないようにするためです。例
自動的なクリーンアップのために、Box::from_raw で生ポインターを Box に戻す:
let x = Box::new(String::from("Hello")); let ptr = Box::into_raw(x); let x = unsafe { Box::from_raw(ptr) };
いいですね。これは僕らのユースケース向けに 文字どおり 設計されたものに見えます。僕らが従おうとしているルールにも合っています。安全なものから始め、生ポインターに変換し、最後にだけ（Drop したいときに）安全なものへ戻す、というルールです。
これは基本的に、奇妙な real_next を使う方法とまったく同じですが、Box が結局は生ポインターとまったく同じポインターであるにもかかわらず、それを格納してあれこれ面倒を見る必要がありません。
また、今ではあらゆる場所で生ポインターを使っているので、unsafe ブロックを狭く保つことを気にするのはやめましょう。今やすべてが unsafe です。（ずっとそうだったのですが、ときには自分に嘘をつくのもいいものです。）
pub fn push(&mut self, elem: T) {
unsafe {
// Boxをただちに生ポインターに変換する
let new_tail = Box::into_raw(Box::new(Node {
elem: elem,
next: ptr::null_mut(),
}));
if !self.tail.is_null() {
(*self.tail).next = new_tail;
} else {
self.head = new_tail;
}
self.tail = new_tail;
}
}生ポインターに徹するようになったら、そのコードは実際かなりきれいに見えるようになりましたね！
次は pop です。これも前回残したものとかなり似ていますが、割り当てをクリーンアップするために Box::from_raw を使うことを忘れないようにしなければなりません。
pub fn pop(&mut self) -> Option<T> {
unsafe {
if self.head.is_null() {
None
} else {
// 墓場から蘇れ
let head = Box::from_raw(self.head);
self.head = head.next;
if self.head.is_null() {
self.tail = ptr::null_mut();
}
Some(head.elem)
}
}
}僕らのかわいい take や map は死にました。これからは手動で null をチェックして設定する必要があります。
ついでに、デストラクターも入れておきましょう。今回は、かわいくて単純なので、ただ繰り返し pop する形で実装します。
impl<T> Drop for List<T> {
fn drop(&mut self) {
while let Some(_) = self.pop() { }
}
}さて、いよいよ正念場です。
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// 空のリストが正しく振る舞うことを確認
assert_eq!(list.pop(), None);
// リストに要素を追加
list.push(1);
list.push(2);
list.push(3);
// 通常の削除を確認
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// 何も壊れていないことを確認するため、さらにいくつか追加
list.push(4);
list.push(5);
// 通常の削除を確認
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// 使い切りを確認
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
// 使い切った場合にポインターが正しく修正されたことを確認
list.push(6);
list.push(7);
// 通常の削除を確認
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}cargo test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
よし、でも miri は同意してくれるかな？
MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
イエーーーイ！！！！！
マジで動いた！
たぶん！
未定義動作を見つけられなかったからといって、それが問題を引き起こそうと待ち構えていないことの証明にはならないが、連結リストについてのジョーク本のために俺が進んで払う厳密さには限度があるので、これは 100% 機械検証済みの証明と呼ぶことにするし、そうじゃないと言う奴は俺の COQ でもしゃぶってろ！
∴ QED □