Crash when generating a type (via template literals) that is too large

[LukeChannings]

Bug Report

🕗 Version & Regression Information

• This is a crash

I have tested this with 4.4.3, 4.4.4, and 4.5.0-dev.20211022 (linked playground)

⏯ Playground Link

Playground

💻 Code

export type Spacing =
    | `0`
    | `${number}px`
    | `${number}rem`
    | `s${1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20}`;

const spacing: Spacing = "s12"

export type SpacingShorthand =
    | `${Spacing} ${Spacing}`
    | `${Spacing} ${Spacing} ${Spacing}`
    | `${Spacing} ${Spacing} ${Spacing} ${Spacing}`;

const test: SpacingShorthand = "0 0 0";

I can get a working version by replacing:

-     | `s${1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20}`;
+     | `s${number}`

🙁 Actual behavior

tsc crashes with the following error:

node_modules/typescript/lib/tsc.js:92656
    throw e;
    ^

RangeError: Value undefined out of range for undefined options property undefined
    at Map.set (<anonymous>)
    at recursiveTypeRelatedTo (node_modules/typescript/lib/tsc.js:51947:30)
    at isRelatedTo (node_modules/typescript/lib/tsc.js:51527:34)
    at checkTypeRelatedTo (node_modules/typescript/lib/tsc.js:51213:26)
    at isTypeRelatedTo (node_modules/typescript/lib/tsc.js:51176:24)
    at isTypeSubtypeOf (node_modules/typescript/lib/tsc.js:50459:20)
    at node_modules/typescript/lib/tsc.js:48286:90
    at Object.some (node_modules/typescript/lib/tsc.js:662:25)
    at _loop_16 (node_modules/typescript/lib/tsc.js:48286:45)
    at removeStringLiteralsMatchedByTemplateLiterals (node_modules/typescript/lib/tsc.js:48291:21)

🙂 Expected behavior

The SpacingShorthand type should be computed.

[ahejlsberg]

It appears we're running into V8's maximum Map/Set size limit. The exception error message is obviously not helpful, and apparently there is work afoot to fix it. See nodejs/node#37320.

That said, it would be nice to handle this more gracefully in the compiler.

[LukeChannings]

Agreed.

It'd be fine if it threw an error telling me what was wrong, and where.

My experience of debugging this went something like:

1. Why is TypeScript not giving me any hints 😤?
2. Oh, running tsc crashes...
3. What did I change last 🤔?
4. Tweak types until tsc doesn't crash anymore

I definitely did something silly with combination of types, but template string types (which are brilliant) do make this kind of thing easier.

[ahejlsberg]

It'd be fine if it threw an error telling me what was wrong, and where.

Agreed, the current behavior is confusing to say the least.

A bit more data on the root cause. During union type construction, the type checker removes string literal types that are matched by template literal types with placeholders (such as `${number}px`). This is a quadratic operation because we relate every string literal to every template literal. We use a subtype relation check and, in your example, end up overflowing the subtype relation cache. It's actually somewhat useless to cache these particular relations and doing so consumes more time and memory than the work itself. So, we should probably revise that logic. I did a little experiment, and things start behaving as expected once I bypass the caching. Specifically, your full example errors with "Expression produces a union type that is too complex to represent" (it attempts to construct a union with >250K elements), but it succeeds when I remove the last line of the SpacingShorthand type.