15

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?

10
  • 6
    Converting an immutable reference to a mutable one is pretty much never a good idea. You should borrow as mutable in the first place. Jan 17, 2019 at 14:21
  • 3
    Or else use interior mutability in your data structure, with something like RefCell.
    – Peter Hall
    Jan 17, 2019 at 14:22
  • 3
    You might want to look at Learning Rust with entirely too many linked lists
    – Jmb
    Jan 17, 2019 at 14:53
  • 4
    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.
    – trent
    Jan 17, 2019 at 15:05
  • 7
    Translation: "Is it possible to shoot myself in the head?" Jan 17, 2019 at 16:18

3 Answers 3

16

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.

7
  • 2
    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.
    – trent
    Jan 17, 2019 at 18:38
  • 1
    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.
    – trent
    Jan 17, 2019 at 18:44
  • 3
    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.
    – Shepmaster
    Jan 17, 2019 at 18:54
  • 4
    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.
    – Shepmaster
    Jan 18, 2019 at 0:47
  • 3
    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...
    – trent
    Jan 18, 2019 at 1:37
12

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:

1
  • 10
    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"
    – E_net4
    Jan 17, 2019 at 15:14
1

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.

5
  • 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. Jun 14 at 21:49
  • 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." Jun 14 at 21:52
  • 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/…
    – zertyz
    Jun 14 at 22:19
  • Now it is fine. Jun 14 at 22:26

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.