前回の続き。パクったコードがわからなかったので、読み解いてみた。
前回
以下のコードがわからん。
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)));
push
2回目終了。テストコードは以下。
#[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