TypeScript 尾递归优化限制999可以被操纵

j5fpnvbx  于 4个月前  发布在  TypeScript
关注(0)|答案(5)|浏览(59)

Bug报告

🔎 搜索词

尾递归,尾递归优化,尾递归检测,尾递归限制

🕗 版本与回归信息

  • 这是一次崩溃:是的
  • 在我尝试的每个版本中,我都检查了关于:是的的常见问题解答条目

⏯ Playground链接

带有相关代码的Playground链接

💔 实际行为

NumberToTuple1 正在使用尾递归优化,因此 BigTuple_Computed 类型为 [0, 0, 0, ..., 0],正如预期。
NumberToTuple2 没有使用尾递归优化,而是以不同的方式使用尾递归优化,因此 BigTuple_Error 类型为 any
它们之间的差异仅在于做无用功的代码片段 0 extends 1 ? never :
更新:NumberToTuple2 可以工作到999,而 NumberToTuple1 可以工作到3153

🙂 预期行为

根据介绍TypeScript尾调用优化的文章,尾调用优化应该应用于 NumberToTuple1NumberToTuple2,因为它们都没有对调用结果进行堆栈转换。预计递归限制保持不变

5ssjco0h

5ssjco0h1#

这真的是个bug吗?
1000 正好位于递归限制的边缘,所以我并不惊讶于两种略有不同的形式在接近极限时会有不同的行为。如果你使用类似 500 的东西,你会发现它们实际上都使用了尾递归优化,而不是像

type NumberToTuple3<N, T extends 0[] = []> =
  T['length'] extends N ? T : (NumberToTuple3<N, [...T, 0]> & {});

这样的东西:

type BigT_Computed = NumberToTuple1<500> // ok
type BigT_StillOkay = NumberToTuple2<500> // ok
type BigT_Bad = NumberToTuple3<500> // ☠

我承认我会认为 NumberToTuple1 会在 NumberToTuple2 之前崩溃,但我认为这并不改变它们是否在使用尾递归检测。
(此外,你通过将类型参数命名为 Number 而使 Number 接口变得模糊不清。我建议使用 NT,甚至可以使用 NumTuple,除非你有非常充分的理由让 X extends Number 意味着不同于它通常的意思)
Playground链接

ruyhziif

ruyhziif2#

这真的是个bug吗?
从某种意义上说,如果有人可以并且愿意修复它,我不会阻止他们。但仅此而已。

ldxq2e6h

ldxq2e6h3#

@jcalz 感谢你的评论,我已经将 Number 更名了 - 你说得对,这个变量名不太好。此外,我也同意你的观点,尾递归优化在这两种情况下都在应用,只是方式不同:NumberToTuple2 在 999 以内运行良好,而未优化的递归在大约 45 处失败。另一方面,NumberToTuple1 可以运行到 3153。我同意我们可以将其视为一种技巧,而不是一个错误。

@RyanCavanaugh 感谢你查看!不确定是否有什么可以修复的地方,但确保两种类型的最大限制相同(可能是 999?)

有趣的一点是,增加更多嵌套层次会使最大限制恢复到 999

type NumberToTuple3<Num extends number, Tuple extends 0[] = []> = 0 extends 1 ? never : 0 extends 1 ? never :
  Tuple['length'] extends Num ? Tuple : NumberToTuple2<Num, [...Tuple, 0]>;

type StillWorking = NumberToTuple3<999>
type AlreadyAnError = NumberToTuple3<1000>
yacmzcpb

yacmzcpb4#

有任何结论吗?

v64noz0r

v64noz0r5#

我遇到了类似的问题,并对编译器进行了调查。在这里,我将我找到的内容留给那些可能想知道发生了什么的人。

我正在寻找绕过递归深度限制的技巧,最终我来到了这个神奇的类型:

type Magic<T> = T

用这种类型 Package 任何尾递归条件类型,都可以让它绕过迭代限制(1000)。

type NumberToTuple3<Num extends number, Tuple extends 0[] = []> = 
  Magic<Tuple['length'] extends Num ? Tuple : NumberToTuple3<Num, [...Tuple, 0]>>;

// It's okay to duplicate `Magic`

type NumberToTuple4<Num extends number, Tuple extends 0[] = []> = 
  Magic<Magic<Tuple['length'] extends Num ? Tuple : NumberToTuple3<Num, [...Tuple, 0]>>>;

令我惊讶的是,我查看了编译器,发现 canTailRecurse 函数在 checker.ts 中。它用于检查给定的类型是否可以进行尾递归优化。更新尾递归计数器只有一个地方:

if (newRoot.aliasSymbol) {
    tailCount++;
}

这个条件语句留下了以下注解:
注意,只有通过别名条件类型才能进行递归,所以我们只对这些类型增加尾递归计数器。
作者似乎希望每个递归条件类型都有 aliasSymbol 。但不知何故,总有一些例外。我在下面的示例中检查了这一点,并发现一些递归条件类型(包括用 Magic Package 的那些)在其表示中没有 aliasSymbol

type Magic<T> = T
type NTuple<N extends number, T, R extends unknown[] = []> = Magic<R['length'] extends N ? R : NTuple<N, T, [T, ...R]>>
type Inc<N extends number> = [0, ...NTuple<N, 0>]['length']

type Test = Inc<1003>

我不知道 aliasSymbol 如何构建和维护,但我认为它是导致这个问题的原因。
P.S. 这个错误似乎从 TCO 对递归条件类型的开始就存在了( #45711 )

相关问题