type_stuff.rs

struct NegOne;
struct Zero;

struct Bit0<N>(PhantomData<N>);
struct Bit1<N>(PhantomData<N>);

type One = Bit1<Zero>;
type NegTwo = Bit1<NegOne>;

trait Integer {
    const VALUE: i128;
    type Add1: Integer; // Calculate (N + 1) as a canonical integer
    type Sub1: Integer; // Calculate (N - 1) as a canonical integer
    type Neg: Integer; // Calculate (-N) as a canonical integer
    type Shift: Integer; // Calculate (N << 1) as a canonical integer
}

impl Integer for Zero {
    const VALUE: i128 = 0;
    type Add1 = One;
    type Sub1 = NegOne;
    type Neg = Zero;
    type Shift = Zero;
}

impl Integer for NegOne {
    const VALUE: i128 = -1;
    type Add1 = Zero;
    type Sub1 = NegTwo;
    type Neg = One;
    type Shift = NegTwo;
}

// We require N to be NonZero and not just an Integer in order to only permit canonical integers
impl<N: NonZero> Integer for Bit0<N> {
    const VALUE: i128 = N::VALUE << 1;
    type Add1 = Bit1<N>;
    type Sub1 = Bit1<<N as Integer>::Sub1>;
    type Neg = <<N as Integer>::Neg as Integer>::Shift;
    type Shift = Bit0<Bit0<N>>;
}

impl<N: Integer> Integer for Bit1<N> {
    const VALUE: i128 = (N::VALUE << 1) | 1;
    type Add1 = <<N as Integer>::Add1 as Integer>::Shift;
    type Sub1 = <N as Integer>::Shift;
    type Neg = Bit1<<<N as Integer>::Neg as Integer>::Sub1>;
    type Shift = Bit0<Bit1<N>>;
}

trait NonZero: Integer {}
impl NonZero for NegOne {}
impl<N: NonZero> NonZero for Bit0<N> {}
impl<N: Integer> NonZero for Bit1<N> {}

trait Add<Other: Integer>: Integer {
    type Result: Integer;
}

impl<N: Integer> Add<N> for Zero {
    type Result = N;
}

impl<N: Integer> Add<N> for NegOne {
    type Result = <N as Integer>::Sub1;
}

impl<N: NonZero> Add<Zero> for Bit0<N> {
    type Result = Bit0<N>;
}

impl<N: NonZero> Add<NegOne> for Bit0<N> {
    type Result = Bit1<<N as Integer>::Sub1>;
}

impl<N: NonZero, M: NonZero> Add<Bit0<M>> for Bit0<N>
where
    N: Add<M>,
{
    type Result = <<N as Add<M>>::Result as Integer>::Shift;
}

impl<N: NonZero, M: Integer> Add<Bit1<M>> for Bit0<N>
where
    N: Add<M>,
{
    type Result = Bit1<<N as Add<M>>::Result>;
}

impl<N: Integer> Add<Zero> for Bit1<N> {
    type Result = Bit1<N>;
}

impl<N: Integer> Add<NegOne> for Bit1<N> {
    type Result = <N as Integer>::Shift;
}

impl<N: Integer, M: NonZero> Add<Bit0<M>> for Bit1<N>
where
    N: Add<M>,
{
    type Result = Bit1<<N as Add<M>>::Result>;
}

impl<N: Integer, M: Integer> Add<Bit1<M>> for Bit1<N>
where
    N: Add<M>,
{
    type Result = <<<N as Add<M>>::Result as Integer>::Add1 as Integer>::Shift;
}