Bug in the 7.12 (A Production Unsafe Deque) final code

[Tomer-Eliahu]

I think there is a bug in the final code. By copying the 7.12 final code to the Rust playground and running the following you can observe it:

        let mut m: LinkedList<u32> = LinkedList::new();
        m.extend([1, 2, 3, 4, 5, 6]);
        let mut cursor = m.cursor_mut();
        assert_eq!(cursor.current(), None);
        cursor.move_next();
        assert_eq!(cursor.current(), Some(&mut 1));
        let before = cursor.split_before();
        
        //prints false then the program panics
        println!("{:#?}", before.front.is_none());

The issue is that in the new list before we create, the front still points to the node with element 1 in m.

This bug is from the split_before function in 7.10:

pub fn split_before(&mut self) -> LinkedList<T> {
    if let Some(cur) = self.cur {
        // We are pointing at a real element, so the list is non-empty.
        unsafe {
            //...
            // What the output will become
            let output_front = self.list.front; // <-- incorrect if we are at index 0 (the first non-ghost node)
            //.....
            LinkedList {
                front: output_front, <-- this is still self.list.front.
                back: output_back,
                len: output_len,
                _boo: PhantomData,
            }
           //.....
}

There is also a mirror of this bug in split_after (where output_back = self.list.back even if the cursor is on the last non-ghost node in the list).
You can observe it by running:

        let mut m: LinkedList<u32> = LinkedList::new();
        m.extend([1, 2, 3, 4, 5, 6]);
        let mut cursor = m.cursor_mut();
        assert_eq!(cursor.current(), None);
        cursor.move_prev();
        assert_eq!(cursor.current(), Some(&mut 6));
        let after = cursor.split_after();
        
        //prints false
        println!("{:#?}", after.back.is_none());

[escape0707]

I also noticed this problem while going through this guide.

I suggest adopting OP's test case and change the implementation to something like:

    pub fn split_before(&mut self) -> LinkedList<T> {
        if let Some(cur) = self.cur {
            unsafe {
                if let Some(front) = (*cur.as_ptr()).front {
                    let ret = LinkedList {
                        front: self.list.front,
                        back: Some(front),
                        len: self.index.unwrap(),
                        _boo: PhantomData,
                    };
                    self.list.front = Some(cur);
                    self.list.len -= self.index.unwrap();
                    self.index = Some(0);
                    (*cur.as_ptr()).front = None;
                    (*front.as_ptr()).back = None;
                    ret
                } else {
                    LinkedList::new()
                }
            }
        } else {
            std::mem::take(self.list)
        }
    }

And also, I'd suggest OP to change the issue title to point out it's a "Bug in 7.10" rather than 7.12.

Edit:

During testing, I also find out that split_after is not a simple copy-paste of split_before, since you need to change the logic that calculate the length of lists and the cursor index. And the author forgot to mention this even later during testing.

Some careless readers might directly copy and paste the code, swap front and back and call it a day, which could result in panics caused by underflow during the len's subtraction operation in the subsequent Drop process.

In case anyone needs the demonstration of the differences in code:

    pub fn split_after(&mut self) -> LinkedList<T> {
        if let Some(cur) = self.cur {
            unsafe {
                if let Some(back) = (*cur.as_ptr()).back {
                    let ret = LinkedList {
                        back: self.list.back,
                        front: Some(back),
                        len: self.list.len - self.index.unwrap() - 1,
                        _boo: PhantomData,
                    };
                    self.list.back = Some(cur);
                    self.list.len = self.index.unwrap() + 1;
                    (*cur.as_ptr()).back = None;
                    (*back.as_ptr()).front = None;
                    ret
                } else {
                    LinkedList::new()
                }
            }
        } else {
            std::mem::take(self.list)
        }
    }