非常慢的递归类型

Question

我使用一个对象来保存应用程序中的所有状态。该对象是任意深度嵌套的，因此我希望能够描述一条仅选择该状态的一部分的路径。

我写了一个递归类型，可以满足我的所有需求：

• 它允许将对象中从顶部（根）节点到对象中每个子属性的任何路径描述为字符串数组
• 它允许在任何级别停止
• 它不允许选择兄弟节点或祖先节点，只能选择子节点
• 如果对象的属性包含一个数组，它允许通过谓词函数或数字索引选择数组条目

这是可行的，但是当使用一个非常简单的状态接口时，递归已经使它变得非常慢。

所以我决定将打字支持的深度限制在某些级别，之后它将回落到“任何”类型：

// Helpers for limiting levels
type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15;
type NextDigit = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 'STOP'];
type Increment<Depth> = Depth extends Digit ? NextDigit[Depth] : 'STOP';

export type PredicateFunction<ArrayType> = (array: ArrayType, index?: number) => boolean;
export type IndexOrPredicateFunction<Type> = number | PredicateFunction<Type>;
export type StatePathKey = IndexOrPredicateFunction<any> | string;

// The type for the path
export type StatePath<Object, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> = Object extends object ?
    (Path |
    // Check if depth > max allowed
    (Depth extends string ?
            // ...if yes, don't typecheck deeper levels and allow everything (for performance reasons)
            [...Path, ...any[]] :
            // ...otherwise check if object is array
            (Object extends readonly any[] ?
                // ...when array only allow index or PredicateFunction
                StatePath<Object[number], [...Path, IndexOrPredicateFunction<Object[number]>], Increment<Depth>>
                // ...when object generate type of all possible keys
                : { [Key in string & keyof Object]: StatePath<Object[Key], [...Path, Key], Increment<Depth>> }[string & keyof Object])))
    : Path;



// Sample State:
export interface State {
    app: {
        testEntry: string;
        testArray: {
            firstname: string,
            lastname: string,
            address?: {
                zip: number;
                street: string;
                doorNumbers: {
                    number: number;
                    appendixes: number[];
                }[]
            }
        }[];
    }
}

// Samples for valid paths (StatePath<State>):
['app', 'testEntry']
['app', 'testArray']
['app', 'testArray', 1, 'firstname']
['app', 'testArray', 5, 'address', 'doorNumbers', doorNumber => doorNumber.number === 1, 'appendixes']
...

这对于小型状态接口来说工作“没问题”（尽管我已经有很长的编译时间），但是对于现实生活中的状态接口来说太慢了。

知道如何改变这种类型以实现相同的效果并获得更好的性能吗？

无限制的递归将是最佳选择，但删除递归并手动循环是可以接受的，例如10 个级别，对于更长的数组，可以回退到“任意”。

Answer 1

当您将generic类型实现为深度嵌套的递归条件类型时，您应该小心处理任意/意外类型参数所发生的情况，并尝试确保没有输入会失败达到你的基本情况，或者导致计算的组合爆炸。 在适用的情况下，尝试输入类型的

{}

、

object

、

unknown

、

null

、

undefined

和 unions。

---

即使您从未计划将此类类型参数传递给您的类型，TypeScript 也可能会在尝试为使用您的类型的事物计算约束时自行计算这些类型。

在你的情况下，如果你有

StatePath<Obj>

，其中

Obj

是通用的，你可以预期 TypeScript 可能会决定用它的约束替换

Obj

，即（隐式）

unknown

。因此，如果

StatePath<unknown>

永远不会达到递归的基本情况，那么您的编译时间可能会很糟糕。

我想说，在你的情况下，你正在检查是否

Obj extends object

，但如果

Obj

本身是

object

或

unknown

，那么看起来TypeScript花费了大量时间向下递归。如果

Obj

很宽，我们可以通过添加一种方法来将其消灭在萌芽状态：

type StatePath<Obj, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> =
    object extends Obj ? Path : ( ⋯ )

其中 ⋯ 是你原来的定义。

---

另一个问题是当输入是事物的大联合时会发生什么。如果您使用任何“分布式条件类型”，则 TypeScript 将为每个联合成员评估一次条件类型。如果这种递归，你最终可能会出现类型的大爆炸，即使联合一开始并没有那么大。 例如，您的

Depth

类型参数可能被指定为

Digit

等事物的联合。你关心支持深度为

0 | 4 | 10

的奇怪案例吗？ 可能不会。理想情况下，你也想在那时退出。因此，您可以放弃分布式条件类型

Depth extends string ? ⋯ : ⋯

并使用非分布式版本

[Depth] extends [string] ? ⋯ : ⋯

。在深度递归类型中使用分布式条件类型的任何地方，您都应该这样做，因为您确实想要处理联合。否则你只是为编译器做更多的工作。

所以现在你有类似的东西

type StatePath<Obj, Path extends (string | IndexOrPredicateFunction<any>)[] = [], Depth = 0> =
    object extends Obj ? Path : (
        Obj extends object ? (Path |
            ([Depth] extends [string] ? ⋯ : (⋯))
        ) : Path
    );

这应该会大大加快计算速度。当然可能还有其他边缘情况，因此您需要进行大量测试并处理任何剩余的问题。

---

Playground 代码链接