Tracking issue for LinkedList cursors

[Amanieu]

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

Steps:

• Implement the RFC (Implement Cursor for linked lists. (RFC 2570). #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]

rust-lang/rfcs#2847 was open to suggest making a number of changes to this rfc.