• diff算法是vdom中最核心、最关键的部分
  • diff算法能在日常使用vue react体现出来（如key）

概述

  • diff即对比，是一个广泛的概念，如Linux diff命令、git diff等
  • 两个js对象也可以做diff，如https://github.com/cujojs/jiff
  • 两颗树做diff，如这里的vdom diff

截屏2020-10-19 下午7.32.54.png

树 diff 的时间复杂度 O(n^3)

  • 遍历🌲1，遍历🌲2
  • 排序

  • 1000个节点，要计算1亿次，算法不可用

    优化时间复杂度 O(n)

  • 只比较同一级，不跨级比较

  • tag不相同，则直接删掉重建，不再深度比较
  • tag和key相同，两者都相同，则认为是相同的节点，不再深度比较

截屏2020-10-19 下午7.42.20.png
截屏2020-10-19 下午7.43.07.png
截屏2020-10-19 下午8.37.31.png

snabbdom 原理解读

来感受 虚拟dom 对比的过程

  1. // 只传递sel参数
  2. export function h (sel: string): VNode
  3. ...
  4. // 常用的是sel data children都传递
  5. export function h (sel: string, data: VNodeData | null, children: VNodeChildren): VNode
  7. // 这个h函数返回的是 一个vnode 虚拟节点
  8. return vnode(sel, data, children, text, undefined)
  10. // 让我们再打开vnode函数
  11. export function vnode (sel: string | undefined,
  12.   data: any | undefined,
  13.   children: Array<VNode | string> | undefined,
  14.   text: string | undefined,
  15.   elm: Element | Text | undefined): VNode {
  16.   const key = data === undefined ? undefined : data.key
  17.   // 只看返回的是什么，是一个对象
  18.   /*
  19.       其中children和text不共存，要不子元素是标签，要不没有子元素，里面是文本
  20.     elm 是这个虚拟dom要渲染到哪个元素下去的
  21.     key 
  22.   */
  23.   return { sel, data, children, text, elm, key }
  24. }
  26. /* 再看patch */
  27. return function patch (oldVnode: VNode | Element, vnode: VNode): VNode {
  28.     .
  29.     .
  30.     .
  31.     // 执行pre hook，生命周期的钩子函数
  32.     for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
  34.       // 第一个参数不是vnode，就是初次渲染，要渲染到dom元素下
  35.     if (!isVnode(oldVnode)) {
  36.       // 创建一个空的vnode 并且关联到这个dom元素下
  37.       oldVnode = emptyNodeAt(oldVnode)
  38.     }
  40.       // 相同的vnode
  41.       /*
  42.         sameVnode的内部是
  43.       return vnode1.key === vnode2.key && vnode1.sel === vode2.sel
  44.       就是之前说的虚拟dom的diff算法如果一个节点的tag（sel）和key相等，就认为他是相同的vnode
  45.         假如 key 都不传， undefined === undefined 是true
  46.     */
  47.     if (sameVnode(oldVnode, vnode)) {
  48.       // vode对比
  49.       patchVnode(oldVnode, vnode, insertedVnodeQueue)
  51.     // 不同的vnode，直接删除重建
  52.     } else {
  53.       elm = oldVnode.elm!
  54.       parent = api.parentNode(elm) as Node
  56.       // 用vnode重建
  57.       createElm(vnode, insertedVnodeQueue)
  59.       。
  60.       。
  61.       。
  62.       。
  63.     return vnode
  64.   }
  66.   /* 打开patchVode */
  67.   function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue){
  69.     // 类似于vue的生命周期的钩子
  70.       const hook = vnode.data?.hook
  71.     hook?.prepatch?.(oldVnode, vnode)
  73.     //  新的来了，就把就得elm存起来
  74.     const elm = vnode.elm = oldVnode.elm!
  76.        // 新旧children
  77.     const oldCh = oldVnode.children as VNode[]
  78.     const ch = vnode.children as VNode[]
  80.     // 如果新的vnode的text是undefined，则意味着children是有值的
  81.     if (isUndef(vnode.text)) {
  83.       // 新旧都有children
  84.       if (isDef(oldCh) && isDef(ch)) {
  85.         if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
  86.       // 新children有，旧children无，
  87.       } else if (isDef(ch)) {
  88.         // 如果旧text有值就情况
  89.         if (isDef(oldVnode.text)) api.setTextContent(elm, '')
  90.         // 然后把新的Children添加，addVnode就是dom操作
  91.         addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  92.       // 旧的有children，新的没有，那就移除旧的children
  93.       } else if (isDef(oldCh)) {
  94.         removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  95.       } else if (isDef(oldVnode.text)) {
  96.         api.setTextContent(elm, '')
  97.       }
  99.     // 有文本值，children是无值的
  100.     } else if (oldVnode.text !== vnode.text) {
  101.       if (isDef(oldCh)) {
  102.         removeVnodes(elm, oldCh, 0, oldCh.length - 1)
  103.       }
  104.       // 新旧text不一样，那就把旧的children移除，再设置新的文本
  105.       api.setTextContent(elm, vnode.text!)
  106.     }
  107.     hook?.postpatch?.(oldVnode, vnode)
  108.   }
  1. // 对应使用方式
  2. var vnode = h('div#container.two.classes', { on: { click: someFn } }, [
  3.   h('span', { style: { fontWeight: 'bold' } }, 'This is bold'),
  4.   ' and this is just normal text',
  5.   h('a', { props: { href: '/foo' } }, 'I\'ll take you places!')
  6. ])

总的来说
h函数，用来根据传入的参数，生成对应的dom节点
patch函数，用来把新旧vnode对比完成，生成且去渲染计算好的dom
patchVode函数，两个vnode节点的一些判断。
比如先判断两个vode的sel和key是否一致
一致：那就继续判断children
不一致：删除重建dom元素

两个nvode的sel和key一样了，去看看children是否一样
新children有值，旧children无值，清空旧的文本内容，插入新的内容
新children无值，旧children有值，移除旧的节点，插入新的文本
新旧Children都有值，那就是要进行对比了。就是接下来对比的函数

updateChildren(elm, oldchildren, newchildren)
截屏2020-10-20 下午6.47.55.png
截屏2020-10-20 下午6.48.47.png
定义一个循环，当两边指针从外到内，碰到之后，循环结束。
进行特殊命中判断 （对比用的是 sel和key）
oldStart 和 newStart 对比一次
或者 oldend和newend
或者 oldstart和newend
或者 oldend和newstart对比
这四个都是尝试对比，命中就抛给patchvnode去处理
如果以上四个都没命中，这个方式是snabbdom的写法，在各种框架中对比方式各有不同
拿新节点的key能否对应上old节点中的key
就是对其它所有节点做对比，看是否能对应上，如果新的一圈下来，发现没有old对应上，那这个就是全新的节点，插入就行
如果对应上了，那就判断sel是否一致，不一致还是新建节点
一致，那就是一样的节点，交给patchVnode去处理。