Vue2.x的diff算法记录

起因

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

生成render函数（runtime版本不具备该功能需要用户传参render函数）
生成VNode
将VNode渲染成真实dom
监听数据变化
生成新的VNode
新旧VNode对比并更新页面

大体分为以上几点（可能是我还没看完全代码，有遗漏的地方希望大佬不吝赐教）。那其实完全可以挑选自己感兴趣的点去查看源码并学习。我目前也阅读了大部分的源码，对第六点即patch的过程做下记录。

准备工作

我们使用vue-cli拉去下2.x的模板，并简单的写下以下代码：

// main.js
new Vue({
  el: '#app',
  data() {
    return {
      list: [1, 2, 3, 4]
    }
  },
  render(h) {
    return h(
      'ul',
      {
        class: 'c-ul'
      },
      this.list.map(_ => h('li', { key: _ }, _))
    )
  },
  mounted() {
    this.list = [2, 5, 3, 6, 7, 1]
  }
})

手动编写render函数的原因是不希望设计到compiler，render给了开发者可以直接编写VNode的能力，以上demo在一开始页面会按照 [1, 2, 3, 4] 的顺序进行列表渲染并记录oldVNode，在mounted生命周期中list被改变，此时会重新生成newVNode，然后将新旧VNode进行patch操作，这篇文章主要讲下这个操作。

VNode

大家可以运行起demo项目然后在控制台中打上断点看看VNode的数据结构是怎么样的，这里我直接上图。

上图是第一次渲染的oldVNode，我们精简一下该VNode数据结构如下：

// oldVNode
let oldVNode = {
  tag: 'ul',
  data: {
    class: 'c-ul'
  },
  children: [
    {
      tag: 'li',
      data: {
        key: 1
      },
      children: [
        {
          tag: undefined,
          text: 1
        }
      ]
    },
    {
      tag: 'li',
      data: {
        key: 2
      },
      children: [
        {
          tag: undefined,
          text: 2
        }
      ]
    },
    // 同上结构共有4个 tag 为 li 的VNode 作为children
  ]
}

而同样的操作在mounted生命周期调用后也会生成一个VNode，结构与上完全相同，只不过 newVNode.children 内容变化：

let oldVNode = {
  tag: 'ul',
  data: {
    class: 'c-ul'
  },
  children: [
    {
      tag: 'li',
      data: {
        key: 2
      },
      children: [
        {
          tag: undefined,
          text: 2
        }
      ]
    },
    {
      tag: 'li',
      data: {
        key: 5
      },
      children: [
        {
          tag: undefined,
          text: 5
        }
      ]
    },
    // 同上结构共有6个 tag 为 li 的VNode 作为children
  ]
}

那么有了这两个VNode对象，我们就可以对其进行比较。注意此时oldVNode中的每个VNode对象都有对起真实dom节点的引用，如：oldVNode.elm

patchVNode

其实在进入patchVNode前，Vue会对两个VNode调用sameVNode方法，判断其是否有patch的必要，而sameVNode的逻辑简单来说是key相同、tag相同、是否同（不）为注释节点、是否同时（未）定义data对象还有对input的判断，这里我们引用的例子显然是返回的true，具体的sameVNode逻辑读者自行查看。

// patchVNode()
function patchVnode (
    oldVNode,
    newVNode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
)  {
    const elm = newVNode.elm = oldVNode.elm
    // 省略
    if (isUndef(newVNode.text)) {
        if (isDef(newVNode.children) && isDef(oldVNode.children)) { // 若新旧VNode都有children
            updateChildren(elm, oldVNode.children, newVNode.children) // 对比children
        } else if (isDef(newVNode.children)) { // 若newVnode有children而oldVNode没有
            // 进行添加节点工作
            if (isDef(oldVNode.text)) { // 若oldVNode有text说明其子节点原先是文本，需要清空文本
                setTextContent(elm, '')
            }
            addVNodes() // 将newVNode的Children添加到dom元素中
        } else if (isDef(oldVNode.children)) { // 如果oldVNode有children而newVNode没有
            removeVNodes()// 将原先的Children删除掉
        }
    } else if (oldVNode.text !== newVNode.text) {
        setTextContent(elm, newVNode.text)
    }
}

在进入方法一开始便让newVNode.elm指向oldVNode.elm，这里能够这样赋值是因为在进入patchVNode前两个VNode就已经经过了sameVNode判断，它们是拥有同样tag的VNode（同为ul）所以这里可以直接让newVNode.elm就复用oldVNode.elm。

然后判断newVNode.text 是否存在，如果存在说明其子节点只有文本内容，而又如果oldVNode的文本内容（可能为空或非空）不于oldVNode.text，那么直接进行textContent替换即可完成patch过程。

而另外一个分支即判断newVNode 和 oldVNode 的children的情况，其中如果单方面拥有children（即一个有一个没有）则要么进行节点的删除，要么进行节点的添加。而如果都有children，则需要updateChildren。

updateChildren

这一部分其实才是diff的真正流程。因为这里涉及到两个VNode数组的对比。
我们在了解diff算法之前考虑下面这个问题：

updateChildren的目的就是将newChildren数组里的VNode渲染成真是dom元素，然后将原来已经根据oldChildren数组里的VNode渲染出来的dom元素替换掉，那最简单的方法是什么？

毫无疑问最简单的本法是先删除，再新增：

function updateChildren(parentElm, oldCh, newCh) {
    // 先将原有的元素全部删除
    for (let i = 0, l = oldCh.length; i < l; i++) {
        parentElm.removeChild(oldCh[i].elm)
    }
    // 将新的VNode渲染成dom并添加到文档流中
    for (let i = 0, l = newCh.length; i < l; i++) {
        parentElm.append(createElm(newCh[i]))
    }
}

以上方法是可行的，但是会有性能问题，为什么需要使用VDOM就是因为频繁操作dom节点是一件耗费性能的事情，如果只是简单的删除替换，根本不需要用到VNode，可以是任何一个记录tag和children的另一种数据结构代替，所以我们不能采用上述的方法来进行updateChildren，因为会存在可复用的元素。

那什么是可复用的元素呢：其实就是能通过sameVNode判断的两个VNode就是可复用的。这里再做下记录：sameVNode只关注VNode本身而不关注其children。如果通过了sameVNode那么两个VNode的tag是相同的，key也是相同的，那么很大概率可以直接复用，或者是简单的对VNode进行一下patch就可以复用。如何去对比两个数组，并找出可复用的元素其实就是diff算法的目的。

那么如何实现diff算法呢？Vue采用的是双端diff。

以上dom表示真实渲染的dom节点，oldCh表示原先的vnode数组，newCh表示心的vnode数组。

而双端的意思就是对oldCh和newCh同时从数组的两个端开始进行比较，会出现一下几种情况

function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0
    let oldEndIdx = oldCh.length - 1
    let newStartIdx = 0
    let newEndIdx = newCh.length - 1
    let oldStartEl = oldCh[oldStartIdx]
    let oldEndEl = oldCh[oldEndIdx]
    let newStartEl = newCh[newStartIdx]
    let newStartEl = newCh[newEndIdx]
    
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdex) {
        if (isUndef(oldStartEl)) {
            oldStartIdx++  
        } else if (isUndef(oldEndEl)) {
            oldEndIdx--
        } else if (sameVNode(oldStartEl, newStartEl)) {
            // 若两个开始元素相同，则只需要patchNode而不需要移动元素
            patchVNode(oldStartEl, newStartEl)
            oldStartIdx++
            newStartIdx++
        } else if (sameVNode(oldEndEl, newEndEl)) {
            // 若尾部元素相同，同上
            patchVNode(oldEndEl, newEndEl)
            oldEndIdx--
            startEndIdx--
        } else if (sameVNode(newStartEl, oldEndEl)) {
            // 若旧尾部元素与新首部元素相同，则需要移动节点再进行patchNode
            // 需要将oldEndEl指向的真实dom元素移到目前oldStartEl指向的元素之前
            parentElm.insertBefore(oldEndEl.elm, oldStartEl.elm)
            patchVNode(oldEndEl, newStartEl)
            newStartIdx++
            oldEndIdx--
        } else if (sameVNode(newEndEl, oldStartEl)) {
            // 若旧首部元素与新尾部元素相同，同上，只不过移动元素的方向变成了将oldStartEl指向的元素往后移
            parentElm.insertBefore(oldStartEl.elm, oldEndEl.elm.nextSibling)
        } else {
            // 如果双端的四个元素对比结束都不匹配，并没有说明新的开始节点就完全找不到复用，就像 el-2 的key是2，这时候应该去oldCh中找到key相同的节点，然后sameVNode判断
            let vnodeToMove = oldCh.findIndex(vnode => vnode.key === newStartEl.key)
            if (vnodeToMove >= 0) {
                // 若找到了key相同的节点
                if (sameVNode(vnodeToMove, newStartEl)) {
                    // 可以复用，移动元素
                    patchVNode(vnodeToMove, newStartEl)
                    parentElm.insertBefore(oldCh[vnodeToMove].elm, oldStartEl.elm)
                    oldCh[vnodeToMove] = undefined
                } else {
                    // 没找到，这是才需要真正新建一个dom元素
                    createElm(newStartEl, parentElm, oldStartEL.elm, newCh, vnodeToMove) // 表示将 vnodeToMove 这个下标的VNode渲染成真实dom并插入到parentElm的oldStartEl.elm之前
                }
            } else {
                // 如果没找到相同的key，与找到了key但是没通过sameVNode的检测一样操作，新建
                createElm(newStartEl, parentElm, oldStartEL.elm, newCh, vnodeToMove)
            }
        }
    }
    // 如果oldCh没有遍历完
    if (newStartIdx > newEndIdx) {
        // 删除旧节点
        removeVNodes(oldCh, oldStartIdx, oldEndIdx)
    }
    // 如果newCh没有遍历完
    if (oldStartIdx > oldEndIdx) {
        // 添加新节点
        addVNodes(newCh, newStartIdx, newEndIdx)
    }
}

后记

以上代码主要是给自己看的，大部分与源码相同，但是比如insertBefore等操作，由于Vue是由weex平台和web平台，所以其采用的设计模式是注入了这些操作，我自行改成了web平台的操作。

原文：https://segmentfault.com/a/1190000022093495

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