Excessive depth exploring template literal type constraints

[ahejlsberg]

TypeScript Version: 4.1.0-dev

Code

type PathKeys<T> =
 T extends readonly any[] ? Extract<keyof T, `${number}`> | SubKeys<T, Extract<keyof T, `${number}`>> :
 T extends object ? Extract<keyof T, string> | SubKeys<T, Extract<keyof T, string>> :
 never;

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

type PropType<T, Path extends string> =
 Path extends keyof T ? T[Path] :
 Path extends `${infer K}.${infer R}` ? K extends keyof T ? PropType<T[K], R> : unknown :
 unknown;

declare function getProp<T, P extends PathKeys<T>>(obj: T, path: P): PropType<T, P>;

const obj = {
 name: 'John',
 age: 42,
 cars: [
 { make: 'Ford', age: 10 },
 { make: 'Trabant', age: 35 }
 ]
} as const;

let make = getProp(obj, 'cars.1.make'); // 'Trabant'

Expected behavior:

No errors.

Actual behavior:

"Type instantiation is excessively deep and possibly infinite" error on declaration of getProp.

Playground Link:

https://www.typescriptlang.org/play?ts=4.1.0-dev.20201006#code/C4TwDgpgBACghsAFgaQiAzgHgCoD4oC8AUFKVNlBAB7AQB2AJulAE4RwMD2dANiFHDogA2gF0oAfigBRGizgBjYJgDWaTgDNyAGigADACQBvOgFcAtgCMILAL578AHygBlU5dQYcu2cHlLVdS1sXUMTC2s7B3wALhIyCmpaRmZOSwArCCVJGTlFZTUQTR0odD8ASzoAcydXd08sENy-fMCi4N0ylkqa2PjSOggANxsAbiIiUEg6jzRG3WRKGnomUorq-AIoRaSV5kLiiikw5FsAOmN4JAacYWRRXHsoGKhBkZZxyfBoGBZOMGw328sAQiCWyVWXR6m36IKQ4L2UAOwRy2GEV0Q4jiZDhYN2KX0xkqGhs23ORLoJJYUAASk8pDtlgTkeQcr9-oDILd7roabEoKY6Co6JwAO50Z6wwXCsV0T4MLI8OBsKAaQVKcrcKBVCDAdlgYEwBEEjE3PC4AAUaXSLyaYFBLxgAEpHX8AUCmjBcJ8FNwylBrYQoEZYXQ4OYIC8AOQAKU4iDoUe0sLgOpeABYAEzJnEKZXoF7CWE4oxQcxwNTRgBinBYDCTAjTUAAjAAGKC2HM4sil8uVqBR7DySyCYAN1ORqAAZgArB3YaIiLYBMxfXQyp8eLqyxXoFsdXq3VaMroo3mWOgzs2zn2IFGnaNSAB6J8DodwEd0MdEIA

[ahejlsberg]

Code similar to the above worked by chance in 4.1 beta because template literal types would collapse to just string when one or more placeholders were ${string}. The code now fails. The core issue is an infinite buildup of nested indexed access types (i.e. T[string][string][string][string]...) that results from constraint resolution. We've seen errors like these before that similarly trip the constraint depth limiter. What need a stack that keeps track of types for which we're resolving constraints and a limit after which we stop the exploration (and resolve to no constraint) using isDeeplyNestedType logic similar to type relationships. I will put up a PR to that effect.