Cannot mutable borrow cursor twice in linked list

Hello,

I was trying to implement a cursor for a linked list, however, the method move_next() does not allow
to be called twice.

Could anybody please explain me why the code does not work?

struct Node {
    val: i32,
    next: Option<Box<Node>>,
}
struct List {
    root: Option<Box<Node>>,
}
impl List {
    fn get_cursor_mut(&mut self) -> CursorMut {
        CursorMut {
            prev: None,
            curr: self.root.as_deref_mut(),
        }
    }
}
struct CursorMut<'a> {
    prev: Option<&'a mut Node>,
    curr: Option<&'a mut Node>,
}
impl<'a> CursorMut<'a> {
    fn move_next<'b: 'a>(&'b mut self) {
        self.prev = self.curr.take();
        self.prev.as_mut().map(|prev| {
            let next = prev.next.as_deref_mut();
            self.curr = next;
        });
    }
}

fn bar(list: &mut List) {
    let mut cursor = list.get_cursor_mut();
    cursor.move_next();
    cursor.move_next();
}

In bar we get an error.

Playground link Rust Playground

Thanks.

It's not possible to implement your cursor as-is. A mutable element to the current node transitively holds a mutable reference to the next node, and storing them both at the same time would result in mutable aliasing.

1 Like

The specific problem in this case is in the definition of CursorMut::move_next(). Since 'b: 'a, every &mut self reference must be extended for at least as long as 'a. However, both move_next calls use the same 'a lifetime (which ends after the 2nd move_next but before bar returns), so both &mut self references must be active at the same time. This results in the error.

Ok. I got it. Thanks for the explanation.

And what is the solution for this problem? Instead of Box to use NonNull as std does?

Nope. Trying to juggle mutable aliasing unsafely is not the right solution, especially so when you aren't yet comfortable enough with the Rust memory model to be able to solve the problem yourself. You are almost guaranteed to get it wrong and cause UB.

Instead of storing the two mutable references next to each other, store the current node only, and compute the next node from it when needed: Playground

struct CursorMut<'a> {
    curr: Option<&'a mut Node>,
}

impl<'a> CursorMut<'a> {
    fn move_next(&mut self) {
        self.curr = self.curr.take().and_then(|node| node.next.as_deref_mut());
    }
    
    fn get_mut_curr(&mut self) -> Option<&mut Node> {
        self.curr.as_deref_mut()
    }
    
    fn get_mut_next(&mut self) -> Option<&mut Node> {
        self.get_mut_curr().and_then(|node| node.next.as_deref_mut())
    }
}
2 Likes

If you want a bi-directional cursor on a singly linked list, you could build up a reversed linked list on the left-hand-side of the cursor. That should be fairly cheap because you can do it by simply re-linking existing nodes (no new allocations required); you do need to repair the list though when the cursor is dropped (which should not increased amortized cost), and the overhead is unnecessary as long as the bi-directional capabilities aren't needed. Here's some demonstration code nonetheless (I also wrote that as a little challenge for myself ^^)

use std::mem;

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

struct List<T> {
    root: Option<Box<Node<T>>>,
}

struct CursorMut<'a, T> {
    previous: Option<Box<Node<T>>>,
    current: &'a mut Box<Node<T>>,
}

impl<T> List<T> {
    fn get_cursor_mut(&mut self) -> Option<CursorMut<'_, T>> {
        let current = self.root.as_mut()?;
        Some(CursorMut {
            current,
            previous: None,
        })
    }
    fn from_iter(i: impl IntoIterator<Item = T>) -> Self {
        let mut list = List { root: None };
        let mut next = &mut list.root;
        for val in i {
            *next = Some(Box::new(Node { val, next: None }));
            next = &mut next.as_mut().unwrap().next
        }
        list
    }
}

// avoid stack overflows on drop
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while let Some(node) = self.root.take() {
            self.root = node.next;
        }
    }
}

impl<T> CursorMut<'_, T> {
    fn get(&self) -> &T {
        &self.current.val
    }

    fn get_mut(&mut self) -> &mut T {
        &mut self.current.val
    }

    fn move_next(&mut self) -> Option<()> {
        let new_current = self.current.next.take()?;
        let mut new_previous = mem::replace(self.current, new_current);
        new_previous.next = self.previous.take();
        self.previous = Some(new_previous);
        Some(())
    }

    fn move_prev(&mut self) -> Option<()> {
        let new_next = mem::replace(self.current, self.previous.take()?);
        self.previous = self.current.next.replace(new_next);
        Some(())
    }
}

impl<T> Drop for CursorMut<'_, T> {
    fn drop(&mut self) {
        while self.move_prev().is_some() {}
    }
}

fn main() {
    let mut l = List::from_iter([1, 2, 3, 4]);
    let mut c = l.get_cursor_mut().unwrap();
    loop {
        dbg!(c.get());
        if c.move_next().is_none() { break; }
    }
    loop {
        dbg!(c.get());
        if c.move_prev().is_none() { break; }
    }
    loop {
        dbg!(c.get());
        if c.move_next().is_none() { break; }
    }
    drop(c);
    let mut c = l.get_cursor_mut().unwrap();
    loop {
        dbg!(c.get());
        if c.move_next().is_none() { break; }
    }
    loop {
        dbg!(c.get());
        if c.move_prev().is_none() { break; }
    }
    loop {
        dbg!(c.get());
        if c.move_next().is_none() { break; }
    }
    drop(c);
}

Rust Playground

There's certainly different designs for cursors and choosing one is a question orthogonal to the "how to implement this" kind of question, the one above always points to an existing element: so the .get() method returns no Option, but creating the cursor is fallible, and moving the cursor can fail to do anything at the end of the list, as indicated by the Option<()> return value.

7 Likes

@steffahn
Yes thanks for the example implementation.

I also wrote something similar at the end, but using Option<NonNull<Node>> as an exercise.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.