puppy 的技术笔记

# Vue2 Diff算法与patch实现

  Vue2 通过其核心的 Diff 算法和 patch 机制实现了高效的 DOM 更新。当数据变化时，Diff 算法会对比新旧虚拟 DOM 树的差异，计算出最小变更集；patch 函数则负责将这些变更精准应用到真实 DOM 上。本文将详细剖析 Vue2 的 Diff 算法实现原理，包括同级比较策略、key的作用以及 patch 函数的工作流程，帮助开发者深入理解Vue2的高效更新机制。同时也会通过具体示例，来帮每个人理解 diff 是怎样一步步完成更新的。

  首先，当响应式数据发生变化后会触发视图更新，不了解的可以看这篇文章。具体表现在源码中是updateComponent函数：

updateComponent = function () {
  vm._update(vm._render(), hydrating);
};

vm._render() 函数的作用是生成虚拟 dom，也就是 vnode。 而vm._update 函数的作用就是更新视图，其中核心代码是这样的：

var prevVnode = vm._vnode;
if (!prevVnode) {
  // initial render
  vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */);
} else {
  // updates
  vm.$el = vm.__patch__(prevVnode, vnode);
}

patch 函数就是 Vue2 中实现虚拟 DOM 差异更新的核心方法，它负责将新旧虚拟 DOM 树进行比对（即 diff 过程），找出最小变更集进行高效更新。接下来就来了解下详细过程。

# 一、patch 原理

  patch 函数代码如下，我们来逐步看下到底做了什么。

patch(oldVnode, vnode, hydrating, removeOnly) {
  // 第一步：新节点不存在，则直接删除旧节点
  if (isUndef(vnode)) {
    if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
    return;
  }
  // 第二步：旧节点不存在，则直接创建新节点
  var isInitialPatch = false;
  var insertedVnodeQueue = [];
  if (isUndef(oldVnode)) {
    isInitialPatch = true;
    createElm(vnode, insertedVnodeQueue);
  } else {
    var isRealElement = isDef(oldVnode.nodeType);
    if (!isRealElement && sameVnode(oldVnode, vnode)) {
      // 第三步：新旧节点一致，进行差异更新
      patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);
    } else {
      // 第四步：新旧节点不同，创建新节点替换旧节点
      if (isRealElement) {
        ...
        oldVnode = emptyNodeAt(oldVnode);
      }
      var oldElm = oldVnode.elm;
      var parentElm = nodeOps.parentNode(oldElm);
      createElm(vnode, insertedVnodeQueue,
      oldElm._leaveCb ? null : parentElm, nodeOps.nextSibling(oldElm));
      if (isDef(vnode.parent)) {
        var ancestor = vnode.parent;
        var patchable = isPatchable(vnode);
        while (ancestor) {
          ...
        }
      }
      // destroy old node
      if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0, 0);
      }
      else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode);
      }
    }
  }
  invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);
  return vnode.elm;
}

# 1.新节点不存在，则直接删除旧节点

if (isUndef(vnode)) {
  if (isDef(oldVnode)) invokeDestroyHook(oldVnode);
  return;
}

  1. 首先通过isUndef(vnode)判断新节点是否存在

    function isUndef(v) {
  return v === undefined || v === null;
}

  2. 然后通过isDef(oldVnode)判断旧节点是否存在

    function isDef(v) {
  return v !== undefined && v !== null;
}

  3. 存在旧节点则用invokeDestroyHook(oldVnode)删除旧节点

    function invokeDestroyHook(vnode) {
  var i, j; // 声明临时变量用于循环
  var data = vnode.data; // 获取vnode的data对象
  if (isDef(data)) {
    // 检查data是否存在
    if (isDef((i = data.hook)) && isDef((i = i.destroy))) i(vnode); // 执行组件destroy钩子
    for (i = 0; i < cbs.destroy.length; ++i) cbs.destroy[i](vnode); // 执行所有destroy回调
  }
  if (isDef((i = vnode.children))) {
    // 检查是否有子节点
    for (j = 0; j < vnode.children.length; ++j) {
      invokeDestroyHook(vnode.children[j]); // 递归调用销毁钩子
    }
  }
}

      关于执行所有 destroy 回调这一步我详细解释下。首先这个 cbs 是在 Vue2 中一个重要的内部对象，包含了 create、update、destroy 等钩子函数集合。大概长这样：

    cbs = {
  create: [],
  activate: [],
  update: [],
  destroy: [], // 这里存储所有销毁相关的回调
};

      我们来看下具体的创建过程。

    // 这里我改造了下代码，便于直观展示创建过程
var cbs = {};
var hooks = ["create", "activate", "update", "remove", "destroy"];
// modules是特定的模块集合，每个模块都实现了特定的钩子函数，类似{create: function(){}, update: function(){}}
var modules = [
  attrs,
  klass$1,
  events,
  domProps,
  style$1,
  transition,
  ref,
  directives$1,
];

for (i = 0; i < hooks.length; ++i) {
  // 循环遍历钩子类型
  cbs[hooks[i]] = []; // 初始化一个数组
  for (j = 0; j < modules.length; ++j) {
    // 遍历 modules 将对应的钩子添加到对应的数组中
    if (isDef(modules[j][hooks[i]])) {
      cbs[hooks[i]].push(modules[j][hooks[i]]);
    }
  }
}

    所以当销毁旧节点时，不仅仅会调用组件的 destroy 钩子，还会执行所有其它特定模块的 destroy 回调。

    • attrs ：处理 HTML 属性
    • klass$1 ：处理 class 绑定
    • events ：处理事件监听
    • domProps ：处理 DOM 属性
    • style$1 ：处理内联样式
    • transition ：处理过渡动画
    • ref ：处理 ref 指令
    • directives$1 ：处理自定义指令

  4. 最后返回undefined, 相当于 vm.$el = undefined。

# 2.旧节点不存在，创建新节点

var isInitialPatch = false;
var insertedVnodeQueue = [];
if (isUndef(oldVnode)) {
  isInitialPatch = true;
  createElm(vnode, insertedVnodeQueue);
}

createElm 函数主要负责创建新节点

# 3.新旧节点一致，进行差异更新

var isRealElement = isDef(oldVnode.nodeType);
if (!isRealElement && sameVnode(oldVnode, vnode)) {
}

  首先会判断新旧节点结构是否一致。isRealElement 表示旧节点是否是真实 DOM 元素。初始化渲染时 isRealElement=true新旧节点肯定是不一致的，直接走 else 逻辑。当二者都是虚拟节点时，会调用sameVnode判断二者结构是否一致。

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

  1. 基础标识匹配

    • 判断两个节点的 key 是否相同：a.key === b.key
    • 判断两个节点的异步工厂函数是否相同：a.asyncFactory === b.asyncFactory

  2. 节点类型匹配（满足以下任一条件） a. 常规节点匹配：

    • 判断两个节点的 tag 是否相同：a.tag === b.tag
    • 判断两个节点是否都是注释节点：a.isComment === b.isComment
    • 判断两个节点是否都有 data 属性：isDef(a.data) === isDef(b.data)
    • 判断两个节点的 input 类型是否相同：sameInputType(a, b)

    b. 异步组件匹配：

    • 判断旧节点是否是异步占位符：isTrue(a.isAsyncPlaceholder)
    • 判断新节点是否有错误：isUndef(b.asyncFactory.error)

  当以上条件都满足时，说明新旧节点是相同的，需要进行差异更新。我们来看看patchVnode的具体过程。

patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);
function patchVnode(
  oldVnode,
  vnode,
  insertedVnodeQueue,
  ownerArray,
  index,
  removeOnly
) {
  // 1. 节点复用检查
  if (oldVnode === vnode) {
    return;
  }
  // 2. 克隆复用节点
  if (isDef(vnode.elm) && isDef(ownerArray)) {
    vnode = ownerArray[index] = cloneVNode(vnode);
  }
  var elm = (vnode.elm = oldVnode.elm);
  // 3. 处理异步组件
  if (isTrue(oldVnode.isAsyncPlaceholder)) {
    if (isDef(vnode.asyncFactory.resolved)) {
      hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
    } else {
      vnode.isAsyncPlaceholder = true;
    }
    return;
  }
  // 4. 静态节点优化
  if (
    isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }
  // 5. prepatch钩子
  var i;
  var data = vnode.data;
  if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
    i(oldVnode, vnode);
  }
  var oldCh = oldVnode.children;
  var ch = vnode.children;
  // 6. 模块更新钩子
  if (isDef(data) && isPatchable(vnode)) {
    for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
    if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
  }
  // 7. 子节点对比更新
  if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      if (process.env.NODE_ENV !== "production") {
        checkDuplicateKeys(ch);
      }
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, "");
    }
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }
  // 8. 触发组件postpatch钩子
  if (isDef(data)) {
    if (isDef((i = data.hook)) && isDef((i = i.postpatch))) i(oldVnode, vnode);
  }
}

  1. 节点复用检查：如果oldVnode === vnode,则直接返回，避免重复操作。

  2. 克隆复用节点：cloneVNode(vnode),这一步主要是updateChildren时执行,后面讲 diff 算法时会提到。

  3. 处理异步组件：如果旧节点是异步占位符（异步占位符是在异步组件加载完成之前，用于临时占据该组件位置的虚拟节点），会根据新节点是否有解析完成的异步组件来进行不同的处理。加载完成则激活异步组件，如果未加载完成， vnode 会被标记为异步占位符，待组件加载完成后再进行渲染。

    if (isTrue(oldVnode.isAsyncPlaceholder)) {
  if (isDef(vnode.asyncFactory.resolved)) {
    hydrate(oldVnode.elm, vnode, insertedVnodeQueue);
  } else {
    vnode.isAsyncPlaceholder = true;
  }
  return;
}

  4. 静态节点优化：如果新旧节点都是静态节点(静态节点指的是不会发生变化的节点，如文本节点、注释节点等)，且 key 相同，并且新节点是克隆节点或只渲染一次。会复用旧节点的组件实例, 并跳过子节点对比。

      if (
    isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    vnode.componentInstance = oldVnode.componentInstance;
    return;
  }

  5. 触发组件prepatch生命周期：prepatch 是专为虚拟 DOM 更新流程设计的钩子，主要作用是更新子组件props、listeners和children

      prepatch: function (oldVnode, vnode) {
    var options = vnode.componentOptions;
    var child = (vnode.componentInstance = oldVnode.componentInstance);
    updateChildComponent(child, options.propsData, // updated props
      options.listeners, // updated listeners
      vnode, // new parent vnode
      options.children // new children
    )
  }

  6. 模块更新钩子：遍历cbs.update调用所有注册的模块更新函数。cbs 是什么之前讲过了, 在这里。

    if (isDef(data) && isPatchable(vnode)) {
  for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
  if (isDef((i = data.hook)) && isDef((i = i.update))) i(oldVnode, vnode);
}

  7. 子节点对比更新:

      if (isUndef(vnode.text)) {
    if (isDef(oldCh) && isDef(ch)) {
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly);
    } else if (isDef(ch)) {
      if (process.env.NODE_ENV !== "production") {
        checkDuplicateKeys(ch);
      }
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, "");
    }
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }
    • 新节点存在文本节点且和旧节点内容不同，则直接更新文本内容
    • 新旧节点都有子节点且不同，则执行 updateChildren,核心算法 diff 实现。
    • 新节点存在子节点而旧的不存在，若旧节点有文本内容则清空，然后调用 addVnodes 函数添加新子节点。
    • 新节点不存在子节点而旧的存在，若旧节点有子节点则删除旧节点的子节点。
    • 若旧节点有文本内容，则清空该文本

  8. 触发组件postpatch钩子：dom 更新后的处理，执行 DOM 更新后的副作用逻辑。

  整个差异更新流程如上，基本上关于更新部分的总结可以列为以下几点：

  1. 判断 vnode 和 oldVnode 是否指向同一个对象，一样直接返回
  2. 如果他们都有文本节点并且不想等，则将 el 的文本替换为 vNode 的文本节点
  3. 如果两者都有子节点，则执行 updateChildren 函数比较子节点（diff算法）
  4. 如果 oldVnode 没有子节点而 Vnode 有，则将 Vnode 的子节点真实化后添加到 el
  5. 如果 oldVnode 有子节点而 Vnode 没有，则直接删除 el 的子节点
  6. 如果 oldVnode 有文本内容，则清空该文本

# 4.新旧节点不一致，创建新节点替换旧节点

  if (isRealElement) {
    // 省略关于服务端渲染相关操作
    ...
    // 1. 清空旧节点
    oldVnode = emptyNodeAt(oldVnode);
  }
  var oldElm = oldVnode.elm;
  var parentElm = nodeOps.parentNode(oldElm);
  // 2. 创建新节点
  createElm(vnode, insertedVnodeQueue, oldElm._leaveCb ? null : parentElm, nodeOps.nextSibling(oldElm));
  if (isDef(vnode.parent)) {
    var ancestor = vnode.parent;
    var patchable = isPatchable(vnode);
    while (ancestor) {
      // 3. 递归更新父节点
      for (var i_8 = 0; i_8 < cbs.destroy.length; ++i_8) {
        cbs.destroy[i_8](ancestor);
      }
      ancestor.elm = vnode.elm;
      if (patchable) {
        for (var i_9 = 0; i_9 < cbs.create.length; ++i_9) {
            cbs.create[i_9](emptyNode, ancestor);
        }
        var insert_1 = ancestor.data.hook.insert;
        if (insert_1.merged) {
          for (var i_10 = 1; i_10 < insert_1.fns.length; i_10++) {
              insert_1.fns[i_10]();
          }
        }
      }
      else {
        registerRef(ancestor);
      }
      ancestor = ancestor.parent;
    }
  }
  // destroy old node
  if (isDef(parentElm)) {
      removeVnodes([oldVnode], 0, 0);
  }
  else if (isDef(oldVnode.tag)) {
      invokeDestroyHook(oldVnode);
  }
  1. 清空旧节点：
    • 通过emptyNodeAt(oldVnode)清空旧节点
    • 通过nodeOps.parentNode(oldElm)定位父节点
  2. 创建新节点：通过 createElm方法创建新节点。
  3. 递归更新父节点：cbs 内容在这里。
    • 递归更新父节点，直到根节点。
    • 调用 cbs.destroy 钩子函数销毁旧节点（及时更新父组件的引用）。
    • 调用 cbs.create 钩子函数创建新节点。
    • 调用 insert 钩子函数触发插入操作（确保DOM完全插入后再执行操作）。
  4. 旧节点清理
    • 有父节点则，调用 removeVnodes 函数从DOM树移除旧节点。
    • 没有父节点则调用invokeDestroyHook方法触发 destroy 钩子完成资源释放。和 新节点不存在，则直接删除旧节点是一样的。

  对于 第2、3、4、种情况，都会调用invokeInsertHook方法执行自定义指令的 insert 方法。

function invokeInsertHook(vnode, queue, initial) {
  // 次渲染且存在父节点
  if (isTrue(initial) && isDef(vnode.parent)) {
    // 延迟到父节点插入后执行
    vnode.parent.data.pendingInsert = queue;
  }
  // 非首次渲染或没有父节点
  else {
    for (var i_6 = 0; i_6 < queue.length; ++i_6) {
      // 立即执行所有insert钩子
      queue[i_6].data.hook.insert(queue[i_6]);
    }
  }
}

# 二、Diff 原理

  上文我们在讲 patch 函数时，在差异更新时会调用 updateChildren 方法，该方法的核心就是 diff 算法。我们先来看下这个方法的源码。

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  var oldStartIdx = 0;
  var newStartIdx = 0;
  var oldEndIdx = oldCh.length - 1;
  var oldStartVnode = oldCh[0];
  var oldEndVnode = oldCh[oldEndIdx];
  var newEndIdx = newCh.length - 1;
  var newStartVnode = newCh[0];
  var newEndVnode = newCh[newEndIdx];
  var oldKeyToIdx, idxInOld, vnodeToMove, refElm;
  var canMove = !removeOnly;
  if (process.env.NODE_ENV !== 'production') {
    checkDuplicateKeys(newCh);
  }
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    }
    else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    }
    // 1.头头比较
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 2.尾尾比较
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 3.头尾比较
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);
      canMove &&
          nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 4.尾头比较
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
      canMove &&
          nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 5.包含步骤
    else {
      // 5.1 创建key到索引的映射
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      // 5.2 查找新节点在旧节点中的索引
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      // 5.3 索引不存在则创建新节点
      if (isUndef(idxInOld)) {
        // New element
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
      }
      // 5.4 索引存在则移动节点位置
      else {
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
          oldCh[idxInOld] = undefined;
          canMove &&
              nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
        }
        else {
          // same key but different element. treat as new element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  }
  else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}

# Diff 原理详解

  首先，vue2 的 diff 算法是四指针，双向遍历的。它定义了四个指针，分别指向新旧两组节点的头和尾。

var oldStartIdx = 0;
var newStartIdx = 0;
var oldEndIdx = oldCh.length - 1;
var oldStartVnode = oldCh[0];
var oldEndVnode = oldCh[oldEndIdx];
var newEndIdx = newCh.length - 1;
var newStartVnode = newCh[0];
var newEndVnode = newCh[newEndIdx];

  然后整个 diff 过程分为 5 步走。

  1. 头头比较： sameVnode(oldStartVnode, newStartVnode)相同的话，则执行 patchVnode进行差异更新，这个函数我们之前分析过了。所以说 vue2 的 diff算法也是深度优先遍历。然后两个头索引都后移。不同则进行步骤2。

  2. 尾尾比较：sameVnode(oldEndVnode, newEndVnode)相同的话，则执行 patchVnode进行差异更新，然后两个尾索引都前移。不同则进行步骤3。

  3. 头尾比较：sameVnode(oldStartVnode, newEndVnode)相同，则执行 patchVnode进行差异更新。除了更新头尾两个指针的位置外，它还需要将 oldStartVnode 对应的真实 DOM 节点插入到 oldEndVnode 对应的真实 DOM 节点的后面。不同则进行步骤4.

      canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));

  4. 尾头比较：sameVnode(oldEndVnode, newStartVnode)相同，则执行 patchVnode进行差异更新。除了更新尾头两个指针的位置外，它还需要将 oldEndVnode 对应的真实 DOM 节点插入到 oldStartVnode 对应的真实 DOM 节点的前面。不同则进行步骤5

      canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));

  5. 包含步骤：

    1. 创建key到索引的映射：oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)。示例：{key1: 0, key2: 1}

    2. 查找 newStartVnode 所匹配的旧节点的位置 idxInOld。如果 newStartVnode 有 key，则通过 key 去查找，如果没有，则遍历旧节点通过 sameVnode 判断来查找

        idxInOld = isDef(newStartVnode.key)
    ? oldKeyToIdx[newStartVnode.key]
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);

  function findIdxInOld(node, oldCh, start, end) {
    for (var i_5 = start; i_5 < end; i_5++) {
      var c = oldCh[i_5];
      if (isDef(c) && sameVnode(node, c))
        return i_5;
    }
  }

    3. 如果 idxInOld 不存在，则说明新节点是一个全新的节点，需要创建新节点。

        if (isUndef(idxInOld)) {
    // New element
    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
  }

    4. 如果 idxInOld 存在，则说明旧节点存在于新节点中。这时候要用 sameVnode 判断旧节点是否可以复用。如果可以复用，则执行 patchVnode进行差异更新，同时将该节点的位置置空。并在dom层种移动元素位置，如果不可以复用，则创建一个新节点。

        vnodeToMove = oldCh[idxInOld];
  if (sameVnode(vnodeToMove, newStartVnode)) {
    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
    oldCh[idxInOld] = undefined;
    canMove &&
        nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);
  }
  else {
    // same key but different element. treat as new element
    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
  }

    5. 更新新节点的头索引位置，向后移动一位。newStartVnode = newCh[++newStartIdx]

特殊处理：

  • 如果 oldStartVnode 不存在，说明该节点被移动了，更新oldStartIdx向后移动一位。
  • 如果 oldEndVnode 不存在，说明该节点被移动了，更新oldEndIdx向前移动一位。
if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
}
else if (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[--oldEndIdx];
}

特别注意，上述关于节点的移动是 dom 层的移动，原 oldCh 数组中不会主动更换元素位置，只是移动指针。所有指针的指向都是针对 oldCh 数组来完成的。

  当整个 while 循环结束后，还需要进行批量更新的操作。

  • 旧节点遍历完成，新节点还有剩余节点，则需要将新节点中剩余的节点插入到 DOM 中。

      if (oldStartIdx > oldEndIdx) {
    // 确定插入位置
    refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
  }

  • 新节点遍历完成，旧节点还有剩余节点，则需要将旧节点中剩余的节点从 DOM 中移除。

      if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }

# 示例

  假设旧节点组为 oldCh = [A, B, C, D, E, F, G]，新节点组为 newCh = [A, D, E, C, F, H, B, G]。

  1. 初始化四个索引,进入while循环: oldStartIdx = 0, oldEndIdx = 6, newStartIdx = 0, newEndIdx = 7。dom = [A, B, C, D, E, F, G]

    • 头头比较，A 和 A 相同，执行 patchVnode 进行差异更新。然后两个头索引都后移。oldStartIdx = 1, newStartIdx = 1。

  2. 重新进入 while 循环: oldStartIdx = 1, oldEndIdx = 6, newStartIdx = 1, newEndIdx = 7。dom = [A, B, C, D, E, F, G]

    • 头头比较，B 和 D 不同，进入下一步骤。
    • 尾尾比较，G 和 G 相同，执行 patchVnode 进行差异更新。然后两个尾索引都前移。oldEndIdx = 5, newEndIdx = 6

  3. 重新进入 while 循环: oldStartIdx = 1, oldEndIdx = 5, newStartIdx = 1, newEndIdx = 6。dom = [A, B, C, D, E, F, G]

    • 头头比较，B 和 D 不同，进入下一步骤。
    • 尾尾比较，F 和 B 不同，进入下一步骤。
    • 头尾比较，B 和 B 相同，执行 patchVnode 进行差异更新，同时移动 B 到 newEndIdx = 6 的前面。dom 层更新为 [A, C, D, E, F, B, G]，并更新索引 oldStartIdx = 2, newEndIdx = 5。

  4. 重新进入 while 循环: oldStartIdx = 2, oldEndIdx = 5, newStartIdx = 1, newEndIdx = 5。dom = [A, C, D, E, F, B, G]

    • 头头比较，C 和 D 不同，进入下一步骤。
    • 尾尾比较，F 和 H 不同，进入下一步骤。
    • 头尾比较，C 和 H 不同，进入下一步骤。
    • 尾头比较，F 和 D 不同，进入下一步骤。
    • 步骤五：
      1. 创建节点索引映射，得到 oldKeyToIdx = { C:2, D:3, E:4, F:5 }
      2. 找 newStartVnode 在旧节点的位置。newStartIdx = 1，所以 newStartVnode = D, 对应索引位置为 idxInOld = 3。
      3. idxInOld 存在并且是同一节点，将 oldCh[3] 置空，然后将移动 D 到 newStartIdx = 1，即 C 的前面。此时 dom 层更新为 [A, D, C, E, F, B, G]。oldCh = [A, B, C, undefined, E, F, G]
      4. 更新 newStartIdx = 2

  5. 重新进入 while 循环: oldStartIdx = 2, oldEndIdx = 5, newStartIdx = 2, newEndIdx = 5。dom = [A, D, C, E, F, B, G],oldCh = [A, B, C, undefined, E, F, G]， newCh = [A, D, E, C, F, H, B, G]。

    • 头头比较，C 和 E 不同，进入下一步骤。
    • 尾尾比较，F 和 H 不同，进入下一步骤。
    • 头尾比较，C 和 H 不同，进入下一步骤。
    • 尾头比较，F 和 E 不同，进入下一步骤。
    • 步骤五：
      1. 复用节点索引映射，得到 oldKeyToIdx = { C:2, D:3, E:4, F:5 }
      2. 找 newStartVnode 在旧节点的位置。newStartIdx = 2，所以 newStartVnode = E, 对应索引位置为 idxInOld = 4。
      3. idxInOld 存在并且是同一节点，将 oldCh[4] 置空, 然后移动 E 到 newStartIdx = 2，即 C 的前面。此时 dom 层更新为 [A, D, E, C, F, B, G]。oldCh = [A, B, C, undefined, undefined, F, G]
      4. 更新 newStartIdx = 3

  6. 重新进入 while 循环: oldStartIdx = 2, oldEndIdx = 5, newStartIdx = 3, newEndIdx = 5。dom = [A, D, E, C, F, B, G],oldCh = [A, B, C, undefined, undefined, F, G]

    • 头头比较，C 和 C 相同，执行 patchVnode 进行差异更新。然后两个头索引都后移。oldStartIdx = 3, newStartIdx = 4。

  7. 重新进入 while 循环: oldStartIdx = 3, oldEndIdx = 5, newStartIdx = 4, newEndIdx = 5。dom = [A, D, E, C, F, B, G],oldCh = [A, B, C, undefined, undefined, F, G]

    • 特别判断：oldCh[oldStartIdx] = undefined, 更新 oldStartIdx = 4

  8. 重新进入 while 循环: oldStartIdx = 4, oldEndIdx = 5, newStartIdx = 4, newEndIdx = 5。dom = [A, D, E, C, F, B, G],oldCh = [A, B, C, undefined, undefined, F, G]

    • 特别判断：oldCh[oldStartIdx] = undefined, 更新 oldStartIdx = 5

  9. 重新进入 while 循环: oldStartIdx = 5, oldEndIdx = 5, newStartIdx = 4, newEndIdx = 5。dom = [A, D, E, C, F, B, G],oldCh = [A, B, C, undefined, undefined, F, G]， newCh = [A, D, E, C, F, H, B, G]。

    • 头头比较，F 和 F 相同，进入下一步骤。执行 patchVnode 进行差异更新。然后两个头索引都后移。oldStartIdx = 6, newStartIdx = 5。

  10. oldStartIdx = 6, oldEndIdx = 5, newStartIdx = 5, newEndIdx = 5。因为此时不满足 oldStartIdx <= oldEndIdx 的条件，跳出 while 循环。执行addVnodes, 主要是对旧节点执行新增逻辑。

    if (oldStartIdx > oldEndIdx) {
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
}

function addVnodes(parentElm, refElm, vnodes, startIdx, endIdx, insertedVnodeQueue) {
  for (; startIdx <= endIdx; ++startIdx) {
    createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx);
  }
}
    • 计算插入点：先计算 newEndIdx 是不是末尾，不是的话取 newEndIdx + 1 对应的节点，作为插入点（因为插入的话主要是在其前面），如果是末尾的话，null。此时 newEndIdx + 1 对应的节点为 B。
    • 从 newStartIdx <= newEndIdx 开始创建元素。此时 newStartIdx = 5, newEndIdx = 5。创建 H 节点，插入到 B 节点前面。此时 dom = [A, D, E, C, F, H, B, G]。和 newCh 完全一致。至此整个 diff 流程结束。

# 总结

# patch 总结

  1. 新节点不存在，则直接删除旧节点
  2. 旧节点不存在，创建新节点
  3. 新旧节点一致，进行差异更新
    • sameVnode原理：
      1. 基础标识匹配。
        1. key 相同
        2. 异步工厂函数（asyncFactory）相同
      2. 节点类型匹配 ：满足以下任一条件即可判定匹配。
        1. 常规节点匹配
          1. tag 相同
          2. 是否都是注释节点
          3. 是否都有data属性
          4. 输入框类型相同
        2. 异步组件匹配
          1. 旧节点是否为异步占位符
          2. 新节点无错误
    • 差异更新原理：
      1. 判断 vnode 和 oldVnode 是否指向同一个对象，一样直接返回
      2. 如果他们都有文本节点并且不想等，则将 el 的文本替换为 vNode 的文本节点
      3. 如果两者都有子节点，则执行 updateChildren 函数比较子节点（diff算法）
      4. 如果 oldVnode 没有子节点而 Vnode 有，则将 Vnode 的子节点真实化后添加到 el
      5. 如果 oldVnode 有子节点而 Vnode 没有，则直接删除 el 的子节点
      6. 如果 oldVnode 有文本内容，则清空该文本
  4. 新旧节点不一致，创建新节点替换旧节点

# diff 算法总结

diff 算法主要是同层节点比较的算法，也是深度优先算法。它是双指针从两边到中间，新旧两个比较对象一共四个指针。

  • 单个匹配环节：
    1. 头头对比，一样则更新，指针后移。否则进行步骤2
    2. 尾尾对比，一样则更新，指针前移。否则进行步骤3
    3. 头尾对比，一样则更新，将旧节点移到后面，更新指针。否则进行步骤4
    4. 尾头对比，一样则更新，将旧节点移到前面，更新指针。否则进行步骤5
    5. 如果以上都没有命中，则遍历旧节点，根据 key 或者 sameVnode 进行对比。找到对应的节点，则将该节点移到对应位置。
  • 批量处理环节： 通过指针位置判断新节点遍历完成还是旧节点遍历完成。
    1. 新节点先遍历完成，说明旧节点有多余节点，需要删除。
    2. 旧节点先遍历完成，说明新节点有多余节点，需要新增。

←