CODEWITHSUNDEEP
rustlifetimeborrow-checker
chs
chs

Reputation: 652

Is there an idiomatic way to keep references to elements of an ever-growing container?

I'm trying to write a container for objects of type T which provides access to references &T to the stored objects (I want to avoid making copies). Since the container only ever grows during its lifetime, the lifetime of the returned references &T should be the same as for the container.

The closest I got so far was to use Box<T> objects internally in my container and use Box<T>.as_ref() to return references to these objects. Then, however, I run into the same problem as in this minimal example:

fn main() {
    let mut v = vec![Box::new(1)]; // line 1
    let x = v[0].as_ref();         // line 2: immutable borrow occurs here
    println!("x = {:?}", x);       // line 3
    v.push(Box::new(2));           // line 4: mutable borrow occurs here -> error
    println!("x = {:?}", x);       // line 5
}

I understand that it would be unsound to use x in line 5 if it had been deleted from v during the the mutable borrow. But that's not the case here, and it'll never be for my container. If there's no safe way to express this in Rust, how could I "repair" the example (without copying x)?

Upvotes: 2

Views: 1230

Answers (3)

oli_obk
oli_obk

Reputation: 31263

Unfortunately there's nothing "ready to use" for your usecase, but you can write a wrapper around Vec that does unsafe stuff to give you the features you need while keeping the guarantees that Rust needs

struct BoxVec<T>(Vec<Box<T>>);

impl<T> BoxVec<T> {
    pub fn new() -> Self { BoxVec(Vec::new()) }
    pub fn push<'a>(&'a mut self, t: T) -> &'a mut T {
        let mut b = Box::new(t);
        let t: &'a mut T = unsafe { std::mem::transmute::<&mut T, &'a mut T>(&mut b) };
        self.0.push(b);
        t
    }
    pub fn pusher<'a>(&'a mut self) -> BoxVecPusher<'a, T> {
        BoxVecPusher(self)
    }
}

struct BoxVecPusher<'a, T: 'a>(&'a mut BoxVec<T>);

impl<'a, T> BoxVecPusher<'a, T> {
    fn push<'b>(&'b mut self, t: T) -> &'a mut T {
        let mut b = Box::new(t);
        let t: &'a mut T = unsafe { std::mem::transmute::<&mut T, &'a mut T>(&mut b) };
        (self.0).0.push(b);
        t
    }
}

The guarantees I chose is that you can't index into the Pusher, but you get a mutable reference to the newly pushed object. Once to release the pusher, you can go back to indexing.

An example usage is

let mut v = BoxVec::new();
v.push(1);
let x = v[0];
let mut p = v.pusher();
let i = p.push(2);
p.push(3); // works now
let y = v[0]; // denied by borrow checker

Full example in the playground

Upvotes: 2

Chris Emerson
Chris Emerson

Reputation: 14051

As @ker's answer says, just because you only grow a container doesn't mean references stay valid, as the memory can be reallocated.

Another solution if you're only growing the container is to just store indices instead of references:

fn main() {
    let mut v = vec!["Foo"];    // line 1
    let x = 0;                  // line 2: just store an index.
    println!("x = {:?}", v[x]); // Use the index as needed
    v.push("bar");              // line 4: No problem, there are no references.
    println!("x = {:?}", v[x]); // line 5: use the index again.
}

Upvotes: 5

oli_obk
oli_obk

Reputation: 31263

The problem is that your Vec might run out of memory. If that happens, it has to allocate a new (bigger) chunk of memory, copy all the old data over, and delete the old memory allocation. At that point all references into the old container would become invalid.

You could design a rope (a Vec of Vec), where, once an inner vec is full, you just create a new one, thus never invalidating pointers just by pushing.

That would require some unsafe code and very careful analysis of the borrowing rules that you have to keep up.

Upvotes: 2

Related Questions