One more tricky problem about lifetime, pls help

help
1

I need to implement a struct most like graph maybe with circle. In another post, the simplified codes have been successfully compiled. but here comes a new problem
the original code is as following

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

It is compiled successfully as far. but when I tried to next step, here comes a new problem

struct Unit <'a> {
    data: Vec<String>,
    ptr_data: Vec<&'a Self>,
}
struct UnitStorage <'a> {
    storage: Vec<Box<Unit<'a>>>,
}
impl <'a> UnitStorage <'a> {
    fn recusive(&'a mut self, unit: &'a mut Unit<'a>) {
        for _ in &unit.data { //only here are different with code above
            let new_unit = Box::new(Unit {data: vec![], ptr_data: vec![] });
            self.storage.push(new_unit);
            unit.ptr_data.push(&self.storage[self.storage.len() - 1]);
        }
    }
}

Here is Playground

The compiler complain

error[E0502]: cannot borrow `self.storage` as mutable because it is also borrowed as immutable
  --> src/lib.rs:14:13
   |
10 | impl <'a> UnitStorage <'a> {
   |       -- lifetime `'a` defined here
...
14 |             self.storage.push(new_unit);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
15 |             unit.ptr_data.push(&self.storage[self.storage.len() - 1]);
   |             ---------------------------------------------------------
   |             |                   |
   |             |                   immutable borrow occurs here
   |             argument requires that `self.storage` is borrowed for `'a`

error: aborting due to previous error

And the error not because that unit has been borrowed at clause for _ in &unit.data while mut borrowed at unit.ptr_data.push(). A simple case has proved it

struct TestA {
  data_1: Vec<String>,
  data_2: Vec<String>,
}
fn main() {
   let a = TestA { data_1: vec![], data_2: vec![] };
   for _ in a.data_1 {
       a.data_2.push("hello".to_owned());
   }
}

It will be compiled sucessfully.

So, why this code snippet does not complie?
I always confused with lifetime in Rust, hope get help in enthusiastic Rust community.
Any help will be appreciated, thanks.

2

.push() may grow the vector and moves all the elements into another memory location, which makes all the &'a Unit<'a>s dangling. If you can make it sure units never be removed from the storage, try store the index of units instead.

3

Thanks, this is a bug, but it not the cause that compiled error. I have corrected in the original post this problem you metioned, thanks.
But in the first code snippet, the compiler pass through the code with this bug, maybe the lifetime mechansim works?

4

This is one of the problems the lifetime system was invented to prevent. To be specific the problems is the concurrency problem, which doesn't necessarily implies parallelism. The lifetime system uses a few simple rules to prevent wide range of concurrency bugs. Note that the simple rule doesn't means easy to master - like chess.

  1. A variable owns its value, which is dropped recursively when its scope ends if not already moved out.
  2. A value can't be moved or dropped during at least one of its borrows are active.
  3. &mut T is an exclusive reference to the underlying value T. While the exclusive reference is alive, no other references to the same value can be active.
  4. &T is an shared reference to the underlying value T. You can have as much as shared references to the same value with 0 runtime cost, but normally you can't modify the value with its shared reference.

It compiles, but I'm pretty sure you can't call it in practical code. The method takes self: &'a mut UnitStorage<'a>, and &'a mut Type<'a> is a common symptom of misunderstanding how the lifetime system works. The type Type<'a> can only be valid for the lifetime 'a, but it's borrowed exclusively for the lifetime 'a which is its entire lifetime. The method borrowed it exclusively for its entire lifetime, so after this method call it can't be used at all though technically it doesn't moved out.

5

Thanks for reply. The first code snippet does work, maybe refer to this blog
Then I confused why the second code snippet is not compiled?

6

hey there ^^ maybe you give RefCell a try?

Here is an example:

a --> b --> c
^-----|     |
^-----------|

Does this show your desired behavior?

use std::cell::RefCell;

struct Unit<'a> {
    data: String,
    ptrs: RefCell<Vec<&'a Self>>,
}

impl Unit<'_> {
    fn new_with(data: &str) -> Self {
        Self {
            data: String::from(data),
            ptrs: RefCell::new(Vec::new()),
        }
    }
}

fn main() {
    let unit_a = Unit::new_with("a");
    let unit_b = Unit::new_with("b");
    let unit_c = Unit::new_with("c");
    // a --> b
    unit_a.ptrs.borrow_mut().push(&unit_b);
    // b --> c
    unit_b.ptrs.borrow_mut().push(&unit_c);
    // b --> a
    unit_b.ptrs.borrow_mut().push(&unit_a);
    // c --> a
    unit_c.ptrs.borrow_mut().push(&unit_a);

    // a --> b --> c
    // ^-----|     |
    // ^-----------|

    assert_eq!(unit_a.data, "a");
    assert_eq!(unit_b.data, "b");
    assert_eq!(unit_c.data, "c");
    assert_eq!(unit_a.ptrs.borrow()[0].data, "b");
    assert_eq!(unit_b.ptrs.borrow()[0].data, "c");
    assert_eq!(unit_b.ptrs.borrow()[1].data, "a");
    assert_eq!(unit_c.ptrs.borrow()[0].data, "a");

    println!("unit_a.data: {}", unit_a.data);
    println!("unit_b.data: {}", unit_b.data);
    println!("unit_a.ptrs.borrow()[0].data: {}", unit_a.ptrs.borrow()[0].data);
    println!("unit_b.ptrs.borrow()[0].data: {}", unit_b.ptrs.borrow()[0].data);
    println!("unit_b.ptrs.borrow()[1].data: {}", unit_b.ptrs.borrow()[1].data);
    println!("unit_c.ptrs.borrow()[0].data: {}", unit_c.ptrs.borrow()[0].data);
}
7

It doesn't work. The blog post uses &'a Arena<'a>, which doesn't have the problem &'a mut Type<'a> have as &T is covariant over T but &mut T is invariant over T.

8

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.