What type can I use to express "&dyn Iterable<str>"?

I'm looking for a type I could use to effectively express "thing that can be iterated on yielding &strs", but without generics so my method is object-safe/dynamically dispatchable, and so it can be iterated on multiple times, i.e. some type of &dyn Iterable<str>.

For example, what type could I put on strings to make this code compile?

trait Foo {
    fn process_strings(&self, strings: ???);
}

struct FooImpl;

impl Foo for FooImpl {
    fn process_strings(&self, strings: ???) {
        for s in strings {
            println!("{}", s);
        }
        for s in strings {
            println!("{}", s);
        }
    }
}

fn run_foo(foo: &dyn Foo) {
    let a: Box<[&str]> = Box::from(["a", "b"]);
    let b: Vec<&str> = a.to_vec();
    let c: Vec<Arc<str>> = a.iter().copied().map(From::from).collect();
    let d: Vec<String> = a.iter().copied().map(From::from).collect();
    let e: HashSet<String> = a.iter().copied().map(From::from).collect();

    foo.process_strings(&a);
    foo.process_strings(&b);
    foo.process_strings(&c);
    foo.process_strings(&d);
    foo.process_strings(&e);
}

fn main() {
    run_foo(&FooImpl {});
}

I did manage to define a trait, but I'm just wondering if there's an easier way to do this with the standard library or a common crate?

This is what I came up with so I can write &dyn Iterable<str>. Playground link.

trait Iterable<'a, T: ?Sized>
where
    Self: 'a,
{
    fn boxed_iter(&'a self) -> Box<dyn Iterator<Item = &'a T> + 'a>;
}

impl<'a, I: 'a + ?Sized, T: Borrow<O> + 'a + ?Sized, O: ?Sized> Iterable<'a, O> for I
where
    &'a I: IntoIterator<Item = &'a T>,
{
    fn boxed_iter(&'a self) -> Box<dyn Iterator<Item = &'a O> + 'a> {
        Box::new(self.into_iter().map(Borrow::borrow))
    }
}

impl<'a, T: ?Sized> IntoIterator for &dyn Iterable<'a, T>
where
    Self: 'a,
{
    type Item = &'a T;
    type IntoIter = Box<dyn Iterator<Item = Self::Item> + 'a>;
    fn into_iter(self) -> Self::IntoIter {
        self.boxed_iter()
    }
}

Thanks!

Wouldn't something like &mut dyn Iterator<Item = &str> do the job?

I thought so too at first, but OP iterates twice over strings here:

That is not possible with a dyn Iterator.

Edit: I'm sorry that I didn't see that you need to pass so many different types, I'll keep trying.

This should help. (The second solution is obj safe)

fn iter_str1<R, S>(strings: R)
where
    R: AsRef<[S]>,
    S: AsRef<str>,
{
    for s in strings.as_ref() {
        println!("{}", s.as_ref())
    }
    for s in strings.as_ref() {
        println!("{}", s.as_ref())
    }
}

fn iter_str2<'a>(strings: &'a [impl AsRef<str>]) {
    for s in strings {
        println!("{}", s.as_ref())
    }
    for s in strings {
        println!("{}", s.as_ref())
    }
}

fn main() {
    let v = vec!["a", "b", "c"];
    iter_str1(&v);
    iter_str2(&v);
}

By the way, I also tried impl IntoIterator<...> as the arg, but it's so hard that I have to collect the refs into a Vec first for multiple for loop. Or impl IntoIterator<...> + Copy is needed.

If there's any method with IntoIterator instead of AsRef<[...]>, please let me know.

Edit:
I decide to give up, here's my final work:

fn iter_str2(strings: impl IntoIterator<Item = impl AsRef<str>> + Clone) {
    for s in strings.clone() {
        println!("{}", s.as_ref())
    }
    for s in strings {
        println!("{}", s.as_ref())
    }
}

fn main() {
    let v: Box<[&str]> = Box::from(["a", "b"]);
    iter_str2(&*v);
    let v = vec!["a".to_string(), "b".to_string(), "c".to_string()];
    iter_str2(&v);
    let v = vec!["a", "b", "c"];
    iter_str2(&v);
    use std::collections::HashSet;
    let v: HashSet<String> = HashSet::from(["a".to_string(), "b".to_string(), "c".to_string()]);
    iter_str2(&v);
    // Above works
    use std::sync::Arc;
    let v: Vec<Arc<String>> = vec!["a".to_string(), "b".to_string(), "c".to_string()]
        .into_iter()
        .map(Arc::new)
        .collect();
    iter_str2(&v); // Error: it's better to use `Arc<Vec<_>>`
}

This works well in most cases, but it seems unnecessary to define function signature like this. It's really useless since the programer should know what concrete type needed to be passed.

Do you actually need the object safety part, or are you assuming you need object safety to iterate multiple times? If not, then IntoIterator + Clone is all you need.

2 Likes

Here's a weakness of your playground.

fn run_owned(foo: &dyn Foo, iter: Box<dyn Iterable<'_, str> + '_>) {
    foo.process_strings(&*iter);
}
error[E0597]: `*iter` does not live long enough
  --> src/main.rs:23:25
   |
22 | fn run_owned(foo: &dyn Foo, iter: Box<dyn Iterable<'_, str> + '_>) {
   |                             ----
   |                             |
   |                             binding `iter` declared here
   |                             has type `Box<dyn Iterable<'1, str>>`
23 |     foo.process_strings(&*iter);
   |     --------------------^^^^^^-
   |     |                   |
   |     |                   borrowed value does not live long enough
   |     argument requires that `*iter` is borrowed for `'1`
24 | }
   | - `*iter` dropped here while still borrowed

Why? Well, looking here:

impl<'a, T: ?Sized> IntoIterator for &dyn Iterable<'a, T>
where
    Self: 'a,

That can be translated to:

impl<'a, T: ?Sized> IntoIterator for &'a dyn Iterable<'a, T>

And in run_owned that means trying to borrow iter for a non-local lifetime. Any coercions involving invariance with the &'a strs to be produced would probably also be problematic.

process_strings works because, due to obscure rules, you're effectively taking a

strings: &'i (dyn Iterable<'i, str> + 'i)

There's a lot of things being tied together in the playground that I didn't have time to unravel, so unfortunately I don't have any actual suggestions for now.[1] I suspect the usual pain around GATs and HRTBs may come into play.


  1. OK, one minor one: AsRef instead of Borrow ↩ī¸Ž

3 Likes

I found a way to get rid of the invariance issue, while also (I believe) dodging the typical GAT/HRTB issues, for this case.

Using AsRef instead of Borrow also works for the playground; choose whichever works better for you.

A long explanation follows. I didn't really cover motivation for the approach, but feel free to ask questions.


We start with this signature. I'm keeping lifetimes out of the trait parameters to avoid invariance. The signature is non-'static-friendly/HRTB-friendly because, given an anonymous lifetime &'this self, there are implied Self: 'this and Item: 'this bounds.

trait Iterable<Item: ?Sized> {
    fn boxed_iter(&self) -> Box<dyn Iterator<Item = &Item> + '_>;
}

Our first attempt to implement it could be

impl<Iter: ?Sized, Item: ?Sized> Iterable<Item> for Iter
where
    for<'any> &'any Iter: IntoIterator<Item = &'any Item>>,
{
    fn boxed_iter(&self) -> Box<dyn Iterator<Item = &Item> + '_> {
        Box::new(self.into_iter())
    }
}

However, this won't work for the cases you wish it could work for: iterators over &Arc<str> and so on. One way to try to add that flexibility would be like so:

impl<Iter: ?Sized, Item: ?Sized, Temp: ?Sized> Iterable<Item> for Iter
where
    for<'any> &'any Iter: IntoIterator<Item = &'any Temp>>,
    Temp: Borrow<Item>,
{
    fn boxed_iter(&self) -> Box<dyn Iterator<Item = &Item> + '_> {
        Box::new(self.into_iter().map(Borrow::borrow))
    }
}

But there is no implicit Temp: 'this bound anywhere in the signature, so this is not HRTB-friendly, without sacrificing something else (like making This: 'static perhaps, which would preclude some things we want to work -- a Vec of locally borrowed &'local str for example).

Instead I introduce a helper trait:

impl<'a, Frm, Tgt> RefInto<&'a Tgt> for &'a Frm
where
    Frm: ?Sized,
    Tgt: ?Sized,
    Frm: Borrow<Tgt>
{
    fn ref_into(self) -> &'a Tgt {
        self.borrow()
    }
}

Tgt: 'a and Frm: 'a are implied bounds in the signature of this helper trait. Then we change the bounds on our Iterable implementation:

impl<Iter: ?Sized, Item: ?Sized> Iterable<Item> for Iter
where
    for<'any> &'any Iter: IntoIterator<Item: RefInto<&'any Item>>,
{
    fn boxed_iter(&self) -> Box<dyn Iterator<Item = &Item> + '_> {
        Box::new(self.into_iter().map(RefInto::ref_into))
    }
}

The key part is that we can add the Item: RefInto<&'any Item> bound underneath the for<'any> binder. In that context, there are implied bounds of Item: 'any and Iter: 'any, and from the latter, the compilier can deduce that <Iter as IntoIterator>::Item: 'any as well. So this version is HRTB-friendly.

The ability to add the bound in this position is new as of a release or two ago, by the way.

Finally (for whatever approach is used), we add your IntoIterator implementation for &dyn Iterable<_>.

impl<'this, Item> IntoIterator for &'this dyn Iterable<Item>
where
    Item: ?Sized + 'this,
{
    type Item = &'this Item;
    type IntoIter = Box<dyn Iterator<Item = Self::Item> + 'this>;
    fn into_iter(self) -> Self::IntoIter {
        self.boxed_iter()
    }
}

'this is in covariant position everywhere in the implementation, so the problems with Box<dyn Iterable + '_> have gone away.

4 Likes

As an alternative, I found another way to fix the weakness (slightly modified by @quinedot)

2 Likes

Thanks so much for the foo_owned example and explanation of your fix. I'm not sure what you mean by "HRTB-friendly", but your fix makes sense and I've incorporated it into my own code.

When dealing with traits built around borrowing, you can run into a lot of unfortunate limitations of HRTBs (T: for<'a> ...) in combination with GATs, such as not being able to implement them for types that don't meet a 'static bound or the like:

But it didn't end up being a blocker this time.

@zylthinking1's solution also dodges those problems by not needing to be higher-ranked to achieve the same or similar functionality.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.