Rust
メモ

非再帰版List::push_back(&mut self, value: T)について

経緯

去年の年末くらいからぼちぼちとRustの勉強をしている。噂通り借用チェッカはややこしく、色々と調べている際に以下のような記事を見つけた。

末尾再帰をループにできないRustプログラムの例 - 簡潔なQ

内容としてはlifetimeの関係でループでは書けず、再帰で書く必要があるケースが存在するというものだが、実際に書けないのか試してみたら書けてしまったので取りあえずメモとして残しておく。

実装と考察

以下コード。rust 1.18.0 で動作を確認している。

struct List<T> {
    root: Option<Box<Node<T>>>,
}
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

impl<T> List<T> {
    fn push_back(&mut self, value: T) {
        let back = if self.root.is_none() {
            &mut self.root
        } else {
            let mut node = self.root.as_mut().unwrap();
            while !node.next.is_none() {
                let old = node;
                node = old.next.as_mut().unwrap();
            }
            &mut node.next
        };
        *back = Some(Box::new(Node {
            value: value,
            next: None,
        }));
    }
}

struct Wrap(i32);
fn main(){
    let mut list = List::<Wrap> {root: None};
    list.push_back(Wrap(5));
    list.push_back(Wrap(6));
    list.push_back(Wrap(7));
    fn f(list: &mut List<Wrap>){
        let mut nodeopt = list.root.as_mut();
        while let Some(node) = nodeopt {
            println!("{}", node.value.0);
            node.value.0 += 1;
            nodeopt = node.next.as_mut();
        }
    }
    f(&mut list);
    f(&mut list);
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

以下初心者の考察というか感想。17行目で node = old.next.as_mut().unwrap(); となっているものを単にnode = node.next.as_mut().unwrap();として、16行目をコメントアウトしてしまうと、

error[E0502]: cannot borrow `node.next` as immutable because it is also borrowed as mutable
  --> prog.rs:15:20
   |
15 |             while !node.next.is_none() {
   |                    ^^^^^^^^^ immutable borrow occurs here
16 |                 // let old = node;
17 |                 node = node.next.as_mut().unwrap();
   |                        --------- mutable borrow occurs here
...
20 |         };
   |         - mutable borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> prog.rs:17:17
   |
17 |                 node = node.next.as_mut().unwrap();
   |                 ^^^^^^^---------^^^^^^^^^^^^^^^^^^
   |                 |      |
   |                 |      borrow of `node` occurs here
   |                 assignment to borrowed `node` occurs here

error[E0499]: cannot borrow `node.next` as mutable more than once at a time
  --> prog.rs:17:24
   |
17 |                 node = node.next.as_mut().unwrap();
   |                        ^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
20 |         };
   |         - first borrow ends here

error[E0499]: cannot borrow `node.next` as mutable more than once at a time
  --> prog.rs:19:18
   |
17 |                 node = node.next.as_mut().unwrap();
   |                        --------- first mutable borrow occurs here
18 |             }
19 |             &mut node.next
   |                  ^^^^^^^^^ second mutable borrow occurs here
20 |         };
   |         - first borrow ends here

error: aborting due to 4 previous errors

というエラーが吐かれる。ここで2つめのエラーは借用されているのに代入しようとしているので、エラーが出るのは分かるし、一旦oldにムーブすることでエラーが回避できるのも分かる。しかし、それ以外のエラーがいまいちピンとこない。もっと借用チェッカについて知る必要がありそう。