React中的神奇算法：提升组件树更新效率的秘密

这篇文章介绍了React中的diff算法的实现原理。它涵盖了单节点diff和多节点diff两种情况。单节点diff主要是通过比较key和type来判断是否复用已有的fiber节点，如果无法复用，则创建新的fiber节点。多节点diff则处理更新、新增和删除的情况，通过遍历比较新旧节点来确定复用或创建新节点，并处理节点的移动。关键方法包括updateSlot和placeChild。通过这些算法，React能够高效地更新组件树.

Prerequisite

• 下面都以 FC 为例子进行说明
• react中的diff算法的本质: 根据 current fiber 和 新的ReactElement , 生成新fiber的过程

• 新的ReactElement: renderWithHooks中调用Component返回的ReactElement
• 新fiber: 根据新的ReactElement创建的fiber 或者 通过useFiber进行复用的fiber

1. 复用fiber指的是复用 current fiber 以及 对应的真实DOM节点

• ReactElement通过索引进行访问,而current fiber则通过fiber.sibling.

• react中fiber节点可复用的条件: key 和 type(元素类型) 相同

• key: 暗示哪些子元素在不同的render下能保持稳定.
• type: fiber.elementType === element.type

• react中diff算法开始于reconciler阶段中的reconcileChildFibers, 根据 新的reactElement(nextChild) 的类型判断走何种 diff算法

• 单节点diff：newChild类型为 object、number、string
• 多节点diff: newChild类型为 array

// 根据newChild类型选择不同diff函数处理
function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
): Fiber | null {
  const isObject = typeof newChild === 'object' && newChild !== null;
  if (isObject) {
    // object类型，可能是 REACT_ELEMENT_TYPE 或 REACT_PORTAL_TYPE
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE`:`
        // 调用 reconcileSingleElement 处理
      // // ...省略其他case
    }
  }
  if (typeof newChild === 'string' || typeof newChild === 'number') {
    // 调用 reconcileSingleTextNode 处理
    // ...省略
  }
  if (isArray(newChild)) {
    // 调用 reconcileChildrenArray 处理
    // ...省略
  }
  // 以上都没有命中，删除节点
  return deleteRemainingChildren(returnFiber, currentFirstChild);
}

单节点diff(reconcileSingleElement)

• 单节点diff 其实很简单 就是 ReactElement在同级的current fiber中找可复用fiber的过程,如果找不到就创建新的fiber. 其核心源码如下,请根据注释阅读.

• 注意下面的代码忽略了 处理 React.Lazy以及React.Fragment

  // element: new ReactElement
  // currentFirstChild: retureFiber的第一个子fiber
	function reconcileSingleElement(returnFiber, currentFirstChild, element, lanes) {
    // 获取 element 的 key
    var key = element.key;
    var child = currentFirstChild;
  	// 遍历同级的 current fiber
    while (child !== null) {
    	// 复用条件1: key相同
      if (child.key === key) {
        var elementType = element.type;
        // 复用条件2: type相同
          if (child.elementType === elementType) {
            // 删除同级剩余的fiber节点
            deleteRemainingChildren(returnFiber, child.sibling);
            // 复用当前的fiber节点
            var _existing = useFiber(child, element.props);
            _existing.ref = coerceRef(returnFiber, child, element);
            _existing.return = returnFiber;
            // _existing 进入 beginWork
            return _existing;
          }
        } 
        // 如果 key相同,type不同.则直接删除所有的同级fiber节点.说明没有可复用的fiber节点，直接跳出循环
        deleteRemainingChildren(returnFiber, child);
        break;
      } else {
        // key如果不相同,直接将当前fiber标记为删除
        deleteChild(returnFiber, child);
      }
    	// 继续看下一个兄弟能不能复用
      child = child.sibling;
    }
    
  	// 代码走到这里说明,没有找到可以复用的fiber节点. 
    // 则根据 ReactElement创建新的fiber节点并返回
    var _created4 = createFiberFromElement(element, returnFiber.mode, lanes);
    return _created4;
  }

多节点diff (reconcileChildrenArray)

• 多节点diff可以分为下面主要分下面3个阶段

• 处理更新的情况
• 处理新增和删除的情况

1. 新增: oldFiber已经遍历完, 但是newChild还没, 说明newChild剩下的节点都是新增节点.
2. 删除: newChild已经遍历完, 但是oldFiber还没, 说明oldFiber剩下的节点都需要删除.

• 处理移动的情况

  // 多节点 diff 算法
  // currentFirstChild: current fiber tree 上 以 returnFiber为父节点的第一个子节点
  // newChildren: 调用 Component 新生成的 children
  function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren, lanes) {
    
    /* 校验 newChildren 中的 key 是否合法 */
    {
      var knownKeys = null;
      for (var i = 0; i < newChildren.length; i++) {
        var child = newChildren[i];
        knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber);
      }
    }   
    
    /* 初始化后续算法所需要的变量 */
    // resultingFirstChild: 记录 WIP fiber tree 上 以 returnFiber为父节点的第一个子节点
    var resultingFirstChild = null;
    // 上一个 挂载到 WIP fiber tree上的fiber节点(用于构建 WIP上子fiber的关系)
    var previousNewFiber = null;
    var oldFiber = currentFirstChild;
    // 最后一个可复用oldFiber的位置索引
    var lastPlacedIndex = 0;
    // 遍历 newChild的索引
    var newIdx = 0;
    // 下一个 fiber节点
    var nextOldFiber = null;
    
  	/* 处理更新的情况 */
    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      //...     
    } 

    /* 处理删除的情况 newChild遍历完 */
    if (newIdx === newChildren.length) {
      //...
      return resultingFirstChild
    }

    /* 处理新增的情况 oldFiber遍历完 */
    if (oldFiber === null) {
      //... 
     return resultingFirstChild
    }

    /* 处理移动的情况 oldFiber和newChild 都没有遍历完 */
    var existingChildren = mapRemainingChildren(returnFiber, oldFiber); 
    for (; newIdx < newChildren.length; newIdx++) {
      //...
    }

    // 如果 newChildren已经遍历完毕, 则删除 existingChildren 中剩余的记录
    if (shouldTrackSideEffects) {
      existingChildren.forEach(function (child) {
        return deleteChild(returnFiber, child);
      });
    }
  	
    // 返回 WIP fiber tree 的第一个子节点, 让其进入到 beginWork
    return resultingFirstChild
  }

• 首先来看处理更新的情况, 其实现其实并不复杂,就是逐个比较 oldFiber以及 newChildren看是否可复用

• 因为 oldFiber是链表 所以其通过 sibling属性进行遍历, 而 newChildren 则通过索引.

for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      // 获取下一个需要处理的oldFiber
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      // 判断 oldFiber 是否可复用,并返回可复用的 fiber
      var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        // 说明 oldFiber不可复用
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        // 因为key不相同,而跳出一层循环.
        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);
        }
      }
      // 使用 newChild 中 newIdx 来更新 newFiber 的 index属性(从而记录了fiber的位置)
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);

      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
    	// previousNewFiber始终指向 WIP tree上新增的fiber节点
      previousNewFiber = newFiber;
      // 继续处理下一个 oldFiber
      oldFiber = nextOldFiber;
    }

• 这里需要重点关注的第一个方法是updateSlot, 该方法的返回值决定了是否跳出第一层循环

1. 由此可以看出如果key不相同,则直接返回null,进而跳出第一层循环.
2. 我也不知道为啥newChild !== object|string|number 🤔️ ?

// Update the fiber if the keys match, otherwise return null.
function updateSlot(returnFiber, oldFiber, newChild, lanes) {
  // 获取 oldFiber上的key
  // 注意 如果 newChild 没有设置key,则其key===null
  var key = oldFiber !== null ? oldFiber.key : null;
  // ...
  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      // 注意 下面只需要关注 newChild为 REACT_ELEMENT_TYPE的情况
      case REACT_ELEMENT_TYPE:
        {
          // 复用条件1: key相同
          if (newChild.key === key) {
            // 继续判断 type是否相同
            return updateElement(returnFiber, oldFiber, newChild, lanes);
          } else {
            // 如果key不相同,则 返回 null
            return null;
          }
        }
      case REACT_PORTAL_TYPE:
    	//... 处理 portal
      case REACT_LAZY_TYPE:
      //... 处理 Lazy
    }
  }
  // newChild 既不是 object|string|number
  return null;
}

1. 当 key相同的时候, 则继续调用updateElement判断type是否相同.

  function updateElement(returnFiber, current, element, lanes) {
    // 获取 newChild的 element's type
    var elementType = element.type;
  	// current存在,则说明是更新的情况
    if (current !== null) {
      // 复用条件2: elementType也相同,则直接复用oldFiber
      if (current.elementType === elementType ) {
        // Move based on index
        var existing = useFiber(current, element.props);
        existing.ref = coerceRef(returnFiber, current, element);
        existing.return = returnFiber;
        // 返回复用的fiber
        return existing;
      }
    }
    // current 不存在 或者 type不相同, 则根据 newChild创建新的fiber节点
    var created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, current, element);
    created.return = returnFiber;
    return created;
  }

• 第二个需要重点关注的是placeChild, 这个方法使用来更新lastPlacedIndex(最后一个可复用oldFiber的位置索引)

1. 注意在useFiber(复用oldFiber)的方法中, 会建立 newFiber和oldFiber的通告 alternate相互引用的关系.

workInProgress.alternate = current;
current.alternate = workInProgress;

1. 还需要明白一点 newChild 每一项位置对应着 WIP fiber tree最终的位置.

  function placeChild(newFiber, lastPlacedIndex, newIndex) {
    // 更新 fiber.index属性
    newFiber.index = newIndex;
    
    var current = newFiber.alternate;
    // 🚀 🚀
    if (current !== null) {
      // current在 currentFiberTree上的位置
      var oldIndex = current.index;
      // 如果小于 lastPlacedIndex,则说明是移动操作
      // 因为 current 在 currentFiberTree上的位置是在lastPlacedIndex的左边
      // 而 newFiber 在lastPlacedIndex的右边
      if (oldIndex < lastPlacedIndex) {
        // This is a move.
        newFiber.flags |= Placement;
        // 相对顺序发生了变化
        return lastPlacedIndex;
      } else {
        // This item can stay in place.
        // oldIndex >= lastPlacedIndex 节点位置不变，并更新最近一个复用节点的位置为 lastPlacedIndex
        // 如果 oldIndex>= lastPlacedIndex,则说明 current 在 currentFiberTree 上的位置是在lastPlacedIndex的右边. 
        // 而 newChild 代表 WIP fiber tree的最终顺序,newFiber也是在current之前,因此其相对顺序是没有改变的.
        return oldIndex;
      }
    } else {
      // This is an insertion.
      newFiber.flags |= Placement;
      return lastPlacedIndex;
    }
  }

• 接下来看删除和新增的情况.

• 首先来看看删除, 其实现也很简单就是当newChildren已经遍历完毕了,说明 current fiber tree 中 剩余的节点都需要进行删除

  
    if (newIdx === newChildren.length) {
      // 删除 current上 未遍历到的oldFiber
      deleteRemainingChildren(returnFiber, oldFiber);
      // 返回 WIP fiber tree 的第一个子节点, 让其进入到 beginWork
      return resultingFirstChild;
    }
  

• 再来看看新增, 同样很简单它和 删除很相似,不过其是当oldFiber遍历完,而newChildren未遍历完. 而未遍历的newChild则需要创建新的fiber节点

// current fiber tree上的节点已经遍历完毕了,说明 newChildren 中剩余的节点都需要进行插入
if (oldFiber === null) {
  // If we don't have any more existing children we can choose a fast path
  // since the rest will all be insertions.
  for (; newIdx < newChildren.length; newIdx++) {
    // 创建新的fiber节点
    var _newFiber = createChild(returnFiber, newChildren[newIdx], lanes);

    if (_newFiber === null) {
      continue;
    }
    // placeChild在这里的作用其实是更新newFiber.index属性
    // 因为在这个使用会命中 新插入的逻辑,其不会更新 lastPlacedIndex
    lastPlacedIndex = placeChild(_newFiber, lastPlacedIndex, newIdx);
    // 下面的逻辑同 第一轮循环中的逻辑
    if (previousNewFiber === null) {
      resultingFirstChild = _newFiber;
    } else {
      previousNewFiber.sibling = _newFiber;
    }

    previousNewFiber = _newFiber;
  }
  // resultingFirstChild: 返回 WIP fiber 
  return resultingFirstChild;
} 

• 最后就是处理节点移动的情况了，这个时候newChildren和oldFiber都没有遍历完. 这里主要涉及到两个重要的方法一个是

• mapRemainingChildren: 这个方法的功能很简单,就是建立一个存储剩余oldFiber的map

1. fiber.key | fiber.index -> fiber

 function mapRemainingChildren(returnFiber, currentFirstChild) {
    // Add the remaining children to a temporary map so that we can find them by
    // keys quickly. Implicit (null) keys get added to this set with their index
    // instead.
    var existingChildren = new Map();
    var existingChild = currentFirstChild;

    while (existingChild !== null) {
      // 存在key,则使用key作为map的键
      if (existingChild.key !== null) {
        existingChildren.set(existingChild.key, existingChild);
      } else {
        // 否则使用 fiber的index
        existingChildren.set(existingChild.index, existingChild);
      }
      existingChild = existingChild.sibling;
    }

    return existingChildren;
  }

• updateFromMap: 这个方法功能也很简单,就是尝试在mapRemainingChildren's map中根据element.key | element.index查找可复用fiber.

1. 这个方法与上述的updateSlot有些相似, 只不过该方法始终会返回一个newFiber,其可能是新创建的也可能是复用的.

  // 从 oldFiber中寻找和 newChild key相同的fiber
  // existingChildren 为 key-> oldFiber 的map
  function updateFromMap(existingChildren, returnFiber, newIdx, newChild, lanes) {
    if (typeof newChild === 'string' || typeof newChild === 'number') {
      // 处理 textNode
      var matchedFiber = existingChildren.get(newIdx) || null;
      return updateTextNode(returnFiber, matchedFiber, '' + newChild, lanes);
    }

    if (typeof newChild === 'object' && newChild !== null) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE:
          {
            // 优先使用 key 来查找,如果没有key,则使用index
            var _matchedFiber = existingChildren.get(newChild.key === null ? newIdx : newChild.key) || null;
            // 如果 _matchedFiber存在,则继续判断 type 是否相同,如果相同则复用_matchedFiber
            // 不存在或者type 不相同,则创建新的fiber
            return updateElement(returnFiber, _matchedFiber, newChild, lanes);
          }

        case REACT_PORTAL_TYPE:
        //...处理 Portal
        case REACT_LAZY_TYPE:
        //...处理 Lazy
      }
    return null;
  }

• ok了解了上述两个方法之后,再看下面这段逻辑就简单了.

    // 走到了这里说明 current fiber tree 和 newChildren 中都还有剩余的节点.
    var existingChildren = mapRemainingChildren(returnFiber, oldFiber); // Keep scanning and use the map to restore deleted items as moves.

    for (; newIdx < newChildren.length; newIdx++) {
      var _newFiber2 = updateFromMap(existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes);

      if (_newFiber2 !== null) {
        if (shouldTrackSideEffects) {
          if (_newFiber2.alternate !== null) {
            // 已经找到了可复用的oldFiber,则删除 map中的记录
            existingChildren.delete(_newFiber2.key === null ? newIdx : _newFiber2.key);
          }
        }
        // 更新 lastPlacedIndex 为最新复用fiber的index
        lastPlacedIndex = placeChild(_newFiber2, lastPlacedIndex, newIdx);
        // 同上
        if (previousNewFiber === null) {
          resultingFirstChild = _newFiber2;
        } else {
          previousNewFiber.sibling = _newFiber2;
        }
        previousNewFiber = _newFiber2;
      }
    }