やっと見つけた。
成果物
参考
コードを読むとiter(), iter_mut()が実装されている。だが、標準モジュールでなく自作の構造体にみえる。これでmap(), filter()などを使えるのか？ まずは、動作確認から。
動作確認
コードを入手してテストを実行する。
$ git clone https://github.com/Gankro/too-many-lists $ cd lists $ cargo test
コンパイルエラー……。
error[E0382]: use of moved value: `node` --> src/first.rs:36:22 | 35 | self.head = node.next; | --------- value moved here 36 | Some(node.elem) | ^^^^^^^^^ value used here after move | = note: move occurs because `node.next` has type `first::Link`, which does not implement the `Copy` trait error[E0382]: use of moved value: `node` --> src/second.rs:29:13 | 28 | self.head = node.next; | --------- value moved here 29 | node.elem | ^^^^^^^^^ value used here after move | = note: move occurs because `node.next` has type `std::option::Option<std::boxed::Box<second::Node<T>>>`, which does not implement the `Copy` trait error: aborting due to 2 previous errors For more information about this error, try `rustc --explain E0382`. error: Could not compile `lists`. warning: build failed, waiting for other jobs to finish... error[E0382]: use of moved value: `node` --> src/first.rs:36:22 | 35 | self.head = node.next; | --------- value moved here 36 | Some(node.elem) | ^^^^^^^^^ value used here after move | = note: move occurs because `node.next` has type `first::Link`, which does not implement the `Copy` trait error[E0382]: use of moved value: `node` --> src/second.rs:29:13 | 28 | self.head = node.next; | --------- value moved here 29 | node.elem | ^^^^^^^^^ value used here after move | = note: move occurs because `node.next` has type `std::option::Option<std::boxed::Box<second::Node<T>>>`, which does not implement the `Copy` trait error: aborting due to 2 previous errors For more information about this error, try `rustc --explain E0382`. error: Could not compile `lists`. To learn more, run the command again with --verbose.
エラーはfirst.rs, second.rsの2ファイルのみ。そこでコードを以下のように修正した。
lib.rs
//pub mod first; //pub mod second; pub mod third; pub mod fourth; pub mod fifth; pub mod silly1;
これでテストは通った。たぶんドキュメントの1章, 2章に対応したコードなのだろう。まだ途中であってエラーを含んでいたコードだったのかな？
$ cargo test ... running 10 tests test fifth::test::basics ... ok test fifth::test::iter ... ok test fifth::test::iter_mut ... ok test fourth::test::basics ... ok test fourth::test::into_iter ... ok test silly1::test::walk_aboot ... ok test fourth::test::peek ... ok test third::test::basics ... ok test third::test::iter ... ok test fifth::test::into_iter ... ok test result: ok. 10 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out ...
mapやfilterが使えるか確認
最終章のコードが完成版だろうと予想し、それにテストコードを追加してみた。
map
fifth.rs
#[test] fn iter_mut_2() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) } }
mapで新たなイテレータを生成できたことを確認。
filter
let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![1,2,3]; for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().filter(|elem| **elem % 2 == 0).enumerate() { assert_eq!(*value, 2) }
filterで偶数のみ抽出できたことを確認。
mutable
let mut expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().enumerate() { *value *= 10; } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) }
値の代入ができた（可変性がある）ことを確認。
最終コード
$ cargo new list_iter --lib
lib.rs
use std::ptr; pub struct List<T> { head: Link<T>, tail: *mut Node<T>, } type Link<T> = Option<Box<Node<T>>>; struct Node<T> { elem: T, next: Link<T>, } impl<T> List<T> { pub fn new() -> Self { List { head: None, tail: ptr::null_mut() } } pub fn push(&mut self, elem: T) { let mut new_tail = Box::new(Node { elem: elem, next: None, }); let raw_tail: *mut _ = &mut *new_tail; if !self.tail.is_null() { unsafe { (*self.tail).next = Some(new_tail); } } else { self.head = Some(new_tail); } self.tail = raw_tail; } pub fn pop(&mut self) -> Option<T> { self.head.take().map(|head| { let head = *head; self.head = head.next; if self.head.is_none() { self.tail = ptr::null_mut(); } head.elem }) } pub fn peek(&self) -> Option<&T> { self.head.as_ref().map(|node| { &node.elem }) } pub fn peek_mut(&mut self) -> Option<&mut T> { self.head.as_mut().map(|node| { &mut node.elem }) } pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_ref().map(|node| &**node) } } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { next: self.head.as_mut().map(|node| &mut **node) } } } pub struct IntoIter<T>(List<T>); pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } pub struct IterMut<'a, T> { next: Option<&'a mut Node<T>>, } impl<T> Drop for List<T> { fn drop(&mut self) { let mut cur_link = self.head.take(); while let Some(mut boxed_node) = cur_link { cur_link = boxed_node.next.take(); } } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.0.pop() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_ref().map(|node| &**node); &node.elem }) } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| { self.next = node.next.as_mut().map(|node| &mut **node); &mut node.elem }) } } #[cfg(test)] mod test { use super::List; #[test] fn basics() { let mut list = List::new(); // Check empty list behaves right assert_eq!(list.pop(), None); // Populate list list.push(1); list.push(2); list.push(3); // Check normal removal assert_eq!(list.pop(), Some(1)); assert_eq!(list.pop(), Some(2)); // Push some more just to make sure nothing's corrupted list.push(4); list.push(5); // Check normal removal assert_eq!(list.pop(), Some(3)); assert_eq!(list.pop(), Some(4)); // Check exhaustion assert_eq!(list.pop(), Some(5)); assert_eq!(list.pop(), None); // Check the exhaustion case fixed the pointer right list.push(6); list.push(7); // Check normal removal assert_eq!(list.pop(), Some(6)); assert_eq!(list.pop(), Some(7)); assert_eq!(list.pop(), None); } #[test] fn into_iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.into_iter(); assert_eq!(iter.next(), Some(1)); assert_eq!(iter.next(), Some(2)); assert_eq!(iter.next(), Some(3)); assert_eq!(iter.next(), None); } #[test] fn iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.iter(); assert_eq!(iter.next(), Some(&1)); assert_eq!(iter.next(), Some(&2)); assert_eq!(iter.next(), Some(&3)); assert_eq!(iter.next(), None); } #[test] fn iter_mut() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.iter_mut(); assert_eq!(iter.next(), Some(&mut 1)); assert_eq!(iter.next(), Some(&mut 2)); assert_eq!(iter.next(), Some(&mut 3)); assert_eq!(iter.next(), None); } #[test] fn iter_2() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![1,2,3]; for (i, value) in list.iter().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter().enumerate() { assert_eq!(*value, expecteds[i]) } let expecteds = vec![10,20,30]; for (i, value) in list.iter().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) } for (i, value) in list.iter_mut().filter(|elem| **elem % 2 == 0).enumerate() { assert_eq!(*value, 2); } } #[test] fn iter_mut_3() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) } let expecteds = vec![1,2,3]; for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().filter(|elem| **elem % 2 == 0).enumerate() { assert_eq!(*value, 2); } let mut expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().enumerate() { *value *= 10; } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } } }
$ cargo test ... running 6 tests test test::basics ... ok test test::into_iter ... ok test test::iter ... ok test test::iter_mut ... ok test test::iter_2 ... ok test test::iter_mut_3 ... ok test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out ...
コードを読む
ListとNodeの構造体。
pub struct List<T> { head: Link<T>, tail: *mut Node<T>, } type Link<T> = Option<Box<Node<T>>>; struct Node<T> { elem: T, next: Link<T>, }
iter()メソッド等の実装。
impl<T> List<T> { ... pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_ref().map(|node| &**node) } } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { next: self.head.as_mut().map(|node| &mut **node) } }
self.head.as_ref().map？
iter()はNodeインスタンスへの不変参照をもった構造体Iterを返す。
そのうちself.head.as_ref().mapの部分がよくわからない。self.headはOption<Box<Node<T>>>であり、その参照を取得すべくas_ref()しているのはわかる。だが、BoxやNodeはmapメソッドなど持っていないと思うのだが。
一体、いつNodeにmapメソッドが実装されたのか？ そのコードはどこ？
pub struct IntoIter<T>(List<T>); pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } pub struct IterMut<'a, T> { next: Option<&'a mut Node<T>>, } impl<T> Drop for List<T> { fn drop(&mut self) { let mut cur_link = self.head.take(); while let Some(mut boxed_node) = cur_link { cur_link = boxed_node.next.take(); } } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.0.pop() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_ref().map(|node| &**node); &node.elem }) } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| { self.next = node.next.as_mut().map(|node| &mut **node); &mut node.elem }) } }
Iter, IterMutは自前の構造体らしい。
pub struct IntoIter<T>(List<T>); pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } pub struct IterMut<'a, T> { next: Option<&'a mut Node<T>>, }
map実装箇所特定のため、それに無関係と思われるコードをコメントアウトする。以下、コンパイルできた。
use std::ptr; pub struct List<T> { head: Link<T>, tail: *mut Node<T>, } type Link<T> = Option<Box<Node<T>>>; struct Node<T> { elem: T, next: Link<T>, } impl<T> List<T> { pub fn new() -> Self { List { head: None, tail: ptr::null_mut() } } pub fn push(&mut self, elem: T) { let mut new_tail = Box::new(Node { elem: elem, next: None, }); let raw_tail: *mut _ = &mut *new_tail; if !self.tail.is_null() { unsafe { (*self.tail).next = Some(new_tail); } } else { self.head = Some(new_tail); } self.tail = raw_tail; } pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_ref().map(|node| &**node) } } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { next: self.head.as_mut().map(|node| &mut **node) } } } pub struct Iter<'a, T> { next: Option<&'a Node<T>>, } pub struct IterMut<'a, T> { next: Option<&'a mut Node<T>>, } impl<T> Drop for List<T> { fn drop(&mut self) { let mut cur_link = self.head.take(); while let Some(mut boxed_node) = cur_link { cur_link = boxed_node.next.take(); } } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_ref().map(|node| &**node); &node.elem }) } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| { self.next = node.next.as_mut().map(|node| &mut **node); &mut node.elem }) } }
#[cfg(test)] mod test { use super::List; #[test] fn iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.iter(); assert_eq!(iter.next(), Some(&1)); assert_eq!(iter.next(), Some(&2)); assert_eq!(iter.next(), Some(&3)); assert_eq!(iter.next(), None); } #[test] fn iter_mut() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.iter_mut(); assert_eq!(iter.next(), Some(&mut 1)); assert_eq!(iter.next(), Some(&mut 2)); assert_eq!(iter.next(), Some(&mut 3)); assert_eq!(iter.next(), None); } #[test] fn iter_2() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![1,2,3]; for (i, value) in list.iter().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter().enumerate() { assert_eq!(*value, expecteds[i]) } let expecteds = vec![10,20,30]; for (i, value) in list.iter().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) } for (i, value) in list.iter_mut().filter(|elem| **elem % 2 == 0).enumerate() { assert_eq!(*value, 2); } } #[test] fn iter_mut_3() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) } let expecteds = vec![1,2,3]; for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } for (i, value) in list.iter_mut().filter(|elem| **elem % 2 == 0).enumerate() { assert_eq!(*value, 2); } let mut expecteds = vec![10,20,30]; for (i, value) in list.iter_mut().enumerate() { *value *= 10; } for (i, value) in list.iter_mut().enumerate() { assert_eq!(*value, expecteds[i]) } } }
- Option.mapメソッド
もしやOptionのメソッドだったのか？ Option.mapはOption::Some(T)のTインスタンスを別の型にした値として新規生成し、返却するメソッドと思われる。
pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_ref().map(|node| &**node) } } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { next: self.head.as_mut().map(|node| &mut **node) } }
上記コードのmapはOption<Box<Node<T>>>を&Option<Node<T>>に変換ている。
self.headはOption<Box<Node<T>>>。Option.as_ref()で不変参照にしつつOption.map()で別型を生成する。型はBoxを参照外しして&を付与する。つまり&Option<Node<T>>型。最後にIter構造体にくるんで返す。
でもlist.iter().map(|elem| *elem * 10).enumerate()は？ enumerate()メソッドはOption型に実装されていない。でも、以下コードは動く。なぜ？
for (i, value) in list.iter().map(|elem| *elem * 10).enumerate() { assert_eq!(value, expecteds[i]) }
さすがにenumerateはイテレータ型でないと実装されていないはず。いつからイテレータ型になっていた？ そして、どこでそれを実装している？
impl<'a, T> Iterator for Iter<'a, T>
もしや、以下だろうか。
impl<'a, T> Iterator for Iter<'a, T> { impl<'a, T> Iterator for IterMut<'a, T> {
Iteratorはstd::iter::Iteratorのことである（標準モジュールであって自作でない）- 自作の
Iter,IterMutにstd::iter::Iteratorを実装する - 2にて、
Iter,IterMutを返すメソッドiter(),iter_mut()はイテレータとなる list.iter()はすでにイテレータ型であり、enumerate(),map(),filter()などが使える
という解釈で合っているかな？
それだと、std::iter::Iteratorトレイトを実装すればいいことになる。だが、これまでは要素が消費されてしまう実装しかできなかった。今回、消費されず参照を返す実装ができていた。違いはどこにあるのか？
おそらく以下コードの&'a, &'a mutがポイント。そのためだけにIter, IterMut構造体をわざわざ新設し、それぞれに以下のようなトレイト実装をしている。これにてiter(), iter_mut()は消費しない参照を返すイテレータになれたのだろう。
impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { self.next.map(|node| { self.next = node.next.as_ref().map(|node| &**node); &node.elem }) } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { self.next.take().map(|node| { self.next = node.next.as_mut().map(|node| &mut **node); &mut node.elem }) } }
つまり、以下のような3種類の型に、それぞれstd::iter::Iteratorトレイトのnextメソッドをオーバーライドせねばならない。
| 型 | type Item |
|---|---|
| 値 | T |
| 不変参照 | &'a T |
| 可変参照 | &'a mut T |
ほぼ重複するコードを大量に書くハメになる。DRYに書けないとかダサすぎる。
消費されない理由
イテレータの要素が消費されない理由。Iter, IterMut構造体インスタンスはListが所有権をもつNodeインスタンスの参照変数をもつだけ。だからIterはListやNodeからそれらの所有権を奪わない。Iterは単に参照変数をもった構造体として新規生成される。
もっとも、Iter, IterMutインスタンスは所有権をムーブしているが、それらは毎回生成して使い捨てればいい。
という解釈で合っていると思う。
Iter.next()
最初はList.head。その参照をとる。List.headはNodeインスタンスを指す。Nodeがもつnextの参照を、Iter.nextにセットする。これにて次回は次のノードに対して実行する。最後にNode.elemの参照を返す。
対象環境
- 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
前回まで
- Rust学習まとめ（ドキュメント）
- Rust自習（じゃんけんゲーム1）
- Rust自習（双方向リスト1）
- Rust自習（単方向リスト1）
- Rust自習（単方向リスト2）
- Rust自習（単方向リスト3）
- Rust自習（単方向リスト4）
- Rust自習（単方向リスト5）
- Rust自習（単方向リスト6）
- Rust自習（単方向リスト7）
- Rust自習（リストのインタフェースを考える）
- Rust自習（連結リスト1）
- Rust自習（連結リスト2）
- Rust自習（連結リスト3）
- Rust自習（連結リスト4）
- Rust自習（連結リストの取得系インタフェース考察）
- Rust自習（連結リスト5）
- Rust自習（連結リストの取得系インタフェース考察2）
- Rust自習（連結リスト6）
- Rust自習（連結リスト7）
- Rust自習（連結リスト8）
- Rust自習（連結リスト9）
- Rust自習（変数名でイテレートする方法）
