Lifetime cannot be inferred by compiler

Im trying to make a grid of Elements so every Element can have references to its neighbors.
My Element looks like

struct Element<'a> {
    value: u32,
    neighbors: Vec<&'a Element<'a>>, // this is the source of all evil I think. But others can confirm. 
}

struct Vec2D<'a> {
    vec_2d: Vec<Element<'a>>,
    col: usize,
}

impl<'a> Vec2D<'a> {
    fn new(col: usize) -> Self {
        Vec2D {
            vec_2d: Vec::new(),
            col,
        }
    }

    fn add(&mut self, element: u32) {
        let mut e1 = Element {
            value: element,
            neighbors: Vec::new(),
        };
        let mut e2 = Element {
            value: element,
            neighbors: Vec::new(),
        };

        e1.neighbors.push(&e2);
        e2.neighbors.push(&e1);

        self.vec_2d.push(e1);
        self.vec_2d.push(e2);
    }
}

fn main() {
    let mut vec_2d = Vec2D::new(5);

    vec_2d.add(1);
}

Error is

Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:86:28
   |
86 |         let last_element = self.vec_2d.last_mut().unwrap(); //last must be there.
   |                            ^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 28:5...
  --> src/main.rs:28:5
   |
28 |     fn calculate_neighbors(&mut self) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:86:28
   |
86 |         let last_element = self.vec_2d.last_mut().unwrap(); //last must be there.
   |                            ^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 11:6...
  --> src/main.rs:11:6
   |
11 | impl<'a> Vec2D<'a> {
   |      ^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:91:37
   |
91 |             neighbor.neighbors.push(last_element);
   |                                     ^^^^^^^^^^^^

error: aborting due to previous error

Can someone explain the error and fix?

Here is the Rust playground link https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=c45e02f1e5bc5ca8b66aa77a41323d44

What if self.vec_2d.last_mut() and self.vec_2d.get_mut(e) refer to the same element? You would get two mutable references to the same element, which is not allowed.

Yeah. But that's not what Im doing. Also the error points to lifetimes.

I also think it has to do with this Element<'a> more specifically neighbors: Vec<&'a Element<'a>>.
Is it even possible to create Element and its neighbor that have the same lifetime 'a? I dont think so because they both will have different lifetimes.

Is my understanding correct?

There is no way for borrowck to prove that they will never refer to the same element. Another problem with your code is that when you use Vec2D<'a> you are saying that the inner elements neighbors will live for an arbitrary caller defined lifetime 'a. They however only live as long as the Vec2D<'a>, which can be shorted. Without unsafe code it is not possible to create self-referential values like this one. You could store indices into vec_2d in neighbors instead.

1 Like

It will be difficult to represent this with references. I recommend that you store the neighbors by index, not be reference.

The slab crate facilitates this pattern. Instead of using references, you could your elements in a Slab from the https://crates.io/crates/slab crate, which will let you give them indices, then store your neighbors by index.

It would look maybe like this:

struct Element {
    value: u32,
    neighbors: Vec<usize>,
}

struct Vec2d {
    vec_2d: Slab<Element>,
    col: usize,
}

Well I do want self-references because if Im a neighbor of someone then my neighbor is my neighbor too.
Also the Elements are owned by Vec in Vec2d. So wouldnt all the Elements have same lifetime ie of Vec?

I can solve this by storing indices but Im trying to understand nuances of lifetimes.

When Vec2D::vec_2d grows as a result of pushing new elements beyond its current capacity, all of the Elements may move and all of the references you've stored would become invalid.

With the 'a you are declaring that the lifetime is bigger than Vec2d. Imagine for example Vec2d<'static>. That would require all neighbors to live forever.

Yeah I can store indices but Im learning nuances of lifetimes. I just dont want to fix the problem without understanding the problem at hand.

References typically allow a local variable to reference a different local variable. Giving a struct a lifetime typically allows (requires) the struct to reference a local variable. I don't think references are the right tool for the job here.

Good point. Is that why what Im doing is disallowed or it is disallowed because of self-references?

There are times when the borrow checker is overzealous and prevents you from doing something that is actually safe. This is not one of those times. Your code is unsound because calling push inside add may cause the Vec to reallocate, which would move all the Elements and invalidate all the references.

The error manifests inside calculate_neighbors because that's where you are trying to store a short-lived reference to self inside self (which is supposed to contain long-lived references of lifetime 'a). But add is where it would actually lead to UB.

This is why people say not to use self-referential structs. It's very easy to make a mistake like this, which is why lifetimes exist. The Rust compiler prevented you from making a grave error. There are situations where using self-referential structs is not an error, but they require an extra degree of caution because most of the things you normally do with a struct come with extra rules when it might contain a reference to itself.

2 Likes

Well, basically, you're trying to create an interconnected matrix of data with references to each other. Since each element will presumably be referenced by several other elements, that makes it difficult to mutate the structure, since you can't mutate something while there's an immutable reference to it.

Yeah @trentj gave a good more detailed explanation of how, adding more elements could trigger an re-allocating, making the existing references point to the wrong memory address.

Dumb question: I have heard the usage in this forum a lot but what exactly is a UB?

1 Like

So I guess my question should have been: how do I store self-references? What is the extra degree of caution?

No problem. It's "undefined behavior," basically it means the program is very broken, the compiler is allowed to assume without proof that undefined behavior will not occur, so when it does occur, the compiler's output could do any possible bad behavior. In practice, it's typically things like corrupting memory, jumping into the wrong machine code paths, etc.

2 Likes

Oh, sorry, that's a C-ism. UB stands for "undefined behavior" and it basically means that the code isn't guaranteed to do anything meaningful, so it might do something like crash, or mistakenly return wrong data, or hang forever but only on Tuesdays, or eat your laundry. Basically the worst kind of bug is one that causes undefined behavior because, like a black hole, it can't be directly observed -- you can only see the wreckage it causes in its vicinity.

2 Likes

I think this blob post is a decent discussion of UB: https://blog.llvm.org/posts/2011-05-13-what-every-c-programmer-should-know/

But, notably, one of the most important ideas of Rust is that, any program which compiles, and doesn't use unsafe, is defined behavior.

1 Like

I modified my question. The errors Im getting make perfect sense and it points to your comments.

I guess I was confused by the actual error the compiler threw with my original code.

Thanks all.

1 Like