如何用TypeScript写一棵树

[jiangshanmeta]

export const findNodeFn = ({
  id,
  list,
  parents = [],
  option = {},
}: {
  id: string;
  list: any[];
  parents?: any[];
  option?: {
    childKey?: string;
    idKey?: string;
  };
}) => {
  const { childKey = 'children', idKey = 'nodeId' } = option;

  for (let i = 0; i < list?.length; i += 1) {
    const nodeId = list[i][idKey];
    const children = list[i][childKey];
    const current = [...parents, list[i]];

    if (nodeId === id) {
      return current;
    }

    const result = findNodeFn({ id, list: children, parents: current, option });

    if (result) {
      return result;
    }
  }
};

这段代码的意思是 给一个森林和一个id，找到从根节点到目标节点的路径。实现的思路就是DFS。

为了提高通用性，支持多种树结构，提供了idKey和childKey两个参数，用来配置ID的key以及子节点的key。

比如以下两种树结构：

interface StdTree1 {
  nodeId: string;
  children?: StdTree1[]
}

interface StdTree2 {
  id: string;
  childs?: StdTree2[]
}

这一定程度上导致了描述这个树结构的类型比较难，于是我看到的最初版本就是any。

我们首先要解决的问题就是如何实现 这种自定义字段的树的类型？

这事不是特别困难：

type MakeTree1<Idkey extends string, ChildrenKey extends string> = {
  [K in Idkey]: string;
} & {
  [K in ChildrenKey]?: MakeTree1<Idkey,ChildrenKey>[]
}

这样我们构造StdTree1这种结构，只需要

type GenTree1 = MakeTree1<'nodeId','children'>

这两个类型是相互兼容，我们可以举个例子：

const treeStd1:StdTree1 = {
  nodeId: '1',
  children:[
    {
      nodeId: '2',
    }
  ],
}

const treeGen1:GenTree1 = treeStd1;

const treeGen2:GenTree1 =  {
  nodeId: '1',
  children:[
    {
      nodeId: '2',
    }
  ],
}

const treeStd2:StdTree1 = treeGen2

可以看到两种类型的变量可以互相赋值。

那么问题来了，StdTree1和GenTree1是否相等呢？我们可以试一试

import { Equal, Expect, ExpectFalse, NotEqual } from '@type-challenges/utils'

type cases1 = [
  Expect<Equal<StdTree1,GenTree1>>,
  Expect<NotEqual<StdTree1,GenTree1>>,
]

可以看到这两个类型并不相等。这意味着在ts中类型兼容和类型相等其实是两个不同的概念。我们可以看一眼ts是如何规定相等的：ts spec。两个类型必须同时都是交叉类型，才会进一步判断，我们这里StdTree1和GenTree1一个不是交叉类型，一个是交叉类型，所以并不相等。

有办法能让两个类型相等呢？我们能不能把这种交叉类型转化为非交叉类型？

type Copy<T> = {
  [K in keyof T]:T[K]
}

这样就可以把交叉类型merge到一起。

举个例子：

type Model1 = {
  id:string;
  name:string;
}

type Model2 = {
  id:string;
} & {
  name:string;
}

type cases2 = [
  // Expect<Equal<Model1,Model2>>,
  Expect<NotEqual<Model1,Model2>>,
  Expect<Equal<Model1, Copy<Model2> >>,
]

对于这种递归结构，稍微有点麻烦：

type MakeTreeH<IdKey extends string ,ChildrenKey extends string> = {
  [k in IdKey]:string;
} & {
  [k in ChildrenKey]?:Copy<MakeTreeH<IdKey,ChildrenKey>>[]
}

type MakeTree2<IdKey extends string ,ChildrenKey extends string > = Copy<MakeTreeH<IdKey,ChildrenKey>>

现在我们构造的树就和StdTree1相等了。

再进一步，构造树的时候，显然表示id的字段应该只有一个，表示子节点的字段也应该只有一个，我们现在的MakeTree其实是允许我们传入多个字段的，比如：

type GenTreeWrong1 = MakeTree2<'nodeId' | 'id','children'>

我们能不能限制一下呢？为此我们需要借助一个工具类型 IsUnion

type IsUnion<T,U = T> = T extends U ?
  [U] extends [T]?false:true
  :never

IsUnion的实现我们最后再说，目前只需要知道它能返回bool类型表示是否是联合类型。

type MakeTree3<IdKey extends ,ChildrenKey extends string > = 
  IsUnion<IdKey> extends false?
    IsUnion<ChildrenKey> extends false?
      Copy<MakeTreeH<IdKey,ChildrenKey>>
      : never
    :never

这时传入联合类型就会得到never：

type GenTreeWrong2 = MakeTree3<'nodeId' | 'id','children'> // never

再进一步，目前IdKey和Children可以都传入string，IdKey和ChildrenKey也可能被传入相同的字符串，我们还需要再补充三个判断。

虽说我很想接着MakeTree3写，但是五个判断，缩进有点太感人了，有什么优雅的写法呢？

type MakeTree4<IdKey extends string,ChildrenKey extends string > = 
  [
    IsUnion<IdKey>,
    IsUnion<ChildrenKey>,
    string extends IdKey? true:false,
    string extends ChildrenKey?true:false,
    IdKey extends ChildrenKey?true:false 
  ] extends [false,false,false,false,false ]?
    Copy<MakeTreeH<IdKey,ChildrenKey>>:never

我们可以借助Tuple。

到现在我们已经能构造一棵树了，可以尝试实现findNodeFn了，简化起见，我们的输入是一棵树，返回值是具体的节点而不是路径。

function findNodeFn<IdKey extends string,ChildrenKey extends string,T extends MakeTree4<IdKey,ChildrenKey>>({
  root,
  target,
  options:{
    idKey,
    childrenKey,
  }
}:{
  root:T,
  target:string,
  options:{
    idKey:IdKey,
    childrenKey:ChildrenKey
  }
}):T | null {


}

先把类型签名写出来，然后 我们走了一些弯路，我们这么类型约束并只能保证子节点是一棵有IdKey和ChildrenKey的树，它并不能保证子节点的类型是T，因为T上可能还有其它字段。

我们可以这么约束。

function findNode<IdKey extends string ,ChildrenKey extends string, T extends Partial<Record<ChildrenKey,T[]>> & Record<IdKey,string>   >({
  data,
  options:{
    idKey,
    childrenKey
  },
  target,
}:{
  data:T,
  options:{
    idKey:IdKey,
    childrenKey:ChildrenKey
  },
  target:string,
} ):T | null{
  if(data[idKey] === target){
    return data;
  }
  if(!data[childrenKey]){
    return null;
  }

  for(let i=0;i<data[childrenKey].length;i++){
    const rst = findNode<IdKey,ChildrenKey,T>({
      data:data[childrenKey][i],
      target,
      options:{
        idKey,
        childrenKey
      }
    });
  }

  return null;
}

最后我们讲讲IsUnion。T extends U,如果T是联合类型，比如 string | number，此时将会触发分布式条件类型，T 会被拆分为一个个子类型分别进行后续操作，在这里相当于是：

([string | number] extends [string]? false:true )| ( [string | number] extends [number]?false:true )

这里虽然也是条件类型，但是因为构成了Tuple，属于非分布式条件类型，所以U并不会拆分为子类型进行判断。对于联合类型，每一个分支都是false，所以最终结果是false。对于非联合类型，相当于判断自己是否等于自己。