　激ムズすぎて完成できなかった。

成果物

github

コード

#[derive(Debug,PartialEq)]
struct Node {
    item: i32,
    next: Option<Box<Node>>,
    prev: Option<Box<Node>>,
}
impl Node {
    fn new(item: i32) -> Node { Node { item: item, next: None, prev: None } }
    fn item(&self) -> i32 { self.item }
    fn next(&self) -> &Option<Box<Node>> { &self.next }
    fn prev(&self) -> &Option<Box<Node>> { &self.prev }
}

Option<Box
>
- Option
  - Option::Some(T): もし値が存在すればSome(T)に入れる
  - Option::None: もし値がなければNoneにする
- Box<Node>
  - 自己参照する型定義なので使う

　返す値が参照でなく値だと以下エラーになる。

error[E0507]: cannot move out of borrowed content
 --> src/lib.rs:9:43
  |
9 |     fn next(&self) -> Option<Box<Node>> { self.next }
  |                                           ^^^^^^^^^ cannot move out of borrowed content

　懸念。push, insertメソッドなどを実装すると&selfでなく&mut selfにする必要があるかも？

NG集

　以下のようなパターンで迷ったりエラーが出まくった。

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

　自己参照する型定義は、ポインタ型にすることでメモリサイズを算出できるようになるはず。結果、コンパイルできるようになるはず。そう思ってBox<Option<Node>>にした。でも、以下のように失敗しまくった。

#[derive(Debug,PartialEq)]
struct Node<T> {
    item: T,
    next: Box<Option<Node<T>>>,
    prev: Box<Option<Node<T>>>,
}
impl<T> Node<T> {
    fn new(item: T) -> Node<T> { Node { item: item, next: Box::new(None), prev: Box::new(None) } }
    fn next(&self) -> T { self.next.unwrap().item } // error[E0507]: cannot move out of borrowed content
    fn prev(&self) -> T { self.prev.unwrap().item }
//    fn next(&self) -> &T { &self.next.unwrap().item } // error[E0515]: cannot return reference to temporary value
//    fn prev(&self) -> &T { &self.prev.unwrap().item }
//    fn next(&'a self) -> Node<T: 'a> { &self.next.unwrap() } // error: expected one of `!`, `(`, `+`, `,`, `::`, `<`, or `>`, found `:`
//    fn prev(&'a self) -> Node<T: 'a> { &self.prev.unwrap() }
//    fn next(&self) -> &Node<T> { &self.next.unwrap() } // error[E0515]: cannot return reference to temporary value
//    fn prev(&self) -> &Node<T> { &self.prev.unwrap() }
//    fn next(&self) -> Option<Node<T>> { *self.next } // error[E0507]: cannot move out of borrowed content
//    fn prev(&self) -> Option<Node<T>> { *self.prev }
//    fn next(&self) -> Box<Option<Node<T>>> { self.next } // error[E0507]: cannot move out of borrowed content
//    fn prev(&self) -> Box<Option<Node<T>>> { self.prev }
//    fn next(&mut self) -> Box<Option<Node<T>>> { self.next } // error[E0507]: cannot move out of borrowed content
//    fn prev(&mut self) -> Box<Option<Node<T>>> { self.prev }
//    fn next(self) -> Box<Option<Node<T>>> { self.next } // error[E0382]: use of moved value: `node`
//    fn prev(self) -> Box<Option<Node<T>>> { self.prev }
//    fn next(&self) -> Box<Option<Node<T>>> { Box::new(self.next) } // error[E0308]: mismatched types
//    fn prev(&self) -> Box<Option<Node<T>>> { Box::new(self.prev) }
//    fn next(&self) -> &Box<Option<Node<T>>> { &self.next } // error[E0308]: mismatched types
//    fn prev(&self) -> &Box<Option<Node<T>>> { &self.prev }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn Node_new_char() {
        let node = Node::new('a');
        assert_eq!(node.item, 'a');
        assert_eq!(node.next, Box::new(None));
        assert_eq!(node.prev, Box::new(None));
        assert_eq!(*node.next, None);
        assert_eq!(*node.prev, None);
        assert_eq!(*node.next(), None);
        assert_eq!(*node.prev(), None);
    }
}

　実行するとエラー。「借用中のものに対して所有権をムーブできません」という意味だと思う。

error[E0507]: cannot move out of borrowed content

　このエラーに苦しめられることになる。

`push`実装

impl TwoWayList {
    // ...
    fn push(&mut self, item: i32) {
        let mut node = Node::new(item);
        if self.head == None {
            node.next = None;
            node.prev = None;
            self.head = Some(Box::new(node)); // error[E0382]: use of moved value: `node`
            self.tail = Some(Box::new(node)); // error[E0382]: use of moved value: `node`
        } else {
            node.next = None;
            node.prev = Some(Box::new(*self.tail.unwrap()));
            self.tail = Some(Box::new(node));
        }
    }
}

error[E0382]: use of moved value: `node`
  --> src/lib.rs:25:39
   |
20 |         let mut node = Node::new(item);
   |             -------- move occurs because `node` has type `Node`, which does not implement the `Copy` trait
...
24 |             self.head = Some(Box::new(node));
   |                                       ---- value moved here
25 |             self.tail = Some(Box::new(node));
   |                                       ^^^^ value used here after move

　nodeの所有権がムーブした後で再び使っているのでエラー。Copyトレイトを実装しろ的なことを書いているが、コピーはしたくない。

　ここで、スマートポインタRcを思い出す。参照カウンタ式のポインタなので複数所有できる。

`Rc<T>`

　Box<T>をRc<T>に変更する。

use std::rc::Rc;
#[derive(Debug,PartialEq)]
struct Node {
    item: i32,
    next: Option<Rc<Node>>,
    prev: Option<Rc<Node>>,
}
impl Node {
    fn new(item: i32) -> Node { Node { item: item, next: None, prev: None } }
    fn item(&self) -> i32 { self.item }
    fn next(&self) -> &Option<Rc<Node>> { &self.next }
    fn prev(&self) -> &Option<Rc<Node>> { &self.prev }
}
struct TwoWayList {
    head: Option<Rc<Node>>,
    tail: Option<Rc<Node>>,
}
impl TwoWayList {
    fn new() -> TwoWayList { TwoWayList { head: None, tail: None } }
    fn push(&mut self, item: i32) {
        let mut node = Node::new(item);
        if self.head == None {
            node.next = None;
            node.prev = None;
            self.head = Some(Rc::new(node));
            self.tail = Some(Rc::clone(&self.head.unwrap())); // error[E0507]: cannot move out of borrowed content
//            self.tail = Some(Rc::clone(self.head.unwrap())); // error[E0308]: mismatched types
//            self.tail = Some(Rc::clone(&self.head.unwrap())); // error[E0507]: cannot move out of borrowed content
        } else {
            node.next = None;
            node.prev = Some(Rc::new(*self.tail.unwrap()));
            self.tail = Some(Rc::new(node));
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn Node_new_char() {
        let node = Node::new(0);
        assert_eq!(node.item, 0);
        assert_eq!(node.next, None);
        assert_eq!(node.prev, None);
        assert_eq!(*node.next(), None);
        assert_eq!(*node.prev(), None);
    }
    #[test]
    fn TwoWayList_new() {
        let list = TwoWayList::new();
        assert_eq!(list.head, None);
        assert_eq!(list.tail, None);
    }

}

　同じエラー。「借用されたものの所有権をムーブできない」と怒られる。

error[E0382]: borrow of moved value: `rc`
  --> src/lib.rs:27:40
   |
25 |             let rc = Rc::new(node);
   |                 -- move occurs because `rc` has type `std::rc::Rc<Node>`, which does not implement the `Copy` trait
26 |             self.head = Some(rc);
   |                              -- value moved here
27 |             self.tail = Some(Rc::clone(&rc)); // error[E0507]: cannot move out of borrowed content
   |                                        ^^^ value borrowed here after move

　Rc変数の所有権をムーブせずにcloneして参照カウンタを加算させてしまえばいい。以下のように修正する。

impl TwoWayList {
    fn push(&mut self, item: i32) {
            // ...
            let rc = Rc::new(node);
            self.head = Some(Rc::clone(&rc));
            self.tail = Some(Rc::clone(&rc)); // error[E0507]: cannot move out of borrowed content
            // ...

　以下、Rcからムーブできないエラー。

error[E0507]: cannot move out of an `Rc`
  --> src/lib.rs:35:38
   |
35 |             node.prev = Some(Rc::new(*self.tail.unwrap()));
   |                                      ^^^^^^^^^^^^^^^^^^^ cannot move out of an `Rc`

　以下のように変更してみたが同じエラー。

//            node.prev = self.tail; // error[E0507]: cannot move out of borrowed content
//            node.prev = Some(Rc::clone(&self.tail.unwrap())); // error[E0507]: cannot move out of borrowed content

            let rc = self.tail.unwrap(); // error[E0507]: cannot move out of borrowed content
//            let rc = &self.tail.unwrap(); // error[E0507]: cannot move out of borrowed content
//            let rc = *self.tail.unwrap(); // error[E0308]: mismatched types
            node.prev = Some(Rc::clone(&rc)); // error[E0507]: cannot move out of borrowed content
            self.tail = Some(Rc::new(node));

error[E0507]: cannot move out of borrowed content
  --> src/lib.rs:44:22
   |
44 |             let rc = self.tail.unwrap();
   |                      ^^^^^^^^^ cannot move out of borrowed content

　正解は以下だった。Optionのas_ref関数にて参照を得れば所有権のムーブが起きない。

            let rc = self.tail.as_ref().unwrap();
            node.prev = Some(Rc::clone(&rc));
            self.tail = Some(Rc::new(node));

　だが、2個目以降のセットアップがうまくいかない。

    fn push(&mut self, item: i32) {
        let mut node = Node::new(item);
        if self.head == None {
            node.next = None;
            node.prev = None;
            let rc = Rc::new(node);
            self.head = Some(Rc::clone(&rc));
            self.tail = Some(Rc::clone(&rc));
        } else {
            /*
            node.next = None;
            let rc = self.tail.as_ref().unwrap();
            node.prev = Some(Rc::clone(&rc));
            self.tail = Some(Rc::new(node));
            */
            /*
            node.next = None;
            let tail = self.tail.as_ref().unwrap();
//            let tail = self.tail.unwrap();
//            node.prev = Some(Rc::clone(&tail));
            node.prev = Some(Rc::clone(&tail));
            let new = Rc::new(node);
            self.tail = Some(new);
            tail.next = Some(Rc::clone(&new))
            */
            /*
            node.next = None;
            let mut old_tail;
//            self.tail = ::std::mem::replace(&mut old_tail, node); // self.tailにnodeが入る。self.tailの代入前の値はold_tailに入る
            let new = Rc::new(node);
            self.tail = ::std::mem::replace(&mut old_tail, Some(new)); // self.tailにnodeが入る。self.tailの代入前の値はold_tailに入る
//            node.prev = Some(Rc::clone(&old_tail)); // error[E0308]: mismatched types
            node.prev = Some(Rc::clone(&old_tail.unwrap())); // error[E0381]: borrow of possibly uninitialized variable: `old_tail`
//            node.prev = Some(Rc::clone(&old_tail.as_ref().unwrap()));
//            self.tail = Some(Rc::new(node));
//            self.tail = Some(Rc::clone(&new));
            */
            /*
//            let mut new: Option<Rc<Node>>;
            let old_tail = ::std::mem::replace(&mut self.tail, Some(Rc::new(node)));;
//            self.tail.prev = old_tail; // error[E0609]: no field `prev` on type `std::option::Option<std::rc::Rc<Node>>`
            self.tail.unwrap().prev = Rc::clone(&old_tail); // error[E0308]: mismatched types
//            old_tail.next = self.tail;
            old_tail.unwrap().next = self.tail; // error[E0594]: cannot assign to data in a `&` reference
            let new = Rc::new(node);
            */
            node.next = None;
            node.prev = Some(Rc::clone(&self.tail.unwrap()));
            let mut old_tail = self.tail.unwrap();
            Rc::get_mut(&mut old_tail).unwrap().prev = Some(Rc::new(node));
//            self.tail.unwrap().get_mut().next = Some(Rc::new(node)); // error[E0599]: no method named `get_mut` found for type `std::rc::Rc<Node>` in the current scope
//            self.tail = Some(Rc::clone(&node)); // error[E0308]: mismatched types
            self.tail = Some(Rc::clone(&node)); // error[E0308]: mismatched types
            /*
            node.next = None;
            node.prev = Some(Rc::clone(&self.tail.unwrap()));
            let rc_new = Rc::new(node);
            let mut old_tail = self.tail.unwrap();
            Rc::get_mut(&mut old_tail).unwrap().prev = Some(rc_new);
//            self.tail.unwrap().get_mut().next = Some(Rc::new(node)); // error[E0599]: no method named `get_mut` found for type `std::rc::Rc<Node>` in the current scope
//            self.tail = Some(Rc::clone(&node)); // error[E0308]: mismatched types
            self.tail = Some(Rc::clone(&rc_new)); // error[E0308]: mismatched types
            */
        }

　どうすればいいの？　借用規則に阻まれまくって全然書けないんですけど！

所感

ドキュメント必須

　難しい。以下の資料などを読まねば絶対に書けない。

借用規則エラー地獄

　C言語を勉強したとき、双方向リストが自分で実装できるようになったら少しは自信を持てるようになった。ヒープ、ポインタ、構造体、関数を思い通りに操作できるかが試される。ので、Rustでもやってみたのだが。

　Rustは借用規則のせいで難解。もうunsafe Rustで書いたほうが早いのでは？　いや、それならRustでやる意味ない。C言語で書いたほうが早い。……あれ、Rustってクソ？　いやたぶん私が未熟なだけだろう。たぶん。

対象環境

2019-07-11
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）

成果物

コード

NG集

`push`実装

`Rc<T>`

所感

ドキュメント必須

借用規則エラー地獄

対象環境

前回まで

成果物

コード

NG集

push実装

Rc<T>

所感

ドキュメント必須

借用規則エラー地獄

対象環境

前回まで

`push`実装

`Rc<T>`