既存のインタフェース調査。
前回
std::iter::Iterator.next()を実装した。これにてinto_iter()も自動的に得られた。そしてIteratorがもつメソッドを使えばfilter()などの操作も使える。
ただし、next()とinto_iter()はどちらも所有権をムーブする。所有権をそのままにした操作も欲しい。どうやって実装するのか不明なため調査する。
調査
iter()デフォルト実装はない
iter()メソッドがトレイト実装のデフォルトに存在したりしないかな？
let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.push(2); for (i, value) in list.iter().enumerate() { assert_eq!(value, expecteds[i]); }
error[E0599]: no method named `iter` found for type `LinkedList<i32>` in the current scope
--> src/lib.rs:582:32
|
2 | pub struct LinkedList<T> {
| ------------------------ method `iter` not found for this
...
582 | for (i, value) in list.iter().enumerate() {
| ^^^^
無いですね、すみません。
std::slice::Iter
これにもiter()がある。でも、こいつが何者なのかイマイチわからん。たぶん配列のように[0]みたいなインデックス指定する記法を実装していると思われる。list[0..3]とかもできるスライス。
でもこれ、スライス型という固有の型であって、自作した構造体にその機能を実装できるものではないかもしれない。[]演算子のオーバーライド実装みたいなことはできないのだろうか？ 情報がない。後回し。
std::vec::Drain
DrainというIteratorの参照版があるらしい。
でもこれ、トレイトでなく構造体らしい。自作の構造体に実装する類のものではないのか？ DrainはVec名前空間内のものみたいだし。
しかもドキュメントを見ると、唯一のメソッドas_slice()は開発版(nightly)でのみ使えるっぽい。安定版(stable)では使えない。（調査時点）
もしかして、自作の構造体でiter()を実装するには、Vecのコードをパクって同じようにunsafe Rustで書かないと実装できないの？
Vecのコード
Drainメソッド
vecインスタンスからDrain構造体を返すメソッド。
#[stable(feature = "drain", since = "1.6.0")] pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> where R: RangeBounds<usize> { // Memory safety // // When the Drain is first created, it shortens the length of // the source vector to make sure no uninitialized or moved-from elements // are accessible at all if the Drain's destructor never gets to run. // // Drain will ptr::read out the values to remove. // When finished, remaining tail of the vec is copied back to cover // the hole, and the vector length is restored to the new length. // let len = self.len(); let start = match range.start_bound() { Included(&n) => n, Excluded(&n) => n + 1, Unbounded => 0, }; let end = match range.end_bound() { Included(&n) => n + 1, Excluded(&n) => n, Unbounded => len, }; assert!(start <= end); assert!(end <= len); unsafe { // set self.vec length's to start, to be safe in case Drain is leaked self.set_len(start); // Use the borrow in the IterMut to indicate borrowing behavior of the // whole Drain iterator (like &mut T). let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start); Drain { tail_start: end, tail_len: len - end, iter: range_slice.iter(), vec: NonNull::from(self), } } }
slice::名前空間のメソッドは触ったこと無いので未知。名前から察するに、生ポインタを取得しているっぽい。しかもメモリアドレス計算しているっぽい。
Drain構造体
#[stable(feature = "drain", since = "1.6.0")] pub struct Drain<'a, T: 'a> { /// Index of tail to preserve tail_start: usize, /// Length of tail tail_len: usize, /// Current remaining range to remove iter: slice::Iter<'a, T>, vec: NonNull<Vec<T>>, }
Drainへの実装
#[stable(feature = "collection_debug", since = "1.17.0")] impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_tuple("Drain") .field(&self.iter.as_slice()) .finish() } } impl<'a, T> Drain<'a, T> { /// Returns the remaining items of this iterator as a slice. /// /// # Examples /// /// ``` /// # #![feature(vec_drain_as_slice)] /// let mut vec = vec!['a', 'b', 'c']; /// let mut drain = vec.drain(..); /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']); /// let _ = drain.next().unwrap(); /// assert_eq!(drain.as_slice(), &['b', 'c']); /// ``` #[unstable(feature = "vec_drain_as_slice", reason = "recently added", issue = "58957")] pub fn as_slice(&self) -> &[T] { self.iter.as_slice() } } #[stable(feature = "drain", since = "1.6.0")] unsafe impl<T: Sync> Sync for Drain<'_, T> {} #[stable(feature = "drain", since = "1.6.0")] unsafe impl<T: Send> Send for Drain<'_, T> {} #[stable(feature = "drain", since = "1.6.0")] impl<T> Iterator for Drain<'_, T> { type Item = T; #[inline] fn next(&mut self) -> Option<T> { self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) }) } fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } } #[stable(feature = "drain", since = "1.6.0")] impl<T> DoubleEndedIterator for Drain<'_, T> { #[inline] fn next_back(&mut self) -> Option<T> { self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) }) } } #[stable(feature = "drain", since = "1.6.0")] impl<T> Drop for Drain<'_, T> { fn drop(&mut self) { // exhaust self first self.for_each(drop); if self.tail_len > 0 { unsafe { let source_vec = self.vec.as_mut(); // memmove back untouched tail, update to new length let start = source_vec.len(); let tail = self.tail_start; if tail != start { let src = source_vec.as_ptr().add(tail); let dst = source_vec.as_mut_ptr().add(start); ptr::copy(src, dst, self.tail_len); } source_vec.set_len(start + self.tail_len); } } } } #[stable(feature = "drain", since = "1.6.0")] impl<T> ExactSizeIterator for Drain<'_, T> { fn is_empty(&self) -> bool { self.iter.is_empty() } } #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for Drain<'_, T> {}
/// Private helper methods for `Splice::drop` impl<T> Drain<'_, T> { /// The range from `self.vec.len` to `self.tail_start` contains elements /// that have been moved out. /// Fill that range as much as possible with new elements from the `replace_with` iterator. /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.) unsafe fn fill<I: Iterator<Item=T>>(&mut self, replace_with: &mut I) -> bool { let vec = self.vec.as_mut(); let range_start = vec.len; let range_end = self.tail_start; let range_slice = slice::from_raw_parts_mut( vec.as_mut_ptr().add(range_start), range_end - range_start); for place in range_slice { if let Some(new_item) = replace_with.next() { ptr::write(place, new_item); vec.len += 1; } else { return false } } true } /// Makes room for inserting more elements before the tail. unsafe fn move_tail(&mut self, extra_capacity: usize) { let vec = self.vec.as_mut(); let used_capacity = self.tail_start + self.tail_len; vec.buf.reserve(used_capacity, extra_capacity); let new_tail_start = self.tail_start + extra_capacity; let src = vec.as_ptr().add(self.tail_start); let dst = vec.as_mut_ptr().add(new_tail_start); ptr::copy(src, dst, self.tail_len); self.tail_start = new_tail_start; } }
Dropを実装している。メモリ解放まで自前でやらねばならないの？ めちゃくちゃ大変そう。
もっと簡単に作れないの？
yeildはない
たとえばnext()の参照版は以下みたいに書けないか？
fn next_ref(&self) -> &Option<Box<Node<T>>> { let ptr = &self.head; while let Some(ref _n) = *ptr { yield return ptr; ptr = ptr.next; } yield return ptr; // *ptr = None }
でも、Rustには執筆時点でyieldキーワードの実装がない。C#ならあるのに……。
impl trait
Rustにはimpl traitとかいう謎の機能があるらしい。
// 奇数を列挙するイテレータ fn odds() -> impl Iterator<Item=i32> { (0..).map(|x| x * 2 + 1) } fn main() { println!("{:?}", odds().take(10).collect::<Vec<_>>()); }
$ rustc main.rs $ ./main [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
ポイントはodds関数の戻り値。impl Iterator<Item=i32>という表記になっている。詳細はURLを参照。とにかくイテレータを返せるみたい。
impl traitを使ってリストのイテレータを返せないか？
以下は色々おかしい。元リストの所有権はそのままである点はOK。でもクローンしたリストは参照ではなく値。into_iter()の戻り値の型が何なのかわからない。
fn iter(&self) -> &Option<Box<Node<T>>> { let list = self.clone(); list.into_iter() }
impl traitを使ってみようとした。が、イテレータってどうやって作るの？ あと、参照にしたいのだがinto_iter()は値が返される。
fn iter(&self) -> impl Iterator<Item=&Option<Box<Node<T>>>> { let list = self.clone(); list.into_iter() }
unsafeを使わずにclone()を使って何とかならないか？
fn iter(&self) -> &Option<Box<Node<T>>> { let list = self.clone(); let ptrs = vec::new(); for item in list { ptrs.push(&item); } ptrs // list領域の参照を返す。でもlist領域はiterメソッド終了時にdropするのでダングリングポインタになってしまう！ }
クローンしてもすぐ死ぬ。そいつの参照を返したらダングリングポインタになってしまう。
なら、素直にnextのポインタを取ればいいのでは？
fn iter(&self) -> Vec<&Option<Box<Node<T>>>> { let mut ptr = &self.head; let mut ptrs:Vec<&Option<Box<Node<T>>>> = Vec::new(); while let Some(ref _n) = *ptr { ptrs.push(ptr); ptr = &ptr.as_ref().unwrap().next; } ptrs }
コンパイルできる。でも、Vec型であって、イテレータじゃない。list.iter().iter()としないとイテレータは取得できないことになる。Vec.iter()でイテレータが取得できるのだから。
じゃあVecのiter()実装はどうなっているの？ と思ってコードをiterで検索したのだが、メソッド定義されているところが見つけられなかった。into_iterならあったのだが。Vec型にはiterメソッドがあるはずなのに、どこに実装されているの？
pub fn iter(&self) -> Iter<T>
pub struct Iter<'a, T> where T: 'a + 'a, { /* fields omitted */ }
Iterator.by_ref()を使ってみたが、2回目の走査ができなかった。ポインタを先頭に戻せないのだろうか？
let mut list: LinkedList<i32> = LinkedList::new(); list.push(0); list.push(1); list.push(2); let mut iter = list.into_iter(); for (i, actual) in iter.by_ref().enumerate() { assert_eq!(actual, expecteds[i]); println!("{} {}", actual, expecteds[i]); } for (i, actual) in iter.by_ref().enumerate() { assert_eq!(actual, expecteds[i]); println!("{} {}", actual, expecteds[i]); }
$ cargo test -- --nocapture ... 0 0 1 1 2 2 ...
期待値は、上記の出力がもう一度現れることだった。つまり、by_ref()しても期待通りにならない。
上記の直後、リストの内容が保存されているかを確認してみようと試みた。が、into_iter()で所有権がムーブされているせいでassert_eq!できなかった。
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, prev: None })) , prev: None })) , prev: None })));
error[E0382]: borrow of moved value: `list` --> src/lib.rs:615:9 | 602 | let mut list: LinkedList<i32> = LinkedList::new(); | -------- move occurs because `list` has type `LinkedList<i32>`, which does not implement the `Copy` trait ... 606 | let mut iter = list.into_iter(); | ---- value moved here ... 615 | / assert_eq!(list.head, Some(Box::new(Node { item: 0, next: 616 | | Some(Box::new(Node { item: 1, next: 617 | | Some(Box::new(Node { item: 2, next: None, prev: None })) 618 | | , prev: None })) 619 | | , prev: None }))); | |__________________________^ value borrowed here after move | = note: this error originates in a macro outside of the current crate (in Nightly builds, run with -Z external-macro-backtrace for more info)
やはりunsafeにiter()を書くしかないのか。Vecのコードがむずかしくて読めない。こんな状態では書ける気がしない。
所感
ここから先はunsafe領域。なんてこった。難易度がどんどん跳ね上がっていきやがる。勉強しはじめたばかりでそれはちょっと早い気がする。でも、そうでないとやりたいことができないというジレンマ。参照を返すイテレータくらいあってもいいと思うのだが。本当にないの？
やりたいことに一番近づけたのは以下のコード。でもこれ、イテレータじゃない。しかも元々のリストとまったく同じ値を別メモリで複製するため、メモリの無駄づかい。
fn iter(&self) -> Vec<&Option<Box<Node<T>>>> { let mut ptr = &self.head; let mut ptrs:Vec<&Option<Box<Node<T>>>> = Vec::new(); while let Some(ref _n) = *ptr { ptrs.push(ptr); ptr = &ptr.as_ref().unwrap().next; } ptrs }
現在位置を示すポインタ変数をLinkedListのフィールドに保持していればいけそうな気もするが。でも、参照イテレータを使わないときは完全にメモリの無駄。どう実装するものなんだろう。
対象環境
- 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
