Lifetimes with traits

This is the first time I'm actually doing something with lifetimes so I am still a bit confused. But I am trying to create a Graph trait that has a function which requires a lifetime like this:

pub trait Graph {
    fn add_node<'a,'b:'a>(&'a mut self, node: &'b Node);
}

and my implementation of this trait looks like this:

pub struct StandardGraph<'a> {
    nodes: Vec<&'a Node>,
}

impl<'a> Graph for StandardGraph<'a> {
    fn add_node<'b:'a> (&'a mut self, node: &'b Node) {
        self.nodes.push(node);
    }
}

However the compiler complains that the lifetimes in impl do not match this method in trait, which makes sense to me but if I try to implement it with <'a,'b:'a> then I get an error that lifetime 'a is already in scope. I've tried a bunch of possible ways to do this but there is something wrong with all of them.

Is there a solution to this problem without adding a lifetime to the trait ?

The problem with adding a lifetime to the trait is that I also have the following trait

pub trait ComponentsAlgorithm<G:Graph> {
    fn get_components(&self, graph: &G) -> Vec<HashSet<i32>>;
}

pub struct ComponentsAlgorithmOptions<G:Graph> {
    pub components_algorithm: Box<dyn ComponentsAlgorithm<G>>,
}

impl<G:Graph> ComponentsAlgorithmOptions<G> {
    pub fn new(algorithm_type: AlgorithmType) -> Self {
        let components_algorithm = create_components_algorithm(&algorithm_type);
        ComponentsAlgorithmOptions{
            components_algorithm,
        }
    }
}

and the lifetime would force the ComponentsAlgorithm to only live as long as the graph if I understand everything correctly.
However since the ComponentsAlgorithm is actually independent of the graph this doesn't seem to make much sense to me. Or is there something conceptually wrong with the second trait ?

You don't want this even if it were valid. 'a here is the lifetime name for "nodes referenced by the StandardGraph" (because you used it that way in impl<'a>, and by using &'a mut self you're saying "I demand that the graph be borrowed for as long as its nodes live", which makes it borrowed for the rest of its existence. You'd only be able to call add_node() once.

You are not obligated to use the same names everywhere. You can call the lifetime in the signature, or the lifetime in the impl, 'c or some more specific name to avoid the conflict.

However, this won't actually solve your original problem, because for all the lifetime annotations you've added, none of them actually require that the &Node live as long as you need it to. In order to impose that rule, you need to actually mention the lifetime in the trait, like this:

pub struct Node {}

pub trait Graph<'node> {
    fn add_node(&mut self, node: &'node Node);
}

pub struct StandardGraph<'a> {
    nodes: Vec<&'a Node>,
}

impl<'b> Graph<'b> for StandardGraph<'b> {
    fn add_node(&mut self, node: &'b Node) {
        self.nodes.push(node);
    }
}

The above code compiles. Note there are no lifetimes declared on &mut self — you usually don't need them and they're usually a mistake, because that lifetime is the lifetime of borrowing StandardGraph for this particular function call, not how long the StandardGraph lives.

Also note that I used various different lifetime names. These all end up serving the same purpose, but I used different names to illustrate when the names need to be the same (within the scope of a particular lifetime variable declaration) and when they don't. Also notice that lifetime names don't have to be single characters.


That should sort out your lifetime problems…

and the lifetime would force the ComponentsAlgorithm to only live as long as the graph if I understand everything correctly.

Ah. Well, some other advice I have for you will address that. It is usually a mistake to build data structures out of & references. In most cases, data structures should be built out of owned values, not references — just replace &Node with Node. (References are used for algorithms manipulating the data structures, not the data structures themselves.)

pub struct Node {}

pub trait Graph {
    fn add_node(&mut self, node: Node);
    
    // Functions that *return* nodes might return them by reference
    // fn get_node(&self, ...) -> &Node;
}

pub struct StandardGraph {
    nodes: Vec<Node>,
}

impl Graph for StandardGraph {
    fn add_node(&mut self, node: Node) {
        self.nodes.push(node);
    }
}

If you really do need borrowed nodes (unlikely), consider having the trait abstract over the type (being a reference type) instead of the lifetime:

pub trait Graph {
    type Node;
    fn add_node(&mut self, node: Self::Node);
}

pub struct SgNode {}
pub struct StandardGraph<'a> {
    nodes: Vec<&'a SgNode>,
}

impl<'a> Graph for StandardGraph<'a> {
    type Node = &'a SgNode;
    fn add_node(&mut self, node: &'a SgNode) {
        self.nodes.push(node);
    }
}
4 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.