# Vue中Diff算法

# 跨平台

因为使用了 Virtual DOM 的原因,Vue.js具有了跨平台的能力,Virtual DOM 终归只是一些 JavaScript 对象罢了,那么最终是如何调用不同平台的 API 的呢?

Vue.js 在渲染时会调用patch 方法。patch 方法是高阶函数 createPatchFunction的返回值,参数是对象。其中,nodeOps 封装了一系列 DOM 操作的方法,modules 定义了一些模块的钩子函数的实现。会在整个 patch 过程的不同阶段执行相应的钩子函数。

patch 是平台相关的,在 WebWeex 环境,它们把 VNode 映射到 真实 DOM 的方法是不同的,并且对 DOM 包括的属性模块创建和更新也不尽相同。因此每个平台都有各自的 nodeOpsmodules,它们的代码需要托管在 src/platforms 这个大目录下。

而不同平台的 patch 的主逻辑部分是相同的,所以这部分公共的部分托管在 core 这个大目录下。差异化部分只需要通过参数来区别,这里用到了一个 函数柯里化 的技巧,通过 createPatchFunction 把差异化参数提前固化,这样不用每次调用 patch 的时候都传递 nodeOpsmodules 了。

通过 nodeOps 对象做适配,根据 platform 区分不同平台来执行当前平台对应的API,而对外则是提供了一致的接口,供 Virtual DOM 来调用。

# patch

patch 的核心 Diff 算法,我们用 Diff 算法可以比对出两颗树的「差异」Diff算法是通过同层的树节点进行比较而非对树进行逐层搜索遍历的方式,所以时间复杂度只有O(n),是一种相当高效的算法。

# 数据更新视图

在对响应式数据进行操作对时候,会触发对应 Dep 中的 Watcher 对象。Watcher 对象会调用对应的 update 来修改视图。最终是将新产生的 VNode 节点与老 VNode 进行一个 patch 的过程,比对得出「差异」,最终将这些「差异」更新到视图上。

Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode
    // Vue.prototype.__patch__ is injected in entry points
    // based on the rendering backend used.
    if (!prevVnode) {
      // initial render 初始化渲染 将 vnode 渲染为真实的 dom 节点,替换调真实的 vm.$el 根节点
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
    } else {
      // updates
      // 数据更新 更新时做Diff操作
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    restoreActiveInstance()
    // update __vue__ reference
    if (prevEl) {
      prevEl.__vue__ = null
    }
    if (vm.$el) {
      vm.$el.__vue__ = vm
    }
    // if parent is an HOC, update its $el as well
    if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
      vm.$parent.$el = vm.$el
    }
    // updated hook is called by the scheduler to ensure that children are
    // updated in a parent's updated hook.
  }

# Diff算法

Vue.js 中 Diff算法是通过同层的树节点进行比较。

# 比对标签

Diff算法首先会对根节点进行比较,如果 tag 标签不一致,直接用新的 VNode 生成真实的 Dom 节点替换旧的 VNode 生成的Dom节点。

if (!isRealElement && sameVnode(oldVnode, vnode)) {
    // patch existing root node
    patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
}

如果标签一致,有可能都是文本节点,那就比较文本的内容即可。

如果是文本,文本都没有 tag,文本内容不一致,直接修改文本即可。

如果标签一致且不是文本就要比对属性。

# 比对属性

比对属性核心是复用Dom节点,并且将新的VNode中的属性更新或新增到Dom节点中,并且删除多余的属性。

简单实现代码如下:

// 复用标签,并且更新属性
let el = vnode.el = oldVnode.el;
updateProperties(vnode,oldVnode.data);
function updateProperties(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 if (key === 'class') {
            el.className = newProps.class;
        } else {
            el.setAttribute(key, newProps[key]);
        }
    }
}

属性比对完,就需要递归比对子节点

# 比对子节点

比对子节点只要存在4种情况:

  • 新老 VNode 都有子节点,需要比对里面的子节点。核心是updateChildren方法
  • 新的 VNode 节点有子节点,老的 VNode 节点没有子节点,则直接将 VNode 子节点转成真实节点,插入真实的父节点即可
  • 新的 VNode 节点没有子节点,老的 VNode 节点有子节点,则真实的父节点删除子节点即可
  • 新老 VNode 都没有子节点,不需进行处理

# updateChildren


function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

function updateChildren(parent, oldChildren, newChildren) {
    // vue采用的是双指针的方式

    // vue在内部比对的过程中做了很多优化策略
    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) => {
        let map = {};
        children.forEach((item, index) => {
            if (item.key) {
                map[item.key] = index; // 根据key 创建一个映射表
            }
        })
        return map;
    }
    let map = makeIndexByKey(oldChildren);

    // 在比对的过程中 新老虚拟节点有一方循环完毕就结束
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // 优化向后插入的情况
        if (!oldStartVnode) { // 在老指针移动过程中可能会碰到undefined
            oldStartVnode = oldChildren[++oldStartIndex]
        } else if (!oldEndVnode) {
            oldEndVnode = oldChildren[--oldEndIndex];
        } else
            if (isSameVnode(oldStartVnode, newStartVnode)) {
                // 优化在oldChildren尾部插入一个新的节点的情况
                // 如果是同一个节点 就需要比对这个元素的属性
                patch(oldStartVnode, newStartVnode); // 比对开头节点
                oldStartVnode = oldChildren[++oldStartIndex];
                newStartVnode = newChildren[++newStartIndex];
            } else if (isSameVnode(oldEndVnode, newEndVnode)) {
                // 优化在oldChildren头部插入一个新的节点的情况
                patch(oldEndVnode, newEndVnode);
                oldEndVnode = oldChildren[--oldEndIndex];
                newEndVnode = newChildren[--newEndIndex]
            } else if (isSameVnode(oldStartVnode, newEndVnode)) {
                // 优化将oldChildren头节点移动到尾部的情况
                patch(oldStartVnode, newEndVnode);
                parent.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
                oldStartVnode = oldChildren[++oldStartIndex];
                newEndVnode = newChildren[--newEndIndex]
            } else if (isSameVnode(oldEndVnode, newStartVnode)) {
                // 优化将oldChildren尾节点移动到头部的情况
                patch(oldEndVnode, newStartVnode);
                parent.insertBefore(oldEndVnode.el, oldStartVnode.el);
                oldEndVnode = oldChildren[--oldEndIndex];
                newStartVnode = newChildren[++newStartIndex];
            } else {
                // 暴力比对  乱序
                // 先根据老节点的key 做一个映射表,拿新的虚拟节点去映射表中查找,如果可以查找到,则进行移动操作(移到头指针的前面位置)  如果找不到则直接将元素插入即可
                let moveIndex = map[newStartVnode.key];
                if (!moveIndex) { // 不需要复用
                    parent.insertBefore(createElm(newStartVnode), oldStartVnode.el);
                } else {
                    // 如果在映射表中查找到了,则直接将元素移走,并且将当前位置置为空
                    let moveVnode = oldChildren[moveIndex]; // 我要移动的那个元素
                    oldChildren[moveIndex] = undefined; // 占位防止塌陷
                    parent.insertBefore(moveVnode.el, oldStartVnode.el);
                    patch(moveVnode, newStartVnode);
                }
                newStartVnode = newChildren[++newStartIndex];
            }
    }
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            let el = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].el;
            parent.insertBefore(createElm(newChildren[i]), el); // 写null 就等价于appendChild
            // 将新增的元素直接进行插入  (可能是像后插入 也有可能从头插入)  insertBefore
        }
    }

    // 删除多余的老节点
    if (oldStartIndex <= oldEndIndex) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            let child = oldChildren[i];
            if (child != undefined) {
                debugger
                parent.removeChild(child.el);
            }
        }
    }
}

Vue.js Diff 算法采用的是双指针的方式。并且在内部比对的过程中做了很多优化策略。

# Diff中的优化策略

# 在开头和结尾新增元素

function updateChildren(parent, 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];

    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // 优化在oldChildren尾部插入一个新的节点的情况
        if(isSameVnode(oldStartVnode,newStartVnode)){
            patch(oldStartVnode,newStartVnode);
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
        // 优化向前追加逻辑
        }else if(isSameVnode(oldEndVnode,newEndVnode)){ 
            // 优化在oldChildren头部插入一个新的节点的情况
            patch(oldEndVnode,newEndVnode); // 比较孩子 
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
        }
    }
    if(newStartIndex <= newEndIndex){
        for(let i = newStartIndex ; i<=newEndIndex ;i++){
            let ele = newChildren[newEndIndex+1] == null? null:newChildren[newEndIndex+1].el;
            parent.insertBefore(createElm(newChildren[i]),ele);
        }
    }
}

如果 oldChildren 为 A,B,C,D,假设在 oldChildren 尾部插入一个新的节点 E

首先会匹配条件判断isSameVnode(oldStartVnode,newStartVnode)。如果条件成立,则会复用节点,将新节点上的属性更新到老节点,删除不需要的旧属性即可。

oldStartIndexoldEndIndex 重合, 遍历结束,将新增的 E 节点插入到尾部即可。

如果 oldChildren 为 A,B,C,D,假设在 oldChildren 头部部插入一个新的节点 E

不符合条件判断isSameVnode(oldStartVnode,newStartVnode)。则会接着匹配条件判断isSameVnode(oldEndVnode,newEndVnode)

如果条件成立,则会复用节点,将新节点上的属性更新到老节点,删除不需要的旧节点即可。

oldStartIndexoldEndIndex 重合, 遍历结束,将新增的 E 节点插入到头部即可。

# 头移尾、尾移头

// 头移动到尾部
else if(isSameVnode(oldStartVnode,newEndVnode)){
    patch(oldStartVnode,newEndVnode);
    parent.insertBefore(oldStartVnode.el,oldEndVnode.el.nextSibling);
    oldStartVnode = oldChildren[++oldStartIndex];
    newEndVnode = newChildren[--newEndIndex]
// 尾部移动到头部
}else if(isSameVnode(oldEndVnode,newStartVnode)){
    patch(oldEndVnode,newStartVnode);
    parent.insertBefore(oldEndVnode.el,oldStartVnode.el);
    oldEndVnode = oldChildren[--oldEndIndex];
    newStartVnode = newChildren[++newStartIndex]
}

如果 oldChildren 为 A,B,C,D,假设将 oldChildren 头部的 A 节点移动到尾部,变成 B,C,D,A。

不符合条件判断isSameVnode(oldStartVnode,newStartVnode)。不符合条件判断isSameVnode(oldEndVnode,newEndVnode)

则会接着匹配条件判断isSameVnode(oldStartVnode,newEndVnode)

如果条件成立,则会复用节点,将新节点上的属性更新到老节点,删除不需要的旧节点即可。

oldStartIndexoldEndIndex 重合, 遍历结束。

# 暴力比对

function createKeyToOldIdx (children, beginIdx, endIdx) {
    let i, key
    const map = {}
    for (i = beginIdx; i <= endIdx; ++i) {
        key = children[i].key
        if (isDef(key)) map[key] = i
    }
    return map
}

// 暴力比对  乱序
// 先根据老节点的key 做一个映射表,拿新的虚拟节点去映射表中查找,如果可以查找到,则进行移动操作(移到头指针的前面位置)  如果找不到则直接将元素插入即可
let moveIndex = map[newStartVnode.key];
if (!moveIndex) { // 不需要复用
    parent.insertBefore(createElm(newStartVnode), oldStartVnode.el);
} else {
    // 如果在映射表中查找到了,则直接将元素移走,并且将当前位置置为空
    let moveVnode = oldChildren[moveIndex]; // 我要移动的那个元素
    oldChildren[moveIndex] = undefined; // 占位防止塌陷
    parent.insertBefore(moveVnode.el, oldStartVnode.el);
    patch(moveVnode, newStartVnode);
}
newStartVnode = newChildren[++newStartIndex];

先根据老节点的key 做一个映射表,拿新的虚拟节点去映射表中查找,如果可以查找到,则进行移动操作(移到头指针的前面位置)复用节点,并更新属性。如果找不到则直接将元素插入即可。最后删除多余的老节点即可。

更新时间: 6/15/2020, 4:13:34 AM