How to use Option.take() on None in a loop correctly?

I an using unsafe code to implement the LeetCode #234.

The input data is like this:
Some(Box(1)) -> Some(Box(2)) -> Some(Box(2)) -> Some(Box(1)) -> None

The first step is to revert the second half of the list. Make it to be:
Some(Box(1)) -> Some(Box(2)) -> Some(Box(1)) -> Some(Box(2)) -> None

The code snippet to doing so is as below (The full code is attached at the end):

let mut cur: *mut _ = p2; // p2 is the start of the second half of the whole list. Which is the 3rd node.
let mut prev: *mut Option<Box<ListNode>> = &mut None;

while (*cur).is_some() {
    let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // PROBLEM LINE
    println!("next: {:?}", *next); // next is None in second loop.
    println!("cur: {:?}", *cur); // cur become None in second loop.
    (*cur).as_mut().unwrap().next = (*prev).take(); // ERROR HAPPENS HERE
    prev = cur;
    cur = next;
}

The first loop works fine.
After first loop the cur is: Some(Box(1)) -> None
The prev is: Some(Box(2)) -> None
My expectation for 2nd loop is as below:

  1. Set next pointer to cur's next, which is None.
  2. Set cur's next to be prev. This can make cur to be: Some(Box(1)) -> Some(Box(2)) -> None
  3. Set prev pointer to cur. This doesn't matter.
  4. Set cur pointer to next. This doesn't matter.

The error happens on the 2nd step. The error is:

'called `Option::unwrap()` on a `None` value'

That means cur becomes None after the 1st step code which is:

let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // PROBLEM LINE

The take() is for the cur's next node, which is None. It should return a None, and leave the cur's next as None as well. It should not impact the value of cur.

I also tried to change the 1st step code to be:

let next: *mut _ = if (*cur).as_mut().unwrap().next.is_some() {
    &mut (*cur).as_mut().unwrap().next.take()
} else {
    &mut None
};

Then it works fine. But I think this alternative code should have same effect as the old 1st step code.

I tried to repro it with a small piece of code without loop, just do the same operations in sequence. It works without any problem. It can be executed on https://play.rust-lang.org/ directly.:

#![allow(unused)]

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>
}



fn main() {
    // make a list as 1 -> 2 -> 3 -> 4 -> None
    let mut list = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 3, next: Some(Box::new(ListNode { val: 4, next: None })) })) })) }));
    unsafe {
        // let the pointer point to the 3rd node which has value 3.
        let mut p: *mut _ = &mut list.as_mut().unwrap().next.as_mut().unwrap().next;
        println!("p: {:?}", *p);
        let mut cur: *mut _ = p;
        let mut prev: *mut Option<Box<ListNode>> = &mut None;
        
        // first loop
        let mut next: *mut _ = &mut (*cur).as_mut().unwrap().next.take();
        (*cur).as_mut().unwrap().next = (*prev).take();
        prev = cur;
        cur = next;

        // second loop
        mut next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // The same of the problem code.
        println!("next: {:?}", *next);
        println!("cur: {:?}", *cur);
        (*cur).as_mut().unwrap().next = (*prev).take();
        prev = cur;
        cur = next;
        
        println!("list: {:?}", list);
        println!("prev: {:?}", *prev);
    }
}

The full code is attached as below. It can be executed on https://play.rust-lang.org/ directly.

#![allow(unused)]
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>
}


pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
        return true;
    }

    unsafe {
        let mut head = head;
        let mut fast: *mut _ = &mut head;
        let mut slow: *mut _ = &mut head;
        
        while (*fast).as_ref().unwrap().next.is_some() && (*fast).as_ref().unwrap().next.as_ref().unwrap().next.is_some() {
            slow = &mut (*fast).as_mut().unwrap().next;
            fast = &mut (*fast).as_mut().unwrap().next.as_mut().unwrap().next;
        }

        let mut p1: *mut _ = &mut head;
        let mut p2: *mut _ = &mut (*slow).as_mut().unwrap().next;
        println!("p1: {:?}", *p1);
        println!("p2: {:?}", *p2);

        let mut cur: *mut _ = p2;
        let mut prev: *mut Option<Box<ListNode>> = &mut None;

        while (*cur).is_some() {
            println!("new loop for cur: {:?}", *cur);
            println!("cur: {:?}", *cur);
            println!("prev: {:?}", *prev);
            let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take();
            println!("next: {:?}", *next);
            (*cur).as_mut().unwrap().next = (*prev).take();
            println!("cur: {:?}", *cur);
            prev = cur;
            println!("prev: {:?}", *prev);
            cur = next;
            println!("cur: {:?}", *cur);
        }
        
        p2 = prev;
        println!("p1: {:?}", *p1);
        println!("p2: {:?}", *p2);

        while (*p2).is_some() {
            if (*p1).as_ref().unwrap().val != (*p2).as_ref().unwrap().val {
                return false;
            }
            else {
                p1 = &mut (*p1).as_mut().unwrap().next;
                p2 = &mut (*p2).as_mut().unwrap().next;
            }
        }
        return true;
    }
}

fn main() {
    let mut list = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 1, next: None })) })) })) }));
    let result = is_palindrome(list);
    println!("result: {:?}", result);
}

Don't use unsafe :wink: That's the first rule (of the fightclub :fist:). And if you do, don't use a block of around ~50 lines. That totally defeats the purpose of using Rust in the first place.

Do you know Learn Rust With Entirely Too Many Linked Lists?

5 Likes

▲ This

Miri flags a few things, among them:

// this only exists until the end of the iteration
&mut (*cur).as_mut().unwrap().next.take()

making cur a dangling pointer from the end of the first iteration onward.

I also tried to change the 1st step code to be: [...] Then it works fine.

That's still not correct but LLVM has decided to be kind to you. In release mode I get a seg fault.

1 Like

This is like Rust's version of Betteridge's Law. Any question that asks "Is this a bug in the compiler or the standard library?" can be answered by the word "no".

1 Like

In so far as "if you have to ask, it's not a bug"? :slight_smile:

I think it's a matter of experience. After spending a lot of time programming, one does get better at avoiding premature compiler blame, and then the answer to the question becomes most frequently "yes" by virtue of weeding out the "no"s.

1 Like

Rather in the sense that the stdlib and the compiler are extremely well-tested, and it's overwhelmingly more likely that some newly-written unsafe code contains a bug, rather than the compiler or the stdlib.

To quote the linked article:

As with similar "laws" (e.g., Murphy's law), it is intended to be humorous rather than the literal truth.

1 Like

I changed the title of this question to avoid the "RUDE" to the compiler.
Actually my meaning was to learn the right way to deal with this problem. I considered some names of this topic, but definitely it is more difficult than naming a variable :slight_smile:

@H2CO3 @AndrewGaspar, I hope this can make you guys feel happier.

1 Like

Thanks you for the suggestions. I know that unsafe is the last choice in rust world. I really spent many hours to try if I can solve this problem by using "Safe" rust without duplicating data. You even can see I tried multiple options to understand why the problem happened. I also tried a lot before I step into the unsafe area.

I am also thinking unsafe is an area that developer should be familiar with even it is not suggested. At least they should know what is the right way to do unsafe if they have to. See, I learned that I should not use unsafe block for ~50 lines. My strategy here is to make it work first, then try to optimize it step by step by using the right way.

Welcome for concrete suggestions on my problem. Is there a way to make it work?

1 Like

Thanks @leudz.

I tried to print the cur in the second loop before this line of code execute. I can see the value is valid. Is this mean the point is not dangling at that moment? The cur become None right after this take() function executed. That's why I was thinking this maybe a wrong way to use take().

Could you please elaborate more about why it is dangling, and teach me how I can correct this to make sure the cur will not be ruined?

Also, thanks for introducing the great book to me. I will read it.

BTW, could you let me know that theoretically if it is feasible to solve this problem by using their ListNode definition without data duplication?

Bedore writing more unsafe code read the rust nomicon

3 Likes

This problem is completely doable in safe rust. I've broken it up into 3 steps below, each of which requires implementing the method being called on that line. That is left as an exercise for you, except for reverse, which I've written up for you further below so that you have an example to help.

pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    // Requires two sequential iterations: (1) compute length,
    // (2) traverse/ a _mutable_ reference up to half that length.
    // Then use that mutable point to split into two lists. In the
    // odd-length case, you can leave the extra middle element
    // in the first list.
    let (first, second) = split(head);
    // Implemented further below.
    let second = reverse(second);
    // Check if `first` and `second` have the same values in order.
    // In the odd-length case, `first` would have an extra element
    // at the end, and this method would be written to allow that.
    let is_palindrome = are_palindrome_halves(&first, &second);

    // Not the case for this LeetCode problem, but if you had to
    // restore the original list and return it, then you would also do:
    // let second = reverse(second);
    // let head = join(first, second);

    is_palindrome
}

Most of these seem straightforward to do. Here's an in-place reverse for reference:

fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut rev_head = head?;
    let mut next = rev_head.next.take();

    // Intermediate state at the beginning of each loop is:
    // [flipped-list] <- [rev_head]    [next] -> [next_next] -> ...

    while let Some(mut next_node) = next {
        let next_next = next_node.next.take();
        // Make [next] point to [rev_head]
        // and become the new [rev_head].
        next_node.next = Some(rev_head);
        rev_head = next_node;
        // Continue process from [next_next]
        next = next_next;
    }

    Some(rev_head)
}

Playground

8 Likes

cur is dangling as soon as you exit the first iteration's scope because (*cur).as_mut().unwrap().next.take() is freed.

Which means (*cur).is_some() dereferences a dangling pointer and makes your entire program UB.
The compiler can do whatever it wants and in debug mode it decides to modify cur apparently for no reason.

1 Like

Thanks for the suggestion. I have finished the practice in Playground here.

There were a little bit struggling when I was implementing the split function. I started the function with below signature.

fn split(head: Option<Box<ListNode>>) -> (Option<Box<ListNode>>, Option<Box<ListNode>>)

I spent a lot of time to handle the error like "behind shared reference...". Finally I tried to add a mut in front of head parameter, it works.

In this way we can solve the problem by using safe rust. But we need one full loop on the LinkedList to get the length. Is there a way to use fast/slow pointers to get the middle position of the LinkedList by using safe rust?

Oof, you're right. That part can be hard since it requires reasoning about owning-Options vs borrowing-Options.

  • Another alternative to adding mut is to reassign to a mut local variable. Can even be the same name as the argument: let mut head = head; (which is equivalent in effect).
  • The problem with the fast/slow pointer approach is that the middle reference needs to be mutable, and we aren't allowed to get two mutable references (or a mutable+non-mutable reference) running along the linked list in safe Rust since Rust cannot easily guarantee that the two pointers don't eventually start aliasing, resulting in undefined behavior. Specifically, &mut translates to the compiler to "uniquely borrowed" and anything that violates that, violates Rust's safety model.
  • The unwrap()s in the second iteration are unfortunate as well since you already know that those references are going to be non-None. My personal bias is to stick to non-panicking code as follows (it should also generate less code underneath since unwrap() has to do this check anyway):
let mid = (len + 1) / 2;
let mut end_first = &mut head;
for _ in 1..mid {
    if let Some(node) = end_first {
        end_first = &mut node.next;
    }
}
let second = match end_first {
    Some(node) => node.next.take(),
    None => None,
}
// or
let second = end_first.as_mut()
    .map(|node| node.next.take())
    .unwrap_or(None);  // can use `.flatten()` once it's stable

If the check-cost in the second iteration is ever a genuine bottleneck, then one can always use one of the crates that provide unsafe_unwrap functionality for Options.

1 Like

Thank again for the kindly communication and suggestion to me. I learned a lot.:grinning: