虚拟DOM+diff算法解读

为何采用虚拟DOM

尤雨溪曾在知乎正面的回答这个问题：

1. 为函数式的 UI 编程方式打开了大门；
2. 可以渲染到 DOM 以外的 backend，比如 ReactNative。

针对这两点谈谈自己的理解：

1. 为函数式的 UI 编程方式打开了大门；

   • 虚拟DOM是由react引入的概念，react的核心理念就是函数式编程，类似ui = f (a)，其中a是数据，函数f则是react的render，每个a的改动，都会重新生成新的ui。
   • 每次生成新的ui就需要重新刷新页面代价太过昂贵，虚拟DOM以及diff算法的引入可以最大限度的复用旧的DOM，使得渲染性能大幅提升。

2. 可以渲染到 DOM 以外的 backend，比如 ReactNative。

   • 有了虚拟DOM就可以轻松实现跨平台，多平台的core都相同，只是在render到具体平台的时候采取不同的render就好了

真实DOM的操作

diff算法最后的结果还是要落到对真实DOM的操作上去，这种操作有三种：新增、删除、移位。这三种操作都需要获取自身DOM和parentDOM，以vue的源码来解释：

• 新增、移位操作可以通过如下实现

export function removeChild (node: Node, child: Node) {
  node.removeChild(child)
}

export function appendChild (node: Node, child: Node) {
  node.appendChild(child)
}

• 移位操作则通过insert实现

export function insertBefore (parentNode: Node, newNode: Node, referenceNode: Node) {
  parentNode.insertBefore(newNode, referenceNode)
}

diff算法

diff算法我认为包括三部分：虚拟DOM树的遍历、parent节点下的children的比较、diff完成之后对真实DOM的操作时机

虚拟DOM的遍历：

虚拟DOM说到底只是一颗树形结构，对于树的遍历我们知道有深度遍历和广度遍历

深度遍历需要栈结构，可以通过递归（内核维护调用栈）的方式实现，也可以采用人为构造栈，然后循环栈完成深度遍历。通常深度优先搜索法不全部保留结点，扩展完的结点从栈中弹出删去，这样，在栈中存储的结点数就是深度值，因此它占用空间较少。

广度遍历则采用队列的方式实现，由于广度优先是按照树的层级来遍历的，在遍历某层的时候需要将下一层的数据推进队列里面，所以队列的长度通常会比树的宽度还要宽。

目前，不管是vue还是react，采用的都是深度遍历算法

vue2.0

vue的渲染主要分三部分：

• 虚拟树的遍历
• 子节点的diff
• 真实DOM的更新

虚拟树的遍历：
采用递归的先序深度遍历算法

子节点的diff：
对于相同的节点，继续比较子节点：

• 同一级子元素新老虚拟DOM列表分别设置startIndex和endIndex，并交叉判断startIndex和endIndex是否是相同元素
• 对比的结果有三种情况：新增、删除、移位
• 新增：老的startIndex不动，新的startIndex移位，并在老的startIndex元素前插入
• 移位：
  • 新startIndex和老startIndex或者新endIndex和老endIndex相同，只要移动startIndex或者endIndex就可以了；
  • 新startIndex和老endIndex相同，新startIndex++，老endIndex--，将老endIndex的ele插入到老startIndex的ele前面
  • 新endIndex和老startIndex相同，新endIndex--，老startIndex++，将老的startIndex的ele插入到老endIndex的ele的后面
  • 新startIndex的key匹配到老的vnode的key，将老vnode的ele插入到老startIndex的ele前面，还有一个操作：将老vnode标记位undefined，（oldCh[idxInOld] = undefined），
• 删除
  • 等新startIndex和新endIndex合拢，老startIndex和老endIndex之间的非undefined的vnode的ele全部删除，undefined的node代表已经处理过了（移位）

真实DOM的更新

• 由于采用递归的方式处理vnode，所以节点更新真实DOM的时机是该节点下所有子节点更新完毕后才会更新，即从下而上
• 节点的props的处理是早于子节点的diff，所以props的更新是从上而下

vue2.0思维导图

react16

react的渲染虽然采用深度遍历，但是是非递归方式，而是采用链表的方式，这样做的原因是方便fiber的引入

react的渲染可以分为两个部分：

• reconciliation 阶段
• commit 阶段

reconciliation 阶段:

react树的reconciliation

所谓的reconciliation阶段就是虚拟DOM的diff阶段，由于采用了递归的链表结构，所以每个节点必然经历两次的遍历，这两次的遍历分别为：beginWork和completeUnitOfWork。

• beginWork：完成对子节点的diff过程（新增，删除，移位），并给相应的vnode打上effectTag，返回第一个子节点。

通过唯一 key 可以判断新老集合中是否存在相同的节点，if (prevChild === nextChild)，如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较，if (child._mountIndex < lastIndex)，则进行节点移动操作，否则不执行该操作。这是一种顺序优化手段，lastIndex 一直在更新，表示访问过的节点在老集合中最右的位置（即最大的位置），如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作。

• completeUnitOfWork：完成对当前节点的副作用的收集（主要的props的改动），并将所有需要改动的节点串成一个链表effect-list，挂到hostRoot节点上，返回兄弟节点或者是父节点。

reconciliation阶段的最终结果是产生一个effect-list列表，这个effect-list列表里面的节点的两个属性标明接下来的commit阶段需要对该节点进行的处理：effectTag以及updateQueue，effectTag表明对节点位置的改动，updateQueue表明对节点状态的改动

commit 阶段
commit阶段主要是循环effect-list来对节点分别处理，并且对effect-list进行了三次循环

• 第一遍：执行所有的（effectTag & Snapshot）为true的节点的commitBeforeMutationLifeCycles，即执行周期函数getSnapshotBeforeUpdate

• 第二遍：为所有（effectTag & (Placement | Update | Deletion)）即移位、更新、删除的节点进行commitPlacement以及commitWork，commitPlacement做的就是移位和删除的动作，commitWork则将节点的updateQueue拿出来更新

• 第三遍：为所有的（effectTag & (Update | Callback)）的节点进行commitLifeCycles，即执行周期函数componentDidUpdate

react16思维导图

fiber节点参考：

const fiber = {
  // Instance
  tag = tag; // fiber 的类型。 
    - IndeterminateComponent
    - FunctionalComponent
    - ClassComponent // Menu, Table
    - HostRoot // ReactDOM.render 的第二个参数
    - HostPortal
    - HostComponent // div, span
    - HostText // 纯文本节点，即 dom  的 nodeName 等于 '#text'
    - CallComponent // 对应 call return 中的 call
    - CallHandlerPhase // call 中的 handler 阶段
    - ReturnComponent // 对应 call return 中的 return
    - Fragment 
    - Mode // AsyncMode || StrictMode
    - ContextConsumer
    - ContextProvider
    - ForwardRef
  key = key; // fiber 的唯一标识
  type = null; // 与 react element 里的 type 一致
  stateNode = null; // 对应组件或者 dom 的实例

  // Fiber
  return = null; // 等价于栈帧中的函数调用后的返回地址，这里即是父 fiber
  child = null; // 即组件的 render 的返回值，是一个单链表（因为返回值不一定是一个单一的元素）
  sibling = null; // 单链表
  index = 0;

  ref = null;

  // props 等价于一个函数的 arguments
  pendingProps = pendingProps; // 新的 props（要么是当前的 props，要么是 wip 的 props），默认就等于 element.props，对于 Fragment 和 Portal，则等于 props.children
  memoizedProps = null; // 旧的 props，等于 wipFiber.pendingProps 或者 wipFiber.pendingProps.children
    - 一般 oldProps = workInProgress.memoizedProps
    - 一般 newProps = workInProgress.pendingProps
  updateQueue = null; // 状态更新和回调的函数队列
  memoizedState = null; // 组件实例的 state

  mode = mode; // 用于描述处理 fiber 和它的子树的方式，创建后就不应被改变，如未指定则从父 fiber 继承。NoContext || AsyncMode || StrictMode

  // Effects
  effectTag = NoEffect; // 当需要变化的时候，具体需要进行的操作的类型
    - NoEffect // 初始值
    - PerformedWork // 开始处理后置为 PerformedWork
    - Placement // 插入，保持原位，移动 dom 节点
    - Update // 对 dom 结构的改变。mount 或者 update 后置为 Update
    - PlacementAndUpdate
    - Deletion
    - ContentReset // 将一个只包含字符串的 dom 节点，或者 textarea，或者 dangerouslySetInnerHTML 替换成其它类型的节点
    - Callback // setState 的回调
    - DidCapture // 渲染出错，准备捕获出错信息
    - Ref // 准备执行 ref 回调
    - ErrLog // 渲染出错，执行 componentDidCatch
    - Snapshot // getSnapshotBeforeUpdate
    - HostEffectMask // 暂时没用
    - Incomplete // 任何造成 fiber 的工作无法完成的情况
    - ShouldCapture //  需要处理错误
    
  nextEffect = null; // 下一个需要处理的有副作用的 fiber

  // 本 fiber 的子树中有副作用的第一个和最后一个 fiber
  firstEffect = null; // 
  lastEffect = null; //

  expirationTime = NoWork; // 将来的某个时间点，在那之前必须完成所有工作

  alternate = null; // WIP 树里面的 fiber，如果不在更新期间，那么就等于当前的 fiber，如果是新创建的节点，那么就没有 alternate
  
  // dev mode
  _debugID; // 自增的标识每一个 fiber 的 id
  _debugSource = null; // 文件名和行数，与 React Element 的 source 一致
  _debugOwner = null; // 与 React Element 的 owner 一致
  _debugIsCurrentlyTiming = false;
}