Diff算法(三)，完结篇——最小量更新

1. 最小量更新插入方式

这里的节点key就是必须的啦

新创建的节点插入到所有未处理的节点之前，而不是所有已处理节点之后（为什么不能所有已处理节点之后呢？因为如果新增的是连续多个节点，那么就会造成逻辑混乱）

2. 子节点更新策略

子节点更新策略，先准备4个指针，分别代表指向新节点的前子节点和新节点的后子节点、旧节点的前子节点和旧节点的后子节点，并且指针的移动规则是前指针往后移，后指针往前移动如图：

于是就有4种匹配情况：

新前与旧前：首先新前节点和旧前节点都是指向各种的第一个子节点，当命中这个条件，将只更新此节点，如果相同就不做处理，然后新前和旧前指针分别下移
新后与旧后,命中后指针上移
新后与旧前,当命中这个，此时要移动节点；移动旧前指向的这个节点到老节点的旧后的后面
新前与旧后,当新前与旧后命中，此时要移动节点；移动旧后指向的这个节点到老节点的旧前的前面

命中了条件一就不在进行条件二的判断，依次类推

如果没有命中就循环查找，这个循环查找也是有一点点技巧的:

先遍历旧节点的子节点以key和index做一个keyMap对象
用新前这个指针放入到这个keyMap中如果找到则说明新节点的子节点是已经存在的了的并输出其在老节点的位置，然后找到这个子节点，将他移动到旧前之前
如果没有找到，说明该节点是不存在于老节点当中的子节点，是新增项，因此要将此虚拟子节点创建，并添加到旧前之前

最后执行：

while( 新前的index<=新后的index && 旧前的index<=旧后的index ){
	if( 旧的节点先循环完毕，说明新节点中有要插入的节点 ){
		append(节点)
	}else if( 新的节点先循环完毕，说明旧节点有要删除的节点){
		remove(节点)
	}
}
复制代码

3. 实现代码

<button id="pacthActionOne">上树</button>
<div id="app"></div>
<div id="app1"></div>
复制代码

// 最小量更新子节点
function updateChild(parentEle, oldChild, newChild){

    // 判断是否是同一个虚拟节点
    function jugeSameVNode( a, b){
        return a.sel === b.sel && a.data.key === b.data.key
    }

    // 旧前索引 节点
    let oldStartIdx = 0;
    let oldStartVnode = oldChild[oldStartIdx];
    // 旧后索引 节点
    let oldEndIdx = oldChild.length -1;
    let oldEndVnode = oldChild[oldEndIdx];
    // 新前索引 节点
    let newStartIdx = 0;
    let newStartVnode = newChild[newStartIdx]
    // 新后索引 节点
    let newEndIdx = newChild.length -1;
    let newEndVnode = newChild[newEndIdx]
    
    // 缓存key
    let keyMap = null;

    while( oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
        
        // 因为没有命中1,2,3,4这四个条件，循环出来给null的因此要判断这个点是不是存在
        if(!oldStartVnode){
            oldStartVnode = oldChild[ ++oldStartIdx ]
        }else if( !oldEndVnode){
            oldEndVnode = oldChild[ --oldEndIdx ]
        }else if( jugeSameVNode(oldStartVnode,newStartVnode) ){
            //新前与旧前 如果两个新旧两个子节点一样直接上树比较
            patch(oldStartVnode, newStartVnode)
            console.log( oldStartIdx,newStartIdx,'新前与旧前')
            oldStartVnode = oldChild[ ++oldStartIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( oldEndVnode,newEndVnode) ){
            // 新后与旧后
            patch(oldEndVnode,newEndVnode);
            console.log( newEndIdx,oldEndIdx,'新后与旧后' )
            oldEndVnode = oldChild[ --oldEndIdx ];
            newEndVnode = newChild[ --newEndIdx ];
        }else if( jugeSameVNode( oldEndVnode,newStartVnode) ){
            // 新前与旧后
            patch(oldEndVnode,newStartVnode)
            parentEle.insertBefore(oldEndVnode.elm,oldStartVnode.elm)
            oldEndVnode = oldChild[ --oldEndIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( newEndVnode,oldStartVnode) ){
            // 新后与旧前
            patch(oldStartVnode,newEndVnode)
            parentEle.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling)
            oldStartVnode = oldChild[ ++oldStartIdx ]
            newEndVnode = newChild[ --newEndIdx ]
        }else{
            // 均没命中启用循环
            console.log( oldEndIdx,newStartIdx,'均未命中' )

            if(!keyMap){
                keyMap = {}
                for(let i = oldStartIdx; i<= oldEndIdx; i++){
                    const key = oldChild[i].data.key;
                    if(key !=undefined ){
                        keyMap[key] = i;
                    }
                }
            }
            // 寻找当前这项(newStartIdx)在keyMap中的映射序号位置
            const idxInold = keyMap[newStartVnode.data.key];
            console.log(idxInold)
            if(!idxInold){
                // 如果idxInold不存在表示他是全新的项
                parentEle.insertBefore( createEle(newStartVnode),oldStartVnode.elm)
            }else{
                // 如果不是则不是全新的项，而是要移动
                console.log('移动')
                const eleToMove = oldChild[idxInold]
                patch(eleToMove,newStartVnode);
                oldChild[idxInold] = null;
                parentEle.insertBefore( eleToMove.elm ,oldStartVnode.elm)
            }
            newStartVnode = newChild[ ++newStartIdx ]
        }
    }

    if( newStartIdx <= newEndIdx ){
        console.log('有剩余节点，做新增操作')
        console.log( newChild[newEndIdx + 1] )
        // const before = !newChild[newEndIdx + 1]?null: newChild[newEndIdx + 1].elm;
        // console.log(before)
        for( let i = newStartIdx; i<= newEndIdx; i++){
            parentEle.insertBefore( createEle(newChild[i]),oldChild[oldStartIdx] )
        }
    }else if(oldStartIdx<=oldStartIdx){
        console.log('还有剩余节点未处理,做删除操作')
        for( let i = oldStartIdx;i<=oldEndIdx;i++){
            parentEle.removeChild(oldChild[i].elm)
        }
    }
}
复制代码

4. 完整的手写简单diff算法代码

function VNode(sel,data,children,text,elm){
	return {
		sel,
		data,
		children,
		text,
		elm
	}
}
/**
 * @param { String } sel 虚拟dom标签
 * @param { Object } data 虚拟dom属性
 * @param { 可以是虚拟dom，文本，[]} c
 * @return VNode 
 * Vnode 返回有三个形态
 * 1. h('div',{},'文本')
 * 2. h('div',{},[...])
 * 3. h('div',{},h())
 **/

function h(sel,data,c){
	if( Array.from(arguments).length !==3 ){
		throw new Error('参数错误，请检查')
	}
	if(typeof c === 'string' || typeof c === 'number'){
		return VNode(sel,data,undefined,c,undefined)
	}
	if( Array.isArray(c) ){
		const children = c.map((item)=>{
			if(!(typeof item === 'object' && item.hasOwnProperty('sel'))){
				throw new Error('传入的数组元素成员不是h()函数返回的虚拟dom')
			}else{
				return item
			}
		})
		
		return VNode(sel,data,children,undefined,undefined)
	}
	if(typeof c === 'object' && c.hasOwnProperty('sel')){
		return VNode(sel,data,[c])
	}
	return new Error('参数错误，请检查')
}    

// 创建真实节点,作用将VNode创建为DOM
function createEle(VNode){
    const domNode = 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){
        VNode.children.forEach( item =>{
            const itemDOM = createEle(item)
            domNode.appendChild(itemDOM);
        })
    }
    // 因为创建生成为真实节点代表即将要上树的，前面说过，上树的时候虚拟节点的elm属性就是这个真实dom
    VNode.elm = domNode;
    return VNode.elm
}

// 上树patch方法
function patch(oldVNode,newVNode){
    // 1. 判断传入的第一个参数，是dom节点还是虚拟节点
    if(oldVNode.sel === '' || oldVNode.sel === undefined ){
        // 说明是dom节点，要包装成虚拟节点
        oldVNode = VNode( oldVNode.tagName.toLowerCase(),{},[],undefined,oldVNode )
    }
    console.log( oldVNode )
    // 2. 判断oldVNode和newVNode是不是同一个节点
    if(oldVNode.key === newVNode.key && oldVNode.sel === newVNode.sel){
        // 同一个节点，精细化比较
        refineCompare(oldVNode,newVNode)
        return
    }
    // 3. 是不同的节点，暴力插入新的，拆除旧的
    const newDOM = createEle(newVNode);
    oldVNode.elm.parentNode.insertBefore( newDOM ,oldVNode.elm);
    oldVNode.elm.parentNode.removeChild(oldVNode.elm)
}

// 同一个节点，精细化比较的各个处理函数

function refineCompare( oldVNode, newVNode){
    if(oldVNode === newVNode){
        return
    }
    if( newVNode.text !== undefined && ( newVNode.children === undefined || newVNode.children.length === 0)){
        console.log('命中newVNode有text属性')
        if(oldVNode.text !== newVNode.text){
            oldVNode.elm.innerHtml = '';
            oldVNode.elm.innerText = newVNode.text;
        }
    }else{
        console.log('命中newVNode没有text属性')
        // 判断老的有没有child
        if(oldVNode.children && oldVNode.children.length >0 ){
            // 老的有children，最复杂的情况，将面临最小量更新,难点，单独抽一节
            console.log('最小量更新')
            updateChild(oldVNode.elm,oldVNode.children,newVNode.children)
        }else{
            // 老的没有children，直接文本替换成newVNode的children即可
            oldVNode.elm.innerText = ''
            newVNode.children.forEach(item=>{
                const dom = createEle(item);
                oldVNode.elm.appendChild(dom);
            })
        }
    }
}
// 最小量更新子节点
function updateChild(parentEle, oldChild, newChild){

    // 判断是否是同一个虚拟节点
    function jugeSameVNode( a, b){
        return a.sel === b.sel && a.data.key === b.data.key
    }

    // 旧前索引 节点
    let oldStartIdx = 0;
    let oldStartVnode = oldChild[oldStartIdx];
    // 旧后索引 节点
    let oldEndIdx = oldChild.length -1;
    let oldEndVnode = oldChild[oldEndIdx];
    // 新前索引 节点
    let newStartIdx = 0;
    let newStartVnode = newChild[newStartIdx]
    // 新后索引 节点
    let newEndIdx = newChild.length -1;
    let newEndVnode = newChild[newEndIdx]
    
    // 缓存key
    let keyMap = null;

    while( oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
        
        // 因为没有命中1,2,3,4这四个条件，循环出来给null的因此要判断这个点是不是存在
        if(!oldStartVnode){
            oldStartVnode = oldChild[ ++oldStartIdx ]
        }else if( !oldEndVnode){
            oldEndVnode = oldChild[ --oldEndIdx ]
        }else if( jugeSameVNode(oldStartVnode,newStartVnode) ){
            //新前与旧前 如果两个新旧两个子节点一样直接上树比较
            patch(oldStartVnode, newStartVnode)
            console.log( oldStartIdx,newStartIdx,'新前与旧前')
            oldStartVnode = oldChild[ ++oldStartIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( oldEndVnode,newEndVnode) ){
            // 新后与旧后
            patch(oldEndVnode,newEndVnode);
            console.log( newEndIdx,oldEndIdx,'新后与旧后' )
            oldEndVnode = oldChild[ --oldEndIdx ];
            newEndVnode = newChild[ --newEndIdx ];
        }else if( jugeSameVNode( oldEndVnode,newStartVnode) ){
            // 新前与旧后
            patch(oldEndVnode,newStartVnode)
            parentEle.insertBefore(oldEndVnode.elm,oldStartVnode.elm)
            oldEndVnode = oldChild[ --oldEndIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( newEndVnode,oldStartVnode) ){
            // 新后与旧前
            patch(oldStartVnode,newEndVnode)
            parentEle.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling)
            oldStartVnode = oldChild[ ++oldStartIdx ]
            newEndVnode = newChild[ --newEndIdx ]
        }else{
            // 均没命中启用循环
            console.log( oldEndIdx,newStartIdx,'均未命中' )

            if(!keyMap){
                keyMap = {}
                for(let i = oldStartIdx; i<= oldEndIdx; i++){
                    const key = oldChild[i].data.key;
                    if(key !=undefined ){
                        keyMap[key] = i;
                    }
                }
            }
            // 寻找当前这项(newStartIdx)在keyMap中的映射序号位置
            const idxInold = keyMap[newStartVnode.data.key];
            console.log(idxInold)
            if(!idxInold){
                // 如果idxInold不存在表示他是全新的项
                parentEle.insertBefore( createEle(newStartVnode),oldStartVnode.elm)
            }else{
                // 如果不是则不是全新的项，而是要移动
                console.log('移动')
                const eleToMove = oldChild[idxInold]
                patch(eleToMove,newStartVnode);
                oldChild[idxInold] = null;
                parentEle.insertBefore( eleToMove.elm ,oldStartVnode.elm)
            }
            newStartVnode = newChild[ ++newStartIdx ]
        }
    }

    if( newStartIdx <= newEndIdx ){
        console.log('有剩余节点，做新增操作')
        console.log( newChild[newEndIdx + 1] )
        // const before = !newChild[newEndIdx + 1]?null: newChild[newEndIdx + 1].elm;
        // console.log(before)
        for( let i = newStartIdx; i<= newEndIdx; i++){
            parentEle.insertBefore( createEle(newChild[i]),oldChild[oldStartIdx] )
        }
    }else if(oldStartIdx<=oldStartIdx){
        console.log('还有剩余节点未处理,做删除操作')
        for( let i = oldStartIdx;i<=oldEndIdx;i++){
            parentEle.removeChild(oldChild[i].elm)
        }
    }
}

// 测试用例
const myVnodeOne = h( 'section',{},'你好，diff');
const app = document.getElementById('app')
patch( app, myVnodeOne)

const myVnodeTwo = h( 'ul',{},[
    h('li',{key:'A'},'A'),
    h('li',{key:'B'},'B'),
    
])
const app1 = document.getElementById('app1');
patch( app1,myVnodeTwo)

const pacthActionOne = document.getElementById('pacthActionOne');

// 测试newVNode是text
const newVNodeText = h('ul',{},'你好')
// 测试oldVNode有text属性 newVNode没有text属性有child
const newVNodeChild = h('section',{},[
    h('p',{},'一入前端深似海'),
    h('p',{},'从此女票是路人'),
])
// 测试最小量更新策略
const newVNodeRefine = h( 'ul',{},[
    h('li',{key:'E'},'E'),
    h('li',{key:'A'},'A'),
    h('li',{key:'B'},'B'),
    h('li',{key:'H'},'H'),
    h('li',{key:'D'},'D'),
])


pacthActionOne.addEventListener('click',()=>{
    // patch(myVnodeTwo,newVNodeText)
    // patch(myVnodeOne,newVNodeChild)
    patch(myVnodeTwo, newVNodeRefine)
})
复制代码