CODEWITHSUNDEEP
data-structuresrustmutabilityinterior-mutability
Aylei
Aylei

Reputation: 428

Is there a way to make an immutable reference mutable?

I want to solve a leetcode question in Rust (Remove Nth Node From End of List). My solution uses two pointers to find the Node to remove:

#[derive(PartialEq, Eq, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

// two-pointer sliding window
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy_head = Some(Box::new(ListNode { val: 0, next: head }));
        let mut start = dummy_head.as_ref();
        let mut end = dummy_head.as_ref();
        for _ in 0..n {
            end = end.unwrap().next.as_ref();
        }
        while end.as_ref().unwrap().next.is_some() {
            end = end.unwrap().next.as_ref();
            start = start.unwrap().next.as_ref();
        }
        // TODO: fix the borrow problem
        // ERROR!
        // start.unwrap().next = start.unwrap().next.unwrap().next.take();
        dummy_head.unwrap().next
    }
}

I borrow two immutable references of the linked-list. After I find the target node to remove, I want to drop one and make the other mutable. Each of the following code examples leads to a compiler error: 

// ERROR
drop(end); 
let next = start.as_mut().unwrap.next.take();

// ERROR
let mut node = *start.unwrap()

I don't know if this solution is possible to be written in Rust. If I can make an immutable reference mutable, how do I do it? If not, is there anyway to implement the same logic while making the borrow checker happy?

Upvotes: 19

Views: 13213

Answers (3)

zertyz
zertyz

Reputation: 705

Although the accepted answer does provide references for safer implementations for the OP specific problem, it is not entirely true that there isn't a way of changing data inside an immutable reference without incurring in Undefined Behavior.

If it was not possible, Mutexes couldn't be implemented in Rust. So, one must assume there is a UB-free way of doing it, which is useful outside Mutexes as well -- for instance, whenever you'll implement atomic synchronizations in persue of extra-speed.

The source of confusion I see everywhere may be in the mixing of the following concepts:

  1. Is the compiler generating the correct assembly code?
  2. Is my program still correct, according to Rust's security premises?

Of course, to transform & into &mut, you need unsafe code -- where Rust trusts you to know better, so the automated (2) guarantees will be turned off for the unsafe regions.

When upgrading an immutable reference, Undefined Behavior arises in (1), when the compiler makes optimizations that assume the data is read-only (like storing it into a set of registers, maybe).

That being said, I'll show two ways of doing it: the first introducing a UB (by not hinting the compiler) and the second doing it in the right way, as suggested by the most recent Rust nightly compier (1.72):

// DON'T DO IT! UNDEFINED BEHAVIOR -- it compiles in Rust stable 1.70, but might produce the wrong assembly
let ub_mutable_self = unsafe { &mut *((ref_self as *const Self) as *mut Self) };

// OK CODE: The Compiler Intrinsics `UnsafeCell` tells LLVM that read-only optimizations should not be used
struct MyStruct {
    data: UnsafeCell<u32>,
}

impl MyStruct {
    
    fn inc(&self) {
        let mutable_data = unsafe {&mut * self.data.get()};
        *mutable_data += 1;
    }
}

See it in the playground (and try the Miri analysis)

As a final note, I'd advise Rust's newcomers to not use this technique: it might be tempting to "by-pass" the wonderful Rust compiler checks, but those checks are there to tell when your program is wrong. There are always alternatives (in the language and in std::) to allow you to rethink your design and write elegant & correct code without using unsafe.

Upvotes: 0

snowsignal
snowsignal

Reputation: 466

The correct answer is that you should not be doing this. This is undefined behavior, and breaks many assumptions made by the compiler when compiling your program.

However, it is possible to do this. Other people have also mentioned why this is not a good idea, but they haven't actually shown what the code to do something like this would look like. Even though you should not do this, this is what it would look like:

unsafe fn very_bad_function<T>(reference: &T) -> &mut T {
    let const_ptr = reference as *const T;
    let mut_ptr = const_ptr as *mut T;
    &mut *mut_ptr
}

Essentially, you convert a constant pointer into a mutable one, and then make the mutable pointer into a reference.

Here's one example why this is very unsafe and unpredictable:

fn main() {
    static THIS_IS_IMMUTABLE: i32 = 0;
    unsafe {
        let mut bad_reference = very_bad_function(&THIS_IS_IMMUTABLE);
        *bad_reference = 5;
    }
}

If you run this... you get a segfault. What happened? Essentially, you invalidated memory rules by trying to write to an area of memory that had been marked as immutable. Essentially, when you use a function like this, you break the trust the compiler has made with you to not mess with constant memory.

Which is why you should never use this, especially in a public API, because if someone passes an innocent immutable reference to your function, and your function mutates it, and the reference is to an area of memory not meant to be written to, you'll get a segfault.

In short: don't try to cheat the borrow checker. It's there for a reason.

EDIT: In addition to the reasons I just mentioned on why this is undefined behavior, another reason is breaking reference aliasing rules. That is, since you can have both a mutable and immutable reference to a variable at the same time with this, it causes loads of problems when you pass them in separately to the same function, which assumes the immutable and mutable references are unique. Read this page from the Rust docs for more information about this.

Upvotes: 18

Shepmaster
Shepmaster

Reputation: 431909

Is there a way to make an immutable reference mutable?

No.

You could write unsafe Rust code to force the types to line up, but the code would actually be unsafe and lead to undefined behavior. You do not want this.

For your specific problem, see:

Upvotes: 13

Related Questions