　できた！

成果物

github

準備

クレート作成

cargo new one_way_list --lib

単方向リスト

　ある型の要素が一列に連なるリスト構造を作りたい。

Node

　単方向リストはNodeの連なりである。Nodeには要素と次のNodeへのポインタ

Node
+----+----+
|item|next|
+----+----+

item: ある型の要素
next: 次の要素へのポインタ

　nextフィールドの参照にて次の要素へアクセスできる。末尾ならはNone。たとえば以下。

Node0       Node1       Node2
+-+------+  +-+------+  +-+----+
|0|&Node1|->|1|&Node2|->|2|None|
+-+------+  +-+------+  +-+----+

`Node`構造体

再帰型（自己参照型）
ジェネリック

再帰型（自己参照型）

　これを構造体で表現してみる。

src/lib.rs

struct Node {
    item: i32,
    next: Node,
}

　だが、これはコンパイルエラーになる。再帰型（自己参照な型定義）となっているため。メモリサイズが無限大になってしまう。

error[E0072]: recursive type `Node` has infinite size
 --> src/lib.rs:1:1
  |
1 | struct Node {
  | ^^^^^^^^^^^ recursive type has infinite size
2 |     item: i32,
3 |     next: Node,
  |     ---------- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Node` representable

　Node型の定義が完了する前にNode型フィールドnextを宣言してしまっている。Nodeに必要なメモリサイズが算出できない（無限大）。

メモリ安全に実装できない？

　どうやら現状のRustでは自己参照型の解決をメモリ安全に行う方法はないようだ。

　unsafe Rustにて生ポインタ操作が必要らしい。

　だが、それではRustでやる価値がない。本当にできないかどうか試してみる。

スマートポインタ

　自己参照型の定義にはスマートポインタを使う。ポインタはメモリのアドレスを指し示すもの。メモリアドレスを格納できるサイズは事前に判明している。32bitマシンなら32bit(4Byte)など。これでサイズ無限大エラーを回避できる。

　C言語なら生ポインタを扱うが、Rustはメモリ安全な仕組みがある。このため、スマートポインタなど標準モジュールを駆使してメモリ安全に実装したい。ただし、もしできなければunsafe Rustで生ポインタを扱うことになる。

Rust: メモリ安全。スマートポインタなど標準モジュールを使う
unsafe Rust: メモリ非安全。生ポインタを使う

`Box`

src/lib.rs

struct Node {
    item: i32,
    next: Box<Node>,
}

　スマートポインタBoxを使って型定義した。コンパイルエラーは解決する。

`None`

src/lib.rs

struct Node {
    item: i32,
    next: Option<Box<Node>>,
}

　最後の要素ならnextはNULLである。次の要素がないならポインタはどこも指し示すべきではないから。

　だが、RustにはNULLがない。代わりにOptionのNoneを使う。Optionの定義は以下。

pub enum Option<T> {
    None,
    Some(T),
}

　要素を生成するコード例は以下。

let first = Node { item: 0, next: None };
let second = Node { item: 0, next: Some(Box::new(first)) };

　まだfirstとsecondのnextは正しい値ではない。だが、型の生成まではできた。

`impl`

　Nodeのメソッドを実装する。

`new`

　まずはコンストラクタであるnewを実装する。

src/lib.rs

impl Node {
    fn new(item: i32) -> Self { Self { item: item, next: None } }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn Node_new() {
        let first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let second = Node::new(1);
        assert_eq!(first.item, 1);
        assert_eq!(first.next, None);
    }
}

　すると以下のようなエラーが出る。

$ cargo test
...
error[E0369]: binary operation `==` cannot be applied to type `std::option::Option<std::boxed::Box<Node>>`
  --> src/lib.rs:23:9
   |
23 |         assert_eq!(first.next, None);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: an implementation of `std::cmp::PartialEq` might be missing for `std::option::Option<std::boxed::Box<Node>>`
   = note: this error originates in a macro outside of the current crate (in Nightly builds, run with -Z external-macro-backtrace for more info)

　ノートをみると「std::cmp::PartialEqがない」と言っている。以下のように#[derive(PartialEq)]を追記する。

#[derive(PartialEq)]
struct Node {
    item: i32,
    next: Option<Box<Node>>,
}

　コンパイルすると以下エラー。

error[E0277]: `Node` doesn't implement `std::fmt::Debug`
  --> src/lib.rs:24:9
   |
24 |         assert_eq!(first.next, None);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `Node` cannot be formatted using `{:?}`
   |
   = help: the trait `std::fmt::Debug` is not implemented for `Node`
   = note: add `#[derive(Debug)]` or manually implement `std::fmt::Debug`
   = note: required because of the requirements on the impl of `std::fmt::Debug` for `std::boxed::Box<Node>`
   = note: required because of the requirements on the impl of `std::fmt::Debug` for `std::option::Option<std::boxed::Box<Node>>`
   = note: required because of the requirements on the impl of `std::fmt::Debug` for `&std::option::Option<std::boxed::Box<Node>>`
   = note: required by `std::fmt::Debug::fmt`
   = note: this error originates in a macro outside of the current crate (in Nightly builds, run with -Z external-macro-backtrace for more info)

　#[derive(Debug, PartialEq)]を追記する。単体テストをするなら必須。構造体を作ったら自動的にこれを追記するくらいの感覚でOK。

#[derive(Debug, PartialEq)]
struct Node {
    item: i32,
    next: Option<Box<Node>>,
}

　以下コードでコンパイル成功する。

#[derive(Debug, PartialEq)]
struct Node {
    item: i32,
    next: Option<Box<Node>>,
}
impl Node {
    fn new(item: i32) -> Self { Self { item: item, next: None } }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn Node_new() {
        let first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
    }
}

　ついでに、要素を追加したときnextを変更させてみたときのテストは以下。

    #[test]
    fn Node_new_2() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let mut second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
        first.next = Some(Box::new(first));
    }
    #[test]
    fn Node_new_3() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let mut second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
        first.next = Some(Box::new(first));
        let mut third = Node::new(2);
        assert_eq!(third.item, 2);
        assert_eq!(third.next, None);
        second.next = Some(Box::new(third));
    }

　これをpushメソッドとして実装してみる。

`push`

impl Node {
    // ...
    fn push(&mut self, item: i32) {
        let new_node = Node::new(item);
        self.next = Some(Box::new(new_node));
    }
}

　テストコードは以下。

    #[test]
    fn Node_push() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);

        first.push(1);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 1, next: None })));
        let mut second = first.next.unwrap();
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);

        second.push(2);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, Some(Box::new(Node { item: 2, next: None })));
        let mut third = second.next.unwrap();
        assert_eq!(third.item, 2);
        assert_eq!(third.next, None);
    }

　じつはバグがある。後述する。

ジェネリック

　Node.itemをi32型でなく、あらゆる型に対応させたい。そこでジェネリックを使う。

`Node`構造体

　<T>でジェネリック型にする。

#[derive(Debug, PartialEq)]
struct Node<T> {
    item: T,
    next: Option<Box<Node<T>>>,
}

　コンパイルすると以下エラー。

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/lib.rs:12:6
   |
12 | impl Node {
   |      ^^^^ expected 1 type argument

`impl`

　実装もジェネリック対応させる。

impl<T> Node<T> {
    fn new(item: T) -> Self { Self { item: item, next: None } }
    fn push(&mut self, item: T) {
        let new_node = Node::new(item);
        self.next = Some(Box::new(new_node));
    }
}

　テストケースは以下。とりあえずString型でも試してみた。

    #[test]
    fn Node_new_string() {
        let first = Node::new(String::from("AA"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, None);
        let second = Node::new(String::from("BB"));
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, None);
    }
    #[test]
    fn Node_push_string() {
        let mut first = Node::new(String::from("AA"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, None);

        first.push(String::from("BB"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, Some(Box::new(Node { item: String::from("BB"), next: None })));
        let mut second = first.next.unwrap();
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, None);

        second.push(String::from("CC"));
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, Some(Box::new(Node { item: String::from("CC"), next: None })));
        let mut third = second.next.unwrap();
        assert_eq!(third.item, String::from("CC"));
        assert_eq!(third.next, None);
    }

`push`のバグ

　問: 今までは必ず末尾の要素にpushしていた。だが、先頭や中間にある要素にpushしたらどうなるか？

　解: 新しい要素のnextがNoneになってしまい、次の要素が取得できなくなってしまう。

`push`した要素の`next`は`None`である

　実装をみてみればわかる。引数で受け取った要素を新たなNodeとして生成する。このとき、nextはNodeである。ここがポイント。もっとも、これはnewメソッドの定義どおり。

　では、pushを呼び出した要素が末尾でなければ？　新たな要素のnextはNoneになってしまう。末尾でないのに、Noneになってしまう。

impl<T> Node<T> {
    fn new(item: T) -> Self { Self { item: item, next: None } }
    fn push(&mut self, item: T) {
        let new_node = Node::new(item);
        self.next = Some(Box::new(new_node));
    }

　順に追ってみよう。Node構造体は以下のような型である。

Node
+----+----+
|item|next|
+----+----+

　ひとつ目のNodeを生成する。nextはNoneである。newメソッドの実装どおりに。

let first = Node::new(0);

first
+-+----+
|0|None|
+-+----+

　ひとつ目のNode(0,first)に1をpushする。新しい要素のnextはNoneになる。newメソッドの実装どおりに。そして、pushメソッド固有の実装によって、pushを呼び出したNodeインスタンスのnextは、新たなNodeを指す。

let first = Node::new(0);
first.push(1);
let second = first.next.unwrap();

first       second
+-+-------+  +-+----+
|0|&second|->|1|None|
+-+-------+  +-+----+

　問題は次。末尾の要素でないものにpushしたときの挙動。末尾の1(second)でなく先頭の0(first)に再びpushする。

let first = Node::new(0);
first.push(1);
let second = first.next.unwrap();
first.push(2);

first       thrid       second
+-+------+  +-+----+    +-+----+
|0|&third|->|2|None|    |1|None|
+-+------+  +-+----+    +-+----+

　お分かりだろうか。新しい要素2のnextはNoneである。newメソッドのとおりに。そして1(second)を指し示すnextはなくなってしまった……。リストから外れてしまった。

　もちろん、以下のように繋がって欲しかった。2(third)のnextで1(second)を指して欲しかった。

first       thrid        second
+-+------+  +-+-------+  +-+-----+
|0|&thrid|->|2|&second|->|1|&None|
+-+------+  +-+-------+  +-+-----+

`push`: 末尾でないときも動かしたい

　問: どうやって実装する？

　解: push呼出したNodeのnextを、新しいNodeのnextにセットすれば良い。

　C言語のように直感的に書くと以下。

struct Node<T> {
    item: T,
    next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
    fn new(item: T) -> Self { Self { item: item, next: None } }
    fn push(&mut self, item: T) {
        if self.next.is_none() {
            let new_node = Node::new(item);
            self.next = Some(Box::new(new_node));
        } else {
            let tmp_node = self.next; // error[E0507]: cannot move out of borrowed content
            let new_node = Node::new(item);
            new_node.next = tmp_node;
            self.next = Some(Box::new(new_node));
        }
    }

　ifのほうは今までどおりselfが末尾のときのコード。これは問題ない。

　elseのほうは新しく追加したコード。selfが末尾でなく先頭や途中なら、selfのnextを新たなNodeのnextにセットする。だが、コンパイルエラーになる。

error[E0507]: cannot move out of borrowed content
  --> src/lib.rs:15:28
   |
15 |             let tmp_node = self.next;
   |                            ^^^^^^^^^
   |                            |
   |                            cannot move out of borrowed content
   |                            help: consider borrowing here: `&self.next`

　selfは借用しているので所有権をムーブできない。

std::mem::replace

　そこでstd::mem::replace関数を使う。self.nextに一旦Noneを代入する。このとき、元々の値を戻り値で受け取る。tmp_nodeという名前で。そして後でこれを新しいNodeのnextにセットする。これで繋がる。

impl<T> Node<T> {
    // ...
    fn push(&mut self, item: T) {
        if self.next.is_none() {
            let new_node = Node::new(item);
            self.next = Some(Box::new(new_node));
        } else {
            let tmp_node = std::mem::replace(&mut self.next, None); // self.nextに一旦Noneを入れる
            let mut new_node = Node::new(item);
            new_node.next = tmp_node;
            self.next = Some(Box::new(new_node));
        }
    }

　はい、ここ今回一番むずかしい所。

　もっとも、やっていることは前回のコードとおなじでnextの付け替え。それを所有権エラー回避する方法にしただけ。std::mem::replaceの動作が理解できればわかるはず。ようはスワップである。それをRustではこう書く。

　std::mem::replaceの動作を確認する。URL先にもあるとおり、以下のコード例をみればわかる。

let mut v: Vec<i32> = vec![1, 2];
let old_v = mem::replace(&mut v, vec![3, 4, 5]);
assert_eq!(vec![1, 2], old_v);
assert_eq!(vec![3, 4, 5], v);

　std::mem::replace関数のそれぞれは以下のような意味。

項目	値	補足
戻り値	古い値	第一引数の変数にあった元々の値（第二引数の値を代入する前の値）
第一引数	値を入れ替えたい変数	元の値を戻り値で返し、新たに第二引数をセットする
第二引数	新しい値

なぜ一旦`None`を入れるの？

　std::mem::replaceの動作がわかったところで、話をpush関数に戻そう。

　self.nextに一旦わざと間違った値Noneを入れている。これに違和感があるかもしれない。

    fn push(&mut self, item: T) {
        // ...
        } else {
            let tmp_node = std::mem::replace(&mut self.next, None); // self.nextに一旦Noneを入れる
            let mut new_node = Node::new(item);
            new_node.next = tmp_node;
            self.next = Some(Box::new(new_node));
        }

　self.nextには最初から新しいNodeへのポインタを代入すればいいじゃないか、と思うかもしれない。だが、それはできない。なぜなら、新しいNodeのnextには、self.nextの値をセットすべきだから。それを取り出す前に代入してしまうと上書きされて消えてしまう。よって、まずはself.nextの値を取り出しておく必要があるわけだ。

　だが、先ほどのエラーのとおり、ふつうに一時変数tmp_nodeにセットしようとすると「所有権をムーブできない」と怒られてしまう。

        } else {
            let tmp_node = self.next; // error[E0507]: cannot move out of borrowed content

　そこで、std::mem::replaceを使って生ポインタによる操作を肩代わりしてもらうことで所有権や借用ルールを回避する。

テストコード

    #[test]
    fn Node_push_not_last() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);

        first.push(1);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 1, next: None })));
//        let mut second = first.next.unwrap(); // error[E0382]: use of moved value: `first.next`
        let second = first.next.as_ref().unwrap();
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);

//        second.push(2);
        first.push(2);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 1, next: None })) })));
//        let mut third = first.next.unwrap(); // error[E0382]: use of moved value: `first.next`
        let third = first.next.as_ref().unwrap();
        assert_eq!(third.item, 2);
        assert_eq!(third.next, Some(Box::new(Node { item: 1, next: None })));
    }

　これで以下のようにnextが繋がっていることを確認できた。

first       thrid        second
+-+------+  +-+-------+  +-+-----+
|0|&thrid|->|2|&second|->|1|&None|
+-+------+  +-+-------+  +-+-----+

　なお、テストで値を確認するときは所有権を奪わぬようas_ref()で参照を取得すること。

Option.as_ref()

`remove`: 要素を削除するメソッドを実装する

　追加ときたら削除がほしい。これは次回にしよう。

今回の最終コード

src/lib.rs

#[derive(Debug, PartialEq)]
struct Node<T> {
    item: T,
    next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
    fn new(item: T) -> Self { Self { item: item, next: None } }
    fn push(&mut self, item: T) {
        if self.next.is_none() {
            let new_node = Node::new(item);
            self.next = Some(Box::new(new_node));
        } else {
            let tmp_node = std::mem::replace(&mut self.next, None); // self.nextに一旦Noneを入れる
            let mut new_node = Node::new(item);
            new_node.next = tmp_node;
            self.next = Some(Box::new(new_node));
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn Node_new() {
        let first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
    }
    #[test]
    fn Node_new_2() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let mut second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
        first.next = Some(Box::new(first));
    }
    #[test]
    fn Node_new_3() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);
        let mut second = Node::new(1);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);
        first.next = Some(Box::new(first));
        let mut third = Node::new(2);
        assert_eq!(third.item, 2);
        assert_eq!(third.next, None);
        second.next = Some(Box::new(third));
    }
    #[test]
    fn Node_new_string() {
        let first = Node::new(String::from("AA"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, None);
        let second = Node::new(String::from("BB"));
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, None);
    }
    #[test]
    fn Node_push() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);

        first.push(1);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 1, next: None })));
        let mut second = first.next.unwrap();
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);

        second.push(2);
        assert_eq!(second.item, 1);
        assert_eq!(second.next, Some(Box::new(Node { item: 2, next: None })));
        let mut third = second.next.unwrap();
        assert_eq!(third.item, 2);
        assert_eq!(third.next, None);
    }
    #[test]
    fn Node_push_string() {
        let mut first = Node::new(String::from("AA"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, None);

        first.push(String::from("BB"));
        assert_eq!(first.item, String::from("AA"));
        assert_eq!(first.next, Some(Box::new(Node { item: String::from("BB"), next: None })));
        let mut second = first.next.unwrap();
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, None);

        second.push(String::from("CC"));
        assert_eq!(second.item, String::from("BB"));
        assert_eq!(second.next, Some(Box::new(Node { item: String::from("CC"), next: None })));
        let mut third = second.next.unwrap();
        assert_eq!(third.item, String::from("CC"));
        assert_eq!(third.next, None);
    }
    #[test]
    fn Node_push_not_last() {
        let mut first = Node::new(0);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, None);

        first.push(1);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 1, next: None })));
        let second = first.next.as_ref().unwrap();
        assert_eq!(second.item, 1);
        assert_eq!(second.next, None);

        first.push(2);
        assert_eq!(first.item, 0);
        assert_eq!(first.next, Some(Box::new(Node { item: 2, next: Some(Box::new(Node { item: 1, next: None })) })));
        let third = first.next.as_ref().unwrap();
        assert_eq!(third.item, 2);
        assert_eq!(third.next, Some(Box::new(Node { item: 1, next: None })));
    }
}

所感

　所有権、借用規則あたりのコンパイルエラーに阻まれまくる。これを回避するための標準モジュールがいくつか用意されているらしい。それはRustでコードを書くのに必須なレベルの要素だと思うが、ドキュメントには書かれていなかった。ググりまくって新たなメソッドなどを学習していかないと実装できなかった。

参考

リファレンス

対象環境

2019-07-12
Raspbierry pi 3 Model B+
Raspbian stretch 9.0 2018-11-13
bash 4.4.12(1)-release
rustc 1.34.2 (6c2484dc3 2019-05-13)
cargo 1.34.0 (6789d8a0a 2019-04-01)

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux

やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

Rust自習（単方向リスト1）

成果物

準備

クレート作成

単方向リスト

Node

`Node`構造体

再帰型（自己参照型）

メモリ安全に実装できない？

スマートポインタ

`Box`

`None`

`impl`

`new`

`push`

ジェネリック

`Node`構造体

`impl`

`push`のバグ

`push`した要素の`next`は`None`である

`push`: 末尾でないときも動かしたい

std::mem::replace

なぜ一旦`None`を入れるの？

テストコード

`remove`: 要素を削除するメソッドを実装する

今回の最終コード

所感

参考

リファレンス

対象環境

前回まで

成果物

準備

クレート作成

単方向リスト

Node

Node構造体

再帰型（自己参照型）

メモリ安全に実装できない？

スマートポインタ

Box

None

impl

new

push

ジェネリック

Node構造体

impl

pushのバグ

pushした要素のnextはNoneである

push: 末尾でないときも動かしたい

std::mem::replace

なぜ一旦Noneを入れるの？

テストコード

remove: 要素を削除するメソッドを実装する

今回の最終コード

所感

参考

リファレンス

対象環境

前回まで

`Node`構造体

`Box`

`None`

`impl`

`new`

`push`

`Node`構造体

`impl`

`push`のバグ

`push`した要素の`next`は`None`である

`push`: 末尾でないときも動かしたい

なぜ一旦`None`を入れるの？

`remove`: 要素を削除するメソッドを実装する