Vue Diff

问题：手动操作 DOM = 命令式 + 频繁重排

开发者需要：
  1. 找到 DOM 节点
  2. 判断哪些数据变了
  3. 手动计算最小 DOM 操作
  4. 逐个执行 DOM 操作
  → 代码难写、难维护、性能难保证

解决：虚拟 DOM + Diff

开发者只需：
  声明数据状态（模板/JSX）
  → 框架自动生成虚拟 DOM
  → Diff 算法比较新旧差异
  → 最小批量更新真实 DOM

Vue 2 双端比较：
┌───────────────────────────────────────┐
│  旧: A  B  C  D  E                   │  ← 4 个指针：旧头、旧尾、新头、新尾
│  新: A  D  B  E  C                   │
│                                       │
│  1. 旧头A == 新头A ✓ 双指针右移      │
│  2. 旧尾E != 新尾C ✗                  │
│  3. 旧头B != 新尾C ✗                  │
│  4. 旧尾E != 新头D ✗                  │
│  5. 用 key 在旧列表查找 D → 移动      │
│  6. 用 key 在旧列表查找 C → 移动      │
└───────────────────────────────────────┘

Vue 3 LIS 优化：
┌───────────────────────────────────────┐
│  旧: A  B  C  D  E     索引: 0,1,2,3,4│
│  新: A  D  B  E  C                    │
│                                       │
│  1. 左→右逐一比较：A==A ✓, B!=D ✗ 跳出│
│  2. 右→左逐一比较：E!=C ✗ 跳出         │
│  3. 中间乱序部分：                      │
│  建 keyToNewIndexMap: D→1,B→2,E→3,C→4 │
│  按新索引填 newIndexToOldIndexMap:     │
│     [3, 1, 4, 2]                      │
│     最长递增子序列: [1, 4] (B和E不动)  │
│     只移动 D 和 C                      │
└───────────────────────────────────────┘

Vue 3 diff 算法的三步走图解：

  旧列表: [A] [B] [C] [D] [E] [F] [G]
  新列表: [A] [B] [D] [F] [C] [E] [G]
            ↑                        ↑
          i=0                      e1/e2

  第一步：从左到右，处理头部相同部分（O(1) 每次比较）
  ┌───┬───┬───┬───┬───┬───┬───┐
  │ A │ B │ C │ D │ E │ F │ G │  旧
  ├───┼───┼───┼───┼───┼───┼───┤
  │ A │ B │ D │ F │ C │ E │ G │  新
  └───┴───┴───┴───┴───┴───┴───┘
  ✓   ✓   ✗
  A==A  B==B  C!=D → 跳出，i=2

  第二步：从右到左，处理尾部相同部分
  ┌───┬───┬───┬───┬───┬───┬───┐
  │ A │ B │ C │ D │ E │ F │ G │  旧
  ├───┼───┼───┼───┼───┼───┼───┤
  │ A │ B │ D │ F │ C │ E │ G │  新
  └───┴───┴───┴───┴───┴───┴───┘
                  ✗       ✓   ✓
              E!=C  F==F  G==G → e1=4, e2=4

  第三步：中间乱序部分 [C,D,E] vs [D,F,C,E]
  ┌─────────────────────────────────────────────┐
  │ 1. 建立 key→新索引 的 Map: D→2, F→3, C→4, E→5│
  │ 2. 遍历旧节点，查找可复用:                     │
  │    C → newIndex=4, 记录 [4]                   │
  │    D → newIndex=2, 记录 [4,2]                 │
  │    E → newIndex=5, 记录 [4,2,5]               │
  │ 3. 最长递增子序列(LIS): [4,5] → C和E不动      │
  │ 4. 只移动 D 和 F                              │
  └─────────────────────────────────────────────┘

// Vue 3 的 diff 核心逻辑（伪代码，每行注释）
function patchKeyedChildren(c1, c2, container) {
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;

  // ===== 第一步：从左到右，处理头部相同的部分 =====
  // 用 i 指针从头部开始，逐一比较新旧节点的 key 和 type
  while (i <= e1 && i <= e2) {
    if (isSameVNode(c1[i], c2[i])) {
      patch(c1[i], c2[i]); // 相同则 patch 更新
      i++;
    } else break; // 不同则跳出，进入下一步
  }

  // ===== 第二步：从右到左，处理尾部相同的部分 =====
  // 用 e1（旧尾）和 e2（新尾）从尾部开始，逐一比较
  while (i <= e1 && i <= e2) {
    if (isSameVNode(c1[e1], c2[e2])) {
      patch(c1[e1], c2[e2]);
      e1--;
      e2--;
    } else break; // 不同则跳出，进入第三步
  }

  // ===== 第三步：中间乱序部分，用 LIS 优化 =====
  const s1 = i; // 旧列表中间段的起点
  const s2 = i; // 新列表中间段的起点

  // 建立 key → 新索引 的 Map，O(1) 查找
  const keyToNewIndexMap = new Map();
  for (let j = s2; j <= e2; j++) {
    keyToNewIndexMap.set(c2[j].key, j);
  }

  // 创建映射数组：newIndexToOldIndexMap[新索引 - s2] = 旧索引 + 1（0 表示新增）
  const toBePatched = e2 - s2 + 1;
  const newIndexToOldIndexMap = new Array(toBePatched).fill(0);

  // 遍历旧节点，在 Map 中查找可复用的节点
  for (let j = s1; j <= e1; j++) {
    const newIndex = keyToNewIndexMap.get(c1[j].key); // O(1) 查找
    if (newIndex !== undefined) {
      newIndexToOldIndexMap[newIndex - s2] = j + 1; // 记录旧索引（+1 避免 0）
    } else {
      unmount(c1[j]); // 旧节点在新列表中不存在，删除
    }
  }

  // 计算最长递增子序列（LIS）—— 这些节点的相对位置没变，不需要移动
  const increasingNewIndexSequence = getSequence(newIndexToOldIndexMap);

  // 从后往前遍历新列表，只移动不在 LIS 中的节点
  let seqIndex = increasingNewIndexSequence.length - 1;
  for (let j = toBePatched - 1; j >= 0; j--) {
    const newIndex = s2 + j;
    if (newIndexToOldIndexMap[j] === 0) {
      patch(null, c2[newIndex]); // 新节点，挂载
    } else if (seqIndex < 0 || j !== increasingNewIndexSequence[seqIndex]) {
      move(c2[newIndex], container); // 不在 LIS 中，移动 DOM
    } else {
      seqIndex--; // 在 LIS 中，保持原位
    }
  }
}

// 初始列表：[{name: '张三'}, {name: '李四'}, {name: '王五'}]

// 用 index 做 key：
// key: [0, 1, 2] → 对应 张三, 李四, 王五
// 删除"张三"后：[{name: '李四'}, {name: '王五'}]
// key: [0, 1]    → 对应 李四, 王五

// Vue 认为：key=0 的节点还在，只是 props 从"张三"变成了"李四"
// 结果：强制更新 key=0 和 key=1 的 props，而不是复用节点
// 如果节点内有输入框，用户输入的内容会错乱！

// 删除"张三"后：key=[2, 3] 对应 李四, 王五
// Vue 认为：key=1（张三）被删除了，key=2（李四）和 key=3（王五）保留
// 结果：只删除一个 DOM 节点，李四和王五被完美复用，内部状态不变

// packages/runtime-core/src/renderer.ts（极度简化）
const patchKeyedChildren = (
  c1: VNode[], // 旧子节点
  c2: VNode[], // 新子节点
  container: RendererElement,
) => {
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;

  // 1. 从左到右：处理头部相同的部分
  while (i <= e1 && i <= e2 && isSameVNode(c1[i], c2[i])) {
    patch(c1[i], c2[i], container);
    i++;
  }
  // 2. 从右到左：处理尾部相同的部分
  while (i <= e1 && i <= e2 && isSameVNode(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container);
    e1--;
    e2--;
  }
  // 3. 中间乱序部分：建立映射 + LIS 优化
  // ...（详见源码）
};

// packages/runtime-core/src/renderer.ts 底部的 getSequence
// 最长递增子序列：动态规划 + 贪心 + 二分查找
// 时间复杂度：O(n log n)
// 返回值：LIS 的索引数组（不是值数组）

// 例：输入 [3, 1, 4, 2]
// 返回 [1, 3]（索引 1 和 3 对应的值 1 和 2 是递增的）

性能对比（从快到慢）：

1. 手写最优 DOM 操作（直接操作，无中间层）
2. 虚拟 DOM + diff（多了 JS 对象创建和比较）
3. 手写低效 DOM 操作（频繁重排、无批量更新）

// 手写最优 DOM 操作（性能最好，但开发体验极差）
const list = document.getElementById('list')
// 你需要手动计算哪些 DOM 节点需要更新
// 手动判断是插入、删除还是移动
// 手动处理属性变化
// 手动处理事件绑定
// 代码量巨大，极易出错

// 虚拟 DOM（性能足够好，开发体验极佳）
// 你只需要声明数据状态
<ul>
  <li v-for="item in list" :key="item.id">{{ item.name }}</li>
</ul>
// 框架自动帮你计算最小 DOM 操作

// 手写 DOM：每次修改都触发重排
element.style.width = "100px"; // 重排
element.style.height = "100px"; // 重排
element.style.margin = "10px"; // 重排
// 3 次重排

// 虚拟 DOM：先在内存中计算，最后一次性更新
// diff 算法把 3 次修改合并为 1 次 DOM 操作

// 手写 DOM（低效）：全量替换
function updateList(newList) {
  container.innerHTML = "";
  newList.forEach((item) => {
    const li = document.createElement("li");
    li.textContent = item.name;
    container.appendChild(li);
  });
  // 销毁所有旧节点，创建所有新节点
}

// 虚拟 DOM：diff 计算最小变更
// 只更新变化的节点，复用不变的节点

虚拟 DOM 是 JS 对象，不依赖浏览器 API
→ 可以渲染到 Web、Native、Canvas、SSR
→ 一次编写，多端运行

// 虚拟 DOM 需要创建 VNode 对象
const vnode = {
  type: "div",
  props: { class: "container" },
  children: [
    { type: "h1", props: null, children: "Hello" },
    { type: "p", props: null, children: "World" },
  ],
};
// 每次渲染都要创建这些对象（虽然有静态提升优化）

// diff 需要遍历新旧两棵 VNode 树
// 时间复杂度 O(n)，n 是节点数量
// 对于 1000 个节点的列表，需要比较 1000 次

// 虚拟 DOM 需要在内存中维护两棵树（新树和旧树）
// 对于大型应用，内存占用不可忽视

// 命令式（无虚拟 DOM）：告诉框架"怎么做"
const element = document.createElement('div')
element.textContent = message
element.addEventListener('click', handler)
container.appendChild(element)

// 声明式（有虚拟 DOM）：告诉框架"要什么"
<div @click="handler">{{ message }}</div>

// 虚拟 DOM 让组件可以返回描述，而不是直接操作 DOM
function MyComponent(props) {
  return h("div", [h("h1", props.title), h("p", props.content)]);
}
// 组件只需要描述"要什么"，框架负责"怎么做"

虚拟 DOM 是平台无关的 JS 对象
→ Web 渲染器：VNode → DOM
→ Native 渲染器：VNode → 原生组件
→ SSR 渲染器：VNode → HTML 字符串
→ Canvas 渲染器：VNode → Canvas 绘制指令

// Svelte 的组件
<script>
  let count = 0;
  function increment() { count += 1; }
</script>

<button on:click={increment}>
  Count: {count}
</button>

// 编译后（简化）
function create_fragment(ctx) {
  let button;
  return {
    create() {
      button = element("button");
      button.textContent = `Count: ${ctx.count}`;
    },
    update(ctx, [dirty]) {
      if (dirty & 1) {
        set_data(button, `Count: ${ctx.count}`);
      }
    },
    // ...
  }
}

Vue 3 的三层优化：
1. PatchFlag：只比较有标记的动态属性
2. Block Tree：跳过整棵静态子树
3. 静态提升：静态 VNode 只创建一次

效果：Vue 3 的虚拟 DOM 在大多数场景下接近甚至超过手写 DOM 操作

虚拟 DOM 不会被干掉，因为：
1. 声明式编程需要它（开发者不想手写 DOM 操作）
2. 组件化架构需要它（组件需要返回描述而不是直接操作 DOM）
3. 跨平台渲染需要它（平台无关的中间表示）
4. 编译时优化让它足够快（PatchFlag + Block Tree + 静态提升）

但虚拟 DOM 也在进化：
- Vue 3：编译时优化减少运行时开销
- Svelte：完全去掉虚拟 DOM，编译时生成 DOM 操作代码
- Solid.js：细粒度响应式 + 无虚拟 DOM