TS 4.5 type instantiation is excessively deep and possibly infinite, with seemingly legal type

[mmvsk]

Bug Report

There seem to be an issue with a very specific edge case:

type F<T> = {} & (
    T extends [any, ...any[]]
        ? { [K in keyof T]?: F<T[K]> }
        : T extends any[]
            ? F<T[number]>[]
            : T extends { [K: string]: any }
                ? { [K in keyof T]?: F<T[K]> }
                : { x: string }
);

function f<T = any>() {
    return undefined! as F<T>;
}

export function g() {
    return f() as F<any>;
}

Gives the following error:

main.ts:16:9 - error TS2589: Type instantiation is excessively deep and possibly infinite.

16  return g() as F<any>;
           ~~~

However, this code worked with typescript prior to 4.5.0-dev.20211001 (so 4.4), and what's unusual, changing almost anything in this code removes the error, such as:

• return f<any>() as F<any>; (and it should be exactly the same as it's function f<T = any>() [?])
• return f();
• replacing { x: unknown } with {}
• removing T extends any[]
• removing T extends [any, ...any[]]
• or using F<T[number]>[] instead of { [K in keyof T]?: F<T[K]> }
• TS 4.4...

🔎 Search Terms

type instantiation is excessively deep and possibly infinite

It returned the possibily related #46404, howver, it was not fixed in #46429 as the comments suggest (still present in latest 4.5.0-dev.20211023).

🕗 Version & Regression Information

Appeared in TypeScript 4.5.0-dev.20211001 (worked until 4.5.0-dev.20210930). Probably it was introduced with PR #41821, it caused then an infinite loop that resulted in a "JS heap out of memory" error. Then, with PR #46326, the problem was caught and the above message appeared.

[ahejlsberg]

Yeah, that isn't right. The issue here is that we bypass caching of relations for small unions and intersections, but that bypass also causes us to loose a check for deeply nested types that would have stopped the recursion. It used to not matter, but after #41821 it does. We need to revise our logic such that we can bypass caching but still check for deep nesting.