写点什么

React 源码中的 dom-diff

  • 2022-10-24
    浙江
  • 本文字数:14705 字

    阅读完需:约 48 分钟

这一章就来讲讲React在协调阶段的beginWork里面主要做的事情 -- dom diff


本文主要讲的是React17.0.2版本的diff,在此我也画了一个简单的流程图:


reconcileChildren

dom diff的入口函数就是reconcileChildren,那么他的源码如下:


//packages/react-reconciler/src/ReactFiberBeginWork.old.jsexport function reconcileChildren(  current: Fiber | null,//当前的fiber节点  workInProgress: Fiber,// 新生成的fiber  nextChildren: any,//  新生成的reactElement内容  renderLanes: Lanes,//渲染优先级) {  if (current === null) {    // 如果没有已经渲染的fiber树,则直接把reactElement内容渲染上去    // If this is a fresh new component that hasn't been rendered yet, we    // won't update its child set by applying minimal side-effects. Instead,    // we will add them all to the child before it gets rendered. That means    // we can optimize this reconciliation pass by not tracking side-effects.    workInProgress.child = mountChildFibers(      workInProgress,      null,      nextChildren,      renderLanes,    );  } else {    // If the current child is the same as the work in progress, it means that    // we haven't yet started any work on these children. Therefore, we use    // the clone algorithm to create a copy of all the current children.
// If we had any progressed work already, that is invalid at this point so // let's throw it out. workInProgress.child = reconcileChildFibers( workInProgress, current.child, nextChildren, renderLanes, ); }}
复制代码


reconcileChildren的源码并不长,主要做了两件事


  • 如果是首次渲染,则会把已经处理好的fiber树进行挂载。

  • 如果不是首次渲染则调用reconcileChildFibers进行下一步处理。


我们关注一下mountChildFibersreconcileChildFibers,我们发现这两个函数分别指向ChildReconciler,只是mountChildFibers的参数为falsereconcileChildFibers的参数为true。我们在这里先埋下一个点,看看这个参数对后期的流程有什么影响。



我们继续深入可以发现,ChildReconciler这个函数冰的执行返回了reconcileChildFibers,所以这便是reconcileChildren的核心功能代码所在了。


reconcileChildFibers

 function reconcileChildFibers(    returnFiber: Fiber,    currentFirstChild: Fiber | null,    newChild: any,    lanes: Lanes,  ): Fiber | null {    // This function is not recursive.    // If the top level item is an array, we treat it as a set of children,    // not as a fragment. Nested arrays on the other hand will be treated as    // fragment nodes. Recursion happens at the normal flow.
// Handle top level unkeyed fragments as if they were arrays. // This leads to an ambiguity between <>{[...]}</> and <>...</>. // We treat the ambiguous cases above the same. const isUnkeyedTopLevelFragment = typeof newChild === 'object' && newChild !== null && newChild.type === REACT_FRAGMENT_TYPE && newChild.key === null; if (isUnkeyedTopLevelFragment) { newChild = newChild.props.children; }
// Handle object types const isObject = typeof newChild === 'object' && newChild !== null;
// 处理对象类型 if (isObject) { switch (newChild.$$typeof) { // REACT_ELEMENT_TYPE类型 case REACT_ELEMENT_TYPE: return placeSingleChild( reconcileSingleElement( returnFiber, currentFirstChild, newChild, lanes, ), ); // REACT_PORTAL_TYPE类型 case REACT_PORTAL_TYPE: return placeSingleChild( reconcileSinglePortal( returnFiber, currentFirstChild, newChild, lanes, ), ); // REACT_LAZY_TYPE类型 case REACT_LAZY_TYPE: if (enableLazyElements) { const payload = newChild._payload; const init = newChild._init; // TODO: This function is supposed to be non-recursive. return reconcileChildFibers( returnFiber, currentFirstChild, init(payload), lanes, ); } } }
// 字符串与数字类型 if (typeof newChild === 'string' || typeof newChild === 'number') { return placeSingleChild( reconcileSingleTextNode( returnFiber, currentFirstChild, '' + newChild, lanes, ), ); } // 数组类型 if (isArray(newChild)) { return reconcileChildrenArray( returnFiber, currentFirstChild, newChild, lanes, ); }
// 可迭代的类型 if (getIteratorFn(newChild)) { return reconcileChildrenIterator( returnFiber, currentFirstChild, newChild, lanes, ); }
if (isObject) { throwOnInvalidObjectType(returnFiber, newChild); }
if (__DEV__) { if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); } } if (typeof newChild === 'undefined' && !isUnkeyedTopLevelFragment) { // If the new child is undefined, and the return fiber is a composite // component, throw an error. If Fiber return types are disabled, // we already threw above. switch (returnFiber.tag) { case ClassComponent: { if (__DEV__) { const instance = returnFiber.stateNode; if (instance.render._isMockFunction) { // We allow auto-mocks to proceed as if they're returning null. break; } } } // Intentionally fall through to the next case, which handles both // functions and classes // eslint-disable-next-lined no-fallthrough case Block: case FunctionComponent: case ForwardRef: case SimpleMemoComponent: { invariant( false, '%s(...): Nothing was returned from render. This usually means a ' + 'return statement is missing. Or, to render nothing, ' + 'return null.', getComponentName(returnFiber.type) || 'Component', ); } } }
// Remaining cases are all treated as empty. return deleteRemainingChildren(returnFiber, currentFirstChild); }
复制代码


reconcileChildFibers中我们根据入参newChild的类型分别对应着不同的处理:



  • 当修改的内容为REACT_ELEMENT_TYPE类型,调用reconcileSingleElement函数。

  • 当修改的内容为REACT_PORTAL_TYPE类型,调用reconcileSinglePortal函数。

  • 当修改的内容为REACT_LAZY_TYPE类型,递归调用reconcileChildFibers函数。

  • 当修改的内容问纯文本类型,调用reconcileSingleTextNode函数。

  • 当修改的内容为数组类型,调用reconcileChildrenArray函数。

  • 当修改的内容为可迭代类型,调用reconcileChildrenIterator函数

  • 参考 React 实战视频讲解:进入学习

reconcileSingleElement

reconcileSingleElement的源码如下:


  function reconcileSingleElement(    returnFiber: Fiber,// 父级    currentFirstChild: Fiber | null, // 父级下diff的第一个    element: ReactElement, // 当前元素    lanes: Lanes, // 优先级  ): Fiber {    const key = element.key;    let child = currentFirstChild;    while (child !== null) {      // TODO: If key === null and child.key === null, then this only applies to      // the first item in the list.      if (child.key === key) {        switch (child.tag) {          // 如果为Fragment类型,并且key也相等          case Fragment: {            if (element.type === REACT_FRAGMENT_TYPE) {
// get后面的兄弟节点添加Deletion标记,用于dom删除 deleteRemainingChildren(returnFiber, child.sibling);
// 通过useFiber复用旧fiber与新的props const existing = useFiber(child, element.props.children); existing.return = returnFiber; if (__DEV__) { existing._debugSource = element._source; existing._debugOwner = element._owner; } return existing; } break; } case Block: if (enableBlocksAPI) { let type = element.type; if (type.$$typeof === REACT_LAZY_TYPE) { type = resolveLazyType(type); } if (type.$$typeof === REACT_BLOCK_TYPE) { // The new Block might not be initialized yet. We need to initialize // it in case initializing it turns out it would match. if ( ((type: any): BlockComponent<any, any>)._render === (child.type: BlockComponent<any, any>)._render ) { deleteRemainingChildren(returnFiber, child.sibling); const existing = useFiber(child, element.props); existing.type = type; existing.return = returnFiber; if (__DEV__) { existing._debugSource = element._source; existing._debugOwner = element._owner; } return existing; } } } // We intentionally fallthrough here if enableBlocksAPI is not on. // eslint-disable-next-lined no-fallthrough default: { if ( // 新的ReactElement与旧的current fiber 的key 与 type都相同 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); existing.return = returnFiber; if (__DEV__) { existing._debugSource = element._source; existing._debugOwner = element._owner; } return existing; } break; } } // 匹配不上,key相等,type不相等,移除旧的fiber以及后面的兄弟 deleteRemainingChildren(returnFiber, child); break; }

else


{ // 如果key不同,则标记Deletion, deleteChild(returnFiber, child); } // 遍历其兄弟 child = child.sibling; }
if (element.type === REACT_FRAGMENT_TYPE) { // 如果是fragment类型,创建fragment,并返回。 const created = createFiberFromFragment( element.props.children, returnFiber.mode, lanes, element.key, ); created.return = returnFiber; return created; } else { //如果不是fragment,创建element并返回fiber const created = createFiberFromElement(element, returnFiber.mode, lanes); created.ref = coerceRef(returnFiber, currentFirstChild, element); created.return = returnFiber; return created; } }
复制代码


根据源码,reconcileSingleElement函数中会遍历当前父级fiber下面的所有子fiber,根据旧的fiber与新生成的ReactElement的keytype进行比较:


  • 如果旧的fiber子节点与新的子节点的keytype不一致,给当前的旧的fiber子节点添加上Deletion标记,继续遍历其兄弟节点。

  • 如果旧的fiber子节点与新的子节点的key是一致的,就会根据当前的节点类型去做匹配处理,通过deleteRemainingChildren给当前子节点以及后面的所有的兄弟节点添加上Deletion标记,并且通过useFiber复用该子节点和该子节点新的props

  • 如果旧的fiber子节点与新的子节点的类型匹配不上,则会直接给旧的fiber子节点打上Deletion标记,移除子节点以及后面的所有兄弟节点。

  • 如果旧的fiber树遍历完毕,但是发现还没有匹配完的节点,那么会通过createFiberFromFragmentcreateFiberFromElement创建新的fiber节点,并指向父级fiber


reconcileSingPortal

 function reconcileSinglePortal(    returnFiber: Fiber,    currentFirstChild: Fiber | null,    portal: ReactPortal,    lanes: Lanes,  ): Fiber {    const key = portal.key;    let child = currentFirstChild;    while (child !== null) {      // TODO: If key === null and child.key === null, then this only applies to      // the first item in the list.      if (child.key === key) {        if (          child.tag === HostPortal &&          child.stateNode.containerInfo === portal.containerInfo &&          child.stateNode.implementation === portal.implementation        ) {          deleteRemainingChildren(returnFiber, child.sibling);          const existing = useFiber(child, portal.children || []);          existing.return = returnFiber;          return existing;        } else {          deleteRemainingChildren(returnFiber, child);          break;        }      } else {        deleteChild(returnFiber, child);      }      child = child.sibling;    }
const created = createFiberFromPortal(portal, returnFiber.mode, lanes); created.return = returnFiber; return created; }
复制代码


有了上面REACT_ELEMENT_TYPE的讲解,对于REACT_PORTAL_TYPE的源码就有一定的思路了,如果还不知道ReactPortal的作用

placeSingleChild

上述的不管是REACT_ELEMENT_TYPEREACT_PORTAL_TYPEREACT_LAZY_TYPE都是用了placeSingleChild包裹起来的,我们来看一看他做了什么事情。


  function placeSingleChild(newFiber: Fiber): Fiber {    // This is simpler for the single child case. We only need to do a    // placement for inserting new children.    if (shouldTrackSideEffects && newFiber.alternate === null) {      newFiber.flags = Placement;    }    return newFiber;  }
复制代码


那么这里我们就发现了这个shouldTrackSideEffects,还记得我们在前面讲的ChildReconciler函数的入参吗?他只是一个布尔。在挂载阶段shouldTrackSideEffects:false,直接是return newFiber。不必要的标记增加性能开销。而在更新阶段,就必须要做这样的操作。Placement为 dom 更新时的插入标记。

reconcileSingleTextNode

reconcileSingleTextNode的源码如下:


  function reconcileSingleTextNode(    returnFiber: Fiber,    currentFirstChild: Fiber | null,    textContent: string,    lanes: Lanes,  ): Fiber {    // There's no need to check for keys on text nodes since we don't have a    // way to define them.    //第一个子节点为文本类型    if (currentFirstChild !== null && currentFirstChild.tag === HostText) {      // We already have an existing node so let's just update it and delete      // the rest.      deleteRemainingChildren(returnFiber, currentFirstChild.sibling);      const existing = useFiber(currentFirstChild, textContent);      existing.return = returnFiber;      return existing;    }    // The existing first child is not a text node so we need to create one    // and delete the existing ones.    //非文本类型打上标记,创建新的文本类型节点    deleteRemainingChildren(returnFiber, currentFirstChild);    const created = createFiberFromText(textContent, returnFiber.mode, lanes);    created.return = returnFiber;//指向父级    return created;  }
复制代码


  • 如果当前fiber的第一个子节点的类型为文本类型,那么其所有的兄弟节点添加Deletion标记,通过useFiber复用当前fiber的子节点和textContent,并指向父级fiber

  • 如果不为文本类型,那么给旧的节点添加Deletion标记,通过createFiberFromText创建新的文本类型节点,并指向父级fiber


reconcileChildrenArray

上面的情况为一对一或者多对一的情况,那么如果是一对多或者多对多的情况就要用 reconcileChildrenArray 来处理了。


  function reconcileChildrenArray(    returnFiber: Fiber,    currentFirstChild: Fiber | null,    newChildren: Array<*>,    lanes: Lanes,  ): Fiber | null {    // This algorithm can't optimize by searching from both ends since we    // don't have backpointers on fibers. I'm trying to see how far we can get    // with that model. If it ends up not being worth the tradeoffs, we can    // add it later.
// Even with a two ended optimization, we'd want to optimize for the case // where there are few changes and brute force the comparison instead of // going for the Map. It'd like to explore hitting that path first in // forward-only mode and only go for the Map once we notice that we need // lots of look ahead. This doesn't handle reversal as well as two ended // search but that's unusual. Besides, for the two ended optimization to // work on Iterables, we'd need to copy the whole set.
// In this first iteration, we'll just live with hitting the bad case // (adding everything to a Map) in for every insert/move.
// If you change this code, also update reconcileChildrenIterator() which // uses the same algorithm.
// 验证key是否合法 if (__DEV__) { // First, validate keys. let knownKeys = null; for (let i = 0; i < newChildren.length; i++) { const child = newChildren[i]; knownKeys = warnOnInvalidKey(child, knownKeys, returnFiber); } }
// 要返回的第一个子fiber节点 let resultingFirstChild: Fiber | null = null; let previousNewFiber: Fiber | null = null;
let oldFiber = currentFirstChild; let lastPlacedIndex = 0; let newIdx = 0; let nextOldFiber = null; // 处理更新情况 // 根据 oldFiber 的 index 和 newChildren 的下标,找到要对比更新的 oldFiber for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) { if (oldFiber.index > newIdx) { nextOldFiber = oldFiber; oldFiber = null; } else { nextOldFiber = oldFiber.sibling; } // 通过updateSlot来diff老的和新的子fiber节点,生成新的fiber const newFiber = updateSlot( returnFiber, oldFiber, newChildren[newIdx], lanes, ); // 如果为null则说明不可复用,退出第一轮循环 if (newFiber === null) { // TODO: This breaks on empty slots like null children. That's // unfortunate because it triggers the slow path all the time. We need // a better way to communicate whether this was a miss or null, // boolean, undefined, etc. 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); } } // 记录老的fiber的下标,并打上PlaceMent标记 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); if (previousNewFiber === null) { // TODO: Move out of the loop. This only happens for the first run. // 如果当前节点的上一个节点是null,则表示当前节点为第一个节点,要返回出去 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. // 如果newChildren遍历完了,则需要删除后面的所有旧的fiber,打上Deletion标记 deleteRemainingChildren(returnFiber, oldFiber); return resultingFirstChild; }
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. // 如果旧的遍历完了,新的还有那么这都是新增的,通过createChild创建新的节点 for (; newIdx < newChildren.length; newIdx++) { const newFiber = createChild(returnFiber, newChildren[newIdx], lanes); if (newFiber === null) { continue; } // 处理移动的情况,给移动的节点加上新增标记,插入到fiber链表树当中 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); if (previousNewFiber === null) { // TODO: Move out of the loop. This only happens for the first run. resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } return resultingFirstChild; }
// Add all children to a key map for quick lookups. // 如果新的老的都没有遍历完毕,则需要处理成一个map,老的key作为key,新的value作为value const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// Keep scanning and use the map to restore deleted items as moves. // 遍历剩下的newChildren for (; newIdx < newChildren.length; newIdx++) { // 找到mapRemainingChildren中key相等的fiber,复用fiber节点并更新props 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. // 如果当前的心得节点的指针为null,则需要删除老的节点 existingChildren.delete( newFiber.key === null ? newIdx : newFiber.key, ); } } // 处理移动dom情况,记录index并打上PlaceMent标记 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 将新创建的fiber插入到fiber链表树当中 if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } }
if (shouldTrackSideEffects) { // Any existing children that weren't consumed above were deleted. We need // to add them to the deletion list. //删除掉剩余的fiber节点 existingChildren.forEach(child => deleteChild(returnFiber, child)); }
return resultingFirstChild; }
复制代码


既然是多对多的这样的一个更新场景,那么就会出现节点的增加、减少、移动等情况,因为大部分的实际场景中,节点更新的情况,往往比增加、减少多得多,所以 React 优先处理了更新的情况。对比的对象为旧的 fiber 和 newChildren。


首先先对newChildren进行遍历,将当前的 oldFiber 与 当前 newIdx 下标的 newChild 通过 updateSlot 进行 diff。

updateSlot

  function updateSlot(    returnFiber: Fiber,    oldFiber: Fiber | null,    newChild: any,    lanes: Lanes,  ): Fiber | null {    // Update the fiber if the keys match, otherwise return null.
const key = oldFiber !== null ? oldFiber.key : null;
// 如果是纯文本 if (typeof newChild === 'string' || typeof newChild === 'number') { // Text nodes don't have keys. If the previous node is implicitly keyed // we can continue to replace it without aborting even if it is not a text // node. if (key !== null) { return null; } return updateTextNode(returnFiber, oldFiber, '' + newChild, lanes); } // 如果是对象 if (typeof newChild === 'object' && newChild !== null) { switch (newChild.$$typeof) { case REACT_ELEMENT_TYPE: { if (newChild.key === key) { if (newChild.type === REACT_FRAGMENT_TYPE) { return updateFragment( returnFiber, oldFiber, newChild.props.children, lanes, key, ); } return updateElement(returnFiber, oldFiber, newChild, lanes); } else { return null; } } case REACT_PORTAL_TYPE: { if (newChild.key === key) { return updatePortal(returnFiber, oldFiber, newChild, lanes); } else { return null; } } case REACT_LAZY_TYPE: { if (enableLazyElements) { const payload = newChild._payload; const init = newChild._init; return updateSlot(returnFiber, oldFiber, init(payload), lanes); } } } // 如果是数组或者可迭代的 if (isArray(newChild) || getIteratorFn(newChild)) { if (key !== null) { return null; }
return updateFragment(returnFiber, oldFiber, newChild, lanes, null); }
throwOnInvalidObjectType(returnFiber, newChild); }
if (__DEV__) { if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); } }
return null; }
复制代码


可见updateSlot函数处理与上面的单节点处理类似:


  • oldFibernewChildren[newIdx]keytype相同,则说明是可以复用的,根据oldFibernewChildprops生成新的fiber,通过 placeChild 给新生成的fiber打上 Placement 副作用标记,同时新 fiber 与之前遍历生成的新 fiber 构建链表树关系。然后继续执行遍历,对下一个oldFiber和下一个newIdx下标的newFiber继续执行diff

  • oldFibernewChildren[newIdx]keytype不相同,说明不可复用,返回 null,直接跳出遍历。



  • 第一轮遍历结束后,可能会执行以下几种情况:

  • newChildren遍历完了,那剩下的oldFiber都是待删除的,通过 deleteRemainingChildren 对剩下的oldFiber打上Deletion副作用标记。

  • oldFiber遍历完了,那剩下的newChildren都是需要新增的,遍历剩下的newChildren,通过 createChild 创建新的fiberplaceChild 给新生成的fiber打上 Placement 副作用标记并添加到fiber链表树中。

  • oldFibernewChildren都未遍历完,通过 mapRemainingChildren 创建一个以剩下的 oldFiberkeykey``oldFibervaluemap。然后对剩下的newChildren进行遍历,通过 updateFromMapmap中寻找具有相同key创建新的fiber(若找到则基于 oldFiber 和 newChild 的 props 创建,否则直接基于 newChild 创建),则从map中删除当前的key,然后placeChild 给新生成的 fiber打上 Placement 副作用标记并添加到fiber链表树中。遍历完之后则existingChildren还剩下 oldFiber的话,则都是待删除的 fiber,deleteChild 对其打上 Deletion 副作用标记。

updateFromMap

  function updateFromMap(    existingChildren: Map<string | number, Fiber>,    returnFiber: Fiber,    newIdx: number,    newChild: any,    lanes: Lanes,  ): Fiber | null {    if (typeof newChild === 'string' || typeof newChild === 'number') {      // Text nodes don't have keys, so we neither have to check the old nor      // new node for the key. If both are text nodes, they match.      const matchedFiber = existingChildren.get(newIdx) || null;      return updateTextNode(returnFiber, matchedFiber, '' + newChild, lanes);    }
if (typeof newChild === 'object' && newChild !== null) { switch (newChild.$$typeof) { case REACT_ELEMENT_TYPE: { const matchedFiber = existingChildren.get( newChild.key === null ? newIdx : newChild.key, ) || null; if (newChild.type === REACT_FRAGMENT_TYPE) { return updateFragment( returnFiber, matchedFiber, newChild.props.children, lanes, newChild.key, ); } return updateElement(returnFiber, matchedFiber, newChild, lanes); } case REACT_PORTAL_TYPE: { const matchedFiber = existingChildren.get( newChild.key === null ? newIdx : newChild.key, ) || null; return updatePortal(returnFiber, matchedFiber, newChild, lanes); } case REACT_LAZY_TYPE: if (enableLazyElements) { const payload = newChild._payload; const init = newChild._init; return updateFromMap( existingChildren, returnFiber, newIdx, init(payload), lanes, ); } }
if (isArray(newChild) || getIteratorFn(newChild)) { const matchedFiber = existingChildren.get(newIdx) || null; return updateFragment(returnFiber, matchedFiber, newChild, lanes, null); }
throwOnInvalidObjectType(returnFiber, newChild); }
if (__DEV__) { if (typeof newChild === 'function') { warnOnFunctionType(returnFiber); } }
return null; }
复制代码


updateFromMap与上面的函数逻辑类似,不再复述,reconcileChildrenArray的流程如下。


React 的 diff 策略

  • 传统的 diff 算法的时间复杂度为O(n³),是因为这种算法是以一棵树的一个节点对比另一棵树的所有节点的,这里为O(n²),之后还需要再处理一次新生成的dom树,故而O(n³)是这么算出来的。

  • 现代的 diff 算法的时间复杂度为 O(n),他是怎么算出来的呢?原来它采用的是,深度优先同层比较。就拿现在的MVVM框架来说吧,借助了vdom这样的一个概念,同层比较在于比较同一层的节点元素,不会出现不同层之间比较的情况。



上图为普通的两棵树,用来阐述什么叫同层级比较。


  • react中的diff策略,则表现为tree diffcomponent diffelement diff

  • tree diff:如果把上图的dom树当做是current FiberworkInProgress Fiber,那么从左到右的操作将会是

  • C节点下面删除G节点。

  • A节点下面创建W节点。

  • E节点下面删除J节点。

  • F下面创建J节点。

  • component diff:组件之间的比较,只会比较他们的类型,如果上图左边的B节点的类型为div,右边的B节点类型为p,那么表示此节点不可复用,则进行的操作如下

  • C节点下面删除G节点。

  • A节点下面创建W节点。

  • root下面创建B节点。

  • B节点下面创建E节点。

  • E节点下面创建I节点。

  • E节点下面删除J节点。

  • B几点下面创建F节点。

  • F节点下面创建J节点。

  • 删除老的B节点。

  • element diff:元素之间的比较分为移动删除新增,如果是下面的这样的例子,他将会进行这些操作。

  • 删除A节点。

  • 移动E节点到C节点之后。

  • 创建J节点插入到D节点之后。

  • 删除F节点。


总结

这一章讲述了,reactdiff过程,也学习了reactdiff策略,经过上述的处理之后就会走到completeUnitWork,在这个过程中我们会根据新生成的fiber树去创建dom元素,根据其上的副作用flagseffectLists链表去做副作用的处理,在commit阶段的commitMutationEffects函数中进行真实dom的插入处理,下一章将讲述真实dom的生成


用户头像

还未添加个人签名 2022-09-05 加入

还未添加个人简介

评论

发布
暂无评论
React源码中的dom-diff_React_夏天的味道123_InfoQ写作社区