Is there any way to simulate Generic Associated Types / Associated Type Constructors in Rust?

user_4698744 0
Viewed 1710

I'm making a graph processing module in Rust. The core of the module models the idea of having multiple containers which hold the data in the graph. For example, I may have a graph whose inner structure is an HashMap or maybe AdjacencyMatrix etc.

These containers must implement a trait:

trait GraphData<V> {
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Iterator<V>; // Here's the problem...
}

I can't just return a trait in my trait definition. I know I must use trait object, but I don't want to Box it. I would like to make the container provide its own NodeIter struct. However, I would be stuck with the same problem explained in Associated type constructors, part 1: basic concepts and introduction. The post explains about associated type constructors (ATC) which do not exist in Rust now. My GraphData resembles the generic Collection described.

Is there any workaround I could use to "simulate" ATC or any pattern specific to Rust I could use for this situation?

I don't want to depend on dynamic dispatch and resort to using Box or the dyn keyword.

I thought to define a struct NodeIter for each type of graph container I created in my module and add "nodes" inside the implementation of the container itself. However, I find this to be poor code reuse.

associated-types rust generics
2 Answers

The problem you’ve described is solved with plain associated types. It does not require generic associated types, a.k.a. associated type constructors. This already works in stable Rust.

trait GraphData<V> {
    type Nodes: Iterator<Item = V>;
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Self::Nodes;
}

struct Graph<V> {
    nodes: Vec<V>,
    edges: Vec<(V, V)>,
}

impl<V: Clone + Eq> GraphData<V> for Graph<V> {
    type Nodes = vec::IntoIter<V>;
    fn has_edge(&self, u: &V, v: &V) -> bool {
        self.edges.iter().any(|(u1, v1)| u == u1 && v == v1)
    }
    fn nodes(&self) -> Self::Nodes {
        self.nodes.clone().into_iter()
    }
}

Nodes has no type or lifetime parameters (it’s not Nodes<T> or Nodes<'a>), so it’s not generic.

If you wanted the Nodes type to be able hold a reference to Self (to avoid the clone()), then Nodes would need to be generic with a lifetime parameter. That’s not the only way to avoid the clone(), though: you could use Rc.

user_1150300

As the answer by Anders Kaseorg already explains: you might not need GATs here, if you can live with cloning your Vec containing the vertices. However, that's probably not what you want. Instead, you usually want to have an iterator that references the original data.

To achieve that, you in fact ideally want to use GATs. But since they are not part of the language yet, let's tackle your main question: Is there any way to simulate Generic Associated Types? I actually wrote a very extensive blog post about this topic: “Solving the Generalized Streaming Iterator Problem without GATs”.

Summarizing the article:

  • The easiest way for you is to box the iterator and return it as trait object:

    fn nodes(&self) -> Box<dyn Iterator<&'_ V> + '_>

    As you said, you don't want that, so that's out.

  • You can add a lifetime parameter to your trait and use that lifetime in your associated type and the &self receiver: 

    trait GraphData<'s, V: 's> {
    type NodesIter: Iterator<Item = &'s V>;
    fn nodes(&'s self) -> Self::NodesIter;
}

struct MyGraph<V> {
    nodes: Vec<V>,
}

impl<'s, V: 's> GraphData<'s, V> for MyGraph<V> {
    type NodesIter = std::slice::Iter<'s, V>;
    fn nodes(&'s self) -> Self::NodesIter {
        self.nodes.iter()
    }
}

    This works! However, now you have an annoying lifetime parameter in your trait. That might be fine (apart from annoyance) in your case, but it can actually be a critical problem in some situations, so this might or might not work for you.

  • You can push the lifetime parameter a level deeper by having a helper trait which works as type level function from lifetime to type. This makes the situation a little less annoying, because the lifetime parameter is not in your main trait anymore, but it suffers from the same limitation as the prior workaround.

  • You can also go a completely different path and write an iterator wrapper that contains a reference to your graph.

    This is just a rough sketch, but the basic idea works: your actual inner iterator doesn't contain any reference to the graph (so its type does not need the self lifetime). The graph reference is instead stored in a specific type Wrap and passed to the inner iterator for each next call.

    Like this:

    trait InnerNodesIter { /* ... */ }

struct Wrap<'graph, G: GraphData, I: InnerNodesIter> {
    graph: &'graph G,
    iter: I,
}

type NodesIterInner: InnerNodesIter;
fn nodes(&self) -> Wrap<'_, Self, Self::NodesIterInner>;

    Then you can implement Iterator for Wrap. You just need some interface to the inner iterator, which you can pass the reference to the graph. Something like fn next(&mut self, graph: &Graph) -> Option<...>. You need to define the interface in InnerNodesIter.

    This of course suffers from being very verbose. And it also might be a bit slower, depending on how your iterator works.

The short and sad summary is: there is no satisfying workaround that works in every situation.

My opinion in this case: I work on a project where this exact situation occurred multiple times. In my case, I just used the Box solution as it's very easy and works fine. The only downside is speed (allocation and dynamic dispatch), but the allocation doesn't happen in a tight loop (except if you have a large number of graphs, each with only very few nodes -- unlikely) and the optimizer is probably capable of devirtualizing the dynamic calls in most cases (after all, the real type information is only one function boundary away).

user_24088670
Related