本文最后更新于：2022年5月31日上午

概念

diff算法，包含渲染器如何对各种类型的vNode的属性，text，fragment进行patch更新，以及判断是patch vNode，还是新增还是删除
采用同级比较

基础的diff

新节点没有子节点->删除全部旧的子节点
新节点只有一个子节点->删除旧的并添加新的

核心diff

新旧节点都有多个子节点时，新旧子节点间的diff
```
oldChildrenNode :[a,x,c,f]

newChildrenNode :[a,c,f,r]
```
key的作用
vNode中的唯一标识符
用于保存新旧vNode的映射关系
找到可复用的vNode
用移动节点达到更新目的⭐️

Vue2的双端比较

借鉴snabbdom.js


(oStart)               [oEnd]
 oldA   oldB   oldC    oldD

 newB   newC   newD    newA
(nStart)               [nEnd]

// oStart与nEnd匹配上了key，将oldA的DOM移动到新dom最后
      (oStart)        [oEnd]
 oldA   oldB   oldC    oldD
 ｜
  ---------------------->
                        ｜
 newB   newC   newD    newA
(nStart)      [nEnd]

vue同时从新旧children的两端开始比较
四个指针，分别查找是否key相同
匹配到了相同的key，则将真实dom移动,同时四个指针对撞移动
如果第一轮四次匹配不上，则遍历旧node寻找nStart
if 找到将其真实DOM移动到oStart之前，并在原vnode位置置空undefined，后序比较会跳过他
else 找不到则添加新增新元素nStart到oStart之前
匹配结束后oEnd<oStart,新增nStart到nEnd新元素到oStart之前

匹配结束后nStart>nEnd,删除oStart到oEnd之间元素

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

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


  function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    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, idxInOld, vnodeToMove, refElm

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) {
        oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
      } else if (isUndef(oldEndVnode)) {
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
      // 说明oldStartVnode节点更新后要移动去末尾位置
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
      // 说明oldEndVnode节点更新后要移动到最前方
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        // oldKeyToIndex是旧节点的key2index映射map
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
          // 去旧节点中寻找newStartVnode
        if (isUndef(idxInOld)) { // 找不到则新增newStartVnode元素到oldStart之前
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } 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)
            // 匹配到的节点移动到oldStart之前
          } else {
            // key相同但不是同一种元素
            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(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
  }

React的最大递增索引值

由于react使用链表存储oldFiber节点，故新旧节点比较时不能使用双指针
需要两次遍历
1. 第一次遍历更新的节点
2. 第二次处理不属于更新的节点

1. 第一轮

从第一个新节点和链表头开始i = 0;i++，比较DOM是否可以复用

如果 key 不同，会导致DOM不可复用，跳出第一轮遍历
如果 type 不同，会导致DOM不可服用，将oldFiber节点标记为删除
如果遍历完新旧或者任意一个，跳出第一轮遍历 i === newChildren.length - 1）或者oldFiber.sibling === null
2. 第二轮
if newChildren和oldFiber同时遍历完
只需要在为第一遍遍历时标记更新
if oldFiber遍历完了
旧DOM都复用了，新children余下的都是需要新插入的DOM

if newChildren遍历完了

oldFiber余下的节点都需要标记为删除

if 都没遍历完，节点发生了移动

oldFiber    = key1 -> key2 -> key3

newChildren = [key2,key3,key1]

K为在旧 children 中所遇到的最大索引值，后续匹配的索引小于这个值意味着都需要移动

设置oldIndex为当前节点在oldFiber中的位置，K为在diff过程中访问到的最大index。

K = 0
key2在oldFiber中的索引是1,oldIndex>K,不用移动,K=Math.max(oldIndex,K) = 1
key3在oldFiber中的索引是2,oldIndex>K,不用移动,K=Math.max(oldIndex,K) = 2
key1在oldFiber中的索引是0,oldIndex<K,需要移动,K=2
比较完了，将key2,key3移动到key1后(考虑性能，节点后移)
Vue3 借鉴inferno和ivi的算法

排除相同的首位节点

[j]             [preEnd]
 |                  |
 a   e   f  k   b   c
 |                  |
---------------------
 |                  |
 a   f   k  e   b   c
 |                  |   
[j]             [nextEnd]

    [j] [preEnd]
     |      |
 a   e   f  k   b   c
     |      |
---------------------
     |      |
 a   f   k  e   b   c
     |      |   
    [j] [nextEnd]

分别从新旧节点的头和尾出发
依次遍历到key值不一样时停止
这样匹配成功后剩下的部分就是需要新增/删除的vNode们

使用剩余新children的长度建立source索引数组

  oldChildren = [e,f,k]
  newChildren = [f,k,e]
  source = [-1,-1,-1]
- 为新vnode建立key，index索引表
  ```javascript
  keyIndex = {f:0,k:1,e:2}

遍历旧children中key去keyIndex中查找k = keyIndex[oldChildren[i]]，有这个k则把source数组该位置的-1改为旧vNode的索引，并且patch该节点 ;k=undefined则说明该节点已经被删除，而source中依旧为-1的节点为新增节点
```
source = [2,0,1]
```

判断是否需要移动

source = [2,0,1]
//source中，最大索引为2，2之后有小于2的索引，说明需要移动
//根据source数组求出最长递增子序列
LIS = [1，2]
// LIS中存储的是source索引
// 表示新旧children中这几个节点位置保持递增关系

根据LIS得出不进行移动的节点
```
newChildren[LIS] = [f,k]
```
从LIS和新children尾处建立两个指针处理余下节点
比较指针的索引是是否相同，不同则移动DOM位置到上个指针的真实DOM之前

oldVnode.el = 真实DOM，同时source.key = -1的节点直接创建了新的真实DOM

最长递增子序列

子序列：不要求连续
字串：要求连续

// 动态规划
const longestChildSequence = arr => {
  let len = arr.length
  if(len < 1) return
  const dp = Array(len).fill(1)
  // dp[i]代表原始数组该位置的最长子序列长度
  for(let i = 1 ; i < len ; i++){
    for(let j = 0 ; j < i ; j++){
      // j遍历之前遍历过的所有元素
      // 可能存在大小不一的递增序列，使用max取得最大值
      if(arr[i] > arr [j]){
        dp[i] = Math.max(dp[i],dp[j]+1)
        // [1,2,3,4,1,2,5]
        // 如果只使用dp[j]+1 ，dp[6]会在[1,2,5]中得出结果3
        // 使用max比较之前更长的序列[1，2，3，4，5]得到5

      }
    }
  }
  return Math.max(...dp)
}

// 贪心+二分
const longestChildSequence = arr => {
  let len = arr.length
  if(len < 1) return
  const res = [arr[0]]
  //将arr中后续元素arr[i]与res末尾元素比较
  //大于则push进res
  //小于则查找res中第一个比arr[i]大的元素并替换
  //由于存在替换，子序列值不一定正确，但长度是正确的
  for(let i = 0 ; i< len ;i++){
    if(arr[i]>res[res.length-1]){
      res.push(arr[i])
    }else{
      // res中左右指针的index
      // 二分查找
      let left = 0
      let right = res.length - 1
      while(left<right){
        // let mid = Math.floor((left+right)/2)
        let mid = (left+right) >> 1
        // let mid = ((left+right)/2) | 0
        // 浮点小数向下求整
        if(arr[i]>res[mid]){
          left = mid + 1
        }else{
          right = mid
        }
      }
      res[left] = arr[i]
    }
  }
  return res.length 
}

#javascript #vue #算法

diff算法

http://yoursite.com/2022/02/24/diff算法/

作者

tatekii

发布于

2022年2月24日

许可协议

axios和fetch 上一篇

实现自适应div高度为宽度一半下一篇

diff算法

概念

基础的diff

核心diff

key的作用

Vue2的双端比较

React的最大递增索引值

1. 第一轮

2. 第二轮

if newChildren和oldFiber同时遍历完

if oldFiber遍历完了

if newChildren遍历完了

if 都没遍历完，节点发生了移动

Vue3 借鉴inferno和ivi的算法

最长递增子序列

Vue3 借鉴`inferno`和`ivi`的算法