React 核心知识点 -- Virtual Dom 与 Diff

[pfan123]

React 核心知识点 -- Virtual Dom 与 Diff

React 最值得称道部分就是 Virtual DOM 和 Diff ，这两块核心点方便我们更好的抽象化的开发组件，提高渲染效率。

Virtual Dom

Virtual DOM 是一种编程概念。在这个概念里， UI 以一种理想化的，或者说“虚拟的 DOM TREE”表现形式被保存于内存中，并通过如 ReactDOM 等类库使之与“真实的” DOM 同步。

Shadow DOM 和 Virtual DOM 不一样。Shadow DOM 是一种浏览器技术，主要用于在 web 组件中封装变量和 CSS。Virtual DOM 则是一种由 Javascript 类库基于浏览器 API 实现的概念。

创建 Virtual Dom

function createElement(tagName, props, ...children) {
  return {
    tagName, 
    props,
    children,
  }
}
// vnode { tagName: 'div', props: { className: 'one' }, children: [{tagName: 'li', props: { className: 'kk', children: [...] }}, children: [{tagName: 'li', props: { className: 'zz', children: ['kkk'] }}] }
const vnode = createElement('div', {className: 'one'}, 
  createElement('li', {className: 'kk'}, 
    createElement('span', {className: 'txt'}, 'kkk'),
    createElement('li', {className: 'zz'}, 'kkk')
  ),
  createElement('li', {className: 'one'}, 'one')
)

JSX 仅仅只是 React.createElement(component, props, ...children) 函数的语法糖，https://reactjs.org/docs/jsx-in-depth.html

React 中此部分 JSX 语法糖，通过 plugin-transform-react-jsx 转换为 React.createElement 函数的语法糖:

Diff 遍历算法

遍历 Tree Dom 结构，涉及常用数据算法： 广度优先搜索(breadth-first search，BFS)，广度优先遍历(breadth-first traversal，BFT)， 深度优先遍历(depth-first traversal，DFT)。笔者这里只讨论：广度优先遍历(breadth-first traversal，BFT)， 深度优先遍历(depth-first traversal，DFT)。

广度优先遍历(breadth-first traversal，BFT)

广度优先遍历（BFT breadth-first traversal）：广度优先遍历是连通图的一种遍历策略，它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。树的广度优先遍历是指优先遍历完某一层的所有节点，然后再依次向下层遍历。

步骤:

• 创建一个队列，并将开始节点放入队列中
• 若队列非空，则从队列中取出第一个节点，并检测它是否为目标节点
• 若是目标节点，则结束搜寻，并返回结果。若不是，则将它所有没有被检测过的字节点都加入队列中
• 若队列为空，表示图中并没有目标节点，则结束遍历

广度优先算法的的非递归实现：

function wideTraversal(vnode) {  
  if(!vnode) {
    throw new Error('Empty Tree')
  }
  const nodeList = []
  const queue = []
  queue.push(vnode)
  while (queue.length !== 0) {  
      const node = queue.shift()
      nodeList.push(node)
      if(node.children){
        const children = node.children
        for (let i = 0; i < children.length; i++)  
            queue.push(children[i])
      }
  }  
  return nodeList
}

深度优先遍历(depth-first traversal，DFT)

深度优先遍历（DFT depth-first traversal）：树的深度优先遍历是指首先遍历树的某个分支上的所有节点，在遍历另一个分支的节点，对于节点中的分支也这样处理。React 中 Dom Diff 采用的深度优先遍历算法，至于React 为何不使用广度优先遍历得到的答案是可能会导致组件的生命周期乱套。

步骤：

• 访问顶点V0
• 依次从V0的未被访问的邻接点出发，对树进行深度优先遍历；直至树中和V0有路径相通的顶点都被访问
• 若此时途中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到所有顶点均被访问过为止

深度优先算法的递归实现：

function deepTraversal(vnode) {  
  if(!vnode) {
    throw new Error('Empty Tree')
  }
  const nodeList = []
  walk(vnode, nodeList)   
  return nodeList 
}  

function walk(vnode, nodeList = []) {
  nodeList.push(vnode)
  if(vnode.children){
    const children = vnode.children
    children.forEach(node => {
      walk(node, nodeList)   
    })
  }
}

深度优先算法的非递归实现：

function deepTraversal(vnode) {  
  if(!vnode) {
    throw new Error('Empty Tree')
  }
  const nodeList = []
  const stack = []
  stack.push(vnode)
  while (stack.length !== 0) {  
    const node = stack.pop()
    nodeList.push(node)
    if(node.children){
      const children = node.children
      for (let i = children.length - 1; i >= 0; i--)  
        stack.push(children[i])
    }
  }  
  return nodeList 
}  

React dom diff 算法

传统 diff 算法

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法 通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数。O(n^3) 到底有多可怕，这意味着如果要展示 1000 个节点，就要依次执行上十亿次的比较。这个开销实在是太过高昂。现今的 CPU 每秒钟能执行大约30亿条指令，即便是最高效的实现，也不可能在一秒内计算出差异情况。

如果 React 只是单纯的引入 diff 算法而没有任何的优化改进，那么其效率是远远无法满足前端渲染所要求的性能。

那么，React diff 到底是如何实现的稳定高效的 diff 呢？

详解 React diff

传统 diff 算法的复杂度为 O(n^3)，显然这是无法满足性能要求的。React 通过制定大胆的策略，将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

diff 策略

1. Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。
2. 拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。
3. 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分（节点移动会导致 diff 开销较大，通过 key 进行优化）。

基于以上三个前提策略，React 分别对 tree diff、component diff 以及 element diff 进行算法优化，事实也证明这三个前提策略是合理且准确的，它保证了整体界面构建的性能。

• tree diff
• component diff
• element diff

tree diff

基于策略一，React 对树的算法进行了简洁明了的优化，即对树进行分层比较，两棵树只会对同一层次的节点进行比较。

既然 DOM 节点跨层级的移动操作少到可以忽略不计，针对这一现象，React 通过 updateDepth 对 Virtual DOM 树进行层级控制，只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

component diff

React 是基于组件构建应用的，对于组件间的比较所采取的策略也是简洁高效。

• 如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。
• 如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点。
• 对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

element diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）、TEXT_CONTENT（文本内容）、REMOVE_NODE（删除）。

详情参考 DOMChildrenOperations.js

类型	情况
MOVE_EXISTING	新的component类型在老的集合里也有，并且element是可以更新的类型，在generateComponentChildren我们已经调用了receiveComponent，这种情况下prevChild=nextChild,那我们就需要做出移动的操作，可以复用以前的dom节点。
INSERT_MARKUP	新的component类型不在老的集合里，那么就是全新的节点，我们需要插入新的节点
REMOVE_NODE	老的component类型，在新的集合里也有，但是对应的element不同了不能直接复用直接更新，那我们也得删除。
REMOVE_NODE	老的component不在新的集合里的，我们需要删除

算法实现

步骤一： 创建 Virtual Dom

// virtual-dom
function createElement(tagName, props = {}, ...children) {
  let vnode = {}
  if(props.hasOwnProperty('key')){
    vnode.key = props.key
    delete props.key
  }
  return Object.assign(vnode, {
    tagName,
    props,
    children,
  })
}

步骤二：渲染 Virtual Dom

function render (vNode) {
  const element = document.createElement(vNode.tagName)
  const props = vNode.props

  for (const key in props) {
    const value = props[key]
    element.setAttribute(key, value)
  }

  vNode.children && vNode.children( child => {
    const childElement = typeof child === 'string' ? document.createTextNode(child) : render(child)
    element.appendChild(childElement)
  })

  return element
}

export default render

步骤三：Dom Diff

• 根据节点变更类型，定义几种变化类型
  • 节点移除
  • 节点替换
  • 文本替换
  • 节点属性变更
  • 插入节点
  • 节点移动

const vpatch = {}
vpatch.REMOVE = 0
vpatch.REPLACE = 1  // node replace
vpatch.TEXT = 2  // text replace
vpatch.PROPS = 3
vpatch.INSERT = 4
vpatch.REORDER = 5

export default vpatch

• diff virtual Dom

/**
 * 二叉树 diff
 * @param lastVNode
 * @param newVNode
 */
function diff (lastVNode, newVNode) {
  let index = 0
  const patches = {}
  // patches.old = lastVNode
  dftWalk(lastVNode, newVNode, index, patches)
  return patches
}

/**
 * 深入优先遍历算法 (depth-first traversal，DFT)
 * @param {*} lastVNode
 * @param {*} newVNode
 * @param {*} index
 * @param {*} patches
 */
function dftWalk(lastVNode, newVNode, index, patches) {
  if (lastVNode === newVNode) {
    return
  }

  const currentPatch = []

  // Node is removed
  if (newVNode === null) {
    currentPatch.push({ type: patch.REMOVE })

  // diff text
  } else if (_.isString(lastVNode) && _.isString(newVNode)) {
    if (newVNode !== lastVNode) {
      currentPatch.push({ type: patch.TEXT, text: newVNode })
    }

  // same node  此处会出行，parentNode 先 moves 处理，childnode 再做一次处理（替换或修改属性）
  } else if (
    newVNode.tagName === lastVNode.tagName
    // && newVNode.key === lastVNode.key
  ) {
    // newVNode.key === lastVNode.key 才会执行 diffChildren
    if (newVNode.key === lastVNode.key) {
      const propsPatches = diffProps(lastVNode.props, newVNode.props)
      if (Object.keys(propsPatches).length > 0) {
        currentPatch.push({ type: patch.PROPS, props: propsPatches })
      }

      diffChildren(
        lastVNode.children,
        newVNode.children,
        currentPatch,
        index,
        patches,
      )
    } else {
      currentPatch.push({ type: patch.REPLACE, node: newVNode })
    }

  // Nodes are not the same
  } else {
    currentPatch.push({ type: patch.REPLACE, node: newVNode })
  }

  if (currentPatch.length) {
    patches[index] = currentPatch
  }
}

function diffChildren (lastChildren, newChildren, apply, index, patches) {
  const orderedSet = reorder(lastChildren, newChildren)
  let len = lastChildren.length > newChildren.length ? lastChildren.length : newChildren.length
  for (var i = 0; i < len; i++) {
    if (!lastChildren[i]) {

      // insert node
      if (newChildren[i] && !orderedSet.moves) {
        apply.push({ type: patch.INSERT, node: newChildren[i] })
      }

    } else {
      dftWalk(lastChildren[i], newChildren[i], ++index, patches)
    }
  }
  console.error('orderedSet.moves', orderedSet.moves)
  if (orderedSet.moves) {
    apply.push(orderedSet)
  }
}

/**
 * diff vnode props
 * @param {*} lastProps
 * @param {*} newProps
 */
function diffProps (lastProps, newProps) {
  const propsPatches = {}

  // Find out diff props
  for (const key in lastProps) {
    if (newProps[key] !== lastProps[key]) {
      propsPatches[key] = newProps[key]
    }
  }


  // Find out new props
  for (const key in newProps) {
    if (!lastProps.hasOwnProperty(key)) {
      propsPatches[key] = newProps[key]
    }
  }
  return propsPatches
}

/**
 * List diff, naive left to right reordering
 * @param {*} lastChildren
 * @param {*} newChildren
 *
 * 原理利用中间数组 simulate， remove得到子集、insert 插入操作完成
 * 例 oldList [1,4,6,8,9] newList [0,1,3,5,6]
 * 转换拿到中间数组按老数组索引 [1, null, 6, null, null ]
 * remove null 得到子集 [1, 6]
 * insert 插入完成
 */
function reorder(lastChildren, newChildren) {
  const lastMap = keyIndex(lastChildren)
  const lastKeys = lastMap.keys
  const lastFree = lastMap.free

  if(lastFree.length === lastChildren.length){
    return {
      moves: null
    }
  }


  const newMap = keyIndex(newChildren)
  const newKeys = newMap.keys
  const newFree = newMap.free

  if(newFree.length === newChildren.length){
    return {
      moves: null
    }
  }

  // simulate list to manipulate
  const children = []
  let freeIndex = 0

  for (let i = 0 ; i < lastChildren.length; i++) {
    const item = lastChildren[i]
    if(item.key){
      if(newKeys.hasOwnProperty('key')){
        const itemIndex = newKeys[item.key]
        children.push(newChildren[itemIndex])
      } else {
        children.push(null)
      }
    } else {
      const itemIndex = newFree[freeIndex++]
      children.push(newChildren[itemIndex] || null)
    }
  }

  const simulate = children.slice()
  const removes = []
  const inserts = []

  let j = 0

  // remove  value is null and  no key property
  while (j < simulate.length) {
    if (simulate[j] === null || !simulate[j].hasOwnProperty('key')) {
      const patch = remove(simulate, j)
      removes.push(patch)
    } else {
      j++
    }
  }

  console.error('simulate', simulate)
  for (let i = 0 ; i < newChildren.length; i++) {
    const wantedItem = newChildren[i]
    const simulateItem = simulate[i]

    if(wantedItem.key){
      if(simulateItem && wantedItem.key !== simulateItem.key){
        // key property is not equal, insert, simulateItem add placeholder
        inserts.push({
          type: patch.INSERT,
          index: i,
          node: wantedItem,
        })
        simulateItem.splice(i, 1)
      }
    } else {
      // no key property, insert, simulateItem add placeholder
      inserts.push({
        type: patch.INSERT,
        index: i,
        node: wantedItem,
      })
      simulateItem && simulateItem.splice(i, 1)
    }
  }

  return {
    type: patch.REORDER,
    moves: {
      removes: removes,
      inserts: inserts
    }
  }
}

function remove(arr, index) {
  arr.splice(index, 1)

  return {
    type: patch.REMOVE,
    index,
  }
}


/**
 * Convert list to key-item keyIndex object.
 * @param {*} children
 * convert [{id: "a", key: 'a'}, {id: "b", key: 'b'}, {id: "a"}]
 * result { keys: { a: 0, b: 1}, free: [ 2 ] }
 */
function keyIndex(children) {
  var keys = {}
  var free = []
  var length = children.length

  for (var i = 0; i < length; i++) {
      var child = children[i]

      if (child.key) {
          keys[child.key] = i
      } else {
          free.push(i)
      }
  }

  return {
      keys: keys,     // A hash of key name to index
      free: free      // An array of unkeyed item indices
  }
}

export default diff

步骤四：收集 patchs

{
  "0": [
    {
      "type": 3,
      "props": {
        "className": "zz",
        "height": "20px"
      }
    },
    {
      "type": 5,
      "moves": {
        "removes": [
          {
            "type": 0,
            "index": 0
          },
          {
            "type": 0,
            "index": 0
          }
        ],
        "inserts": [
          {
            "type": 4,
            "index": 1,
            "node": {
              "tagName": "li",
              "props": {
                "className": "one"
              },
              "children": [
                "one"
              ]
            }
          }
        ]
      }
    }
  ],
  "1": [
    {
      "type": 5,
      "moves": {
        "removes": [
          {
            "type": 0,
            "index": 0
          },
          {
            "type": 0,
            "index": 0
          }
        ],
        "inserts": [
          {
            "type": 4,
            "index": 2,
            "node": {
              "tagName": "li",
              "props": {
                "className": "ooo"
              },
              "children": [
                "插入节点"
              ]
            }
          }
        ]
      }
    }
  ],
  "2": [
    {
      "type": 1,
      "node": {
        "key": "1",
        "tagName": "li",
        "props": {
          "className": "teext"
        },
        "children": [
          "哈咯"
        ]
      }
    }
  ],
  "3": [
    {
      "type": 1,
      "node": {
        "key": "2",
        "tagName": "li",
        "props": {
          "className": "zz"
        },
        "children": [
          "大家好"
        ]
      }
    }
  ]
}

步骤五：更新 patchs，把差异应用到真正的DOM树上

import patch from './vpatch.js'
import render from './render.js'

/**
 * 真实的 Dom 打补钉
 * @param {*} rootNode 实际的 DOM
 * @param {*} patches
 */
function patch (rootNode, patches) {
  const walker = { index: 0 }
  dftWalk(rootNode, walker, patches)
}

/**
 * 深入优先遍历算法 (depth-first traversal，DFT)
 * @param {*} node
 * @param {*} walker
 * @param {*} patches
 */
function dftWalk (node, walker, patches) {
  const currentPatches = patches[walker.index] || {}
  node.childNodes && node.childNodes.forEach(child => {
    walker.index++
    dftWalk(child, walker, patches)
  })
  if (currentPatches) {
    applyPatches(node, currentPatches)
  }
}


function applyPatches (node, currentPatches) {
  currentPatches.forEach(currentPatch => {
    switch (currentPatch.type) {
      case patch.REMOVE:
        node.parentNode.removeChild(node)
        break
      case patch.REPLACE:
        const newNode = currentPatch.node
        node.parentNode.replaceChild(render(newNode), node)
        break
      case patch.TEXT:
        node.textContent = currentPatch.text
        break
      case patch.PROPS:
        const props = currentPatch.props
        setProps(node, props)
        break
      case patch.INSERT:
        // parentNode.insertBefore(newNode, referenceNode)
        const newNode = currentPatch.node
        node.appendChild(render(newNode))
        break
      case patch.REORDER:
        reorderChildren(node, currentPatch.moves)
        break
    }
  })

}

/**
 * 设置真实 Dom 属性值
 * @param {*} node
 * @param {*} props
 */
function setProps (node, props) {
  for (const key in props) {
    // void 666 is undefined
    if (props[key] === void 666) {
      node.removeAttribute(key)
    } else {
      const value = props[key]
      node.setAttribute(key, value)
    }
  }
}

/**
 * reorderChildren 处理 list diff render
 * @param {*} domNode
 * @param {*} moves
 */
function reorderChildren(domNode, moves) {
  for (const i = 0; i < moves.removes.length; i++) {
    const { index } = moves.removes[i]
    const node = domNode.childNodes[index]
    domNode.removeChild(node)
  }

  for (const j = 0; j < moves.inserts.length; j++) {
    const { index, node } = moves.inserts[j]
    domNode.insertBefore(node, index === domNode.childNodes.length ? null : childNodes[index])
  }
}

Other Resources

树的广度优先遍历和深度优先遍历

React diff

React’s diff algorithm

snabbdom A virtual DOM library'

浅析虚拟dom原理并实现

virtual-dom--A Virtual DOM and diffing algorithm

simple-virtual-dom

React源码分析与实现(三)：实操DOM Diff

深度剖析：如何实现一个 Virtual DOM 算法

fast-diff

React Fiber实现原理

React Fiber为什么使用链表来设计组件树

[Stanny2017]

文章很赞👍，收益匪浅

步骤二：渲染 Virtual Dom 代码中 应该是element.setAttribute 吧