Reference lifetimes borrowed value do not live long enough

I am new to rust and am trying to work through reference lifetimes. I am unable to understand why the program compiles if self.rate.insert(&vertex, inner_matrix) is uncommented.

pub struct Vertex {
  pub exchange: String,
  pub currency: String,
  pub last_updated: u64
}

impl Vertex {
  pub fn new(exchange: String, currency: String, last_updated: u64) -> Vertex {
    Vertex {
      exchange, currency, last_updated
    }
  }
}

impl Hash for Vertex {
  fn hash<H: Hasher>(&self, state: &mut H) {
    self.exchange.hash(state);
    self.currency.hash(state);
  }
}

impl PartialEq for Vertex {
  fn eq(&self, other: &Vertex) -> bool {
    self.exchange == other.exchange && self.currency == other.currency
  }
}

#[derive(Debug)]
pub struct Graph<'a> {
  vertices: HashSet<&'a Vertex>,
  rate: HashMap<&'a Vertex, HashMap<&'a Vertex, f64>>, // stores the edge weights between each pair of vertex
  next: HashMap<&'a Vertex, HashMap<&'a Vertex, &'a Vertex>>, // stores vertices to reconstruct the path for best rate from vertex i to j
}

impl<'a> Graph<'a> {
  pub fn new() -> Graph<'a> {
    Graph {
      vertices: HashSet::new(),
      rate: HashMap::new(),
      next: HashMap::new()
    }
  }

  pub fn add_vertex(&mut self, vertex: Vertex) {
    match self.vertices.get(&vertex) {
      Some(inner_matrix) => {
        // Do stuff
      },
      None => {
        let mut inner_matrix: HashMap<&Vertex, f64> = HashMap::new();
        inner_matrix.insert(&vertex, 0.0);

        // Error if uncomment any line below
        self.rate.insert(&vertex, inner_matrix);
        // self.vertices.insert(&vertex);
      }
    }
  }
}

Compiler error
impl<'a> Graph<'a> {
| – lifetime 'a defined here

142 | inner_matrix.insert(&vertex, 0.0);
| ^^^^^^^ borrowed value does not live long enough

145 | self.rate.insert(&vertex, inner_matrix);
| --------------------------------------- argument requires that vertex is borrowed for 'a

149 | }
| - vertex dropped here while still borrowed

References are not for storing things by reference (Box is). References are for borrowing objects that already permanently live elsewhere, and locking source of that object to be read-only.

In your case vertex given to the function is owned by that function, and the function will always destroy it when it ends. But you want that soon-to-be-destroyed object without a permanent home to be temporarily borrowed inside self.vertices that lives longer than this function call.

It’s equivalent of C code:

void add_vertex(Graph *self, Vertex *vertex) {
    insert(self, vertex);
    free(vertex); // added by compiler for owned types
}

Your solutions are:

  • If all Vertex objects are already stored elsewhere, outside of Graph and statically guarantee to always outlive Graph (in practice it means they all must have been created before Graph is created), then you can make add_vertex take a temporarily borrowed &Vertex.

  • otherwise take ownership of Vertex, and store actual Vertex in the HashMaps. If you want to store a pointer instead of struct, then Box<Vertex> is a plain pointer.

1 Like

Hi kornel, thank you for the swift and helpful reply.

Now I have a better understanding why my code doesn’t work. I admit that I haven’t come across the concept of Box, and will read up on it.

It should also be the same reason why it fails when I try to pass in &Vertex to add_vertex function?
How it works it that I create a Vertex from the calling function and pass a Vertex reference to add_vertex. When the calling function ends, both self.vertices and inner_matrix contains Vertex that have already been freed.

Since I intend to store vertices and rate and next holds the reference to all the Vertex objects, I will make vertices own the Vertex object, and store the references in rate and next.

Yes. Ownership and scopes are tied to memory management in Rust, so owned objects going out of scope will be freed automatically and can’t have references to them outlive them.

Just to clarify again after re-reading this part:

If all Vertex objects are already stored elsewhere, outside of Graph and statically guarantee to always outlive Graph (in practice it means they all must have been created before Graph is created), then you can make add_vertex take a temporarily borrowed &Vertex .

So making vertices own the Vertex, while rate and next holds a Vertex reference still wouldn’t make it.

pub struct Graph<'a> {
  vertices: HashSet<Vertex>,
  rate: HashMap<&'a Vertex, HashMap<&'a Vertex, f64>>,
  next: HashMap<&'a Vertex, HashMap<&'a Vertex, &'a Vertex>>
}

add_vertex function:

self.rate.insert(&vertex, inner_matrix);
self.vertices.insert(vertex);

I tried making rate and next hold Box<Vertex> instead of &'a Vertex. What happens after inserting vertex to rate is that its ownership is taken up by Box, and I am unable to add the vertex into next

It looks like I should rethink my data structure and create the Vertex outside of the struct, or not use struct at all.

One way is this:

let vertices: HashSet<Vertex>;
…
pub struct Graph<'a> {
  rate: HashMap<&'a Vertex, HashMap<&'a Vertex, f64>>,
  next: HashMap<&'a Vertex, HashMap<&'a Vertex, &'a Vertex>>
}

so that graph only references vertices stored elsewhere, and the borrow checker will limit usage of Graph to scope of vertices.

Another option is this:

pub struct Graph<'a> {
  vertices: HashSet<Arc<Vertex>>,
  rate: HashMap<Arc<Vertex>, HashMap<Arc<Vertex>, f64>>,
  next: HashMap<Arc<Vertex>, HashMap<Arc<Vertex>, Arc<Vertex>>>
}

Arc is an owning type, but has shared ownership, so the same Vertex can live in multiple hashsets/maps at the same time. By default in Rust ownership is unique — an object can exist in one place at a time only, which is how it knows when to free it.

However, you can’t have:

pub struct Graph<'a> {
  vertices: HashSet<Vertex>,
  rate: HashMap<&'a Vertex, HashMap<&'a Vertex, f64>>,
  next: HashMap<&'a Vertex, HashMap<&'a Vertex, &'a Vertex>>
}

because what if you put references from vertices into rate, and then called vertices.clear()? It’d free all vertices, and rate would end up full of dangling pointers. That’s called self-referential struct in Rust, and the borrow checker won’t allow it (the borrow checker rules guarantee you can’t make dangling pointers, and it’s not enough for the borrowcheker to have code that doesn’t make dangling pointers, but could). That’s why Arc may be needed, because it dynamically enforces you can’t make a dangling pointer.

1 Like

Ok now I understood I cannot have an immutable reference to an owned mutable object while that reference is still living.

What I did is to put vertices: HashSet<Vertex> in a struct Graph, and rate, next with Arc<Vertex> in another struct GraphResult

The reason why I want to put vertices in a struct is that I want to implement methods on it.

So in main function, I instantiate both Graph and GraphResult, create a Vertex object clone it twice and store it in rate and next of GraphResult and store the original Vertex object in vertices of Graph.

I feel this isn’t using the shared references feature of Arc, because Arc will take ownership of Vertex if I just create an Arc out of Vertex

Cloning of Arc<Vertex> gives you another Arc that shares the same Vertex (the vertex isn’t copied). From Rust’s perspective you own multiple Arc objects, so you can pass them around individually, but thanks to Arc's internal reference counting, there’s only one Vertex.

1 Like

My data structure looks like this

pub struct Graph {
    vertices: HashSet<Vertex>,
}

pub struct GraphResult {
  // stores the edge weights between each pair of vertex
  rate: HashMap<Arc<Vertex>, HashMap<Arc<Vertex>, f64>>,
  // stores vertices to reconstruct the path for best rate from vertex i to j
  next: HashMap<Arc<Vertex>, HashMap<Arc<Vertex>, Arc<Vertex>>>
}

In main function:

// 1. Create a vertex object
// 2. Create Arc vertex using Arc::new(vertex.clone())
// 3. Clone the Arc vertex and add it to `rate`
// 4. Add Arc vertex to `next`
// 5. Add vertex to `vertices`

I am unsure of whether I am using Arc properly. Should I be concerned about whether the Arc vertex are indeed a reference to the actual vertex object when I do step 2?

Your solution is technically correct.

But if you want to ensure there’s only one copy each vertex, then it has to be always Arc<Vertex> everywhere, so use HashSet<Arc<Vertex>>. Conversion of Vertex to Arc<Vertex> makes a copy (Vertex::clone() is a real clone, Arc::clone() is a cheap refcounting clone).

1 Like

Thank you for the help kornel! I think using Arc<Vertex> for all 3 data structures should be the way if I only want a single heap allocated Vertex. I make 2 clones for Arc<Vertex> for rate and next and store the converted Arc<Vertex> from Vertex in vertices.

For some reason, I miss the fact that conversion of Arc<Vertex> from Vertex is still the ‘source of truth’ rather than just a reference.