Iterator<T> not sized

1 
pub trait GraphReadT<NodeId: Sized> {
    fn nodes(&self) -> std::iter::Iterator<Item = NodeId>;

    fn neighbors(&self, node: NodeId) -> std::iter::Iterator<Item = NodeId>;
}

impl GraphUtil {
    pub fn connected_component<NodeId, GraphRead: GraphReadT<NodeId> + Sized>(graph_read: GraphRead) {
        for node in graph_read.nodes() {
            //
        }

        //
    }
}

What am I doing wrong here? I am trying to abstract out the notion of a graph in a trait and then implement connected components only via the trait.

The first step is to iterate over all the nodes ...

2

Writing a trait alone as a type, like Iterator, is the old way of writing what is now dyn Iterator, a dynamically-dispatched trait object. This can be filled by any type that implements that trait, which is why it has indeterminate size.

In some cases, you might want to write impl Iterator instead, but that can't be returned from trait methods yet. That leaves you with the option of a boxed trait object, Box<dyn Iterator>.

3

I thought part of the magic of traits is that I can have this generate a unique function for every NodeId type and thus have it be zero cost abstraction.

Box<dyn Iterator> sounds like there is a heap allocation going on. Is this necessary?

4

Oh, wait, is the problem not

Iterator<NodeId> can be generic over NodeId

but rather the problem is that

Iterator<NodeId>an be generic over the type of iterator used to implement the trait Iterator, and these iterators might have different size ?

5

Correct.

1 Like
6 
pub struct GraphUtil {}

pub trait GraphReadT<NodeId: Sized, ItT: std::iter::Iterator<Item = NodeId>> {
    fn nodes(&self) -> ItT;

    fn neighbors(&self, node: NodeId) -> ItT;
}

impl GraphUtil {
    pub fn connected_component<NodeId, ItT: std::iter::Iterator<Item = NodeId>, GraphRead: GraphReadT<NodeId, ItT> + Sized>(graph_read: GraphRead) {
        for node in graph_read.nodes() {
            //
        }

        //
    }
}

This compiles.

This now allows rustc to generate a copy of the function per NodeId, per iterator type used to implement Iterator<NodeId> right? Does everything look right? Any pitfalls I should watch out for?

7

I think you'll find that using a generic parameter for ItT is difficult (if not impossible) for both the implementer and caller to use. It might work in your connected_component as written, but just because you've pushed the choice of ItT up a level. The problem is that at some point that type has to be chosen by the caller, which likely isn't what you want.

An associated type is meant for situations like this, where an implementation of the trait has exactly one appropriate type for the given trait (and all its parameters). The IntoIterator trait is a good example of this, or you might write your example like this:

pub trait GraphReadT<NodeId: Sized> {
    type Nodes: std::iter::Iterator<Item = NodeId>;
    type Neighbors: std::iter::Iterator<Item = NodeId>;

    fn nodes(&self) -> Self::Nodes;
    fn neighbors(&self, node: NodeId) -> Self::Neighbors;
}

I showed separate iterator types allowed for each, but you could lock them to the same type if you want.

2 Likes
8

Your solution has the additional benefit that Self::Nodes and Self::Neighbors can be different iterators.

Thanks!

9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.