Rustの学習を進めています。前回に引き続き、イテレーターの章で気になった結果を発見しました。vec型の値に対してinto_iter関数を実行した場合にはvec型に定義された構造体vec::into_iter::IntoIterが返るのですが、iter関数を実行すると...slice型に定義された構造体slice::iter::Iterが返るのです。
fn type_of<T>(_: T) -> String{ let a = std::any::type_name::<T>(); return a.to_string(); } fn main () { println!("type: {}", type_of(vec![1,2,3])); println!("type: {}", type_of(vec![1,2,3].into_iter())); println!("type: {}", type_of(vec![1,2,3].iter())); } // type: alloc::vec::Vec<i32> // type: alloc::vec::into_iter::IntoIter<i32> // type: core::slice::iter::Iter<i32>
自分のような素人発想では「iter関数を実行した時もvec::Iterが返ればいいんじゃないの？」と思ってしまいます。しかしながら、結果は先ほどの通り。一体なぜなのでしょうか。
結論としては、slice型とvec型で同じようなデータを保持しており、Iter構造体を使い回すことが出来るのではないかという判断に至りましたが、決定的な情報がなかったため、1つの説という視点でご覧ください。
Iter構造体とIteratorトレイト
Iter構造体は以下のように3つのフィールドを持ちます。ptrはおそらくpointerの略称でしょう。
pub struct Iter<'a, T: 'a> { ptr: NonNull<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: PhantomData<&'a T>, }
rust/iter.rs at master · rust-lang/rust · GitHub
それぞれのフィールドがどういう意図を持って用意されているものかは現時点では正確な判別は不能ですが、イテレーションの処理をするのに必要な情報だということは推測出来ます。
次に、vec型のiter関数が構造体slice::iter::Iterを返しているコードを探してみます。fn iterでコードを検索してみても、それっぽい定義は見つかりません。…ということで、次はIteratorトレイトが構造体slice::iter::Iterに対して実装されているかどうか検索してみます。
rust/iterator.rs at master · rust-lang/rust · GitHub
こちらは明示的にIterator for Iterと定義された箇所はありませんでしたが、どうもマクロを利用して構造体Iterに対してIteratorトレイトを実装しているようです。
impl<'a, T> Iterator for $name<'a, T> { type Item = $elem; // 長いので省略 }
rust/macros.rs at master · rust-lang/rust · GitHub
マクロの呼び出し
iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, { fn is_sorted_by<F>(self, mut compare: F) -> bool where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>, { self.as_slice().windows(2).all(|w| { compare(&&w[0], &&w[1]).map(|o| o != Ordering::Greater).unwrap_or(false) }) } }}
rust/iter.rs at master · rust-lang/rust · GitHub
これで構造体slice::iter::IterがIteratorトレイトを実装していることが分かりました。また、マクロが定義されたファイルにはnext関数の定義もあったので、次はこちらを見てみます。
fn next(&mut self) -> Option<$elem> { // 長いので省略 unsafe { assume(!self.ptr.as_ptr().is_null()); if !<T>::IS_ZST { assume(!self.end.is_null()); } if is_empty!(self) { None } else { Some(next_unchecked!(self)) } } }
rust/macros.rs at master · rust-lang/rust · GitHub
今回の問題の調査として、この関数を深掘りしたのですが、かなり情報量が多くなるため、今回は理解に必要な部分的な情報のみをピックアップします。このnext関数と関数内で呼ばれる処理の多くはself(Iter構造体)のptrフィールドを使って様々な処理が実装されています。つまりptrの情報がフィールドに記録されていれば、Iter構造体は生成可能で、イテレーションの処理が行えるのではないかと考えられます。そこで、slice型とvec型が持つ情報を見てみます。
※厳密にはptrとendと_markerの3つ
slice型とvec型
この2つの型は微妙に異なります。slice型はRustではDST(Dynamically Sized Types)として定義されており、コンパイル時にサイズが分からない型です。それに対してvec型はなんとDSTではありません。またarray型も同様にDSTではなくコンパイル時にサイズが分かっている型です。
「え、でもvec型って可変長で値の追加が出来るんじゃ...?」と思いますが、vec型は要素の格納をヒープ領域へ行います。array型はスタック領域に連続的に要素を確保していますが、slice型は状態によって、スタックかヒープを選択するそうです。
| 名前 | DSTかどうか | 可変長かどうか | 要素の確保領域 |
|---|---|---|---|
| array | いいえ | いいえ | スタック |
| slice | はい | いいえ | スタックかヒープ |
| vector | いいえ | はい | ヒープ |
その上で、slice型とvector型が持つ情報を見てみます。まず、slice型はドキュメントの情報から読み取るに2つの値を持ちます。
- pointer to the data
- length
a slice is a two-word object, the first word is a pointer to the data, and the second word is the length of the slice.
Arrays and Slices - Rust By Example
そしてvec型は3つの値を持ちます。
- pointer to the data
- length
- capacity
ptr len capacity
+--------+--------+--------+
| 0x0123 | 2 | 4 |
+--------+--------+--------+
|
v
Heap +--------+--------+--------+--------+
| 'a' | 'b' | uninit | uninit |
+--------+--------+--------+--------+
結論
決定的な情報がなかったので、僕の個人的な結論にはなりますが、slice型とvec型はどちらもptrフィールドを持っており、Iter構造体を生成可能です。ここで、vec型とslice型で別のIter構造体を定義しなかったのは、slice型のIter構造体でvec型でも同様にイテレーションが出来るため、共通化をしたかったのではないかという判断に至りました。
少し自分の主観が入りましたが、調査の結果、上記を一旦の結論としました。 もし、詳しい情報をご存知の方がいましたら、せび教えていただきたいです。
