use std::ops::Add;

use generic_array::{ArrayLength, GenericArray, functional::FunctionalSequence, sequence::Concat};
use typenum::{ATerm, B0, B1, Bit, Sum, TArr, U0, Unsigned};

use crate::{
    Enum, Size, SizeExt, ToOutput,
    enumkind::{EnumKind, UsizeTag},
};

/// This *might* contain a valid [`Niche`].
///
/// If `Self: Size`, a niche must have the same size.
///
/// A niche must satisfy these requirements if it *doesn't need a tag*:
/// - No valid values are a prefix of it, if `Self` is inline. Otherwise we might misinterpret a
///   concatenation.
/// - It's not a prefix of any values. Otherwise we wouldn't be able to parse some valid values.
pub trait MaybeHasNiche {
    /// Should implement [`MnArray`]. Not constraint explicitly, because that breaks things.
    type MnArray;
}

/// Special [`Niche`] to force use of a tag without any padding.
pub struct NicheForUnsized;

impl Niche for NicheForUnsized {
    type NeedsTag = B1;
    type Cut = B1;
    type N = U0;
    fn niche() -> GenericArray<u8, Self::N> {
        Default::default()
    }
    type Next = Self;
}

/// [`MaybeNiche`] asserting that `V` is a fake niche.
pub struct NoNiche<V>(V);
/// [`MaybeNiche`] asserting that `A` and `B` are fake niches.
pub struct NoNiche2<A, B>(A, B);
/// [`MaybeNiche`] asserting that `T` is a true niche.
pub struct AndNiche<V, T>(V, T);
/// [`MaybeNiche`] asserting that `T` is a true niche.
pub struct NicheAnd<T, V>(T, V);
/// [`MaybeNiche`] asserting that `T` is a true niche.
pub struct SomeNiche<T>(T);

/// True or fake (placeholder) niche.
pub trait Niche {
    /// Whether this is a fake niche (true niches, i.e. those which don't need a tag, don't
    /// represent a value).
    type NeedsTag: Bit;
    /// Whether to stop tail extension of this niche.
    type Cut: Bit;
    /// Length in bytes.
    type N: ArrayLength;
    /// Get the niche bytes.
    fn niche() -> GenericArray<u8, Self::N>;
    /// What we're left with once we occupy [`Self::niche`].
    type Next;
}

/// Conditionally implements [`Niche`]. Used to simplify derivations (and make them possible at
/// all).
pub trait MaybeNiche {
    /// Length in bytes.
    type N: Unsigned;
    /// Whether to stop tail extension of this niche.
    type Cut: Bit;
}

pub trait AsTailOf<U: MaybeNiche>: MaybeNiche {
    type WithHead: MaybeNiche;
}

pub trait AsHeadOf<U: MaybeNiche>: MaybeNiche {
    type WithTail: MaybeNiche;
}

impl<V: Niche<NeedsTag = B1>> Niche for NoNiche<V> {
    type NeedsTag = B1;
    type Cut = V::Cut;
    type N = V::N;
    fn niche() -> GenericArray<u8, Self::N> {
        V::niche()
    }
    type Next = Self;
}

impl<V: Niche<NeedsTag = B1>> MaybeNiche for NoNiche<V> {
    type N = V::N;
    type Cut = V::Cut;
}

impl<U: MaybeNiche<N: Add<V::N, Output: Unsigned>>, V: Niche<NeedsTag = B1>> AsTailOf<U>
    for NoNiche<V>
{
    type WithHead = NoNiche2<U, Self>;
}

impl<V: Niche<NeedsTag = B1, Cut = Cut>, U: AsTailOf<Self>, Cut: CutNone<Self, U>> AsHeadOf<U>
    for NoNiche<V>
{
    type WithTail = Cut::Cut;
}

impl<A: Niche<N: Add<B::N, Output: ArrayLength>>, B: Niche> Niche for NoNiche2<A, B> {
    type NeedsTag = B1;
    type Cut = B::Cut;
    type N = Sum<A::N, B::N>;
    fn niche() -> GenericArray<u8, Self::N> {
        Concat::concat(A::niche(), B::niche())
    }
    type Next = NoNiche<Self>;
}

impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> MaybeNiche for NoNiche2<A, B> {
    type N = Sum<A::N, B::N>;
    type Cut = B::Cut;
}

impl<
    U: MaybeNiche<N: Add<Sum<A::N, B::N>, Output: Unsigned>>,
    A: MaybeNiche<N: Add<B::N, Output: Unsigned>>,
    B: MaybeNiche,
> AsTailOf<U> for NoNiche2<A, B>
{
    type WithHead = NoNiche2<U, Self>;
}

impl<
    A: MaybeNiche<N: Add<B::N, Output: Unsigned>>,
    B: MaybeNiche<Cut = Cut>,
    U: AsTailOf<Self>,
    Cut: CutNone<Self, U>,
> AsHeadOf<U> for NoNiche2<A, B>
{
    type WithTail = Cut::Cut;
}

impl<
    V: Niche<N = N, NeedsTag: NicheAuto>,
    N: ArrayLength + Add<T::N, Output: ArrayLength>,
    T: Niche,
> Niche for AndNiche<V, T>
{
    type NeedsTag = T::NeedsTag;
    type Cut = T::Cut;
    type N = Sum<N, T::N>;
    fn niche() -> GenericArray<u8, Self::N> {
        Concat::concat(V::niche(), T::niche())
    }
    type Next = AndNiche<AutoNiche<V>, T::Next>;
}

impl<V: MaybeNiche<N = N>, N: Unsigned, T: MaybeNiche> MaybeNiche for AndNiche<V, T>
where
    N: Add<T::N, Output: Unsigned>,
{
    type N = Sum<N, T::N>;
    type Cut = T::Cut;
}

impl<
    U: MaybeNiche<N: Add<Sum<N, T::N>, Output: Unsigned>>,
    V: MaybeNiche<N = N>,
    N: Unsigned,
    T: MaybeNiche,
> AsTailOf<U> for AndNiche<V, T>
where
    N: Add<T::N, Output: Unsigned>,
{
    type WithHead = AndNiche<U, Self>;
}

impl<
    V: MaybeNiche<N = N>,
    N: Unsigned,
    T: MaybeNiche<Cut = Cut>,
    U: MaybeNiche,
    Cut: CutSome<Self, U>,
> AsHeadOf<U> for AndNiche<V, T>
where
    N: Add<T::N, Output: Unsigned>,
    Sum<N, T::N>: Add<U::N, Output: Unsigned>,
{
    type WithTail = Cut::Cut;
}

impl<T: Niche<N: Add<N, Output: ArrayLength>>, V: Niche<N = N, NeedsTag: NicheAuto>, N: ArrayLength>
    Niche for NicheAnd<T, V>
{
    type NeedsTag = T::NeedsTag;
    type Cut = V::Cut;
    type N = Sum<T::N, N>;
    fn niche() -> GenericArray<u8, Self::N> {
        Concat::concat(T::niche(), V::niche())
    }
    type Next = NicheAnd<T::Next, AutoNiche<V>>;
}

impl<T: MinNiche, V> MinNiche for NicheAnd<T, V> {}

impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> MaybeNiche
    for NicheAnd<T, V>
{
    type N = Sum<T::N, N>;
    type Cut = V::Cut;
}

impl<
    U: MaybeNiche<N: Add<Sum<T::N, N>, Output: Unsigned>>,
    T: MaybeNiche<N: Add<N, Output: Unsigned>>,
    V: MaybeNiche<N = N>,
    N: Unsigned,
> AsTailOf<U> for NicheAnd<T, V>
{
    type WithHead = AndNiche<U, Self>;
}

impl<
    T: MaybeNiche<N: Add<N, Output: Unsigned>>,
    V: MaybeNiche<N = N, Cut = Cut>,
    N: Unsigned,
    U: MaybeNiche,
    Cut: CutSome<Self, U>,
> AsHeadOf<U> for NicheAnd<T, V>
where
    Sum<T::N, N>: Add<U::N, Output: Unsigned>,
{
    type WithTail = Cut::Cut;
}

impl<T: Niche<NeedsTag = B0>> Niche for SomeNiche<T> {
    type NeedsTag = T::NeedsTag;
    type Cut = T::Cut;
    type N = T::N;
    fn niche() -> GenericArray<u8, Self::N> {
        T::niche()
    }
    type Next = T::Next;
}

impl<T: MinNiche> MinNiche for SomeNiche<T> {}

impl<T: Niche<NeedsTag = B0>> MaybeNiche for SomeNiche<T> {
    type N = T::N;
    type Cut = T::Cut;
}

impl<U: MaybeNiche<N: Add<T::N, Output: Unsigned>>, T: Niche<NeedsTag = B0>> AsTailOf<U>
    for SomeNiche<T>
{
    type WithHead = AndNiche<U, Self>;
}

impl<
    T: Niche<N: Add<U::N, Output: Unsigned>, NeedsTag = B0, Cut = Cut>,
    U: MaybeNiche,
    Cut: CutSome<Self, U>,
> AsHeadOf<U> for SomeNiche<T>
{
    type WithTail = Cut::Cut;
}

/// Array ([`typenum`]-ish) that *might* be reducible down to a [`Niche`].
pub trait MnArray {
    /// Possibly, [`Niche`].
    type MaybeNiche: MaybeNiche;
}

impl MnArray for ATerm {
    type MaybeNiche = NoNiche<ZeroNoNiche<U0>>;
}

impl<T: MaybeNiche> MnArray for T {
    type MaybeNiche = T;
}

impl<T: MnArray<MaybeNiche = U>, U: AsHeadOf<R::MaybeNiche>, R: MnArray> MnArray for TArr<T, R> {
    type MaybeNiche = U::WithTail;
}

/// Already occupied/unusable byte representation filled with `0x00` bytes.
pub struct ZeroNoNiche<N>(N);

impl<N: ArrayLength> Niche for ZeroNoNiche<N> {
    type NeedsTag = B1;
    type Cut = B0;
    type N = N;
    fn niche() -> GenericArray<u8, Self::N> {
        GenericArray::default()
    }
    type Next = NoNiche<Self>;
}

/// Niche filled with `0x00` bytes.
pub struct ZeroNiche<N, Next = NoNiche<ZeroNoNiche<N>>>(N, Next);

impl<N: ArrayLength, Next> Niche for ZeroNiche<N, Next> {
    type NeedsTag = B0;
    type Cut = B0;
    type N = N;
    fn niche() -> GenericArray<u8, Self::N> {
        GenericArray::default()
    }
    type Next = Next;
}

impl<N: ArrayLength, Next> MinNiche for ZeroNiche<N, Next> {}

/// Niche filled with `0xFF` bytes.
pub struct OneNiche<N>(N);

impl<N: ArrayLength> Niche for OneNiche<N> {
    type NeedsTag = B0;
    type Cut = B0;
    type N = N;
    fn niche() -> GenericArray<u8, Self::N> {
        GenericArray::default().map(|()| 0xff)
    }
    type Next = NoNiche<ZeroNoNiche<N>>;
}

#[doc(hidden)]
pub trait NicheOr: MaybeNiche {
    type NicheOr<U: NicheOr<N = Self::N>>: NicheOr<N = Self::N>;
    fn index(index: usize) -> usize;
}

impl<V: Niche<NeedsTag = B1>> NicheOr for NoNiche<V> {
    type NicheOr<U: NicheOr<N = Self::N>> = U;
    fn index(index: usize) -> usize {
        index + 1
    }
}

impl<A: MaybeNiche<N: Add<B::N, Output: Unsigned>>, B: MaybeNiche> NicheOr for NoNiche2<A, B> {
    type NicheOr<U: NicheOr<N = Self::N>> = U;
    fn index(index: usize) -> usize {
        index + 1
    }
}

impl<V: MaybeNiche<N = N>, N: Unsigned + Add<T::N, Output: Unsigned>, T: MaybeNiche> NicheOr
    for AndNiche<V, T>
{
    type NicheOr<U: NicheOr<N = Self::N>> = Self;
    fn index(_: usize) -> usize {
        0
    }
}

impl<T: MaybeNiche<N: Add<N, Output: Unsigned>>, V: MaybeNiche<N = N>, N: Unsigned> NicheOr
    for NicheAnd<T, V>
{
    type NicheOr<U: NicheOr<N = Self::N>> = Self;
    fn index(_: usize) -> usize {
        0
    }
}

impl<T: Niche<NeedsTag = B0>> NicheOr for SomeNiche<T> {
    type NicheOr<U: NicheOr<N = Self::N>> = Self;
    fn index(_: usize) -> usize {
        0
    }
}

pub trait NicheFoldOr {
    type Or: NicheOr;
    fn index() -> usize;
}

impl<T: MnArray<MaybeNiche: NicheOr>> NicheFoldOr for TArr<T, ATerm> {
    type Or = T::MaybeNiche;
    fn index() -> usize {
        0
    }
}

impl<T: NicheOr, A: NicheFoldOr<Or: MaybeNiche<N = T::N>>> NicheFoldOr for TArr<T, A> {
    type Or = T::NicheOr<A::Or>;
    fn index() -> usize {
        T::index(A::index())
    }
}

#[doc(hidden)]
pub struct NicheFoldOrArray<T>(T);

impl<T: NicheFoldOr> MnArray for NicheFoldOrArray<T> {
    type MaybeNiche = T::Or;
}

pub struct EnumNiche<E, const X: usize>(E);

impl<
    E: Enum<Kind = K>,
    K: EnumKind<Tag = T>,
    T: UsizeTag + ToOutput + Size<Size = N> + MaybeHasNiche<MnArray: MnArray<MaybeNiche = V>>,
    V: Niche<N = N>,
    N: ArrayLength,
    const X: usize,
> Niche for EnumNiche<E, X>
{
    type NeedsTag = V::NeedsTag;
    type Cut = B0;
    type N = N;
    fn niche() -> GenericArray<u8, Self::N> {
        if V::NeedsTag::BOOL {
            T::from_usize(X).to_array()
        } else {
            V::niche()
        }
    }
    type Next = NoNiche<ZeroNoNiche<N>>;
}

pub trait NicheAuto: Bit {
    type Auto<T: Niche<NeedsTag = Self>>: MaybeNiche<N = T::N>;
}

impl NicheAuto for B0 {
    type Auto<T: Niche<NeedsTag = Self>> = SomeNiche<T>;
}

impl NicheAuto for B1 {
    type Auto<T: Niche<NeedsTag = Self>> = NoNiche<T>;
}

#[doc(hidden)]
pub type AutoNiche<T> = <<T as Niche>::NeedsTag as NicheAuto>::Auto<T>;

#[doc(hidden)]
pub type AutoEnumNiche<E, const X: usize> = AutoNiche<EnumNiche<E, X>>;

#[doc(hidden)]
pub struct HackNiche<const X: usize>;

impl<const X: usize> Niche for HackNiche<X> {
    type NeedsTag = B1;
    type Cut = B0;
    type N = U0;
    fn niche() -> GenericArray<u8, Self::N> {
        GenericArray::default()
    }
    type Next = NoNiche<Self>;
}

/// This niche precedes all non-niche values.
pub trait MinNiche {}

pub trait CutSome<A, B> {
    type Cut: MaybeNiche;
}

impl<A, B> CutSome<A, B> for B0
where
    NicheAnd<A, B>: MaybeNiche,
{
    type Cut = NicheAnd<A, B>;
}

impl<A: MaybeNiche, B> CutSome<A, B> for B1 {
    type Cut = A;
}

pub trait CutNone<A, B> {
    type Cut: MaybeNiche;
}

impl<A: MaybeNiche, B: AsTailOf<A>> CutNone<A, B> for B0 {
    type Cut = B::WithHead;
}

impl<A: MaybeNiche, B> CutNone<A, B> for B1 {
    type Cut = A;
}
