Problem with multiple lifetimes and impl Trait

#1

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
}

(Playground)

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
#2

You need something like a GAT (generic associated type) here. Note that when you have a generic type parameter, such as IN here:

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,

It must monomorphize down to a single concrete type. That's impossible in this case as the type of IN depends on the inputs to FN (every lifetime produces a different output type). You need some sort of indirection (something GAT-like) so that IN is not a type parameter.

It's even more complicated in this case, because you need your closures to be higher-ranked over their inputs (accepting different lifetimes), but still capped (not exceeding your captured Context). There are some tricks that can sometimes accomplish this, but it's messy.

There are some additional challenges, like your iterators not having nameable types. So you also want some sort of TAIT (type alias impl trait) here, ideally. That's not available in traits, but you can get around that on stable by boxing up your iterators, at a cost.

Sorry, that's a bunch of jargon that boils down to "it probably possible with some sacrifices, but a pain to solve this directly."

Let's take a step back though, and consider another approach. A lot of the challenge here is that you're borrowing the Context and threading that borrow through the rest of the API. When it comes to the closures, you need closures that are simultaneously higher-ranked (can handle reference inputs with various lifetimes) but within a range (capped by the borrow of the captured Context).

Instead of trying to bound all these things, we can express everything we want to do with a borrowed Context:

pub trait NodeContext<N> {
    fn check(&self, node: &N) -> bool;
    // We still take a hit due to the inability to name the iterator
    // as there is no `-> impl Trait` on trait methods yet
    fn reachable<'a>(&'a self, node: &'a N) -> Box<dyn 'a + Iterator<Item = N>>;
}

Implement it for our concrete types:

impl NodeContext<Node> for Context {
    fn check(&self, node: &Node) -> bool {
        self.check(node)
    }
    fn reachable<'a>(&'a self, node: &'a Node) -> Box<dyn 'a + Iterator<Item=Node>> {
        Box::new(node.reachable_nodes(self))
    }
}

And make use of it in bfs:

pub fn bfs<N, Ctx, FS>(start: &N, context: &Ctx, success: FS) -> Option<Vec<N>>
where
    N: Eq + Hash + Clone,
    Ctx: NodeContext<N>,
    FS: FnMut(&N) -> bool,
{
    // details not important
    todo!()
}
// ...
    let _result = bfs(
        &start,
        &context,
        |node| *node == goal,
    );

Playground. Not sure if it meets your use case or not.

#3

Actually, there's no need for something like a GAT if you can name the type with the lifetime. impl Trait isn't allowed in trait bounds, but Box also erases the underlying (unnameable/opaque) type, so that just leaves the "higher-ranked but bound" annoyance.

So with this bound:

pub fn bfs<'context, N, FN, FS>(start: &N, successors: FN, success: FS) -> Option<Vec<N>>
where
    N: Eq + Hash + Clone,
    FN: for<'x> FnMut(&'x N, [&'x &'context (); 0]) -> Box<dyn 'x + Iterator<Item=N>>,
    FS: FnMut(&N) -> bool,
{

There's no problem with monomorphizing the return type, as it's under the for<'x> inside the Box. As alluded to, we need the box because we can't use impl Trait, and we can't name the type and put a bound on it elsewhere without needing something GAT-like.

There's no point in trying to make something GAT-like in this case, as GAT emulation on stable requires going through a trait with an associated type, and you can't name the types, so they'd have to just be the Box anyway.

The weird second parameter is to indirectly supply the cap on 'x. 'context: 'x due to the well-formed requirements of nested references.

You can use it like so:

    let _result = bfs(
        &start,
        |node, _| Box::new(node.reachable_nodes(&context)),
        |node| *node == goal,
    );

Playground.

#4

Thank you for your responses, they've been really helpful. I think I understand the problem now, i.e. there really are different lifetimes for the self and the context parameters but there's no way to express that in a way that satisfies the bounds on the bfs function. Unfortunately, the solutions you proposed require changes to the bfs function in the pathfinding crate. Since this is just for a small coding exercise this is not something I can do right now, especially since these seem to be potentially breaking changes.

However, writing down the problem and your explanation have given me another solution: I can wrap the Context in an Rc and clone the node one extra time in the iterator returning function. The iterator is producing node values anyway so one more clone shouldn't hurt too much:

    fn reachable_nodes(&self, context: &Rc<Context>) -> impl Iterator<Item = Node> {
        let this = self.clone();
        let context = context.clone();
        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(move |node| this.check(node) && context.check(node))
    }

    // in the search function:
    let context = Rc::new(Context);

    let _result = bfs(
        &start,
        {
            let context = context.clone();
            move |node| node.reachable_nodes(&context)
        },
        |node| *node == goal,
    );

(Playground)

1 Like
#5

Ah, you don't control bfs; I overlooked that, but at least my replies were still useful, heh. Then yes, the current bounds dictate that the return value of FN be a single type, which can therefore not capture the borrow of the input.