Why explicitly non-dispatchable methods in Iterator are dispatchable?

user_7607923 0
Viewed 120

Rust reference object-safety confused me for a while, and says:

Explicitly non-dispatchable functions require:

Have a where Self: Sized bound (receiver type of Self (i.e. self) implies this).

But I found code::iter::Iterator has dozen of methods are declared as explicitly non-dispatchable functions, one of them below:

pub trait Iterator {
    ...
    fn count(self) -> usize
    where
        Self: Sized,
    {
        self.fold(
            0,
            #[rustc_inherit_overflow_checks]
            |count, _| count + 1,
        )
    }
    ...
}

However, all of them are dispatchable by trait-object at rust-playground:

fn main() {
    let it: &mut dyn Iterator<Item = u32> = &mut [1, 2, 3].into_iter();
    assert_eq!(3, it.count()); // ok
}

That is good, I start try to implements a worked example, but it can not be dispatched at rust-playground, and report compiler error: "the dispatch method cannot be invoked on a trait object" that is expected:

fn main() {
    pub trait Sup {
        fn dispatch(self) -> String
        where
            Self: Sized,
        {
            "sup".to_string()
        }
    }

    struct Sub;
    impl Sup for Sub {
        fn dispatch(self) -> String {
            "sub".to_string()
        }
    }

    let it: &mut dyn Sup = &mut Sub;
    assert_eq!("trait", it.dispatch());
}

Why explicitly non-dispatchable methods in code::iter::Iterator are dispatchable? Is there any magic which I didn't found?

rust
1 Answers

The reason is simple, if we think of this: what type we're invoking the method count on?

Is it dyn Iterator<Item = u32>? Let's check:

assert_eq!(3, <dyn Iterator<Item = u32>>::count(it));

Nope, there are two errors:

error[E0308]: mismatched types
 --> src/main.rs:3:53
  |
3 |     assert_eq!(3, <dyn Iterator<Item = u32>>::count(it));
  |                                                     ^^ expected trait object `dyn Iterator`, found mutable reference
  |
  = note:   expected trait object `dyn Iterator<Item = u32>`
          found mutable reference `&mut dyn Iterator<Item = u32>`

error[E0277]: the size for values of type `dyn Iterator<Item = u32>` cannot be known at compilation time
   --> src/main.rs:3:53
    |
3   |     assert_eq!(3, <dyn Iterator<Item = u32>>::count(it));
    |                   --------------------------------- ^^ doesn't have a size known at compile-time
    |                   |
    |                   required by a bound introduced by this call
    |
    = help: the trait `Sized` is not implemented for `dyn Iterator<Item = u32>`
note: required by a bound in `count`

OK, well... is it &mut dyn Iterator, then?

assert_eq!(3, <&mut dyn Iterator<Item = u32>>::count(it));

Now it compiles. It's understandable that the second error goes away - &mut T is always Sized. But why do the &mut dyn Iterator has access to the method of Iterator?

The answer is in the documentation. First, dyn Iterator obviously implements Iterator - that's true for any trait. Second, there's implementation of Iterator for any &mut I, where I: Iterator + ?Sized - which our dyn Iterator satisfies.

Now, one may ask - what code is executed when we use this implementation? After all, count requires consuming self, so calling it on reference can't delegate to the dyn Iterator - otherwise we'd be back to square one, dispatching non-dispatchable.

Here, the answer lies in the structure of the Iterator trait. As one can see, it has only a single required method, namely next, which takes &mut self; all other methods are provided, that is, they have some default implementations using next - for example, here's it for count:

fn count(self) -> usize
where
    Self: Sized,
{
    self.fold(
        0,
        #[rustc_inherit_overflow_checks]
        |count, _| count + 1,
    )
}

where fold, in turn, is the following:

fn fold<B, F>(mut self, init: B, mut f: F) -> B
where
    Self: Sized,
    F: FnMut(B, Self::Item) -> B,
{
    let mut accum = init;
    while let Some(x) = self.next() {
        accum = f(accum, x);
    }
    accum
}

As you can see, knowing just the next, compiler can derive fold and then count.

Now, back to our &mut dyn Iterators. Let's check how, exactly, this implementation looks like; it appears to be quite simple:

#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator + ?Sized> Iterator for &mut I {
    type Item = I::Item;
    #[inline]
    fn next(&mut self) -> Option<I::Item> {
        (**self).next()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        (**self).size_hint()
    }
    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
        (**self).advance_by(n)
    }
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        (**self).nth(n)
    }
}

You can see that the &self and &mut self methods, i.e. the ones which can be called on the trait object, are forwarded by the reference to the inner value and dispatched dynamically.

The self methods, i.e. the ones which cannot use the trait object, are dispached statically using their default implementation, which consume the reference and pass it, eventually, into one of these - non-consuming, dynamically-dispatched - methods.

user_30034010
Related