4.6.2 regression: `Type instantiation is excessively deep and possibly infinite.`

[seansfkelley]

Bug Report

🔎 Search Terms

recursive conditional types

🕗 Version & Regression Information

• This changed between versions 4.5.5 and 4.6.2

⏯ Playground Link

Playground Link

💻 Code

type Query<T> = {
  [P in DeepKeys<T>]?: string;
};

type Primitive =
	| null
	| undefined
	| string
	| number
	| boolean
	| symbol
	| bigint;

type DeepKeys<T> = T extends Primitive
  ? never
  :
      | (keyof T & string)
      | {
          [P in keyof T & string]: T[P] extends (infer Inner)[]
            ? `${P}.${DeepKeys<Inner>}`
            : T[P] extends object
            ? `${P}.${DeepKeys<T[P]>}`
            : P;
        }[keyof T & string];

🙁 Actual behavior

Type instantiation is excessively deep and possibly infinite. at the ${P}.${DeepKeys<T[P]>} snippet.

🙂 Expected behavior

No error. Type properly resolves to dot-notation keys of input object.

[RyanCavanaugh]

Bisected to #47341

[ahejlsberg]

In #47341 we added code to not explore circular constraints, which for sure is correct. But with that code in place we now run into #30639, which by its nature explores more type relations. In this case, the constraints of the types we explore just balloon and we run into the instantiation limiter after creating >5M instantiations.

The quick fix is to rewrite the DeepKeys<T> to be more efficient:

type DeepKeys<T> = T extends Primitive ? never :
    (keyof T & string) | { [P in keyof T & string]: DeepSubKeys<T, P> }[keyof T & string];

type DeepSubKeys<T, P extends keyof T & string> =
    T[P] extends (infer Inner)[] ? `${P}.${DeepKeys<Inner>}` :
    T[P] extends object ? `${P}.${DeepKeys<T[P]>}` :
    never;

It's subtle, but moving the template type in the mapped type into a separate type alias causes us to do more caching and explore fewer implied constraints (because there are fewer containing conditional types), and that in turn eliminates the ballooning.

It seems that we might also be able to reduce the number of types we explore in getResolvedBaseConstraint. I'll look into that and put up a PR so we can see the effects.

[seansfkelley]

Thanks for the detailed explanation! I had fiddled with some solutions using two related types, but I don't think I ever tried breaking them across these lines with mutual recursion.

[ahejlsberg]

@seansfkelley You're welcome. BTW, here's an alternate formulation that avoids mapped types which is likely more efficient:

type DeepKeys<T> =
    object extends T ? string :
    T extends readonly unknown[] ? DeepKeys<T[number]> :
    T extends object ? keyof T & string | DeepSubKeys<T, keyof T & string> :
    never;

type DeepSubKeys<T, K extends string> = K extends keyof T ? `${K}.${DeepKeys<T[K]>}` : never;

The separate type for subkeys here is needed to ensure distribution over K.

[seansfkelley]

Indeed! Anecdotally, that is far more efficient to respond to autocompletes than the type I was using before. Definitely more readable, too.