Overflow evaluating requirement when using a wrapping struct and trait bounds

I am trying to implement a RootedGraph<G> type (see the minimal example demonstrating the issue below), which when constructed takes some graph G and finds its root (or inserts it). My problem is that I can't seem to express the traits bounds properly when trying to write a generic solution, because the compiler tries to construct the recursive type RootedGraph<RootedGraph<RootedGraph<....>>>

error[E0275]: overflow evaluating the requirement `&RootedGraph<_>: GraphIndices`
  --> src/lib.rs:38:21
   |
38 |         let roots = find_roots(&self.graph);
   |                     ^^^^^^^^^^
...
46 | fn find_roots<'a, G, I, V>(graph: &'a G) -> Vec<V>
   |    ----------
47 | where
48 |     &'a G: GraphIndices<Iter = I, VertexId = V>,
   |            ------------------------------------ required by this bound in `find_roots`
   |
   = help: consider adding a `#![recursion_limit="8"]` attribute to your crate (`recursion_error`)
   = note: required because of the requirements on the impl of `GraphIndices` for `&RootedGraph<RootedGraph<_>>`
   = note: required because of the requirements on the impl of `GraphIndices` for `&RootedGraph<RootedGraph<RootedGraph<_>>>`
   = note: required because of the requirements on the impl of `GraphIndices` for `&RootedGraph<RootedGraph<RootedGraph<RootedGraph<_>>>>`

error: aborting due to previous error

Can somebody explain where I am going wrong? I have repeatedly found mentioned on the rust issue tracker that the message is actually misleading and there is some other issues with this error, but it's not always clear what the problem is.

Is there maybe something wrong with my for<'a> bound?

MWE (link to playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f10b5fec0c0eb2a4c2cf14f839c0c871):

#![recursion_limit="4"]
pub trait GraphIndices {
    type VertexId;
    type Iter: Iterator<Item = Self::VertexId>;

    fn vertex_indices(self) -> Self::Iter;
}

pub struct RootedGraph<G>
{
    inner: G,
}

impl<'a, G, I, V> GraphIndices for &'a RootedGraph<G>
where
    &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    type VertexId = V;
    type Iter = I;

    fn vertex_indices(self) -> I {
        self.inner.vertex_indices()
    }
}

pub struct RootedGraphBuilder<G>
{
    graph: G,
}

impl<G, I, V> RootedGraphBuilder<G>
where
    for<'a> &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    pub fn build(self) -> RootedGraph<G> {
        let roots = find_roots(&self.graph);

        RootedGraph {
            inner: self.graph,
        }
    }
}

fn find_roots<'a, G, I, V>(graph: &'a G) -> Vec<V>
where
    &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    todo!()
}

I have just found a way to at least get it to compile by moving find_roots into the impl block on RootedGraphBuilder (and I am not yet sure if it will eventually do what it's supposed to do); see playground for the code below (https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=095af7ab04bfa059408db5049b1580e5):

#![recursion_limit="4"]
pub trait GraphIndices {
    type VertexId;
    type Iter: Iterator<Item = Self::VertexId>;

    fn vertex_indices(self) -> Self::Iter;
}

pub struct RootedGraph<G>
{
    inner: G,
}

impl<'a, G, I, V> GraphIndices for &'a RootedGraph<G>
where
    &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    type VertexId = V;
    type Iter = I;

    fn vertex_indices(self) -> I {
        self.inner.vertex_indices()
    }
}

pub struct RootedGraphBuilder<G>
{
    graph: G,
}

impl<G, I, V> RootedGraphBuilder<G>
where
    for<'a> &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    pub fn build(self) -> RootedGraph<G> {
        let roots = Self::find_roots(&self.graph);

        RootedGraph {
            inner: self.graph,
        }
    }
    
    fn find_roots<'a>(graph: &'a G) -> Vec<V>
    {
        todo!()
    }
}

Can somebody explain to me in how far these codes are different? Am I making a mistake or is this maybe a compiler bug?

The recursion seems to be something with respect to that reference in implementing the trait. My guess is your second one avoids it because when you moved the function into the graph builder it shared the same types so it didn’t need to do the type lookup logic that’s causing the problem. I’m certainly a bit out of my depth here, so I can’t give you a good answer as for exactly why it’s happening.

Here's another version that works which is simpler Link

I got rid of all the lifetime references and for the trait implementation I changed it such that vertex_indices take &self. I think this is a more common way to implement traits, so you're implementing the trait directly on the type rather than a reference to the type and the function signature indicates whether you need a reference to the type. As with so many other people with Rust, the more lifetimes that are involved, the more trouble I find myself in with satisfying the compiler.

Initially I had exactly that, but I am restricted in terms of what I can implement GraphIndices for. While I control GraphIndices, I am implementing it for a foreign type, let's call it ForeignGraph, which in turn has a function that provides provides an iterator over its indices. But that foregin iterator is implemented using some lifetime, ForeignIndexIterator<'a>, and so I cannot actually write GraphIndices for ForeignGraph, because then I have no way of expressing the lifetime 'a in type Iter = ForeignIndexIterator<'a>:

impl GraphIndices for ForeignGraph {
    type Iter = ForeignIndexIterator<'a>;
    // The rest
}

In the absence of GATs, that leaves me only with the option of writing

impl<'a> GraphIndices for &'a ForeignGraph {
    tyoe Iter = ForeignIndexIterator<'a>;
   // The rest

So this is the source of all my sorrow.

While not being 100% sure, I feel like these 2 threads explain my issue (lazy normalization and not having an implementation of GraphIndices for the general case &G):


Can you not do something like this for ForeignGraph



pub struct ForeignGraph<'a,G>
{
    inner: &'a G,
}

impl<'a, G, I, V> GraphIndices for ForeignGraph<'a, G>
where
    G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    type VertexId = V;
    type Iter = I;

    fn vertex_indices(&self) -> I {
        self.inner.vertex_indices()
    }
}

Playground Link

Obviously, i don't know the details of Foreign Graph, but I wouldn't think there would be an issue just because of the lifetime.

I believe I figured out what the “ultimate” fix given eager evaluation is: I need to ensure that there is no generic impl<'a, G> GraphIndices for &'a RootedGraph<G> where &'a G: GraphIndices, because this is what the evaluator/normalizer chokes on. I have not completely digested/understood the explanations in the two links I provided above, but Rust is trying to normalize at the point of trait definition and not at the point of trait usage, and since there is no impl<&'a, T> GraphIndices for &'a T for some generic T, it somehow shortcircuits and just keeps putting in RootedGraph as G, because at that specific point that's the only thing it knows that fulfills the condition.

In other words, I have to change this:

impl<'a, G, I, V> GraphIndices for &'a RootedGraph<G>
where
    &'a G: GraphIndices<Iter = I, VertexId = V>,
    I: Iterator<Item = V>,
{
    type VertexId = V;
    type Iter = I;

    fn vertex_indices(self) -> I {
        self.inner.vertex_indices()
    }
}

to this (and for every type that I want this to work for):

// Assume I have this
impl<'a> GraphIndices for &'a ForeignGraph {
    type VertexId = // Foreign Vertex Id;
    type Iter = // Foreign Vertex iterator;

    fn vertex_indices(self) -> Self::Iter {
        todo!()
    }
}

impl<'a> GraphIndices for &'a RootedGraph<ForeignGraph> {
    type VertexId = <&'a ForeignGraph as GraphIndices>::VertexId;
    type Iter = <&'a ForeignGraph as GraphIndices>::Iter;

    fn vertex_indices(self) -> Self::Iter {
        self.inner.vertex_indices()
    }
}

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