Сопровождающий код к статье "Как написать FizzBuzz на собеседовании" (habr.com/ru/post/578198)

main.rs

struct Z;
struct S<T>(T);

trait Add<Rhs> {
    type Sum;
}

type SumOf<N, M> = <N as Add<M>>::Sum;

impl<N> Add<N> for Z {
    type Sum = N;
}

impl<N, M> Add<M> for S<N>
where
    N: Add<S<M>>,
{
    type Sum = SumOf<N, S<M>>;
}

type One = S<Z>;
type Two = SumOf<One, One>;
type Three = SumOf<One, Two>;
type Five = SumOf<Two, Three>;
type Ten = SumOf<Five, Five>;
type TwentyFive = SumOf<Five, SumOf<Ten, Ten>>;
type Fifty = SumOf<TwentyFive, TwentyFive>;
type OneHundred = SumOf<Fifty, Fifty>;

type N = OneHundred;

struct Nil;
struct Cons<H, T>(H, T);

trait RangeDownFrom {
    type Output;
}

impl RangeDownFrom for Z {
    type Output = Cons<Z, Nil>;
}

impl<N> RangeDownFrom for S<N>
where
    N: RangeDownFrom,
{
    type Output = Cons<S<N>, N::Output>;
}

type MakeRangeDownFrom<N> = <N as RangeDownFrom>::Output;

trait ReverseWith<Acc> {
    type Output;
}

impl<Acc> ReverseWith<Acc> for Nil {
    type Output = Acc;
}

impl<Head, Tail, Acc> ReverseWith<Acc> for Cons<Head, Tail>
where
    Tail: ReverseWith<Cons<Head, Acc>>,
{
    type Output = <Tail as ReverseWith<Cons<Head, Acc>>>::Output;
}

type Reverse<List> = <List as ReverseWith<Nil>>::Output;
type RangeTo<N> = Reverse<MakeRangeDownFrom<N>>;

trait DecrementByMod<M> {
    type Output;
}

impl<T> DecrementByMod<S<T>> for Z {
    type Output = T;
}

impl<M, T> DecrementByMod<M> for S<T> {
    type Output = T;
}

type DecMod<T, M> = <T as DecrementByMod<M>>::Output;

trait EnumerateFromWithCycle<Start, N> {
    type Output;
}
type EnumeratedFromWithCycle<T, Start, N> = <T as EnumerateFromWithCycle<Start, N>>::Output;

impl<Start, N> EnumerateFromWithCycle<Start, N> for Nil {
    type Output = Nil;
}

impl<Start, N, Head, Tail> EnumerateFromWithCycle<Start, N> for Cons<Head, Tail>
where
    Start: DecrementByMod<N>,
    Tail: EnumerateFromWithCycle<DecMod<Start, N>, N>,
{
    type Output = Cons<(Head, Start), EnumeratedFromWithCycle<Tail, DecMod<Start, N>, N>>;
}

type EnumerateFromZeroWithCycle<T, N> = <T as EnumerateFromWithCycle<Z, N>>::Output;

type EnumerateFromZeroWithCycle3<T> = EnumerateFromZeroWithCycle<T, Three>;
type EnumerateFromZeroWithCycle5<T> = EnumerateFromZeroWithCycle<T, Five>;
type FizzBuzzEnumerate<T> = EnumerateFromZeroWithCycle5<EnumerateFromZeroWithCycle3<T>>;

struct Fizz;
struct Buzz;
struct FizzBuzz;

trait ToFizzBuzz {
    type Output;
}

type FizzBuzzed<T> = <T as ToFizzBuzz>::Output;

impl<T> ToFizzBuzz for ((T, Z), Z) {
    type Output = FizzBuzz;
}

impl<T, N> ToFizzBuzz for ((T, Z), S<N>) {
    type Output = Fizz;
}

impl<T, N> ToFizzBuzz for ((T, S<N>), Z) {
    type Output = Buzz;
}

impl<T, N, M> ToFizzBuzz for ((T, S<N>), S<M>) {
    type Output = T;
}

impl ToFizzBuzz for Nil {
    type Output = Nil;
}

impl<Head, Tail> ToFizzBuzz for Cons<Head, Tail> 
where
    Head: ToFizzBuzz,
    Tail: ToFizzBuzz,
{
    type Output = Cons<
        Head::Output,
        Tail::Output,
    >;
}

trait TailOf {
    type Output;
}

type Tail<T> = <T as TailOf>::Output;

impl<Head, Tail> TailOf for Cons<Head, Tail> {
    type Output = Tail;
}

type FizzBuzzList<T> = FizzBuzzed<Tail<FizzBuzzEnumerate<RangeTo<T>>>>;
type List = FizzBuzzList<N>;

trait AsStr<const N: usize> {
    const VALUE: Str<{ N }>;
}

impl<const N: usize> AsStr<{ N }> for Fizz {
    const VALUE: Str<{ N }> = Str::from_literal("fizz");
}

impl<const N: usize> AsStr<{ N }> for Buzz {
    const VALUE: Str<{ N }> = Str::from_literal("buzz");
}

impl<const N: usize> AsStr<{ N }> for FizzBuzz {
    const VALUE: Str<{ N }> = Str::from_literal("fizzbuzz");
}

trait NumericValue {
    const VALUE: usize;
}

impl NumericValue for Z {
    const VALUE: usize = 0;
}

impl<N> NumericValue for S<N>
where
	N: NumericValue,
{
    const VALUE: usize = N::VALUE + 1;
}

const fn to_str<const N: usize>(mut value: usize) -> Str<{ N }> {
    let mut s = [0; N];
    if value == 0 {
        s[0] = b'0';
        return unsafe { Str::from_parts_unchecked(s, 1) }
    }

    let mut i = 0;
    while value > 0 {
        s[i] = (value % 10) as u8 + b'0';
        value /= 10;
        i += 1;
    }

    let n_digits = i;
    let mut i = 0;
    while i < n_digits / 2 {
        let digit = s[n_digits - i - 1];
        s[n_digits - i - 1] = s[i];
        s[i] = digit;
        i += 1;
    }

    unsafe { Str::from_parts_unchecked(s, n_digits) }
}

impl<T, const N: usize> AsStr<{ N }> for T
where
    T: NumericValue,
{
    const VALUE: Str<{ N }> = to_str(<T as NumericValue>::VALUE);
}

trait AsStrList<const N: usize> {
    type List;
    const LIST: Self::List;
}

impl<const N: usize> AsStrList<{ N }> for Nil {
    type List = Nil;
    const LIST: Nil = Nil;
}

impl<Head, Tail, const N: usize> AsStrList<{ N }> for Cons<Head, Tail>
where
    Head: AsStr<{ N }>,
    Tail: AsStrList<{ N }>,
{
    type List = Cons<Str<{ N }>, Tail::List>;
    const LIST: Self::List = Cons(
        <Head as AsStr<{ N }>>::VALUE,
        <Tail as AsStrList<{ N }>>::LIST,
    );
}

mod str {
    pub struct Str<const N: usize>(StrInner<{ N }>);
    enum StrInner<const N: usize> {
        Plain(&'static str),
        Decomposed([u8; N], usize),
    }

    impl<const N: usize> Str<{ N }> {
        pub const fn from_literal(s: &'static str) -> Self {
            Self(StrInner::Plain(s))
        }

        pub const unsafe fn from_parts_unchecked(bytes: [u8; N], len: usize) -> Self {
            Self(StrInner::Decomposed(bytes, len))
        }

        pub fn as_str(&self) -> &str {
            match &self.0 {
                &StrInner::Plain(s) => s,
                &StrInner::Decomposed(ref bytes, len) => unsafe {
                    std::str::from_utf8_unchecked(bytes.get_unchecked(..len))
                }
            }
        }
    }
}

use crate::str::Str;

trait ForEach<Arg> {
    fn for_each<F>(&self, f: F)
    where
        F: FnMut(&Arg);
}

impl<Arg> ForEach<Arg> for Nil {
    fn for_each<F>(&self, _f: F)
    where
        F: FnMut(&Arg),
    {}
}

impl<Arg, Tail> ForEach<Arg> for Cons<Arg, Tail>
where
	Tail: ForEach<Arg>,
{
    fn for_each<F>(&self, mut f: F)
    where
        F: FnMut(&Arg),
    {
        f(&self.0);
        self.1.for_each(f);
    }
}

const fn n_digits(mut n: usize) -> usize {
    if n == 0 {
        return 1
    }
    let mut ret = 0;
    while n > 0 {
        n /= 10;
        ret += 1;
    }
    ret
}

fn main() {
    <List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST
        .for_each(|s| println!("{}", s.as_str()));
}