传统diff算法复杂度o(n^3)

对比两棵树所有的节点，传统的方式一次比较两棵树的每一个节点，时间复杂度为o(n^2)。比较完之后，再把找到的差异循环更新（移动，创建，删除时需要遍历一次）到都没上去，又有循环一次，所以总的时间复杂度为o(n^3)

三个层级

  • Tree Diff（层级比较）
    • 先进行树结构的层级比较，对同一个父节点下的所有子节点进行比较；
    • 接着看节点是什么类型的，是组件就做 Component Diff;
    • 如果节点是标签或者元素，就做 Element Diff;
  • Component Diff （组件比较）
    • 若组件类型相同，则继续按照层级比较其虚拟 DOM的结构;
    • 如果组件类型不同，则替换整个组件的所有内容

  • Element Diff (元素比较)
    • 如果节点是原生标签，则看标签名做比较是否相同来决定替换还是更新属性
    • 然后进入标签后代递归 Tree Diff

    步骤

  • patch(oldVnode,newVnode)

  • 打补丁，把新节点变化的内容渲染到真实DOM
  • 对比新旧节点是否是相同的节点
  • 如果不是相同节点，删除之前的内容，重新渲染
  • 如果是相同节点，再判断新的vnode是否有text，如果有并且和oldVnode的text不同，直接更新文本
  • 如果新的Vnode有children，判断子节点是够有变化，递归调用patchVnode

  • diff过程只进行同层级比较，时间复杂度为o(n)

    patch

    功能：

  • 传入新的Vnode，对比差异，把差异渲染到DOM

  • 返回新的Vnode，作为下一次patch的oldVnode

执行过程

  • 首先执行模块中的钩子函数pre
    • 如果oldVnode和vnode相同
      • 调用patchVnode，找到节点并更新DOM

  • 如果oldVnode是DOM元素

    • 把DOM元素转换成oldVnode，
    • 调用creatElement把vnode转换成真实的DOM，记录到vnode.elm
    • 把刚创建的DOM元素插入到parent中
    • 移除老节点

      patchVnode

      功能：
      对比新街差异，把差异渲染到DOM
      执行过程

  • 首先执行用户设置的prepatch钩子函数

  • 执行create钩子函数
    • 首先执行模块的create钩子函数
    • 然后执行用户设置的create钩子函数
  • 如果vnode.text未定义
    • 如果oldVnode.children和vnode.children都有值
      • 调用updateChildren()
      • 使用diff算法对比子节点，更新子节点
    • 如果vnode.children有值，oldVnode.children无值
      • 清空DOM元素
      • 调用addVnodes，批量添加子节点
    • 如果oldVnode.children有值，vnode.children无值
      • 调用removeVnodes，批量移除子节点
    • 如果oldVnode.text有值
    • 清空DOM元素的内用
  • 如果vnode.text有值，并且和oldVnode。text不等
    • 如果老节点有子节点，全部移除
    • 设置DOM元素的textContent为vnode.text

  • 最后执行用户设置的postpatch钩子函数

    updateChildren

    功能：

  • diff算法的核心，对比新旧节点的children，更新DOM

执行过程：

  • 在进行同级比较的时候，首先会对新老节点数组的开始和结尾节点设置标记索引，遍历的过程中移动索引
  • 在开始和结束节点对比的时候，总共有四种情况
    • 旧开始节点和新开始节点
    • 旧结束节点和新结束节点
    • 旧开始节点和新结束节点
    • 旧结束节点和新开始节点
  • 如果oldVnode和newVnode是sameVnode
    • 调用patchVnode进行和更新节点
    • 同时把移动新旧节点的索引
  • 如果不是以上四种情况
    • 遍历新节点，使用newStartNode的key在老节点数组中找到相同节点
    • 如果没有找到，说明newStartNode是新节点
      • 创建新节点对应的DOM于是怒，插入到DOM树中
    • 如果找到了
      • 判断新节点和找到的老节点的sel选择器是否相同
      • 如果不相同，说明改节点被修改了
        • 重新创建对应的DOM元素，插入到DOM树中
      • 如果相同，把eleToMove对应的元素，移动到左边
  • 循环结束

当老节点的所有子节点先遍历完，循环结束，说明新节点有剩余，把剩余节点批量插入到右边
当新节点的所有子节点先遍历完，循环结束，说明老节点有剩余，直接把老节点的剩余节点删除。