《TypeScript高级编程》3.2 尾递归消除与深度限制

error TS2589: Type instantiation is excessively deep and possibly infinite.

// 撞第一道：展开太深，栈式递归
type Repeat<T, N extends number, Acc extends T[] = []> =
  Acc["length"] extends N ? Acc : Repeat<T, N, [...Acc, T]>;   // 这是尾递归，走第三道

type Nest<T, N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? T : { v: Nest<T, N, [...Acc, 0]> };

type A = Nest<number, 5>; // 递归结果被对象包装，五层嵌套
// 类型可能按需展开；单独声明更深的 Nest 别名不保证立刻触发限制

// 撞第二道：每个分支都产生新实例化，总量失控
type Combinator<T extends string> = `${T}a` | `${T}b` | `${T}c` | `${T}d`;
type Level1 = Combinator<"">;
type Level2 = Combinator<Level1>;   // 16 种
type Level3 = Combinator<Level2>;   // 64 种
type Level4 = Combinator<Level3>;   // 256 种，逐层 ×4

// 非尾递归：结果被 [...Reverse<R>, H] 包住，必须等内层返回后再拼接
type Reverse<T extends unknown[]> =
  T extends [infer H, ...infer R] ? [...Reverse<R>, H] : [];

// 尾递归：递归调用就是整个分支的结果，待办事项通过 Acc 参数下传
type ReverseFast<T extends unknown[], Acc extends unknown[] = []> =
  T extends [infer H, ...infer R] ? ReverseFast<R, [H, ...Acc]> : Acc;

type R1 = ReverseFast<[1, 2, 3]>;    // [3, 2, 1]
type Build<N extends number, A extends 1[] = []> =
  A["length"] extends N ? A : Build<N, [...A, 1]>;
type R2 = ReverseFast<Build<900>>; // TS 5.9.3 下长度 900 元组通过

// ❌ 没有趋近终止条件，最终会耗尽预算
type Chunk<T extends unknown[]> =
  T extends [] ? [] : Chunk<[T]>;

// ✅ 消费输入，保证对有限元组终止
type Walk<T extends unknown[]> =
  T extends [unknown, ...infer R] ? Walk<R> : [];

// 非尾递归的 Filter
type Filter<T extends unknown[], U> =
  T extends [infer H, ...infer R]
    ? H extends U
      ? [H, ...Filter<R, U>]
      : Filter<R, U>
    : [];

// 尾递归版本
type FilterFast<T extends unknown[], U, Acc extends unknown[] = []> =
  T extends [infer H, ...infer R]
    ? H extends U
      ? FilterFast<R, U, [...Acc, H]>
      : FilterFast<R, U, Acc>
    : Acc;

type Odd = FilterFast<[1, 2, 3, 4, 5], 1 | 3 | 5>;   // [1, 3, 5]

// 非尾递归：替换全部，结果在递归返回后拼接
type ReplaceAll<S extends string, From extends string, To extends string> =
  S extends `${infer A}${From}${infer B}` ? `${A}${To}${ReplaceAll<B, From, To>}` : S;

// 尾递归：已处理的前缀放进 Acc
type ReplaceAllFast<
  S extends string,
  From extends string,
  To extends string,
  Acc extends string = "",
> = S extends `${infer A}${From}${infer B}`
  ? ReplaceAllFast<B, From, To, `${Acc}${A}${To}`>
  : `${Acc}${S}`;

type S1 = ReplaceAllFast<"a-b-c-d", "-", "_">;   // "a_b_c_d"

type IsEven<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? true : IsOdd<N, [...Acc, 0]>;
type IsOdd<N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? false : IsEven<N, [...Acc, 0]>;
type Expect<T extends true> = T;
type E1 = Expect<IsEven<10>>;
type E2 = Expect<IsEven<900>>;
type E3 = Expect<IsOdd<901>>;

type Parity<N extends number, Acc extends unknown[] = [], Even extends boolean = true> =
  Acc["length"] extends N ? Even : Parity<N, [...Acc, 0], Even extends true ? false : true>;
type IsEvenFast<N extends number> = Parity<N>;
type E4 = Expect<IsEvenFast<900>>;
type E5 = Expect<IsEvenFast<901> extends false ? true : false>;

// Prev[3] = 2，Prev[0] = never：到 0 就终止
type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

type Paths<T, D extends number = 6> = [D] extends [0]
  ? never
  : T extends object
    ? {
        [K in keyof T & string]-?: K | `${K}.${Paths<T[K], Prev[D]>}`;
      }[keyof T & string]
    : never;

interface Api {
  user: { id: number; profile: { name: string; city: string } };
  post: { title: string };
}

type ApiPaths = Paths<Api>;
// "user" | "user.id" | "user.profile" | "user.profile.name"
//   | "user.profile.city" | "post" | "post.title"

interface TreeNode {
  value: number;
  children: TreeNode[];   // 自引用
}

type DeepReadonlySafe<T, D extends number = 4> = [D] extends [0]
  ? T
  : T extends string | number | boolean | null | undefined
    ? T
    : T extends readonly (infer E)[]
      ? readonly DeepReadonlySafe<E, Prev[D]>[]
      : T extends object
        ? { readonly [K in keyof T]: DeepReadonlySafe<T[K], Prev[D]> }
        : T;

// 递归映射可能延迟展开；计数器明确限定要处理的深度
type FrozenTree = DeepReadonlySafe<TreeNode>;   // 深度 4 干净终止

npx tsc --noEmit 2>&1 | head -20                       # 看报错落在哪个类型上
npx tsc --noEmit --generateTrace ./trace               # 生成 types.json
node analyze-trace.mjs ./trace/types.json | head -10   # 复用 3.1 的聚合脚本

// 临时把可疑类型换成具体参数，二分定位是哪一步开始超限
type Probe1 = Paths<Api, 2>;   // 通过？
type Probe2 = Paths<Api, 4>;   // 通过？
type Probe3 = Paths<Api, 6>;   // 报错？→ 临界点在 4~6 之间

type Prev = [never, 0, 1, 2, 3, 4, 5, 6];

// 单递归 + 累加器 + 计数器封顶
type ParamsOf<
  R extends string,
  D extends number = 6,
  Acc extends string = never,
> = [D] extends [0]
  ? Acc
  : R extends `${string}:${infer Rest}`
    ? Rest extends `${infer Name}/${infer Tail}`
      ? ParamsOf<`/${Tail}`, Prev[D], Acc | Name>
      : ParamsOf<"", Prev[D], Acc | Rest>
    : Acc;

type P1 = ParamsOf<"/user/:id/post/:slug">;   // "id" | "slug"
type P2 = ParamsOf<"/user/:id/:a/:b/:c/:d/:e/:f/:g">;   // 深度 6 截断，仍是合法结果
type P3 = ParamsOf<"/static/path">;            // never