【Vue】源码—虚拟DOM和diff算法


theme: smartblue

github源码链接:虚拟DOM和diff算法

1.理解虚拟DOM和diff算法

1.1什么是虚拟DOM?

从本质上来说,虚拟DOM是一个JavaScript对象,通过对象的方式来表示DOM结构。将页面状态抽象为JS对象的形式,配合不同的渲染工具,使跨平台渲染成为可能。虚拟DOM是DOM的抽象,这个对象是更加轻量级的对DOM的描述。

1.2 为什么要用虚拟DOM?

1. 保证性能下限,在不进行手动优化的情况下,提供过得去的性能。

对比一下修改DOM时真实DOM操作和虚拟DOM的过程,来看一下它们重排重绘的性能消耗:

  • 真实DOM:生成HTML字符串+重建所有的DOM元素
  • 虚拟DOM:生成vNode+DOMdiff+必要的dom更新

虚拟DOM的更新DOM的准备工作耗费更多的时间,也就是JS层面,相比于更多的DOM操作它的消费是极其便宜的。尤雨溪在社区论坛中说道:框架给你的保证是,你不需要手动优化的情况下,依然可以给你提供过得去的性能。

2. 跨平台

虚拟DOM本质上是JavaScript的对象,它可以很方便的跨平台操作。比如服务器渲染、uniapp等

1.3diff算法简介

新虚拟DOM和旧虚拟DOM进行diff(精细化比较),算出应该如何最小量更新,最后反映到真正的DOM上【虚拟节点变成DOM节点】在Vue里面叫做patch

1.4diff算法原理

在新老虚拟DOM进行对比:

  • 首先,对比节点本身,判断是否为同一节点,如果不为相同节点,则删除该节点重新创建节点进行替换
  • 如果为相同节点,进行patchVnode,判断如何对该节点的子节点进行处理,先判断一方有子节点一方没有子节点的情况(如果新的children没有子节点,将旧的子节点移除)
  • 比较如果都有子节点,则进行updateChildren,判断如何对这些新老节点的子节点进行操作(diff核心)
  • 匹配时,找到相同的子节点,递归比较子节点

在diff中,只对同层的子节点进行比较,放弃跨级的节点比较,使得时间复杂度降低至O(n),也就是说只有当新旧children都为多个子节点时才需要用diff算法进行精细化比较。

1.5diff算法什么时候执行?

在页面首次渲染的时候会调用一次patch并创建新的vnode,不会进行更深层次的比较

然后在组件中数据发生变化时,会触发setter然后通过notify通知Watcher,对应的Watcher会通知更新并执行更新函数,它会执行render函数获取新的虚拟DOM,然后执行patch对比上次渲染结果的老的虚拟DOM,并计算出最小的变化,然后再去根据这个最小的变化去更新DOM

1.6diff算法的优化

1.只比较同一层级,不跨级比较

diff过程只会把同颜色并且同一层级的DOM进行比较,这样能够简化比较次数

2.比较标签名

如果同一层级的标签名不同,就直接移除老的虚拟DOM对应的节点,不继续按这个树状结构左深度比较。

3.比较key

如果标签名相同,key也相同,就会认为是相同节点,也不继续按这个树状结构做深度比较。

key的作用

比如有一个列表,我们需要在中间插入一个元素,会导致后面的元素进行重新渲染。如图li1,li2不会重新渲染,li3,li4,li5都会重新渲染。

因为在不使用key或列表的index作为key的时候,每个元素对应的位置关系都是index,上图中的结果导致我们插入的元素到后面的全部元素,对应的位置关系都发生了变更,所以全部都会执行更新操作,而我们希望的是只渲染添加的元素,其他的元素不再进行重新渲染。

而再使用唯一key的情况下,每个元素对应的位置关系都是key,看一下使用唯一key值的情况下,这样图中的li3和li4就不会重新渲染,因为元素内容没有发生改变,对应的位置关系也没有发生改变。

因此,不建议使用index作为key

原因是:使用index作为key和没写基本上没区别。因为不管数组的顺序怎么颠倒,index都是0,1,2…这样排列,导致Vue会复用错误的旧子节点,做很多额外的工作。

总结:

  • 在diff算法中,key是vnode的唯一标记,key的作用主要是为了更高效的更新虚拟DOM,因为它可以非常精确的找到相同节点,因此patch过程会非常高效
  • Vue在patch过程中会判断两个节点是不是相同的节点时,key是一个必要条件。在渲染列表时,如果不写key,Vue在比较的时候,就可能会导致频繁更新元素,使整个patch过程比较低效,影响性能。
  • 应该避免使用数组下标作为key,因为key值不是唯一的话,也可能会出现上面图中的问题,还有比如在使用相同标签元素过渡切换的时候,就会导致只替换其内部属性,而不会触发过渡效果。这个时候key的作用是用来表示一个独立的元素。
  • Vue判断两个节点是否相同时,主要判断两者的元素类型和key等。因为带key就不是就地复用。在checkSameVnode函数中a.key===b.key对比中可以避免就地复用。所以会更加准确。

2.实现虚拟DOM和diff算法

3.1h函数【简易版】

用来产生虚拟节点(vnode)

  1. 判断第三个参数是否是一个字符串或是数字。如果是字符串或数字,直接返回vnode
  2. 判断第三个参数是否是一个数组。声明一个数组,用于存储子节点,需要遍历数组,这里需要判断每一项是否是一个对象(因为vnode返回一个对象并且一定会有sel属性),但是不需要执行每一项,因为在数组中已经执行了h函数。其实,并不是函数递归进行调用(自己调用自己),而是一层一层的嵌套
  3. 判断第三个参数是否是一个对象。直接将这个对象赋值给children,并返回vnode
import vnode from './vnode';

// 这个函数必须接受3个参数,缺一不可
// 相当于它的重载功能较弱
/*
*  也就是说,调用的时候形态必须是下面的三种之一:
*  形态一:h('div', {}, '文字');
*  形态二:h('div', {}, []);
*  形态三:h('div', {}, h());
*/
export default function(sel, data, c) {
  // 检查参数的个数
  if(arguments.length != 3) {
    throw new Error('h() takes exactly 3 arguments');
  }
  // 检查参数c的类型
  if(typeof c == 'string' || typeof c == 'number') {
    // 说明现在调用h函数是形态一
    return vnode(sel, data, undefined, c, undefined);
  } else if(Array.isArray(c)) {
    // 说明现在调用h函数是形态二
    let children = [];
    // 遍历c,收集children
    for(let i = 0; i < c.length; i++) {
      // 检查c[i]必须是一个对象, 如果不满足
      if(!(typeof c[i] == 'object' || c.hasOwnProperty('sel'))) {
        throw new Error('h() takes an array of objects or selectors');
      }
      children.push(c[i]);
    }
    // 循环结束了,就说明children收集完毕,此时可以返回虚拟节点,有children属性
    return vnode(sel, data, children, undefined, undefined);
  } else if(typeof c == 'object' && c.hasOwnProperty('sel')) {
    // 说明现在调用h函数是形态三
    // 传入的c是唯一的children,不用执行c,因为测试语句中已经执行了c
    let children = [c];
  } else {
    throw new Error('此h函数必须传入三个参数')
  }
}

3.2vnode函数

用于创建虚拟节点

export default function(sel, data, children, text, elm) {
  const key = data.key;
  // sel 选择器, data 属性, children 子节点,text 文本内容, elm 虚拟节点绑定的真实DOM节点
  return {
    sel,
    data,
    children,
    text,
    elm,
    key
  }
}

3.3patch函数

首先判断旧节点是否是虚拟节点,不是则将旧节点变为虚拟节点【vnode函数】,如果是则判断是否是同一个节点类型,在这个判断中是则进行精细化比较,不是则进行暴力删除

import vnode from "./vnode";
import createElement from "./createElement";
import patchVnode    from "./patchVnode";
export default function(oldVnode, newVnode) {
  // 判断传入的第一个参数,是DOM节点还是虚拟节点?
  if(oldVnode.sel == '' || oldVnode.sel == undefined) {
    // 传入的第一个参数是DOM节点,此时要包装为虚拟节点
    // toLowerCase()变成小写字母
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
  }
  // 判断oldVnode和newVnode是不是同一个节点
  if(oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
    patchVnode(oldVnode, newVnode);
  } else {
    console.log('暴力插入新的,删除旧的');
    // 需要.elm得到  
    let newVnodeElm = createElement(newVnode);
    if(oldVnode.elm.parentNode && newVnodeElm) {
      // 插入到老节点之前
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
    }
    // 删除老节点
    oldVnode.elm.parentNode.removeChild(oldVnode.elm);
  }
}

补充知识

appendChild():

是在父节点中的子节点列表的末尾添加新的节点(相对于父节点来说)【添加后属于父子关系

insertBefore():

是在已有的节点前添加新的节点(相对于子节点来说)【添加后属于兄弟关系

parentNode属性:

该属性可指定元素对象后获取该元素的父节点元素

3.4createElement函数

将vNode转换为真实DOM【上树】

  • 首先获取新虚拟节点的sel属性,并且为他创建真实的DOM节点
  • 紧接着判断是有子节点还是有文本,文本直接进行上树
  • 如果是是子节点,则进入for循环中,获取children中的第一项,并调用createElement函数为该子节点创建真实DOM,执行完第一项返回创建的虚拟DOM,然后使用appendChild方法追加到domNode【最开始创建的的真实DOM】,依次类推,执行后面的数组项。
  • 最后,将创建好的所有真实的DOM返回回去,在patch函数中进行上树
//真正创建节点.将vnode创建为DOM
export default function createElement(vnode){
  //创建一个DOM节点,现在这个节点还是孤儿节点,不进行插入
  let domNode = document.createElement(vnode.sel)
  //有子节点还是有文本
  if(vnode.text != '' && (vnode.children == undefined || vnode.children.length == 0)){
    //文本-使用innerText直接进行上树
    domNode.innerText = vnode.text;
    
  }else if(Array.isArray(vnode.children) && vnode.children.length > 0){
    //内部是子节点,就要递归创建节点
    for(let i =0 ;i<vnode.children.length;i++){
      //得到当前这个children
      let children = vnode.children[i];
      console.log(children);
      //创建出它的DOM,一旦调用createElement意味着:创建出DOM了,并且他的elm属性指向了
      //创建出的DOM,但是还没有上树,是一个孤儿节点
      let chDOM = createElement(children);
      //上树
      domNode.appendChild(chDOM)
    }
  }
  //补充elm属性
  vnode.elm = domNode;
  //返回elem,elm属性是个纯DOM对象
  return vnode.elm;
}

3.5patchVnode函数

patchVnode函数的主要作用是:

  • 首先判断newVnode和oldVnode是否指向同一个对象,如果是,则直接return
  • 如果它们都有text并且都不相等或者oldVnode有子节点而newVnode没有,那么将oldVnode.elm的文本节点设置为newVnode的文本节点
  • 如果oldVnode没有子节点而newVnode有,则将newVnode的子节点变成真实DOM之后添加到oldVnode.elm后面
  • 如果两者都有子节点,则执行updateChildren函数比较子节点-四种优化策略 【重要!!!】
import createElement from "./createElement.js";
import updateChildren from './updateChildren.js'

//对比同一个虚拟节点
export default function patchVnode(oldVnode,newVnode){
  //判断新旧vnode是否是同一个对象
  if(oldVnode === newVnode) return;
  //判断新vnode有没有text属性
  if(newVnode.text != undefined && (newVnode.children === undefined || newVnode.children.length == 0)){
    //新vnode有text属性
    //console.log('新vnode有text属性')
    if(newVnode.text !== oldVnode.text){
      //如果新虚拟节点中的text和老的虚拟节点的text不同,那么直接让新的text写入老的elm中即可。如果老的elm中是children,那么也会立即消失
      oldVnode.elm.innerText = newVnode.text
    }
  } else {
    //新节点没有text属性
    //console.log('新节点没有text属性')
    //判断老的有没有children
    if(oldVnode.children != undefined && oldVnode.children.length > 0){
      //老的有children,此时就是最复杂的情况,新老都有children
      updateChildren(oldVnode.elm,oldVnode.children,newVnode.children)

    }else{
      //老的没有children,新的有children
      //情况老节点内容
      oldVnode.elm.innerHTML = '';
      //遍历新的vnode子节点,创建DOM,上树
      for(let i = 0;i<newVnode.children.length;i++){
        let dom = createElement(newVnode.children[i]);
        // elm 虚拟节点绑定的真实DOM节点
        oldVnode.elm.appendChild(dom)
      }      
    }
  }
}

3.6 updateChidren函数

这个是新的vnode和oldVnode都有子节点,且子节点不一样的时候进行对比子节点的函数,在这个过程中进行精细化比较,然后更新子节点。

精细化比较是diff算法中的四种优化策略,这里将使用双指针的进行进行diff算法的比较,能够有效加快diff效率。

四种优化策略:(前提:sel和key都要相同)

【只有当第一种不命中的时候,才会采取第二种,依次类推,如果四种都不命中,则需要通过循环来查找。命中指针才会进行移动,否则不移动】

①新前与旧前

②新后与旧后

③新后与旧前 【将新后newEnd指向的节点移动到旧后oldEnd之后】

④新前与旧后 【将新前newStart指向的节点移动到旧前oldStart之前】

对比流程:

①依次比较,当比较成功后退出比较

②渲染结果以newVnode为准

③每次比较成功后start点和end点向中间靠拢

④当新旧节点中有一个start点跑到end点右侧时终止比较

⑤如果都匹配不到,则旧虚拟DOMkey值去比对新虚拟DOM的key值,如果key相同则复用,并移动到新虚拟DOM的位置

import patchVnode from "./patchVnode";
import createElement from "./createElement";
// 判断是不是同一个虚拟节点
function checkSameVnode(a, b) {
  return a.sel == b.sel && a.key == b.key && a.key;
}
export default function updateChildren(parentElm, oldCh, newCh) {
  console.log('update');
  // 旧前
  let oldStartId = 0;
  // 新前
  let newStartId = 0;
  // 旧后
  let oldEndId = oldCh.length - 1;
  // 新后
  let newEndId = newCh.length - 1;
  // 旧前节点
  let oldStartVnode = oldCh[0];
  // 新前节点
  let newStartVnode = newCh[0];
  // 旧后节点
  let oldEndVnode = oldCh[oldEndId];
  // 新后节点
  let newEndVnode = newCh[newEndId];

  let keyMap = null;
  while(oldStartId <= oldEndId && newStartId <= newEndId) {
    // 首先不是判断一二三四命中,而是要略过已经加undefined标记的东西
    if(oldStartVnode == null || oldCh[oldStartId] == undefined) {
      oldStartVnode = oldCh[++oldStartId];
    } else if(oldEndVnode == null || oldCh[oldEndId] == undefined) {
      oldEndVnode = oldCh[--oldEndId];
    } else if(newStartVnode == null || newCh[newStartId] == undefined) {
      newStartVnode = newCh[++newStartId];
    } else if(newEndVnode == null || newCh[newEndId] == undefined) {
      newEndVnode = newCh[--newEndId];
    } else if(checkSameVnode(oldStartVnode, newStartVnode)) {
      console.log('①');
      // 对比
      patchVnode(oldStartVnode, newStartVnode);
      // 指针后移[先后移后使用]
      oldStartVnode = oldCh[++oldStartId];
      newStartVnode = newCh[++newStartId];
    } else if(checkSameVnode(oldEndVnode, newEndVnode)) {
      console.log('②');
      // 新后和旧后
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndId];
      newEndVnode = newCh[--newEndId];
    } else if(checkSameVnode(oldStartVnode,newEndVnode)) {
      // 新后与旧前
      console.log('③');
      patchVnode(oldStartVnode, newEndVnode);
      // 当新后与旧前命中的时候,此时要移动节点,移动新前指向的这个节点到老节点的旧后的后面【当前最后一个未处理的节点】
      // 为什么没有使用appendChild,是因为appendChild是所有子元素的前面,而就后不一定是所有子元素后面
      // 如何移动节点?只要你插入一个已经在DOM树上的节点,它就会移动
      // elm 虚拟节点绑定的真实DOM节点
      // nextSibling属性返回元素节点之后的下一个兄弟节点(包括文本节点、注释节点)
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      oldStartVnode = oldCh[++oldStartId];
      newEndVnode = newCh[--newEndId];
    }  else if(checkSameVnode(oldEndVnode,newStartVnode)) {
      console.log('④');
      patchVnode(oldEndVnode,newStartVnode);
      // 当新前与旧后命中的时候,此时要移动节点,移动新前指向的这个节点到老节点的旧前的前面
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm.nextSibling);
      oldEndVnode = oldCh[--oldEndId];
      newStartVnode = newCh[++newStartId];
    } else {
      // 四种命中都没有命中
      // 寻找key的map
      // 为old节点制作keyMap一个映射对象,这样就不用每次都遍历老对象
      if(!keyMap) {
        keyMap = {};
        // 从oldStartId开始,到oldEndId结束,创建keyMap映射对象
        for(let i = oldStartId; i <= oldEndId; i++) {
          const key = oldCh[i].key;
          if(key != undefined) {
            keyMap[key] = i;
          }
        }
      }
      // 寻找当前这项(newStartId)这项在keyMap中的映射的位置序号
      const idInOld = keyMap[newStartVnode.key];
      console.log(idInOld);
      if(idInOld == undefined) {
        // 判断,如果idInOld是undefined表示它是全新的项
        // 被加入的项(就是newStartVnode这项)现在不是真正的DOM节点
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
      } else {
        // 如果不是undefined,不是全新的项,而是要移动
        // 存储移动的项
        const elmToMove = oldCh[idInOld];
        patchVnode(elmToMove, newStartVnode);
        // 把这项设置为undefined,表示我已经处理完这项了
        oldCh[idInOld] = undefined;
        // 移动,调用insertBefore也可以实现移动
        parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
      }
      // 指针下移,只移动新的头
      newStartVnode = newCh[++newStartId];
    }
  }
  // 继续看看有没有剩余的,循环结束了start还是比old小,说明有新增项
  // 因此需要插入这些节点
  if(newStartId <= newEndId) {
    console.log('new还有剩余节点没有处理,要加项。要把所有剩余的节点都插入到oldStartId之前');
    // 插入的标杆,因为在插入之前可能会存在新后和旧后的对比,你需要确定新后和旧后对比的最后一次,插入到最后一次之前
    // 遍历新的newCh,添加老的没有处理的之前
    for(let i = newStartId; i <= newEndId; i++) {
      console.log('新增');
      // insertBefore方法可以自动识别null,如果是null就会自动排到队尾去,和appendChild是一致的
      // newCh[i]现在还没有真正的DOM,所以要调用createElement()函数变为DOM
      parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartId].elm);
    }
  } else if(oldStartId <= oldEndId) {
    // 只能删除中间项,不能删除最后一项
    console.log('old还有剩余节点没有处理');
    // 表示有删除节点
    // 批量删除oldStart和oldEnd指针之间的项
    for(let i = oldStartId; i <= oldEndId; i++) {
      if(oldCh[i]) {
        parentElm.removeChild(oldCh[i].elm);
      }
    }
  }
}

总结

在JavaScript中,渲染DOM的开销是非常大的,比如我们修改了某个数据,如果直接渲染到真实的DOM,会引起整个DOM树的回流和重绘。

因此我们需要通过虚拟DOM和diff算法进行优化,只更新修改部分,实现最小量更新。

此时我们需要根据真实DOM生成虚拟DOM,当虚拟DOM某个节点的数据改变后会生成一个新的vnode,然后新vnode和旧vnode进行比较,发现有不一样的地方就直接修改到真实DOM上,然后使旧vnode变成新vnode。

diff算法的过程就是patch函数的调用,比较新旧节点。

在采用diff算法比较新旧节点的时候,只会进行同层级的比较。

在patch方法中,首先先比较新旧虚拟节点是否是同一个节点,如果不是同一个节点,那么就会将旧的节点删除掉,插入新的虚拟节点,然后再使用createElement函数创建其真实DOM,将其渲染到真实的DOM树。

如果是同一个节点,使用patchVnode函数比较新旧节点,包括属性更新、文本更新、子节点更新。

但如果新旧节点都有子节点,则需要进行diff算法,调用updateChildren函数,如果新节点没有文本内容而旧节点有文本内容,则需要将旧节点文本内容删除,如果新节点有文本内容,则直接进行替换。

uppdateChildren方法将新旧节点的子节点提取出来,使用的是双指针的方式进行四种优化策略的循环比较。

①新前与旧前比较;②新后与旧后比较;③新后与旧前比较;④新前与旧后比较。

如果四种优化策略方法均没有命中,则会进行遍历方法进行比较(源码中使用Map对象进行缓存,加快了比较的速率),如果设置了key,就会使用key进行比较,找到当前的新节点的子节点在Map中的映射位置,如果不存在,则需要添加节点,存在则需要移动节点。最后循环结束之后,如果新节点还有剩余节点,则说明需要添加节点,如果旧节点还有剩余,则说明需要删除节点。

© 版权声明
THE END
喜欢就支持一下吧
点赞9 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容