supply 0.1.0

//! List of lifetimes `Lt<'a, Lt<'b, Lt<'c, ...>>>`.
//!
//! This module implements a `cons` list for lifetimes.
//! This allows APIs to work on an arbitrary number of lifetimes.
//!
//! See the [`tag`][crate::tag] module for a usage of these lifetime lists.
//! Most of the time only [`LtList`] is needed as a generic bound along with the
//! `LtN` type aliases.
//!
//! ## Invariants
//!
//! This module provides a few invariants for unsafe code to use.
//!
//! 1. [`LtList`] implementers are invariant over their contained lifetimes.
//!    - This means that unsafe code can use the borrow checker to assert the lifetimes contained
//!      are the exact same.
//! 2. [`LtList::Tag`] is unique per lifetime list minus the lifetimes in the
//!    list.
//!    - This means that it would be unique between `<'a, 'b, 'c>` and `<'a, 'b>` but not unique
//!      between `<'a, 'b>` and `<'b, 'c`>.
//! 3. [`Subset`] implementers always connect the shared lifetimes.
//!    - This means that `<'a, 'b>` being a subset of `<'c, 'd, 'e>` results in `'a == 'c` and
//!      `'b == 'd`.

use core::marker::PhantomData;
use core::panic::{RefUnwindSafe, UnwindSafe};

/// A type level `cons` list of lifetimes.
///
/// All lists are invariant over their lifetimes.
///
/// This trait is sealed and is only implemented for `()` and [`Lt`].
// The Sized here is important to prevent `dyn LtList` which has
// subtyping relations. Unsafe code relies on LtList generics being
// fully invariant.
pub trait LtList:
    Subset<Self> + Sized + Send + Sync + Unpin + UnwindSafe + RefUnwindSafe + lt_list_seal::Sealed
{
    /// A [`Lt`] type with the first lifetime.
    ///
    /// The lifetime is `'static` for zero length lists.
    type Head: Subset<Self> + Sized + Send + Sync + Unpin + UnwindSafe + RefUnwindSafe;

    /// The rest of the lifetimes.
    type Tail: LtList;

    /// `'static` type that acts as a tag for the lifetime list.
    ///
    /// This is used by [`TagTypeId`](crate::tag::TagTypeId).
    type Tag: ReifyLt<Self, Lifetimes = Self> + 'static;
}

/// Helper for [`LtList::Head`].
///
/// This will always be a [`Lt`]. At the end of a list the lifetime is `'static`.
pub type HeadOf<L> = <L as LtList>::Head;

/// Helper for [`LtList::Tail`].
pub type TailOf<L> = <L as LtList>::Tail;

/// Helper for [`LtList::Tag`].
pub type LtTagOf<T> = <T as LtList>::Tag;

mod lt_list_seal {
    use super::*;

    pub trait Sealed {}

    impl Sealed for () {}

    // LtList requires Sealed.
    impl<'lt, Tail: LtList> Sealed for Lt<'lt, Tail> {}
}

/// `<>`
///
/// `L` is an arbitrary list. No lifetimes is an empty list, so 'L' is the list
/// after combining them.
pub type Lt0<L = ()> = L;

/// `<'a>`
///
/// `L` is an arbitrary list to place after the given lifetime.
pub type Lt1<'l0, L = ()> = Lt<'l0, L>;

/// `<'a, 'b>`
///
/// `L` is an arbitrary list to place after the given lifetimes.
pub type Lt2<'l0, 'l1, L = ()> = Lt<'l0, Lt<'l1, L>>;

/// `<'a, 'b, 'c>`
///
/// `L` is an arbitrary list to place after the given lifetimes.
pub type Lt3<'l0, 'l1, 'l2, L = ()> = Lt<'l0, Lt<'l1, Lt<'l2, L>>>;

/// `<'a, 'b, 'c, 'd>`
///
/// `L` is an arbitrary list to place after the given lifetimes.
pub type Lt4<'l0, 'l1, 'l2, 'l3, L = ()> = Lt<'l0, Lt<'l1, Lt<'l2, Lt<'l3, L>>>>;

/// `<'a, 'b, 'c, 'd, 'e>`
///
/// `L` is an arbitrary list to place after the given lifetimes.
pub type Lt5<'l0, 'l1, 'l2, 'l3, 'l4, L = ()> = Lt<'l0, Lt<'l1, Lt<'l2, Lt<'l3, Lt<'l4, L>>>>>;

/// `<'a, 'b, 'c, 'd, 'e, 'f>`
///
/// `L` is an arbitrary list to place after the given lifetimes.
pub type Lt6<'l0, 'l1, 'l2, 'l3, 'l4, 'l5, L = ()> =
    Lt<'l0, Lt<'l1, Lt<'l2, Lt<'l3, Lt<'l4, Lt<'l5, L>>>>>>;

/// This type is invariant over `T`.
///
/// See https://doc.rust-lang.org/nomicon/subtyping.html
/// By combining a contravariant and covariant place at the same time this
/// type becomes invariant over `T`.
struct Invariant<T>(PhantomData<fn(T) -> T>);

impl LtList for () {
    type Head = Lt<'static>;

    type Tail = (); // The tail is itself.

    type Tag = ();
}

/// `cons` of a lifetime `'lt` and a tail.
///
/// This struct is invariant over `'lt`.
pub struct Lt<'lt, Tail: LtList = ()>(Invariant<&'lt ()>, PhantomData<fn() -> Tail>);

impl<'lt, Tail: LtList> LtList for Lt<'lt, Tail> {
    type Head = Lt<'lt>;

    type Tail = Tail;

    type Tag = EmptyLt<Tail::Tag>;
}

/// A [`LtList`] without it's lifetimes.
///
/// This allows encoding the length of a [`LtList`] as a `'static` type.
/// See [`ReifyLt`] for adding the lifetimes.
///
/// This trait is sealed and is only implemented by `()` and [`EmptyLt`].
pub trait LtListStructure: empty_tag_seal::Sealed {
    type Tail: LtListStructure;
}

impl LtListStructure for () {
    type Tail = ();
}

impl<Tail: LtListStructure> LtListStructure for EmptyLt<Tail> {
    type Tail = Tail;
}

mod empty_tag_seal {
    use super::*;

    pub trait Sealed {}

    // Only the end () and element TagLt are allowed.
    impl Sealed for () {}
    impl<T: Sealed> Sealed for EmptyLt<T> {}
}

/// Adds the lifetimes from `L` into the empty list.
///
/// This allows a type tag to also store the lifetime it needs.
/// This need can then be filled in later with real lifetimes using this trait.
// This is already sealed via LtListStructure so it doesn't need it's own.
pub trait ReifyLt<L: LtList>: LtListStructure {
    /// Some subset of `L` with the same length as `Self`.
    ///
    /// For example, if `L = <'a, 'b, 'c>` and `Self` has length 2, then
    /// `Lifetimes = <'a, 'b>`.
    type Lifetimes: LtList<Tag = Self> + Subset<L>;
}

/// Helper for [`ReifyLt::Lifetimes`].
pub type LifetimesOf<T, L> = <T as ReifyLt<L>>::Lifetimes;

impl<L: LtList> ReifyLt<L> for () {
    type Lifetimes = ();
}

/// [`Lt`] without it's lifetime.
pub struct EmptyLt<Tail>(Tail);

impl<'lt, Tail: ReifyLt<L::Tail>, L: LtList<Head = Lt<'lt>>> ReifyLt<L> for EmptyLt<Tail>
where
    Lt<'lt, <Tail as ReifyLt<L::Tail>>::Lifetimes>: Subset<L>,
{
    type Lifetimes = Lt<'lt, <Tail as ReifyLt<L::Tail>>::Lifetimes>;
}

/// Implemented when `Self` is a subset of another list of lifetimes.
///
/// Being a subset means that the list has less or equal lifetimes than the other list.
/// For example, `<'a, 'b>` is a subset of `<'a, 'b, 'c>` because there is an extra `'c`
/// lifetime. Additionally, all lists are subsets of themselves. However, different lifetimes
/// do not form a subset. For example, `<'a, 'b>` is not a subset of `<'c, 'd, 'e>` where `'a !=
/// 'c` and `'b != 'd`.
///
/// This property is used to allow providing values with less lifetime needs than the
/// provider can provide.
///
/// This trait is sealed and is only implemented by `()` and [`Lt`].
pub trait Subset<More: lt_list_seal::Sealed>: lt_list_seal::Sealed {}

impl<L: LtList> Subset<L> for () {}
impl Subset<()> for Lt<'static> {}
impl<'lt, Tail: LtList + Subset<L>, L: LtList> Subset<Lt<'lt, L>> for Lt<'lt, Tail> {}

/// Merge two lifetime list structures into one by taking the larger.
///
/// This trait is sealed and is only implemented by `()` and [`EmptyLt`].
pub trait Merge<L: empty_tag_seal::Sealed>: Sized + empty_tag_seal::Sealed {
    /// The larger of the lifetime list structures.
    type LtStructure: LtListStructure;
}

type M<L1, L2> = <L1 as Merge<L2>>::LtStructure;

impl<L: LtListStructure> Merge<L> for () {
    type LtStructure = L;
}

impl<Tail: LtListStructure + Merge<L::Tail>, L: LtListStructure> Merge<L> for EmptyLt<Tail> {
    type LtStructure = EmptyLt<<Tail as Merge<L::Tail>>::LtStructure>;
}

/// [`Merge`] but for a tuple of lifetime lists.
pub trait MergeTuple {
    /// The largest of the lifetime lists.
    type LtStructure: LtListStructure;
}

impl MergeTuple for () {
    type LtStructure = ();
}

impl<L: LtListStructure> MergeTuple for (L,) {
    type LtStructure = L;
}

impl<L0, L1> MergeTuple for (L0, L1)
where
    L0: LtListStructure,
    L1: LtListStructure,
    L0: Merge<L1>,
{
    type LtStructure = M<L0, L1>;
}

impl<L0, L1, L2> MergeTuple for (L0, L1, L2)
where
    L0: LtListStructure,
    L1: LtListStructure,
    L2: LtListStructure,
    L0: Merge<L1>,
    M<L0, L1>: Merge<L2>,
{
    type LtStructure = M<M<L0, L1>, L2>;
}

impl<L0, L1, L2, L3> MergeTuple for (L0, L1, L2, L3)
where
    L0: LtListStructure,
    L1: LtListStructure,
    L2: LtListStructure,
    L3: LtListStructure,
    L0: Merge<L1>,
    M<L0, L1>: Merge<L2>,
    M<M<L0, L1>, L2>: Merge<L3>,
{
    type LtStructure = M<M<M<L0, L1>, L2>, L3>;
}

impl<L0, L1, L2, L3, L4> MergeTuple for (L0, L1, L2, L3, L4)
where
    L0: LtListStructure,
    L1: LtListStructure,
    L2: LtListStructure,
    L3: LtListStructure,
    L4: LtListStructure,
    L0: Merge<L1>,
    M<L0, L1>: Merge<L2>,
    M<M<L0, L1>, L2>: Merge<L3>,
    M<M<M<L0, L1>, L2>, L3>: Merge<L4>,
{
    type LtStructure = M<M<M<M<L0, L1>, L2>, L3>, L4>;
}

impl<L0, L1, L2, L3, L4, L5> MergeTuple for (L0, L1, L2, L3, L4, L5)
where
    L0: LtListStructure,
    L1: LtListStructure,
    L2: LtListStructure,
    L3: LtListStructure,
    L4: LtListStructure,
    L5: LtListStructure,
    L0: Merge<L1>,
    M<L0, L1>: Merge<L2>,
    M<M<L0, L1>, L2>: Merge<L3>,
    M<M<M<L0, L1>, L2>, L3>: Merge<L4>,
    M<M<M<M<L0, L1>, L2>, L3>, L4>: Merge<L5>,
{
    type LtStructure = M<M<M<M<M<L0, L1>, L2>, L3>, L4>, L5>;
}