plunger 0.1.0-rc.6

//! The list itself, and its cursor API.

use crate::pin_list::Id;
use crate::pin_list::InitializedNode;
use crate::pin_list::Node;
use crate::pin_list::id;
use crate::pin_list::util::debug_unreachable;
use core::cell::UnsafeCell;
use core::fmt;
use core::fmt::Debug;
use core::fmt::Formatter;
use core::mem;
use core::mem::align_of;
use core::mem::transmute;
use core::pin::Pin;
use core::ptr;
use core::ptr::NonNull;

/// Types used in a [`PinList`]. This trait is used to avoid an excessive number of generic
/// parameters on [`PinList`] and related types.
///
/// Generally you won't want to implement this trait directly — instead you can create ad-hoc
/// implementations by using `dyn Trait` syntax, for example:
pub trait Types {
    /// The ID type this list uses to ensure that different [`PinList`]s are not mixed up.
    ///
    /// This crate provides a couple built-in ID types, but you can also define your own:
    /// - [`id::Checked`]:
    ///   IDs are allocated with a single global atomic `u64` counter.
    /// - [`id::Unchecked`]:
    ///   The responsibility is left up to the user to ensure that different [`PinList`]s are not
    ///   incorrectly mixed up. Using this is `unsafe`.
    /// - [`id::DebugChecked`]:
    ///   Equivalent to [`id::Checked`] when `debug_assertions` are enabled, but
    ///   [`id::Unchecked`] in release.
    /// - [`id::Lifetime`]:
    ///   A fully statically checked ID based on invariant lifetimes and HRTBs — this is the same
    ///   technique as used by `GhostCell`. While theoretically the best option, its infectious
    ///   nature makes it not very useful in practice.
    type Id: Id;

    /// Data owned by each node in the list (before it has been removed) and protected by the list.
    /// This is only accessible when the list is.
    ///
    /// When the node is removed from the list, this value is replaced with [`Removed`].
    ///
    /// [`Removed`]: Self::Removed
    type Protected;

    /// Data owned by each node after it has been acquired from the list.
    type Acquired;

    /// Data owned by each node after it has been released from the list.
    type Released;

    /// Data owned by each node in the list but not protected by the list.
    ///
    /// This is always accessible by shared reference from the node itself without accessing the
    /// list, and is acessible by shared reference from the [`PinList`].
    type Unprotected;
}

/// An intrusive linked list.
pub struct PinList<T: ?Sized + Types> {
    /// The list's unique ID.
    pub(crate) id: T::Id,

    /// The head of the list.
    ///
    /// If this is `None`, the list is empty.
    head: OptionNodeShared<T>,

    /// The tail of the list.
    ///
    /// Whether this is `None` must remain in sync with whether `head` is `None`.
    tail: OptionNodeShared<T>,
}

/// An optional pointer to a `NodeShared`.
///
/// Unlike `Option<NonNull<NodeShared<T>>>`, this has a niche.
pub(crate) struct OptionNodeShared<T: ?Sized + Types>(NonNull<NodeShared<T>>);

impl<T: ?Sized + Types> OptionNodeShared<T> {
    pub(crate) const NONE: Self = Self(Self::SENTINEL);
    pub(crate) fn some(ptr: NonNull<NodeShared<T>>) -> Self {
        Self(ptr)
    }
    pub(crate) fn get(self) -> Option<NonNull<NodeShared<T>>> {
        (self.0 != Self::SENTINEL).then_some(self.0)
    }
    const SENTINEL: NonNull<NodeShared<T>> = {
        // `NodeShared` indirectly contains pointers, so we know this is true.
        assert!(2 <= align_of::<NodeShared<T>>());

        // We use a value of 1 as the sentinel since it isn’t aligned
        // and thus can’t be mistaken for a valid value.
        //
        // We use a transmute to explicitly polyfill `ptr::without_provenance`.
        #[allow(clippy::useless_transmute)]
        unsafe {
            NonNull::new_unchecked(transmute::<usize, *mut NodeShared<T>>(1))
        }
    };
}

impl<T: ?Sized + Types> Clone for OptionNodeShared<T> {
    fn clone(&self) -> Self {
        *self
    }
}
impl<T: ?Sized + Types> Copy for OptionNodeShared<T> {}

/// The state of a node in a list shared between the node's owner and other types.
///
/// This type is only accessed by shared reference because there are multiple places that need to
/// have non-invalidated pointers to it.
pub(crate) struct NodeShared<T: ?Sized + Types> {
    /// State of this node that is protected by the `PinList`.
    pub(crate) protected: UnsafeCell<NodeProtected<T>>,

    /// State of this node not protected by the `PinList`.
    pub(crate) unprotected: T::Unprotected,
}

pub(crate) enum NodeProtected<T: ?Sized + Types> {
    /// The node is present in the list.
    Linked(NodeLinked<T>),

    /// The node is not in the list, but it's temporarily owned by a third party.
    Acquired(NodeAcquired<T>),

    /// This node has been removed from the list.
    Released(NodeReleased<T>),
}

pub(crate) struct NodeLinked<T: ?Sized + Types> {
    /// The previous node in the linked list.
    pub(crate) prev: OptionNodeShared<T>,

    /// The next node in the linked list.
    pub(crate) next: OptionNodeShared<T>,

    /// Any extra data the user wants to store in this state.
    pub(crate) data: T::Protected,
}

pub(crate) struct NodeAcquired<T: ?Sized + Types> {
    /// Any extra data the user wants to store in this state.
    pub(crate) data: T::Acquired,
}

pub(crate) struct NodeReleased<T: ?Sized + Types> {
    /// Any extra data the user wants to store in this state.
    pub(crate) data: T::Released,
}

unsafe impl<T: ?Sized + Types> Send for PinList<T>
where
    // Required because it is owned by this type and will be dropped by it.
    T::Id: Send,
    // (SAFETY) Not required because the ownership of IDs are not shared.
    /* T::Id: ?Sync, */
    // Required because we we expose exclusive access to values of this type.
    T::Protected: Send,
    // (SAFETY) Not required because multiple `&PinList`s on different threads are required to
    // access this type in a `Sync`-requiring way, which would need `PinList: Sync` (which does
    // require `T::Protected: Sync`). In other words, `Self: Send` alone only allows exclusive or
    // reentrant access which is OK by `Send + !Sync`.
    /* T::Protected: ?Sync, */
    // Required because ownership can be transferred into the list nodes which may be on a
    // different thread.
    T::Released: Send,
    // (SAFETY) Not required because we never deal in `&T::Removed` — it's always passed by
    // ownership.
    /* T::Removed: ?Sync, */

    // (SAFETY) Not required because we don't drop it and we only access it by shared reference.
    /* T::Unprotected: ?Send, */
    // Required because values of the type can be shared between this list and its nodes even
    // without the guard held.
    T::Unprotected: Sync,
{
}

unsafe impl<T: ?Sized + Types> Sync for PinList<T>
where
    // (SAFETY) Not required because ownership of IDs can't be obtained from a shared reference.
    /* T::Id: ?Send, */
    // Required because ID comparison code uses its `PartialEq` implementation, which accesses it
    // by shared reference.
    T::Id: Sync,
    // Both `Send` and `Sync` are required because this value can be accessed by both shared
    // and exclusive reference from a shared reference to the list.
    T::Protected: Send + Sync,
    // Required because ownership can be transferred into the list nodes which may be on
    // a different thread.
    T::Released: Send,
    // (SAFETY) Not required because we never deal in `&T::Removed` — it's always passed by
    // ownership.
    /* T::Removed: ?Sync, */

    // (SAFETY) Not required because we don't drop it and we only access it by shared reference.
    /* T::Unprotected: ?Send, */
    // Required because values of the type can be shared between this list and its nodes.
    T::Unprotected: Sync,
{
}

impl<T: ?Sized> PinList<T>
where
    T: Types,
{
    /// Create a new empty `PinList` from a unique ID.
    #[must_use]
    pub const fn new(id: id::Unique<<T as Types>::Id>) -> Self {
        Self {
            id: id.into_inner(),
            head: OptionNodeShared::NONE,
            tail: OptionNodeShared::NONE,
        }
    }
}

impl<T: ?Sized + Types> PinList<T> {
    /// # Safety
    ///
    /// - The node must be present in the list.
    /// - This cursor must not be used to invalidate any other cursors in the list (by e.g.
    ///   removing nodes out from under them).
    pub(crate) unsafe fn cursor_mut(&mut self, current: OptionNodeShared<T>) -> CursorMut<'_, T> {
        CursorMut {
            list: self,
            current,
        }
    }

    /// Obtain a `CursorMut` pointing to the "ghost" element of the list.
    #[must_use]
    pub fn cursor_ghost_mut(&mut self) -> CursorMut<'_, T> {
        // SAFETY: The ghost cursor is always in the list, and the `&mut Self` ensures that safe
        // code cannot currently hold a cursor.
        unsafe { self.cursor_mut(OptionNodeShared::NONE) }
    }

    /// Obtain a `CursorMut` pointing to the first element of the list, or the ghost element if the
    /// list is empty.
    #[must_use]
    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
        let mut cursor = self.cursor_ghost_mut();
        cursor.move_next();
        cursor
    }

    /// Obtain a `CursorMut` pointing to the last element of the list, or the ghost element if the
    /// list is empty.
    #[must_use]
    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
        let mut cursor = self.cursor_ghost_mut();
        cursor.move_previous();
        cursor
    }

    pub fn acquire_front(
        &mut self,
        acquired: T::Acquired,
    ) -> Result<(<T as Types>::Protected, AcquiredNode<T>), <T as Types>::Acquired> {
        self.cursor_front_mut().acquire_current(acquired)
    }

    /// Append a node to the back of the list.
    ///
    /// # Panics
    ///
    /// Panics if the node is not in its initial state.
    pub fn push_back<'node>(
        &mut self,
        node: Pin<&'node mut Node<T>>,
        protected: T::Protected,
    ) -> Pin<&'node mut InitializedNode<'node, T>> {
        node.insert_before(&mut self.cursor_ghost_mut(), protected)
    }
}

#[allow(clippy::missing_fields_in_debug)]
impl<T: ?Sized + Types> Debug for PinList<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_struct("PinList").field("id", &self.id).finish()
    }
}

/// A unique cursor into a linked list.
///
/// This can be created by methods like [`PinList::cursor_ghost_mut`].
///
/// Each cursor conceptually points to a single item in the list. It can also point to the space
/// between the start and end of the list, in which case it is called the ghost cursor.
pub struct CursorMut<'list, T: ?Sized + Types> {
    pub(crate) list: &'list mut PinList<T>,
    pub(crate) current: OptionNodeShared<T>,
}

unsafe impl<T: ?Sized + Types> Send for CursorMut<'_, T> where
    // (SAFETY) Required because we hold a unique reference to a `PinList`.
    PinList<T>: Send
{
}

unsafe impl<T: ?Sized + Types> Sync for CursorMut<'_, T> where
    // (SAFETY) Required because we hold a unique reference to a `PinList`.
    PinList<T>: Sync
{
}

impl<T: ?Sized + Types> CursorMut<'_, T> {
    fn current_shared(&self) -> Option<&NodeShared<T>> {
        // SAFETY: A cursor always points to a valid node in the list (ensured by
        // `PinList::cursor_mut`).
        self.current
            .get()
            .map(|current| unsafe { current.as_ref() })
    }
    fn current_protected(&self) -> Option<&NodeProtected<T>> {
        // SAFETY: Our shared reference to the list gives us shared access to the protected data of
        // every node in it.
        Some(unsafe { &*self.current_shared()?.protected.get() })
    }
    fn current_protected_mut(&mut self) -> Option<&mut NodeProtected<T>> {
        // SAFETY: Our unique reference to the list gives us unique access to the protected data of
        // every node in it.
        Some(unsafe { &mut *self.current_shared()?.protected.get() })
    }
    fn current_linked(&self) -> Option<&NodeLinked<T>> {
        match self.current_protected()? {
            NodeProtected::Linked(linked) => Some(linked),
            NodeProtected::Acquired(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        }
    }
    fn current_linked_mut(&mut self) -> Option<&mut NodeLinked<T>> {
        match self.current_protected_mut()? {
            NodeProtected::Linked(linked) => Some(linked),
            NodeProtected::Acquired(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        }
    }
    pub(crate) fn prev_mut(&mut self) -> &mut OptionNodeShared<T> {
        match self.current.get() {
            // Unwrap because we don't have polonius
            Some(_) => &mut self.current_linked_mut().unwrap().prev,
            None => &mut self.list.tail,
        }
    }
    pub(crate) fn next_mut(&mut self) -> &mut OptionNodeShared<T> {
        match self.current.get() {
            // Unwrap because we don't have polonius
            Some(_) => &mut self.current_linked_mut().unwrap().next,
            None => &mut self.list.head,
        }
    }

    /// Move the cursor to the next element in the linked list.
    pub fn move_next(&mut self) {
        self.current = *self.next_mut();
    }

    /// Move the cursor to the previous element in the linked list.
    pub fn move_previous(&mut self) {
        self.current = *self.prev_mut();
    }

    /// Retrieve a shared reference to the list this cursor uses.
    #[must_use]
    pub fn list(&self) -> &PinList<T> {
        self.list
    }

    /// Retrieve a shared reference to the protected data of this linked list node.
    ///
    /// Returns [`None`] if the cursor is currently the ghost cursor.
    #[must_use]
    pub fn protected(&self) -> Option<&T::Protected> {
        Some(&self.current_linked()?.data)
    }

    /// Retrieve a shared reference to the unprotected data of this linked list node.
    ///
    /// Returns [`None`] if the cursor is currently the ghost cursor.
    #[must_use]
    pub fn unprotected(&self) -> Option<&T::Unprotected> {
        Some(&self.current_shared()?.unprotected)
    }

    /// Remove this node from the linked list with a given "removed" value.
    ///
    /// The cursor is moved to point to the next element in the linked list.
    ///
    /// # Errors
    ///
    /// Fails if the cursor is currently the ghost cursor (not over an item).
    pub fn acquire_current(
        &mut self,
        acquired: T::Acquired,
    ) -> Result<(T::Protected, AcquiredNode<T>), T::Acquired> {
        let protected: *mut NodeProtected<T> = match self.current_protected_mut() {
            Some(x) => x,
            None => return Err(acquired),
        };

        // Take the protected data so we can do things to it.
        // SAFETY: Control flow cannot exit this function until a value is placed into `protected`
        // by `ptr::write`.
        let old = match unsafe { ptr::read(protected) } {
            NodeProtected::Linked(linked) => linked,
            NodeProtected::Acquired(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        };

        // Remove ourselves from the list.
        *unsafe { self.list.cursor_mut(old.prev) }.next_mut() = old.next;
        *unsafe { self.list.cursor_mut(old.next) }.prev_mut() = old.prev;

        // Move the cursor to the next element in the list
        let acquired_node = self.current.0;
        self.current = old.next;

        // Calculate the new user data and set the state to to removed.
        let old_data = old.data;
        let acquired = NodeAcquired { data: acquired };
        unsafe { ptr::write(protected, NodeProtected::Acquired(acquired)) };

        Ok((
            old_data,
            AcquiredNode {
                node: acquired_node,
                list_id: self.list.id,
            },
        ))
    }
}

impl<T: ?Sized + Types> Debug for CursorMut<'_, T>
where
    T::Unprotected: Debug,
    T::Protected: Debug,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_struct("CursorMut")
            .field("list", &self.list)
            .field("protected", &self.protected())
            .field("unprotected", &self.unprotected())
            .finish()
    }
}

/// A unique cursor into a linked list.
///
/// This can be created by methods like [`PinList::cursor_ghost_mut`].
///
/// Each cursor conceptually points to a single item in the list. It can also point to the space
/// between the start and end of the list, in which case it is called the ghost cursor.
pub struct AcquiredNode<T: ?Sized + Types> {
    pub(crate) list_id: T::Id,
    pub(crate) node: NonNull<NodeShared<T>>,
}

unsafe impl<T: ?Sized + Types> Send for AcquiredNode<T> where
    // (SAFETY) Required because we hold a unique reference to a `PinList`.
    PinList<T>: Send
{
}

unsafe impl<T: ?Sized + Types> Sync for AcquiredNode<T> where
    // (SAFETY) Required because we hold a unique reference to a `PinList`.
    PinList<T>: Sync
{
}

impl<T: ?Sized + Types> AcquiredNode<T> {
    fn current_shared(&self, list: &PinList<T>) -> &NodeShared<T> {
        assert_eq!(self.list_id, list.id, "incorrect `PinList`");

        // SAFETY: A cursor always points to a valid node in the list
        unsafe { self.node.as_ref() }
    }

    fn current_protected(&self, list: &PinList<T>) -> &NodeProtected<T> {
        // SAFETY: Our shared reference to the list gives us shared access to the protected data of
        // every node in it.
        unsafe { &*self.current_shared(list).protected.get() }
    }

    pub fn unprotected(&self, list: &PinList<T>) -> &T::Unprotected {
        &self.current_shared(list).unprotected
    }

    pub fn acquired(&self, list: &PinList<T>) -> &T::Acquired {
        match self.current_protected(list) {
            NodeProtected::Acquired(node_acquired) => &node_acquired.data,
            NodeProtected::Linked(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        }
    }

    fn current_protected_mut(self, list: &mut PinList<T>) -> &mut NodeProtected<T> {
        // SAFETY: Our unique reference to the list gives us unique access to the protected data of
        // every node in it.
        unsafe { &mut *self.current_shared(list).protected.get() }
    }

    /// Remove this node from the linked list with a given "removed" value.
    ///
    /// The cursor is moved to point to the next element in the linked list.
    ///
    /// # Errors
    ///
    /// Fails if the cursor is currently the ghost cursor (not over an item).
    pub fn release_current(self, list: &mut PinList<T>, removed: T::Released) -> T::Acquired {
        let protected: *mut NodeProtected<T> = self.current_protected_mut(list);

        // Take the protected data so we can do things to it.
        // SAFETY: Control flow cannot exit this function until a value is placed into `protected`
        // by `ptr::write`.
        let old = match unsafe { ptr::read(protected) } {
            NodeProtected::Acquired(acquired) => acquired,
            NodeProtected::Linked(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        };

        // Calculate the new user data and set the state to to removed.
        let old_data = old.data;
        let removed = NodeReleased { data: removed };
        unsafe { ptr::write(protected, NodeProtected::Released(removed)) };

        old_data
    }

    /// Insert this node into the linked list after the given cursor.
    ///
    /// # Panics
    ///
    /// Panics if the node is not in its initial state.
    pub fn insert_after(
        self,
        cursor: &mut CursorMut<'_, T>,
        protected: T::Protected,
    ) -> T::Acquired {
        let node = self.node;
        let next = *cursor.next_mut();

        let shared = self.current_protected_mut(cursor.list);

        let linked = NodeProtected::Linked(NodeLinked {
            prev: cursor.current,
            next,
            data: protected,
        });

        let acquired = match mem::replace(shared, linked) {
            NodeProtected::Acquired(node_acquired) => node_acquired.data,
            NodeProtected::Linked(..) | NodeProtected::Released(..) => unsafe {
                debug_unreachable!()
            },
        };

        // Update the previous node's `next` pointer and the next node's `prev` pointer to both
        // point to us.
        *cursor.next_mut() = OptionNodeShared::some(node);
        *unsafe { cursor.list.cursor_mut(next) }.prev_mut() = OptionNodeShared::some(node);

        acquired
    }
}