递归深度

在使用ts时，偶尔会碰到 Type instantiation is excessively deep and possibly infinite.ts(2589) 这个告警，绝大部分网上的资料会告诉你，递归深度控制在 50 以内，就不会有这个问题。

但是实际情况中，往往有时候我们的递归深度可以超过 50，达到 999，也不会触发这个问题，直到达到 1000。

问题复现

我们以计算字符的长度问题为例，复现这种情况。

要计算字符长度，思路有两种：

第一种，遍历字符，将字符转换成元组，元组 length 就是要求的长度，代码如下：

type StringToUnion<S extends string> = S extends `${string}${infer R}`
  ? [1, ...StringToUnion<R>]
  : [];

// Case1 = 20
type Case1 = StringToUnion<'12345678901234567890'>['length'];

第二种，也是遍历字符，通过增加一个辅助的计数元组，每次遍历一个字符，就往辅助元组里塞一个值，最终，遍历结束，辅助元组的长度就是题解。代码如下：

type LengthOfString<
  S extends string,
  Arr extends any[] = [],
> = S extends `${string}${infer R}`
  ? LengthOfString<R, [...Arr, 1]>
  : Arr['length'];

// Case2 = 20
type Case2 = LengthOfString<'12345678901234567890'>;

这两种解法看着没什么区别，但是当字符长度达到 49 时，解法一，就会出现 Type instantiation is excessively deep and possibly infinite.ts(2589) 这个问题，而解法二，会在字符长度达到 1000 时，才会出现这个问题。

同样是递归，这有啥区别？为什么第一种解法只能递归 50 次，而解法二，能够到 1000 呢？

尾调用、尾递归

在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

ts 中的尾递归优化

通过搜索 ts 的 checker.ts 代码，具体可以查看 源码 (opens new window) 中搜索: Type_instantiation_is_excessively_deep_and_possibly_infinite。

可以浅显的看到：

if (tailCount === 1000) {
  error(
    currentNode,
    Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite,
  );
  result = errorType;
  break;
}

如果尾递归超过了 1000，会报这个错误。

而单纯的递归：

function instantiateTypeWithAlias(
  type: Type,
  mapper: TypeMapper,
  aliasSymbol: Symbol | undefined,
  aliasTypeArguments: readonly Type[] | undefined,
): Type {
  if (!couldContainTypeVariables(type)) {
    return type;
  }
  if (instantiationDepth === 100 || instantiationCount >= 5000000) {
    // We have reached 100 recursive type instantiations, or 5M type instantiations caused by the same statement
    // or expression. There is a very high likelyhood we're dealing with a combination of infinite generic types
    // that perpetually generate new type identities, so we stop the recursion here by yielding the error type.
    tracing?.instant(tracing.Phase.CheckTypes, 'instantiateType_DepthLimit', {
      typeId: type.id,
      instantiationDepth,
      instantiationCount,
    });
    error(
      currentNode,
      Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite,
    );
    return errorType;
  }
  totalInstantiationCount++;
  instantiationCount++;
  instantiationDepth++;
  const result = instantiateTypeWorker(
    type,
    mapper,
    aliasSymbol,
    aliasTypeArguments,
  );
  instantiationDepth--;
  return result;
}

在深度超过了 100 或者内存占用超过了 5M，也会报这个错误。

结论

对于 上述计算字符长度的解法一：

type StringToUnion<S extends string> = S extends `${string}${infer R}`
  ? [1, ...StringToUnion<R>]
  : [];

// Case1 = 20
type Case1 = StringToUnion<'12345678901234567890'>['length'];

它的返回值并不是一个函数执行的返回值，所以并没有触发尾调用，此时深度只能达到 50。

对于解法二：

type LengthOfString<
  S extends string,
  Arr extends any[] = [],
> = S extends `${string}${infer R}`
  ? LengthOfString<R, [...Arr, 1]>
  : Arr['length'];

// Case2 = 20
type Case2 = LengthOfString<'12345678901234567890'>;

返回值，就是自身，触发了尾递归，此时深度可以达到 1000。