A tricky problem about lifetime

help
1

I have encounter another problem about lifetime, the lifetime of Rust always confused me...
simplified code as follow

struct Unit<'a> {
  data: String,
  ptr_data: Vec<&'a Self>,
}
struct UnitStorage <'a> {
  storage: Vec<Unit<'a>>,
}
impl <'a> UnitStorage<'a> {
  fn recusive(&mut self, unit: &mut Unit<'a>) {
     let new_unit = Unit {data: "hello".to_owned(), ptr_data: vec![]};
     self.storage.push(new_unit);
     unit.ptr_data.push(&self.storage[self.storage.len() - 1]); 
  }
}

Playground Is Here

These codes compile error

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements

I thought that the lifetime of new_unit and its ref are all 'a, as same as lifetime of struct UnitStorage
But why does it compile error? Or how can I implement the same function?
Any help will be appreciated, thanks.

2

You are unlikely to get this structure to work. What are you actually trying to do?

3

I agree that it would be easier to give meaningful help if we know what you are trying to make. There are more than one solution that all have trade-offs.

But just to try to explain the errors, let's look at a version of your function with explicit lifetime parameters added in:

struct Unit<'a> {
  data: String,
  ptr_data: Vec<&'a Self>,
}
struct UnitStorage <'a> {
  storage: Vec<Unit<'a>>,
}

impl <'a> UnitStorage<'a> {
  fn recusive<'self, 'unit>(&'self mut self, unit: &'unit mut Unit<'a>) {
     let new_unit = Unit {data: "hello".to_owned(), ptr_data: vec![]};
     self.storage.push(new_unit);
     unit.push(self.storage[self.storage.len() - 1]); 
  }
}

This is pretty much how the borrow checker is treating it. You have the two lifetimes that I have named 'self and 'unit to show what they are borrowing from. They could be anything, as far as the compiler knows, and not necessarily the same as 'a.

In your first two lines, you create a Unit that, through inference, are set to hold references that's valid for the rest of 'a. That's all good for now, since the ptr_data is empty, but would also be fine if you added some explicitly 'a marked references to it.

The problem occurs at the last line. You are borrowing from self.storage with an even shorter lifetime (let's name it 'index), that's at most valid for the rest of 'self, where it was borrowed from. Note that this is not 'a, just some lifetime that happens to exist during a period 'a because 'self happens to exist during a period of 'a. But both 'index and 'self may end before 'a ends. That's why it's not assignable as 'a.

That's why it's complaining.

At this point it may be tempting to try fn recusive(&'a mut self, unit: &mut Unit<'a>), so let me continue the train of thought.

This would force the borrow to be valid for 'a and will actually compile. We are not trying to pass anything off for what it isn't there, since everything is explicitly borrowed from 'a. But we will not be able to use the function as you may expect.

This will not work, no matter how you turn it, since it requires two mutable references to storage:

let mut storage = UnitStorage { storage: vec![] };
storage.storage.push(Unit { data: "first".to_owned(), ptr_data: vec![] });
storage.recusive(&mut storage.storage[0]); // borrows `storage` as mut twice here

This boils down to having UnitStoreage store a reference to itself. That's instant headache in Rust because you can't make the &mut borrow after the & borrow you want to store.

Fun fact is that you can use the function if you can store the first Unit somewhere else. Let's try with a separate Vec. We can call it once:

let mut arena = Vec::new();
let mut storage = UnitStorage { storage: vec![] };
arena.push(Unit { data: "first".to_owned(), ptr_data: vec![] });
storage.recusive(&mut arena[0]);

...but we can't do it again because storage is still borrowed by the first call:

let mut arena = Vec::new();
let mut storage = UnitStorage { storage: vec![] };
arena.push(Unit { data: "first".to_owned(), ptr_data: vec![] });
storage.recusive(&mut arena[0]);
storage.recusive(&mut arena[0]); // Already borrowed as mut!

In fact, storage is completely inaccessible now while arena is still around.

That's because when we are saying fn recusive(&'a mut self, unit: &mut Unit<'a>) we are telling the compiler that a call to recusive need to borrow self for the remainder of 'a to avoid invalid references, since everything we borrow from self should be possible to store in unit. And 'a lasts for as long as arena is around, since that's where we put the Unit that now borrows from storage.

4

It's not possible to implement an arena in safe Rust, because the borrow checker can't know that you're not planning to remove elements from the vector.

However, it's doable with a bit of unsafe. There are a few crates for that.

The second issue is that you can't store arena in the same struct as elements borrowing from the arena. This creates a self-referential struct. You'll need to make the arena first, and the pass it as an argument to functions that need it, or store it by reference in a struct, but not by value.

5

Sorry, I make a mistake with the codes, the last line should be

  unit.ptr_data.push(&self.storage[self.storage.len() - 1]);

I have corrected it in the original post. The code in playground is correct to show the case.

I want to implement a case most like a graph, maybe also exist circle.

6

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.