diff的快速了解 - javascript

简介

diff算法存在很多的地方，比如linux中可以对比两文件的差异；Beyond Compare 4这个软件对比线上文件以及本地的文件差异；git 上对比文件差异等……
而前端中使用diff算法主要是为了减少DOM的操作，因为在浏览器中对DOM的操作代价以及速度比执行JavaScript性能消耗代价要大；使用diff算法可以找出新旧两个vNode的差异，进行对比更新从而只更新需要更新的节点；一切为了优化

开始

1. 以下过程基于Vue
   Vue的基本编译过程为：
   Template->AST->render->vNode->新旧vNode对比>diff和patch->updater

   AST与vNnode合并的对对象属性进行监听时候生成dep，形成闭包；初次mount的时候将watcher放到Dep变量中，然后调用render将AST以及data一同combine成vNode；combine的时候会调用dep里的方法将watcher push到被一开始defineProperty被监听的dep中；当data进行更新的时候会调用notify通知watcher进行update；diff发生在通知所有订阅者watcher之后，将虚拟dom渲染到页面中之前，新旧vNode进行对比，打补丁，更新对应的DOM；

2. 以下不基于Vue
   假设以下图片为旧的vDom以及新的vDom的树结构（不考虑位移，只考虑文本替删除以及替换新节点）
   
   假设我现在有两个vDom树（与上图结构无联系，上图仅做为一个抽象的理解）：

const vDom1 = createElement('ul', {
        class: 'list',
        style: 'width:300px;height:300px;background:orenge'
    },
    [
        createElement('li', {
            class: 'item',
            'data-index': 0
        }, [
            createElement('p', {
                class: 'text'
            }, ['第1个列表']),
        ]),
        createElement('li', {
            class: 'item',
            'data-index': 1
        }, [
            createElement('p', {
                class: 'text'
            }, [
                createElement('span', {
                    class: 'title'
                }, ['第2个列表'])
            ])
        ]),
        createElement('li', {
            class: 'item',
            'data-index': 2
        }, ['第3个列表'])
    ]
)

const vDom2 = createElement('ul', {
        class: 'list',
        style: 'width:300px;height:300px;background:orenge'
    },
    [
        createElement('li', {
            class: 'item',
            'data-index': 0
        }, [
            createElement('p', {
                class: 'text'
            }, ['第12个列表']),
        ]),
        createElement('li', {
            class: 'item',
            'data-index': 1
        }, [
            createElement('p', {
                class: 'text'
            }, [
                createElement('span', {
                    class: 'title'
                }, ['第2个列表'])
            ])
        ]),
        createElement('div', {
            class: 'item',
            'data-index': 2
        }, ['第3个列表'])
    ]
)

我需要对这两个节点进行domDiff以获得补丁

// 节点index
// 标记节点，深度遍历
let vNodeIndex = 0;
// 生成补丁
function domDiff(oldVDom, newVDom) {
    // '../img/domdiff图示.png'
    let index = 0; //根节点vnnodewalk的index
    vnodeWalk(oldVDom, newVDom, index)
    return patches
}

function vnodeWalk(oldNode, newNode, index) {
    let vnPatch = []
    // 如果新的newNode没有了
    if (!newNode) {
        vnPatch.push({
            type: REMOVE,
            index
        })
    } else if (typeof oldNode === 'string' && typeof newNode === 'string') {
        if (oldNode !== newNode) {
            vnPatch.push({
                type: TEXT,
                text: newNode
            })
        }
    } else if (oldNode.type == newNode.type) {
        const attrPatch = attrsWalk(oldNode.props, newNode.props)
        if (Object.keys(attrPatch).length) {
            vnPatch.push({
                type: ATTR,
                attrs: attrPatch
            })
        }
        childrenWalk(oldNode.children, newNode.children)
    } else {
        vnPatch.push({
            type: REPLACE,
            newNode
        })
    }
    if (vnPatch.length) {
        patches[index] = vnPatch
    }
}

function attrsWalk(odlAattrs, newAattrs) {
    let attrPatch = {};
    for (const key in odlAattrs) {
        if (odlAattrs[key] != newAattrs[key]) {
            attrPatch[key] = newAattrs[key]
        }
    }
    for (const key in newAattrs) {
        if (!odlAattrs.hasOwnProperty(key)) {
            attrPatch[key] = newAattrs[key]
        }
    }
    return attrPatch
}

function childrenWalk(oldChildren, newChildren) {
    oldChildren.map((item, index) => {
        vnodeWalk(item, newChildren[index], ++vNodeIndex)
    })
}

domDiff完得到一个补丁，结构如下

patches = {
    2: [{
        type: 'TEXT',
        text: '第12个列表'
    }],
}

期中type表示更改的dom进行了什么修改，基本有如下操作

export const ATTR = 'ATTR'
export const TEXT = 'TEXT'
export const REPLACE = 'REPLACE'
export const REMOVE = 'REMOVE'

等……

获得补丁之后就是更新差异了，doPatch

let finalPatches = {}
let rnIndex = 0

function doPatch(rDom, patches) {
    finalPatches = patches;
    rNodeWalk(rDom)
}

function rNodeWalk(rNode) {
    const rnPatch = finalPatches[rnIndex++];
    let childNodes = rNode.childNodes;
    [...childNodes].map(item => {
        doPatch(item, finalPatches)
    })
    //  获取更新
    if (rnPatch) {
        patchAction(rNode, rnPatch)
    }

}

function patchAction(rNode, rnPatch) {
    rnPatch.map(p => {
        switch (p.type) {
            case ATTR:

                for (const key in p.attrs) {
                    const value = p.attrs[key];
                    if (value) {
                        setAttrs(rNode, key, value)
                    } else {
                        rNode.removeAttribute(key)
                    }
                }
                break;
            case TEXT:
                rNode.textContent = p.text;
                break;
            case REPLACE:
                const newNode = (p.newNode instanceof Element) ? render(p.newNode) : document.createTextNode(p.newNode);
                rNode.parentNode.replaceChild(newNode, rNode)
                break;
            case REMOVE:
                rNode.parentNode.removeChild(rNode)
                break;
            default:
                break;
        }
    })
}

更新差异，替换需要更新的节点；大致diff的流程就是这样；获取补丁，更新差异。就可以做到更新所需更新的节点