type checking complexity with multiple template literals in unions #63342
Description
🔎 Search Terms
template literals, performance
🕗 Version & Regression Information
4.1 introduced template literals where tsc fails with RangeError: Map maximum size exceeded.
4.5 is the first version that completes where typechecking time already scales exponentially.
⏯ Playground Link
https://github.com/eps1lon/repro-ts-template-literals-complexity
💻 Code
The example is based on how Next.js typechecks the href in <Link /> components.
// Example type definitions for Next.js routes
type SearchOrHash = `?${string}` | `#${string}`;
type WithProtocol = `${string}:${string}`;
type Suffix = "" | SearchOrHash;
type SafeSlug<S extends string> = S extends `${string}/${string}`
? never
: S extends `${string}${SearchOrHash}`
? never
: S extends ""
? never
: S;
type StaticRoutes =
| `/next`
| ...;
// comment out union constituents to see exponential impact of dynamic routes
// 6 routes -> 5 -> 4 -> 3
// tsc on M3:
// 45s -> 24s -> 12s -> 6s
// tsgo on M3:
// 9s. -> 5s -> 2.5s -> 0.08s
type DynamicRoutes<T extends string = string> =
| `/${SafeSlug<T>}/${SafeSlug<T>}/${SafeSlug<T>}`
| `/${SafeSlug<T>}/${SafeSlug<T>}/integrations/${SafeSlug<T>}/${SafeSlug<T>}/resources/${SafeSlug<T>}/${SafeSlug<T>}/billing`
| ...;
type RouteImpl<T> =
| StaticRoutes
| SearchOrHash
| `${StaticRoutes}${SearchOrHash}`
| (T extends `${DynamicRoutes<infer _>}${Suffix}` ? T : never);
function Link<RouteType>(href: RouteImpl<RouteType>): void {}
Link("/api/ai-playground/sandbox"); // OK
Link("/new/~/integrations/vercel/front/billing"); // OK🙁 Actual behavior
Type checking time doubles with every constituent of DynamicRoutes with template literals
🙂 Expected behavior
Type-checking is reasonably fast
Additional information about the issue
No response