Is there a way to make an immutable reference mutable?

Question

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?

Superjacent

Converting an immutable reference to a mutable one is pretty much never a good idea. You should borrow as mutable in the first place. – Cerelly

Or else use interior mutability in your data structure, with something like RefCell. – Eyeopener

You might want to look at Learning Rust with entirely too many linked lists – Tanika

I don't think the downvotes are warranted. No, you can't do this without UB, but it's not an unreasonable question -- especially for a user coming from a language like C++ where constness is really more of a suggestion than a rule. – Coated

Translation: "Is it possible to shoot myself in the head?" – Unsophisticated

@trentcl even in C++ removing the const is UB en.cppreference.com/w/cpp/language/const_cast#Notes – Paraphrase

@Paraphrase From that page: "Modifying a const object through a non-const access path [...] results in undefined behavior." In C++ you can trigger UB by modifying a const object through a non-const pointer. In Rust you can trigger UB whether or not the referent is const, even without trying to modify it, because you can violate aliasing assumptions. This is not the case in C++ (unless perhaps you invoke C99-esque restrict pointers, but not the case of const_cast, anyway). – Coated

Or, put another way: const_cast is valid to do sometimes. Casting &T to &mut T is valid never. – Coated

Ah okay, I got that, sorry :) – Paraphrase

Thanks all you guys (comments guideline told me not to comment for complimenting, but upvotes just cannot fully express my gratitude). I feel like I am dumber when I write Rust, but you guys show me why Rust was designed that way and the friendliness of the community. This inspired to learn more in Rust and thinking in the Rust way, then I can help someone like me someday ;) – Superjacent

Answer 1

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:

• How to remove the Nth node from the end of a linked list?
• How to use two pointers to iterate a linked list in Rust?

Terri

The Nomicon has a related passage which I appreciate very much: "transmuting an & to &mut is UB; Transmuting an & to &mut is always UB; No you can't do it; No you're not special" – Pronuba

Answer 2

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.

Jerryjerrybuild

This answer is misleading. In Rust, unlike C/C++, it's unsound just to convert a & reference into a &mut reference even if the underlying object could be mutated. This is because &mut references are like restrict-qualified pointers in C, and casting a T* to a T* restrict can lead to undefined behavior as the compiler is allowed to optimize loads and stores based around the restrict assumption. – Coated

In other words, the answer to this question does not apply in Rust. More than guaranteeing the referent is mutable, you have to guarantee the &T is unaliased. – Coated

This function is undefined behavior; there is no possible usage of it that is safe to use. Try running it with Miri. There's a reason my answer did not provide the code that can never be safely used. – Terri

This answer was meant to show why this undefined behavior, I wasn't trying to suggest this should ever be used. – Jerryjerrybuild

show why this undefined behavior — you cannot show that something is undefined behavior. By definition, UB means that anything can happen. Running that code is allowed to erase your hard drive or summon nasal demons. The fact that it happens to segfault is basically luck. – Terri

The assumption "If you run this... you get a segfault" suggests that the compiler is actually bound to compile the code to something meaningful, but incorrect given the values provided at runtime. In fact, very_bad_function may not be compiled to anything meaningful at all, as the optimizer may make assumptions about reachability based on the non-aliasing of &mut T. Breaking aliasing rules is not an extra reason "in addition to" the problem of writing to read-only memory -- it's the only reason why this code has undefined behavior... – Coated

... since, in order to claim the code writes to read-only memory, you have to believe that it has a meaningful translation into machine code, which it does not. – Coated

Answer 3

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.

Storytelling

This is still UB. The fact that you cast the pointer to UnsafeCell may make the compiler not optimize it (although I'm not sure about that), but it is still UB according to Rust laws. – Azo

And Miri also detects that. – Azo

Like the Nomicon says (which E_net4 cited): "Transmuting an & to &mut is always Undefined Behavior. No you can't do it. No you're not special." – Azo

Thanks for everybody's input. I've provided a reviewed version based on your input + correct usage for UnsafeCell and it now works as expected -- play.rust-lang.org/… – Storytelling

Now it is fine. – Azo