How to write a trait method taking an iterator of strings, avoiding monomorphization (static dispatch)?

Question

I want to define a trait that has a method operating on sequences of strings. At the same time, I want to avoid having generic methods, a.k.a. static dispatch, in the trait, so that I can use this trait as a trait object. The best solution I was given till now was to do it like below:

pub trait Store {
    fn query_valid_paths(&mut self, paths: &mut dyn Iterator<Item = &str>) -> Vec<String>;
}

Unfortunately, it's not perfect:

1. It works out of the box only for iterators of &str; for iterators of String, e.g. Vec<String>, I have to call it with the following magic map incantation, which is really ugly, and I'd never invent it as a newbie without help:

   // `vec` is a std::vec::Vec<String>
   store.query_valid_paths(&mut vec.iter().map(|s| &**s));
   

2. It takes an Iterator, but I'd love if I could take an IntoIterator. In other words, I'd like to be able to call it just like this:

   store.query_valid_paths(&vec);
   

Is it possible?

Failed Attempt 1

Based on a simpler question about functions taking string iterators, I'd imagine something like this could work:

pub trait Store {
    fn query_valid_paths<S>(&mut self, paths: impl IntoIterator<Item = S>) -> Vec<String>
    where
        S: AsRef<str>;
}

but this seems to make it a "generic method", triggering static dispatch...

Failed Attempt 2

I was suggested another idea on Rust discord, specifically:

pub trait Store {
    fn query_valid_paths_inner(&mut self, paths: &mut dyn Iterator<Item = &str>) -> Vec<String>;
}

impl dyn Store {
    pub fn query_valid_paths<'a>(&mut self, paths: impl IntoIterator<Item = &'a str>) -> Vec<String> {
        let mut it = paths.into_iter();
        self.query_valid_paths_inner(&mut it)
    }
}

— but when I try to add AsRef<str> to it, I'm getting lifetime errors, and cannot seem to make it work for both String and &str iterators...

Answer 1

I recommend you read this question, which has lots of good information about why you can't use generics with trait methods if you want to use them as objects.

The short answer is that you can't do what you're trying to do: have a function that takes in an iterator of any type (which is an associated generic function) and still have the trait be object safe.

There are a few tricks you can use, though, that will let you manipulate string iterators with a trait object. I'll go over each method.

1. Use multiple methods in your trait

Rust only has two kinds of strings: String and &str. As you've stated in your answer, you want to work with both. In this case, all you need to do is make two different methods:

pub trait Store {
    fn query_valid_paths_str(&mut self, paths: &mut dyn Iterator<Item = &str>) -> Vec<String>;
    fn query_valid_paths_string(&mut self, paths: &mut dyn Iterator<Item = String>) -> Vec<String>;
}

Now, this gets counter-intuitive at a certain point, if you have too many types you're dealing with. But if there's only two, this is the most straightforward option.

If you're wanting to use IntoIterator instead, the function signatures will look like this:

pub trait Store {
    fn query_valid_paths_str(&mut self, paths: &mut dyn IntoIterator<IntoIter = IntoIter<&str>, Item = &str>) -> Vec<String>;
    fn query_valid_paths_string(&mut self, paths: &mut dyn IntoIterator<IntoIter = IntoIter<String>, Item = String>) -> Vec<String>;
}

2. Use Box and dynamic dispatch

This approach is much more involved, and probably not worth the effort, but I'll put it here as a proof of concept.

pub trait Store {
    fn query_valid_paths(&mut self, paths: &mut dyn Iterator<Item = &Box<dyn AsRef<str>>) -> Vec<String>;
}

Here, paths is an iterator over a box which owns an AsRef<str> trait object.

This is (as far as I know) the only way to create a truly polymorphic solution. But at what cost? For this to work, you not only need to explicitly declare the list you passed in as a Vec<Box<AsRef<str>>>, it adds a lot of overhead with dynamic dispatch from the box pointers. Just to show how cumbersome this can be:

let mut str_vec: Vec<Box<AsRef<str>>> = vec!(Box::new("string one"), Box::new("string two".to_string()));
some_store_object.query_valid_paths(&mut str_vec.iter());

I do not recommend this method unless you absolutely need this functionality. Use the first method instead.

If you do use this method, but want to use it with IntoIterator, it would look like this:

pub trait Store {
    fn query_valid_paths(&mut self, paths: &mut dyn IntoIterator<IntoIter = IntoIter<Box<dyn AsRef<str>>>, Item = Box<dyn AsRef<str>>>) -> Vec<String>;
}

Answer 2

I don't think there is a nice solution without static dispatch. But the docs for the error about trait objects with methods with generic parameters actually provide a solution for this situation:

First, you mark your method with where Self: Sized – this makes it unavailable in trait objects. Maybe you don't need that method in trait object context – then you're done here.

If you need the method in trait object context, you can make it usable again via a sized type that contains your trait object e.g. Box:

struct MyStruct(i32);

pub trait Store {
    fn len_of_first_str(&self, paths: impl IntoIterator<Item = impl AsRef<str>>) -> usize
    where Self: Sized{
        paths.into_iter().next().unwrap().as_ref().len()
    }
}

impl Store for Box<dyn Store>{}

fn myfun(arg: Box<dyn Store>) -> usize {
    arg.len_of_first_str(vec!["string"])
}

Answer 3

Besides the Box approach, it is possible to define the generic in the trait definition. This method is limited by the type being implemented and uses static dispatch but your trait won't break the rules of object safety.

trait Store<'a, I>
where
    I: IntoIterator<Item = &'a str>,
{
    fn query_valid_paths(&mut self, iter: I) -> Vec<String>;
}

impl<'a, I> Store<'a, I> for ()
where
    I: IntoIterator<Item = &'a str>,
{
    fn query_valid_paths(&mut self, iter: I) -> Vec<String> {
        iter.into_iter().map(|x| x.to_string()).collect()
    }
}

// Store is object safe
struct _Bar<'a, I> {
    vec: Vec<Box<dyn Store<'a, I>>>,
}

fn main() {
    let vec_of_strings = vec!["one", "two", "three"];
    println!("{:?}", ().query_valid_paths(vec_of_strings));
}

To avoid taking ownership, you can use vec_of_strings.iter().cloned() instead.