Implement trait that has function which return traits

I am trying to implement a trait for a struct which in turn has functions that return traits. I want this, because I do not want to bind the uer to a specific data structure. However, trying to apply the compiler's correction suggestions, I fell deeper and deeper into a rabbit hole to no avail. Here's a minimal example of what I'm trying to do:

trait WordsFilter {
    fn starting_with(&self, chr: char) -> dyn Iterator<Item = String>;
}

struct WordsContainer {
    words: Vec<String>,
}

impl WordsFilter for WordsContainer {
    fn starting_with(&self, chr: char) -> dyn Iterator<Item = String>
    {
        self.words.iter().filter(|word| word.starts_with("a"))
    }
}

fn main() {}

Which results in:

error[E0277]: the size for values of type `(dyn Iterator<Item = String> + 'static)` cannot be known at compilation time
  --> .\traits.rs:10:40
   |
10 |     fn starting_with(&self, chr: char) -> dyn Iterator<Item = String>
   |                                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `(dyn Iterator<Item = String> + 'static)`
   = note: the return type of a function must have a statically known size

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.

I tried to apply the compiler's correction's step by step but they were just getting more.

Solution

TL;DR Use generics or associated types.

You cannot use bare dyn Trait types. They are Unsized which means that compiler cannot know their size at the compile time. Therefore you can only use them behind some reference (similarly to how you cannot use str or [T] and must use &str and &[T]). The easiest way is to use Box<dyn Trait>, like PitaJ earlier suggested. This requires of course one heap allocation, but allows a very nice API.

In normal functions and methods you can however use impl Trait trick to make compiler infer returned type. This is used like this

fn foo() -> impl Iterator<Item = ()> {
    todo!()
}

Calling this function would return some concrete object that implements given trait. This however is currently not possible in Trait definitions. There is active development and hopefully in the future we will be able to use it. However now it's not the case. So following code will not compile!

// XXX: This doesn't currently work!
trait Foo {
    fn foo() -> impl Iterator<Item = ()>;
}

There is luckily a simple solution that wouldn't require boxing trait objects. You can define an associated type and require each implementator to specify a concrete type. You can also require that this type must implement the Iterator trait.

trait WordsFilter {
    type Iter: Iterator<Item = String>;
    
    fn starting_with(&self, chr: char) -> Self::Iter;
}

This would make each implementation specify one concrete type of returned iterator. If you would like to be able to return multiple different iterators for a single type you can use generics.

trait WordsFilter<I>
where
    I: Iterator<Item = String>
{
    fn starting_with(&self, chr: char) -> I;
}