虚拟 DOM 与 Diff 算法的实现原理

更新日期: 2021-06-08阅读: 1.6k标签: diff

前言

vue 源码中虚拟 dom 与 Diff 算法的实现借鉴了 snabbdom 这个库,snabbdom 是一个虚拟 DOM 库,它专注于简单,模块化,强大的功能和性能。要彻底明白虚拟 DOM 与 Diff 算法就得分析 snabbdom 这个库到底做了什么?


获取源代码

可以通过npm i snabbdom -D 来下载 snabbdom 库,这样我们既能看到 src 下用 Typescript 编写的源码,也能看到编译好的 JavaScript 代码。下面贴的源码是 2.1.0 版本,现在已经更新到 3.0.3 版本了。建议将下方出现的源码复制到下载的 snabbdom 库中相应位置,这样看源码比较清晰。那我们就开始分析源码吧。


源码分析

JavaScript 对象模拟真实 DOM 树

通过调用 snabbdom 库中的 h函数就可以对真实 DOM 节点进行抽象。我们先来看看一个完整的虚拟 DOM 节点(vnode)是什么样的:

{
  sel: "div", // 当前vnode的选择器
  elm: undefined, // 当前vnode对应真实的DOM节点
  key: undefined, // 当前vnode的唯一标识
  data: {}, // 当前vnode的属性,样式等
  children: undefined, // 当前vnode的子元素
  text: '文本内容' // 当前vnode的文本节点内容
}

实际上,h函数的作用就是用 JavaScript 对象模拟真实的 DOM 树,对真实 DOM 树进行抽象。调用 h函数就能得到由 vnode 组成的虚拟 DOM 树。

调用 h函数有多种形式:

 ① h('div')
 ② h('div', 'text')
 ③ h('div', h('p'))
 ④ h('div', [])
 ⑤ h('div', {})
 ⑥ h('div', {}, 'text')
 ⑦ h('div', {}, h('span'))
 ⑧ h('div', {}, [])

使得 h函数的第二和第三个参数比较灵活,要判断的情况也比较多,下面把这部分的核心源码分析贴一下:

// h函数:根据传入的参数推测出h函数的调用形式以及每个vnode对应属性的属性值
export function h(sel: string): VNode
export function h(sel: string, data: VNodeData | null): VNode
export function h(sel: string, children: VNodeChildren): VNode
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode
export function h(sel: any, b?: any, c?: any): VNode {
  var data: VNodeData = {};
  var children: any;
  var text: any;
  var i: number
  // c有值,情况有:⑥ ⑦ ⑧
  if (c !== undefined) { 
    // c有值的情况下b有值,情况有:⑥ ⑦ ⑧
    if (b !== null) { 
      // 将b赋值给data 
      data = b  
    }
    // c的数据类型是数组,情况有:⑧
    if (is.array(c)) { 
      children = c 
    // 判断c是文本节点,情况有:⑥
    } else if (is.primitive(c)) { 
      text = c 
    // 情况有:⑦,⑦这条语句会先执行h('span')代码,直接调用vnode函数,调用后会返回{sel: 'span'},
    // 这时c有值并且c并且含有sel属性
    } else if (c && c.sel) {
      // 注:这里的c不是h('span'),而是h('span')的返回值,是个{ sel: 'span' }这样的对象,
      // 最后组装成数组赋值给children
      children = [c]
    }
  // c没有值,b有值,情况有:② ③ ④ ⑤
  } else if (b !== undefined && b !== null) { 
    // b的数据类型是数组,情况有:④
    if (is.array(b)) { 
      children = b 
    // 判断b是文本节点,情况有:②
    } else if (is.primitive(b)) { 
      text = b 
    // 情况有:③,③这条语句会先执行h('p')代码,直接调用vnode函数,调用后会返回{sel: 'p'},
    // 这时b有值并且b并且含有sel属性
    } else if (b && b.sel) {
      // 注:这里的b不是h('p'),而是h('p')的返回值,是个{ sel: 'p' }这样的对象,
      // 最后组装成数组赋值给children
      children = [b] 
    // 情况有:⑤,将b赋值给data
    } else { data = b } 
  }
  // children有值,遍历children
  if (children !== undefined) { 
    for (i = 0; i < children.length; ++i) {
      // 判断children中的每一项的数据类型是否是string/number,调用vnode函数
      if (is.primitive(children[i])) {
          children[i] = vnode(undefined, undefined, undefined, children[i], undefined)
      }
    }
  }
  /**
   * 调用vnode后返回形如
   * {
   *    sel: 'div',
   *    data: { style: '#000' },
   *    children: undefined,
   *    text: 'text',
   *    elm: undefined, 
   *    key: undefined
   * }
   * 这样的JavaScript对象
  */
  return vnode(sel, data, children, text, undefined);  
}
// vnode函数:根据传入的参数组装vnode结构
export function vnode(sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined): VNode {
  // 判断data是否有值,有值就将data.key赋值给key,无值就将undefined赋值给key
  const key = data === undefined ? undefined : data.key 
  // 将传入vnode函数的参数组装成一个对象返回
  return { sel, data, children, text, elm, key } 
}

diff 算法--入口函数

通过 h函数得到新旧虚拟节点 DOM 对象后就可以进行差异比较了。在实际使用过程中,我们是直接调用 snabbdom 的 patch 函数,然后传入两个参数,通过 patch 函数内部处理就可以得到新旧虚拟节点 DOM 对象的差异,并将差异部分更新到真正的 DOM 树上。

首先,patch 函数会去判断 oldVnode 是否是真实DOM节点,如果是则需要先转换为虚拟DOM节点 oldVnode = emptyNodeAt(oldVnode) ;然后去比较新旧 vnode 是否是同一个节点 sameVnode(oldVnode, vnode),如果是同一节点则精确比较新旧 vnode patchVnode(oldVnode, vnode, insertedVnodeQueue) ,如果不是则直接创建新 vnode 对应的真实 DOM 节点 createElm(vnode, insertedVnodeQueue),在 createElm 函数中创建新 vnode 的真实 DOM 节点以及它对应的子节点,并把子节点插入到相应位置。如果 oldVnode.elm 有父节点则把新 vnode 对应的真实 DOM 节点作为子节点插入到相应位置,并且删除旧节点。下面贴一下 patch 函数的源码解析:

function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node
    const insertedVnodeQueue: VNodeQueue = []
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()

    // isVnode(oldVnode)判断oldVnode.sel是否存在,不存在表示oldVnode是真实的DOM节点
    if (!isVnode(oldVnode)) {
      // oldVnode可能是真实的DOM节点,也可能是旧的虚拟DOM节点,
      // 如果是真实的DOM节点要调用vnode函数组装成虚拟DOM节点
      oldVnode = emptyNodeAt(oldVnode)
    }

    // 判断出是同一个虚拟DOM节点
    if (sameVnode(oldVnode, vnode)) { 
      // 精确比较两个虚拟DOM节点
      patchVnode(oldVnode, vnode, insertedVnodeQueue) 
    } else {
      // oldVnode.elm是虚拟DOM节点对应的真实DOM节点
      elm = oldVnode.elm! 
      // api.parentNode(elm)获取elm的父节点elm.parentNode
      parent = api.parentNode(elm) as Node 

      // 创建vnode下真实DOM节点并更新到相应位置
      createElm(vnode, insertedVnodeQueue) 

      // elm的父节点存在
      if (parent !== null) { 
        // api.nextSibling(elm)-->elm.nextSibling 返回紧跟在elm之后的节点
        // api.insertBefore(parent, B, C)-->-->parent.insertBefore(B, C),将B节点插入到C节点之前
        api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
        removeVnodes(parent, [oldVnode], 0, 0) // 删除旧的DOM节点
      }
    }

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i])
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
    return vnode
  }

patch 函数中用到了 emptyNodeAt 函数,这个函数主要是处理 patch 函数第一个参数为真实DOM节点的情况。下面贴一下这个函数的源码解析:

  function emptyNodeAt(elm: Element) {
    // 判断传入的DOM节点elm有没有id属性,因为虚拟DOM节点的sel属性是选择器,例如:div#wrap
    const id = elm.id ? '#' + elm.id : '' 
    // 判断传入的ODM节点elm有没有class属性,因为虚拟DOM节点的sel属性是选择器,例如:div.wrap
    const c = elm.className ? '.' + elm.className.split(' ').join('.') : '' 
    // 调用vnode函数将传入的DOM节点组装成虚拟DOM节点
    return vnode(api.tagName(elm).toLowerCase() + id + c, {}, [], undefined, elm) 
  }

patch 函数中用到了 sameVnode 函数,这个函数主要用来比较两个虚拟DOM节点是否是同一个虚拟节点。下面贴一下这个函数的源码分析:

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  // 判断vnode1和vnode2是否是同一个虚拟DOM节点
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel 
}

diff 算法--新旧 vnode 不是同一个节点的情况

根据 sameVnode 函数返回的结果,新旧 vnode 不是同一个虚拟节点。首先获取到 oldVnode 对应真实 DOM 节点的父节点 parent ,然后调用 createElm 函数去创建 vnode 对应的真实 DOM 节点以及它的子节点和标签属性等等。判断是否有 parent, 如果有则将 vnode.elm 对应的DOM节点作为子节点插入到 parent 节点下的相应位置。部分源码分析在patch函数中,下面贴一下 createElm 函数的源码分析:

 function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue): Node {
    let i: any
    let data = vnode.data
    if (data !== undefined) {
      const init = data.hook?.init
      if (isDef(init)) {
        init(vnode)
        data = vnode.data
      }
    }
    const children = vnode.children
    const sel = vnode.sel
    // 判断sel值中是否包含!
    if (sel === '!') {
      if (isUndef(vnode.text)) {
        vnode.text = ''
      }
      // --> document.createComment(vnode.text!)创建注释节点
      vnode.elm = api.createComment(vnode.text!)
    } else if (sel !== undefined) {
      // 解析sel选择器
      // 查找sel属性值中#的索引,没找到返回-1
      const hashIdx = sel.indexOf('#')
      // hashIdx作为起始位置查找sel属性值中.的索引,如果hashIdx < 0 那么从位置0开始查找
      const dotIdx = sel.indexOf('.', hashIdx)
      const hash = hashIdx > 0 ? hashIdx : sel.length
      const dot = dotIdx > 0 ? dotIdx : sel.length
      // 若id选择器或class选择器存在,则从0位开始截取到最小索引值的位置结束,截取出的就是标签名称
      // 都不存在直接取sel值
      const tag = hashIdx !== -1 || dotIdx !== -1 ? sel.slice(0, Math.min(hash, dot)) : sel
      // 根据tag名创建DOM元素
      const elm = vnode.elm = isDef(data) && isDef(i = data.ns)
        ? api.createElementNS(i, tag)
        : api.createElement(tag)
      // 设置id属性
      if (hash < dot) elm.setAttribute('id', sel.slice(hash + 1, dot))
      // 设置calss属性
      if (dotIdx > 0) elm.setAttribute('class', sel.slice(dot + 1).replace(/\./g, ' '))
      for (i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode)
      // 判断children是否是数组,是数组则遍历children
      if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
          const ch = children[i]
          if (ch != null) {
            // createElm(ch as VNode, insertedVnodeQueue)递归创建子节点
            // api.appendChild(A, B)-->A.appendChild(B)将B节点插入到指定父节点A的子节点列表的末尾
            api.appendChild(elm, createElm(ch as VNode, insertedVnodeQueue))
          }
        }
        // 判断vnode.text有没有值
      } else if (is.primitive(vnode.text)) {
        // api.createTextNode(vnode.text)根据vnode.text创建文本节点
        // api.appendChild(elm, B)-->A.appendChild(B)将文本节点B添加到父节点elm子节点列表的末尾处
        api.appendChild(elm, api.createTextNode(vnode.text))
      }
      const hook = vnode.data!.hook
      if (isDef(hook)) {
        hook.create?.(emptyNode, vnode)
        if (hook.insert) {
          insertedVnodeQueue.push(vnode)
        }
      }
    } else {
      // sel不存在直接创建文本节点
      vnode.elm = api.createTextNode(vnode.text!)
    }
    return vnode.elm
  }

diff 算法--新旧 vnode 是同一个节点的情况

上面分析了新旧 vnode 不是同一个虚拟节点,那么是同一个虚拟节点又该怎么去处理?首先,调用 patchVnode 函数 patchVnode(oldVnode, vnode, insertedVnodeQueue),这个函数会对新旧 vnode 进行精确比较:

① 如果新旧虚拟 DOM 对象全等 oldVnode === vnode ,那么不做任何操作,直接返回;

② 然后判断 vnode 是否有文本节点 isUndef(vnode.text) ,如果没有文本节点则判断 oldVnode 与 vnode 有没有子节点 isDef(oldCh) && isDef(ch),如果都有子节点且不相等则调用 updateChildren 函数去更新子节点;

③ 如果只有 vnode 有子节点而 oldVnode 有文本节点或没有内容,将 oldVnode 的文本节点置空或不做处理,调用 addVnodes 函数将 vnode 的子节点创建出对应的真实DOM并循环插入到父节点下;

④ 如果只有 oldVnode 有子节点而 vnode 没有内容,则直接删除 oldVnode 下的子节点;

⑤ 如果只有 oldVnode 有文本节点而 vnode 没有内容,则将 oldVnode 对应的真实 DOM 节点的文本置空;

⑥ 如果 vnode 有文本节点,oldVnode 有子节点就将对应真实 DOM 节点的子节点删除,没有就不处理,然后将 vnode 的文本节点作为子节点插入到对应真实 DOM 节点下。

部分源码分析在patch函数中,下面贴一下 patchVnode 函数的源码分析:

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    const hook = vnode.data?.hook
    hook?.prepatch?.(oldVnode, vnode)
    const elm = vnode.elm = oldVnode.elm!
    const oldCh = oldVnode.children as VNode[]
    const ch = vnode.children as VNode[]
    // oldVnode与vnode完全相等并没有需要更新的内容则直接返回,不做处理
    if (oldVnode === vnode) return 
    if (vnode.data !== undefined) {
      for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
      vnode.data.hook?.update?.(oldVnode, vnode)
    }
    // vnode.text为undefined表示vnode虚拟节点没有文本内容
    if (isUndef(vnode.text)) { 
      // oldCh与ch都不为undefined表示oldVnode与vnode都有虚拟子节点children
      if (isDef(oldCh) && isDef(ch)) { 
        // oldCh !== ch 利用算法去更新子节点
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
      } else if (isDef(ch)) { 
        // 将oldVnode的文本节点设置为''
        if (isDef(oldVnode.text)) api.setTextContent(elm, '') 
        // 调用addVnodes方法将vnode的虚拟子节点循环插入到elm节点的子列表下
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      // oldCh不为undefined表示oldVnode有虚拟子节点children
      } else if (isDef(oldCh)) { 
        // vnode没有children则直接删除oldVnode的children
        removeVnodes(elm, oldCh, 0, oldCh.length - 1) 
      // oldVnode.text有值而vnode.text没有值
      } else if (isDef(oldVnode.text)) { 
        // 将oldVnode的文本节点设置为''
        api.setTextContent(elm, '') 
      }
    // oldVnode与vnode文本节点内容不同
    } else if (oldVnode.text !== vnode.text) { 
      // isDef(oldCh)-->oldCh !== undefined 表明oldVnode虚拟节点下有虚拟子节点
      if (isDef(oldCh)) { 
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      }
      // oldCh虚拟节点下没有虚拟子节点则直接更新文本内容
      api.setTextContent(elm, vnode.text!)
    }
    hook?.postpatch?.(oldVnode, vnode)
  }

diff 算法--新旧 vnode 子节点的更新策略

当新旧 vnode 都有子节点时,diff 算法定义了四个指针来处理子节点,四个指针分别是:oldStartVnode(旧前vnode)/newStartVnode(新前vnode)/oldEndVnode(旧后vnode)/newEndVnode(新后vnode) 。进入循环体内后,新旧 vnode 的子节点两两比较,这里提供了一套比较规则,如下图:

如果上面四个规则都不满足,将 oldVnode 的子节点从旧的前索引 oldStartIdx 到旧的后索引 oldEndIdx 做一个 key 与对应位置序号的映射 oldKeyToIdx ,通过新 vnode 的 key 去找 oldKeyToIdx 中是否有对应的索引值,若没有,表明 oldVnode 没有对应的旧节点,是一个新增的节点,进行插入操作;若有,表明 oldVnode 有对应的旧节点,不是一个新增节点,进行移动操作。下面贴一下源码解析:

// 旧vnode的子节点的前索引oldStartIdx到后索引oldEndIdx的key与对应位置序号的映射关系
function createKeyToOldIdx(children: VNode[], beginIdx: number, endIdx: number): KeyToIndexMap {
  const map: KeyToIndexMap = {}
  for (let i = beginIdx; i <= endIdx; ++i) {
    const key = children[i]?.key
    if (key !== undefined) {
      map[key] = i
    }
  }
  /**
   * 例如:map = { A: 1, B: 2 }
  */
  return map
}
function updateChildren(parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue) {
    let oldStartIdx = 0 // 旧的前索引
    let newStartIdx = 0 // 新的前索引
    let oldEndIdx = oldCh.length - 1 // 旧的后索引
    let newEndIdx = newCh.length - 1 // 新的后索引
    let oldStartVnode = oldCh[0] // 旧的前vnode
    let newStartVnode = newCh[0] // 新的前vnode
    let oldEndVnode = oldCh[oldEndIdx] // 旧的后vnode
    let newEndVnode = newCh[newEndIdx] // 新的后vnode
    let oldKeyToIdx: KeyToIndexMap | undefined
    let idxInOld: number
    let elmToMove: VNode
    let before: any

    // 当旧的前索引 <= 旧的后索引 && 新的前索引 <= 新的后索引时执行循环语句
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      // 为什么oldStartVnode == null? 
      // 因为虚拟节点进行移动操作后要将原来的虚拟节点置为undefined了
      // oldCh[idxInOld] = undefined as any
      if (oldStartVnode == null) {
        // oldStartVnode为null就过滤掉当前节点,取oldCh[++oldStartIdx]节点(旧的前索引的下一个索引的节点)
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (oldEndVnode == null) {
        // oldEndVnode为null就过滤掉当前节点,取oldCh[--oldEndIdx]节点(旧的后索引的上一个索引的节点)
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (newStartVnode == null) {
        // newStartVnode为null就过滤掉当前节点,取newCh[++newStartIdx]节点(新的前索引的下一个索引的节点)
        newStartVnode = newCh[++newStartIdx]
      } else if (newEndVnode == null) {
        // newEndVnode为null就过滤掉当前节点,取newCh[--newEndIdx]节点(新的后索引的上一个索引的节点)
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        /**
        * ① 旧的前vnode(oldStartVnode) 与 新的前vnode(newStartVnode) 比较是否是同一个虚拟节点
        * 旧的虚拟子节点                       新的虚拟子节点
        * h('li', { key: 'A' }, 'A')      h('li', { key: 'A' }, 'A')
        * h('li', { key: 'B' }, 'B')      h('li', { key: 'B' }, 'B')
       */
        // 如果判断是同一个虚拟节点则调用patchVnode函数
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
        // oldCh[++oldStartIdx]取旧的前索引节点的下一个虚拟节点(例子中key为B的节点),赋值给oldStartVnode
        oldStartVnode = oldCh[++oldStartIdx]
        // oldCh[++oldStartIdx]取新的前索引节点的下一个虚拟节点(例子中key为B的节点),赋值给newStartVnode
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        /**
         * 如果旧的前vnode(例子中key为B的虚拟节点) 与 新的前vnode(例子中key为B的虚拟节点) 
         * 不是同一个虚拟节点则进行方案②比较
         * ② 旧的后vnode(oldEndVnode) 与 新的后vnode(newEndVnode) 比较是否是同一个虚拟节点
         * 旧的虚拟子节点                   新的虚拟子节点
         * h('li', { key: 'C' }, 'C')      h('li', { key: 'A' }, 'A')
         * h('li', { key: 'B' }, 'B')      h('li', { key: 'B' }, 'B')
        */
        // 如果判断是同一个虚拟节点则调用patchVnode函数
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
        // oldCh[--oldEndIdx]取旧的后索引节点的上一个虚拟节点(例子中key为C的虚拟节点),赋值给oldEndVnode
        oldEndVnode = oldCh[--oldEndIdx]
        // newCh[--newEndIdx]取新的后索引节点的上一个虚拟节点(例子中key为A的虚拟节点),赋值给newEndVnode
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        /**
        * 如果旧的后vnode 与 新的后vnode 不是同一个虚拟节点则进行方案③比较
        * ③ 旧的前vnode(oldStartVnode) 与 新的后vnode(newEndVnode) 比较是否是同一个虚拟节点
        * 旧的虚拟子节点                   新的虚拟子节点
        * h('li', { key: 'C' }, 'C')      h('li', { key: 'A' }, 'A')
        * h('li', { key: 'B' }, 'B')      h('li', { key: 'B' }, 'B')
        *                                 h('li', { key: 'C' }, 'C')
       */
        // 如果判断是同一个虚拟节点则调用patchVnode函数
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
        // 将旧的前vnode(相当于例子中key为C的虚拟节点)插入到当前旧的后vnode的下一个兄弟节点的前面
        // 如果oldEndVnode是最末尾的虚拟节点,则node.nextSibling会返回null,
        // 则新的虚拟节点直接插入到最末尾,等同于appenChild
        api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
        // oldCh[++oldStartIdx]取旧的前索引虚拟节点的下一个虚拟节点(例子中key为B的虚拟节点),赋值给oldStartVnode
        oldStartVnode = oldCh[++oldStartIdx]
        // newCh[--newEndIdx]取新的后索引虚拟节点的上一个虚拟节点(例子中key为B的虚拟节点),赋值给newEndVnode
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        /**
        * 如果旧的前vnode 与 新的后vnode 不是同一个虚拟节点则进行方案④比较
        * ④ 旧的后vnode(oldEndVnode) 与 新的前vnode(newStartVnode) 比较是否是同一个虚拟节点
        * 旧的虚拟子节点                   新的虚拟子节点
        * h('li', { key: 'C' }, 'C')      h('li', { key: 'B' }, 'B')
        * h('li', { key: 'B' }, 'B')      h('li', { key: 'A' }, 'A')
        *                                 h('li', { key: 'C' }, 'C')
       */
        // 如果判断是同一个虚拟节点则调用patchVnode函数
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
        // 将旧的后vnode(例子中key为B)插入到当前旧的前vnode(例子中key为C)的前面
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
        // oldCh[--oldEndIdx]取旧的后索引节点的上一个虚拟节点(例子中key为C的虚拟节点),赋值给oldEndVnode
        oldEndVnode = oldCh[--oldEndIdx]
        // newCh[++newStartIdx]取新的前索引节点的下一个虚拟节点(例子中key为A的虚拟节点),赋值给newStartVnode
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 不满足以上四种情况
        if (oldKeyToIdx === undefined) {
          // oldKeyToIdx保存旧的children中各个节点的key与对应位置序号的映射关系
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        }
        // 从oldKeyToIdx中获取当前newStartVnode节点key对应的序号
        idxInOld = oldKeyToIdx[newStartVnode.key as string]
        if (isUndef(idxInOld)) { // isUndef(idxInOld) --> idxInOld === undefined
          /**
           * idxInOld = undefined 要插入节点
           * 旧的虚拟子节点中没有idxInOld对应的节点,而新的虚拟子节点中有,
           * 所以newStartVnode是需要插入的虚拟节点
           * 旧的虚拟子节点                   新的虚拟子节点
           * h('li', { key: 'A' }, 'A')      h('li', { key: 'C' }, 'C') 
           * h('li', { key: 'B' }, 'B')
          */
          // 根据newStartVnode(例子中key为C的虚拟节点)创建真实DOM节点createElm(),
          // 将创建的DOM节点插入到oldStartVnode.elm(例子中key为A的节点)的前面
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
        } else {
          /**
           * idxInOld != undefined 要移动节点
           * 旧的虚拟子节点中有idxInOld对应的节点,所以oldCh[idxInOld]是需要移动的虚拟节点
           * 旧的虚拟子节点                   新的虚拟子节点
           * h('li', { key: 'A' }, 'A')      h('div', { key: 'B' }, 'B')
           * h('li', { key: 'B' }, 'B')      h('li', { key: 'D' }, 'D')                                                      
          */
          elmToMove = oldCh[idxInOld] // elmToMove保存要移动的虚拟节点
          // 判断elmToMove与newStartVnode在key相同的情况下sel属性是否相同
          if (elmToMove.sel !== newStartVnode.sel) {
            // sel属性不相同表明不是同一个虚拟节点,
            // 根据newStartVnode虚拟节点创建真实DOM节点并插入到oldStartVnode.elm(旧的key为A的节点)之前
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
          } else {
            // key与sel相同表示是同一个虚拟节点,调用patchVnode函数
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
            // 处理完被移动的虚拟节点oldCh[idxInOld]要设置为undefined,方便下次循环处理时过滤掉已经处理的节点
            oldCh[idxInOld] = undefined as any
            // 将elmToMove.elm(例子中旧的key为B的节点)插入到oldStartVnode.elm(例子中key为A的节点)的前面
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
          }
        }
        // 取newCh[++newStartIdx]虚拟节点(例子中key为D的虚拟节点)赋值给newStartVnode
        newStartVnode = newCh[++newStartIdx]
      }
    }
    /**
     * 循环结束后旧的前索引 <= 旧的后索引 || 新的前索引 <= 新的后索引,
     * 表示还有部分虚拟节点(例子中key为C的虚拟节点)没处理
     * 旧的虚拟子节点                   新的虚拟子节点
     * 情况一:
     * h('li', { key: 'A' }, 'A')      h('li', { key: 'A' }, 'A')
     * h('li', { key: 'B' }, 'B')      h('li', { key: 'B' }, 'B')
     * h('li', { key: 'D' }, 'D')      h('li', { key: 'C' }, 'C')
     *                                 h('li', { key: 'D' }, 'D')
     * 情况二:
     * h('li', { key: 'A' }, 'A')      h('li', { key: 'A' }, 'A')
     * h('li', { key: 'B' }, 'B')      h('li', { key: 'B' }, 'B')
     * h('li', { key: 'C' }, 'C')
    */
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      // 处理例子中情况一
      if (oldStartIdx > oldEndIdx) {
        // 待插入的节点以before节点为参照,newCh[newEndIdx]是例子中新的子节点中key为C的虚拟节点,
        // 所以before = newCh[newEndIdx + 1]是key为D的虚拟节点
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
        // 例子中现在newStartIdx,newEndIdx都为2
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
      } else {
        // 处理例子中情况二,删除旧的前索引到旧的后索引中间的节点(例子中删除旧的key为C的虚拟节点)
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
      }
    }
  }

原文来自:https://segmentfault.com/a/1190000040142729


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

React Diff 算法

React 是 facebook 出的一个前端框架. 设计的关键处就是性能问题。在本文中,我主要是介绍 Diff 算法以及 React 渲染 ,这样你可以更好的优化你的应用程序。

浅析vue2.0的diff算法

如果不了解virtual dom,要理解diff的过程是比较困难的。虚拟dom对应的是真实dom, 使用document.CreateElement 和 document.CreateTextNode创建的就是真实节点。vue2.0才开始使用了virtual dom,有向react靠拢的意思。

简述dom diff原理

关于react的虚拟dom以及每次渲染更新的dom diff,网上文章很多。但是我一直信奉一个原则,即:但凡复杂的知识,理解之后都只需要记忆简单的东西,而想简单、精确描述一个复杂知识,是极困难的事。

传统diff、react优化diff、vue优化diff

传统diff计算两颗树形结构差异并进行转换,传统diff算法是这样做的:循环递归每一个节点;传统diff算法复杂度达到O(n^3 )这意味着1000个节点就要进行数10亿次的比较,这是非常消耗性能的

React 中 Virtual DOM 与 Diffing 算法的关系

Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

Vue2.x的diff算法记录

为什么在Vue3.0都已经出来这么久了我还要写这篇文章,因为目前自己还在阅读Vue2.x的源码,感觉有所悟。作为一个刚毕业的新人,对Vue框架的整体设计和架构突然有了一点认知,所以才没头没尾地突然写下了diff算法。

深入理解React Diff算法

fiber上的updateQueue经过React的一番计算之后,这个fiber已经有了新的状态,也就是state,对于类组件来说,state是在render函数里被使用的,既然已经得到了新的state

手写一个虚拟DOM库,彻底让你理解diff算法

所谓虚拟DOM就是用js对象来描述真实DOM,它相对于原生DOM更加轻量,因为真正的DOM对象附带有非常多的属性,另外配合虚拟DOM的diff算法,能以最少的操作来更新DOM,除此之外

详解虚拟DOM与Diff算法

那么需要真实的操作DOM100w次,触发了回流100w次。每次DOM的更新都会按照流程进行无差别的真实dom的更新。所以造成了很大的性能浪费。如果循环里面是复杂的操作,频繁触发回流与重绘

浅析snabbdom中vnode和diff算法

目前前端使用最多的就是 vue 或 react 了,我们在学习这两个框架的过程中,总有一个绕不开的话题:vnode,也就是虚拟 dom。什么是虚拟 DOM,引用一段 vue 官方的解释就是:

点击更多...

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