前回の続き。パクったコードがわからなかったので、読み解いてみた。
前回
以下のコードがわからん。
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関数内に入る。このとき、引数nodeはself.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変数で受け取っている。つまりlastはself.headへの可変参照である。
let last = last_node(&mut self.head);
次。lastを参照外しして、その値にSome<Box<Node<T>>>を代入している。lastはself.headへの可変参照である。その値はNone。そこへ新たな値Someを代入している。itemはpushの引数。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の引数について。selfはlist、itemは1である。
pub fn push(&mut self, item: T) {
push関数内に入る。最初の実行文は以下。引数はself.headへの可変参照。self.headはSome(Box::new(Node { item: 0, next: None }))である。1回目のpush呼出でセットされた値だ。
let last = last_node(&mut self.head);
last_node関数内に入る。このとき、引数nodeはself.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である。nodeはlast_nodeの引数であり、self.headである。つまり、node.nextとは、self.head.nextである。
if let文のパターンSome(ref mut _n)により、*nodeがSomeのとき{ last_node(&mut _n.next) }を実行するよう示している。_nはSomeの中にある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.nextはNode.nextフィールドへの可変参照である。これを再帰への引数として渡している。再帰の実行が完了したら、その戻り値をそのままリターンする。これにてlast_node関数を抜ける。
... { last_node(&mut _n.next) }
再帰呼出元がわかったところで、再帰処理に入る。引数nodeは先述のとおりself.head.nextへの可変参照である。self.headはSome(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を通る。elseはnodeをそのまま返す。ここで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_nodeはself.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を代入している。lastはself.head.nextへの可変参照であり、その値はNoneだった。これが次の値Some(...)で上書きされる。内部でitemが使われている。itemは2回目pushの呼出list.push(1);にあるとおり1である。よってself.head.nextにSome(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 }
大まかに言ってこの4ステップが必要か。単方向リストを作るって、大変だね……。楽勝だと思ってたのに、どんどん奈落の底に転がり落ちていく感じ。
対象環境
- 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
