やってみる

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

Rust自習(単方向リスト4)

 前回の続き。パクったコードがわからなかったので、読み解いてみた。

前回

 以下のコードがわからん。

    pub fn push(&mut self, item: T) {
        // 1. 最後の要素を取得する
        fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }
        }
        // 2. 最後の要素の`next`に新要素へのポインタをセットする
        let last = last_node(&mut self.head);
        *last = Some(Box::new(Node::new(item)));
    }

読み解く

構造体

 まずは構造体の定義から。

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

new

 構造体のコンストラクタ。

impl<T> Node<T> {
    fn new(item: T) -> Self { Self { item: item, next: None } }
}
impl<T> OnewayList<T> {
    pub fn new() -> Self { Self { head: None } }

 コンストラクタのテスト。

let list: OnewayList<i32> = OnewayList::new();
assert_eq!(list.head, None);

push

 ここからが問題。pushの定義。

    pub fn push(&mut self, item: T) {
        // 1. 最後の要素を取得する
        fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }
        }
        // 2. 最後の要素の`next`に新要素へのポインタをセットする
        let last = last_node(&mut self.head);
        *last = Some(Box::new(Node::new(item)));
    }

 pushのテスト。

let mut list: OnewayList<String> = OnewayList::new();
list.push(0);
list.push(1);
list.push(2);
assert_eq!(list.head, 
    Some(Box::new(Node { item: 0, next: 
        Some(Box::new(Node { item: 1, next: 
            Some(Box::new(Node { item:2, next: None }))
        }))
    }))
);

 成功する。だが、push内で何が起こっているのか、いまいちわからない。特にlast_node内部関数。

pushのコードを追ってみる

let mut list: OnewayList<String> = OnewayList::new();
list.push(0);
list.push(1);
list.push(2);

 このとき、いつ、何が、どうなっているか、追ってみる。

new

 一応、最初のnewから見る。

let mut list: OnewayList<String> = OnewayList::new();

 これは簡単。以下の通り。OnewayList::new()メソッドはOnewayList { head: None }構造体を返している。

pub struct OnewayList<T> {
    head: Option<Box<Node<T>>>,
}
impl<T> OnewayList<T> {
    pub fn new() -> Self { Self { head: None } }

 問題はpush

push: 1回目

 初回push

list.push(0);

 pushの引数について。self=list(OnewayList<i32>)、item=0(i32)。

    pub fn push(&mut self, item: T) {

 push関数内にはlast_node内部関数が定義されている。これをlet last = last_node(&mut self.head);で呼び出している。

 last_nodeの引数について。node=self.head(OnewayList.head)で開始。引数がNoneでなくSomeなら再帰する。再帰するときの引数はself.head.next(Node.next)なのがポイント。

        fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            // ...
        }
        // ...
        let last = last_node(&mut self.head);

 では、初回pushに戻って、追ってみる。まずは呼出。

list.push(0);

 push関数内に入る。最初の実行文は以下。引数はself.headへの可変参照。self.headの値はNoneである。newの実装どおり。

        let last = last_node(&mut self.head);

 last_node関数内に入る。このとき、引数nodeself.headへの可変参照である。if let文により*nodeで参照外しされ、self.headへの参照が指す値をみる。その値はNoneである。Someならif、それ以外ならelse。今回はNoneであるため、elseを通る。

 (ここを読み解くにはOption列挙体、if let文パターン(if let)パターンでの参照(ref)、参照外し*、参照&可変mutセミコロンがない式=戻り値、の理解が必須)

            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }

 nodeは引数である。つまりself.headへの可変参照。末尾にセミコロンがないので戻り値としてリターンする。

            else { node }

 last_node呼出元に戻る。たった今nodeを返した。それをlast変数で受け取っている。つまりlastself.headへの可変参照である。

        let last = last_node(&mut self.head);

 次。lastを参照外しして、その値にSome<Box<Node<T>>>を代入している。lastself.headへの可変参照である。その値はNone。そこへ新たな値Someを代入している。itempushの引数。list.push(0);で呼び出したとき0を渡している。この値が引数itemである。つまりself.headの値にSome(Box::new(Node::new(0)))を代入した。

        *last = Some(Box::new(Node::new(item)));

 テストコード。OnewayListインスタンスheadフィールド値は、Node { item: 0, next: None }である。

    #[test]
    fn OnewayList_push_1() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.push(0);
        assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None })));
    }

push: 2回目

 2回目のpush呼出。引数に1を渡す。

list.push(1);

 pushの引数について。selflistitem1である。

    pub fn push(&mut self, item: T) {

 push関数内に入る。最初の実行文は以下。引数はself.headへの可変参照。self.headSome(Box::new(Node { item: 0, next: None }))である。1回目のpush呼出でセットされた値だ。

        let last = last_node(&mut self.head);

 last_node関数内に入る。このとき、引数nodeself.headへの可変参照である。if let文により*nodeで参照外しされ、self.headへの参照が指す値をみる。その値はSome(Box::new(Node { item: 0, next: None }))である。Someならif、それ以外ならelse。今回はifを通る。

            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }

push: 2回目: last_node: 再帰1回目

 ifの処理内容をみてみる。last_node(&mut _n.next)を実行し、その戻り値を返す。last_node関数内で、last_node関数を呼んでいる。つまり再帰である。

 ただし引数が違う。再帰前はself.headが渡されていたが、今回再帰するときの引数はnode.nextである。nodelast_nodeの引数であり、self.headである。つまり、node.nextとは、self.head.nextである。

 if let文のパターンSome(ref mut _n)により、*nodeSomeのとき{ last_node(&mut _n.next) }を実行するよう示している。_nSomeの中にあるBox::new(Node { item: 0, next: None })である。*で参照外ししているためNode { item: 0, next: None }となる。refはパターン式における参照&を意味する。ref mut&mutの意である。つまりSome(ref mut _n) = *nodeは、Node { item: 0, next: None }がもつNodeインスタンスnextフィールドにおける可変参照を、変数_nに代入している。let _n = *node.as_mut();と同じ意味だと思う。

            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }

 再帰呼出をみてみる。&mut _n.nextNode.nextフィールドへの可変参照である。これを再帰への引数として渡している。再帰の実行が完了したら、その戻り値をそのままリターンする。これにてlast_node関数を抜ける。

            ... { last_node(&mut _n.next) }

 再帰呼出元がわかったところで、再帰処理に入る。引数nodeは先述のとおりself.head.nextへの可変参照である。self.headSome(Box::new(Node { item: 0, next: None }))である。そのnextフィールドの値はNone。つまり、self.head.nextの値はNoneである。self.head.nextの可変参照はそのメモリアドレスである。つまりNode構造体インスタンスのうちnextフィールドを指す先頭アドレス。

        fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }

 if let文により、引数nodeを参照外しする。その値はNoneである。よってelseを通る。elsenodeをそのまま返す。ここでlast_node再帰1回目を抜ける。

            else { node }

push: 2回目: last_node: 再帰1回目からの帰還

 再帰1回目は以下コードのifから呼び出されていた。再帰1回目が返した値nodeは、self.head.nextへの可変参照である。その値はNone

        fn last_node<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> {
            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }

 再帰で返された値を、再びそのまま返す。

            ... { last_node(&mut _n.next) }

push: 2回目: last_node: 呼出からの帰還

 最初のlast_node呼出元に帰ってきた。last_nodeself.head.nextへの可変参照を返している。それをlast変数で受け取っている。

    pub fn push(&mut self, item: T) {
        // ...
        let last = last_node(&mut self.head);
        *last = Some(Box::new(Node::new(item)));
    }

 lastを参照外しし、その値にSomeを代入している。lastself.head.nextへの可変参照であり、その値はNoneだった。これが次の値Some(...)で上書きされる。内部でitemが使われている。itemは2回目pushの呼出list.push(1);にあるとおり1である。よってself.head.nextSome(Box::new(Node::new(1)))が代入される。

        *last = Some(Box::new(Node::new(item)));

 push2回目終了。テストコードは以下。

    #[test]
    fn OnewayList_push_2() {
        let mut list: OnewayList<i32> = OnewayList::new();
        list.push(0);
        list.push(1);
        assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None })) })));
    }

last_node内部関数の正体

 ここまででlast_node内部関数の正体がわかっただろう。last_nodeはOnewayListが持つNode数に応じて可変参照を返す。その条件と戻り値の対応は以下。

条件(Node数) 戻り値(可変参照)
0 OnewayList.head
1以上 Node.next

 リストが持つノード数がゼロならOnewayList.headフィールドへの可変参照を返す。リストが持つノード数が1つ以上なら、最後のノードのNode.nextフィールドへの可変参照を返す。それらの値は必ずNoneである。また、それらの型は各構造体の定義どおりOption<Box<Node<T>>>型である。last_node関数では、それらの可変参照を扱うため&mutを付与している。

所感

 Rust構文のむずかしさもさることながら、再帰のむずかしさもある。処理を順に追っていかねばピンとこない。また、処理を追うためには都度Rust構文の意味を解釈せねばならず、混乱する。

 少なくとも、Rust構文はすべて空気を吸うかのごとく当然のこととして解釈できるだけの知識がほしい。でも、Rustの自習をしている最中だから、両方を同時にせざるを得ない。そのせいで混乱しやすい。

 今回はif letまわりが難しかった。これ、パターン構文のせいで難しいのだと思う。参照がrefになるとか。さらにstd::option::Option列挙体やstd::boxed::Box構造体にラップされているせいでネストが深いのも難解さに拍車をかけている。ほかにも参照外しとか可変性とか細かいのが絡み合っている。Rustの理解力を試されるコードだった。私はまだ構文レベルでの理解が浅いと痛感した。

 ちなみに、以下の文はどちらで書いても同じである。私はmatch文のほうが見やすい。

case1

            if let Some(ref mut _n) = *node { last_node(&mut _n.next) }
            else { node }

case2

            match *node {
                Some(ref mut _n) => last_node(&mut _n.next),
                _ => node
            }
  1. Rust構文をマスターする(読める、書ける)
  2. 再帰を知る
  3. 再帰を読み解く
  4. 再帰を書けるようになる

 大まかに言ってこの4ステップが必要か。単方向リストを作るって、大変だね……。楽勝だと思ってたのに、どんどん奈落の底に転がり落ちていく感じ。

対象環境

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

前回まで