This is the 16th day of my participation in Gwen Challenge

Virtual DOM DIFF algorithm for front-end framework

Diff algorithm (3), the end – minimum update

1. Update the insertion mode at the minimum

The node key is required

The newly created node is inserted before all unprocessed nodes, not after all processed nodes (why not after all processed nodes? If you add multiple nodes in a row, it will cause logic chaos.)

2. Update policy of child nodes

In the child node update strategy, four Pointers are prepared, representing the former child node pointing to the new node and the rear child node of the new node, the former child node of the old node and the rear child node of the old node respectively. In addition, the movement rule of the Pointers is that the front pointer moves backward and the rear pointer moves forward, as shown in the figure:

So there are four matches:

  1. New and old: First, both the new and old former nodes point to the first child nodes of various kinds. When this condition is matched, only this node will be updated. If they are the same, no processing will be done
  2. New queen and old queen, pointer moves up after hit
  3. New after and old before, when hit this, to move the node; Move the node pointed to by the old node to behind the old node
  4. New before and old after, when the new before and old after match, to move the node; Move the old node to the front of the old node

If you hit condition one, you don’t judge condition two, and so on

If there is no hit, the loop lookup is also a little tricky:

  1. Let’s go through the children of the old node and do one with key and indexkeyMapobject
  2. If found, the child node of the new node already exists and outputs its position in the old node. Then locate the child node and move it to before the old node
  3. If not, it indicates that the virtual child node does not exist in the old node and is a new item. Therefore, you need to create the virtual child node and add it before the old node

Last execution:

while(old index<= new index && old index<= old index){if{appEnd (node)} {append(node){append(node)}else if{remove(node)}}Copy the code

3. Implementation code

<button id="pacthActionOne">On the tree</button>
<div id="app"></div>
<div id="app1"></div>
Copy the code
// Minimize the number of child nodes updated
function updateChild(parentEle, oldChild, newChild){

    // Check whether it is the same virtual node
    function jugeSameVNode( a, b){
        return a.sel === b.sel && a.data.key === b.data.key
    }

    // Old index node
    let oldStartIdx = 0;
    let oldStartVnode = oldChild[oldStartIdx];
    // Old index node
    let oldEndIdx = oldChild.length -1;
    let oldEndVnode = oldChild[oldEndIdx];
    // New former index node
    let newStartIdx = 0;
    let newStartVnode = newChild[newStartIdx]
    // New index node
    let newEndIdx = newChild.length -1;
    let newEndVnode = newChild[newEndIdx]
    
    / / the cache 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) ){
            // If the new node is the same as the old node, the tree can be directly compared
            patch(oldStartVnode, newStartVnode)
            console.log( oldStartIdx,newStartIdx,'Old and new')
            oldStartVnode = oldChild[ ++oldStartIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( oldEndVnode,newEndVnode) ){
            // New queen and old queen
            patch(oldEndVnode,newEndVnode);
            console.log( newEndIdx,oldEndIdx,'New queen and old queen' )
            oldEndVnode = oldChild[ --oldEndIdx ];
            newEndVnode = newChild[ --newEndIdx ];
        }else if( jugeSameVNode( oldEndVnode,newStartVnode) ){
            // New before and old after
            patch(oldEndVnode,newStartVnode)
            parentEle.insertBefore(oldEndVnode.elm,oldStartVnode.elm)
            oldEndVnode = oldChild[ --oldEndIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( newEndVnode,oldStartVnode) ){
            // The new and the old
            patch(oldStartVnode,newEndVnode)
            parentEle.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling)
            oldStartVnode = oldChild[ ++oldStartIdx ]
            newEndVnode = newChild[ --newEndIdx ]
        }else{
            // Enable loop in all dead
            console.log( oldEndIdx,newStartIdx,'All missed' )

            if(! keyMap){ keyMap = {}for(let i = oldStartIdx; i<= oldEndIdx; i++){
                    const key = oldChild[i].data.key;
                    if(key ! =undefined){ keyMap[key] = i; }}}// Find the location of the current entry (newStartIdx) in the keyMap
            const idxInold = keyMap[newStartVnode.data.key];
            console.log(idxInold)
            if(! idxInold){// If idxInold does not exist, it is completely new
                parentEle.insertBefore( createEle(newStartVnode),oldStartVnode.elm)
            }else{
                // If not, it is not a new item, but a move
                console.log('mobile')
                const eleToMove = oldChild[idxInold]
                patch(eleToMove,newStartVnode);
                oldChild[idxInold] = null;
                parentEle.insertBefore( eleToMove.elm ,oldStartVnode.elm)
            }
            newStartVnode = newChild[ ++newStartIdx ]
        }
    }

    if( newStartIdx <= newEndIdx ){
        console.log('There are some remaining nodes. Add them.')
        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('There are still nodes unprocessed, delete them')
        for( leti = oldStartIdx; i<=oldEndIdx; i++){ parentEle.removeChild(oldChild[i].elm) } } }Copy the code

4. Complete handwritten simple DIFF algorithm code

function VNode(sel,data,children,text,elm){
	return {
		sel,
		data,
		children,
		text,
		elm
	}
}
/ * * *@param { String } Sel Virtual DOM label *@param { Object } Data virtual DOM property *@param {can be virtual DOM, text, []} c
 * @return VNode * VNode return * 1. There are three form h (' div ', {}, 'text') * 2 h (' div ', {}, [...]. ) * 3. h('div',{},h()) **/

function h(sel,data,c){
	if( Array.from(arguments).length ! = =3) {throw new Error('Parameter error, please check')}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('The array element member passed in is not the virtual DOM returned by h()')}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('Parameter error, please check')}// Create a real node to create a 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= >{
            constitemDOM = createEle(item) domNode.appendChild(itemDOM); })}The real DOM is the elm attribute of the virtual node when it is created
    VNode.elm = domNode;
    return VNode.elm
}

// the tree patch method
function patch(oldVNode,newVNode){
    // 1. Check whether the first argument passed in is a DOM node or a virtual node
    if(oldVNode.sel === ' ' || oldVNode.sel === undefined) {// It is a DOM node and should be wrapped as a virtual node
        oldVNode = VNode( oldVNode.tagName.toLowerCase(),{},[],undefined,oldVNode )
    }
    console.log( oldVNode )
    // 2. Check whether oldVNode and newVNode are the same node
    if(oldVNode.key === newVNode.key && oldVNode.sel === newVNode.sel){
        // Same node, fine comparison
        refineCompare(oldVNode,newVNode)
        return
    }
    // 3. Are different nodes, violent insert new, remove old
    const newDOM = createEle(newVNode);
    oldVNode.elm.parentNode.insertBefore( newDOM ,oldVNode.elm);
    oldVNode.elm.parentNode.removeChild(oldVNode.elm)
}

// The same node, refine the comparison of each handler function

function refineCompare( oldVNode, newVNode){
    if(oldVNode === newVNode){
        return
    }
    if( newVNode.text ! = =undefined && ( newVNode.children === undefined || newVNode.children.length === 0)) {console.log('Hit newVNode with text property')
        if(oldVNode.text ! == newVNode.text){ oldVNode.elm.innerHtml =' '; oldVNode.elm.innerText = newVNode.text; }}else{
        console.log('Hit newVNode without text property')
        // Check if there is a child
        if(oldVNode.children && oldVNode.children.length >0) {// The most complex case will face the minimum number of updates, difficulties, separate section
            console.log('Minimum update')
            updateChild(oldVNode.elm,oldVNode.children,newVNode.children)
        }else{
            // There is no children in the old text. Replace the text with children in newVNode
            oldVNode.elm.innerText = ' '
            newVNode.children.forEach(item= >{
                constdom = createEle(item); oldVNode.elm.appendChild(dom); })}}}// Minimize the number of child nodes updated
function updateChild(parentEle, oldChild, newChild){

    // Check whether it is the same virtual node
    function jugeSameVNode( a, b){
        return a.sel === b.sel && a.data.key === b.data.key
    }

    // Old index node
    let oldStartIdx = 0;
    let oldStartVnode = oldChild[oldStartIdx];
    // Old index node
    let oldEndIdx = oldChild.length -1;
    let oldEndVnode = oldChild[oldEndIdx];
    // New former index node
    let newStartIdx = 0;
    let newStartVnode = newChild[newStartIdx]
    // New index node
    let newEndIdx = newChild.length -1;
    let newEndVnode = newChild[newEndIdx]
    
    / / the cache 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) ){
            // If the new node is the same as the old node, the tree can be directly compared
            patch(oldStartVnode, newStartVnode)
            console.log( oldStartIdx,newStartIdx,'Old and new')
            oldStartVnode = oldChild[ ++oldStartIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( oldEndVnode,newEndVnode) ){
            // New queen and old queen
            patch(oldEndVnode,newEndVnode);
            console.log( newEndIdx,oldEndIdx,'New queen and old queen' )
            oldEndVnode = oldChild[ --oldEndIdx ];
            newEndVnode = newChild[ --newEndIdx ];
        }else if( jugeSameVNode( oldEndVnode,newStartVnode) ){
            // New before and old after
            patch(oldEndVnode,newStartVnode)
            parentEle.insertBefore(oldEndVnode.elm,oldStartVnode.elm)
            oldEndVnode = oldChild[ --oldEndIdx ];
            newStartVnode = newChild[ ++newStartIdx ];
        }else if( jugeSameVNode( newEndVnode,oldStartVnode) ){
            // The new and the old
            patch(oldStartVnode,newEndVnode)
            parentEle.insertBefore(oldStartVnode.elm,oldEndVnode.elm.nextSibling)
            oldStartVnode = oldChild[ ++oldStartIdx ]
            newEndVnode = newChild[ --newEndIdx ]
        }else{
            // Enable loop in all dead
            console.log( oldEndIdx,newStartIdx,'All missed' )

            if(! keyMap){ keyMap = {}for(let i = oldStartIdx; i<= oldEndIdx; i++){
                    const key = oldChild[i].data.key;
                    if(key ! =undefined){ keyMap[key] = i; }}}// Find the location of the current entry (newStartIdx) in the keyMap
            const idxInold = keyMap[newStartVnode.data.key];
            console.log(idxInold)
            if(! idxInold){// If idxInold does not exist, it is completely new
                parentEle.insertBefore( createEle(newStartVnode),oldStartVnode.elm)
            }else{
                // If not, it is not a new item, but a move
                console.log('mobile')
                const eleToMove = oldChild[idxInold]
                patch(eleToMove,newStartVnode);
                oldChild[idxInold] = null;
                parentEle.insertBefore( eleToMove.elm ,oldStartVnode.elm)
            }
            newStartVnode = newChild[ ++newStartIdx ]
        }
    }

    if( newStartIdx <= newEndIdx ){
        console.log('There are some remaining nodes. Add them.')
        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('There are still nodes unprocessed, delete them')
        for( leti = oldStartIdx; i<=oldEndIdx; i++){ parentEle.removeChild(oldChild[i].elm) } } }// Test case
const myVnodeOne = h( 'section', {},'Hello, 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');

// Test that newVNode is text
const newVNodeText = h('ul', {},'hello')
// Test that oldVNode has a text attribute. NewVNode has no text attribute
const newVNodeChild = h('section',{},[
    h('p', {},'As deep as the sea in front'),
    h('p', {},'From now on the girl is a passer-by'),])// Test the minimum update policy
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)
})
Copy the code