Help with complex lifetime situation

help
1

We're porting the WebGraph framework for graph compression from Java to Rust, and we are stuck with a complex lifetime problem.

We have a trait SequentialGraph representing graphs that can be scanned sequentially: it has an associated type GraphIterator which returns a lending iterator over (usize, Successors), where the usize is a node and Successors is an iterator on usize that returns the successors of the node. Up to here, piece of cake.

The problem is that we want to be able to wrap something implementing the trait in a PermutedGraph. A permuted graph contains a reference to a permutation p, a reference to a SequentialGraph G, and should return the same output of the GraphIterator of G, but where all output (x, [s_0, s_1,..]) become (p[ x ], [p[s_0], p[s_1],...]), that is, the permuted graph.

While the code to obtain this is literally less than ten lines, we haven't been able to set up lifetimes so that this works (because of the lending iterator). The main problem is that of connecting the lifetime of the Successor iterator of G with that of the Successor iterator of the permuted graph.

Here's a playground with a minimal example:

Thanks for any help!

2

Here is a solution based on replacing LendingIterator with a less general trait:

pub trait GraphIterator {
    type Gr: SequentialGraph;

    fn next(
        &mut self,
    ) -> Option<(
        usize,
        <<Self as GraphIterator>::Gr as SequentialGraph>::Successors<'_>,
    )>;
}

Following the consequences of this produces this program which compiles. No promises it makes sense, but I didn't touch any of the function bodies — only the types.

2 Likes
3

Thanks, that's really helpful as we can continue to develop the code and maybe in the future we can find a more general solution.

4

the LendingIterator is unnecessary (at least for the example code) and only complicates the problem.

your iterator type is not an owning type, you can just use regular Iterator:

pub struct PermutedGraphIterator<'a, G: SequentialGraph + 'a> {
    iter: G::GraphIterator<'a>,
    perm: &'a [usize],
}

impl<'a, G: SequentialGraph> Iterator for PermutedGraphIterator<'a, G> {
    type Item = (usize, PermutedSuccessors<'a, G::Successors<'a>>);

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(node, succ)| {
            (
                self.perm[node],
                PermutedSuccessors {
                    iter: succ,
                    perm: self.perm,
                },
            )
        })
    }
}

this way, the bounds on the associated types of SequentialGraph can be simplfied:

pub trait SequentialGraph {
    /// Iterator over the nodes of the graph
    type GraphIterator<'a>: Iterator<Item = (usize, Self::Successors<'a>)>
    where
        Self: 'a;
    /// Iterator over the successors of a node
    type Successors<'a>: Iterator<Item = usize> + 'a
    where
        Self: 'a;

    /// Get an iterator over the nodes of the graph
    fn iter_nodes(&self) -> Self::GraphIterator<'_>;
}

then it compiles:

1 Like
5

The problem is that we definitely need the lending iterator. We have sequential graphs (such as those deriving by on-the-fly merge of some data sources) for which a standard iterator is incredibly inefficient, because it makes impossible to have lazy successors. We had a working implementation with standard iterators, and we were horribly cheating when necessary using unsafe and pointer dereferences, but we would like to have proper types that pass the borrow checker.

6

then your current design is not implementable I think. I might be wrong, please correct me.

the PermutedGraph is a reference (not an owned wrapper) to the underlying graph:

pub struct PermutedGraph<'a, G: SequentialGraph> {
    pub graph: &'a G,
    pub perm: &'a [usize],
}

so I guess your PermutedIterator should borrow the same inner graph too (because it is an owned wrapper of the underlying node iterator, which itself is a lending iterator and borrows the inner graph):

pub struct PermutedGraphIterator<'a, G: SequentialGraph + 'a> {
    iter: G::GraphIterator<'a>,
    perm: &'a [usize],
}

semantically, you want the following signature:

impl<'a> PermutedGraph<'a, G> {
    fn nodes(&self) -> PermutedIterator<'a, G::GraphIterator<'a>>;
}

but your SequentialGraph requires a different lifetime:

pub trait SequentialGraph {
    fn iter_nodes<'b>(&'b self) -> Self::GraphIterator<'b>;
 }

i.e. you can only borrow PermutedGraph but you need to borrow the inner graph.

7

You're right, that's our problem. Wouldn't adding a reference to the inner graph in PermutedGraphIterator make it possible the borrow?

8

I don't know, maybe, you can try it, but it isn't gonna be easy.

you'll need to make it an exclusive borrow, as iterators needs to be mutated to yield next value, which means the SequentialGraph::iter_nodes() function need to take &mut self, which means your wrapper PermutatedGraph can only hold one iterator a time and not the reference to the inner graph, so your PermutatedGraph itself is the iterator wrapper after all.

lending iterators are hard to use, especially when iterator adapters are involved, like in your case.

9

Actually, it turns out your solution is all we need as we can implement LendingIterator for GraphIterator.

10

I've reduced the problem to this.

I think that the problem is that in

type GraphIterator<'a>: for<'b> 
        LendingIterator<Item<'b> = ...>
        + 'a

The for<'b> bound is supposed to apply for all lifetimes 'b, while what you really want is for it to apply only for lifetimes where 'b is shorter than 'a.

I would've thought that the Item<'b> would've brought in an implicit bound of GraphIterator<'a> : 'b since the definition of LendingIterator has Self : 'b bound.
So, either:

  • GraphIterator<'a> : 'b doesn't imply 'a : 'b. after all, without knowing the specific impl, GraphIterator might live longer than 'a. But the error is for a specific impl.
  • The bound GraphIterator<'a> : 'b doesn't get introduced, so the compiler expects it to apply for all 'b, even for 'static
  • I'm wrong wrong and the problem is something else.
11

I turned out that the situation is much more complex, in particular because of limitations of the borrow checker. After a lot of interaction here and here I came up with this playground which uses the "traitification" of a 2-tuple suggested by David to be able to define a function scan() taking a lending iterator and iterating over it (without all this mess, the borrow checker won't let you iterate).

I'm puzzled now because the compiler won't let me call the scan() function above with a lending iterator returning 2-tuples, in spite of 2-tuples implementing Tuple2. Any suggestion is welcome...

12

No suggestion but you're still running into GAT/HRTB limitations it seems.

13

can you share a playground link?