Type-level list in Rust.

type_list.rs

//! A type-level list implementation that can assert
//! a list must contain a specific type element.

use std::marker::PhantomData;

/// Type-level boolean.
pub trait Bool {}

/// Type-level `false`.
pub struct False;
impl Bool for False {}

/// Type-level `true`.
pub struct True;
impl Bool for True {}

/// Trait for computing type-level logical OR.
pub trait TypeOr<T: Bool> {
    type Output: Bool;
}

/// Result of type-level logical OR.
pub type Or<T, U> = <T as TypeOr<U>>::Output;

impl TypeOr<False> for False {
    type Output = False;
}

impl TypeOr<True> for False {
    type Output = True;
}

impl TypeOr<False> for True {
    type Output = True;
}

impl TypeOr<True> for True {
    type Output = True;
}

/// Trait for computing type-level logical AND.
pub trait TypeAnd<T: Bool> {
    type Output: Bool;
}

/// Result of type-level logical AND.
pub type And<T, U> = <T as TypeAnd<U>>::Output;

impl TypeAnd<False> for False {
    type Output = False;
}

impl TypeAnd<True> for False {
    type Output = False;
}

impl TypeAnd<False> for True {
    type Output = False;
}

impl TypeAnd<True> for True {
    type Output = True;
}

/// Trait for computing type-level equality.
pub trait TypeEq<T> {
    type Output: Bool;
}

/// Helper macro for implementing `TypeEq` for types.
macro_rules! impl_type_eq {
    ($($t:ty),+ $(,)?) => {
        impl_type_eq!(@expand () $(,$t)+);
    };
    (@expand ($($pre:ty),*), $cur:ty $(,$post:ty)*) => {
        $(impl_type_eq!(@impl $cur, $pre, False);)*
        impl_type_eq!(@impl $cur, $cur, True);
        $(impl_type_eq!(@impl $cur, $post, False);)*
        impl_type_eq!(@expand ($($pre,)* $cur) $(,$post)*);
    };
    (@expand ($($pre:ty),*)) => {};
    (@impl $t1:ty, $t2:ty, $out:ty) => {
        impl TypeEq<$t2> for $t1 {
            type Output = $out;
        }
    };
}

/// Result of type-level equality.
pub type Equals<T, U> = <T as TypeEq<U>>::Output;

/// Type-level list.
pub trait List {}

/// Type-level empty list.
pub struct Nil;
impl List for Nil {}

/// Type-level list element.
pub struct Cons<T, L: List>(PhantomData<(T, L)>);
impl<T, L: List> List for Cons<T, L> {}

/// Helper macro for constructing list type.
macro_rules! list {
    [] => { Nil };
    [$head:ty $(,$t:ty)* $(,)?] => { Cons<$head, list![$($t),*]> };
}

/// Trait for computing type-level list contains (for element).
pub trait TypeContains<T> {
    type Output: Bool;
}

/// Result of type-level list contains (for element).
pub type Contains<L, T> = <L as TypeContains<T>>::Output;

impl<T> TypeContains<T> for Nil {
    type Output = False;
}

impl<T, U, L> TypeContains<T> for Cons<U, L>
where
    T: TypeEq<U>,
    L: List + TypeContains<T>,
    Equals<T, U>: TypeOr<Contains<L, T>>,
{
    type Output = Or<Equals<T, U>, Contains<L, T>>;
}

/// Trait for computing type-level list contains (for another list).
pub trait TypeContainsList<L: List> {
    type Output: Bool;
}

/// Result of type-level list contains (for another list).
pub type ContainsList<L, L2> = <L as TypeContainsList<L2>>::Output;

impl<L> TypeContainsList<Nil> for L
where
    L: List,
{
    type Output = True;
}

impl<T, L, L2> TypeContainsList<Cons<T, L>> for L2
where
    L: List,
    L2: List + TypeContains<T> + TypeContainsList<L>,
    Contains<L2, T>: TypeAnd<ContainsList<L2, L>>,
{
    type Output = And<Contains<L2, T>, ContainsList<L2, L>>;
}

// Some list element types.
struct E1;
struct E2;
struct E3;

impl_type_eq!(E1, E2, E3);

/// This function requires the input list type contains `E2`.
fn must_contains_e2<L: TypeContains<E2, Output = True>>() {}

/// This function requires the input list type contains `[E3, E1]`.
fn must_contains_e3_e1<L: TypeContainsList<list![E3, E1], Output = True>>() {}

fn main() {
    must_contains_e2::<list![E2]>();
    must_contains_e2::<list![E1, E2, E3]>();
    must_contains_e2::<list![E2, E1, E3]>();
    must_contains_e2::<list![E1, E3, E2]>();
    must_contains_e2::<list![E2, E2, E2]>();
    // Does not compile:
    // must_contains_e2::<list![E1]>();
    // must_contains_e2::<list![E3, E1]>();

    must_contains_e3_e1::<list![E1, E2, E3]>();
    must_contains_e3_e1::<list![E2, E1, E3]>();
    must_contains_e3_e1::<list![E1, E3, E2]>();
    must_contains_e3_e1::<list![E3, E1]>();
    // Does not compile:
    // must_contains_e3_e1::<list![E1]>();
    // must_contains_e3_e1::<list![E2]>();
    // must_contains_e3_e1::<list![E2, E2, E2]>();
}