如何解决TypeScript类型级深度优先搜索的类型实例化过深错误？

问题背景 #

尝试用TypeScript类型系统实现深度优先搜索（DFS）算法，已定义递归DFS所需的各类类型函数及测试图结构，但编译时触发以下错误：

Type instantiation is excessively deep and possibly infinite.

相关代码 #

const MyGraph: Graph = {
  A: ["B", "C", "D"],
  B: ["F", "E"],
  C: ["E", "F"],
  D: ["E", "F", "G"],
  E: [],
  F: [],
  G: [],
};

type Graph = {
  A: ["B", "C", "D"],
  B: ["F", "E"],
  C: ["E", "F"],
  D: ["E", "F", "G"],
  E: [],
  F: [],
  G: [],
}

export type Concat<T extends string[], U extends string[]> = [...T, ...U];
export type Pop<T extends string[]> = T extends [...infer Rest extends string[], infer Last extends string]
  ? T extends [infer Last]
  ? []
  : Rest
  : never;
export type Append<T extends string[], U extends string> = [...T, U];
export type IsEmpty<T extends string[]> = T extends [] ? true : false;
export type Difference<T extends string[], U extends string[], Result extends string[] = []> =
  T extends [infer First extends string, ...infer Rest extends string[]]
  ? false extends Contains<U, First> 
  ? Difference<Rest, U, Append<Result, First>>
  : Difference<Rest, U, Result>
  : T extends string[]
  ? string[]
  : Result;
export type Peek<T extends string[]> = T extends [...infer Rest extends string[], infer Last extends string]
  ? Last
  : T extends [infer Last extends string]
  ? Last
  : T extends string[]
  ? never
  : never;
export type Contains<T extends string[], Element extends string> = T extends [infer Head, ...infer Rest extends string[]]
  ? Head extends Element
  ? true
  : Contains<Rest, Element>
  : false;

export type DFSRecursive<Curr extends string, GraphType extends Graph, Stack extends string[], Visited extends string[] = []> =
  true extends IsEmpty<Stack>
  ? Visited
  : true extends Contains<Visited, Peek<Stack>>
  ? DFSRecursive<Peek<Stack>, GraphType, Pop<Stack>, Visited>
  : GraphType[keyof Graph & Peek<Stack>] extends infer GT extends string[]
  ? Difference<GT, Visited> extends infer D extends string[]
  ? Peek<Stack> extends infer PS extends string
  ? Append<Visited, PS> extends infer A extends string[]
  ? Concat<Pop<Stack>, D> extends infer C extends string[]
  ? DFSRecursive<Peek<Stack>, GraphType, C, A>
  : never
  : never
  : never
  : never
  : never;

type X = DFSRecursive<"A", Graph, ["A"]>

解决方案 #

1. 简化基础类型函数 #

减少不必要的条件分支，让类型推导更直接：

• 简化Peek和Pop类型，去掉冗余判断：

export type Peek<T extends string[]> = T extends [...infer _, infer Last extends string] ? Last : never;
export type Pop<T extends string[]> = T extends [...infer Rest extends string[], infer _] ? Rest : [];

• 修正Difference的兜底分支，避免意外类型拓宽导致递归无法终止：

export type Difference<T extends string[], U extends string[], Result extends string[] = []> =
  T extends [infer First extends string, ...infer Rest extends string[]]
  ? false extends Contains<U, First> 
  ? Difference<Rest, U, Append<Result, First>>
  : Difference<Rest, U, Result>
  : Result;

2. 扁平化DFS递归逻辑 #

拆分嵌套的infer层级，降低编译器的推导复杂度：

export type DFSRecursive<GraphType extends Graph, Stack extends string[], Visited extends string[] = []> =
  IsEmpty<Stack> extends true
  ? Visited
  : Peek<Stack> extends infer Top extends string
  ? Contains<Visited, Top> extends true
    ? DFSRecursive<GraphType, Pop<Stack>, Visited>
    : Append<Visited, Top> extends infer NewVisited extends string[]
      ? GraphType[Top] extends infer Neighbors extends string[]
        ? Difference<Neighbors, NewVisited> extends infer UnvisitedNeighbors extends string[]
          ? Concat<Pop<Stack>, UnvisitedNeighbors> extends infer NewStack extends string[]
            ? DFSRecursive<GraphType, NewStack, NewVisited>
            : never
          : never
        : never
      : never
  : never;

// 调用时无需传Curr参数，栈顶元素即为当前节点
type X = DFSRecursive<Graph, ["A"]>

3. 确保递归终止条件明确 #

所有递归分支必须有清晰的终止路径，避免编译器陷入无限推导循环。比如IsEmpty<Stack> extends true直接返回Visited，是明确的终止信号。

原理说明 #

TypeScript对递归类型的实例化有深度限制，原代码中多层嵌套的infer和递归调用快速耗尽了这个限制。通过简化类型逻辑、减少嵌套层级、明确终止条件，能让编译器高效处理类型推导，避免触发"过深实例化"错误。

内容的提问来源于stack exchange，提问作者Jim