乐趣区

关于vue.js:vue源码分析diff算法核心原理

这一节,仍然是 深刻分析 Vue 源码系列 ,上几节内容介绍了Virtual DOM 是 Vue 在渲染机制上做的优化,而渲染的外围在于数据变动时,如何高效的更新节点,这就是 diff 算法。因为源码中对于 diff 算法局部流程简单,间接分析每个流程不易于了解,所以这一节咱们换一个思路,参考源码来手动实现一个简易版的 diff 算法。

之前讲到 Vue 在渲染机制的优化上,引入了 Virtual DOM 的概念,利用 Virtual DOM 形容一个实在的 DOM, 实质上是在JS 和实在 DOM 之间架起了一层缓冲层。当咱们通过大量的 JS 运算, 并将最终后果反馈到浏览器进行渲染时,Virtual DOM能够将多个改变合并成一个批量的操作,从而缩小 dom 重排的次数,进而缩短了生成渲染树和绘制节点所花的工夫,达到渲染优化的目标。之前的章节,咱们简略的介绍了 VueVnode的概念,以及创立 Vnode渲染 Vnode再到实在 DOM 的过程。如果有遗记流程的,能够参考后面的章节剖析。

render 函数到创立虚构 DOM, 再到渲染实在节点,这一过程是残缺的,也是容易了解的。然而引入虚构DOM 的外围不在这里,而在于当数据发生变化时,如何最优化数据变动到视图更新的过程。这一个过程才是 Vnode 更新视图的外围,也就是常说的 diff 算法。上面跟着我来实现一个简易版的 diff 算法

8.1 创立根底类

代码编写过程会遇到很多根本类型的判断,第一步须要先将这些办法封装。

class Util {constructor() {}
  // 检测根底类型
  _isPrimitive(value) {return (typeof value === 'string' || typeof value === 'number' || typeof value === 'symbol' || typeof value === 'boolean')
  }
  // 判断值不为空
  _isDef(v) {return v !== undefined && v !== null}
}
// 工具类的应用
const util = new Util()

8.2 创立 Vnode

Vnode这个类在之前章节曾经剖析过源码,实质上是用一个对象去形容一个实在的 DOM 元素,简易版关注点在于元素的 tag 标签,元素的属性汇合 data, 元素的子节点children,text 为元素的文本节点, 简略的形容类如下:

class VNode {constructor(tag, data, children) {
    this.tag = tag;
    this.data = data;
    this.children = children;
    this.elm = ''
    // text 属性用于标记 Vnode 节点没有其余子节点,只有纯文本
    this.text = util._isPrimitive(this.children) ? this.children : ''
  }
}

8.3 模仿渲染过程

接下来须要创立另一个类模仿将 render 函数转换为 Vnode, 并将Vnode 渲染为实在 DOM 的过程,咱们将这个类定义为 Vn,Vn 具备两个根本的办法 createVnode, createElement, 别离实现创立虚构Vnode, 和创立实在DOM 的过程。

8.3.1 createVnode

createVnode模仿 Vuerender函数的实现思路,目标是将数据转换为虚构的Vnode, 先看具体的应用和定义。

// index.html

<script src="diff.js">
<script>

// 创立 Vnode

let createVnode = function() {  let _c = vn.createVnode;  return _c('div', { attrs: { id: 'test'} }, arr.map(a => _c(a.tag, {}, a.text)))}

// 元素内容构造
let arr =   [{tag: 'i',    text: 2}, {tag: 'span',    text: 3}, {tag: 'strong',    text: 4}]
</script>



// diff.js
(function(global) {
  class Vn {constructor() {}
    // 创立虚构 Vnode
    createVnode(tag, data, children) {return new VNode(tag, data, children)
    }
  }
  global.vn = new Vn()}(this))

这是一个残缺的 Vnode 对象,咱们曾经能够用这个对象来简略的形容一个 DOM 节点,而 createElement 就是将这个对象对应到实在节点的过程。最终咱们心愿的后果是这样的。

Vnode 对象

渲染后果

8.3.2 createElement

渲染实在 DOM 的过程就是遍历 Vnode 对象,递归创立实在节点的过程,这个不是本文的重点,所以咱们能够毛糙的实现。参考 Vue3 源码视频解说:进入学习

class Vn {createElement(vnode, options) {
      let el = options.el;
      if(!el || !document.querySelector(el)) return console.error('无奈找到根节点')
      let _createElement = vnode => {const { tag, data, children} = vnode;
        const ele = document.createElement(tag);
        // 增加属性
        this.setAttr(ele, data);
        // 简略的文本节点,只有创立文本节点即可
        if (util._isPrimitive(children)) {const testEle = document.createTextNode(children);
          ele.appendChild(testEle)
        } else {
        // 简单的子节点须要遍历子节点递归创立节点。children.map(c => ele.appendChild(_createElement(c)))
        }
        return ele
      }
      document.querySelector(el).appendChild(_createElement(vnode))
    }
}

8.3.3 setAttr

setAttr是为节点设置属性的办法,利用 DOM 原生的 setAttribute 为每个节点设置属性值。

class Vn {setAttr(el, data) {if (!el) return
    const attrs = data.attrs;
    if (!attrs) return;
    Object.keys(attrs).forEach(a => {el.setAttribute(a, attrs[a]);
    })
  }
}

至此一个简略的 数据 -> Virtual DOM => 实在 DOM 的模型搭建胜利, 这也是数据变动、比拟、更新的根底。

8.4 diff 算法实现

更新组件的过程首先是响应式数据产生了变动, 数据频繁的批改如果间接渲染到实在 DOM 上会引起整个 DOM 树的重绘和重排,频繁的重绘和重排是极其耗费性能的。如何优化这一渲染过程,Vue源码中给出了两个具体的思路,其中一个是在介绍响应式零碎时提到的将屡次批改推到一个队列中,在下一个 tick 去执行视图更新,另一个就是接下来要着重介绍的 diff 算法,将须要批改的数据进行比拟,并只渲染必要的DOM

数据的扭转最终会导致节点的扭转,所以 diff 算法的外围在于在尽可能小变动的前提下找到须要更新的节点,间接调用原生相干 DOM 办法批改视图。不论是实在 DOM 还是后面创立的 Virtual DOM, 都能够了解为一颗DOM 树,算法比拟节点不同时,只会进行同层节点的比拟,不会跨层进行比拟,这也大大减少了算法复杂度。

8.4.1 diffVnode

在之前的根底上,咱们实现一个思路,1 秒之后数据产生扭转。

// index.html
setTimeout(function() {arr = [{    tag: 'span',    text: 1},{tag: 'strong',    text: 2},{tag: 'i',    text: 3},{tag: 'i',    text: 4}]
  // newVnode 示意扭转后新的 Vnode 树
  const newVnode = createVnode();
  // diffVnode 会比拟新旧 Vnode 树,并实现视图更新
  vn.diffVnode(newVnode, preVnode);
})

diffVnode的逻辑,会比照新旧节点的不同,并实现视图渲染更新

class Vn {
  ···
  diffVnode(nVnode, oVnode) {if (!this._sameVnode(nVnode, oVnode)) {
      // 间接更新根节点及所有子节点
      return ***
    }
    this.generateElm(vonde);
    this.patchVnode(nVnode, oVnode);
  }
}

8.4.2 _sameVnode

新旧节点的比照是算法的第一步,如果新旧节点的根节点不是同一个节点,则间接替换节点。这听从下面提到的准则,只进行同层节点的比拟,节点不统一,间接用新节点及其子节点替换旧节点 。为了了解不便,咱们假设节点雷同的判断是tag 标签是否统一(理论源码要简单)。

class Vn {_sameVnode(n, o) {return n.tag === o.tag;}
}

8.4.3 generateElm

generateElm的作用是跟踪每个节点理论的实在节点,不便在比照虚构节点后实时更新实在 DOM 节点。尽管 Vue 源码中做法不同,然而这不是剖析 diff 的重点。

class Vn {generateElm(vnode) {const traverseTree = (v, parentEl) => {
      let children = v.children;
      if(Array.isArray(children)) {children.forEach((c, i) => {c.elm = parentEl.childNodes[i];
          traverseTree(c, c.elm)
        })
      }
    }
    traverseTree(vnode, this.el);
  }
}

执行 generateElm 办法后,咱们能够在旧节点的 Vnode 中跟踪到每个 Virtual DOM 的实在节点信息。

8.4.4 patchVnode

patchVnode是新旧 Vnode 比照的外围办法,比照的逻辑如下。

  1. 节点雷同,且节点除了领有文本节点外没有其余子节点。这种状况下间接替换文本内容。
  2. 新节点没有子节点,旧节点有子节点,则删除旧节点所有子节点。
  3. 旧节点没有子节点,新节点有子节点,则用新的所有子节点去更新旧节点。
  4. 新旧都存在子节点。则比照子节点内容做操作。

代码逻辑如下:

class Vn {patchVnode(nVnode, oVnode) {if(nVnode.text && nVnode.text !== oVnode) {
      // 以后实在 dom 元素
      let ele = oVnode.elm
      // 子节点为文本节点
      ele.textContent = nVnode.text;
    } else {
      const oldCh = oVnode.children;
      const newCh = nVnode.children;
      // 新旧节点都存在。比照子节点
      if (util._isDef(oldCh) && util._isDef(newCh)) {this.updateChildren(ele, newCh, oldCh)
      } else if (util._isDef(oldCh)) {// 新节点没有子节点} else {// 老节点没有子节点}
    }
  }
}

上述例子在 patchVnode 过程中,新旧子节点都存在,所以会走 updateChildren 分支。

8.4.5 updateChildren

子节点的比照,咱们通过文字和画图的模式剖析,通过图解的模式能够很清晰看到 diff 算法的奇妙之处。

大抵逻辑是:

  1. 旧节点的起始地位为oldStartIndex, 截至地位为oldEndIndex, 新节点的起始地位为newStartIndex, 截至地位为newEndIndex
  2. 新旧 children 的起始地位的元素两两比照,程序是newStartVnode, oldStartVnode; newEndVnode, oldEndVnode;newEndVnode, oldStartVnode;newStartIndex, oldEndIndex
  3. newStartVnode, oldStartVnode节点雷同,执行一次 patchVnode 过程,也就是递归比照相应子节点,并替换节点的过程。oldStartIndex,newStartIndex都像右挪动一位。
  4. newEndVnode, oldEndVnode节点雷同,执行一次 patchVnode 过程,递归比照相应子节点,并替换节点。oldEndIndex,newEndIndex都像左挪动一位。
  5. newEndVnode, oldStartVnode节点雷同,执行一次 patchVnode 过程,并将旧的 oldStartVnode 挪动到尾部,oldStartIndex右移一味,newEndIndex左移一位。
  6. newStartIndex, oldEndIndex节点雷同,执行一次 patchVnode 过程,并将旧的 oldEndVnode 挪动到头部,oldEndIndex左移一味,newStartIndex右移一位。
  7. 四种组合都不雷同,则会搜寻旧节点所有子节点,找到将这个旧节点和 newStartVnode 执行 patchVnode 过程。
  8. 一直比照的过程使得 oldStartIndex 一直迫近 oldEndIndexnewStartIndex 一直迫近 newEndIndex。当oldEndIndex <= oldStartIndex 阐明旧节点曾经遍历完了,此时只有批量减少新节点即可。当 newEndIndex <= newStartIndex 阐明旧节点还有剩下,此时只有批量删除旧节点即可。

联合后面的例子:

第一步:

第二步:

第三步:

第三步:

第四步:

依据这些步骤,代码实现如下:

class Vn {updateChildren(el, newCh, oldCh) {
    // 新 children 开始标记
    let newStartIndex = 0;
    // 旧 children 开始标记
    let oldStartIndex = 0;
    // 新 children 完结标记
    let newEndIndex = newCh.length - 1;
    // 旧 children 完结标记
    let oldEndIndex = oldCh.length - 1;
    let oldKeyToId;
    let idxInOld;
    let newStartVnode = newCh[newStartIndex];
    let oldStartVnode = oldCh[oldStartIndex];
    let newEndVnode = newCh[newEndIndex];
    let oldEndVnode = oldCh[oldEndIndex];
    // 遍历完结条件
    while (newStartIndex <= newEndIndex && oldStartIndex <= oldEndIndex) {
      // 新 children 开始节点和旧开始节点雷同
      if (this._sameVnode(newStartVnode, oldStartVnode)) {this.patchVnode(newCh[newStartIndex], oldCh[oldStartIndex]);
        newStartVnode = newCh[++newStartIndex];
        oldStartVnode = oldCh[++oldStartIndex]
      } else if (this._sameVnode(newEndVnode, oldEndVnode)) {
      // 新 childre 完结节点和旧完结节点雷同
        this.patchVnode(newCh[newEndIndex], oldCh[oldEndIndex])
        oldEndVnode = oldCh[--oldEndIndex];
        newEndVnode = newCh[--newEndIndex]
      } else if (this._sameVnode(newEndVnode, oldStartVnode)) {
      // 新 childre 完结节点和旧开始节点雷同
        this.patchVnode(newCh[newEndIndex], oldCh[oldStartIndex])
        // 旧的 oldStartVnode 挪动到尾部
        el.insertBefore(oldCh[oldStartIndex].elm, null);
        oldStartVnode = oldCh[++oldStartIndex];
        newEndVnode = newCh[--newEndIndex];
      } else if (this._sameVnode(newStartVnode, oldEndVnode)) {
        // 新 children 开始节点和旧完结节点雷同
        this.patchVnode(newCh[newStartIndex], oldCh[oldEndIndex]);
        el.insertBefore(oldCh[oldEndIndex].elm, oldCh[oldStartIndex].elm);
        oldEndVnode = oldCh[--oldEndIndex];
        newStartVnode = newCh[++newStartIndex];
      } else {
        // 都不合乎的解决,查找新节点中与比照旧节点雷同的 vnode
        this.findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      }
    }
    // 新节点比旧节点多,批量减少节点
    if(oldEndIndex <= oldStartIndex) {for (let i = newStartIndex; i <= newEndIndex; i++) {
        // 批量减少节点
        this.createElm(oldCh[oldEndIndex].elm, newCh[i])
      }
    }
  }

  createElm(el, vnode) {
    let tag = vnode.tag;
    const ele = document.createElement(tag);
    this._setAttrs(ele, vnode.data);
    const testEle = document.createTextNode(vnode.children);
    ele.appendChild(testEle)
    el.parentNode.insertBefore(ele, el.nextSibling)
  }

  // 查找匹配值
  findIdxInOld(newStartVnode, oldCh, start, end) {for (var i = start; i < end; i++) {var c = oldCh[i];
      if (util.isDef(c) && this.sameVnode(newStartVnode, c)) {return i}
    }
  }
}

8.5 diff 算法优化

后面有个分支,当四种比拟节点都找不到匹配时,会调用 findIdxInOld 找到旧节点中和新的比拟节点统一的节点。节点搜寻在数量级较大时是迟缓的。查看 Vue 的源码,发现它在这一个环节做了优化,也就是咱们常常在编写列表时被要求退出的惟一属性 key,有了这个惟一的标记位,咱们能够对旧节点建设简略的字典查问,只有有key 值便能够不便的搜寻到符合要求的旧节点。批改代码:

class Vn {updateChildren() {···} else {
      // 都不合乎的解决,查找新节点中与比照旧节点雷同的 vnode
      if (!oldKeyToId) oldKeyToId = this.createKeyMap(oldCh, oldStartIndex, oldEndIndex);
      idxInOld = util._isDef(newStartVnode.key) ? oldKeyToId[newStartVnode.key] : this.findIdxInOld(newStartVnode, oldCh, oldStartIndex, oldEndIndex);
      // 后续操作
    }
  }
  // 建设字典
  createKeyMap(oldCh, start, old) {const map = {};
    for(let i = start; i < old; i++) {if(oldCh.key) map[key] = i;
    }
    return map;
  }
}

8.6 问题思考

最初咱们思考一个问题,Virtual DOM 的重绘性能真的比单纯的 innerHTML 要好吗,其实并不是这样的,作者的解释

  • innerHTML: render html string O(template size) + 从新创立所有 DOM 元素 O(DOM size)
  • Virtual DOM: render Virtual DOM + diff O(template size) + 必要的 DOM 更新 O(DOM change)
  • Virtual DOM render + diff 显然比渲染 html 字符串要慢,然而!它仍然是纯 js 层面的计算,比起前面的 DOM 操作来说,仍然便宜了太多。能够看到,innerHTML 的总计算量不论是 js 计算还是 DOM操作都是和整个界面的大小相干,但Virtual DOM 的计算量外面,只有 js 计算和界面大小相干,DOM 操作是和数据的变动量相干的。
退出移动版