1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

// Vue 3的Diff算法（简化）
// 1. 预处理相同前置/后置节点
// 2. 处理新增/删除节点
// 3. 使用LIS算法计算最小移动次数
function patchKeyedChildren(c1, c2, container, parentAnchor) {
  let i = 0;
  const l1 = c1.length;
  const l2 = c2.length;
  let e1 = l1 - 1; // 旧节点的结束索引
  let e2 = l2 - 1; // 新节点的结束索引

  // 1. 预处理相同前置节点
  // (a b) c
  // (a b) d e
  while (i <= e1 && i <= e2) {
    const n1 = c1[i];
    const n2 = c2[i];
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container);
    } else {
      break;
    }
    i++;
  }

  // 2. 预处理相同后置节点
  // a (b c)
  // d e (b c)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1];
    const n2 = c2[e2];
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container);
    } else {
      break;
    }
    e1--;
    e2--;
  }

  // 3. 处理新增节点（旧节点已遍历完，新节点有剩余）
  // (a b)
  // (a b) c d
  // i = 2, e1 = 1, e2 = 3
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1;
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
      while (i <= e2) {
        patch(null, c2[i], container, anchor);
        i++;
      }
    }
  }

  // 4. 处理删除节点（新节点已遍历完，旧节点有剩余）
  // (a b) c d
  // (a b)
  // i = 2, e1 = 3, e2 = 1
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i]);
      i++;
    }
  }

  // 5. 处理乱序节点（核心Diff）
  // a b [c d e] f g
  // a b [e d c h] f g
  else {
    const s1 = i; // 旧节点的开始索引
    const s2 = i; // 新节点的开始索引

    // 5.1 建立新节点的key到index的映射
    const keyToNewIndexMap = new Map();
    for (i = s2; i <= e2; i++) {
      const nextChild = c2[i];
      if (nextChild.key !== null) {
        keyToNewIndexMap.set(nextChild.key, i);
      }
    }

    // 5.2 遍历旧节点，寻找匹配的新节点
    let j;
    let patched = 0;
    const toBePatched = e2 - s2 + 1;
    let moved = false;
    let maxNewIndexSoFar = 0;
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0);

    for (i = s1; i <= e1; i++) {
      const prevChild = c1[i];
      if (patched >= toBePatched) {
        // 所有新节点都已处理，剩余旧节点全部删除
        unmount(prevChild);
        continue;
      }

      let newIndex;
      if (prevChild.key !== null) {
        // 通过key查找新节点位置
        newIndex = keyToNewIndexMap.get(prevChild.key);
      } else {
        // 没有key，遍历查找
        for (j = s2; j <= e2; j++) {
          if (
            newIndexToOldIndexMap[j - s2] === 0 &&
            isSameVNodeType(prevChild, c2[j])
          ) {
            newIndex = j;
            break;
          }
        }
      }

      if (newIndex === undefined) {
        // 没有找到匹配的新节点，删除当前旧节点
        unmount(prevChild);
      } else {
        // 保存旧节点索引（+1 是为了避免与默认值0冲突）
        newIndexToOldIndexMap[newIndex - s2] = i + 1;
        
        // 判断节点是否需要移动
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          moved = true;
        }
        
        // 复用旧节点，更新内容
        patch(prevChild, c2[newIndex], container);
        patched++;
      }
    }

    // 5.3 使用LIS算法计算最小移动次数
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap)
      : [];
    j = increasingNewIndexSequence.length - 1;

    // 5.4 移动和插入节点
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i;
      const nextChild = c2[nextIndex];
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;

      if (newIndexToOldIndexMap[i] === 0) {
        // 新节点，需要插入
        patch(null, nextChild, container, anchor);
      } else if (moved) {
        // 需要移动节点
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor);
        } else {
          j--;
        }
      }
    }
  }
}

// 判断两个VNode是否可以复用（key和type都相同）
function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key;
}

// 最长递增子序列算法（Vue 3源码实现）
function getSequence(arr) {
  const p = arr.slice();
  const result = [0];
  let i, j, u, v, c;
  const len = arr.length;
  for (i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      j = result[result.length - 1];
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      u = 0;
      v = result.length - 1;
      while (u < v) {
        c = (u + v) >> 1;
        if (arr[result[c]] < arrI) {
          u = c + 1;
        } else {
          v = c;
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1];
        }
        result[u] = i;
      }
    }
  }
  u = result.length;
  v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  return result;
}