CODEWITHSUNDEEP
rusttraits
Nyi Nyi
Nyi Nyi

Reputation: 788

How does Rust understand to call the appropriate implementation of from_iter using only FromIterator::from_iter?

An iterator can be transformed to a collection using the Iterator trait's collect method if the collection implements FromIterator.

let vec = (0..10).collect::<Vec<_>>();
let devec = (0..10).collect::<VecDeque<_>>();

Vec and VecDeque implement FromIterator trait.

The implementation of Iterator::collect method is:

fn collect<B: FromIterator<Self::Item>>(self) -> B
where
    Self: Sized,
{
    FromIterator::from_iter(self)
}

How does Rust understand to call from_iter method of Vec or VecDeque from FromIterator::from_iter(self)?

Upvotes: 3

Views: 741

Answers (2)

Boiethios
Boiethios

Reputation: 42829

When the FromIterator trait has an implementor, it has the form:

impl<T> FromIterator<T> for Vec<T> {
    fn from_iter<I>(iter: I) -> Vec<T> { /* ... */ }
}

It returns the concrete type Self; that is the generic parameter B in the collect code.

When you type collect::<Vec<_>>(), you say that B is Vec<_> and therefore, that Vec<_>::from_iter() must be called.

The implementation of collect could have been written: <B as FromIterator>::from_iter(self), but it is more verbose.

Upvotes: 8

Sven Marnach
Sven Marnach

Reputation: 602115

Let's look at the definition of the FromIterator trait:

pub trait FromIterator<A>: Sized {
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self;
}

From how FromIterator::from_iter() is used in the implementation of the collect() method, Rust knows that the call to FromIterator::from_iter() takes the iterator self as parameter, and returns an object of type B. This information is matched against the definition of the from_iter() method, so Rust can conclude that the Self type of the FromIterator trait implementation must be B, and that the type A must be the item type of the iterator. The Self type of the FromIterator trait is precisely the type Rust needs to call from_iter() for.

The details of how type inference works are complex. Rust uses a variant of the Hindley-Milner type inference algorithm. You can find some further information in this document from the rustc guide.

Roughly, Rust uses all information it has about unknown types as constraints and iteratively refines its knowledge about generic types, until only a single type for each unknown type remains, or some type remains ambiguous. In the former case, type inference was successful and all types have been inferred, and in the latter case, Rust will throw an error stating that it needs further type annotations.

Upvotes: 3

Related Questions