React Diff 算法初探

emm会用react，咱都知道react用virtual dom的形式解耦了视图层级和代码的交互操作。
既然托管了view层次的生成，react必然得提供高效的视图生成，不然如果组件之间的转换卡顿严重一定是所有人都受不了的。所以呢，在渲染html方面，react整了个diff算法，提升了html重新渲染的速度。
废话不多说这里先推荐两篇文章，后面写的东西基本都是对于这两篇文章的思路(图片资源也是这里扒下来的= =)。
1：从零开始实现一个React（三）：diff算法
2：React 源码剖析系列－不可思议的 react diff
首先咱声明以及明确以下几点。
1：react的diff算法对于新旧两颗dom树只会对同一层级的节点进行比较，如果类型不同，旧的节点将会直接删除重建即使是有跨层级移动的节点(节点内容相同，但是新的节点深度和旧节点深度不同)，也是直接删了重建，而不会进行节点移动。
2：新旧两颗树在进行比较之后并不会直接去更新旧树，而是生成一个个patch，然后执行方法根据patch去更新旧树。(在推荐的第一篇文章中由于并没有两颗virtual dom树，用的virtual dom直接和html节点比较，所以它是是直接更新了旧树)。
3：由于react的virtual dom有多种形式，原生的html element标签，自定义的component，字符串，实际上的dom比较还是比较繁琐的，为了简化代码理解，所以这里在后面的代码中默认都是同类型的标签数组。

这里定义简单一个TreeNode

export type ReactNode = {
  tag: string;
  attrs: null | object;
  children: ReactNode[] | string[];
};

然后写diff方法，这里由于咱默认没有string类型以及component类型的节点，所以我们只需要比较当新节点的tag类型和旧节点的tag类型是否一致。不一样的就删了重新建立。

const diffNode = (preNode: ReactNode, currentNode: ReactNode) => {
  
  const preNodeT = preNode as ReactNode;
  const curNode = currentNode as ReactNode;
  // tag类型不同时直接销毁原node，创建新node。
  if (!preNode || preNodeT.tag.toLowerCase() !== curNode.tag.toLowerCase()) {
    if (preNodeT) {
      preNode = {
        tag: curNode.tag,
        attrs: curNode.attrs,
        children: curNode.children
      };
    }
  }

  if (
    (preNodeT.children && preNodeT.children.length > 0) ||
    (curNode.children && curNode.children.length > 0)
  ) {
//关键方法是这个。
    diffChildren(preNodeT, curNode.children);
  }
};

关键的在同级比较以及同级节点交换的地方，我相信搜索过diff并且看过一些diff的文章的人都熟悉这么一张同级比较的图。
diff
如果用上述说的不同则删除的说法来处理同级比较的话，react diff算法就没啥好讲了，事实上，在同级计算中用key作为element的唯一标识符，在新旧node的key相同的一些情况下可以直接移动节点而不用删除再创建节点。




const diffChildren =  (preChildren: ReactNode[], currentChildren: ReactNode[]) => {

  const preKeyArray:string[] = preChildren.map(node => {
    return node.attrs['key'];
  });
  const currentKeyArray:string[] = currentChildren.map(node => {
    return node.attrs['key'];
  });

  if (currentChildren && currentChildren.length > 0) {
    //  lastIndex 作为旧树中已经比较过的节点最右的位置
    let lastIndex = 0;
    // 遍历新树，preIndex 就是作为旧树的地址下标。
    let preIndex = 0;
    currentChildren.forEach((currentNode,currentIndex) => {
        const currentKey = currentNode["key"];
        // 新树的key同时存在于旧树
        if (preKeyArray.includes(currentKey)) {
          const preIndex = preKeyArray.indexOf(currentKey)
          // 仅当当前旧树中的节点位置比lastIndex小的时候需要移动节点
          // 因为这意味着这个节点的新位置将会破坏旧位置的顺序，所以需要进行移动
          if (preIndex < lastIndex) {
            // moveChild(preIndex,currentIndex)
            preChildren[currentIndex] = preChildren[preIndex];
          }
          lastIndex = Math.max(preIndex, lastIndex);
        }
        // 新树的key不存在旧树的时候
        else{
          // 旧树同位置节点存在则删除旧节点并且创建节点
          // 否则直接创建节点
          if (preChildren[currentIndex]) {
            lastIndex = Math.max(currentIndex, lastIndex);
            // removeChild(preChildren[currentIndex])
            preChildren[currentIndex] = undefined;
          }
          // createChild(currentNode,preIndex);
          preChildren[currentIndex] = currentNode;
        }
        diffNode(preChildren[preIndex],currentChildren[currentIndex])
        preIndex++;
    });

    preChildren.forEach((item,index)=>{
      if (!currentKeyArray.includes(item.attrs['key'])) {
        preChildren[index]=undefined;
        // removeChild(item)
      }
    });
  }
};

基本的diff大概就是这样了，这里用了两个测试用例。分别是：旧树key为1234，新树key为2143，以及旧树key为1234，新树key为214，结果如下所示
test case1
test case2
但说实话要完全实现的话还是比较复杂的，要比对是否为react element还是component，要对attribute就行比较，节点删除又专门的unMount方法，但是咱也不可能真就复制一份react代码呗。而且现在react开始使用fiber结构(就是说这个方法过时了= =)，上面文章2的代码都得去react之前的release去找了…
但是(震声)！咱也不是白看的diff啊，咱至少知道了key有啥用不是。
写代码要是细一点，就该把所有的位置有可能变化的列表数据都给他添上唯一性ID，即使后台给的数据，我们也可以在获得数据的同时自己给他加一个不变的唯一性id，不加的话，这可都是新建以及销毁的开销是吧。