Vue2.x的diff算法记录

时间: 2020-03-19阅读: 984标签: 算法

起因

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

  1. 生成render函数(runtime版本不具备该功能需要用户传参render函数
  2. 生成VNode
  3. 将VNode渲染成真实DOM
  4. 监听数据变化
  5. 生成新的VNode
  6. 新旧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
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

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

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

js实现:在字符串中找出第一个只出现一次的字符

在给出一个字符串,找出第一个只出现一次的字符。思路分析:可以用对象保存字符出现的次数。将值删除,用 indexOf 查找还有没有相同字符,并查找之前删过的字符,indexOf 的第二个参数,从当前值往后搜索,并查找之前已经查过的字符

用 Javascript 写排序算法

至于为什么选择用 Javascript,则是因为我觉得 Javascript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况

迭代算法

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题

用js在控制台打印九九乘法表

不管是打印什么样三角形九九乘法表,我们都应该找到有规律的地方,比如第一列的数字是什么规律,第一行的数字是什么规律,只要找到了共性,九九乘法表就很简单

js二分查找算法

二分查找高效的前提是数据结构是有序的。就好比猜1~100之间的数,先猜50,如果太大了就猜25,如果太小了就猜75.每一次都猜最大值和最小值的中间点.

现在算法是新锐前端框架成功的重要因素

随着前端MVVM的流行,小型框架现在越来越难存活了!react, angular等打着大公司旗号的框架占了半壁江山,而avalon以其良好兼容性在国内份额不断上升。前端也与后端一样,遵循马太效应,强者愈强,弱者愈弱。最后只剩下两种框架

Js七种排序算法

冒泡排序的思路:遍历数组,然后将最大数沉到最底部;<br/>时间复杂度:O(N^2);<br/>空间复杂度:O(1);选择排序的实现思路:遍历数组,把最小数放在头部;

JavaScript 实现归并排序

在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。

js实现分解质因数

定义一个数组,用来存放因数; 定义数组里面数的位置的起始值0;定义分解质因数的函数;如果被分解的数为1、2、3,则直接存入数组,并返回结果

点击更多...

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