以下の内容はhttps://ytyaru.hatenablog.com/entry/2020/11/23/000000より取得しました。

Rust自習（iter、iter_mut実装方法）

Rust

　やっと見つけた。

成果物

参考

　コードを読むと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のメソッドだったのか？　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> {
  1. Iteratorはstd::iter::Iteratorのことである（標準モジュールであって自作でない）
  2. 自作のIter, IterMutにstd::iter::Iteratorを実装する
  3. 2にて、Iter, IterMutを返すメソッドiter(), iter_mut()はイテレータとなる
  4. 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の参照を返す。

対象環境

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux

前回まで



以上の内容はhttps://ytyaru.hatenablog.com/entry/2020/11/23/000000より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14