React源码分析之diff核心算法

更新日期: 2023-12-05阅读: 407标签: 源码

前言

react的diff算法是在render的beginWork阶段中进行处理

beginWork是在向下深度遍历fiber树时会对途径的每个节点进行状态处理和进行diff对比

首先diff的入口是在reconcileChildFibers中,然后会根据type来判断使用哪种diff函数进行处理

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  lanes: Lanes,
): Fiber | null {
  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        return placeSingleChild(
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );··
      case REACT_PORTAL_TYPE:
        // ...
      case REACT_LAZY_TYPE:
        //...
    }

    if (isArray(newChild)) {
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    if (getIteratorFn(newChild)) {
      //...
    }
  }
  // ...
}

我在本篇会针对两种较常用的diff函数进行分析

reconcileSingleElement
reconcileChildrenArray


reconcileSingleElement

reconcileSingleElement是针对新newChild是单节点,而oldChild单节点或者是多节点就无法确定了,所以在此diff算法中就会对旧节点进行遍历,然后删除不匹配的oldFiber

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement
  lanes: Lanes,
): Fiber {
  const key = element.key;
  let child = currentFirstChild;
  /**
    * 遍历旧节点,找到与newChild相同key的节点,不匹配的删除
    * 针对匹配的oldFiber, 用newChild中新节点的props来生成新的fiber节点
    */
  while (child !== null) {
    if (child.key === key) {
      const elementType = element.type;
      /**
        * 通过useFiber创建一个新的Fiber
        * 如果element是一个Fragment,则以element.props.children建立Fiber
        * 将returnFiber赋给新的fiber的return字段,然后返回这个新的fiber
        */·
      if (elementType === REACT_FRAGMENT_TYPE) {
        if (child.tag === Fragment) {
          deleteRemainingChildren(returnFiber, child.sibling);
          const existing = useFiber(child, element.props.children);
          existing.return = returnFiber;
          if (__DEV__) {
            existing._debugSource = element._source;
            existing._debugOwner = element._owner;
          }
          return existing;
        }
      } else {
        if (
          child.elementType === elementType ||
          (__DEV__
            ? isCompatibleFamilyForHotReloading(child, element)
            : false) ||
          (typeof elementType === 'object' &&
            elementType !== null &&
            elementType.$$typeof === REACT_LAZY_TYPE &&
            resolveLazy(elementType) === child.type)
        ) {
          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;
        }
      }
      // Didn't match.
      deleteRemainingChildren(returnFiber, child);
      break;
    } else {
      // key不相同就删除
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 如果没有命中一个key,则通过createFiberFormElement或CreateFiberFormFragment创建一个新的fiber,然后返回
  if (element.type === REACT_FRAGMENT_TYPE) {
    const created = createFiberFromFragment(
      element.props.children,
      returnFiber.mode,
      lanes,
      element.key,
    );
    created.return = returnFiber;
    return created;
  } else {
    const created = createFiberFromElement(element, returnFiber.mode, lanes);
    created.ref = coerceRef(returnFiber, currentFirstChild, element);
    created.return = returnFiber;
    return created;
  }
}


reconcileChildrenArray

针对newChild是多节点的情况就需要调用reconcileChildrenArray进行diff操作

多节点会有四种可能性的变化:删除、新增、位移、更新

reconcileChildrenArray针对这四种变化,首先会处理的是更新,当出现无法匹配的情况时,就会根据遍历的情况来判断是否处理删除或者新增,然后最后会根据情况处理位移

因为fiber是单向链表,所以reconcileChildrenArray的遍历不是双端遍历

首先第一轮遍历,是处理节点更新

for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
  // newChildren遍历完了,oldFiber没有遍历完,中断遍历
  if (oldFiber.index > newIdx) {
    nextOldFiber = oldFiber;
    oldFiber = null;
  } else {
    // 记录oldFiber的下一个节点
    nextOldFiber = oldFiber.sibling;
  }
  // 更新节点,如果节点没有匹配上,就会返回null
  const newFiber = updateSlot(
    returnFiber,
    oldFiber,
    newChildren[newIdx],
    lanes,
  );
  // newFiber为null说明节点没有匹配上,中断遍历
  if (newFiber === null) {
    // oldFiber为null说明oldFiber也遍历完了
    if (oldFiber === null) {
      oldFiber = nextOldFiber;
    }
    break;
  }

  /**
   * shouldTrackSideEffects为true表示是更新过程
   * mountChildFibers = ChildReconciler(false);
   * reconcileChildFibers = ChildReconciler(true);
   * ChildReconciler接收的就是shouldTrackSideEffects
   */
  if (shouldTrackSideEffects) {
    if (oldFiber && newFiber.alternate === null) {
      // 新节点没有现有节点,需要删除
      deleteChild(returnFiber, oldFiber);
    }
  }
  // 记录固定节点的位置
  lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);

  // 将新节点拼接成以sibling为指针的单向链表
  if (previousNewFiber === null) {
    resultingFirstChild = newFiber;
  } else {
    previousNewFiber.sibling = newFiber;
  }
  previousNewFiber = newFiber;
  oldFiber = nextOldFiber;
}

遍历完匹配的节点后,就判断新节点是否遍历完,如果遍历完,那么剩余的oldFiber都是要删除的

if (newIdx === newChildren.length) {
  deleteRemainingChildren(returnFiber, oldFiber);
  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  return resultingFirstChild;
}

如果新旧点没有遍历完,就判断旧fiber链是否遍历完,如果遍历完那么剩余的新节点全部作为新fiber插入

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);

    // 将新fiber拼接成以sibling为指针的单向链表
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
  if (getIsHydrating()) {
    const numberOfForks = newIdx;
    pushTreeFork(returnFiber, numberOfForks);
  }
  return resultingFirstChild;
}

执行到这一步,说明新旧节点都没有遍历完,就说明存在有位移的未知序列

// 首先创建一个以oldFiber key为键,值为oldFiber的map
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

for (; newIdx < newChildren.length; newIdx++) {
  // 然后根据map中的oldFiber创建新fiber
  const newFiber = updateFromMap(
    existingChildren,
    returnFiber,
    newIdx,
    newChildren[newIdx],
    lanes,
  );
  if (newFiber !== null) {
    if (shouldTrackSideEffects) {
      if (newFiber.alternate !== null) {
        // 如果newFiber.alternate不为null,说明是根据oldFiber创建的,那么就需要在map中删除oldFiber
        existingChildren.delete(
          newFiber.key === null ? newIdx : newFiber.key,
        );
      }
    }

    // 根据lastPlacedIndex判断是否移动节点
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);

    // 将新fiber拼接成以sibling为指针的单向链表
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
  }
}

if (shouldTrackSideEffects) {
  // 删除剩余的oldFiber
  existingChildren.forEach(child => deleteChild(returnFiber, child));
}

移动节点的核心是在placeChild这个函数中,如果当前正在遍历的节点的oldIndex是在lastPlacedIndex的右边,就说明它的位置没变化,因为旧节点中就处于右边,新节点中也处于右边。

例如:old:A -> B -> C -> D,new:D -> A -> B -> C

遍历到D时,lastPlacedIndex = D的oldIndex = 3

然后遍历到A时,A的oldIndex为0,小于3,说明A在旧序列中肯定不是D的右边,所以A肯定产生了位移

function placeChild(
  newFiber: Fiber,
  lastPlacedIndex: number,
  newIndex: number,
): number {
  newFiber.index = newIndex;
  if (!shouldTrackSideEffects) {
    newFiber.flags |= Forked;
    return lastPlacedIndex;
  }
  const current = newFiber.alternate;
  if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
      // 小于lastPlacedIndex 产生了位移
      newFiber.flags |= Placement | PlacementDEV;
      return lastPlacedIndex;
    } else {
      // 没有位移,返回当前的oldIndex
      return oldIndex;
    }
  } else {
    newFiber.flags |= Placement | PlacementDEV;
    return lastPlacedIndex;
  }
}

总结

针对单节点的diff,会遍历oldFiber链,如果有匹配的fiber,就以匹配的生成新fiber,如果没有就新建一个fiber,然后删除不匹配的fiber

针对多节点diff

  • 首先是从头向尾遍历,针对复用的fiber进行更新,如果无法复用就中断遍历
  • 然后判断新旧节点的遍历情况,来判断是否新增或者删除
  • 如果都没有遍历完,就创建一个mapMap<old key, old Fiber>,然后遍历新节点,基于map来创建新fiber,然后根据lastPlacedIndex来判断是否产生了位移,遍历完最后删除剩余的oldFiber
来自:https://songlh.top/2022/09/04/React源码分析之diff核心算法/

链接: https://www.fly63.com/article/detial/12590

Js中的 forEach 源码

在日常 Coding 中,码农们肯定少不了对数组的操作,其中很常用的一个操作就是对数组进行遍历,查看数组中的元素,然后一顿操作猛如虎。今天暂且简单地说说在 JavaScript 中 forEach。

微信小程序代码源码案例大全

克隆项目代码到本地(git应该都要会哈,现在源码几乎都会放github上,会git才方便,不会的可以自学一下哦,不会的也没关系,gitHub上也提供直接下载的链接);打开微信开发者工具;

Node 集群源码初探

随着这些模块逐渐完善, Nodejs 在服务端的使用场景也越来越丰富,如果你仅仅是因为JS 这个后缀而注意到它的话, 那么我希望你能暂停脚步,好好了解一下这门年轻的语言,相信它会给你带来惊喜

Vue源码之实例方法

在 Vue 内部,有一段这样的代码:上面5个函数的作用是在Vue的原型上面挂载方法。initMixin 函数;可以看到在 initMixin 方法中,实现了一系列的初始化操作,包括生命周期流程以及响应式系统流程的启动

vue源码解析:nextTick

nextTick的使用:vue中dom的更像并不是实时的,当数据改变后,vue会把渲染watcher添加到异步队列,异步执行,同步代码执行完成后再统一修改dom,我们看下面的代码。

React源码解析之ReactDOM.render()

React更新的方式有三种:(1)ReactDOM.render() || hydrate(ReactDOMServer渲染)(2)setState(3)forceUpdate;接下来,我们就来看下ReactDOM.render()源码

React源码解析之ExpirationTime

在React中,为防止某个update因为优先级的原因一直被打断而未能执行。React会设置一个ExpirationTime,当时间到了ExpirationTime的时候,如果某个update还未执行的话,React将会强制执行该update,这就是ExpirationTime的作用。

扒开V8引擎的源码,我找到了你们想要的前端算法

算法对于前端工程师来说总有一层神秘色彩,这篇文章通过解读V8源码,带你探索 Array.prototype.sort 函数下的算法实现。来,先把你用过的和听说过的排序算法都列出来:

jQuery源码之extend的实现

extend是jQuery中一个比较核心的代码,如果有查看jQuery的源码的话,就会发现jQuery在多处调用了extend方法。作用:对任意对象进行扩;’扩展某个实例对象

vuex源码:state及strict属性

state也就是vuex里的值,也即是整个vuex的状态,而strict和state的设置有关,如果设置strict为true,那么不能直接修改state里的值,只能通过mutation来设置

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!