Hello,
I have a problem with lifetimes and impl Trait
that I can't figure out how to solve. The code below exemplifies the error I'm getting (sorry it's kind of long). I'm trying to use the bfs
function from the pathfinding
crate. Which requires giving a closure that returns an iterator of successor nodes given a reference to a node. The iterator in my case references the node and an additional context. Somehow I cannot call my method from the closure. I tried giving the node and context parameters different lifetime parameters but couldn't make this work either.
One way I found to sidestep the issue is to return an iterator from my reachable_nodes
function that doesn't capture any parameters my appending .collect::<Vec<_>>().into_iter()
to my chain of iterator adapters. I feel like this shouldn't be necessary, though.
#![allow(unused_variables)]
use std::hash::Hash;
/// Compute a shortest path using the [breadth-first search
/// algorithm](https://en.wikipedia.org/wiki/Breadth-first_search).
///
/// The shortest path starting from `start` up to a node for which `success` returns `true` is
/// computed and returned in a `Some`. If no path can be found, `None`
/// is returned instead.
///
/// - `start` is the starting node.
/// - `successors` returns a list of successors for a given node.
/// - `success` checks whether the goal has been reached.
///
/// See https://docs.rs/pathfinding/3.0.11/pathfinding/directed/bfs/fn.bfs.html
pub fn bfs<N, FN, IN, FS>(start: &N, successors: FN, success: FS) -> Option<Vec<N>>
where
N: Eq + Hash + Clone,
FN: FnMut(&N) -> IN,
IN: IntoIterator<Item = N>,
FS: FnMut(&N) -> bool,
{
// details not important
todo!()
}
/// This is a stand-in for a node in my undirected graph. The actual type contains some fields but
/// no references.
#[derive(Eq, PartialEq, Hash, Clone)]
struct Node;
impl Node {
/// Check if a neighbor node has a certain property.
fn check(&self, node: &Node) -> bool {
todo!()
}
/// Return an iterator that returns all nodes reachable from this one.
fn reachable_nodes<'a>(&'a self, context: &'a Context) -> impl Iterator<Item = Node> + 'a {
let some_nodes = vec![Node, Node, Node];
some_nodes
.into_iter()
// The actual implementation uses multiple adapters in a more
// complex way (e.g. Itertools::cartesian_product). Crucially, both
// self and the context are referenced in closures.
.filter(|node| self.check(node) && context.check(node))
}
}
/// Some arbitrary context that contains information that applies to all nodes, e.g. a string dictionary to avoid storing strings in nodes.
struct Context;
impl Context {
/// Check if the node has a certain property.
fn check(&self, node: &Node) -> bool {
todo!()
}
}
/// Do the search.
pub fn search() {
// Start of the search.
let start = Node;
// Goal of the search.
let goal = Node;
// The context.
let context = Context;
let _result = bfs(
&start,
|node| node.reachable_nodes(&context),
|node| *node == goal,
);
// do something with the result
}
Errors:
Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
--> src/lib.rs:62:16
|
72 | |node| node.reachable_nodes(&context),
| ----- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ returning this value requires that `'1` must outlive `'2`
| | |
| | return type of closure `impl Iterator<Item = Node>` contains a lifetime `'2`
| has type `&'1 Node`
error: could not compile `playground` due to previous error