//! Higher-ranked traits and types.
//!
//! A higher-ranked type is a type that needs a lifetime to be "complete". Consider the following
//! code.
//! ```rs
//! type IntBorrow<'a> = &'a i32;
//! ```
//! What if we could pass just `IntBorrow` around as a type; without it's lifetime.
//! In Rust syntax, this type would be `for<'a> IntBorrow<'a>`. `'a` can be filled in with any
//! lifetime. Sadly, Rust only allows `for<'a>` in trait objects. However, trait object provide
//! enough for us to implement arbitrary hifher-ranked types with some extra effort.
//!
//! In this module the [`higher_ranked_type!`] macro generates a type that needs a lifetime to
//! be complete. Before a higher-ranked type can be generated we need a higher-ranked trait to
//! describe what behavior the resulting "true" type will have.
//!
//! The [`higher_ranked_trait!`] macro cgenerates a trait that can be used with
//! [`higher_ranked_type!`] and as a bound by code wanting to accept a higher ranked type.
//! Bounding a generic by a higher-ranked trait simultaniously allows any higher-ranked type with
//! a "true" type with the required traits and any lifetime to be given to that "true" type.

/// Used to cause `'lt` to have extra bounds when using `for<'lt>` syntax.
///
/// Including this type where a `for<'lt>` is being generated will result in the following bounds
/// being applied.
/// * `'bound: 'lt` - `'lt` will **not** outlive `'bound`.
/// * `T: 'lt` - `T` will outlive `'lt`.
pub type Bound<'lt, 'bound, T = ()> = (&'lt &'bound (), &'lt T);

/// Generate a higher-ranked trait.
#[doc(hidden)]
#[macro_export]
macro_rules! higher_ranked_trait {
    {
        $vis:vis type class $name:ident[$ctx:lifetime $(, $($generic:tt)*)?]: [for<$lt:lifetime> $($($provides:tt)+)?]
        $(where {
            $($bound:tt)*
        })?
        $(for where {
            $($for_bound:tt)*
        })?
    } => {
        $vis mod $name {
            #![allow(unused, non_snake_case)]

            use super::*;

            pub trait ForLt<$lt, $ctx: $lt, B $(, $($generic)*)?>
            where $($($bound)*)? $($($for_bound)*)?

            {
                type T: $lt $(+ $($provides)+)?;
            }

            pub trait Trait<$ctx $(, $($generic)*)?>: for<$lt> ForLt<$lt, $ctx, $crate::hkt::Bound<$lt, $ctx $(, $($generic)*)?> $(, $($generic)*)?>
            where
                $($($bound)*)?
            {}

            impl<$ctx, ____ $(, $($generic)*)?> Trait<$ctx $(, $($generic)*)?> for ____
            where
                ____: for<$lt> ForLt<$lt, $ctx, $crate::hkt::Bound<$lt, $ctx $(, $($generic)*)?> $(, $($generic)*)?>,
                $($($bound)*)?
            {}

            pub type T<$lt, $ctx, H $(, $($generic)*)?> = <H as ForLt<$lt, $ctx, $crate::hkt::Bound<$lt, $ctx $(, $($generic)*)?> $(, $($generic)*)?>>::T;
        }
    };
}

use core::marker::PhantomData;

#[doc(inline)]
pub use higher_ranked_trait;

/// Generate a higher-ranked type.
#[doc(hidden)]
#[macro_export]
macro_rules! higher_ranked_type {
    {
        $vis:vis type $name:ident[$ctx:lifetime $(, $($generic:tt)*)?]: ($($type_class:tt)*)$([$($type_class_generic:tt)*])?
        $(where {$($bound:tt)*})?
        = for<$lt:lifetime> $for_lt_type:ty
        $(where {$($higher_bound:tt)*})?
    } => {
        $vis struct $name<$ctx $(, $($generic)*)?>(core::marker::PhantomData<fn() -> (&$ctx (), $($($generic)*)?)>);

        impl<$lt, $ctx $(, $($generic)*)?> $($type_class)*::ForLt<$lt, $ctx, $crate::hkt::Bound<$lt, $ctx $(, $($generic)*)?> $(, $($type_class_generic)*)?> for $name<$ctx $(, $($generic)*)?>
        where $($($bound)*)? $($($higher_bound)*)?
        {
            type T = $for_lt_type;
        }
    }
}

#[doc(inline)]
pub use higher_ranked_type;

#[doc(hidden)]
#[macro_export]
macro_rules! bijective_higher_ranked_trait {
    {
        $(#[$($meta:tt)*])*
        $vis:vis type class $name:ident[
            $($lifetimes:lifetime),*
        ][
            $($generic:ident),*
        ]: $({$($self_provides:tt)*})? [for<$lt:lifetime> $($($provides:tt)+)?]
        $(where {
            $($bound:tt)*
        })?
        $(for where {
            $($for_bound:tt)*
        })?
    } => {
        $(#[$($meta)*])*
        $vis mod $name {
            #![allow(unused, non_snake_case)]

            use super::*;

            /// Trait for lowering a higher ranked type to a lower type.
            ///
            /// Do not use this trait directly instead use the [`MemberType`] trait and [`T`]
            /// type alias.
            ///
            /// This acts to inject a lifetime into the higher ranked type to make it concrete.
            pub trait LowerForLt<$lt, $($lifetimes: $lt,)* B: $lt, $($generic: $lt),*> $(: $($self_provides)*)?
            where
                $($($bound)*)?
                $($($for_bound)*)?
            {
                /// The lower type for this higher ranked type.
                ///
                /// The lower type must live for a minimum of the injected lifetime.
                ///
                /// Note this type must be raisable back to the same higher ranked type to make
                /// this a bijective mapping.
                type T: ?Sized + RaiseForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic,)*
                    HigherRanked = Self
                > $(+ $($provides)+)? + $lt;
            }

            /// Trait for raising a lower type to it's higher ranked form.
            ///
            /// Do not use this trait directly instead use the [`LowerType`] trait and [`HigherRanked`]
            /// type alias.
            ///
            /// this acts to remove a lifetime from the lower type.
            pub trait RaiseForLt<$lt, $($lifetimes: $lt,)* B: $lt, $($generic: $lt),*>
            where
                $($($bound)*)?
                $($($for_bound)*)?
            {
                /// The higher ranked type for this lower type.
                ///
                /// Note this type must be lowerable back to the same lower type to make
                /// this a bijective mapping.
                type HigherRanked: ?Sized + LowerForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic,)*
                    T = Self
                > $(+ $lifetimes)*;
            }

            /// Trait for higher ranked types of this form.
            ///
            /// A higher ranked type can have a lifetime injected to form a lower type.
            /// To perform this operation use the [`T`] type alias.
            ///
            /// This is basically a trait alias for the bound `for<'a> LowerForLt<'a, ...>`.
            pub trait MemberType<$($lifetimes,)* $($generic),*>:
                for<$lt> LowerForLt<
                    $lt,
                    $($lifetimes,)*
                    // Use a implied bound to make sure the lifetime from the for syntax is
                    // correctly bounded.
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic),*
                >
            where
                $($($bound)*)?
            {}

            // Impl the higher ranked trait for all higher ranked types with the ability to lower.
            impl<
                $($lifetimes,)*
                __: ?Sized,
                $($generic),*
            > MemberType<$($lifetimes,)* $($generic),*> for __
            where
                __: for<$lt> LowerForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic),*
                >,
                $($($bound)*)?
            {}

            /// Inject a lifetime into a higher ranked type to form its lower type.
            pub type T<$lt, $($lifetimes,)* __, $($generic),*> =
                <__ as LowerForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic),*
                >>::T;

            /// Trait for lower types with a higher ranked form.
            ///
            /// A lower type can have a lifetime removed to form a higher ranked type.
            /// To perform this operation use the [`HigherRanked`] type alias.
            ///
            /// This is basically a trait alias for the bound `RaiseForLt<'a, ...>`.
            pub trait LowerType<
                $lt,
                $($lifetimes: $lt,)*
                $($generic: $lt),*
            >: RaiseForLt<
                $lt,
                $($lifetimes,)*
                &$lt ($(&$lifetimes (),)* $($generic),*),
                $($generic),*
            > $(+ $($provides)+)?
            where
                $($($bound)*)?
            {}

            // Impl the lower type trait for all lower types with the ability to raise.
            impl<
                $lt,
                $($lifetimes: $lt,)*
                __: ?Sized,
                $($generic: $lt),*
            > LowerType<$lt, $($lifetimes,)* $($generic),*> for __
            where
                __: RaiseForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic),*
                > $(+ $($provides)+)?,
                $($($bound)*)?
            {}

            /// Remove a lifetime into a lower type to form its higher ranked type.
            pub type HigherRanked<$lt, $($lifetimes,)* __, $($generic),*> =
                <__ as RaiseForLt<
                    $lt,
                    $($lifetimes,)*
                    &$lt ($(&$lifetimes (),)* $($generic),*),
                    $($generic),*
                >>::HigherRanked;
        }
    };
}

#[doc(inline)]
pub use bijective_higher_ranked_trait;

/// Generate a higher-ranked type.
#[doc(hidden)]
#[macro_export]
macro_rules! bijective_higher_ranked_type {
    {
        $(#[$($meta:tt)*])*
        $vis:vis type $name:ident[
            $($ctx:lifetime),*
        ][
            $($generic:ident),*
        ]$([
            $($forwarding_generic:ident[$($forward_lt:lifetime),*][$($forward_generic:ident),*]),*
        ])?: $type_class:ident[$($type_class_lifetime:lifetime)*][$($type_class_generic:ident)*]
        for<$lt:lifetime>
        ($for_lt_type:ty)
        ($higher_ranked_type:ty)
        $(where {$($bound:tt)*})?
    } => {
        $(#[$($meta)*])*
        $vis struct $name<
            $($type_class_lifetime,)*
            $($generic: ?Sized,)*
            $($($forwarding_generic: ?Sized),*)?
        >(
            core::marker::PhantomData<fn() -> (
                $(&$type_class_lifetime (),)*
                $(*const $generic,)*
                $($(*const $forwarding_generic,)*)?
            )>
        );

        impl<
            $lt,
            $($ctx,)*
            $($generic,)*
            $($($forwarding_generic),*)?
        > $type_class::LowerForLt<
            $lt,
            $($type_class_lifetime,)*
            &$lt (
                $(&$type_class_lifetime (),)*
                $(*const $type_class_generic,)*
            ),
            $($type_class_generic),*
        > for $name<
            $($type_class_lifetime,)*
            $($generic,)*
            $($($forwarding_generic),*)?
        >
        where
            $($(
                $forwarding_generic: $type_class::LowerForLt<
                    $lt,
                    $($forward_lt,)*
                    &$lt (
                        $(&$forward_lt (),)*
                        $(*const $forward_generic,)*
                    )
                    $($forward_generic,)*
                >,
            )*)?
            $($($bound)*)?
        {
            type T = $for_lt_type;
        }

        impl<
            $lt,
            $($ctx,)*
            $($generic,)*
            $($($forwarding_generic),*)?
        > $type_class::RaiseForLt<
            $lt,
            $($type_class_lifetime,)*
            &$lt (
                $(&$type_class_lifetime (),)*
                $(*const $type_class_generic,)*
            ),
            $($type_class_generic),*
        > for $higher_ranked_type
        where
            $($(
                $forwarding_generic: $type_class::RaiseForLt<
                    $lt,
                    $($forward_lt,)*
                    &$lt (
                        $(&$forward_lt (),)*
                        $(*const $forward_generic,)*
                    )
                    $($forward_generic,)*
                >,
            )*)?
            $($($bound)*)?
        {
            type HigherRanked = $name<
                $($type_class_lifetime,)*
                $($generic,)*
                $($(
                    <$forwarding_generic as $type_class::RaiseForLt<
                        $lt,
                        $($forward_lt,)*
                        &$lt (
                            $(&$forward_lt (),)*
                            $(*const $forward_generic,)*
                        )
                        $($forward_generic,)*
                    >>::HigherRanked
                ),*)?
            >;
        }
    };
    {
        $vis:vis type [
            $($ctx:lifetime),*
        ][
            $($generic:ident),*
        ]$([
            $($forwarding_generic:ident[$($forward_lt:lifetime),*][$($forward_generic:ident),*]),*
        ])?: $type_class:ident[$($type_class_lifetime:lifetime)*][$($type_class_generic:ident)*]
        for<$lt:lifetime>
        ($for_lt_type:ty)
        $(($higher_ranked_type:ty))?
        $(where {$($bound:tt)*})?
    } => {
        const _: () = {
            $crate::hkt::bijective_higher_ranked_type! {
                $vis type __HigherRanked[
                    $($ctx),*
                ][
                    $($generic),*
                ]$([
                    $($forwarding_generic[$($forward_lt),*][$($forward_generic),*]),*
                ])?: $type_class[$($type_class_lifetime)*][$($type_class_generic)*]
                for<$lt>
                ($for_lt_type)
                $(($higher_ranked_type))?
                $(where {$($bound)*})?
            }
        };
    };
    {
        $(#[$($meta:tt)*])*
        $vis:vis type $name:ident[
            $($ctx:lifetime),*
        ][
            $($generic:ident),*
        ]$([
            $($forwarding_generic:ident[$($forward_lt:lifetime),*][$($forward_generic:ident),*]),*
        ])?: $type_class:ident[$($type_class_lifetime:lifetime)*][$($type_class_generic:ident)*]
        for<$lt:lifetime>
        ($for_lt_type:ty)
        $(where {$($bound:tt)*})?
    } => {
        $crate::hkt::bijective_higher_ranked_type! {
            $(#[$($meta)*])*
            $vis type $name[
                $($ctx),*
            ][
                $($generic),*
            ]$([
                $($forwarding_generic[$($forward_lt),*][$($forward_generic),*]),*
            ])?: $type_class[$($type_class_lifetime)*][$($type_class_generic)*]
            for<$lt>
            ($for_lt_type)
            ($for_lt_type)
            $(where {$($bound)*})?
        }
    }
}

#[doc(inline)]
pub use bijective_higher_ranked_type;

higher_ranked_trait! {
    pub type class AnySend['ctx]: [for<'lt> Send]
}

#[cfg(test)]
mod test {
    use super::*;

    /// Some trait with two lifetimes and a generic.
    trait Demo<'lt, 'ctx, T: Send + 'lt> {
        fn add(&self, x: &'lt &'ctx i32) -> i32;
    }

    impl<'lt, 'ctx, T: Send + 'lt> Demo<'lt, 'ctx, T> for i32 {
        fn add(&self, x: &'lt &'ctx i32) -> i32 {
            self + **x
        }
    }

    impl<'lt, 'ctx, T: Send + 'lt> Demo<'lt, 'ctx, T> for &'lt (dyn Demo<'lt, 'ctx, T> + 'lt) {
        fn add(&self, x: &'lt &'ctx i32) -> i32 {
            (**self).add(x)
        }
    }

    // Higher-ranked trait that requires the "true" type to implement Demo.
    higher_ranked_trait! {
        type class Any['ctx, T]: [for<'lt> Demo<'lt, 'ctx, T>]
        where {
            T: Send,
        }
        for where {
            T: 'lt
        }
    }

    // Higher-ranked type with a "true" type of a borrow of a trait object.
    // The complex part to support here is the `+ 'lt`.
    // This entire module is specialized to support this usecase because that is what treaty needs
    // for it's API.
    higher_ranked_type! {
        type X['ctx, T]: (Any)[T]
        where {
            T: Send,
        } = for<'lt> &'lt (dyn Demo<'lt, 'ctx, T> + 'lt)
    }

    // We bound the generic T by the higher-ranked trait Any.
    //
    // We then inject a 'lt into the higher-ranked type to get a "true" type.
    fn demo<'lt, 'ctx, T: Any::Trait<'ctx, i32>>(x: Any::T<'lt, 'ctx, T, i32>, y: &'lt &'ctx i32) {
        assert_eq!(x.add(y), 10);
    }

    #[test]
    fn can_use_hkt() {
        let ctx = 2;
        let ctx = &ctx;

        {
            // The lifetimes here can't be 'static because local isn't static even though z could be.
            let local = &ctx;
            let z: &dyn Demo<'_, '_, i32> = &8i32;
            demo::<X<'_, i32>>(z, local);
        }
    }
}