CODEWITHSUNDEEP
rust
Nico227
Nico227

Reputation: 366

Lifetime collision when bounding reference of a trait as IntoIterator

I tried to implement some graph algorithms on generic graphs. For that, I defined two graph traits which would return either a generic trait (having set-operations) SetGraph or an IntoIterator used to iterate over the nodes NeighborhoodIteratorGraph.

pub trait NeighborhoodIteratorGraph<'a> {
    //which into_iterator do we have?
    type IntoIter: 'a + std::iter::IntoIterator<Item = usize>;
    fn get_neighborhood_iterator(&'a self, index: usize) -> Self::IntoIter;
}

pub trait SetGraph<'a>
where
    &'a Self::S: IntoIterator<Item = usize>,
    Self::S: 'a,
{
    type S;
    fn get_neighborhood(&'a self, index: usize) -> &'a Self::S;
}

Because one is usually able to iterate over sets, I also implemented NeighborhoodIteratorGraph for all SetGraph which are able to iterate over their sets.

impl<'a, G> NeighborhoodIteratorGraph<'a> for G
where
    G: SetGraph<'a>,
    &'a G::S: IntoIterator<Item = usize>,
{
    type IntoIter = &'a G::S;
    fn get_neighborhood_iterator(&'a self, index: usize) -> Self::IntoIter {
        self.get_neighborhood(index)
    }
}

I needed to add a lifetime to NeighborrhoodIteratorGraph otherwise the compiler would tell me my implementation would have an unbounded lifetime.

However I quicky run into problems with these lifetimes and I get an error for the following code:

struct Foo<'a, G: NeighborhoodIteratorGraph<'a>> {
    graph: G,
    //otherwise we get an error because 'a wouldn't be used
    _marker: std::marker::PhantomData<&'a G>,
}

impl<'a, G: NeighborhoodIteratorGraph<'a>> Foo<'a, G> {
    pub fn find_matching_for<I>(&mut self, nodes: I) -> bool
    where
        I: std::iter::IntoIterator<Item = usize>,
    {
        for node in self.graph.get_neighborhood_iterator(3) {}
        return true;
    }
}

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements

It seems that the PhantomData field is more a hack and I can't find a way in which I get a set refernce which can be seen as a IntoIterator object.

Here is the Rust Playground of the problem.

Full error message:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:38:32
   |
38 |         for node in self.graph.get_neighborhood_iterator(3) {}
   |                                ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 34:5...
  --> src/lib.rs:34:5
   |
34 | /     pub fn find_matching_for<I>(&mut self, nodes: I) -> bool
35 | |     where
36 | |         I: std::iter::IntoIterator<Item = usize>,
   | |_________________________________________________^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:38:21
   |
38 |         for node in self.graph.get_neighborhood_iterator(3) {}
   |                     ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 33:6...
  --> src/lib.rs:33:6
   |
33 | impl<'a, G: NeighborhoodIteratorGraph<'a>> Foo<'a, G> {
   |      ^^
note: ...so that the types are compatible
  --> src/lib.rs:38:32
   |
38 |         for node in self.graph.get_neighborhood_iterator(3) {}
   |                                ^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `&'a G`
              found `&G`

Upvotes: 2

Views: 132

Answers (1)

Aiden4
Aiden4

Reputation: 2654

What you want is a workaround for the lack of generic associated types, which are currently very unstable. Something Like

pub trait NeighborhoodIteratorGraph {
    type IntoIter<'a>: std::iter::IntoIterator<Item = usize> + 'a;
    fn get_neighborhood_iterator<'b>(&'b self, index: usize) -> Self::IntoIter<'b>;
}

would serve you perfectly if they were stable.

The first thing I did is remove the lifetime bound on NeighborhoodIteratorGraph and add it to the return type:

pub trait NeighborhoodIteratorGraph {
    type IntoIter: std::iter::IntoIterator<Item = usize>;
    fn get_neighborhood_iterator<'b>(&'b self, index: usize) -> Self::IntoIter
    where
        Self::IntoIter: 'b;
}

I then removed unnecessary lifetime annotations from SetGraph:

pub trait SetGraph<'a>
where
    &'a Self::S: IntoIterator<Item = usize>,
    Self::S: 'a,
{
    type S;
    fn get_neighborhood(&self, index: usize) -> &Self::S;
}

I then changed the blanket impl's signature to match the modified traits, and changed the impl from G to &'a G to properly constrain the lifetime 'a:

impl<'a, G> NeighborhoodIteratorGraph for &'a G
where
    G: SetGraph<'a>,
    &'a G::S: IntoIterator<Item = usize>,
{
    type IntoIter = &'a G::S;
    fn get_neighborhood_iterator<'b>(&'b self, index: usize) -> Self::IntoIter
    where
        Self::IntoIter: 'b,
    {
        self.get_neighborhood(index)
    }
}

Because of those changes I was able to simplify Foo and its impl:

struct Foo<G: NeighborhoodIteratorGraph> {
    graph: G,
}

impl<G: NeighborhoodIteratorGraph> Foo<G> {
    pub fn find_matching_for<I>(&mut self, nodes: I) -> bool
    where
        I: std::iter::IntoIterator<Item = usize>,
    {
        for node in self.graph.get_neighborhood_iterator(3) {}
        return true;
    }
}

Leaving the compiler output with nothing but dead code warnings. Playground link

Upvotes: 1

Related Questions