What is the best way to resolve mutable borrow after immutable borrow, IF there is no perceived reference conflict

Question

This question popped into my head (while I wasn't programming), and it actually made me question a lot of things about programming (like in C++, C#, Rust, in particular).

I want to point out, I'm aware there is a similar question on this issue: Cannot borrow as mutable because it is also borrowed as immutable. But I believe this question is aiming at a particular situation; a sub-problem. And I want to better understand how to resolve a thing like this in Rust.

The "thing" that I realised recently was that: "If I have a pointer/reference to an element in a dynamic array, and then I add an element, causing the array to expand and reallocate, that would break the pointer. Therefore, I need a special refererence that will always point to the same element even if it re-allocates". This made me start thinking differently about a lot of things. But outside of that, I am aware that this problem is trivial to experienced c++ programmers. I have simply not come across this situation in my experiences, unfortunately.

So I wanted to see if Rust either had an existing 'special type' for this type of issue, and if not, what would happen if I made my own (for testing). The idea is that this "special pointer" would simply be a pointer to the Vector (List) itself, but also have a i32 field for the index; so it's all bundled under 1 variable that can be 'dereferenced' whenever you need.

Note: "VecPtr" is meant to be a immutable reference.

struct VecPtr<'a, T> {
    vec: &'a Vec<T>,
    index: usize
}

impl<T: Copy> VecPtr<'_, T> {
    pub fn value(&self) -> T {
        return self.vec[self.index];
    }
}

fn main() {
    let mut v = Vec::<i32>::with_capacity(6);

    v.push(3);
    v.push(1);
    v.push(4);
    v.push(1);

    let r = VecPtr {vec: &v,index: 2};
    let n = r.value();
    println!("{}",n);

    v.push(5); // error!
    v.push(9); // error!
    v.push(6); // re-allocation triggered // also error!

    let n2 = r.value();
    println!("{}",n2);

    return;
}

So the above example code is showing that you can't have an existing immutable reference while also trying to have a mutable reference at the same time. good!

From what I've read from the other StackOverflow question, one of the reasons for the compiler error is that the Vector could re-allocate it's internal array at any time when it is calling "push". Which would invalidate all references to the internal array. Which makes 100% sense. So as a programmer, you may desire to still have references to the array, but they are designed to be a bit more safer. Instead of a direct pointer to the internal array, you just have a pointer to the vector itself in question, and include an i32 index so you know the element you are looking at. Which means the dangling pointer issue that would occur at v.push(6); shouldn't happen any more. But yet the compiler still complains about the same issue. Which I understand.

I suppose it's still concerned about the reference to the vector itself, not the internals. Which makes things a bit confusing. Because there are different pointers here that the compiler is looking at and trying to protect. But to be honest, in the example code, the pointer to vec itself looks totally fine. That reference doesn't change at all (and it shouldn't, from what I can tell).

So my question is, is there a practice at which you can tell the compiler your intentions with certain references? So the compiler knows there isn't an issue (other than the unsafe keyword).

Or alternatively, is there a better way to do what I'm trying to do in the example code?

After some more research

It looks like one solution here would be to use reference counting Rc<T>, but I'm not sure that's 100% it.

I would normally not ask this question due to there being a similar existing question, but this one (I think) is investigating a slightly different situation, where someone (or me) would try to resolve an unsafe reference situation, but the compiler still insists there is an issue.

Answer 1

I guess the question comes down to this: would you find this acceptable?

fn main() {
    let mut v = Vec::<i32>::with_capacity(6);

    v.push(3);
    v.push(1);
    v.push(4);
    v.push(1);

    let r = VecPtr { vec: &v, index: 2 };
    let n = r.value();
    println!("{}",n);

    v[2] = -1;

    let n2 = r.value(); // This returned 4 just three lines ago and I was 
                        // promised it wouldn't change! Now it's -1.
    println!("{}",n2);
}

Or this

fn main() {
    let mut v = Vec::<i32>::with_capacity(6);

    v.push(3);
    v.push(1);
    v.push(4);
    v.push(1);

    let r = VecPtr { vec: &v, index: 2 };
    let n = r.value();
    println!("{}",n);

    v.clear();

    let n2 = r.value(); // This exact same thing that worked three lines ago will now panic.
    println!("{}",n2);
}

Or, worst of all:

fn main() {
    let mut v = Vec::<i32>::with_capacity(6);

    v.push(3);
    v.push(1);
    v.push(4);
    v.push(1);

    let r = VecPtr { vec: &v, index: 2 };
    let n = r.value();
    println!("{}",n);

    drop(v);

    let n2 = r.value(); // Now you do actually have a dangling pointer.
    println!("{}",n2);
}

Rust's answer is an emphatic "no" and that is enforced in the type system. It's not just about the unsoundness of dereferencing dangling pointers, it's a core design decision.

Can you tell the compiler your intentions with certain references? Yes! You can tell the compiler whether you want to share your reference, or whether you want to mutate through it. In your case, you've told the compiler that you want to share it. Which means you're not allowed to mutate it anymore. And as the examples above show, for good reason.

For the sake of this, the borrow checker has no notion of the stack or the heap, it doesn't know what types allocate and which don't, or when a Vec resizes. It only knows and cares about moving values and borrowing references: whether they're shared or mutable and for how long they live.

Now, if you want to make your structure work, Rust offers you some possibilities: One of those is RefCell. A RefCell allows you to borrow a mutable reference from an immutable one at the expense of runtime checking that nothing is aliased incorrectly. This together with an Rc can make your VecPtr:

use std::cell::RefCell;
use std::rc::Rc;

struct VecPtr<T> {
    vec: Rc<RefCell<Vec<T>>>,
    index: usize,
}

impl<T: Copy> VecPtr<T> {
    pub fn value(&self) -> T {
        return self.vec.borrow()[self.index];
    }
}

fn main() {
    let v = Rc::new(RefCell::new(Vec::<i32>::with_capacity(6)));

    {
        let mut v = v.borrow_mut();
        v.push(3);
        v.push(1);
        v.push(4);
        v.push(1);
    }

    let r = VecPtr {
        vec: Rc::clone(&v),
        index: 2,
    };
    let n = r.value();
    println!("{}", n);

    {
        let mut v = v.borrow_mut();
        v.push(5);
        v.push(9);
        v.push(6);
    }

    let n2 = r.value();
    println!("{}", n2);
}

I'll leave it to you to look into how RefCell works.