intrex 0.2.0

//! # Node value access traits
//!
//! This module defines the following traits providing access to node values
//! (application-specific data). They are used by iterators and methods such as
//! [`Values`] and [`ListAccessorMut::front_mut`].
//!
//! | Trait                  | Receiver                | Output type   | [`NodesWithMapLink`] | [`NodesWithMapLinkMut`] |
//! | ---------------------- | ----------------------- | ------------- | -------------------- | ----------------------- |
//! | [`NodesData`]          | `&'this Self`           | `Data`        | `&'pool Element`     | *See note*              |
//! | [`NodesDataLend`]      | `&'this Self`           | `Data<'this>` | `&'pool Element`     | `&'this Element`        |
//! | [`NodesDataLendMut`]   | `&'this mut Self`       | `Data<'this>` |                      | `&'this mut Element`    |
//!
//! - The Output Type column uses a generic associated type (GAT) syntax, but
//!   actual implementation uses non-generic associated types to work around
//!   [issues][1] with lifetime bounds.
//!
//! - The [`NodesWithMapLink`] and [`NodesWithMapLinkMut`] columns show the
//!   concrete output types in the respective implementors.
//!
//! - [`NodesData`] is used in cases where output types cannot depend on
//!   `'this`, such as [`Values`].
//!
//! - [`NodesWithMapLinkMut`] cannot implement [`NodesData`] because it contains
//!   a mutable reference `&'pool mut Pool`, which cannot be downgraded to
//!   a [`Copy`]-able immutable reference `&'pool Pool` without consuming the original
//!   reference.
//!
//! They have forwarding implementations for reference types (`&T`, `&mut T`).
//!
//! | Implementor                         | Implements           | Output type    |
//! | ----------------------------------- | -------------------- | -------------- |
//! | `&'a impl `[`NodesDataLend`]        | **[`NodesData`]**    | **`Data<'a>`** |
//! | `&'a impl `[`NodesDataLend`]        | [`NodesDataLend`]    | No change      |
//! | `&'a mut impl `[`NodesData`]        | [`NodesData`]        | No change      |
//! | `&'a mut impl `[`NodesDataLend`]    | [`NodesDataLend`]    | No change      |
//! | `&'a mut impl `[`NodesDataLendMut`] | [`NodesDataLendMut`] | No change      |
//!
//! - The non-consuming iterator methods (e.g., [`ListAccessor::values`]) rely
//!   on the forwarding implementations.
//!
//! - Note that `&'a T: `[`NodesData`] forwards to `T: `[`NodesDataLend`] using
//!   `'a` as the pseudo-GAT parameter.
//!   This allows [`ListAccessor::values`] to depend on only [`NodesDataLend`]
//!   and not [`NodesData`].
//!
//! [`Values`]: crate::list::accessor::Values
//! [`ListAccessor::values`]: crate::list::accessor::ListAccessor::values
//! [`ListAccessorMut::front_mut`]: crate::list::accessor_mut::ListAccessorMut::front_mut
//! [`NodesWithMapLink`]: crate::list::NodesWithMapLink
//! [`NodesWithMapLinkMut`]: crate::list::NodesWithMapLinkMut
//! [1]: https://sabrinajewson.org/blog/the-better-alternative-to-lifetime-gats

// Trick to avoid GAT
// <https://sabrinajewson.org/blog/the-better-alternative-to-lifetime-gats#hrtb-implicit-bounds>
mod sealed {
    pub trait Sealed: Sized {}
    pub struct Bounds<T>(T);
    impl<T> Sealed for Bounds<T> {}
}
use sealed::{Bounds, Sealed};

/// Access to node application data through a `&Self` with an independent
/// lifetime.
///
/// The implementors should also implement [`NodesDataLend`]`<Index>`.
pub trait NodesData<Index> {
    /// Node application data.
    ///
    /// Most commonly `&'a T` where `'a` is the lifetime of a reference
    /// owned by `Self`, but it can be something else.
    type Data;

    /// Get the application data of a node.
    fn node_data(&self, node: Index) -> Self::Data;
}

/// `<&'a T>::node_data(&&'a T)` → `T::`[`node_data_lend`]`<'a>(&'a T)`
///
/// [`node_data_lend`]: NodesDataLend::node_data_lend
impl<'a, T, Index> NodesData<Index> for &'a T
where
    T: ?Sized + NodesDataLend<Index>,
{
    type Data = <T as NodesDataLendGat<'a, Index>>::Data;

    #[inline]
    #[track_caller]
    fn node_data(&self, node: Index) -> Self::Data {
        (**self).node_data_lend(node)
    }
}

/// Forwarding implementation
impl<T, Index> NodesData<Index> for &mut T
where
    T: ?Sized + NodesData<Index>,
{
    type Data = T::Data;

    #[inline]
    #[track_caller]
    fn node_data(&self, node: Index) -> Self::Data {
        (**self).node_data(node)
    }
}

/// Access to node application data through a `&'this Self` with a potentially
/// related lifetime (e.g., `&'this Node`).
///
/// If the lifetime is independent from `'this`, the implementors should also
/// implement [`NodesData`]`<Index>`.
pub trait NodesDataLend<Index>: for<'this> NodesDataLendGat<'this, Index> {
    /// Get the application data of a node, which may depend on `self`'s
    /// lifetime.
    fn node_data_lend(&self, node: Index) -> <Self as NodesDataLendGat<'_, Index>>::Data;
}

/// Provides a generic associated type used by [`NodesDataLend`].
pub trait NodesDataLendGat<'this, Index, ImplicitBounds: Sealed = Bounds<&'this Self>> {
    /// Node application data.
    ///
    /// Most commonly `&'a T` where `'a` is the lifetime of a reference
    /// owned by `Self`, but it can be something else.
    type Data;
}

impl<'this, T, Index> NodesDataLendGat<'this, Index> for &T
where
    T: ?Sized + NodesDataLendGat<'this, Index>,
{
    type Data = T::Data;
}

impl<T, Index> NodesDataLend<Index> for &T
where
    T: ?Sized + NodesDataLend<Index>,
{
    #[inline]
    #[track_caller]
    fn node_data_lend(&self, node: Index) -> <Self as NodesDataLendGat<'_, Index>>::Data {
        (**self).node_data_lend(node)
    }
}

impl<'this, T, Index> NodesDataLendGat<'this, Index> for &mut T
where
    T: ?Sized + NodesDataLendGat<'this, Index>,
{
    type Data = T::Data;
}

impl<T, Index> NodesDataLend<Index> for &mut T
where
    T: ?Sized + NodesDataLend<Index>,
{
    #[inline]
    #[track_caller]
    fn node_data_lend(&self, node: Index) -> <Self as NodesDataLendGat<'_, Index>>::Data {
        (**self).node_data_lend(node)
    }
}

/// Mutably access to node application data through a `&'this mut Self` with a
/// potentially related lifetime (e.g., `&'this mut Node`).
pub trait NodesDataLendMut<Index>: for<'this> NodesDataLendMutGat<'this, Index> {
    /// Get the mutable application data of a node, which may depend on
    /// `self`'s lifetime.
    fn node_data_lend_mut(&mut self, node: Index)
    -> <Self as NodesDataLendMutGat<'_, Index>>::Data;
}

/// Provides a generic associated type used by [`NodesDataLendMut`].
pub trait NodesDataLendMutGat<'this, Index, ImplicitBounds: Sealed = Bounds<&'this Self>> {
    /// Node application data.
    ///
    /// Most commonly `&'this mut T`, but it can be anything.
    type Data;
}

impl<'this, T, Index> NodesDataLendMutGat<'this, Index> for &mut T
where
    T: ?Sized + NodesDataLendMutGat<'this, Index>,
{
    type Data = T::Data;
}

impl<T, Index> NodesDataLendMut<Index> for &mut T
where
    T: ?Sized + NodesDataLendMut<Index>,
{
    #[inline]
    #[track_caller]
    fn node_data_lend_mut(
        &mut self,
        node: Index,
    ) -> <Self as NodesDataLendMutGat<'_, Index>>::Data {
        (**self).node_data_lend_mut(node)
    }
}