Good old reference problem :)

1

Hello,

I stop coding with rust for few month and I try to do some simple trick ( At least in C and C++ ^^).
I have the following code in rust

struct A<'x>
{
    ref_b : Vec<&'x B<'x>>
}

impl<'x> A<'x>{
    pub fn new() -> A<'x>{
        A {
            ref_b : Vec::default(),
        }
    }
    pub fn push_b(&mut self, b : &'x B<'x>){
        self.ref_b.push(b);
    }
}

struct B<'x>
{
    ref_a : Vec<&'x A<'x>>
}
impl<'x> B<'x>{
    pub fn new() -> B<'x>{
        B {
            ref_a : Vec::default(),
        }
    }
    pub fn push_a(&mut self, a : &'x A<'x>){
        self.ref_a.push(a);
    }
}

struct C<'x>
{
    pub all_a : Vec<A<'x>>,
    pub all_b : Vec<B<'x>>,
}

impl<'x> C<'x>{
    pub fn new() -> C<'x>{
        C {
            all_a : Vec::default(),
            all_b : Vec::default()
        }
    }

    pub fn add_link_a_b(&mut self, i_a:usize, i_b:usize)
    {
        let b_ref = &mut self.all_b[i_b];
        let a_ref = &mut self.all_a[i_a];
        a_ref.push_b(b_ref);
        b_ref.push_a(a_ref);
    }
}


fn main(){
    let mut c = C::new();
    c.all_a.push(A::new());
    c.all_b.push(B::new());
    c.add_link_a_b(0, 0);
}

I have the following well known error:

error: lifetime may not live long enough
  --> <source>:50:9
   |
38 | impl<'x> C<'x>{
   |      -- lifetime `'x` defined here
...
46 |     pub fn add_link_a_b(&mut self, i_a:usize, i_b:usize)
   |                         - let's call the lifetime of this reference `'1`
...
50 |         a_ref.push_b(b_ref);
   |         ^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'x`

error[E0502]: cannot borrow `*b_ref` as mutable because it is also borrowed as immutable
  --> <source>:51:9
   |
38 | impl<'x> C<'x>{
   |      -- lifetime `'x` defined here
...
50 |         a_ref.push_b(b_ref);
   |         -------------------
   |         |            |
   |         |            immutable borrow occurs here
   |         argument requires that `*b_ref` is borrowed for `'x`
51 |         b_ref.push_a(a_ref);
   |         ^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error: aborting due to 2 previous errors

I try to do it but I'm stuck. How can i do a simple thing like this without dynamic memory allocation like Rc, Arc, etc....?

2

You have a fun notion of “simple thing” :sweat_smile:

You’re trying to write a struct with quite some complicated structure of interior pointers. Rust is best at expressing data structures that are tree-shaped. Though, if C or C++ are the measure to beat, one can of course also try to use unsafe code and raw pointers in Rust, too.

Moreover, your API is already set up for becoming a bit of a dangling references factory really easily. Imagine you pushed some more elements like

fn main(){
    let mut c = C::new();
    c.all_a.push(A::new());
    c.all_b.push(B::new());
    c.add_link_a_b(0, 0);
    // let's do it one more time!
    c.all_a.push(A::new());
    c.all_b.push(B::new());
    c.add_link_a_b(1, 1);
}

then you’re already risking that the new round of all_a.push+all_b.push could have made the respective Vec grow, moved the old A and/or B value to a new place in memory, and made the existing &'x A<'a> or &'x B<'a> dangling.

5 Likes
3

The code I show is just a simple exemple. Not the real one.
In the real code, both Vec are already filled in a 1st step and dependencies are resolved in a 2nd step.
Here the struct C do not allowed the end-user to modifiy the list, just to request some A and B and to take non mutable references on it.

I find a way with Vec<*const A> and Vec<*const B> and some unsafe dereferencing.
My question was more like : Can I do the same with non unsafe and no dynamic allocation in Rust?

4

Maybe like this:

use elsa::FrozenVec;

struct A<'x>
{
    ref_b : FrozenVec<&'x B<'x>>
}

impl<'x> A<'x>{
    pub fn new() -> A<'x>{
        A {
            ref_b : FrozenVec::default(),
        }
    }
    pub fn push_b(&self, b : &'x B<'x>){
        self.ref_b.push(b);
    }
}

struct B<'x>
{
    ref_a : FrozenVec<&'x A<'x>>
}
impl<'x> B<'x>{
    pub fn new() -> B<'x>{
        B {
            ref_a : FrozenVec::default(),
        }
    }
    pub fn push_a(&self, a : &'x A<'x>){
        self.ref_a.push(a);
    }
}

struct C<'x>
{
    pub all_a : Vec<A<'x>>,
    pub all_b : Vec<B<'x>>,
}

impl<'x> C<'x>{
    pub fn new() -> C<'x>{
        C {
            all_a : Vec::default(),
            all_b : Vec::default()
        }
    }

    pub fn add_link_a_b(&'x self, i_a:usize, i_b:usize)
    {
        let b_ref = &self.all_b[i_b];
        let a_ref = &self.all_a[i_a];
        a_ref.push_b(b_ref);
        b_ref.push_a(a_ref);
    }
}

Do note that this makes add_link_a_b take a maximally long borrow on self of type &'x C<'x>, with invariant 'x, so you can’t do anything in terms of mutating or moving with that same C<'x> value anymore; only “immutable” access (but the contained FrozenVec can still grow nonetheless, because of interior mutability).

5

Three answers.

  • What's the real use case? The API you're making reminds me of petgraph::Graph.

  • The problem you're hitting is the cycles. Rust's borrow checker doesn't love reference cycles. But you can work around that, using an arena to solve the lifetime issues and RefCell to solve mut access.

  • But honestly, that's not what I'd do. Sometimes in cases where, as a C++ programmer, I used to reach for raw pointers all the time, in Rust it makes more sense to use :sparkles: integer IDs :sparkles:.

    Yeah, they do result in extra bounds checks, but that is usually negligible in practice. And there are benefits: storing the actual data in a Vec is great for locality, plus integer IDs can be any convenient size (it's hard to make a pointer fit in 32 bits on a 64-bit platform).

3 Likes
6

&mut isn't just mutable, it's exclusive. And this exclusivity is applied very broadly, recursively, for as long as any reference with that lifetime may exist. Rust is super very serious about enforcing the exclusivity, and it's going to forbid everything anywhere that could potentially violate it.

When you write let b_ref = &mut self.all_b you're not just getting mutable reference, you're blocking all access to all of self.all_b's content from anywhere, in any way, other than through this b_ref. This b_ref is now the only place in the whole program that can access self.all_b. Rust will not allow anything to even look at self.all_b until the b_ref is gone. If you make b_ref have a lifetime visible externally, such as the 'x being on the type, then the loan of b_ref will extend to that larger scope and won't count as being gone until everything related to this lifetime 'x is proven gone and inaccessible (and it's easy to create circular requirements that forbid objects from being ever used again, because their exclusive loan must outlive themselves).
This also affects borrowing through &mut self methods, which exclusively borrow all of self's fields on principle, even fields the method doesn't use. When you borrow a field through &mut self.all_b, then Rust has to block all other method calls that may access self to be sure nothing else can look at the borrowed all_b field in any way.

As you can see, &mut virally paralyzing everything it may touch is not a good way to keep long-lived references to data. Rust references aren't general-purpose pointers. They don't store data, they forbid keeping it. They restrict access. They're locks on fields and objects, enforced at compile time. They exist to have mutable arguments in functions, with a guarantee the pointer can't be saved anywhere. They exist to freeze collections while they're iterated, to prevent iterator invalidation problem. They can be used to prevent data races and ensure different threads can never ever have a mutable reference to the same object, but they are a wrong tool for building graphs.

If you need to work with data within a statically limited scope (basically limited to some function call, and nothing that can outlive that call), then & shared temporary references are probably still not the right thing, still not general-purpose pointers, but they're less restrictive and at least possible to use in limited situations. Their lifetime can be shortened (but never extended), and they can co-exist with each other. You can mutate through the & shared references by using Cell, RefCell, Atomic or Mutex. To create them, you're going to need an arena/object pool that internally has to use unsafe to fudge the lifetimes and promise the borrow checker it will not allow deletion of objects for as long as they're borrowed from the arena.

If you use indexes (could be generational ones), you can implement an arena without involving the borrow checker.

And you can use Rc/Arc or Box to have references/pointers that aren't restricted by lifetimes.

7

I just go indexes
Thank you

1 Like