How do I return a reference to an iterator using conservative_impl_trait?

Question

I have a petgraph::Graph structure onto which I have imposed a tree structure by giving every node weight a parent_edge_idx which is an Option<EdgeIdx> of the edge that connects from its parent to itself.

I need to iterate over a node's children. I need the edge weight of the connecting edge and the node weight of the child.

I wanted to factor that iteration into a helper function that returns a reference to an Iterator<Item = (EdgeIdx, NodeIdx)>. I want to do this cost-free; since I have to borrow self.search_tree in order to do this, the iterator is only valid for the lifetime of self.

1. Is this a reasonable function to want to write?
2. Is it possible to write this function?

Any gated features are ok; I'm on nightly.

fn children<'a>(
    &'a mut self,
    node_idx: NodeIdx,
) -> &'a impl Iterator<Item = (EdgeIdx, NodeIdx)> {
    &self.search_tree.neighbors(node_idx).map(|child_idx| {
        let node = self.search_tree.node_weight(child_idx).unwrap();
        let edge_idx = node.parent_edge_idx.unwrap();
        (edge_idx, child_idx)
    })
}

Answer 1

How to return an iterator is already covered in this question.

1. Note that you don't need to return a reference: you want to return an iterator value directly, so if we remove the first & in both the method body and the return type, that's closer to what we need.

2. We will use impl Iterator so that we don't have to name the actual iterator type exactly. Just note (code below) that we need to use the impl Iterator<..> + 'a syntax, which means that the (anonymous) iterator contains references valid to use for at least the lifetime 'a.

3. We can't use &mut self here! Note that we need to borrow self.search_tree twice: once for the .neighbors() iterator and once for the self.search_tree that's used in the map closure. Multiple borrowing is incompatible with mutable references.

4. We put move as the capture mode on the closure, so that it captures the self reference directly, and not by reference (this is important so that we can return the iterator and the closure.

5. Petgraph specific, but we replace g.node_weight(node_index).unwrap() with just &g[node_index] which is equivalent, but the latter is easier to read.

Here is a reproduction of your code, but with modifications along 1-5 to make it compile:

#![feature(conservative_impl_trait)]
extern crate petgraph;

use petgraph::Graph;
use petgraph::graph::{NodeIndex, EdgeIndex};

struct Foo {
    search_tree: Graph<Node, i32>,
}

struct Node {
    parent_edge_idx: Option<EdgeIndex>,
}

impl Foo {
    fn children<'a>(&'a self, node_idx: NodeIndex)
        -> impl Iterator<Item = (EdgeIndex, NodeIndex)> + 'a
    {
        self.search_tree.neighbors(node_idx).map(move |child_idx| {
            let node = &self.search_tree[child_idx];
            let edge_idx = node.parent_edge_idx.unwrap();
            (edge_idx, child_idx)
        })
    }
}