谈谈我对Vue中diff算法的理解｜七日打卡

前言

我认为diff算法具备两个特点。
一、高效性：有虚拟dom，必然需要diff算法。通过对比新旧虚拟dom，将有变化的地方更新在真实dom上，另外，通过diff高效的执行比对过程，从而降低时间复杂度为O(n)。
二、必要性：vue2中为了降低watcher粒度，每个组件只有一个watcher。通过diff精确找到发生变化的节点，并复用相同的节点。
下面我们通过手写简易diff算法，来看看具体是怎么实现的吧？

比较新旧虚拟节点

patch(vnode,newVnode)分为以下几种情况

1.标签名不一样，直接换掉老节点

可以通过vnode.el 属性，获取真实的dom元素

 if(oldVnode.tag !== vnode.tag){
    oldVnode.el.parentNode.replaceChild(createElm(vnode),oldVnode.el)
 }

2.都是文本节点，比较文本内容

如果新老文本不相等，el.textContent=vnode.text

// 如果标签一致但是不存在则是文本节点
if(!oldVnode.tag){
    if(oldVnode.text !== vnode.text){
    	oldVnode.el.textContent = vnode.text;
    }
}

3.标签一样

复用老真实节点 vnode.el=oldnode.el

1.比较属性 patchProps

let el = vnode.el = oldVnode.el;
function patchProps(vnode, oldProps = {}) { // 初次渲染时可以调用此方法，后续更新也可以调用此方法
    let newProps = vnode.data || {};
    let el = vnode.el;
    // 如果老的属性有，新的没有直接删除
    let newStyle = newProps.style || {};
    let oldStyle = oldProps.style || {};
    for (let key in oldStyle) {
        if (!newStyle[key]) { // 新的里面不存在这个样式
            el.style[key] = '';
        }
    }
    for (let key in oldProps) {
        if (!newProps[key]) {
            el.removeAttribute(key);
        }
    }
    // 直接用新的生成到元素上
    for (let key in newProps) {
        if (key === 'style') {
            for (let styleName in newProps.style) {
                el.style[styleName] = newProps.style[styleName];
            }
        } else {
            el.setAttribute(key, newProps[key]);
        }
    }
}

2.比较子节点

 let oldChildren = oldVnode.children || [];
        let newChildren = vnode.children || [];

        if (oldChildren.length > 0 && newChildren.length > 0) {
            // 双方都有子节点

            //  vue用了双指针的方式 来比对 
            patchChildren(el, oldChildren, newChildren);
        } else if (newChildren.length > 0) { 
        // oldVnode 无子节点，newVnode 有子节点
            for (let i = 0; i < newChildren.length; i++) {
                let child = createElm(newChildren[i]);
                el.appendChild(child); // 循环创建新节点
            }

        } else if (oldChildren.length > 0) { 
        // oldVnode 有子节点，newVnode 无子节点
            el.innerHTML = ``; // 直接删除老节点
        }

都有子节点patchChildren

function patchChildren(el, oldChildren, newChildren) {
    let oldStartIndex = 0;
    let oldStartVnode = oldChildren[0];
    let oldEndIndex = oldChildren.length - 1;
    let oldEndVnode = oldChildren[oldEndIndex];
    let newStartIndex = 0;
    let newStartVnode = newChildren[0];
    let newEndIndex = newChildren.length - 1;
    let newEndVnode = newChildren[newEndIndex];

    const makeIndexByKey = (children)=>{
        return children.reduce((memo,current,index)=>{
            if(current.key){
                memo[current.key] = index;
            }
            return memo;
        },{})
    }
    const keysMap = makeIndexByKey(oldChildren);
     // 同时循环新的节点和 老的节点，有一方循环完毕就结束了
     //开头指针和结尾指针重合，则比对完毕
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // 头头比较 尾尾比较 头尾比较 尾头比较
        // 优化了 向后添加， 向前添加，尾巴移动到头部，头部移动到尾部 ，反转
        if(!oldStartVnode){ // 已经被移动走了
            oldStartVnode = oldChildren[++oldStartIndex];
        }else if(!oldEndVnode){
            oldEndVnode = oldChildren[--oldEndIndex];
        }
       
        if (isSameVnode(oldStartVnode, newStartVnode)) { // 头头比较，发现标签一致，
            patch(oldStartVnode, newStartVnode);
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
        }else if(isSameVnode(oldEndVnode,newEndVnode)){ // 从尾部开始比较
            patch(oldEndVnode,newEndVnode);
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
        } 
        // 头尾比较  =》 reverse
        else if(isSameVnode(oldStartVnode,newEndVnode)){
            patch(oldStartVnode,newEndVnode);
            el.insertBefore(oldStartVnode.el,oldEndVnode.el.nextSibling); // 移动老的元素，老的元素就被移动走了，不用删除
            oldStartVnode = oldChildren[++oldStartIndex];
            newEndVnode = newChildren[--newEndIndex];
        }
        else if(isSameVnode(oldEndVnode,newStartVnode)){ // 尾头比较
            patch(oldEndVnode,newStartVnode);
            el.insertBefore(oldEndVnode.el,oldStartVnode.el);
            oldEndVnode = oldChildren[--oldEndIndex];
            newStartVnode = newChildren[++newStartIndex];
        }else{
            // 乱序比对   核心diff
            // 1.需要根据key和 对应的索引将老的内容生成程映射表
            let moveIndex = keysMap[newStartVnode.key]; // 用新的去老的中查找
            if(moveIndex == undefined){ // 如果不能复用直接创建新的插入到老的节点开头处
                el.insertBefore(createElm(newStartVnode),oldStartVnode.el);
            }else{
                let moveNode = oldChildren[moveIndex];
                oldChildren[moveIndex] = null; // 此节点已经被移动走了
                el.insertBefore(moveNode.el,oldStartVnode.el);
                patch(moveNode,newStartVnode); // 比较两个节点的属性
            }
            newStartVnode = newChildren[++newStartIndex]
        }
    }
    // 如果用户追加了一个怎么办？  

    // 这里是没有比对完的
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            // el.appendChild(createElm(newChildren[i]))  
            // insertBefore方法 他可以appendChild功能 insertBefore(节点,null)  dom api

            //  看一下为指针的下一个元素是否存在
            let anchor = newChildren[newEndIndex + 1] == null? null :newChildren[newEndIndex + 1].el
            el.insertBefore(createElm(newChildren[i]),anchor);
        }
    }
    if(oldStartIndex <= oldEndIndex){
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            //  如果老的多 将老节点删除 ， 但是可能里面有null 的情况
            if(oldChildren[i] !== null) el.removeChild(oldChildren[i].el);
        }
    }

}

开始循环新老节点，有一方循环完毕就结束

if 旧头==新头 isSameVnode

patch(旧头，新头) 递归 双头指针后移一位

else if 旧尾==新尾

patch(旧尾，新尾) 递归 双尾指针向前移一位

else if 旧头==新尾

parentElm.insertBefore( oldStartVnode.elm, oldEndVnode.elm.nextSibling ); 旧头.el 移到老尾指针真实节点后面 旧头指针 后移 新尾指针 前移

else if 旧尾==新头

parentElm.insertBefore( oldEndVnode.elm, oldStartVnode.elm );

旧尾指针 前移 新头指针 后移

else if 都没匹配上 对比查找

1. 根据 key 和对应的索引将老的内容生成映射表

2. 用新 key 去旧 key 中查找

   • 没找到-直接创建新 dom 的插入到旧节点的开头处

   • 找到了-插入，并比较两个节点的子节点，把移动的节点插入到旧节点，移动走的节点=null,指针碰到 null，跳过，直接向后/前移一位

循环结束

看看是哪对指针重合没有比对完的，处理可能剩下的节点

• 旧指针重合 新指针越界 oldVnode 还有多余没比对

旧节点进行 for 循环批量删除 el.removeChild(oldChildren[i].el);

• 新指针重合 旧指针越界 Vnode 还有多余没比对

看一下新尾指针的下一个元素 newChildren[newEndIndex + 1]是否存在 不存在 直接插入，插在当前新尾真实节点的前面 全部新建，for 循环插入

更新操作

Vue.prototype._update = function (vnode) {
    const vm  = this;
    const prevVnode = vm._vnode; // 保留上一次的vnode
    vm._vnode = vnode;
    if(!prevVnode){
        vm.$el = patch(vm.$el,vnode); // 需要用虚拟节点创建出真实节点 替换掉 真实的$el
        // 我要通过虚拟节点 渲染出真实的dom     
    }else{
        vm.$el = patch(prevVnode,vnode); // 更新时做diff操作
    }
}

小结

diff过程遵循深度优先、同层比较的策略。两个节点之间会根据它们是否拥有子节点或者文本节点做不同的擦欧总。比较两组子节点是算法的重点，首先假设头尾节点可能相同作四次比对尝试，如果没有找到相同节点才按照通用方式遍历查找，查找结束再按情况处理剩下的节点。借助key通常可以非常精准找到相同节点，因此整个patch过程非常高效。 不过值得注意的一点，在对于需要增删的数据,我们不建议使用index作为key。