What is the correct return type of a function returning an iterator produced with a closure borrowing self

Question

Consider the following code with an emphasis on children_iter():

use std::collections::HashMap;

type NodeMap = HashMap<i32, Node>;

struct Node {
    id: i32,
    parent: Option<i32>,
    sibling: Option<i32>,
    children: Vec<i32>,
    content: String,
}

pub struct NodeIterator<'a> {
    nodes: &'a NodeMap,
    current: &'a Node,
}

impl<'a> NodeIterator<'a> {
    fn new(node: &'a Node, nodes: &'a NodeMap) -> NodeIterator<'a> {
        NodeIterator {
            nodes,
            current: node,
        }
    }

    pub fn children_iter(&self) -> impl Iterator<Item = NodeIterator> {
        self.current
            .children
            .iter()
            .map(|i| self.nodes.get(i).unwrap())
            .map(|n| Self::new(n, self.nodes))
    }
}

The compilation of this code fails with:

error[E0373]: closure may outlive the current function, but it borrows `self`, which is owned by the current function
  --> src/lib.rs:30:18
   |
30 |             .map(|i| self.nodes.get(i).unwrap())
   |                  ^^^ ---- `self` is borrowed here
   |                  |
   |                  may outlive borrowed value `self`
   |
note: closure is returned here
  --> src/lib.rs:26:36
   |
26 |     pub fn children_iter(&self) -> impl Iterator<Item = NodeIterator> {
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: to force the closure to take ownership of `self` (and any other referenced variables), use the `move` keyword
   |
30 |             .map(move |i| self.nodes.get(i).unwrap())
   |                  ^^^^^^^^

error[E0373]: closure may outlive the current function, but it borrows `self`, which is owned by the current function
  --> src/lib.rs:31:18
   |
31 |             .map(|n| Self::new(n, self.nodes))
   |                  ^^^              ---- `self` is borrowed here
   |                  |
   |                  may outlive borrowed value `self`
   |
note: closure is returned here
  --> src/lib.rs:26:36
   |
26 |     pub fn children_iter(&self) -> impl Iterator<Item = NodeIterator> {
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: to force the closure to take ownership of `self` (and any other referenced variables), use the `move` keyword
   |
31 |             .map(move |n| Self::new(n, self.nodes))
   |                  ^^^^^^^^

Is there a way to correctly specify lifetimes so that it is clear that the returned iterators are only valid for the lifetime of the current NodeIterator?

Answer 1

The reason you are getting this error is because in Rust iterators are lazily-evaluated. It looks like your closures will execute within the children_iter function but they actually don't get executed until the caller calls the next method on the returned iterator.

The compiler suggests using the move keyword to move the borrowed reference into the closure which fixes the problem. However, you could also fix the problem by eagerly-evaluating your iterator and collecting the results in a Vec<NodeIterator>. Here's both approaches in a fixed and compiling example:

use std::collections::HashMap;

type NodeMap = HashMap<i32, Node>;

struct Node {
    id: i32,
    parent: Option<i32>,
    sibling: Option<i32>,
    children: Vec<i32>,
    content: String,
}

pub struct NodeIterator<'a> {
    nodes: &'a NodeMap,
    current: &'a Node,
}

impl<'a> NodeIterator<'a> {
    fn new(node: &'a Node, nodes: &'a NodeMap) -> NodeIterator<'a> {
        NodeIterator {
            nodes,
            current: node,
        }
    }

    pub fn children_iter(&self) -> impl Iterator<Item = NodeIterator> {
        self.current
            .children
            .iter()
            // lazily-evaluted closures
            // they run in the caller's scope
            .map(move |i| self.nodes.get(i).unwrap())
            .map(move |n| Self::new(n, self.nodes))
    }
    
    pub fn children_iter_vec(&self) -> Vec<NodeIterator> {
        self.current
            .children
            .iter()
            // eagerly-evaluted closures
            // we run them in the current scope
            .map(|i| self.nodes.get(i).unwrap())
            .map(|n| Self::new(n, self.nodes))
            .collect()
    }
}

playground