Little bench for TypeScript's extremely slow large type union type checking

bench.js

// Mirrors the `Shortcut` type from bench.ts in plain JS.
// Enumerates the 200k+ string literals TS would build internally for the
// `Shortcut` union, then measures how long it takes to stuff them into a Set.
//
//   node bench.js

// ---- modifiers, grouped by family (aliases within a family are interchangeable) ----
const ModifierAlt = ['Alt', 'Option'];
const ModifierCmd = ['Command', 'Cmd', 'Meta'];
const ModifierCtrl = ['Control', 'Ctrl'];
const ModifierCmdOrCtrl = ['CommandOrControl', 'CmdOrCtrl'];
const ModifierShift = ['Shift'];
const families = [ModifierAlt, ModifierCmd, ModifierCtrl, ModifierCmdOrCtrl, ModifierShift];
const Modifier = families.flat();

const familyIndexOf = new Map();
for (let fi = 0; fi < families.length; fi++) {
  for (const m of families[fi]) familyIndexOf.set(m, fi);
}

// ---- triggers ----
const TriggerDigit = '0123456789'.split('');
const TriggerLetter = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');
const TriggerFunction = Array.from({ length: 12 }, (_, i) => `F${i + 1}`);
const TriggerSpecial = ['Backspace','Delete','Del','Down','End','Enter','Return','Esc','Escape','Home','Left','PageDown','PageUp','Right','Space','Spacebar','Tab','Up'];
const TriggerPunctuation = '!@#$%^&*()-_+=[{]}\\|;:\'"<>/?~`'.split('');
const Trigger = [...TriggerDigit, ...TriggerLetter, ...TriggerFunction, ...TriggerSpecial, ...TriggerPunctuation];

// Decrement<N> = [never, 0, 1, 2, 3, 4][N]  ->  4->3, 3->2, 2->1, 1->0, 0->undefined(stop)
const decrement = (n) => (n <= 0 ? -1 : n - 1);

// ShortcutTail<Pool, Full, Depth>:
//   | `+${Trigger}`
//   | (Depth extends 0 ? never : for each M in Pool: `+${M}${ShortcutTail<Full minus family(M), ..., Decrement<Depth>>}`)
function* shortcutTail(pool, full, depth) {
  for (const t of Trigger) yield `+${t}`;
  if (depth === 0) return; // matches `Depth extends 0 ? never : ...`
  for (const m of pool) {
    const fi = familyIndexOf.get(m);
    const remaining = full.filter((x) => familyIndexOf.get(x) !== fi);
    for (const tail of shortcutTail(remaining, remaining, decrement(depth))) {
      yield `+${m}${tail}`;
    }
  }
}

// ShortcutHandAndTail<Pool, Full>:
//   | Trigger
//   | for each M in Pool: `${M}${ShortcutTail<Full minus family(M), ..., Decrement<4>>}`
function* shortcutHand(pool = Modifier, full = pool) {
  for (const t of Trigger) yield t;
  for (const m of pool) {
    const fi = familyIndexOf.get(m);
    const remaining = full.filter((x) => familyIndexOf.get(x) !== fi);
    for (const tail of shortcutTail(remaining, remaining, decrement(4))) {
      yield `${m}${tail}`;
    }
  }
}

// ---- generation benchmark ----

function runOnce() {
  const set = new Set();
  for (const s of shortcutHand()) set.add(s);
  return set;
}

console.time('shortcuts.generation');
const shortcuts = runOnce();
console.timeEnd('shortcuts.generation');
console.log('Generated', shortcuts.size, 'shortcuts');

// ---- has benchmark ----

const tests = ['A', 'Alt+A', 'Alt+Cmd+A', 'Alt+Cmd+Ctrl+Shift+A', 'Cmd+Shift+1', 'Ctrl+Shift+F5', 'Option+CmdOrCtrl+Tab', '!', 'Shift+~', 'Cmd+Meta+Down', 'Alt+Option+A', 'Cmd+Meta+A', 'Control+Ctrl+A', 'CommandOrControl+CmdOrCtrl+A', 'Alt+Alt+A', 'Shift+Shift+A', 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A', 'Alt+Foo', 'Baz', 'Alt+', 'A', 'Alt+A', 'Alt+Cmd+A', 'Alt+Cmd+Ctrl+Shift+A', 'Cmd+Shift+1', 'Ctrl+Shift+F5', 'Option+CmdOrCtrl+Tab', '!', 'Shift+~', 'Cmd+Meta+Down', 'Alt+Option+A', 'Cmd+Meta+A', 'Control+Ctrl+A', 'CommandOrControl+CmdOrCtrl+A', 'Alt+Alt+A', 'Shift+Shift+A', 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A', 'Alt+Foo', 'Baz', 'Alt+', 'A', 'Alt+A', 'Alt+Cmd+A', 'Alt+Cmd+Ctrl+Shift+A', 'Cmd+Shift+1', 'Ctrl+Shift+F5', 'Option+CmdOrCtrl+Tab', '!', 'Shift+~', 'Cmd+Meta+Down', 'Alt+Option+A', 'Cmd+Meta+A', 'Control+Ctrl+A', 'CommandOrControl+CmdOrCtrl+A', 'Alt+Alt+A', 'Shift+Shift+A', 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A', 'Alt+Foo', 'Baz', 'Alt+', 'A', 'Alt+A', 'Alt+Cmd+A', 'Alt+Cmd+Ctrl+Shift+A', 'Cmd+Shift+1', 'Ctrl+Shift+F5', 'Option+CmdOrCtrl+Tab', '!', 'Shift+~', 'Cmd+Meta+Down', 'Alt+Option+A', 'Cmd+Meta+A', 'Control+Ctrl+A', 'CommandOrControl+CmdOrCtrl+A', 'Alt+Alt+A', 'Shift+Shift+A', 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A', 'Alt+Foo', 'Baz', 'Alt+', 'A', 'Alt+A', 'Alt+Cmd+A', 'Alt+Cmd+Ctrl+Shift+A', 'Cmd+Shift+1', 'Ctrl+Shift+F5', 'Option+CmdOrCtrl+Tab', '!', 'Shift+~', 'Cmd+Meta+Down', 'Alt+Option+A', 'Cmd+Meta+A', 'Control+Ctrl+A', 'CommandOrControl+CmdOrCtrl+A', 'Alt+Alt+A', 'Shift+Shift+A', 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A', 'Alt+Foo', 'Baz', 'Alt+'];

function runHas() {
  for (const t of tests) {
    shortcuts.has(t);
  }
};

console.time('shortcuts.has');
runHas();
console.timeEnd('shortcuts.has');

bench.ts

// Run the follwowing to benchmark this:
// npx tsc --noEmit --extendedDiagnostics



// Shortcut enumartion, 200k+ shortcuts, it makes sense that it takes a bit

type ModifierAlt = 'Alt' | 'Option';
type ModifierCmd = 'Command' | 'Cmd' | 'Meta';
type ModifierCtrl = 'Control' | 'Ctrl';
type ModifierCmdOrCtrl = 'CommandOrControl' | 'CmdOrCtrl';
type ModifierShift = 'Shift';
type Modifier = ModifierAlt | ModifierCmd | ModifierCtrl | ModifierCmdOrCtrl | ModifierShift;

type TriggerDigit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
type TriggerLetter = 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z';
type TriggerFunction = 'F1' | 'F2' | 'F3' | 'F4' | 'F5' | 'F6' | 'F7' | 'F8' | 'F9' | 'F10' | 'F11' | 'F12';
type TriggerSpecial = 'Backspace' | 'Delete' | 'Del' | 'Down' | 'End' | 'Enter' | 'Return' | 'Esc' | 'Escape' | 'Home' | 'Left' | 'PageDown' | 'PageUp' | 'Right' | 'Space' | 'Spacebar' | 'Tab' | 'Up';
type TriggerPunctuation = '!' | '@' | '#' | '$' | '%' | '^' | '&' | '*' | '(' | ')' | '-' | '_' | '+' | '=' | '[' | '{' | ']' | '}' | '\\' | '|' | ';' | ':' | "'" | '"' | '<' | '>' | '/' | '?' | '~' | '`';
type Trigger = TriggerDigit | TriggerLetter | TriggerFunction | TriggerSpecial | TriggerPunctuation;

type Decrement<N extends number> = [never, 0, 1, 2, 3, 4][N];

type ModifierFamily<T extends Modifier> =
  T extends ModifierAlt ? ModifierAlt :
  T extends ModifierCmd ? ModifierCmd :
  T extends ModifierCtrl ? ModifierCtrl :
  T extends ModifierCmdOrCtrl ? ModifierCmdOrCtrl :
  T extends ModifierShift ? ModifierShift :
  never;

type ShortcutTail<Pool extends Modifier, Full extends Modifier, Depth extends number> =
  | `+${Trigger}`
  | (Depth extends 0 ? never : (Pool extends infer M extends Modifier ? `+${M}${ShortcutTail<Exclude<Full, ModifierFamily<M>>, Exclude<Full, ModifierFamily<M>>, Decrement<Depth>>}` : never));

type ShortcutHandAndTail<Pool extends Modifier = Modifier, Full extends Modifier = Pool> =
  | Trigger
  | (Pool extends infer M extends Modifier ? `${M}${ShortcutTail<Exclude<Full, ModifierFamily<M>>, Exclude<Full, ModifierFamily<M>>, Decrement<4>>}` : never);

type Shortcut = ShortcutHandAndTail;
// type Shortcut = string;



// Type checking, extremely slow, when it could just be a constant-time check over the 200k type union, no?
// If you comment the following out the time to type-check the file plummets

const _v1: Shortcut = 'A';
const v2: Shortcut = 'Alt+A';
const v3: Shortcut = 'Alt+Cmd+A';
const v4: Shortcut = 'Alt+Cmd+Ctrl+Shift+A';
const v5: Shortcut = 'Cmd+Shift+1';
const v6: Shortcut = 'Ctrl+Shift+F5';
const v7: Shortcut = 'Option+CmdOrCtrl+Tab';
const v8: Shortcut = '!';
const v9: Shortcut = 'Shift+~';
const v10: Shortcut = 'Cmd+Meta+Down';

/* INVALID — alias/family repetition */

const i1: Shortcut = 'Alt+Option+A';
const i2: Shortcut = 'Cmd+Meta+A';
const i3: Shortcut = 'Control+Ctrl+A';
const i4: Shortcut = 'CommandOrControl+CmdOrCtrl+A';
const i5: Shortcut = 'Alt+Alt+A';
const i6: Shortcut = 'Shift+Shift+A';

/* INVALID — depth exceeded (5 modifiers) */

const i7: Shortcut = 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A';

/* INVALID — bad trigger */

const i8: Shortcut = 'Alt+Foo';
const i9: Shortcut = 'Baz';
const i10: Shortcut = 'Alt+';

// ----------------------------

const _v1: Shortcut = 'A';
const _v2: Shortcut = 'Alt+A';
const _v3: Shortcut = 'Alt+Cmd+A';
const _v4: Shortcut = 'Alt+Cmd+Ctrl+Shift+A';
const _v5: Shortcut = 'Cmd+Shift+1';
const _v6: Shortcut = 'Ctrl+Shift+F5';
const _v7: Shortcut = 'Option+CmdOrCtrl+Tab';
const _v8: Shortcut = '!';
const _v9: Shortcut = 'Shift+~';
const _v10: Shortcut = 'Cmd+Meta+Down';

/* INVALID — alias/family repetition */

const _i1: Shortcut = 'Alt+Option+A';
const _i2: Shortcut = 'Cmd+Meta+A';
const _i3: Shortcut = 'Control+Ctrl+A';
const _i4: Shortcut = 'CommandOrControl+CmdOrCtrl+A';
const _i5: Shortcut = 'Alt+Alt+A';
const _i6: Shortcut = 'Shift+Shift+A';

/* INVALID — depth exceeded (5 modifiers) */

const _i7: Shortcut = 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A';

/* INVALID — bad trigger */

const _i8: Shortcut = 'Alt+Foo';
const _i9: Shortcut = 'Baz';
const _i10: Shortcut = 'Alt+';

// ----------------------------

const __v1: Shortcut = 'A';
const __v2: Shortcut = 'Alt+A';
const __v3: Shortcut = 'Alt+Cmd+A';
const __v4: Shortcut = 'Alt+Cmd+Ctrl+Shift+A';
const __v5: Shortcut = 'Cmd+Shift+1';
const __v6: Shortcut = 'Ctrl+Shift+F5';
const __v7: Shortcut = 'Option+CmdOrCtrl+Tab';
const __v8: Shortcut = '!';
const __v9: Shortcut = 'Shift+~';
const __v10: Shortcut = 'Cmd+Meta+Down';

/* INVALID — alias/family repetition */

const __i1: Shortcut = 'Alt+Option+A';
const __i2: Shortcut = 'Cmd+Meta+A';
const __i3: Shortcut = 'Control+Ctrl+A';
const __i4: Shortcut = 'CommandOrControl+CmdOrCtrl+A';
const __i5: Shortcut = 'Alt+Alt+A';
const __i6: Shortcut = 'Shift+Shift+A';

/* INVALID — depth exceeded (5 modifiers) */

const __i7: Shortcut = 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A';

/* INVALID — bad trigger */

const __i8: Shortcut = 'Alt+Foo';
const __i9: Shortcut = 'Baz';
const __i10: Shortcut = 'Alt+';

// ----------------------------

const ____v1: Shortcut = 'A';
const ___v2: Shortcut = 'Alt+A';
const ___v3: Shortcut = 'Alt+Cmd+A';
const ___v4: Shortcut = 'Alt+Cmd+Ctrl+Shift+A';
const ___v5: Shortcut = 'Cmd+Shift+1';
const ___v6: Shortcut = 'Ctrl+Shift+F5';
const ___v7: Shortcut = 'Option+CmdOrCtrl+Tab';
const ___v8: Shortcut = '!';
const ___v9: Shortcut = 'Shift+~';
const ___v10: Shortcut = 'Cmd+Meta+Down';

/* INVALID — alias/family repetition */

const ___i1: Shortcut = 'Alt+Option+A';
const ___i2: Shortcut = 'Cmd+Meta+A';
const ___i3: Shortcut = 'Control+Ctrl+A';
const ___i4: Shortcut = 'CommandOrControl+CmdOrCtrl+A';
const ___i5: Shortcut = 'Alt+Alt+A';
const ___i6: Shortcut = 'Shift+Shift+A';

/* INVALID — depth exceeded (5 modifiers) */

const ___i7: Shortcut = 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A';

/* INVALID — bad trigger */

const ___i8: Shortcut = 'Alt+Foo';
const ___i9: Shortcut = 'Baz';
const ___i10: Shortcut = 'Alt+';

// ----------------------------

const ____v1: Shortcut = 'A';
const ____v2: Shortcut = 'Alt+A';
const ____v3: Shortcut = 'Alt+Cmd+A';
const ____v4: Shortcut = 'Alt+Cmd+Ctrl+Shift+A';
const ____v5: Shortcut = 'Cmd+Shift+1';
const ____v6: Shortcut = 'Ctrl+Shift+F5';
const ____v7: Shortcut = 'Option+CmdOrCtrl+Tab';
const ____v8: Shortcut = '!';
const ____v9: Shortcut = 'Shift+~';
const ____v10: Shortcut = 'Cmd+Meta+Down';

/* INVALID — alias/family repetition */

const ____i1: Shortcut = 'Alt+Option+A';
const ____i2: Shortcut = 'Cmd+Meta+A';
const ____i3: Shortcut = 'Control+Ctrl+A';
const ____i4: Shortcut = 'CommandOrControl+CmdOrCtrl+A';
const ____i5: Shortcut = 'Alt+Alt+A';
const ____i6: Shortcut = 'Shift+Shift+A';

/* INVALID — depth exceeded (5 modifiers) */

const ____i7: Shortcut = 'Alt+Cmd+Ctrl+Shift+CmdOrCtrl+A';

/* INVALID — bad trigger */

const ____i8: Shortcut = 'Alt+Foo';
const ____i9: Shortcut = 'Baz';
const ____i10: Shortcut = 'Alt+';

package.json

{
  "name": "test",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "typescript": "^6.0.3"
  }
}

tsconfig.json

{
  "compilerOptions": {
    "target": "esnext",
    "module": "esnext",
    "moduleResolution": "bundler",
    "lib": ["esnext"],
    "strict": true,
    "noEmit": true,
    "skipLibCheck": true,
    "isolatedModules": true,
    "esModuleInterop": true,
    "forceConsistentCasingInFileNames": true,
    "noUncheckedIndexedAccess": true,
    "exactOptionalPropertyTypes": true
  },
  "include": ["bench.ts"]
}