Returning the iterator trait from another trait

help
1

I have a custom container, for which I want to implement a custom iterator. The container type is described by an interface, as it can have multiple underlying implementations (e.g. vector or tree based).

Currently I have these methods that return a boxed iterator, since we cannot use impl Iterator in trait return types

pub trait TagContainer: Default + std::fmt::Debug {
    fn iter(&self) -> Box<dyn Iterator<Item = (&Tag, u32)>>;
    fn iter_mut(&self) -> Box<dyn Iterator<Item = (&Tag, u32)>>;
}

The reason why I want to make the trait have the iter methods, is because I have other methods on the trait like has_any that I then could implement with default implementations on the trait itself.

For a concrete implementation I then use

#[derive(Debug, Default)]
pub struct TagVector {
    tags: Vec<(Tag, u32)>,
    len: usize,
}

impl TagContainer for TagVector {
    fn iter(&self) -> Box<dyn std::iter::Iterator<Item = (&Tag, u32)>> {
        let i = self.tags.into_iter();
        Box::new(i)
    }
    // ...
}

Now the iter implementation obviously doesn't work since I cannot move the tags into the Box, but using &self.tags.into_iter() yields a reference and not an iterator.

Is the thing I want to do even possible? Do I need to use nightly, or a completely different approach?

Thanks in advance.

2

You can put a lifetime on the trait object. By default, in function signatures, trait objects have an implicit + 'static lifetime bound, which means they can't store any references. But we can override that by adding our own bound. In this case, we can use an elided + '_ bound to say that the returned trait object must live as long as the &self or &mut self reference.

pub trait TagContainer: Default + std::fmt::Debug {
    fn iter(&self) -> Box<dyn Iterator<Item = (&Tag, u32)> + '_>;
    fn iter_mut(&mut self) -> Box<dyn Iterator<Item = (&mut Tag, u32)> + '_>;
}

#[derive(Debug)]
pub struct Tag;

#[derive(Debug, Default)]
pub struct TagVector {
    tags: Vec<(Tag, u32)>,
    len: usize,
}

impl TagContainer for TagVector {
    fn iter(&self) -> Box<dyn Iterator<Item = (&Tag, u32)> + '_> {
        let i = self.tags.iter().map(|(tag, i)| (tag, *i));
        Box::new(i)
    }

    fn iter_mut(&mut self) -> Box<dyn Iterator<Item = (&mut Tag, u32)> + '_> {
        let i = self.tags.iter_mut().map(|(tag, i)| (tag, *i));
        Box::new(i)
    }
}
3 Likes
3

This compiles:

#[derive(Debug)]
pub struct Tag;

pub trait TagContainer: Default + std::fmt::Debug {
    fn iter(&self) -> Box<dyn Iterator<Item = &(Tag, u32)> + '_>;
}

#[derive(Debug, Default)]
pub struct TagVector {
    tags: Vec<(Tag, u32)>,
    len: usize,
}

impl TagContainer for TagVector {
    fn iter(&self) -> Box<dyn std::iter::Iterator<Item = &(Tag, u32)> + '_> {
        let i = self.tags.iter();
        Box::new(i)
    }
    // ...
}

(Playground)

4

The rules are actually slightly more complex, the TL;DR being that Box<dyn Trait> is indeed Box<dyn Trait + 'static>, but &dyn Trait and &mut dyn Trait don't use 'static but the lifetime from the reference, so that &'a dyn Trait is &'a (dyn Trait + 'a) and &'a mut dyn Trait is &'a mut (dyn Trait + 'a).

6 Likes
5

That works, thanks.

Follow up question:
I can do

let left = vec![1,2,3];
let right = vec![1,2,3];
dbg!(left.iter().zip(right).collect::<Vec<_>>());

and right is automatically coerced(?) into an interator. However, for my type I have to use

left.iter().zip(other.iter()).collect::<Vec<_>>());

Is there any particular reason for this? I assume it's because I used Box.

6

For that to work, you'll want to implement the IntoIterator trait for references to TagVector.

// optional
impl IntoIterator for TagVector {
    type Item = (Tag, u32);
    type IntoIter = Box<dyn Iterator<Item = (Tag, u32)>>;
    
    fn into_iter(self) -> Self::IntoIter {
        Box::new(self.tags.into_iter())
    }
}

impl<'a> IntoIterator for &'a TagVector {
    type Item = (&'a Tag, u32);
    type IntoIter = Box<dyn Iterator<Item = (&'a Tag, u32)> + 'a>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a> IntoIterator for &'a mut TagVector {
    type Item = (&'a mut Tag, u32);
    type IntoIter = Box<dyn Iterator<Item = (&'a mut Tag, u32)> + 'a>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

This allows left.iter().zip(&right) and for (tag, i) in &vec { ... } to work as expected.

1 Like