`RangeError: Map maximum size exceeded` with `typescript@4.8.1-rc`

[nstepien]

Bug Report

🔎 Search Terms

Map maximum size exceeded

🕗 Version & Regression Information

• This is a crash
• This changed between versions ~4.7.2 and 4.8.1-rc

⏯ Playground Link

Playground link with relevant code
I don't know what causes this exactly, but the repo isn't too big:
Comcast/react-data-grid#2988

💻 Code

I don't know what code causes the crash. Please see this branch:
Comcast/react-data-grid#2988

🙁 Actual behavior

> tsc

D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:98414
                throw e;
                ^

RangeError: Map maximum size exceeded
    at Map.set (<anonymous>)
    at recursiveTypeRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55247:42)
    at isRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:54809:25)
    at eachTypeRelatedToType (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55098:35)
    at unionOrIntersectionRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:54990:25)        
    at structuredTypeRelatedToWorker (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55321:34)       
    at structuredTypeRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55261:30)
    at recursiveTypeRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55230:30)
    at isRelatedTo (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:54809:25)
    at eachTypeRelatedToType (D:\repos\react-data-grid\node_modules\typescript\lib\tsc.js:55098:35)

Node.js v18.7.0

🙂 Expected behavior

No crash.

[nstepien]

I also tried 4.9.0-dev.20220812 and had the same crash

[weswigham]

I threw together a custom build that works around the map size limit (pretty easy to do with a wrapper around the builtin Map). Here's some stats on the linked project with said build (running on a piddly laptop, so while the > 1m time is annoying, it's not too worrying):

That's right, the assignability cache contains just shy of 17M entries! The max entry count for a single map is 2^24, which is 16,777,216 - just below that comparison count, hence the error in the OP.
Here are the same stats from 4.7.4:

We've casually added around 16 million extra assignability comparisons into the build. Now, I'm honestly impressed that we can do that and still finish in human-scale time and standard memory limits - but we've 5x'd the build time here, so clearly something could use improvement. We're not making too many more instantiations or types, so it's likely some heuristic we used to skip comparisons is no longer being triggered, though I can't claim to know which and for sure that that's the case yet.

Still, while I keep looking into the underlying perf issue, since evidently we can continue to chug along and check meaningful projects beyond the 2**24 map size limit in somewhat reasonable time, I may put up a PR with my Map wrapper, to at least alleviate the crash in the nightly, assuming it doesn't negatively affect perf in the general case.

[ahejlsberg]

@weswigham Did you bisect to identify the commit that caused the issue?

[nstepien]

in somewhat reasonable time
assuming it doesn't negatively affect perf in the general case

FWIW with 4.8.1-rc, tsc takes over 1 minute until it crashes, while it takes ~17 seconds in CI in the main branch with 4.7.

[weswigham]

@ahejlsberg Yea, it looks like it's 51b346d, so the {} | null | undefined <-> unknown rules may have some poor behavior in some edge cases.

[ahejlsberg]

I researched the cause of the assignability relation cache size explosion in 4.8 and later. The original repro contains this helper function in the @linaria package dependency:

declare const isTypedNode:
    <T extends NodePath['type']>(type: T) => (p: NodePath<Node>) => p is NodePath<Extract<Node, { type: T }>>;

where NodePath is a class declared in @types/babel__traverse/index.d.ts (type definitions for Babel 7). Checking of that declaration ends up relating NodePath<Node> to NodePath<Extract<Node, { type: T }>>, which then goes off the tracks when relating the generic get method in the NodePath class.

get<K extends keyof T>(
    key: K,
    context?: boolean | TraversalContext,
): T[K] extends Array<Node | null | undefined>
    ? Array<NodePath<T[K][number]>>
    : T[K] extends Array<Node | null | undefined> | null | undefined
    ? Array<NodePath<NonNullable<T[K]>[number]>> | NodePath<null | undefined>
    : T[K] extends Node | null | undefined
    ? NodePath<T[K]>
    : never;

The use of inline anonymous conditional types means that we always relate structurally (instead of computing variance and relating type arguments). Futhermore, we produce intersections in the true branches of the conditional types because we intersect with the extends type to reflect the check. This, in combination with #49119 that improves intersection reduction (more often reducing them to never), sets us up for the mismatched union lengths problem described by @weswigham here.

The best way to fix this issue is to change the generic get method to use an aliased conditional type:

get<K extends keyof T>(key: K, context?: boolean | TraversalContext): NodePathResult<T[K]>;

where NodePathResult<T> is

export type NodePathResult<T> =
    (Extract<T, Node | null | undefined> extends never ? never : NodePath<Extract<T, Node | null | undefined>>) |
    (T extends Array<Node | null | undefined> ? Array<NodePath<T[number]>> : never);

This fixes the issue and generally improves check time with both earlier and later versions than 4.8. It also is a more correct type becase it can handle combinations of Node and Node[].

I will submit a PR to @types/babel__traverse to get this fixed.

EDIT: Given we now have a fix in #50397 I won't be submitting a PR to Babel.

[nstepien]

Hopefully fixed in 4.8.3?