typescript - 在 typescript 中递归转换对象树的所有叶子

Question

给定一个简单的对象树，它要么包含其自身类型的值，要么包含需要转换的类型的值:

interface Tree<Leaf> {
  [key: string]: Tree<Leaf> | Leaf;
}

我想定义一个函数，将所有叶子递归地转换为另一种类型，如下所示:

function transformTree<S, T>(
  obj: Tree<S>,
  transform: (value: S) => T,
  isLeaf: (value: S | Tree<S>) => boolean
): Tree<T> {
  return Object.assign(
    {},
    ...Object.entries(obj).map(([key, value]) => ({
      [key]: isLeaf(value)
        ? transform(value as S)
        : transformTree(value as Tree<S>, transform, isLeaf),
    }))
  );
}

如何维护源树和转换树之间的叶子类型？

测试上述不起作用:

class Wrapper<T> {
  constructor(public value: T) {}
}

function transform<T>(wrapped: Wrapper<T>): T {
  return wrapped.value;
}

function unwrap<T>(wrapped: Tree<Wrapper<T>>): Tree<T> {
  return transformTree<Wrapper<T>, T>(
    wrapped,
    transform,
    (value: Wrapper<T> | Tree<Wrapper<T>>) => value instanceof Wrapper
  );
}

const obj = unwrap<string>({
  foo: {
    bar: new Wrapper("baz"),
  },
  cow: new Wrapper("moo"),
});

function handleBaz(value: "baz") {
  return true;
}

function handleMoo(value: "moo") {
  return true;
}

handleBaz(obj.foo.bar); // Error:(162, 19) TS2339: Property 'bar' does not exist on type 'string | Tree<string>'. Property 'bar' does not exist on type 'string'.
handleMoo(obj.cow); //Error:(163, 11) TS2345: Argument of type 'string | Tree<string>' is not assignable to parameter of type '"moo"'. Type 'string' is not assignable to type '"moo"'.

我可以看到错误发生了，因为树结构不是通过转换来维护的(转换只在运行时起作用)。但是鉴于输入树的已知结构，转换是可预测的，我觉得应该有一种方法可以在 typescript 中做到这一点。

这是我解决这个问题的尝试:

type TransformTree<Leaf, InputTree extends Tree<Leaf>, T> = {
  [K in keyof InputTree]: InputTree[K] extends Leaf
    ? T
    : InputTree[K] extends Tree<Leaf>
    ? TransformTree<Leaf, InputTree[K], T>
    : never;
};

type IsLeaf<Leaf> = (value: Tree<Leaf> | Leaf) => boolean;

function transformTree<T extends Tree<From>, From, To>(
  tree: T,
  transform: (value: From) => To,
  isLeaf: IsLeaf<From>
): TransformTree<From, typeof tree, To> {
  return Object.assign(
    {},
    ...Object.entries(tree).map(([key, value]) => ({
      // XXX have to cast the value in each case, because typescript cannot predict
      // the outcome of isLeaf().
      [key]: isLeaf(value)
        ? transform(value as Extract<typeof tree[typeof key], From>)
        : transformTree(
            value as Extract<typeof tree[typeof key], Tree<From>>,
            transform,
            isLeaf
          ),
    }))
  );
}

它似乎仍然不理解嵌套类型:

function unwrap<T>(
  wrapped: Tree<Wrapper<T>>
): TransformTree<Wrapper<T>, typeof wrapped, T> {
  return transformTree(
    wrapped,
    transform,
    (value: Wrapper<T> | Tree<Wrapper<T>>) => value instanceof Wrapper
  );
}


function handleBaz(value: "baz") {
  return true;
}

function handleMoo(value: "moo") {
  return true;
}

handleMoo(obj.cow); // OK

handleBaz(obj.foo.bar); // TS2339: Property 'bar' does not exist on type 'never'.

Playground Link

似乎 typescript 仍然认为如果字段值不是叶子，那么它可能不是子树。

Answer 1

在接下来的内容中，我只会担心打字而不是实现。所有函数将只是 declare d，好像实际的实现在一些 JS 库中，这些是它们的 declaration files .

另外，您的 isLeaf函数应该输入为 user-defined type guards其返回类型是类型谓词，而不仅仅是 boolean .函数签名 isLeaf: (value: S | Tree<S>) => value is S类似于返回 boolean ，除了编译器实际上会在 if (isLeaf(x)) { x } else { x } 中理解, x在真正的 block 中将是 S和 x在错误 block 中将是 Tree<S> .

好的，这里开始:

类型Tree<X>过于笼统，无法跟踪特定的键和值类型。所有编译器都知道该类型的值，例如 Tree<string> , 是它是一个对象类型，其属性是 string 类型之一或 Tree<string> .一旦你这样做，说，这个:

const x: Tree<string> = { a: "", b: { c: "", d: { e: "" } } };

你已经抛弃了关于​​特定结构的所有细节以及关于 string 的任何特定子类型的所有细节。在叶子:

x.a.toUpperCase(); // error
x.z; // no error 

如果您所关心的只是想出一个类型转换来保持嵌套键结构并转换 Tree<X> 的某些子类型变成 Tree<Y> 的子类型同样的形状，你可以做到。但在最直接的实现中，结果树的所有叶子都是 Y 类型。而不是更窄的类型。我是这样写的:

type TransformTree<T extends Tree<X>, X, Y> = { [K in keyof T]:
    T[K] extends X ? Y :
    T[K] extends Tree<X> ? TransformTree<T[K], X, Y> :
    T[K];
};
declare function transformTree<X, Y, TX extends Tree<X>>(
    obj: TX,
    transform: (value: X) => Y,
    isLeaf: (value: X | Tree<X>) => value is X
): TransformTree<TX, X, Y>;

你可以看到它在这样一个简单的例子中工作:

const t1 = { a: "A", b: { c: "CC", d: { e: "EEE" } } };
const t2 = transformTree(t1,
    (x: string) => x.length,
    (v): v is string => typeof v === "string"
); 
t2.a; // number
t2.b.c; // number
t2.b.d.e; // number

但是你想要一些更加雄心勃勃的东西；似乎您不仅希望获得来自特定类型的叶变换图 X到特定类型 Y ，但您想指定一些通用类型函数，如 type F<T extends X> = ...并从类型 Z extends X 映射叶子至 F<Z> .

在您的示例中，您的输入类型类似于 Wrapped<any> , 你的输出类型函数看起来像 type F<T extends Wrapped<any> = T["value"];
不幸的是，这种更通用的转换类型无法在 TypeScript 中表达。你不能有像 type TransformType<T extends Tree<X>, X, F> = ... 这样的类型函数在哪里 F本身就是一个带参数的类型函数。这将要求该语言支持所谓的“高级类型”。在 microsoft/TypeScript#1213 上有一个长期开放的功能请求。 ，虽然拥有它们会很棒，但在可预见的将来似乎不会发生。

您可以做的是设想特定类型的叶类型转换并实现 TransformTree 的特定版本。为他们。例如，如果您的叶类型映射只是索引到单个属性，如 type F<T extends Record<K, any>, K extends PropertyKey> = T[K] ，如您的 Unwrap情况下，那么你可以这样写:

type TransformTreeIdx<T, X, K extends keyof X> = { [P in keyof T]:
    T[P] extends X ? X[K] :
    TransformTreeIdx<T[P], X, K>;
};
declare function transformTreeIdx<TX, X, K extends keyof X>(
    obj: TX,
    key: K,
    isLeaf: (value: any) => value is X
): TransformTreeIdx<TX, X, K>;

然后使用它:

const w = {
    foo: {
        bar: new Wrapper("baz" as const),
    },
    cow: new Wrapper("moo" as const),
};

const w2 = transformTreeIdx(
    w, "value", (x: any): x is Wrapper<any> => x instanceof Wrapper
);

handleBaz(w2.foo.bar);
handleMoo(w2.cow);

或者，正如您在评论中提到的，您可能希望对特定的通用接口(interface)/类做相反的事情，例如 Wrapper ...映射是转换 Z extends X进入 Wrapper<Z> :

type TransformTreeWrap<T, X> = { [P in keyof T]:
    T[P] extends X ? Wrapper<T[P]> :
    TransformTreeWrap<T[P], X>;
};
declare function transformTreeWrap<TX, X, K extends keyof X>(
    obj: TX,
    isLeaf: (value: any) => value is X
): TransformTreeWrap<TX, X>;

并使用它:

const u = {
    foo: {
        bar: "baz" as const,
    },
    cow: "moo" as const,
};

const u2 = transformTreeWrap(
    u, (x: any): x is string => typeof x === "string"
);
handleBaz(u2.foo.bar.value);
handleMoo(u2.cow.value);

或者，您可能有一个数组 isLeaf/ transform允许每个节点针对不同的更具体的转换进行测试的对。因此，例如，任何时候您发现 "moo"输出树中的值 number并且任何时候您找到 "baz"输出树中的值 boolean .

然后你的打字可能看起来像:

type TransformTreeMap<T, M extends [any, any]> = { [K in keyof T]:
    T[K] extends M[0] ? Extract<M, [T[K], any]>[1] :
    TransformTreeMap<T[K], M> };

type IsLeafAndTransformer<I, O> = {
    isLeaf: (x: any) => x is I,
    transform: (x: I) => O
}
type TransformArrayToMap<M extends Array<IsLeafAndTransformer<any, any>>> = {
    [K in keyof M]: M[K] extends IsLeafAndTransformer<infer I, infer O> ?
    [I, O] : never }[number]

declare function transformTreeMap<T, M extends Array<IsLeafAndTransformer<any, any>>>(
    obj: T,
    ...transformers: M
): TransformTreeMap<T, TransformArrayToMap<M>>;

你使用它:

const mm = transformTreeMap(u,
    { isLeaf: (x: any): x is "moo" => x === "moo", transform: (x: "moo") => 123 },
    { isLeaf: (x: any): x is "baz" => x === "baz", transform: (x: "baz") => true }
);
mm.cow // number
mm.foo.bar // boolean

因此，您可以定义许多不同甚至非常强大的树转换......只是不是问题所暗示的完全通用的高阶类型。希望其中一个能给你一条前进的道路。好的，祝你好运!

Playground link to code