Question about impl Trait in return position

help
#1

I have some code like this (the real code is more complex but I’ve created a simplified example):

use std::sync::Arc;

#[derive(Clone)]
struct Baz; 

struct Foo {
    bazzes: Vec<Arc<Baz>>
}

impl Foo {
    fn inner_zero(&self) -> impl Iterator<Item = Arc<Baz>> {
        // return some concrete iterator X
    }

    fn inner_one(&self) -> impl Iterator<Item = Arc<Baz>> {
        // return some concrete iterator Y
    }

    fn iter(&self)  -> impl Iterator<Item = Arc<Baz>> {
        if some_condition {
            self.inner_one()
        } else {
            self.inner_two()
        }
    }
}

The lifetimes and return types should be compatible even though the concrete iterator types are different.
As I understand impl Trait in return position is that it’s simply the promise “some type that implements Trait”. So why does the compiler complain about this?

#2

Emphasis mine. “some type”. As in singular. It expects exactly one type to be returned, not two that implement the same trait.

If you want dispatch, you need to use dispatch, be that Box<Iterator<..>> or an enum like Either.

#3

In return position it doesn’t indicate, “Some type that implements this trait”, rather, it indicates, “Some SPECIFIC CONCRETE type that implements this trait”. In other words, you are not naming the type specifically, but, it is some specific type that is being returned. In your case inner_zero and inner_one are not guaranteed to return the same specific type, so they both can’t be the return type of iter because then iter would not have a specific return type. If you want to return just something that is the given trait, then, you need to return a Box<dyn Trait> instead (dynamic dispatch) instead of impl Trait (static dispatch).

Put another way, impl Trait in return position is “Existential”, whereas Box<dyn Trait> is “Universal”. (see Wikipedia for defs of these terms).

#4

@DanielKeep @gbutler69 yeah I was afraid of that.
The problem is that I am trying to reduce heap allocation, not increase it.
The code in the example can run in the body of several nested several loops, so allocation quickly becomes really expensive.

So I guess I’ll have to find another solution, thanks anyway :slight_smile:

#5

Hence why I mentioned either.

1 Like
#6

The either crate looks interesting, so I’m going to try that and see what happens.

#7

For iterators specifically, just accepting a callback (i.e, “internal iteration”) or even just an buf: &mut Vec<Item> often works well.

And for some cases, like iterating over a tree, you might need some form of heap allocation for external iterators, while internal iterators can use stack space via recursion.

2 Likes
#8

Internal iteration is another good idea to explore, but I’ll only do that if the either crate solution turns out not to work out.

At the moment it seems to do the job however, and it even allowed me to remove a couple of hair-raising .cloned() calls on the iterators.

So now the code roughly looks like this:

use std::sync::Arc;

#[derive(Clone)]
struct Baz; 

struct Foo {
    bazzes: Vec<Arc<Baz>>
}

impl Foo {
    fn inner_zero(&self) -> impl Iterator<Item = &Arc<Baz>> {
        // return some concrete iterator X
    }

    fn inner_one(&self) -> impl Iterator<Item = &Arc<Baz>> {
        // return some concrete iterator Y
    }

    fn iter<'f>(&'f self)  -> impl Iterator<Item = &Arc<Baz>> + 'f {
        if some_condition {
            Either::Left(self.inner_one())
        } else {
            Either::Right(self.inner_two())
        }
    }
}

This solution does a pretty nice job of abstracting over the 2 different iterators. Either's internal magic even allows me to treat the return type of Foo::iter() itself as an iterator, which is ideal both because it does wat the name iter implies and because I can continue to leverage the impl Trait syntax.

1 Like