rustのIteratorの実装

関連するトレイト

Iterator

libcore/iter/traits/itetarot.rs

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    ...
}

• イテレータの関数のためのトレイト
• next()さえ実装すれば，あとはデフォルト定義が存在

IntoIterator

libcore/iter/traits/collect.rs

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item=Self::Item>;
    fn into_iter(self) -> Self::IntoIter;
}

impl<I: Iterator> IntoIterator for I {
    type Item = I::Item;
    type IntoIter = I;

    fn into_iter(self) -> I {
        self
    }
}

• IntoIteratorはイテレータを得るためのトレイト
• for _ in x としたとき，xに対してinto_iter()が呼ばれる
• IteratorにはIntoIteratorが実装されている (単純に自分自身を返すだけ)

Slice ([T])

iter(), iter_mut()

libcore/slice/mod.rs

impl<T> [T] {
    ...
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn iter(&self) -> Iter<T> {
        unsafe {
            let ptr = self.as_ptr();
            assume(!ptr.is_null());

            let end = if mem::size_of::<T>() == 0 {
                (ptr as *const u8).wrapping_add(self.len()) as *const T
            } else {
                ptr.add(self.len())
            };

            Iter {
                ptr,
                end,
                _marker: marker::PhantomData
            }
        }
    }
    ...
}

• sliceのiter()はIter<T>を返す
  • iter_mut()も同様
• Iter<T>の定義は以下の通り

libcore/slice/mod.rs

pub struct Iter<'a, T: 'a> {
    ptr: *const T,
    end: *const T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
                   // ptr == end is a quick test for the Iterator being empty, that works
                   // for both ZST and non-ZST.
    _marker: marker::PhantomData<&'a T>,
}

macro_rules! iterator {
    ...
        impl<'a, T> Iterator for $name<'a, T> {
            type Item = $elem;

            #[inline]
            fn next(&mut self) -> Option<$elem> {
                // could be implemented with slices, but this avoids bounds checks
                unsafe {
                    assume(!self.ptr.is_null());
                    if mem::size_of::<T>() != 0 {
                        assume(!self.end.is_null());
                    }
                    if is_empty!(self) {
                        None
                    } else {
                        Some(& $( $mut_ )* *self.post_inc_start(1))
                    }
                }
            }
        ...
        }
    ...
}

iterator!{struct Iter -> *const T, &'a T, const, {/* no mut */}, {...

• Iter<T>に対してIteratorが実装されている
  • 各要素の参照を返す
• iter()とiter_mut()で実装を共通化するためマクロで定義されている

into_iter()

• iter(), iter_mut()を呼ぶ形で&'a [T], &'a mut [T]に実装
  • let x = [1,2,3];のとき，for loopにおいては，for _ in x.iter()もfor _ in &xも同じ意味
    • 前者の場合, x.iter()はIteratorを実装するIter<T>を返し，それに対してIntoIteration::into_iter()が呼ばれる
      • イテレータ自身はIntoIterationを実装するので問題ない
    • 後者の場合は&[T]に対してIntoIteration::into_iter()が呼ばれる．
  • [T]に対してはinto_iter()の実装なし (そもそもsliceで実際に使えるのはshared (&[T]) かmutable (&mut [T]) の形のみ)

libcore/slice/mod.rs

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a [T] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut [T] {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

Array ([T; N])

iter(), iter_mut()

• coerceによってsliceのiter(), iter_mut()が呼ばれる

into_iter()

• sliceと同様に，iter(), iter_mut()を呼ぶ形で&'a [T; N], &'a mut [T; N]に実装
  • [T; N]に対する実装はない

libcore/array.rs

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a [T; $N] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut [T; $N] {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

Vec (Vec<T>)

iter(), iter_mut()

• deref coerceによってsliceのiter(), iter_mut()が呼ばれる

into_iter()

src/liballoc/vec.rs

impl<T> IntoIterator for Vec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    #[inline]
    fn into_iter(mut self) -> IntoIter<T> {
        unsafe {
            let begin = self.as_mut_ptr();
            assume(!begin.is_null());
            let end = if mem::size_of::<T>() == 0 {
                arith_offset(begin as *const i8, self.len() as isize) as *const T
            } else {
                begin.add(self.len()) as *const T
            };
            let cap = self.buf.cap();
            mem::forget(self);
            IntoIter {
                buf: NonNull::new_unchecked(begin),
                phantom: PhantomData,
                cap,
                ptr: begin,
                end,
            }
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a Vec<T> {
    type Item = &'a T;
    type IntoIter = slice::Iter<'a, T>;

    fn into_iter(self) -> slice::Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut Vec<T> {
    type Item = &'a mut T;
    type IntoIter = slice::IterMut<'a, T>;

    fn into_iter(self) -> slice::IterMut<'a, T> {
        self.iter_mut()
    }
}

• &'a Vec<T>, &'a mut Vec<T>の場合はiter(), iter_mut()を呼ぶ
• Vec<T>の場合はIntoIter<T>を返す
  • IntoIter<T>は以下の様に定義
  • これにより，Vec<T>では要素そのものをに対してイテレーションすることが可能 (vec自身は消費される)

src/liballoc/vec.rs

#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<T> {
    buf: NonNull<T>,
    phantom: PhantomData<T>,
    cap: usize,
    ptr: *const T,
    end: *const T,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        unsafe {
            if self.ptr as *const _ == self.end {
                None
            } else {
                if mem::size_of::<T>() == 0 {
                    // purposefully don't use 'ptr.offset' because for
                    // vectors with 0-size elements this would return the
                    // same pointer.
                    self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;

                    // Make up a value of this ZST.
                    Some(mem::zeroed())
                } else {
                    let old = self.ptr;
                    self.ptr = self.ptr.offset(1);

                    Some(ptr::read(old))
                }
            }
        }
    }
    ...
}

Arrayに[T; N]のIntoIteratorが実装されていない理由

• 前述の通り，rustではArrayの要素そのものをiterationすることが不可能
  • 一方で，Vecであればそれは可能
• ドキュメントには"There is no way to move elements out of an array."と書いてある
  • しかしながら，原理的にはmove可能な気がする
• 実装されていない理由
  • redditでの議論 "Iterating over array?" https://www.reddit.com/r/rust/comments/7lhhj8/iterating_over_array/
    • iteration中にpanicしたときどう対処するかが問題
    • 現状rustはconst generics(定数のパラメタライズ)がない(ので実装が冗長になりがち)
    • const generics待ち? https://github.com/rust-lang/rust/pull/32871
    • Vec<T>の場合は，panicした場合メモリリークを許容する形で実装

まとめ

• trait/struct
  • Iterationトレイト
    • next()を実装することでイテレータとして利用できるようになる
  • IntoIteratorトレイト
    • イテレータが欲しい時にtrait boundとして利用する
    • for loopはIntoIteratorが実装されているものを受け取るようになっている
  • Iter
    • sliceの&T, &mut Tに対するIterationのために存在
  • IntoIter
    • vecのTに対するIterationのために存在
• 一般にstdでのcollectionでは
  • iter()で&Tに対してイテレーション
  • iter_mut()で&mut Tに対してイテレーション
  • into_iter()でTに対してイテレーション (要素はmoveされる)
• 現状Arrayに関してはTに対してイテレーションはできない