Vue源码解析之虚拟DOM和diff算法

举个小栗子：

我们要对一个屋子进行装修，装修图上只是对一部分空间进行改造，现有两种选择：①全拆了再按照装修图进行建造，②根据装修图，只对修改部分进行建造。

关于真实dom和虚拟dom的区别大致和上述例子相同，真实dom是①每一次修改都需要拆了之前的再新建，而虚拟dom是②通过比对不同，通过appendchild等来操作dom节点。

渲染真实dom的开销非常大，和页面性能优化中的重绘重排意义类似。当我们修改了页面中的某个数据，如果直接渲染到真实DOM中会引起整棵数的重绘重排, 如果我们使用虚拟dom，只让我们修改的数据映射到真实DOM, 做一个最少化重绘重排，这样的页面性能优化将大大提高。

知识讲解

虚拟dom

将真实的DOM的数据抽取出来，以对象的形式模拟树形结构

<div>
    <p>你好</p>
</div>

// VNode:
const Vnode = {
    tag: 'div',
    children: [
        { tag: 'p', text: '你好' }
    ]
};

1. h函数用来产生虚拟节点

const hFun = h('a', { props:{ href: 'http:baidu.com' } }, '百度');

// 将得到这样的虚拟节点:
{'sel': 'a','data': { props: { href: 'http:baidu.com' } }, 'text': '百度'};

// 得到的真正DOM节点
<a href = "http:baidu.com" >百度</a>

2. 虚拟节点的属性

{
	children: undefined// 子元素 数组
	data: {} // 属性、样式、key
	elm: undefined // 对应的真正的dom节点(对象)，undefined表示节点还没有上dom树
	key: // 唯一标识
	sel: "" // 选择器
	text: "" // 文本内容
}

3. h函数使用patch函数进行”上树“

创建节点时，所有子节点都需要递归创建的

diff算法

简单的说：就是新旧虚拟dom 的比较，如果有差异就以新的为准，然后再插入的真实的dom中，重新渲染。

1. 在diff中，key起着非常重要的作用

• 无key：新的和旧的只会在进行头尾两端比较
• 有key：除了比较头尾两端，还会根据key生成对象oldKeyToIdx中查找匹配的节点

为节点设置key可以更高效的利用dom

例如：

在B和C之间加一个F，Diff算法默认执行起来是这样的：C更新成F，D更新成C，E更新成D，最后再插入E，这个效率emmm。。。。。。

如果我们给每个节点设置好key，Diff算法就可以正确的识别此节点，找到正确的位置区插入新的节点。

哦豁，for循环要设置key…..

2. 特点

• 只会做同级比较，不做跨级比较
• 比较后几种情况
  • if (oldVnode === vnode)，他们的引用一致，可以认为没有变化。
  • if(oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text)，文本节点的比较，需要修改，则会调用Node.textContent = vnode.text。
  • if( oldCh && ch && oldCh !== ch ), 两个节点都有子节点，而且它们不一样，这样我们会调用updateChildren函数比较子节点，这是diff的核心
  • else if (ch)，只有新的节点有子节点，调用createEle(vnode)，vnode.el已经引用了老的dom节点，createEle函数会在老dom节点上添加子节点。
  • else if (oldCh)，新节点没有子节点，老节点有子节点，直接删除老节点。

3. 总结

• 只有是同一个虚拟节点，才进行精细化比较，否则就是暴力删除旧的、插入新的
• 定义同一个虚拟节点：选择器系统 && key相同
• key是节点的唯一标识

• 只进行同层比较，不会进行跨层比较

• diff不是万能的，肯定有情况是做不到虚拟dom优化的

4. 在实际开发中要注意

• 尽量不要跨层级的修改dom
• 在开发组件时，保持稳定的 DOM 结构会有助于性能的提升
• 设置key可以让diff更高效

手写源码

虚拟DON

// 把传入安的5个参数组合成对象返回
export default function(sel, data, children, text, elm){
    const key = data.key  // 将data中的key拿出来
    return {
        sel, data, children, text, elm, key
    }
}

patch第一次上树

精细化比较具体内容

patch.js

import vnode from './vnode.js';
import createElement from './createElement.js';
import patchVnode from './patchVnode.js';

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

createElement.js

// 真正创建节点，将vnode创建为DOM，是孤儿节点，不进行插入
export default function createElement (vnode) {
    // 把虚拟节点Vnode,真正变为DOM
    let demNode = document.createElement(vnode.sel);
    // 判断有子节点还是有文本
    if(vnode.text != '' && vnode.children == undefined || vnode.children.length == 0) {
        // 内部是文字
        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 ch = vnode.children[i];
            // 创建出它的DOM，一旦调用createElement意味着：创建出了DOM了，并且它的elm属性指向了创建出的DOM，但是还没有上树，是一个孤儿节点
            let chDOM = createElement(ch);
            // 上树
            domNode.appendChild(chDOM);
        }
    }
    // 补充elm属性
    vnode.elm = domNode;
    return vnode.elm;  // 返回值为纯DOM对象，后续递归需要返回
}

patchVnode.js

import createElement from "./createElement.js"

export default function patchVnode(oldVnode, newVnode) {
  // 判断新旧vnode是否是同一个对象
  if (newVnode === oldVnode) 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 {
    // 新vnode没有text属性
    console.log("新vnode没有text属性");
    // 判断老的有没有children
    if (oldVnode.children != undefined && oldVnode.children.length > 0) {
      // 老的有children，此时就是最复杂的情况（新老节点都有children）
///////////////////////////////////////////////////////////////////////////////
        // 所有未处理的节点的开头
        let un = 0;
        for (let i = 0; i < newVnode.children.length; i++) {
            let ch = newVnode.children[i];
            // 再次遍历，看看oldVnode中有没有节点和它是same的
            let isExist = false;
            for(let j = 0; j < oldVnode.children.length; j++) {
                if(oldVnode.children[j].sel == ch.sel && oldVnode.children[j].key == ch.key){
                    isExist = true;
                }
            }
            if(!isExist) {
                let dom = createElement(ch);
                ch.elm = dom;
                if (un < oldVnode.children.length) {
                    oldVnode.elm.insertBefore(dom, oldVnode.children[un].elm);
                } else {
                    oldVnode.elm.appendChild(dom);
                }
            } else {
                un++;
            }
        }
/////////////////////////////////////////////////////////////////////////////////        
    } else {
      // 老的没有children，新的有children
      // 清空老节点的内容
      oldVnode.elm.innerHTML = "";
      // 遍历新节点的子节点，创建DOM，上树
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i]);
        oldVnode.elm.appendChild(dom);
      }
    }
  }
}

diff算法优化

子节点更新策略

四种命中查找

• 新前与旧前
• 新后与旧后
• 新后与旧前（新前指向的节点，移动到旧后之后）
• 新前与旧后（新前指向的节点，移动到旧前之前）

命中一种就不再进行命中判断，若全都没命中，需要用循环来寻找

举例子

• 新增：

  刚开始，旧前和新前均指向第一个节点，对比这两者是否相同，若相同，同时移动一个节点，再次比较，直到旧前指针移动到没有节点处，新前与新后之间的所有节点为新节点，全部插入到dom树中。

  

• 删除：

  刚开始，旧前和新前均指向第一个节点，对比这两者是否相同，若相同，同时移动一个节点，再次比较……

  如果旧前和新前指向的节点不相同，使用下一个命中查找：新后与旧后，此时新后与旧后同时移动一个节点，进行比较，直到新节点循环完毕，此时若老节点有剩余节点，说明他们是要被删除的节点

  

代码改进

patchVnode.js

import createElement from "./createElement.js"
import updateChildren from "./updateChildren.js"

// 对比同一个虚拟节点
export default function patchVnode(oldVnode, newVnode) {
  // 判断新旧vnode是否是同一个对象
  if (newVnode === oldVnode) return;
  // 判断新vnode有没有text属性
  if (
    newVnode.text != undefined &&
    (newVnode.children == undefined || newVnode.children.length == 0)
  ) {
    // 新vnode有text属性
    if (newVnode.text != oldVnode.text) {
      // 如果新虚拟节点中的text和老的虚拟节点的text不同，那么直接让新的text写入老的elm中即可。如果老的elm中是children，那么也会立即消失
      oldVnode.elm.innerText = newVnode.text;
    }
  } else {
    // 新vnode没有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 = "";
      // 遍历新节点的子节点，创建DOM，上树
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i]);
        oldVnode.elm.appendChild(dom);
      }
    }
  }
}

updateChildren.js

import patchVnode from "./patchVnode.js"
import createElement from "./createElement.js"

// 判断是否为同一个虚拟节点
function checkSameVnode(a, b) {
    return a.sel == b.sel && a.key == b.key;
}
export default function updateChildren(parentElm, oldCh, newCh) {
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let newEndIdx = oldCh.length - 1;
    
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    
    while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
        // 先略过已经加了undefined标记的东西
        if(oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
            oldStartVnode = old[++oldStartIdx]
        } else if(oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
            oldEndVnode = old[--oldEndIdx]
        } else if(newStartVnode == null || newCh[newStartIdx] == undefined) {
            newStartVnode = old[++oldStartIdx]
        } else if(newEndVnode == null || newCh[newEndIdx] == undefined) {
            newEndVnode = old[--newEndIdx]
        } else if(checkSameVnode(oldStartVnode, newStartVnode)){
            // ①新前和旧前
            patchVnode(oldStartVnode,newStartVnode);
            oldStartVnode = oldCh[++oldStartIdx];   //先自增后使用
            newStartVnode = newCh[++newStartIdx];
        } else if(checkSameVnode(oldStartVnode, newStartVnode)){
            // ②新后和旧后
            patchVnode(oldStartVnode, newStartVnode);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if(checkSameVnode(oldStartVnode, newEndVnode)){
            // ③新后和旧前
            patchVnode(oldStartVnode, newEndVnode);
            // 此时要移动节点，移动新前指向的这个节点到老节点的旧后的后面
            parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling) //下一个兄弟节点前
            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        } else if(checkSameVnode(oldEndVnode, newStartVnode)){
            // ④新前和旧后
            patchVnode(oldEndVnode, newStartVnode);
            // 此时要移动节点，移动新前指向的这个节点到老节点的旧后的后面
            parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm) //下一个兄弟节点前
            oldEndVnode = oldCh[++oldEndIdx];
            newStartVnode = newCh[--newStartIdx];
        } else {
            // 全都没有命中
            // 制作key的map
            if(!keyMap) {
                keyMap = {};
                for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                    const key = oldCh[i].key;
                    if (key != undefined) {
                        keyMap[key] = i;
                    }
                }
            }
            // 寻找当前这项newStartIdx在keyMap中的映射的位置序号
            const idxInOld = keyMap[newStartVnode.key];
            if(idxInOld == undefined) {
                // 判断，如果idxInOld是undefined，表示是全新的项
                // 被加入的项（极速newStartVnode这项），现在还不是真正的DOM节点
                parentElm.insertBefore(ceateElem(newSrartVnode), oldStartVnode.elm);
            } else {
                // 如果不是undefined，不是全新的项，要移动
                const elmToMove = oldCh[idxInOld];
                patchVnode(elmToMove, newStartVnode);
                // 处理完后，设置为undefined
                oldCh[idxInOld] = undefined;
                parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
            }
            // 指针下移，只移动新的头
            newStartVnode = newCh[++newStartIdx]
        }
    }
    
    //继续看看有没有剩余的
    // 当start还是比old小,new还有剩余节点没有处理，要加项
    if (newStartIdx <= oldEndIdx) {
        // 遍历新的newChrome，添加到老的没有处理的之前
        for(let i = newStartIdx; i <= newEndIdx; i++) {
            // 如果是null，自动排到队尾
            parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
        }
    } else if (oldStartIdx <= oldEndIdx) {
        // old还有剩余节点没有处理
        // 批量删除oldStart和oldEnd指针之间的项，要减项
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
            if (oldCh[i]) {
                parentElm.removeChild(oldCh[i].elm);
            }
        }
    }
}

参考：