`impl Trait` in Traits

[cramertj]

Edit: A draft RFC for this feature was written. Linking here for visibility.

This is really two separate but related features: impl Trait in trait definitions, and impl Trait in trait implementations:

// In definitions:
trait Foo {
    fn bar() -> impl Debug;
}

// In declarations:
impl Foo for Blah {
    fn bar() -> impl Debug;
}

A proposal on this front should address the following issues:

• How to place bounds on the return type of an impl Trait-returning impl.
• How to use a trait function returning impl Trait in a trait object.

@nikomatsakis suggested the possibility of inferring associated types based on the definitions of other items.

[cramertj]

I spoke with @aturon about this, and they're really emphasizing this part of the proposal. In the interest of making progress on this, I'd like to start exploring what exactly each of these features should do.

impl Trait in definitions

I think this is the more confusing of the two cases (definitions vs. implementations) because there are two different but reasonable interpretations of what this should mean.

trait Foo {
    fn bar() -> impl Debug { "" }
}

// Could be sugar for Interpretation A: 
trait Foo {
    type bar_return: Debug;
    fn bar() -> bar_return { "" }
}

// OR it could just mean Interpretation B:
trait Foo {
    fn bar() -> &'static str { "" } // (where `&'static str` is hidden from the caller)
}

Let's try and write part of the Iterator trait using each of these interpretations. For now, let's ignore the conditional bounds issue (tracked separately).

trait Iterator {
    // trait implementer implements these:
    type Item;
    fn next(&mut self) -> Option<Self:Item>;
    
    // We implement a bunch of these:
    fn map<B>(self, f: impl FnMut(Self::Item) -> B) -> impl Iterator<Item=B> { ... }
    fn filter(self, predicate: impl FnMut(&Self::Item) -> bool) -> impl Iterator<Item=Self::Item> { ... }
    ...
}

Using Interpretation A, we wind up with a bunch of extra associated types (map_return, filter_return, etc. etc.). This allows Iterator implementations to specify their own return types for each of these methods, so long as they conform to the specified bounds. However, it makes trait objects like Box<Iterator<Item=Foo>> basically unusable. We'd have to specify all of the extra associated types, or otherwise we wouldn't know the size of the result from any of the Iterator combinators.

Using Interpretation B, we get essentially the same Iterator trait we have today-- only one associated type (Self::Item), with all of the combinators returning some concrete type. Unfortunately, this makes it impossible for the trait implementer to override any of the impl Trait-returning methods, since they won't be able to match the exact return type. The exact type returned by the combinators is hidden, which could greatly improve documentation and error messages (since you don't have to visually scan through lengthy, complicated types to understand what traits they implement). It also allows Iterator to hide its implementation details, allowing for changes to the type returned by each of these combinators. It allows Iterator methods to return lengthy or unnameable types, such as closures.

Personally, I lean towards the second interpretation, since it makes "impl Trait in traits" usable with trait objects. However, not being able to override / provide your own implementations of these traits is a serious downside. It's also unclear how this interacts with methods with no default implementation:

trait Foo {
    fn bar() -> impl Debug; // What the heck does this mean under Interpretation B?
}

One option would be to use Interpretation B for trait methods with a body, and Interpretation A for trait methods without a body, but this seems like it would greatly violate the principle of least surprise-- we'd surely be constantly fielding questions about why adding a default implementation of a method broke all existing implementations of a trait.

What do you think?

[nikomatsakis]

Interesting points. I had never considered "interpretation B" -- it still seems strikingly less useful to me, but I agree that Iterator makes a good case for where you do want exactly that (the downside of not being able to override those methods in the trait is real, but strikes me as somewhat minimal; after all, when the types are fully specified (as today) there isn't much you can productively do in the implementation anyway, since you still have to return the same kind of thing in the end, and that type defines all the behavior when the iteration takes place).

Basically interpretation B is tailored for "combinator"-style traits (iterator, parsing combinators, that sort of thing), which are certainly common.

[nikomatsakis]

On a related note, I have mixed feelings about the pattern where all the combinator methods are defined in the trait itself, to be honest. I think the main reason we do it this way is because it's sort of "seems" simple, and it looks good in rustdoc, but it has some surprising effects:

Implementing types have some freedom to override, but not much. If I have some better way of implementing map, I can't really do anything about it. (On the other hand, I could implement e.g. all() in a better way, so sometimes it's meaningful.)

It doesn't play that great with objects. To make the trait object safe, we had to add various where Self: Sized annotations on those default methods, because often they would require that Self: Sized. The thing is that, really, you want the iterator object to be a Box<Iterator>, or &mut Iterator, so that you can wrap it up in other, derived iterators. To handle this, we have e.g. an implementation of Iterator for Box<Iterator>. But if you rely on that, then when you call map() you won't get the "overridden" variant from your trait object: you get the generic one, with the only virtual calls being the call to next().

Originally I sort of preferred the idea of having the map() etc methods be defined in some way that they are not really derivable. i.e., if we had final functions, maybe something like that. This would more express their intent. It would also eliminate this ambiguity.

But, water under the bridge, probably, and I don't really want to add final functions per se. =) Anyway, I guess it's just something to think about.

[withoutboats]

A major motivation for this is making #[async] functions in traits work correctly. For example, cargonauts deeply needs this.

However, its often the case that we do care about things like S: Service, S::Future: Send + 'static.

[nikomatsakis]

If you ignore trait objects, then there isn't much of a reason to adopt the first interpretation -- where impl Trait desugars into an associated type on the trait -- is strictly more general, right?

(Really it would desugar into an associated type that is tied to the particular implementation in a way that you can't normally do. In other words, fn foo() -> impl Bar in a trait kind of desugars to this imaginary syntax:

trait Foo {
    // in place of `fn foo() -> impl Bar { ... }`
    type FooRet: Bar;
    fn foo() -> Self::FooRet;
}

default impt<T: Foo> Foo<T> {
    default {
        type FooRet = XXX;
        fn foo(&self) -> XXX { ... }
    }
}

Here the "inner" default allows the fn foo() definition to "see" the value of Self::FooRet, which would otherwise be opaque. This implies that these two members cannot be overridden independently -- if one is overridden, the other must be.)

It's sort of interesting because, in the case of the Iterator trait at least, most, if not all, of those methods can't be invoked on iterator objects anyway (because of where Self: Sized). We might allow the associated types for their return values to go unspecified as a result. Similarly, we might use a defaulting scheme so that, if you don't say, we assume the value is the default given in the trait object.

[aturon]

I wrote up my thoughts on an early draft RFC on this topic here.

[warlord500]

I personally don't like the idea of having impl trait in trait prototype. I don't like it either in argument position. but for some reason this gets added to stable, I can more use cases for interpretation B.
where there exists one definition of function in trait prototype used for combinators