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

user_456370 0
Viewed 552

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)?

rust traits
2 Answers

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

impl<T> FromIterator 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.

user_44988310

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.

user_2796270
Related