rust - 将特征的边界引用作为 IntoIterator 时的生命周期冲突

Question

我试图在通用图上实现一些图算法。为此，我定义了两个图形特征，它们将返回一个通用特征(具有集合操作)SetGraph 或一个用于迭代节点 NeighborhoodIteratorGraph 的 IntoIterator。

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;
}

因为通常能够迭代集合，所以我还为所有能够迭代集合的 SetGraph 实现了 NeighborhoodIteratorGraph。

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)
    }
}

我需要为 NeighborrhoodIteratorGraph 添加一个生命周期，否则编译器会告诉我我的实现将有一个无限的生命周期。
但是，我很快遇到了这些生命周期的问题，并且我收到以下代码的错误:

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

似乎 PhantomData 字段更像是一个 hack，我找不到一种方法来获得一个可以被视为 IntoIterator 对象的集合引用。
Here是问题的 Rust Playground。
完整的错误信息:

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`

Answer 1

您想要的是一种针对缺乏通用关联类型的解决方法，这些类型目前非常不稳定。就像是

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

如果它们稳定，将为您提供完美的服务。
我做的第一件事是删除 NeighborhoodIteratorGraph 上的生命周期限制。并将其添加到返回类型:

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;
}

然后我从 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;
}

然后我更改了毯子 impl 的签名以匹配修改后的特征，并将 impl 从 G 更改为至 &'a G正确限制生命周期 '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)
    }
}

由于这些更改，我能够简化 Foo及其含义:

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;
    }
}

只留下死代码警告的编译器输出。 Playground link