type checking complexity with multiple template literals in unions

[eps1lon]

🔎 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

[jakebailey]

I'm pretty sure I tried this (no pun intended) in #59759

[eps1lon]

What was the conclusion to that? Seems like it fizzled out after memory concerns. Though the benchmarks only showed a noticeable memory increase for "self-build-src - node (v18.15.0, x64)" which I can dig into more if you want.

[jakebailey]

The conclusion was "we didn't come to a conclusion before this codebase became closed to new PRs": https://github.com/microsoft/TypeScript#contribute

[eps1lon]

There's a Go port: microsoft/typescript-go#3331