Rust: Tracking issue for LinkedList cursors

[Amanieu]

This is a tracking issue for the RFC "Linked list cursors" (rust-lang/rfcs#2570).

Steps:

• [x] Implement the RFC (#68123)
• [ ] Update documentation, add examples
• [ ] Stabilization PR (see instructions on forge)

Unresolved questions:

• [ ] Only for linked lists?

[gnzlbg]

While the RFC doesn't explicitly show how these APIs should be documented. I think that for operations like insert_list, etc. it might be worth documenting that they have constant-time complexity.

[programmerjake]

one thing that I think would be a useful addition is a Walker type for linked lists, where the walker keeps track of a position in a linked list, but to access/modify the list, it has to be combined with borrowing the list, allowing you to have several walkers that are not limited in which elements they can point to that can all be used to modify the list, similar to being able to have several indexes into a Vec that can all be used to modify elements of the Vec.

[gnzlbg]

one thing that I think would be a useful addition is a Walker type for linked lists, where the walker keeps track of a position in a linked list, but to access/modify the list, it has to be combined with borrowing the list,

Does the Walker "borrow" the list, preventing removals? If so, why does one need to combine it with borrowing the list? If not, how does the Walker handle the case, in which the position it refers to has been deleted?

[programmerjake]

Does the Walker "borrow" the list, preventing removals? If so, why does one need to combine it with borrowing the list? If not, how does the Walker handle the case, in which the position it refers to has been deleted?

no, the walker doesn't borrow the list. the list would panic or return None when passed a walker to a deleted item. to prevent needing the extra space in a list to track deleted nodes to prevent dangling pointers, we could add a WalkableList struct that borrows the list and keeps deleted nodes from being freed until the WalkableList is dropped or changes Walkers pointing to the deleted item to point to nothing. all access of the list would go through WalkableList. WalkableList would keep track of the Walkers and on drop would panic if there are any walkers left.

we may want to make a generic Walkable trait to allow walking types other than linked lists.

Something like this:

struct WalkableList<'a, T> {
    list: &'a mut LinkedList<T>,
    deletedNodes: Option<NonNull<Node<T>>, // element already dropped when in this list
    walkerTracker: Rc<()>,
}

#[derive(Clone)]
struct Walker<T> {
    node: Option<NonNull<Node<T>>>,
    walkerTracker: Rc<()>,
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: ManuallyDrop<T>,
}

impl<T> Drop for WalkableList<'_, T> {
    fn drop(&mut self) {
        assert!(self.walkerTracker.get_mut().is_some(), "Walkers left");
        while let Some(node) = self.deletedNodes {
            let node = Box::from_raw(node.as_ptr());
            self.deletedNodes = node.next;
            // don't drop node.element; already dropped
        }
    }
}

impl<T> WalkableList<'_, T> {
    pub fn begin(&self) -> Walker<T> {
        Walker { node: self.list.head, walkerTracker: self.walkerTracker.clone(), }
    }
    pub fn remove(&mut self, w: &Walker<T>) -> Option<T> {
        assert!(Rc::ptr_eq(&self.walkerTracker, &w.walkerTracker);
        let node = w.node?;
        unsafe {
            if node.as_ref().prev == Some(node) {
                // node is deleted
                return None;
            }
            self.list.unlink_node(node);
            let retval = ManuallyDrop::take(&mut node.as_mut().element);
            node.prev = Some(node); // mark as deleted
            node.next = self.deletedNodes;
            self.deletedNodes = node;
            Some(retval)
        }
    }
    pub fn get(&self, w: &Walker<T>) -> Option<&T> {
        // ...
    }
    pub fn get_mut(&mut self, w: &Walker<T>) -> Option<&mut T> {
        assert!(Rc::ptr_eq(&self.walkerTracker, &w.walkerTracker);
        let node = w.node?;
        unsafe {
            if node.as_ref().prev == Some(node) {
                // node is deleted
                return None;
            }
            Some(&mut *(*node.as_ptr()).element)
        }
    }
    // other members
}

[crlf0710]

I'm working on this. Currently i'm writing unit tests. Will put up a PR soon.

[crlf0710]

https://github.com/rust-lang/rfcs/pull/2847 was open to suggest making a number of changes to this rfc.

[crlf0710]

68123 has been merged.

[smessmer]

Any reason why Cursors aren't Clone?

[Amanieu]

It seems to just be an oversight. Feel free to send a PR to add Clone.

[main--]

Something I needed just now was to move an element from somewhere within the list to the front. remove_current does this nicely, but also destroys the list node which then has to be re-allocated in the followup push_front call. If I want to avoid that, the only way I see is to call both split_after and split_before and then splice everything back together in the right order. Perhaps something like remove_current_node(&mut self) -> LinkedList<T> could be added, to make this case more convenient.

[Amanieu]

Maybe remove_current_as_list? Feel free to submit a PR!