Feature idea: Generic trait methods on trait objects (using the default implementation)

Context

Thinking about the Iterator trait recently, and what kind of unsized types could implement it, there’s really two kinds.

  • Trait objects for Iterator or some trait that has an Iterator supertrait bound. These implement Iterator automatically
  • Other unsized types, e.g. be other trait objects, or generic types Foo<T: ?Sized> with a T-typed field which are unsized in case that T: !Sized. These types need to come with a manual Iterator implementation.

The latter case could be something like TupleStruct<T: ?Sized>(Foo, T). Imagine Foo is an iterator and I want a delegating iterator implementation for TupleStruct<T> even if T: !Sized. This immediately has the effect that methods like try_fold

fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
where
    Self: Sized,
    F: FnMut(B, Self::Item) -> R,
    R: Try<Output = B>,
{
    // … default implementation
}

cannot be implemented as delegating from TupleStruct<T> to the underlying Foo iterator, with potential performance implications. (Please ignore the fact that Try isn’t stable yet. And in any case, the same argument could be done for e.g. the find method, but try_fold will eventually be the more important Iterator method everyone wants to override for maximal performance benefits.)

Now, the only reason for the Self: Sized bound in this method is that Iterator wouldn’t be object safe without it. The reason why Iterator wouldn’t be object safe is that there are generic parameters (B, F, R), so that the trait object couldn’t preserve the implementation of the underlying type, because you cannot dynamically do a generic function call.

However, you typically can call try_fold on an Iterator trait object. When you’re calling try_fold on a Box<dyn Iterator<Item=…>> or a &mut dyn Iterator<Item=…>>, then you’re calling try_fold for the Iterator implementation of Box<I> or &mut I. This uses the default implementation of try_fold, implemented in terms of next.


So that’s the situation: We have a generic trait method which would make the trait non-object safe (if it weren’t for Self: Sized) because the trait object couldn’t implement the method using the vtable, however it could implement it with the provided default implementation instead. But that’s a bad thing in general, because for many traits you wouldn’t necessarily expect to hit the traitʼs default implementation of a method (which might behave completely different from the actual implementation) when calling a method on a trait object.

But the trait Iterator is implemented using this default implementation on &mut I and Box<I> (where I: Iterator), and the trait requires that (non-buggy) implementors don’t change the behavior of try_fold from the default in ways that aren’t just a performance optimization over the default implementation. So as long as traits like Iterator could explicitly opt-in to using the default implementations of generic methods for trait objects, there wouldnʼt be any of the unexpected behavior described above.

Feature Idea

Now the feature idea: Add a way to indicate that trait objects should use the default implementation of a method. E.g. this could be used for Iterator, changing the signature of try_fold to

#[trait_object_uses_default_implementation]
fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
where
    F: FnMut(B, Self::Item) -> R,
    R: Try<Output = B>,
{
    // … default implementation
}

with the effect that implementors of Iterator for !Sized or ?Sized types can then override try_fold. Final syntax to be determined. This attribute would only be allowed without warning or error on a method

  • with default implementation
  • that violates object safety conditions on a trait,
  • and when that trait without the method would be object safe.

The attribute will have the effect that object safety is preserved and the trait object uses the default implementation. AFAICT there need be no further limitations on the type signature of the method. E.g. things like an owned fn …(self, …) argument or -> Self return type for a method with default implementation are prohibited in an object safe trait anyways (because of the missing : Sized constraint).


I might want to make an RFC out of this, feedback on the idea is much appreciated.

8 Likes

I feel there's some overlap with default impl here. E.g. a future possibility of how to implement this:

// Really you want something more generic due to supertraits, e.g.
// default impl<T, U> Iterator for T where T: dyn Iterator<Item=U>
default impl<U> Iterator for dyn Iterator<Item=U> {
    final fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
//  ^^^^^ Made up ability to have final `fn` in a `default impl`
//  (i.e. a way to have partial `impl`s with final `fn`s)
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    { /* ... */ }
}

And/or for DRY reasons:

pub trait Iterator {
    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    final where
        for<U> Self: dyn Iterator<Item=U>,
    { /* ... */ }
}

(The downsides of using Sized to mean !dyn is certainly showing itself here...)

1 Like