bad type-level TypeScript ideas

generate-tables.ts

import * as fs from 'fs';
import * as ts from 'typescript';

function flat<T>(arr: T[][]): T[] {
  return arr.reduce((acc, val) => acc.concat(val), []);
}

const noDecorators = undefined;
const noImportClause = undefined;
const noInitializer = undefined;
const noModifiers = undefined;
const noName = undefined;
const noPropertyName = undefined;
const noQuestionToken = undefined;
const noType = undefined;
const noTypeArguments = undefined;
const noTypeParameters = undefined;

function createModifiers(flags: ts.ModifierFlags[]): ts.Modifier[] {
  return ts.createModifiersFromModifierFlags(
    flags.reduce((acc, val) => acc | val, 0)
  );
}

function createLiteral<T>(value: T):
  T extends boolean ? ts.BooleanLiteral :
  T extends number ? ts.NumericLiteral :
  T extends string ? ts.StringLiteral :
  never
{
  switch (typeof value) {
    case "boolean": {
      return ts.createLiteral(value) as ts.BooleanLiteral as unknown as any;
    }
    case "number": {
      return ts.createNumericLiteral(value + '') as ts.NumericLiteral as unknown as any;
    }
    case "string": {
      const literal = ts.createStringLiteral(value);
      (literal as any).singleQuote = true;
      return literal as ts.StringLiteral as unknown as any;
    }
    default:
      throw "bad literal type"
  }
}
function createTypeLiteral<T>(value: T): ts.LiteralTypeNode {
  return ts.createLiteralTypeNode(createLiteral(value));
}

function createPropertySignature<T extends number | string>(
  name: T, type: ts.TypeNode | undefined, initializer: ts.Expression | undefined
): ts.PropertySignature {
  const literal = createLiteral(name);
  const propName: ts.PropertyName = typeof name === "number" ?
    ts.createComputedPropertyName(literal) :
    literal;
  return ts.createPropertySignature(noModifiers, propName, noQuestionToken, type, initializer);
}

function returnEveryN<T>(n: number, f: (i: number) => T): () => T | undefined {
  let i = 0;
  return function () {
    return ++i % n === 0 ? f(i) : undefined;
  }
}

function withComment<T extends ts.Node>(node: T, text: string | undefined): T {
  return text === undefined ? node :
    ts.addSyntheticTrailingComment(
      node, ts.SyntaxKind.SingleLineCommentTrivia, text, true
    );
}
function withCommentFun<T extends ts.Node>(
  node: T, f: ((n: T) => string | undefined) | undefined
): T {
  return f === undefined ? node : withComment(node, f(node));
}

function createTableType(
  properties: {n: string | number, t: ts.TypeNode, v?: ts.Expression}[],
  multiline: boolean = false,
  commentForPropSig?: ((ps: ts.PropertySignature) => string | undefined)
): ts.TypeNode {
  const typeNode = ts.createTypeLiteralNode(
    properties.map(
      ({n, t, v}) =>
        withCommentFun(createPropertySignature(n, t, v), commentForPropSig)
    )
  );
  if (!multiline) {
    ts.setEmitFlags(typeNode, ts.EmitFlags.SingleLine);
  }
  return typeNode;
}
function createTableDeclaration(
  name: ts.Identifier,
  parameters: ts.Identifier[],
  type: ts.TypeNode
): ts.TypeAliasDeclaration {
  return ts.createTypeAliasDeclaration(
    noDecorators,
    createModifiers([ts.ModifierFlags.Export]),
    name,
    parameters.length === 0 ?
      undefined :
      parameters.map((name) => ts.createTypeParameterDeclaration(name)),
    type
  );
}

function generateTableFile(sourceFile: ts.SourceFile): ts.SourceFile {
  const tyIntMax = 16;
  const tyInt = Array.from({length: tyIntMax + 1}, (_, i) => i);

  const imports: ts.Statement[] = [];

  const breakEvery = 4;

  const tyIntMaxDecl = ts.createTypeAliasDeclaration(
    noDecorators,
    createModifiers([ts.ModifierFlags.Export]),
    ts.createIdentifier('TyIntMax'),
    noTypeParameters,
    createTypeLiteral(tyIntMax)
  );

  const tyIntUnionBreaker = returnEveryN(breakEvery, () => '');
  const tyIntUnionType = ts.createUnionTypeNode(
    tyInt.map(
      (n) => withCommentFun(createTypeLiteral(n), tyIntUnionBreaker)
    )
  );
  ts.setEmitFlags(tyIntUnionType, ts.EmitFlags.SingleLine);
  const tyIntDecl = ts.createTypeAliasDeclaration(
    noDecorators,
    createModifiers([ts.ModifierFlags.Export]),
    ts.createIdentifier('TyInt'),
    noTypeParameters,
    tyIntUnionType
  );

  const tyIntTableDecl = createTableDeclaration(
    ts.createIdentifier('TyIntTable'),
    [],
    createTableType(
      tyInt.map((n) => ({n, t: createTypeLiteral(n)})),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const tyIntStringUnionBreaker = returnEveryN(breakEvery, () => '');
  const tyIntStringUnionType = ts.createUnionTypeNode(
    tyInt.map(
      (n) => withCommentFun(createTypeLiteral(n + ''), tyIntStringUnionBreaker)
    )
  );
  ts.setEmitFlags(tyIntStringUnionType, ts.EmitFlags.SingleLine);
  const tyIntStringDecl = ts.createTypeAliasDeclaration(
    noDecorators,
    createModifiers([ts.ModifierFlags.Export]),
    ts.createIdentifier('TyIntString'),
    noTypeParameters,
    tyIntStringUnionType
  );

  const tyIntStringTableDecl = createTableDeclaration(
    ts.createIdentifier('TyIntStringTable'),
    [],
    createTableType(
      tyInt.map((n) => ({n: n + '', t: createTypeLiteral(n)})),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const tyIntToStringTableDecl = createTableDeclaration(
    ts.createIdentifier('TyIntToStringTable'),
    [],
    createTableType(
      tyInt.map((n) => ({n, t: createTypeLiteral(n + '')})),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const stringToTyIntTableDecl = createTableDeclaration(
    ts.createIdentifier('StringToTyIntTable'),
    [],
    createTableType(
      tyInt.map((n) => ({n: n + '', t: createTypeLiteral(n)})),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const incTableOverflowIdent = ts.createIdentifier('Overflow');
  const incTableOverflow = ts.createTypeReferenceNode(incTableOverflowIdent, noTypeArguments);
  const incTableDecl = createTableDeclaration(
    ts.createIdentifier('IncTable'),
    [incTableOverflowIdent],
    createTableType(
      tyInt.map(
        (n) => ({n, t: n === tyIntMax ? incTableOverflow : createTypeLiteral(n + 1)})
      ),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const decTableUnderflowIdent = ts.createIdentifier('Underflow');
  const decTableUnderflow = ts.createTypeReferenceNode(decTableUnderflowIdent, noTypeArguments);
  const decTableDecl = createTableDeclaration(
    ts.createIdentifier('DecTable'),
    [decTableUnderflowIdent],
    createTableType(
      tyInt.map(
        (n) => ({n, t: n === 0 ? decTableUnderflow : createTypeLiteral(n - 1)})
      ),
      false, returnEveryN(breakEvery, () => '')
    )
  );

  const addTableOverflowIdent = ts.createIdentifier('O');
  const addTableOverflow = ts.createTypeReferenceNode(addTableOverflowIdent, noTypeArguments);
  const addTableDecl = createTableDeclaration(
    ts.createIdentifier('AddTable'),
    [addTableOverflowIdent],
    createTableType(
      tyInt.map(
        (n) => ({
          n,
          t: createTableType(
            tyInt.map((m) => ({
              n: m,
              t: n + m > tyIntMax ? addTableOverflow : createTypeLiteral(n + m)
            })),
            false, returnEveryN(breakEvery, () => '')
          )
        })
      ),
      true,
    )
  );

  const subTableUnderflowIdent = ts.createIdentifier('U');
  const subTableUnderflow = ts.createTypeReferenceNode(subTableUnderflowIdent, noTypeArguments);
  const subTableDecl = createTableDeclaration(
    ts.createIdentifier('SubTable'),
    [subTableUnderflowIdent],
    createTableType(
      tyInt.map(
        (n) => ({
          n,
          t: createTableType(
            tyInt.map((m) => ({
              n: m,
              t: n - m < 0 ? subTableUnderflow : createTypeLiteral(n - m)
            })),
            false, returnEveryN(breakEvery, () => '')
          )
        })
      ),
      true,
    )
  );

  const mulTableOverflowIdent = ts.createIdentifier('O');
  const mulTableOverflow = ts.createTypeReferenceNode(mulTableOverflowIdent, noTypeArguments);
  const mulTableDecl = createTableDeclaration(
    ts.createIdentifier('MulTable'),
    [mulTableOverflowIdent],
    createTableType(
      tyInt.map(
        (n) => ({
          n,
          t: createTableType(
            tyInt.map((m) => ({
              n: m,
              t: n * m > tyIntMax ? mulTableOverflow : createTypeLiteral(n * m)
            })),
            false, returnEveryN(breakEvery, () => '')
          )
        })
      ),
      true,
    )
  );

  const divModTableUndefIdent = ts.createIdentifier('Undef');
  const divModTableUndef = ts.createTypeReferenceNode(divModTableUndefIdent, noTypeArguments);
  const divModTableDecl = createTableDeclaration(
    ts.createIdentifier('DivModTable'),
    [divModTableUndefIdent],
    createTableType(
      tyInt.map(
        (n) => ({
          n,
          t: createTableType(
            tyInt.map((m) => ({
              n: m,
              t: m === 0 ? createTableType([
                {n: 'div', t: divModTableUndef},
                {n: 'mod', t: divModTableUndef},
              ]) : createTableType([
                {n: 'div', t: createTypeLiteral(Math.trunc(n / m))},
                {n: 'mod', t: createTypeLiteral(n % m)},
              ])
            })),
            false, returnEveryN(Math.trunc(breakEvery / 2), () => '')
          )
        })
      ),
      true,
    )
  );

  const tableDecls = [
    tyIntTableDecl,
    tyIntStringTableDecl,
    tyIntToStringTableDecl,
    stringToTyIntTableDecl,
    incTableDecl,
    decTableDecl,
    addTableDecl,
    subTableDecl,
    mulTableDecl,
    divModTableDecl,
  ];

  const statements: ts.Statement[] = flat([
    imports,
    [tyIntMaxDecl, tyIntDecl, tyIntStringDecl],
    tableDecls,
  ]);

  return ts.updateSourceFileNode(sourceFile, statements);
}

const tableFile = ts.createSourceFile(
  /*fileName*/ "util-tables.ts",
  /*sourceText*/ "",
  /*languageVersion*/ ts.ScriptTarget.Latest,
  /*setParentNodes?*/ false,
  /*scriptKind*/ ts.ScriptKind.TS,
);

function writeSourceFileSync(sourceFile: ts.SourceFile) {
  const printer = ts.createPrinter();
  return fs.writeFileSync(sourceFile.fileName, printer.printFile(sourceFile));
}

writeSourceFileSync(generateTableFile(tableFile));

util.ts

import * as tables from './util-tables';
import {
  NoInfer,
  Omit, OmitStrict,
  Overwrite,
  Param0, Param1, Param2, Param3, ParamTypes,
  Pick2, Pick3, Pick4,
  Public,
  Purify,
} from 'type-zoo';

export type unreachable = never;
export type tyVarDef = unreachable;

declare const privateWrap: unique symbol;
type PrivateWrap<T = unknown> = {[privateWrap]: T};

export type IntBoolTable = {[0]: false; [1]: true};

export type EqualDistrib<X, Y> =
  X extends Y ? Y extends X ? true : false : false;
export type Equal<X, Y> =
  [X] extends [Y] ? [Y] extends [X] ? true : false : false;
const test_Equal_00: Equal<{a: 5}, {a: 5}> = true;
const test_Equal_01: Equal<{a: 5}, {a: 4}> = false;
const test_Equal_02: Equal<{a: 5, b: 7}, {a: 5}> = false;
const test_Equal_03: Equal<{}, {a: 5}> = false;
const test_Equal_04: Equal<0 | 1, 1 | 0> = true;
const test_Equal_05: Equal<0, 1 | 0> = false;
const test_Equal_06: Equal<0 | 1, 1> = false;
const test_Equal_07: Equal<never, never> = true;
const test_Equal_08: Equal<unknown, unknown> = true;
const test_Equal_09: Equal<unknown, never> = false;

// everything except false is truthy
export type IfDistrib<P, X, Y> = P extends false ? Y : X;
export type IfExact<P, X, Y> = [P] extends [false] ? [false] extends [P] ? Y : X : X;
export type If<P, X, Y> = IfDistrib<P, X, Y>;
// export type If<P, X, Y> = IfExact<P, X, Y>;
const test_If_00: Equal<If<false, 1, 'a'>, 'a'> = true;
const test_If_01: Equal<If<true, 1, 'a'>, 1> = true;
const test_If_02: Equal<If<'yo', 1, []>, 1> = true;
const test_If_03: Equal<IfDistrib<never, 1, 'a'>, never> = true;
const test_If_04: Equal<IfExact<never, 1, 'a'>, 1> = true;

export type IsTrue<P> = If<P, true, false>;
export type IsFalse<P> = If<P, false, true>;

export type Not<P> = If<P, false, true>;
const test_Not_00: Equal<Not<false>, true> = true;
const test_Not_01: Equal<Not<true>, false> = true;
export type And<P, Q> = If<P, Q, P>;
const test_And_00: Equal<And<false, false>, false> = true;
const test_And_01: Equal<And<false, true>, false> = true;
const test_And_02: Equal<And<true, false>, false> = true;
const test_And_03: Equal<And<true, true>, true> = true;
const test_And_04: Equal<And<true, 'yo'>, 'yo'> = true;
const test_And_05: Equal<And<true, unknown>, unknown> = true;
const test_And_06: Equal<And<true, never>, never> = true;
const test_And_07: Equal<And<1, 'yo'>, 'yo'> = true;
const test_And_08: Equal<And<1, unknown>, unknown> = true;
const test_And_09: Equal<And<1, never>, never> = true;
const test_And_10: Equal<And<false, 'yo'>, false> = true;
const test_And_11: Equal<And<false, unknown>, false> = true;
const test_And_12: Equal<And<false, never>, false> = true;
export type Or<P, Q> = If<P, P, Q>;
const test_Or_00: Equal<Or<false, false>, false> = true;
const test_Or_01: Equal<Or<false, true>, true> = true;
const test_Or_02: Equal<Or<true, false>, true> = true;
const test_Or_03: Equal<Or<true, true>, true> = true;
const test_Or_04: Equal<Or<true, 'yo'>, true> = true;
const test_Or_05: Equal<Or<true, unknown>, true> = true;
const test_Or_06: Equal<Or<true, never>, true> = true;
const test_Or_07: Equal<Or<1, 'yo'>, 1> = true;
const test_Or_08: Equal<Or<1, unknown>, 1> = true;
const test_Or_09: Equal<Or<1, never>, 1> = true;
const test_Or_10: Equal<Or<false, 'yo'>, 'yo'> = true;
const test_Or_11: Equal<Or<false, unknown>, unknown> = true;
const test_Or_12: Equal<Or<false, never>, never> = true;
export type Xor<P, Q> = If<P, IsFalse<Q>, IsTrue<Q>>;
const test_Xor_00: Equal<Xor<false, false>, false> = true;
const test_Xor_01: Equal<Xor<false, true>, true> = true;
const test_Xor_02: Equal<Xor<true, false>, true> = true;
const test_Xor_03: Equal<Xor<true, true>, false> = true;
const test_Xor_04: Equal<Xor<true, 'yo'>, false> = true;
const test_Xor_05: Equal<Xor<true, unknown>, false> = true;
const test_Xor_06: Equal<Xor<1, 'yo'>, false> = true;
const test_Xor_07: Equal<Xor<1, unknown>, false> = true;
const test_Xor_08: Equal<Xor<false, 'yo'>, true> = true;
const test_Xor_09: Equal<Xor<false, unknown>, true> = true;

export type TyIntMax = tables.TyIntMax;
export type TyInt = tables.TyInt;
export type TyIntString = tables.TyIntString;

export type TyIntTable = tables.TyIntTable;
export type TyIntStringTable = tables.TyIntStringTable;

export type TyIntToStringTable = tables.TyIntToStringTable;
export type TyIntToString<N extends TyInt> = TyIntToStringTable[N];
export type StringToTyIntTable = tables.StringToTyIntTable;
export type StringToTyInt<N extends TyIntString> = StringToTyIntTable[N];

export type IncTable<Overflow> = tables.IncTable<Overflow>;
export type Inc<N extends TyInt, Overflow = never> =
  IncTable<Overflow>[N];
const test_Inc_00: Equal<Inc<0>, 1> = true;
const test_Inc_01: Equal<Inc<0, never>, 1> = true;
const test_Inc_02: Equal<Inc<10>, 11> = true;
const test_Inc_03: Equal<Inc<15>, 16> = true;
const test_Inc_04: Equal<Inc<15>, 16> = true;
const test_Inc_05: Equal<Inc<16, 'woah'>, 'woah'> = true;
const test_Inc_06: Equal<Inc<16, never>, never> = true;

export type DecTable<Underflow> = tables.DecTable<Underflow>;
export type Dec<N extends TyInt, Underflow = never> = DecTable<Underflow>[N];
const test_Dec_00: Equal<Dec<0, 'woah'>, 'woah'> = true;
const test_Dec_01: Equal<Dec<0, never>, never> = true;
const test_Dec_02: Equal<Dec<1>, 0> = true;
const test_Dec_03: Equal<Dec<10>, 9> = true;
const test_Dec_04: Equal<Dec<15>, 14> = true;
const test_Dec_05: Equal<Dec<16>, 15> = true;
const test_Dec_06: Equal<Dec<16, never>, 15> = true;

export type LoopUntil<P> = If<P, 'ret', 'loop'>;
export type LoopUntilZero<I extends TyInt> = LoopUntil<Equal<I, 0>>;

export type AddTable<Overflow> = tables.AddTable<Overflow>;
export type AddRec<N extends TyInt, M extends TyInt, Overflow = never> = {
  'loop':
    Inc<N, PrivateWrap<Overflow>> extends infer N ?
    N extends PrivateWrap<infer Overflow> ? Overflow : N extends TyInt ?
    Dec<M> extends infer M ? M extends TyInt ?
    AddRec<N, M, Overflow>
    : unreachable : tyVarDef
    : unreachable : tyVarDef;
  'ret': N;
}[LoopUntilZero<M>];
export type Add<N extends TyInt, M extends TyInt, Overflow = never> =
  AddTable<Overflow>[N][M];
const test_Add_00: Equal<Add<0, 0>, 0> = true;
const test_Add_01: Equal<Add<0, 1>, 1> = true;
const test_Add_02: Equal<Add<1, 0>, 1> = true;
const test_Add_03: Equal<Add<1, 1>, 2> = true;
const test_Add_04: Equal<Add<2, 3>, 5> = true;
const test_Add_05: Equal<Add<8, 8>, 16> = true;
const test_Add_06: Equal<Add<1, 15>, 16> = true;
const test_Add_07: Equal<Add<15, 1>, 16> = true;
const test_Add_08: Equal<Add<8, 9, 'woah'>, 'woah'> = true;
const test_Add_09: Equal<Add<9, 8, 'woah'>, 'woah'> = true;
const test_Add_10: Equal<Add<8, 10, 'woah'>, 'woah'> = true;
const test_Add_11: Equal<Add<10, 8, 'woah'>, 'woah'> = true;
const test_Add_12: Equal<Add<1, 16, 'woah'>, 'woah'> = true;
const test_Add_13: Equal<Add<16, 1, 'woah'>, 'woah'> = true;
const test_Add_14: Equal<Add<2, 16, 'woah'>, 'woah'> = true;
const test_Add_15: Equal<Add<16, 2, 'woah'>, 'woah'> = true;
const test_Add_16: Equal<Add<16, 16, 'woah'>, 'woah'> = true;

export type SubTable<Underflow> = tables.SubTable<Underflow>;
export type SubRec<N extends TyInt, M extends TyInt, Underflow = never> = {
  'loop':
    Dec<N, PrivateWrap<Underflow>> extends infer N ?
    N extends PrivateWrap<infer Underflow> ? Underflow : N extends TyInt ?
    Dec<M> extends infer M ? M extends TyInt ?
    SubRec<N, M, Underflow>
    : unreachable : tyVarDef
    : unreachable : tyVarDef;
  'ret': N;
}[LoopUntilZero<M>];
export type Sub<N extends TyInt, M extends TyInt, Underflow = never> =
  SubTable<Underflow>[N][M];
//   SubTable<Underflow> extends infer Table ?
//     N extends keyof Table ? M extends keyof Table[N] ? Table[N][M]
//   : SubRec<N, M, Underflow> : SubRec<N, M, Underflow> : tyVarDef;

const test_Sub_00: Equal<Sub<0, 0>, 0> = true;
const test_Sub_01: Equal<Sub<1, 0>, 1> = true;
const test_Sub_02: Equal<Sub<1, 1>, 0> = true;
const test_Sub_03: Equal<Sub<2, 1>, 1> = true;
const test_Sub_04: Equal<Sub<3, 1>, 2> = true;
const test_Sub_05: Equal<Sub<8, 0>, 8> = true;
const test_Sub_06: Equal<Sub<8, 1>, 7> = true;
const test_Sub_07: Equal<Sub<8, 8>, 0> = true;
const test_Sub_08: Equal<Sub<16, 0>, 16> = true;
const test_Sub_09: Equal<Sub<16, 1>, 15> = true;
const test_Sub_10: Equal<Sub<16, 16>, 0> = true;
const test_Sub_11: Equal<Sub<1, 2, 'woah'>, 'woah'> = true;
const test_Sub_12: Equal<Sub<1, 3, 'woah'>, 'woah'> = true;
const test_Sub_13: Equal<Sub<8, 9, 'woah'>, 'woah'> = true;
const test_Sub_14: Equal<Sub<8, 10, 'woah'>, 'woah'> = true;
const test_Sub_15: Equal<Sub<1, 16, 'woah'>, 'woah'> = true;

export type LtEq<N extends TyInt, M extends TyInt> =
  [Sub<N, M, 0>] extends [0] ? true : false;
export type GtEq<N extends TyInt, M extends TyInt> = LtEq<M, N>;
export type Lt<N extends TyInt, M extends TyInt> =
  [Sub<N, M, true>] extends [true] ? true : false;
export type Gt<N extends TyInt, M extends TyInt> = Lt<M, N>;

const test_Cmp_00: Equal<Lt<0, 0>, false> = true;
const test_Cmp_01: Equal<LtEq<0, 0>, true> = true;
const test_Cmp_02: Equal<Lt<8, 8>, false> = true;
const test_Cmp_03: Equal<LtEq<8, 8>, true> = true;
const test_Cmp_04: Equal<Lt<16, 16>, false> = true;
const test_Cmp_05: Equal<LtEq<16, 16>, true> = true;
const test_Cmp_06: Equal<Lt<0, 1>, true> = true;
const test_Cmp_07: Equal<LtEq<0, 1>, true> = true;
const test_Cmp_08: Equal<Lt<1, 3>, true> = true;
const test_Cmp_09: Equal<LtEq<1, 3>, true> = true;
const test_Cmp_10: Equal<Lt<0, 8>, true> = true;
const test_Cmp_11: Equal<LtEq<0, 8>, true> = true;
const test_Cmp_12: Equal<Lt<0, 16>, true> = true;
const test_Cmp_13: Equal<LtEq<0, 16>, true> = true;
const test_Cmp_14: Equal<Lt<2, 1>, false> = true;
const test_Cmp_15: Equal<LtEq<2, 1>, false> = true;
const test_Cmp_16: Equal<Lt<2, 8>, true> = true;
const test_Cmp_17: Equal<LtEq<2, 8>, true> = true;
const test_Cmp_18: Equal<Lt<11, 8>, false> = true;
const test_Cmp_19: Equal<LtEq<11, 8>, false> = true;
const test_Cmp_20: Equal<Lt<11, 16>, true> = true;
const test_Cmp_21: Equal<LtEq<11, 16>, true> = true;

export type Max<N extends TyInt, M extends TyInt> =
  If<Gt<N, M>, N, M>;
export type Min<N extends TyInt, M extends TyInt> =
  If<Lt<N, M>, N, M>;

const test_Max_00: Equal<Max<0, 0>, 0> = true;
const test_Max_01: Equal<Max<0, 1>, 1> = true;
const test_Max_02: Equal<Max<1, 0>, 1> = true;
const test_Max_03: Equal<Max<0, 3>, 3> = true;
const test_Max_04: Equal<Max<3, 0>, 3> = true;
const test_Max_05: Equal<Max<2, 5>, 5> = true;
const test_Max_06: Equal<Max<5, 2>, 5> = true;
const test_Max_07: Equal<Max<15, 0>, 15> = true;
const test_Max_08: Equal<Max<0, 15>, 15> = true;
const test_Max_09: Equal<Max<15, 1>, 15> = true;
const test_Max_10: Equal<Max<1, 15>, 15> = true;
const test_Max_11: Equal<Max<16, 0>, 16> = true;
const test_Max_12: Equal<Max<0, 16>, 16> = true;

export type MulTable<Overflow> = tables.MulTable<Overflow>;
export type MulRec<N extends TyInt, M extends TyInt, Overflow = never,
Acc extends TyInt = 0> = {
  'loop':
    Add<Acc, N, PrivateWrap<Overflow>> extends infer Acc ?
    Acc extends PrivateWrap<infer E> ? E : Acc extends TyInt ?
    Dec<M> extends infer M ? M extends TyInt ?
    MulRec<N, M, Overflow, Acc>
    : unreachable : tyVarDef
    : unreachable : tyVarDef;
  'ret': Acc;
}[LoopUntilZero<M>];
export type Mul<N extends TyInt, M extends TyInt, Overflow = never> =
  MulTable<Overflow>[N][M];
export type DivModTable<Undef> = tables.DivModTable<Undef>;
export type DivModRec<N extends TyInt, M extends TyInt,
Acc extends TyInt = 0> = {
  'loop':
    Add<Acc, M> extends infer Acc ? Acc extends TyInt ?
    Sub<M, N> extends infer N ? N extends TyInt ?
    DivModRec<N, M, Acc>
    : unreachable : tyVarDef
    : unreachable : tyVarDef;
  'ret': {
    'div': Acc;
    'mod': Sub<M, Acc> extends infer X ? X extends TyInt ?
      X : unreachable : tyVarDef;
  };
}[LoopUntil<Lt<N, M>>];
export type DivMod<N extends TyInt, M extends TyInt, Undef = never> =
  DivModTable<Undef>[N][M];
export type Div<N extends TyInt, M extends TyInt, Undef = never> =
  DivMod<N, M, Undef>['div'];
export type Mod<N extends TyInt, M extends TyInt, Undef = never> =
  DivMod<N, M, Undef>['mod'];

export type EqualPropNames<T, U> = {
  [P in keyof T]: If<Equal<T[P], U>, P, never>;
}[keyof T];
export type NotEqualPropNames<T, U> = {
  [P in keyof T]: If<Equal<T[P], U>, never, P>;
}[keyof T];

export type OverrideExisting<T, U, K extends keyof U = keyof U> = {
  [P in keyof T]: P extends K ? U[P] : T[P];
};
export type Override<T, U, K extends keyof U = keyof U> =
  OverrideExisting<T, U, K> & Pick<U, Exclude<K, keyof T>>;
const test_Override_01: Equal<Override<{}, {}>, {}> = true;
const test_Override_02: Equal<Override<{a: 5}, {}>, {a: 5}> = true;
const test_Override_03: Equal<Override<{a: 5}, {b: 7}>, {a: 5, b: 7}> = true;
const test_Override_04: Equal<Override<{a: 5, b: 1}, {b: 7}>, {a: 5, b: 7}> = true;
const test_Override_05: Equal<Override<{a: 5, b: 1}, {a: 9, b: 7}>, {a: 9, b: 7}> = true;
const test_Override_06: Equal<Override<{a: 5, b: 1}, {a: 9, b: 7}, never>, {a: 5, b: 1}> = true;
const test_Override_07: Equal<Override<{a: 5, b: 1}, {a: 9, b: 7}, 'a'>, {a: 9, b: 1}> = true;
const test_Override_08: Equal<Override<{a: 5, b: 1}, {a: 9, b: 7}, 'a' | 'b'>, {a: 9, b: 7}> = true;
const test_Override_09: Equal<Override<{a: 5}, {a: 3}>, {a: 3}> = true;
const test_Override_10: Equal<Override<{}, {a: 3}>, {a: 3}> = true;
const test_Override_11: Equal<Override<{a: unknown}, {a: 3}>, {a: 3}> = true;
const test_Override_12: Equal<Override<{a: never}, {a: 3}>, {a: 3}> = true;
const test_Override_13: Equal<Override<{a: 5}, {a: unknown}>, {a: unknown}> = true;
const test_Override_14: Equal<Override<{a: 5}, {a: never}>, {}> = false;
const test_Override_15: Equal<Override<{a: 5}, {a: never}>, {a: never}> = true;
const test_Override_16: Equal<Override<[1, 2], [3, 4], '0'>, [3, 2]> = true;
// can't modify length, as tuple members aren't normal members with a length,
// but rather params to the builtin tuple type
const test_Override_17: Equal<Override<[1, 2], [3, 4, 5], '2' | 'length'>, [1, 2, 5]> = false;
export type Spread<T, U,
TKeys extends keyof T = keyof T, UKeys extends keyof U = keyof U> = {
  [P in TKeys | UKeys]: P extends UKeys ?
    // if in both, optional props need to fall back to T
    P extends TKeys ?
      U[P] extends infer V ? (V extends undefined ? T[P] : V) : tyVarDef
    : U[P]
  : P extends TKeys ? T[P] : unreachable;
};

export type ClosestDefinedTupleIndex<
  T, I extends TyInt, Max extends TyInt = TyIntMax,
  NotFound = never,
IStr extends TyIntString = TyIntToString<I>,
Val = IStr extends keyof T ? T[IStr] : undefined> = {
  'loop': ClosestDefinedTupleIndex<T, Inc<I>, Max, NotFound>;
  'found': I;
  'ret': NotFound;
}[If<Equal<Val, undefined>, LoopUntil<GtEq<I, Max>>, 'found'>];

const test_ClosestDefinedTupleIndex_00: Equal<ClosestDefinedTupleIndex<{
}, 0>, never> = true;
const test_ClosestDefinedTupleIndex_01: Equal<ClosestDefinedTupleIndex<{
  '0': 'yo';
}, 0>, 0> = true;
const test_ClosestDefinedTupleIndex_02: Equal<ClosestDefinedTupleIndex<{
  '1': 'yo';
}, 0>, 1> = true;
const test_ClosestDefinedTupleIndex_03: Equal<ClosestDefinedTupleIndex<{
  '0': undefined; '1': 'yo';
}, 0>, 1> = true;
const test_ClosestDefinedTupleIndex_04: Equal<ClosestDefinedTupleIndex<{
  '2': 'yo';
}, 0>, 2> = true;
const test_ClosestDefinedTupleIndex_05: Equal<ClosestDefinedTupleIndex<{
  '0': 'yo'; '5': 'yo';
}, 1>, 5> = true;

// type CompactTupleGo<T, Max,
// I extends TyInt = 0, Found extends TyInt = 0> =
//   T extends {length: TyInt} ? T['length'] extends infer Max ? Max extends TyInt ? {
//     'loop':
//       ClosestDefinedTupleIndex<T, Max, I, Max> extends infer NextI ?
//       NextI extends TyInt & keyof T ?
//       If<Equal<NextI, Max>,
//         CompactTupleGo<T, Max, Max, Found>,
//         CompactTupleGo<
//           Override<T, {[P in I]: T[NextI]} & {[P in NextI]: never}>, Max,
//           Inc<NextI, Max>, Inc<Found, Found>
//         >
//       > : unreachable : tyVarDef;
//     'ret': Override<T, {length: Found}>;
//   }[LoopUntil<Equal<I, Max>>] : T : tyVarDef : T;

// export type CompactTuple<T, Max = PrivateWrap> =
//   Max extends PrivateWrap ?
//   T extends {length: TyInt} ? T['length'] extends infer Max ? Max extends TyInt ?
//   CompactTupleGo<T, Max> : T : tyVarDef : T
//   : CompactTupleGo<T, Max>;
// const test_CompactTuple_01: Pick<['a'], keyof ['a']> = ['a'];
// const test_CompactTuple_02: Equal<CompactTuple<[undefined]>, []> = true;
// const test_CompactTuple_03: Equal<CompactTuple<['a']>, ['a']> = true;
// const test_CompactTuple_04: Equal<CompactTuple<[undefined, 'a']>, ['a']> = true;

// type ObjectPropValues<T> = T[keyof T];
// // takes {[A]: X} | {[A]: Y} and produces {[A]: X | Y}
// type JoinPropUnions<T> = T;
// const test_JoinPropUnions_1: Equal<JoinPropUnions<{} | {}>, {}> = true;
// const test_JoinPropUnions_2: Equal<
//   JoinPropUnions<{a: 1;} | {a: 2;}>,
//   {a: 1 | 2;}
// > = true;
// const test_JoinPropUnions_3: Equal<
//   JoinPropUnions<{a: 1;} | {a: 2;} | {a: 3;}>,
//   {a: 1 | 2 | 3;}
// > = true;

// type ExcludeExtract<T, U> = T extends U ? {exclude: never, extract: T} : {exclude: T, extract: never};
// const test_ExcludeExtract_1: Equal<
//   ExcludeExtract<'a' | 'b' | 'c' | 'd', 'a' | 'c' | 'f'>,
//   {exclude: 'b' | 'd', extract: 'a' | 'c'}
// > = true;
// // takes an object {[A]: {[X]: T}; [B]: {[X]: U}}
// // and produces {[X]: {[A]: T} | {[B]: U}}
// type Foo<T> = ObjectPropValues<{
//   [P in keyof T]: {
//     [Q in keyof T[P]]: {[R in P]: T[R][Q]}
//   }
// }>;
// // type PickIndexed<T, K> = FlattenObject<{
// //   [P in keyof T[keyof T]]: P extends K ? {[Q in keyof T]: P extends Q ? Q : never} : never;
// // }>;
// const test = {a: {y: true}, b: {y: 7}, c: {x: 'foo'}};
// const test2: Equal<Foo<typeof test>['x'], {c: 'foo'}> = true;
// const test3: Equal<Foo<typeof test>, {y: {a: true} | {b: 7}} | {x: {c: 'foo'}}> = true;
// // type ExcludeExtractPropNames<T, U> =
// //   {[P in keyof T]: T[P] extends U ? {extract: P} : {exclude: P}}[keyof T];
// // type ExcludeExtractProps<T, U> = PickIndexed<T, ExcludeExtractPropNames<T, U>>;

export namespace Circular {
  declare const hole: unique symbol;
  export interface Hole { [hole]: typeof hole }
  declare const optional: unique symbol;
  export interface Optional { [optional]: typeof optional }

  export type Substitute<T, N extends TyInt = 1, S = Optional, W = T> = {
    'hole': N extends 0 ? If<Equal<S, Optional>, undefined, S> : Substitute<W, Dec<N>, S, W>;
    'array': {
      [P in keyof T]: If<Equal<T[P], Hole>,
        N extends 0 ? S : Substitute<W, Dec<N>, S, W>,
        Substitute<T[P], N, S, W>
      >;
    } extends infer U ? If<Equal<S, Optional>, Pick<U, NotEqualPropNames<U, Optional>>, U> : tyVarDef;
    'object': {
      [P in keyof T]: If<Equal<T[P], Hole>,
        N extends 0 ? S : Substitute<W, Dec<N>, S, W>,
        Substitute<T[P], N, S, W>
      >;
    } extends infer U ? If<Equal<S, Optional>, Pick<U, NotEqualPropNames<U, Optional>>, U> : tyVarDef;
    'basic': T;
  }[
    Equal<T, Hole> extends true ? 'hole' :
    T extends any[] ? 'array' :
    T extends object ? [T] extends [{[P in keyof T]: infer V}] ? 'object' : unreachable :
    'basic'
  ];

  type GenTest<T> = [
    Circular.Substitute<T, 0>,
    Circular.Substitute<T, 1>,
    Circular.Substitute<T, 2>
  ];

  type Test1 = GenTest<Test1T<Circular.Hole>>;
  type Test1T<T> = T;

  const test1_0: Test1[0] = undefined;
  const test1_1: Test1[1] = undefined;
  const test1_2: Test1[2] = undefined;

  type Test2 = GenTest<Test2T<Circular.Hole>>;
  type Test2T<T> = { a: 'yo', b: T };

  const test2_0: Test2[0] = { a: 'yo' };
  const test2_1: Test2[1] = { a: 'yo', b: { a: 'yo' } };
  const test2_2: Test2[2] = { a: 'yo', b: { a: 'yo', b: { a: 'yo' } } };

  type Test3 = GenTest<Test3T<Circular.Hole>>;
  type Test3T<T> = ['yo', T];

  // const test3_0: Test3[0] = ['yo'];
  // const test3_1: Test3[1] = ['yo', ['yo']];
  // const test3_2: Test3[2] = ['yo', ['yo', ['yo']]];
}