Relating large unions of literal types performs poorly

[ahejlsberg]

🕗 Version & Regression Information

All versions.

⏯ Playground Link

Playground link with relevant code

💻 Code

type Digits = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
type T9XXXX = `9${Digits}${Digits}${Digits}${Digits}`;
type TXXXXX = `${Exclude<Digits, '0'>}${Digits}${Digits}${Digits}${Digits}`;

let x: Exclude<TXXXXX, T9XXXX> = '88888';

🙁 Actual behavior

The example above takes ~45s to compile on a reasonably fast machine. The underlying issue is that as we relate large unions of primitive types, we have a fast path for matches, but not for mismatches. Because the majority of the constituents of TXXXXX are not present in T9XXXX, we spend a lot of time in the slow path that attempts to find matches by iterating through all constituents.

🙂 Expected behavior

We can do much better by implementing a fast path for mismatches.

[fatcerberus]

The example above takes ~45s to compile on a reasonably fast machine.

So more out of morbid curiosity than anything...

fatcerberus@Bruces-MacBook-Pro temp % time npx tsc wtf.ts
npx tsc wtf.ts  60.97s user 0.17s system 101% cpu 1:00.28 total
fatcerberus@Bruces-MacBook-Pro temp % node -v
v19.7.0

That was with an M2 Pro. Holy crap.