typescript - 从平面配置推断嵌套递归类型

Question

我正在尝试正确输入将树状结构的平面配置转换为树状结构本身的函数的返回值，例如:

转动这个

{
  key1: { property: "value1" },
  key2: { property: "value2" },
  key3: { property: "value3", parentKey: "key2"},
  key4: { property: "value4", parentKey: "key3" }
}

进入

{
  key1: { property: "value1", ... },
  key2: {
    property: "value2",
    key3: {
      property: "value3", ...,
      key4: { property: "value4", ... }
    }
  }
}

以一种捕获键名称的方式，而不仅仅是允许嵌套字符串索引(具有可能不存在的键)。

我试图从输入配置(上面的第一个代码片段)开始，但没有太多运气让 Typescript 正确推断它们的键联合类型，同时将“parentKey”限制为可用值，例如:

type Config<T extends string> = Record<T, Properties & { parentKey?: T }>;

不起作用，因为 Typescript 将 T 缩小为仅在parentKey 中指定的值的并集。不将parentKey绑定(bind)到其他键(例如将其指定为string而不是T)使TS将T推断为所有键的并集，但允许将不存在的值作为父项。

---

尝试执行此类操作的原因是将一些默认属性值/行为嵌入到树的每个节点中，而无需重复手动指定它们。

---

感谢任何关于这是否可以表达的指示，如果可以，那么如何处理它。另外，也许有一种更好的形式来表示配置和生成的树，这将允许更好的推理，同时仍然允许对每个节点进行一些扩充 - 很高兴看到任何其他想法。

Answer 1

我只会考虑类型级转换，而不是有关类型推断或任何类型的实现的问题。我的目标是编写一个实用程序类型 toTree<T>这样给定一个“平面”数据结构，例如

type Flat = {
  key1: { property: "value1" },
  key2: { property: "value2" },
  key3: { property: "value3", parentKey: "key2" },
  key4: { property: "value4", parentKey: "key3" }
};

转换后的类型 ToTree<Flat>就是对应的树结构:

type Tree = ToTree<Flat>;
/* type Tree = {
    key1: { property: "value1"; };
    key2: {
        property: "value2";
        key3: {
            property: "value3";
            key4: { property: "value4"; };
        };
    };
 */

这必然是 recursive conditional type ，往往有有趣的边缘情况。如果递归条件类型的边缘情况行为不理想，有时需要进行大量重构来解决它。所以请注意。

---

我的方法是这样的。首先，我要编写一个中间实用程序类型 ToTreeInner<T>假设 T 中的每个属性有一个parentKey属性可以是键或 undefined 。所以而不是 { key1: { property: "value1" }} ，需要{ key1: { property: "value1", parentKey: undefined }} 。这使得实现起来更加简单，因为我们总是可以捕获 parentKey属性，而不必每次都编写处理丢失键的逻辑。那么如果我们有ToTreeInner ，我们可以写 ToTree像这样:

type ToTree<T extends Record<keyof T, {
  parentKey?: PropertyKey, [k: string]: any
}>> = ToTreeInner<{ [K in keyof T]: T[K] & (
  "parentKey" extends keyof T[K] ? unknown : { parentKey: undefined }
) }>;

这允许 T 的每个属性可选拥有 parentKey属性(并且我添加了一个包罗万象的 index signature 以免遇到 weak type detection )。然后添加 undefined值为 parentKey任何不具有此类属性的属性，然后将其传递给 ToTreeInner .

现在让我们实现 ToTreeInner :

type ToTreeInner<
  T extends Record<keyof T, { parentKey: PropertyKey | undefined }>,
  P extends PropertyKey | undefined = undefined
> = { [K in keyof T as P extends T[K]["parentKey"] ? K : never]:
    (Omit<T[K], "parentKey"> & ToTreeInner<T, K>) extends
    infer O ? { [K in keyof O]: O[K] } : never
  };

此类型函数采用两个类型参数。类型T是全扁平结构，而P是输出树中当前节点的父键的名称。这可以是 undefined如果我们在树的根部，那么 defaults至undefined因此您可以省略该类型参数来获取完整的树。

然后我们有一个key-remapped type { [K in keyof T as P extends T[K]["parentKey"] ? K : never]: ⋯ }它使用 as子句来过滤键。输出对象只有一个键 K如果P extends T[K]["parentKey"] ，这意味着它只有一个 key K如果 T 中对应的属性有一个parentKey的P .

以及键 K 处的值本质上是 Omit<T[K], "parentKey"> & ToTreeInner<T, K> 。我们使用 Omit utility type剥离 parentKey property out(因为我们不希望输出具有 parentKey 属性)。而我们intersect递归调用 ToTreeInner<T, K> ，这意味着我们还将在此处添加一棵新树，以当前键 K 为根。 .

这基本上就是整个事情，但如果你直接使用它并显示输出类型，你会得到嵌套 Omit 的一团糟。 s 和交叉点和 DeepTreeInner类型。所以我使用 How can I see the full expanded contract of a Typescript type? 中描述的技巧将类型扩展为单个属性类型。而不是PossiblyUglyType ，我写PossiblyUglyType extends infer O ? { [K in keyof O]: O[K] } : never ，它“复制”PossiblyUglyType到一个新的类型参数 O ，然后遍历 O 的属性而不修改它们。这本质上或多或少是一个大的无操作，但它会影响显示。

---

那么让我们尝试一下:

type Tree = ToTree<Flat>;
/* type Tree = {
    key1: { property: "value1"; };
    key2: {
        property: "value2";
        key3: {
            property: "value3";
            key4: { property: "value4"; };
        };
    };
 */

看起来不错。让我们尝试一下其他方法:

type Test = ToTree<{
  a: { b: string, c: number },
  d: { e: boolean, parentKey: "a" },
  f: { g: Date, parentKey: "a" },
  h: { i: any, parentKey: "d" }
}>
/* type Test = {
    a: {
        b: string;
        c: number;
        d: {
            e: boolean;
            h: {
                i: any;
            };
        };
        f: {
            g: Date;
        };
    };
} */

看起来也不错!

Playground link to code