关闭

Vue2.x的diff算法记录

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

起因

为什么在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.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

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

关闭

JavaScript实现获取两个排序数组的中位数算法示例

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 不同时为空。

Js集合的实现与应用

与数学中的集合概念类似,集合由一组无序的元素组成,且集合中的每个元素都是唯一存在的。可以回顾一下中学数学中集合的概念,我们这里所要定义的集合也具有空集(即集合的内容为空)、交集、并集、差集、子集的特性

从js讲解时间复杂度和空间复杂度

今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客;复杂度的表示方式之前有看过的,你可能会看到这么一串东西

RSA 背后的算法

随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

用 Javascript 写排序算法

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

一些常用的语音特征提取算法

语言是一种复杂的自然习得的人类运动能力。成人的特点是通过大约100块肌肉的协调运动,每秒发出14种不同的声音。说话人识别是指软件或硬件接收语音信号,识别语音信号中出现的说话人,然后识别说话人的能力

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

细数20世纪最伟大的10大算法

在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,现在要计算这个不规则图形的面积,怎么计算列?

最短编辑距离

1.第一行表示从ME到空字符所要删除的字符的所以情况 2.第一列表示从空字符到MY所需要插入字符的所有情况 3.斜箭头表示相同字符不需要替换,不相同字符所有替换次数的所有情况

点击更多...

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