Integer addition in the TypeScript type system

type-system-integer-addition.d.ts

// An implementation of arithmetic (well, of integer addition) in the TypeScript type system
// base-10 adaptation of this: https://blog.joshuakgoldberg.com/binary-arithmetic/
// note: this whole program is opposite endianness from the original article because Arabic numbers are RTL

type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

/**
 * Our integer type, a tuple of digits with length 1-6
 * Note: for a simpler version with static-length Int, see the second revision of this gist
 */
type Int =
| [Digit]
| [Digit, Digit]
| [Digit, Digit, Digit]
| [Digit, Digit, Digit, Digit]
| [Digit, Digit, Digit, Digit, Digit]
| [Digit, Digit, Digit, Digit, Digit, Digit]

/**
 * Represents the sum of 2-3 single digits (only used internally)
 */
type DigitPair = [Digit /* tens/carry */, Digit /* ones/sum */];

/**
 * Add 2 single digits together, which is guaranteed to fit into 2 digits (9+9 < 99)
 * Generated using https://github.com/mrjacobbloom/my_first_calculator.d.ts
 * @returns {DigitPair} // yes I'm aware this is an abuse of the JSDoc returns tag
 */
type Add2Digits<A extends Digit, B extends Digit> = 
  A extends 0 ? B extends 0 ? [0, 0] : B extends 1 ? [0, 1] : B extends 2 ? [0, 2] : B extends 3 ? [0, 3] : B extends 4 ? [0, 4] : B extends 5 ? [0, 5] : B extends 6 ? [0, 6] : B extends 7 ? [0, 7] : B extends 8 ? [0, 8] : B extends 9 ? [0, 9] : never :
  A extends 1 ? B extends 0 ? [0, 1] : B extends 1 ? [0, 2] : B extends 2 ? [0, 3] : B extends 3 ? [0, 4] : B extends 4 ? [0, 5] : B extends 5 ? [0, 6] : B extends 6 ? [0, 7] : B extends 7 ? [0, 8] : B extends 8 ? [0, 9] : B extends 9 ? [1, 0] : never :
  A extends 2 ? B extends 0 ? [0, 2] : B extends 1 ? [0, 3] : B extends 2 ? [0, 4] : B extends 3 ? [0, 5] : B extends 4 ? [0, 6] : B extends 5 ? [0, 7] : B extends 6 ? [0, 8] : B extends 7 ? [0, 9] : B extends 8 ? [1, 0] : B extends 9 ? [1, 1] : never :
  A extends 3 ? B extends 0 ? [0, 3] : B extends 1 ? [0, 4] : B extends 2 ? [0, 5] : B extends 3 ? [0, 6] : B extends 4 ? [0, 7] : B extends 5 ? [0, 8] : B extends 6 ? [0, 9] : B extends 7 ? [1, 0] : B extends 8 ? [1, 1] : B extends 9 ? [1, 2] : never :
  A extends 4 ? B extends 0 ? [0, 4] : B extends 1 ? [0, 5] : B extends 2 ? [0, 6] : B extends 3 ? [0, 7] : B extends 4 ? [0, 8] : B extends 5 ? [0, 9] : B extends 6 ? [1, 0] : B extends 7 ? [1, 1] : B extends 8 ? [1, 2] : B extends 9 ? [1, 3] : never :
  A extends 5 ? B extends 0 ? [0, 5] : B extends 1 ? [0, 6] : B extends 2 ? [0, 7] : B extends 3 ? [0, 8] : B extends 4 ? [0, 9] : B extends 5 ? [1, 0] : B extends 6 ? [1, 1] : B extends 7 ? [1, 2] : B extends 8 ? [1, 3] : B extends 9 ? [1, 4] : never :
  A extends 6 ? B extends 0 ? [0, 6] : B extends 1 ? [0, 7] : B extends 2 ? [0, 8] : B extends 3 ? [0, 9] : B extends 4 ? [1, 0] : B extends 5 ? [1, 1] : B extends 6 ? [1, 2] : B extends 7 ? [1, 3] : B extends 8 ? [1, 4] : B extends 9 ? [1, 5] : never :
  A extends 7 ? B extends 0 ? [0, 7] : B extends 1 ? [0, 8] : B extends 2 ? [0, 9] : B extends 3 ? [1, 0] : B extends 4 ? [1, 1] : B extends 5 ? [1, 2] : B extends 6 ? [1, 3] : B extends 7 ? [1, 4] : B extends 8 ? [1, 5] : B extends 9 ? [1, 6] : never :
  A extends 8 ? B extends 0 ? [0, 8] : B extends 1 ? [0, 9] : B extends 2 ? [1, 0] : B extends 3 ? [1, 1] : B extends 4 ? [1, 2] : B extends 5 ? [1, 3] : B extends 6 ? [1, 4] : B extends 7 ? [1, 5] : B extends 8 ? [1, 6] : B extends 9 ? [1, 7] : never :
  A extends 9 ? B extends 0 ? [0, 9] : B extends 1 ? [1, 0] : B extends 2 ? [1, 1] : B extends 3 ? [1, 2] : B extends 4 ? [1, 3] : B extends 5 ? [1, 4] : B extends 6 ? [1, 5] : B extends 7 ? [1, 6] : B extends 8 ? [1, 7] : B extends 9 ? [1, 8] : never :
  never;

/**
 * Add 3 single digits together, which is guaranteed to fit into 2 digits (9+9+9 < 99)
 * @returns {DigitPair}
 */
type Add3Digits<
  A extends Digit,
  B extends Digit,
  C extends Digit,
  AB extends DigitPair = Add2Digits<A, B>,
  ABC extends DigitPair = Add2Digits<AB[1], C>
  > = [Add2Digits<AB[0], ABC[0]>[1], ABC[1]];

/**
 * Get the nth-from-last digit from a number, since I'm so attached to this RTL thing. Defaults to 0 if the tuple is shorter than the requested length
 * @reutrns {Digit}
 */
type NthFromLast<
    A extends Int,
    I extends number
> = A extends { length: 1 } ? I extends 0 ? A[0] : 0 :
    A extends { length: 2 } ? I extends 0 ? A[1] : I extends 1 ? A[0] : 0 :
    A extends { length: 3 } ? I extends 0 ? A[2] : I extends 1 ? A[1] : I extends 2 ? A[0] : 0 :
    A extends { length: 4 } ? I extends 0 ? A[3] : I extends 1 ? A[2] : I extends 2 ? A[1] : I extends 3 ? A[0] : 0 :
    A extends { length: 5 } ? I extends 0 ? A[4] : I extends 1 ? A[3] : I extends 2 ? A[2] : I extends 3 ? A[1] : I extends 4 ? A[0] : 0 :
    A extends { length: 6 } ? I extends 0 ? A[5] : I extends 1 ? A[4] : I extends 2 ? A[3] : I extends 3 ? A[2] : I extends 4 ? A[1] : I extends 5 ? A[0] : 0 :
    never;

/**
 * Remove left-pad ;)
 * @returns {Int}
 */
type Unpad<A extends Int> =
    A[0] extends 0 ?
        A[1] extends 0 ?
            A[2] extends 0 ?
                A[3] extends 0 ?
                    A[4] extends 0 ?
                        [A[5]]
                    : [A[4], A[5]]
                : [A[3], A[4], A[5]]
            : [A[2], A[3], A[4], A[5]]
        : [A[1], A[2], A[3], A[4], A[5]]
    : A;

// rest parameters don't work in tuples for some reason: https://github.com/microsoft/TypeScript/issues/26113
// type GetFirstDigit<A extends [Int]> = A extends [infer First, ...infer Rest] ? [First, Rest] : never;
// type Unpad2<
//     A extends Int,
//     B extends [Digit, Int] = GetFirstDigit<A>
// > = A extends [0] ? A : B[0] extends 0 ? Unpad2<B[1]> : A;

type Add<
  A extends Int,
  B extends Int,
  // Start at the right and move left, 'cause Arabic numbers are RTL
  At5 extends DigitPair = Add2Digits<NthFromLast<A, 0>, NthFromLast<B, 0>>,
  At4 extends DigitPair = Add3Digits<NthFromLast<A, 1>, NthFromLast<B, 1>, At5[0]>,
  At3 extends DigitPair = Add3Digits<NthFromLast<A, 2>, NthFromLast<B, 2>, At4[0]>,
  At2 extends DigitPair = Add3Digits<NthFromLast<A, 3>, NthFromLast<B, 3>, At3[0]>,
  At1 extends DigitPair = Add3Digits<NthFromLast<A, 4>, NthFromLast<B, 4>, At2[0]>,
  At0 extends DigitPair = Add3Digits<NthFromLast<A, 5>, NthFromLast<B, 5>, At1[0]>,
  > = Unpad<[At0[1], At1[1], At2[1], At3[1], At4[1], At5[1]]>;

/**
 * Assert utility to verify it's working
 * @returns {boolean}
 */
type AssertEquals<Actual, Expected> = Actual extends Expected ? Expected extends Actual ? true : false : false;

// the moment of truth:
type result = AssertEquals<Add<[1, 4, 5, 4], [6, 2]>,  [1, 5, 1, 6]>; // true, it works!