React Diff 浅析

一、前言

在虚拟 DOM 出现之前，我们通常都进行实际 DOM 操作，包括使用Jquery、kissy 和原生的方式来进行 DOM 和内容的增删改，来达到更新的目的。虚拟 DOM 出现后，数据驱动视图这种思想，慢慢替代了原先 DOM 操作的方式，而我们大多情况要做的往往就是维护数据的状态。

PS：需要的前置知识

• 什么是 V-DOM?
• 什么是 Fiber？
• React 更新流程？

二、正文

什么是 Diff 算法？

让 V-DOM 快起来的根本因素，用于更新虚拟 DOM 的变化部分的执行策略。

Diff 算法的根本

• 传统的 Diff 算法通过循环递归对节点进行依次对比，这么做算法复杂度 O(n^3)；
• React Diff 三大策略可以将原本 O(n^3) 的复杂度降低到 O(n);

以下是三大策略介绍：

1、Tree Diff

** DOM 节点中跨层级的移动操作特别少，几乎可以忽略。**

Tree 级别的 Diff 具体方案：

• 可以通过 UpdateDepth 对 V-DOM 树进行层级控制。
• 对树进行分层比较，两树只进行同一层级节点比较，如节点不存在，则删除该节点及其子节点，不再进一步比较。
• 只需遍历一次就能完成整棵 DOM 树的比较。

2、Component Diff

拥有相同类的两个组件生成相似的树形结构，反之则不同。

Component 级别的 Diff 方案：

• 相同类型组件：按层级比较 V-DOM 树；
• 不同类型组件：一个将被改变的组件判断为 Dirty Component，替换整个组件；

3、Element Diff

在对比同一层级的子节点时，通过唯一 key 区分。

Element 级别的 Diff 方案：

• 插入：集合（A，B）中不存在组件C，组件C若要添加到集合中，组件C只需插入到集合中；
• 删除：
  • 集合（A，B，D）存在组件D，但D发生改变，不能复用和更新，所以集合中但D需要删除，重新创建；
  • 集合（A，B，D）变成了新集合（A，B），组件D删除；
• 移动：集合内组件位置发生变化，只需添加唯一key区分移动即可；

Diff 策略浅析

/**
 * diff算法核心部分
 * @param {*} returnFiber 
 * @param {*} currentFirstChild 
 * @param {*} newChild 判断JSX类型
 * @param {*} lanes 
 * @returns 
 */
function reconcileChildFibers(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChild: any,
    lanes: Lanes,
): Fiber | null {

    ...
    
    // 判断是否对象
    const isObject = typeof newChild === 'object' && newChild !== null;
    
    if (isObject) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          return placeSingleChild(
            reconcileSingleElement(
              returnFiber,
              currentFirstChild,
              newChild,
              lanes,
            ),
          );
        ....
      }
    }
    
    ...
    
    // 数组多节点
    if (isArray(newChild)) {
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }
    
    ...
    
    // 删除没有匹配上的节点
    return deleteRemainingChildren(returnFiber, currentFirstChild);
}

单节点 Diff

单节点的 Diff 实现逻辑较为简单
​

1、主要流程

2、源代码
​

/**
  * 单节点diff逻辑
  * @param {*} returnFiber 
  * @param {*} currentFirstChild 
  * @param {*} element 
  * @param {*} lanes 
  * @returns 
  */
 function reconcileSingleElement(
   returnFiber: Fiber,
   currentFirstChild: Fiber | null,
   element: ReactElement,
   lanes: Lanes,
 ): Fiber {
   const key = element.key;
   let child = currentFirstChild;
   // 判断是否存在dom节点
   while (child !== null) {
     // TODO: If key === null and child.key === null, then this only applies to
     // the first item in the list.
     // 是否存在相同的key
     if (child.key === key) {
       // 类型是否相同
       switch (child.tag) {
         case Fragment: {
           ...
           break;
         }
         case Block:
           
         // We intentionally fallthrough here if enableBlocksAPI is not on.
         // eslint-disable-next-lined no-fallthrough
         default: {
           // 类型相同，可以复用
           if (
             child.elementType === element.type ||
             // Keep this check inline so it only runs on the false path:
             (__DEV__
               ? isCompatibleFamilyForHotReloading(child, element)
               : false)
           ) {
             deleteRemainingChildren(returnFiber, child.sibling);
             const existing = useFiber(child, element.props);
             existing.ref = coerceRef(returnFiber, child, element);
             // 返回复用fiber
             existing.return = returnFiber;
             if (__DEV__) {
               existing._debugSource = element._source;
               existing._debugOwner = element._owner;
             }
             return existing;
           }
           break;
         }
       }
       // key相同，类型不匹配，对应fiber为删除状态
       deleteRemainingChildren(returnFiber, child);
       break;
     } else {
       // key不同fiber标记为删除状态
       deleteChild(returnFiber, child);
     }
     child = child.sibling;
   }

   // 创建新的fragment fiber
   if (element.type === REACT_FRAGMENT_TYPE) {
     const created = createFiberFromFragment(
       element.props.children,
       returnFiber.mode,
       lanes,
       element.key,
     );
     created.return = returnFiber;
     return created;
   } else {
     // 创建新的iber节点
     const created = createFiberFromElement(element, returnFiber.mode, lanes);
     created.ref = coerceRef(returnFiber, currentFirstChild, element);
     created.return = returnFiber;
     return created;
   }
 }

多节点Diff

多节点的 Diff 比之单节点复杂了很多，主要涉及以下四个操作：

• 更新节点
• 新增节点
• 删除节点
• 移动节点

1、主要流程

2、源代码

function reconcileChildrenArray(
    returnFiber: Fiber,
    currentFirstChild: Fiber | null,
    newChildren: Array<*>,
    lanes: Lanes,
  ): Fiber | null {
    // 新fiber链表的第一个fiber
    let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;
    // 和新的child比较
    let oldFiber = currentFirstChild;
    // 存储固定节点位置
    let lastPlacedIndex = 0;
    // 遍历到新节点的索引
    let newIdx = 0;
    // 遍历到oldFiber的下一个节点
    let nextOldFiber = null;
    
    
    
    /******** 第一次遍历  更新节点 ********/ 
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      // newChildren小于oldFiber，中断遍历
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
      // 存储当前遍历到到oldFiber的下一个节点
        nextOldFiber = oldFiber.sibling;
      }
      
      // 更新Fiber
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      // 节点不可复用 key或tag，中断遍历
      if (newFiber === null) {
       
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // We matched the slot, but we didn't reuse the existing fiber, so we
          // need to delete the existing child.
          deleteChild(returnFiber, oldFiber);
        }
      }
      // 记录固定节点位置
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // fiber连接sibling连成sibling位置的，单向链表
      if (previousNewFiber === null) {
        // TODO: Move out of the loop. This only happens for the first run.
        resultingFirstChild = newFiber;
      } else {
        // TODO: Defer siblings if we're not at the right index for this slot.
        // I.e. if we had null values before, then we want to defer this
        // for each null value. However, we also don't want to call updateSlot
        // with the previous one.
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }
    
    
    /******** 删除节点  *********/
    if (newIdx === newChildren.length) {
      // We've reached the end of the new children. We can delete the rest.
      deleteRemainingChildren(returnFiber, oldFiber);
      return resultingFirstChild;
    }
    
    
    /******** 第二次遍历 新增节点  *********/
    if (oldFiber === null) {
      // 在老节点遍历完，还有新节点没遍历的情况，就创建新节点
      for (; newIdx < newChildren.length; newIdx++) {
        // 创建Fiber节点
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          // TODO: Move out of the loop. This only happens for the first run.
          resultingFirstChild = newFiber;
        } else {
          //  sibling链接兄弟节点
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
      return resultingFirstChild;
    }

    // Add all children to a key map for quick lookups.
    const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    
    /******** 第三次遍历 移动节点  **********/
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {
        if (shouldTrackSideEffects) {
          if (newFiber.alternate !== null) {
            // The new fiber is a work in progress, but if there exists a
            // current, that means that we reused the fiber. We need to delete
            // it from the child list so that we don't add it to the deletion
            // list.
            existingChildren.delete(
              newFiber.key === null ? newIdx : newFiber.key,
            );
          }
        }
        // 移动节点
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        if (previousNewFiber === null) {
          resultingFirstChild = newFiber;
        } else {
          previousNewFiber.sibling = newFiber;
        }
        previousNewFiber = newFiber;
      }
    }
   	...

    return resultingFirstChild;
  }

三、小结

• Diff 时 key 和 type 确定了 Fiber 节点能否复用；
• Diff 中的三大策略是 Diff 算法的根本，而 Diff 算法又是 V-DOM 大行其道的主要两大因素之一；

四、推荐

如何编写一个简易的 react： Build your own React