Auto merge of #68254 - Dylan-DPC:rollup-9vhc59u, r=Dylan-DPC

Rollup of 6 pull requests

Successful merges:

 - #68123 (Implement Cursor for linked lists. (RFC 2570).)
 - #68212 (Suggest to shorten temporary lifetime during method call inside generator)
 - #68232 (Optimize size/speed of Unicode datasets)
 - #68236 (Add some regression tests)
 - #68237 (Account for `Path`s in `is_suggestable_infer_ty`)
 - #68252 (remove redundant clones, found by clippy)

Failed merges:

r? @ghost

2 files changed, 707 insertions, 24 deletions

diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs
index 29bf2fdb30c..b88ca8a0fb0 100644
--- a/src/liballoc/collections/linked_list.rs
+++ b/src/liballoc/collections/linked_list.rs
@@ -242,6 +242,121 @@ impl<T> LinkedList<T> {
 
         self.len -= 1;
     }
+
+    /// Splices a series of nodes between two existing nodes.
+    ///
+    /// Warning: this will not check that the provided node belongs to the two existing lists.
+    #[inline]
+    unsafe fn splice_nodes(
+        &mut self,
+        existing_prev: Option<NonNull<Node<T>>>,
+        existing_next: Option<NonNull<Node<T>>>,
+        mut splice_start: NonNull<Node<T>>,
+        mut splice_end: NonNull<Node<T>>,
+        splice_length: usize,
+    ) {
+        // This method takes care not to create multiple mutable references to whole nodes at the same time,
+        // to maintain validity of aliasing pointers into `element`.
+        if let Some(mut existing_prev) = existing_prev {
+            existing_prev.as_mut().next = Some(splice_start);
+        } else {
+            self.head = Some(splice_start);
+        }
+        if let Some(mut existing_next) = existing_next {
+            existing_next.as_mut().prev = Some(splice_end);
+        } else {
+            self.tail = Some(splice_end);
+        }
+        splice_start.as_mut().prev = existing_prev;
+        splice_end.as_mut().next = existing_next;
+
+        self.len += splice_length;
+    }
+
+    /// Detaches all nodes from a linked list as a series of nodes.
+    #[inline]
+    fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> {
+        let head = self.head.take();
+        let tail = self.tail.take();
+        let len = mem::replace(&mut self.len, 0);
+        if let Some(head) = head {
+            let tail = tail.unwrap_or_else(|| unsafe { core::hint::unreachable_unchecked() });
+            Some((head, tail, len))
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    unsafe fn split_off_before_node(
+        &mut self,
+        split_node: Option<NonNull<Node<T>>>,
+        at: usize,
+    ) -> Self {
+        // The split node is the new head node of the second part
+        if let Some(mut split_node) = split_node {
+            let first_part_head;
+            let first_part_tail;
+            first_part_tail = split_node.as_mut().prev.take();
+            if let Some(mut tail) = first_part_tail {
+                tail.as_mut().next = None;
+                first_part_head = self.head;
+            } else {
+                first_part_head = None;
+            }
+
+            let first_part = LinkedList {
+                head: first_part_head,
+                tail: first_part_tail,
+                len: at,
+                marker: PhantomData,
+            };
+
+            // Fix the head ptr of the second part
+            self.head = Some(split_node);
+            self.len = self.len - at;
+
+            first_part
+        } else {
+            mem::replace(self, LinkedList::new())
+        }
+    }
+
+    #[inline]
+    unsafe fn split_off_after_node(
+        &mut self,
+        split_node: Option<NonNull<Node<T>>>,
+        at: usize,
+    ) -> Self {
+        // The split node is the new tail node of the first part and owns
+        // the head of the second part.
+        if let Some(mut split_node) = split_node {
+            let second_part_head;
+            let second_part_tail;
+            second_part_head = split_node.as_mut().next.take();
+            if let Some(mut head) = second_part_head {
+                head.as_mut().prev = None;
+                second_part_tail = self.tail;
+            } else {
+                second_part_tail = None;
+            }
+
+            let second_part = LinkedList {
+                head: second_part_head,
+                tail: second_part_tail,
+                len: self.len - at,
+                marker: PhantomData,
+            };
+
+            // Fix the tail ptr of the first part
+            self.tail = Some(split_node);
+            self.len = at;
+
+            second_part
+        } else {
+            mem::replace(self, LinkedList::new())
+        }
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -319,6 +434,27 @@ impl<T> LinkedList<T> {
         }
     }
 
+    /// Moves all elements from `other` to the begin of the list.
+    #[unstable(feature = "linked_list_prepend", issue = "none")]
+    pub fn prepend(&mut self, other: &mut Self) {
+        match self.head {
+            None => mem::swap(self, other),
+            Some(mut head) => {
+                // `as_mut` is okay here because we have exclusive access to the entirety
+                // of both lists.
+                if let Some(mut other_tail) = other.tail.take() {
+                    unsafe {
+                        head.as_mut().prev = Some(other_tail);
+                        other_tail.as_mut().next = Some(head);
+                    }
+
+                    self.head = other.head.take();
+                    self.len += mem::replace(&mut other.len, 0);
+                }
+            }
+        }
+    }
+
     /// Provides a forward iterator.
     ///
     /// # Examples
@@ -373,6 +509,42 @@ impl<T> LinkedList<T> {
         IterMut { head: self.head, tail: self.tail, len: self.len, list: self }
     }
 
+    /// Provides a cursor at the front element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_front(&self) -> Cursor<'_, T> {
+        Cursor { index: 0, current: self.head, list: self }
+    }
+
+    /// Provides a cursor with editing operations at the front element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
+        CursorMut { index: 0, current: self.head, list: self }
+    }
+
+    /// Provides a cursor at the back element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_back(&self) -> Cursor<'_, T> {
+        Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
+    }
+
+    /// Provides a cursor with editing operations at the back element.
+    ///
+    /// The cursor is pointing to the "ghost" non-element if the list is empty.
+    #[inline]
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
+        CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self }
+    }
+
     /// Returns `true` if the `LinkedList` is empty.
     ///
     /// This operation should compute in O(1) time.
@@ -703,30 +875,7 @@ impl<T> LinkedList<T> {
             }
             iter.tail
         };
-
-        // The split node is the new tail node of the first part and owns
-        // the head of the second part.
-        let second_part_head;
-
-        unsafe {
-            second_part_head = split_node.unwrap().as_mut().next.take();
-            if let Some(mut head) = second_part_head {
-                head.as_mut().prev = None;
-            }
-        }
-
-        let second_part = LinkedList {
-            head: second_part_head,
-            tail: self.tail,
-            len: len - at,
-            marker: PhantomData,
-        };
-
-        // Fix the tail ptr of the first part
-        self.tail = split_node;
-        self.len = at;
-
-        second_part
+        unsafe { self.split_off_after_node(split_node, at) }
     }
 
     /// Creates an iterator which uses a closure to determine if an element should be removed.
@@ -986,6 +1135,388 @@ impl<T> IterMut<'_, T> {
     }
 }
 
+/// A cursor over a `LinkedList`.
+///
+/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
+///
+/// Cursors always rest between two elements in the list, and index in a logically circular way.
+/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
+/// tail of the list.
+///
+/// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty.
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+pub struct Cursor<'a, T: 'a> {
+    index: usize,
+    current: Option<NonNull<Node<T>>>,
+    list: &'a LinkedList<T>,
+}
+
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish()
+    }
+}
+
+/// A cursor over a `LinkedList` with editing operations.
+///
+/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
+/// safely mutate the list during iteration. This is because the lifetime of its yielded
+/// references is tied to its own lifetime, instead of just the underlying list. This means
+/// cursors cannot yield multiple elements at once.
+///
+/// Cursors always rest between two elements in the list, and index in a logically circular way.
+/// To accommodate this, there is a "ghost" non-element that yields `None` between the head and
+/// tail of the list.
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+pub struct CursorMut<'a, T: 'a> {
+    index: usize,
+    current: Option<NonNull<Node<T>>>,
+    list: &'a mut LinkedList<T>,
+}
+
+#[unstable(feature = "linked_list_cursors", issue = "58533")]
+impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish()
+    }
+}
+
+impl<'a, T> Cursor<'a, T> {
+    /// Returns the cursor position index within the `LinkedList`.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn index(&self) -> Option<usize> {
+        let _ = self.current?;
+        Some(self.index)
+    }
+
+    /// Moves the cursor to the next element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_next(&mut self) {
+        match self.current.take() {
+            // We had no current element; the cursor was sitting at the start position
+            // Next element should be the head of the list
+            None => {
+                self.current = self.list.head;
+                self.index = 0;
+            }
+            // We had a previous element, so let's go to its next
+            Some(current) => unsafe {
+                self.current = current.as_ref().next;
+                self.index += 1;
+            },
+        }
+    }
+
+    /// Moves the cursor to the previous element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_prev(&mut self) {
+        match self.current.take() {
+            // No current. We're at the start of the list. Yield None and jump to the end.
+            None => {
+                self.current = self.list.tail;
+                self.index = self.list.len().checked_sub(1).unwrap_or(0);
+            }
+            // Have a prev. Yield it and go to the previous element.
+            Some(current) => unsafe {
+                self.current = current.as_ref().prev;
+                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
+            },
+        }
+    }
+
+    /// Returns a reference to the element that the cursor is currently
+    /// pointing to.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn current(&self) -> Option<&'a T> {
+        unsafe { self.current.map(|current| &(*current.as_ptr()).element) }
+    }
+
+    /// Returns a reference to the next element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_next(&self) -> Option<&'a T> {
+        unsafe {
+            let next = match self.current {
+                None => self.list.head,
+                Some(current) => current.as_ref().next,
+            };
+            next.map(|next| &(*next.as_ptr()).element)
+        }
+    }
+
+    /// Returns a reference to the previous element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_prev(&self) -> Option<&'a T> {
+        unsafe {
+            let prev = match self.current {
+                None => self.list.tail,
+                Some(current) => current.as_ref().prev,
+            };
+            prev.map(|prev| &(*prev.as_ptr()).element)
+        }
+    }
+}
+
+impl<'a, T> CursorMut<'a, T> {
+    /// Returns the cursor position index within the `LinkedList`.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn index(&self) -> Option<usize> {
+        let _ = self.current?;
+        Some(self.index)
+    }
+
+    /// Moves the cursor to the next element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_next(&mut self) {
+        match self.current.take() {
+            // We had no current element; the cursor was sitting at the start position
+            // Next element should be the head of the list
+            None => {
+                self.current = self.list.head;
+                self.index = 0;
+            }
+            // We had a previous element, so let's go to its next
+            Some(current) => unsafe {
+                self.current = current.as_ref().next;
+                self.index += 1;
+            },
+        }
+    }
+
+    /// Moves the cursor to the previous element of the `LinkedList`.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this will move it to
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this will move it to the "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn move_prev(&mut self) {
+        match self.current.take() {
+            // No current. We're at the start of the list. Yield None and jump to the end.
+            None => {
+                self.current = self.list.tail;
+                self.index = self.list.len().checked_sub(1).unwrap_or(0);
+            }
+            // Have a prev. Yield it and go to the previous element.
+            Some(current) => unsafe {
+                self.current = current.as_ref().prev;
+                self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len());
+            },
+        }
+    }
+
+    /// Returns a reference to the element that the cursor is currently
+    /// pointing to.
+    ///
+    /// This returns `None` if the cursor is currently pointing to the
+    /// "ghost" non-element.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn current(&mut self) -> Option<&mut T> {
+        unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) }
+    }
+
+    /// Returns a reference to the next element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the first element of the `LinkedList`. If it is pointing to the last
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_next(&mut self) -> Option<&mut T> {
+        unsafe {
+            let next = match self.current {
+                None => self.list.head,
+                Some(current) => current.as_ref().next,
+            };
+            next.map(|next| &mut (*next.as_ptr()).element)
+        }
+    }
+
+    /// Returns a reference to the previous element.
+    ///
+    /// If the cursor is pointing to the "ghost" non-element then this returns
+    /// the last element of the `LinkedList`. If it is pointing to the first
+    /// element of the `LinkedList` then this returns `None`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn peek_prev(&mut self) -> Option<&mut T> {
+        unsafe {
+            let prev = match self.current {
+                None => self.list.tail,
+                Some(current) => current.as_ref().prev,
+            };
+            prev.map(|prev| &mut (*prev.as_ptr()).element)
+        }
+    }
+
+    /// Returns a read-only cursor pointing to the current element.
+    ///
+    /// The lifetime of the returned `Cursor` is bound to that of the
+    /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
+    /// `CursorMut` is frozen for the lifetime of the `Cursor`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn as_cursor<'cm>(&'cm self) -> Cursor<'cm, T> {
+        Cursor { list: self.list, current: self.current, index: self.index }
+    }
+}
+
+// Now the list editing operations
+
+impl<'a, T> CursorMut<'a, T> {
+    /// Inserts a new element into the `LinkedList` after the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new element is
+    /// inserted at the front of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn insert_after(&mut self, item: T) {
+        unsafe {
+            let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
+            let node_next = match self.current {
+                None => self.list.head,
+                Some(node) => node.as_ref().next,
+            };
+            self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1);
+            if self.current.is_none() {
+                // The "ghost" non-element's index has changed.
+                self.index = self.list.len;
+            }
+        }
+    }
+
+    /// Inserts a new element into the `LinkedList` before the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new element is
+    /// inserted at the end of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn insert_before(&mut self, item: T) {
+        unsafe {
+            let spliced_node = Box::into_raw_non_null(Box::new(Node::new(item)));
+            let node_prev = match self.current {
+                None => self.list.tail,
+                Some(node) => node.as_ref().prev,
+            };
+            self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1);
+            self.index += 1;
+        }
+    }
+
+    /// Removes the current element from the `LinkedList`.
+    ///
+    /// The element that was removed is returned, and the cursor is
+    /// moved to point to the next element in the `LinkedList`.
+    ///
+    /// If the cursor is currently pointing to the "ghost" non-element then no element
+    /// is removed and `None` is returned.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn remove_current(&mut self) -> Option<T> {
+        let unlinked_node = self.current?;
+        unsafe {
+            self.current = unlinked_node.as_ref().next;
+            self.list.unlink_node(unlinked_node);
+            let unlinked_node = Box::from_raw(unlinked_node.as_ptr());
+            Some(unlinked_node.element)
+        }
+    }
+
+    /// Inserts the elements from the given `LinkedList` after the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new elements are
+    /// inserted at the start of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn splice_after(&mut self, list: LinkedList<T>) {
+        unsafe {
+            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
+                Some(parts) => parts,
+                _ => return,
+            };
+            let node_next = match self.current {
+                None => self.list.head,
+                Some(node) => node.as_ref().next,
+            };
+            self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len);
+            if self.current.is_none() {
+                // The "ghost" non-element's index has changed.
+                self.index = self.list.len;
+            }
+        }
+    }
+
+    /// Inserts the elements from the given `LinkedList` before the current one.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the new elements are
+    /// inserted at the end of the `LinkedList`.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn splice_before(&mut self, list: LinkedList<T>) {
+        unsafe {
+            let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() {
+                Some(parts) => parts,
+                _ => return,
+            };
+            let node_prev = match self.current {
+                None => self.list.tail,
+                Some(node) => node.as_ref().prev,
+            };
+            self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len);
+            self.index += splice_len;
+        }
+    }
+
+    /// Splits the list into two after the current element. This will return a
+    /// new list consisting of everything after the cursor, with the original
+    /// list retaining everything before.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the entire contents
+    /// of the `LinkedList` are moved.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn split_after(&mut self) -> LinkedList<T> {
+        let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 };
+        if self.index == self.list.len {
+            // The "ghost" non-element's index has changed to 0.
+            self.index = 0;
+        }
+        unsafe { self.list.split_off_after_node(self.current, split_off_idx) }
+    }
+
+    /// Splits the list into two before the current element. This will return a
+    /// new list consisting of everything before the cursor, with the original
+    /// list retaining everything after.
+    ///
+    /// If the cursor is pointing at the "ghost" non-element then the entire contents
+    /// of the `LinkedList` are moved.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn split_before(&mut self) -> LinkedList<T> {
+        let split_off_idx = self.index;
+        self.index = 0;
+        unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
+    }
+}
+
 /// An iterator produced by calling `drain_filter` on LinkedList.
 #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
 pub struct DrainFilter<'a, T: 'a, F: 'a>
diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs
index 1b1d8eab39b..085f734ed91 100644
--- a/src/liballoc/collections/linked_list/tests.rs
+++ b/src/liballoc/collections/linked_list/tests.rs
@@ -304,3 +304,155 @@ fn drain_to_empty_test() {
     assert_eq!(deleted, &[1, 2, 3, 4, 5, 6]);
     assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
 }
+
+#[test]
+fn test_cursor_move_peek() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front();
+    assert_eq!(cursor.current(), Some(&1));
+    assert_eq!(cursor.peek_next(), Some(&2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&2));
+    assert_eq!(cursor.peek_next(), Some(&3));
+    assert_eq!(cursor.peek_prev(), Some(&1));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut cursor = m.cursor_back();
+    assert_eq!(cursor.current(), Some(&6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&1));
+    assert_eq!(cursor.peek_prev(), Some(&6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&5));
+    assert_eq!(cursor.peek_next(), Some(&6));
+    assert_eq!(cursor.peek_prev(), Some(&4));
+    assert_eq!(cursor.index(), Some(4));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    assert_eq!(cursor.current(), Some(&mut 1));
+    assert_eq!(cursor.peek_next(), Some(&mut 2));
+    assert_eq!(cursor.peek_prev(), None);
+    assert_eq!(cursor.index(), Some(0));
+    cursor.move_prev();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.peek_next(), Some(&mut 3));
+    assert_eq!(cursor.peek_prev(), Some(&mut 1));
+    assert_eq!(cursor.index(), Some(1));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&2));
+    assert_eq!(cursor2.index(), Some(1));
+    cursor2.move_next();
+    assert_eq!(cursor2.current(), Some(&3));
+    assert_eq!(cursor2.index(), Some(2));
+    assert_eq!(cursor.current(), Some(&mut 2));
+    assert_eq!(cursor.index(), Some(1));
+
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_back_mut();
+    assert_eq!(cursor.current(), Some(&mut 6));
+    assert_eq!(cursor.peek_next(), None);
+    assert_eq!(cursor.peek_prev(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(5));
+    cursor.move_next();
+    assert_eq!(cursor.current(), None);
+    assert_eq!(cursor.peek_next(), Some(&mut 1));
+    assert_eq!(cursor.peek_prev(), Some(&mut 6));
+    assert_eq!(cursor.index(), None);
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.peek_next(), Some(&mut 6));
+    assert_eq!(cursor.peek_prev(), Some(&mut 4));
+    assert_eq!(cursor.index(), Some(4));
+    let mut cursor2 = cursor.as_cursor();
+    assert_eq!(cursor2.current(), Some(&5));
+    assert_eq!(cursor2.index(), Some(4));
+    cursor2.move_prev();
+    assert_eq!(cursor2.current(), Some(&4));
+    assert_eq!(cursor2.index(), Some(3));
+    assert_eq!(cursor.current(), Some(&mut 5));
+    assert_eq!(cursor.index(), Some(4));
+}
+
+#[test]
+fn test_cursor_mut_insert() {
+    let mut m: LinkedList<u32> = LinkedList::new();
+    m.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.insert_before(7);
+    cursor.insert_after(8);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    cursor.insert_before(9);
+    cursor.insert_after(10);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]);
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), None);
+    cursor.move_next();
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(7));
+    cursor.move_prev();
+    cursor.move_prev();
+    cursor.move_prev();
+    assert_eq!(cursor.remove_current(), Some(9));
+    cursor.move_next();
+    assert_eq!(cursor.remove_current(), Some(10));
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
+    let mut cursor = m.cursor_front_mut();
+    let mut p: LinkedList<u32> = LinkedList::new();
+    p.extend(&[100, 101, 102, 103]);
+    let mut q: LinkedList<u32> = LinkedList::new();
+    q.extend(&[200, 201, 202, 203]);
+    cursor.splice_after(p);
+    cursor.splice_before(q);
+    check_links(&m);
+    assert_eq!(
+        m.iter().cloned().collect::<Vec<_>>(),
+        &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
+    );
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_prev();
+    let tmp = cursor.split_before();
+    assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]);
+    m = tmp;
+    let mut cursor = m.cursor_front_mut();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    cursor.move_next();
+    let tmp = cursor.split_after();
+    assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]);
+    check_links(&m);
+    assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
+}