diff算法 - 图1

同层比较会发生的情况：

  1. 节点类型发生变化
  2. 节点类型不变，属性发生变化
  3. 增/删/改 节点
  4. 文本变化

    Vue2

    patch

    1. function patch(oldVnode, newVnode) { // 传入新、旧节点
    2. // 比较是否为一个类型的节点
    3. if (sameVnode(oldVnode, newVnode)) {
    4.  // 是：继续进行深层比较
    5.  patchVnode(oldVnode, newVnode)
    6. } else {
    7.  // 否
    8.  const oldEl = oldVnode.el // 旧虚拟节点的真实DOM节点
    9.  const parentEle = api.parentNode(oldEl) // 获取父节点
    10.  createEle(newVnode) // 创建新虚拟节点对应的真实DOM节点
    11.  if (parentEle !== null) {
    12.    api.insertBefore(parentEle, newVnode.el, api.nextSibling(oldEl)) // 将新元素添加进父元素
    13.    api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
    14.    // 设置null，释放内存
    15.    oldVnode = null
    16.  }
    17. }
    18. return newVnode
    19. }

    sameVnode

    1. function sameVnode(oldVnode, newVnode) {
    2. return (
    3.  oldVnode.key === newVnode.key && // key 值是否一样
    4.  oldVnode.tagName === newVnode.tagName && // 标签名是否一样
    5.  oldVnode.isComment === newVnode.isComment && // 是否都为注释节点
    6.  isDef(oldVnode.data) === isDef(newVnode.data) && // 是否都定义了 data
    7.  sameInputType(oldVnode, newVnode) // 当标签为 input 时，type 必须是否相同
    8. )
    9. }

    patchVNode

    1. function patchVnode(oldVnode, newVnode) {
    2. const el = newVnode.el = oldVnode.el // 获取真实DOM对象
    3. // 获取新旧虚拟节点的子节点数组
    4. const oldCh = oldVnode.children, newCh = newVnode.children
    5. // 如果新旧虚拟节点是同一个对象，则终止
    6. if (oldVnode === newVnode) return
    7. // 如果新旧虚拟节点是文本节点，且文本不一样
    8. if (oldVnode.text !== null && newVnode.text !== null && oldVnode.text !== newVnode.text) {
    9.  // 则直接将真实DOM中文本更新为新虚拟节点的文本
    10.  api.setTextContent(el, newVnode.text)
    11. } else {
    12.  if (oldCh && newCh && oldCh !== newCh) {
    13.    // 新旧虚拟节点都有子节点，且子节点不一样
    14.    // 对比子节点，并更新
    15.    /*  diff核心！！*/  
    16.    updateChildren(el, oldCh, newCh) 
    17.  } else if (newCh) {
    18.    // 新虚拟节点有子节点，旧虚拟节点没有
    19.    // 创建新虚拟节点的子节点，并更新到真实DOM上去
    20.    createEle(newVnode)
    21.  } else if (oldCh) {
    22.    // 旧虚拟节点有子节点，新虚拟节点没有
    23.    // 直接删除真实DOM里对应的子节点
    24.    api.removeChild(el)
    25.  }
    26. }
    27. }
  • 拿到真实的 dom 节点 el（即 oldVnode）
  • 判断当前 newVnode 和 oldVnode 是否指向同一个对象，如果是则直接 return
  • 如果是文本节点，且文本有变化，则直接调用api 将文本替换；若文本没有变化，则继续对比新旧节点的子节点 children
  • 如果 oldVnode 有子节点而 newVnode 没有，则删除 el 的子节点
  • 如果 oldVnode 没有子节点而 newVnode 有，则将 newVnode 的子节点真实化之后添加到 el
  • 如果两者都有子节点，则执行 updateChildren 函数比较子节点，这一步很重要—-diff 的核心

updateChildren

此方法就是diff算法的核心部分，当发现新旧虚拟节点的的子节点都存在时候，我们就需要通过一些方法来判断哪些节点是需要移动的，哪些节点是可以直接复用的，来提高我们整个diff的效率；

  • Vue 的 diff 算法是同级比较，不考虑跨级比较的情况。内部采用深度递归的方式 + 双指针的方式进行比较。
    • 1.先比较是否是相同节点 key tag
    • 2.相同节点比较属性,并复用老节点
    • 3.比较儿子节点，考虑老节点和新节点儿子的情况
    • 4.优化比较：头头、尾尾、头尾、尾头
    • 5.比对查找进行复用

双端对比

所谓 双端比较 就是新列表和旧列表两个列表的头与尾互相对比，在对比的过程中指针会逐渐向内靠拢，直到某一个列表的节点全部遍历过，对比停止。
image.png

  1.  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){....}
  • 使用以上四步进行对比，去寻找 key相同的可复用的节点，当在某一步中找到了则停止后面的寻找。
  • 当对比时找到了可复用的节点，我们还是先 patch 给元素打补丁，然后将指针进行前/后移一位指针。根据对比节点的不同，我们移动的指针和方向也不同

什么情况下DOM节点需要移动 / DOM节点如何移动

  1. // a b c d   旧 
  2. // d b a c   新
  4. #循环1
  5. 发现 oldEndNode = newStartNode  移动 d 到开头 =>  d a b c
  6. oldEndIndex--  newStartIndex++ 
  8. #循环2 
  9. 发现尾节点相同， oldEndIndex--  newEndIndex--
  11. #循环3
  12. 发现 oldStartNode = newEndNode  移动a到b后面 => d b a c 
  13. oldStartNode++  newEndIndex--
  15. #循环4
  16. b = b 四个指针也相同，退出循环

image.png image.png

image.png 

  1. // a b c d   旧 
  2. // b d a c   新
  4. #循环1
  5. 没找到，拿新列表的第一个节点去旧列表中找与其key相同的节点。
  7. 找到对应的VNode，我们只需要将找到的节点的DOM元素，移动到开头，旧列表中的节点改为undefined
  9. 如果没找到直接创建一个新的节点放到最前面
  11. newStartIndex++

image.png image.png

Vue3

最长递增子序列

  • 头和头比
  • 尾和尾比
  • 基于最长递增子序列进行移动/添加/删除

看个例子，比如

老的 children：[ a, b, c, d, e, f, g ]
新的 children：[ a, b, f, c, d, e, h, g ]

  • 先进行头和头比，发现不同就结束循环，得到 [ a, b ]
  • 再进行尾和尾比，发现不同就结束循环，得到 [ g ]
  • 再保存没有比较过的节点 [ f, c, d, e, h ]，并通过 newIndexToOldIndexMap 拿到在数组里对应的下标，生成数组 [ 5, 2, 3, 4, -1 ]，-1 是老数组里没有的就说明是新增
  • 然后再拿取出数组里的最长递增子序列，也就是 [ 2, 3, 4 ] 对应的节点 [ c, d, e ]
  • 然后只需要把其他剩余的节点，基于 [ c, d, e ] 的位置进行移动/新增/删除就可以了

image.png

image.png
我们从后向前进行遍历source每一项。此时会出现三种情况：

  • 当前的值为-1，这说明该节点是全新的节点，又由于我们是从后向前遍历，我们直接创建好 DOM 节点插入到队尾就可以了。
  • 当前的索引为最长递增子序列中的值，也就是i === seq[j]，这说说明该节点不需要移动
  • 当前的索引不是最长递增子序列中的值，那么说明该 DOM 节点需要移动，这里也很好理解，我们也是直接将 DOM 节点插入到队尾就可以了，因为队尾是排好序的。

React

仅右移动
1648277673(1).png

附录

为什么同层比较

如果不同层比较的话，全部的对比完一整个 dom 结构，时间复杂度是 O(n^3) ; 时间成本太大了；所以改用同层比较这样的方法去牺牲了精度而提高了时间效率。

事件复杂度变成O(n)
image.png

为什么使用 key

  • 匹配了key，则之移动元素 — 性能较好
  • 未匹配key，则删除重建 — 性能较差

dom

  1. <div id="test">
  2.   <span style="color:red">test1</span> test2
  3. </div>
  5. var dom = document.getElementById('test');
  8. dom.innerHTML // <span style="color:red">test1</span> test2 
  10. dom.innerText // test1 test2
  12. dom.outerHTML //  <div id="test"><span style="color:red">test1</span> test2</div>
  14. dom..textContent // = innerText

https://github.com/Zheaoli/weekly-share/issues/17