remove_tailメソッドを実装した。
成果物
コード
pub fn remove_tail(&mut self) { if self.head.is_none() { return; } // 1. 末尾ノードを指すポインタを返す(OnewayList.head or Node.next) fn get_booby_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) if _n.next.is_some() => get_booby_node_ptr(&mut _n.next), _ => node } } let booby = get_booby_node_ptr(&mut self.head); if booby.is_some() { std::mem::replace(&mut *booby, None); } }
テストコード
#[test] fn OnewayList_remove_tail_3() { let mut list: OnewayList<i32> = 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 })) })) }))); list.remove_tail(); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: Some(Box::new(Node { item: 1, next: None })) }))); list.remove_tail(); assert_eq!(list.head, Some(Box::new(Node { item: 0, next: None }))); list.remove_tail(); assert_eq!(list.head, None); }
解説
ポイントはget_booby_node_ptr内部関数。
// 1. 末尾ノードを指すポインタを返す(OnewayList.head or Node.next) fn get_booby_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) if _n.next.is_some() => get_booby_node_ptr(&mut _n.next), _ => node } }
これ、push関数のときに似たような関数get_tail_node_ptrがあった。そこからパクった。
pub fn push(&mut self, item: T) { // 1. 新しい末尾ノードを指すポインタを返す(OnewayList.head or Node.next) fn get_tail_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) => get_tail_node_ptr(&mut _n.next), _ => node } } // 2. 新しい末尾ノードを指すポインタを取得する let last = get_tail_node_ptr(&mut self.head); // 3. 新しい末尾ノードポインタの値として生成した新ノードを代入する *last = Some(Box::new(Node::new(item))); }
これはNoneなNode.nextかOnewayList.headのポインタを返していた。
今回はnextがNoneになる一つ前のノードを指すポインタを返す。ビリから二番目のブービー賞boobyという名前にした。
fn get_booby_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) if _n.next.is_some() => get_booby_node_ptr(&mut _n.next), _ => node } }
コードを追う: remove_tail
まずは1行目。ノードがひとつもなかったら即座に終了する。
ここ、スマートでない。じつはこの行がなくとも、ノードがゼロのときは何も実行されないよう実装している。だが、いくらか無駄に処理が走る。そこでこの一行を入れた。だが、この行も無駄に思える。ま、いっか。
if self.head.is_none() { return; }
内部関数の呼出。最後のノードを指すポインタを取得する。
let booby = get_booby_node_ptr(&mut self.head);
なぜ最後のノードを指すポインタなのに、ブービー(最後から二番目)という名前なのか？ これも、なんと名付けていいか迷った。ただ、pushのときに最後tailと名付けてしまったから、それより1つ前のノードを返す本関数にはboobyと名付けるしかなかった。まさか処理が違うのに同じ名前にするわけにもいかない。
また、次のような理由もある。最後のノードを所有しているのは、最後から二番目のNodeインスタンスがもつnextフィールドである。つまり最後のノードを削除するには、最後から二番目のノードがもつnextフィールドを取得する必要がある。よって、最後から二番目であるブービー(booby)という名前にした。でもそのノードは末尾ノードであって最後から2番目ではない。だから本関数こそget_tail_node_ptrという名前にすべきな気がする。じゃあそのノードのnextを返す関数の名前はどうすべき？ わからん！
どうも直感的な名前じゃない気がする。だからといって、「末尾ノードのnextフィールドを取得する（get_next_field_for_last_node()）」という正確だけど長ったらしい名前にするのも、どうかと思った。いや、OnewayList.headを返すときもあるから正確ですらない。名付けは難しい。
では本題のget_booby_node_ptr内部関数を見てみる。
fn get_booby_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) if _n.next.is_some() => get_booby_node_ptr(&mut _n.next), _ => node } }
引数nodeがSome(Nodeがある)で、かつnextフィールドもSome(Nodeがある)なら、再帰する。それ以外なら、引数nodeを返す。
ポイントはマッチガードのif文。nextフィールドに次のノードがあるということは、今のノードは末尾ノードではないということ。そのときは再帰する。そして、nextがNoneならば、そのノードを指すポインタを返す。つまり末尾ノードを指すポインタを返す。
末尾ノードを指すポインタ変数は、そのひとつ前のNode構造体インスタンスのnextが所有している。それの所有権を奪わず&mutという可変参照を引数と戻り値にしている。このメソッドで最終的に返すのは、先述の通り、末尾ノードを指すnextポインタ変数への可変参照だ。
内部関数が終了する。booby変数にて、末尾ノードを指すポインタ変数への可変参照を受け取る。
let booby = get_booby_node_ptr(&mut self.head);
boobyにNoneを代入し、前の値をとりだす。それを戻り値で受け取らず、そのままスコープ終了するとdropする。これにて末尾ノードの削除完了。
if booby.is_some() { std::mem::replace(&mut *booby, None); }
末尾ノードを指すポインタ変数への可変参照？
って何？ お前は何を言っているんだ？
これはメモリの状態を見ながらでないと説明できない。というわけで、ひとつずつ見ていく。
Nodeインスタンス
Node構造体をメモリ確保したときのメモリの様子。
Node +-----------+-----------+ |item |next | +--+--+--+--+--+--+--+--+ |00|00|00|00|00|00|00|00| バイト状態(0x00〜0xFF) +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 メモリアドレス(番地)
状態とアドレスは16進数で表現する。
メモリアドレスは適当に割り振った。1Byte単位で1番ずつ割り振らるものとする。PCのメモリが4GBだとすると、4*(10^9)番まである。つまり4,000,000,000番まで。
バイト状態。1Byteあたりの状態は0x00〜0xFFの256種類ある。最初はすべて0x00だと仮定する。
itemは<T>型だが、ここではi32型(4Byte)と仮定する。nextはOption<Box<Node<T>>>だが、ここではメモリアドレス番地を格納するサイズi32型(4Byte)と仮定する。
このNodeインスタンスは8Byteのメモリを専有している。専有しているメモリの場所は、メモリ番地0〜7である。
list.push(1) (Node::new(1))
最初のノードを生成する。itemの値は1。list.push(1)で呼び出すとNode::new(1)が実行される。。
first +-----------+-----------+ |item |next | +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|00| +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7
メモリ番地3の値が01になっている。これはitemの値。ちなみに、もしNode::new(255)なら以下。
first +-----------+-----------+ |item |next | +--+--+--+--+--+--+--+--+ |00|00|00|FF|00|00|00|00| +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7
メモリ番地3の値がFFになっている。これは10進数255を16進数で表現したときの値である。
そしてNode::new(256)なら以下。
first +-----------+-----------+ |item |next | +--+--+--+--+--+--+--+--+ |00|00|01|00|00|00|00|00| +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7
メモリ番地2の値が01, メモリ番地3の値が00。item4Byte全体でいうと00 00 01 00。つまり16進数でいう0x0100である。こんな感じでitemは4Byteの表現幅がある。
list.push(2) (Node::new(2))
2番目のノードを作成する。
first second +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|08| |00|00|00|02|00|00|00|00| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F
ポイントはfirstのnext。メモリ番地7の値が08になっている。これはsecondの先頭アドレスである。secondはメモリ番地8〜Fを専有している。firstノードがもつnextフィールドは、次のノードを指し示すポインタだ。ポインタとはアドレス番地を指し示すものである。特に、ある単位における先頭アドレスを指す。ここではNode構造体インスタンスsecondの先頭アドレスを指す。つまり8。
そしてsecondのitemは2である。メモリ番地Bが02になっているのがそれだ。secondのnextはNoneである。ここではNoneを0としている。だが、メモリ番地0と重複していて紛らわしい。これだとメモリ番地0を示しているように見える。そこで、ここでは便宜上FF FF FF FFをNoneとする。
first second +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|08| |00|00|00|02|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F
このルールに則り、ノードがfirstひとつだけだったときの状態を、以下のように表現しなおしておく。もっとも、すでにこの状態ではないが。
first +-----------+-----------+ |item |next | +--+--+--+--+--+--+--+--+ |00|00|00|01|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7
list.push(3) (Node::new(3))
3つ目のノードを追加した。もうお分かりだろう。
first second third +-----------+-----------+ +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|08| |00|00|00|02|00|00|00|10| |00|00|00|03|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17
3つ目のノードthirdのitemは3である。メモリ番地13の値03でそれを表している。nextフィールドはNoneである。これはFF FF FF FFで表現している。
2つ目のノードsecondのnextがthirdの先頭アドレスを指している。thirdの先頭アドレスは10。これをsecond.nextに代入している。メモリ番地Fの値10でそれを表している。
ポインタ(参照)
ポインタ(参照)とは、メモリアドレスである。
ポインタとは指し示す者である。つまり、メモリ領域を指し示す者である。
ポインタ変数
メモリ領域を指し示すとは、「メモリ番地を記憶すること」によって実現している。当然、記憶領域が必要である。その分だけメモリを食う。
どのくらい必要なのか。システムのメインメモリ量などによる。たとえば4GBなら0〜4,000,000,000番まである。これを格納できるのは4Byte。
細かい話をすれば正確ではないかもしれない。だが、本筋から外れるので省略。
ポインタのポインタ
ポインタもまたメモリ領域が必要である。ならば、そのメモリ領域を指し示すポインタもありうる。
first second third +-----------+-----------+ +-----------+-----------+ +-----------+-----------+ |item |next | |item |next | |item |next | +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |00|00|00|01|00|00|00|08| |00|00|00|02|00|00|00|10| |00|00|00|03|FF|FF|FF|FF| +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17
構造体を生成する。
let first = Node::new(1); let second = Node::new(2); let third = Node::new(3);
変数に&, &mutを付与すると以下のような意味になる。
first // 値 &first // 読取専用ポインタ(不変参照) &mut first // 読書ポインタ(可変参照)
ref_node変数に各ノードのポインタ(不変参照)を代入する。最後に参照外しして取得されるのはthirdの値である。
let ref_node = &first; ref_node = &second; ref_node = &third; *ref_node // 参照外し（指し示している値を取り出す）
Node<i32>としたとき、itemはi32である。i32型でも同様。
first.item // 値 &first.item // 読取専用ポインタ(不変参照) &mut first.item // 読書ポインタ(可変参照)
Boxはスマートポインタである。つまりnextはポインタ変数。
struct Node<T> { item: T, next: Option<Box<Node<T>>>, }
&mut Boxは「ポインタのポインタ」である。
fn get_tail_node_ptr<T>(node: &mut Option<Box<Node<T>>>) -> &mut Option<Box<Node<T>>> { match *node { Some(ref mut _n) => get_tail_node_ptr(&mut _n.next), _ => node } }
Nodeインスタンスが所有するnextフィールドはポインタ変数である。これをそのまま関数でリターンすることはできない。所有権がNodeインスタンスからムーブすることになってしまう。その結果、get_tail_node_ptr関数のスコープが終了すると削除されてしまう。それは困る。所有権はそのまま保持してリストを構築していて欲しい。
末尾ノードの検索は、所有権を奪わず、末尾ノードのメモリアドレスだけ分かればいい。つまり、nextというポインタ変数のメモリアドレスを取得できればいい。ポインタ変数のメモリアドレスを格納するポインタ変数を用意する。それが関数の引数と戻り値の&mut Boxである。
&mutは可変参照、つまり読書できるポインタ。つまり代入もできる。pushメソッドは検索した末尾ノードを指すポインタ変数にノードを代入している。
*last = Some(Box::new(Node::new(item)));
remove_tailメソッドは現存する末尾ノードを指すポインタ変数にNoneを代入している。std::mem::replace関数によって所有権ムーブエラーを回避する方法で。
if booby.is_some() { std::mem::replace(&mut *booby, None); }
紛らわしい用語
- ポインタ＝ポインタ変数＝参照≒不変参照≒可変参照
紛らわしいのは私がまとまりのない書き方をしているせい。たぶん理解度も微妙なのだろう。
参照
ここでは「ポインタ」と「参照」という語を併用した。ほぼ同じ意味なのに。本当は統一したほうがいい。Rustは「参照」と言う。だが、参照という言葉が一般的すぎて混同してしまうことがある。たとえば、ただ変数の値を読むとき「変数aを参照する」などと言ったりする。その文脈ではポインタなど一切意識する必要がないにも関わらず。その意味は「変数aが指すメモリの状態をinteger型として読み取る」という意味である。あるいは、それをやった上でprintln!で表示することを「変数aを参照する」と言ったりする。文脈によって変わるので非常に紛らわしい。だから「参照」という語は避けたい。
ポインタ
どう表現するのが適切か？ Rustでは「不変参照」か「可変参照」とするのが正確だろう。「参照」という語を単独で使うと先述のような混同が生じうるが、可変性と併用すれば区別がつくはず。だが、「不変」や「可変」が余計な説明であるときがある。今回のようにポインタの概念を説明するときなどだ。
ポインタと参照は、CとRustという異なる文脈の用語である
そもそもRustの「参照」はC言語のポインタに制約をつけた版。だからまずはC言語のポインタを理解している必要がある。なのに、ポインタの概念はわかりにくい。それに、事前に16進数とかバイトとかも知っている必要がある。べつに大雑把に説明するなら他にやりようもあるが。そんなわけで、できるだけ簡潔明瞭に表したかった。そこで「ポインタ」という名前を使ってしまった。というか、ポインタの説明もせずにポインタの制約版である参照の説明などできるはずがない。だから不変参照とか可変参照という名前は使えなかった。
だが、途中から「ポインタの可変参照」という表現を使っていた。C言語なら「ポインタのポインタ」と言っていた所だ。ポインタという語を使ったのは先述の理由である。なのにすぐ後で「可変参照」という避けたいはずの用語を使った。その理由は、&mutというコード表現に引きずられた結果である。
どうやって説明すれば良かったんだろう。最初にC言語の「ポインタ」を説明し、次に別文脈としてRust言語の「参照」を説明するのが良かったのか。
所感
ポインタのポインタは超便利。だけど抽象的すぎて何が何だかわからなくなりやすい。
対象環境
- 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
