跳到主要内容

diff 算法

Vue.js 的虚拟 DOM (VNode) 和 diff 算法是 Vue.js 高效更新 DOM 的关键技术。Vue 2.x 版本中，虚拟 DOM 和 diff 算法的核心思想是通过比较新旧虚拟 DOM 的差异，计算出最小的更新操作，然后应用这些操作到真实的 DOM 上，以达到高效渲染的目的。

1. 虚拟 DOM (VNode)​

  • 使用 JS 模拟 Dom 结构
  • Dom diff 的对比，放在 JS 层来做(图灵完备语言: 可以处理逻辑算法的语言)
  • 提高重绘性能
  • Dom 操作开销较大，执行 diff 算法性能影响小
<ul class="wrap">
    <li class="item1">item1</li>
    <li class="item2">item1</li>
    <li class="item3">item1</li>
</ul>

vnode :

{
    tag: "ul",
    attribute: {
       className: 'warp'
    },
    children: [
       {
           tag: "li",
           attribute: [
               className: 'item1'
           ],
           children: ['item1']
       },
       {
           tag: "li",
           attribute: [
               className: 'item2'
           ],
           children: ['item2']
       },
       {
           tag: "li",
           attribute: [
               className: 'item3'
           ],
           children: ['item3']
       }
    ]
}

diff 算法​

Vue 的 diff 算法是基于虚拟 DOM 的一种高效算法，用于比较两棵树（新旧虚拟 DOM 树）并确定如何最小化地更新 DOM。

Alt text

核心思路​

  1. 同层比较：只比较同一层级的节点，不跨层级比较。这样可以减少比较的复杂度，提高效率。
  2. key 的作用：给每个节点分配一个唯一的 key 可以帮助 Vue 快速识别和比较虚拟 DOM 中的节点，尤其是在列表渲染时，通过 key 可以有效地重用和重新排序节点，而不是重新渲染整个列表。
  3. 双端比较：在比较同层级的多个子节点时，Vue 采用双端比较的策略。具体来说，就是同时从旧节点和新节点的两端开始比较，通过四种基本操作（头头、尾尾、头尾、尾头比较）快速识别出哪些节点是可以复用的。
// 头头
if (sameVnode(oldStartVnode, newStartVnode)) {
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
    oldStartVnode = oldCh[++oldStartIdx];
    newStartVnode = newCh[++newStartIdx];
} 
// 尾尾
else if (sameVnode(oldEndVnode, newEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
    oldEndVnode = oldCh[--oldEndIdx];
    newEndVnode = newCh[--newEndIdx];
} 
// 头尾
else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
    api.insertBefore(
        parentElm,
        oldStartVnode.elm!,
        api.nextSibling(oldEndVnode.elm!)
    );
    oldStartVnode = oldCh[++oldStartIdx];
    newEndVnode = newCh[--newEndIdx];
} 
// 尾头
else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
    api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
    oldEndVnode = oldCh[--oldEndIdx];
    newStartVnode = newCh[++newStartIdx];
}

patch 函数​

在Vue中，每当组件的状态发生变化时，Vue会生成一个新的虚拟DOM树，并将这个新树与旧的虚拟DOM树进行比较。这个比较过程就是通过patch函数来完成的。patch函数的目标是找出两棵树的差异（即“补丁”），并且只更新那些实际发生变化的部分，而不是重新渲染整个DOM树。

patch函数的工作流程​

  1. 比较新旧节点：首先，patch会比较新旧虚拟节点。如果它们完全相同（即，是同一个对象），则不做任何操作。如果它们有不同的标签或者key属性，意味着节点不同，旧节点将被移除，并创建新节点。
  2. 更新节点：如果新旧节点是同一类型的，patch会详细比较并更新节点的属性（如class、style等）、事件监听器等。对于文本节点，如果文本发生变化，直接更新文本内容。
  3. 递归子节点：如果新旧节点都有子节点，patch函数会递归地对子节点进行diff比较。Vue在这一步采用了一种高效的策略，只比较同一层级的子节点，并尽量重用节点。
  4. 列表对比：对于子节点的列表，Vue使用了一种高效的算法来最小化DOM操作。这个算法通过同时从旧列表和新列表的两端开始比较，识别出可以重用的节点，以及需要移动、添加或删除的节点。

patch函数的优化策略​

  1. 静态节点优化：Vue会在编译阶段标记静态节点（即，不会改变的节点），这样在patch过程中就可以跳过这些节点，因为它们不会发生变化。
  2. key属性：在处理列表时，使用key属性可以帮助Vue更快地识别节点是否可以重用，从而减少不必要的DOM操作。
  3. 预判节点类型：通过判断节点类型（如元素节点、文本节点等），Vue可以快速决定采取的更新策略，避免不必要的比较。

patch 源码​

// 简化的虚拟节点构造函数
function VNode(tag, data, children, text, elm) {
  this.tag = tag; // 标签名
  this.data = data; // 节点数据，如属性、指令等
  this.children = children; // 子节点数组
  this.text = text; // 文本内容
  this.elm = elm; // 对应的真实DOM节点
}

// 简化的patch函数，只处理元素和文本节点的创建、更新
function patch(oldVnode, newVnode) {
  // 如果新旧vnode相同，则不做任何处理
  if (oldVnode === newVnode) return;

  // 如果新旧vnode是同一个类型的节点
  if (oldVnode.tag === newVnode.tag && oldVnode.key === newVnode.key) {
    // 更新节点属性等（示例中略去细节）
    updateNodeAttributes(oldVnode, newVnode);

    // 递归更新子节点
    updateChildren(oldVnode.children, newVnode.children);
  } else {
    // 如果节点不同，则替换旧节点
    const oldElm = oldVnode.elm;
    const newElm = createElement(newVnode); // 创建新节点
    if (oldElm.parentNode) {
      oldElm.parentNode.replaceChild(newElm, oldElm);
    }
  }
}

function updateNodeAttributes(oldVnode, newVnode) {
  // 更新节点的属性（示例中略去细节）
}

function updateChildren(oldChildren, newChildren) {
  // 递归更新子节点（示例中略去细节）
}

function createElement(vnode) {
  // 根据vnode创建真实DOM节点（示例中略去细节）
}

如何判断两个 vnode 相同​

  1. 类型（Type）: 如果两个vnode的类型不同（例如，一个是div，另一个是span），则它们不相同。
  2. 键（Key）: 如果两个vnode都有key属性，那么只有当它们的key相同时，它们才相同。key用于识别在同一层级的不同兄弟节点。
  3. 属性（Props）: 如果它们的属性不同，它们也不相同。属性比较可能涉及深度比较。
  4. 文本内容（Text）: 对于文本节点，如果文本内容不同，它们不相同。
function isSameVnode(vnode1, vnode2) {
  // 检查类型
  if (vnode1.type !== vnode2.type) {
    return false;
  }

  // 检查键
  if (vnode1.key !== vnode2.key) {
    return false;
  }

  // 检查标签名
  if (vnode1.tag !== vnode2.tag) {
    return false;
  }

  // 进一步的属性或文本内容比较可以在这里实现
  // 例如，比较属性对象或文本内容等

  // 如果通过所有检查，认为它们相同
  return true;
}

子节点diff算法​

源码链接

  • tagName 不一致
  • attribute 不一致
  • children 不一致(重点)
function updateChildren(
    parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue
    ) 
{
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    let oldKeyToIdx: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
        } else if (oldEndVnode == null) {
        oldEndVnode = oldCh[--oldEndIdx];
        } else if (newStartVnode == null) {
        newStartVnode = newCh[++newStartIdx];
        } else if (newEndVnode == null) {
        newEndVnode = newCh[--newEndIdx];
        } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
        } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
        } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(
            parentElm,
            oldStartVnode.elm!,
            api.nextSibling(oldEndVnode.elm!)
        );
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];
        } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];
        } else {
        if (oldKeyToIdx === undefined) {
            oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        idxInOld = oldKeyToIdx[newStartVnode.key!];
        if (idxInOld === undefined) {
            // `newStartVnode` is new, create and insert it in beginning
            api.insertBefore(
            parentElm,
            createElm(newStartVnode, insertedVnodeQueue),
            oldStartVnode.elm!
            );
            newStartVnode = newCh[++newStartIdx];
        } else if (oldKeyToIdx[newEndVnode.key!] === undefined) {
            // `newEndVnode` is new, create and insert it in the end
            api.insertBefore(
            parentElm,
            createElm(newEndVnode, insertedVnodeQueue),
            api.nextSibling(oldEndVnode.elm!)
            );
            newEndVnode = newCh[--newEndIdx];
        } else {
            // Neither of the new endpoints are new vnodes, so we make progress by
            // moving `newStartVnode` into position
            elmToMove = oldCh[idxInOld];
            if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(
                parentElm,
                createElm(newStartVnode, insertedVnodeQueue),
                oldStartVnode.elm!
            );
            } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
            }
            newStartVnode = newCh[++newStartIdx];
        }
        }
    }

    if (newStartIdx <= newEndIdx) {
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
        addVnodes(
        parentElm,
        before,
        newCh,
        newStartIdx,
        newEndIdx,
        insertedVnodeQueue
        );
    }
    if (oldStartIdx <= oldEndIdx) {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
    // ... 代码简化
}

diff 过程​

在更新 DOM 时，Vue 会创建一个新的虚拟 DOM 树，并将其与旧的虚拟 DOM 树进行比较。比较过程遵循以下步骤：

  1. 开始和结束节点的比较：首先比较旧树和新树的开始节点（头头比较），然后比较它们的结束节点（尾尾比较）。如果开始或结束节点是相同的（即，相同的标签和 key），它们可以被快速更新。
  2. 交叉比较：如果开始和结束节点不匹配，Vue 将尝试交叉比较旧树的开始节点与新树的结束节点（头尾比较），以及旧树的结束节点与新树的开始节点（尾头比较）。这有助于识别节点的移动。
  3. 未找到匹配节点：如果以上步骤都未找到匹配节点，Vue 会用新树的开始节点去旧树中寻找相同 key 的节点。如果找到，将该节点移动到正确的位置。如果没有找到，说明是一个新节点，将其创建并插入。
  4. 更新剩余的节点：经过上述步骤后，如果旧树和新树中还有未处理的节点，Vue 将根据情况添加新节点或删除旧节点。