vue3核心组件更新diff算法(简易)

前言

数据发生变化时组件更新
新老虚拟节点进行比对
最长递增子序列
主要通过patch(老虚拟节点, 新虚拟节点, 父元素, 参照物)方法比对
有以下几种情况
1. 类型不同直接替换
2. 比对属性
3. 老的是数组新的是文本(孩子)
4. 都是文本
5. null 特殊情况删除掉老的
6. 老的是文本现在是数组(孩子)
7. 新的是数组老的也是数组(孩子重点讲diff算法)
新的是数组老的也是数组有以下几种情况
1. diff children 1 从头开始比不同的就停止
2. diff children 2 从尾开始比不同的就停止
3. diff children 3 老的少新的多(有一方比对完成)
4. diff children 4 老的多新的少(有一方比对完成)
5. diff children 5 乱序比较

示例

<script src="../node_modules/@vue/runtime-dom/dist/runtime-dom.global.js"></script>
<div id="app"></div>
<script>
const { createApp, h, reactive, ref } = VueRuntimeDOM

let App = {
  setup(props, context) {
    let flag = ref(true)
    setTimeout(() => { flag.value = false }, 2000)

    return () => {
      // 1.type 不同直接替换
      // return flag.value ?
      //   h('div', { style: { color: '#000' } }, 'Bob') :
      //   h('p', { style: { color: 'blue' } }, 'Tom')

      // 2.比对属性
      // return flag.value ?
      //   h('div', { style: { color: '#000' } }, 'Bob') :
      //   h('div', { style: { color: 'blue' } }, 'Tom')
      
      // 3.老的是数组 新的是文本
      // 4.都是文本
      // 5.null 特殊情况 删除掉老的
      // 6.老的是文本 现在是数组
      // return flag.value ? h('div', null, [h('span', null, 'Bob')]) : h('div', null, 'Tom')
      // return flag.value ? h('div', null, 'Bob') : h('div', null, 'Tom')
      // return flag.value ? h('div', null, [h('span', null, 'Bob')]) : h('div', null)
      // return flag.value ? h('div', null, 'Bob') : h('div', null)


      // diff children 1 从头开始比 不同的就停止
      // diff children 2 从尾开始比 不同的就停止
      // diff children 3 老的少 新的多(有一方比对完成)
      // diff children 4 老的多 新的少(有一方比对完成)
      // diff children 5 乱序比较
      return flag.value ?
        h('div', { style: { color: '#000' } }, [
            h('li', { key: 'a' }, 'a'),
            h('li', { key: 'b' }, 'b'),
            h('li', { key: 'c' }, 'c'),
            h('li', { key: 'd', style: {color: 'green'}}, 'd'),
            h('li', { key: 'e' }, 'e'),
            // h('li', { key: 'q' }, 'q'),
            h('li', { key: 'f' }, 'f'),
            h('li', { key: 'g' }, 'g'),
        ]) :
        h('div', { style: { color: 'blue' } }, [
            h('li', { key: 'a' }, 'a'),
            h('li', { key: 'b' }, 'b'),
            h('li', { key: 'e' }, 'e'),
            h('li', { key: 'c' }, 'c'),
            h('li', { key: 'd', style: {color: 'red'}}, 'd'),
            h('li', { key: 'h' }, 'h'),
            h('li', { key: 'f' }, 'f'),
            h('li', { key: 'g' }, 'g'),
        ])
    }
  },
}

let app = createApp(App, { name: 'zf', age: 12 })
app.mount('#app')
</script>

组件更新

/**
   * @desc 创建组件的effect函数 执行render函数
   */
  const setupRenderEffect = (instance, container) => {
    instance.update = effect(function componentEffect() {
      if (!instance.isMounted) {
        let proxyToUse = instance.proxy
        let subTree = instance.subTree = instance.render.call(proxyToUse, proxyToUse)

        // 用render函数的返回值 继续渲染
        patch(null, subTree, container)
        instance.isMounted = true
      } else {
        // 看这里
        // 获取老组件的subTree(组件render方法返回的vnode) 在调用一次render函数 获取新的subTree
        // 最后patch比对
        const prevTree = instance.subTree
        let proxyToUse = instance.proxy
        const nextTree = instance.render.call(proxyToUse, proxyToUse)

        instance.subTree = nextTree
        patch(prevTree, nextTree, container)
      }
    }, {
      scheduler: queueJob
    })

  }

新老元素不一样

/**
   * @param n1          oldVNode
   * @param n2          newVNode
   * @param container   Dom
   * @param anchor      参照物节点
   */
  /**
   * @desc 比较两个虚拟节点 是否一致
   */
  const isSameVNodeType = (n1, n2) => {
    return n1.type === n2.type && n1.key === n2.key
  }

  /**
   * @desc 销毁元素, 组件
   */
  const unmount = (n1) => {
    // 源码中如果是组件(这里就展示)
    // 调用的组件的生命周期 调用组件的销毁方法等
    hostRemove(n1.el)
  }

  const patch = (n1, n2, container, anchor = null) => {
    const { shapeFlag, type } = n2

    // 看这里
    // 1.不同直接替换 将新的虚拟节点渲染成真实DOM
    if (n1 && !isSameVNodeType(n1, n2)) {
      anchor = hostNextSibling(n1.el)
      // 直接移除老节点
      unmount(n1)
      n1 = null
    }

    switch (type) {
      case Text:
        processText(n1, n2, container)
        break;
    
      default:
        if (shapeFlag & ShapeFlags.ELEMENT) {
          // 渲染成真实DOM 挂载页面
          processElement(n1, n2, container, anchor)
        } else if (shapeFlag & ShapeFlags.STATEFUL_COMPONENT) {
          processComponent(n1, n2, container)
        }

        break;
    }
  }

元素一样

如果前后虚拟节点一样将老的dom元素复用
然后比对属性和孩子(子节点)

/**
 * @desc 比对元素节点
 */
const patchElement = (n1, n2, container) => {
  // 相同节点
  let el = (n2.el = n1.el)

  // 2.比对属性
  const oldProps = n1.props || {}
  const newProps = n2.props || {}
  patchProps(oldProps, newProps, el)

  // 比对孩子
  patchChildren(n1, n2, el)
}

比对属性

/**
 * @desc 比对属性
 */
const patchProps = (oldProps, newProps, el) => {
  if (oldProps !== newProps) {
    for (let key in newProps) {
      const prev = oldProps[key]
      const next = newProps[key]
      if (prev !== next) {
        hostPatchProp(el, key, prev, next)
      }
    }
    for (const key in oldProps) {
      if (!(key in newProps)) {
        hostPatchProp(el, key, oldProps[key], null)
      }
    }
  }
}

比对孩子(子节点)

/**
   * @desc 比对孩子
   */
  const patchChildren = (n1, n2, el) => {
    const c1 = n1.children
    const c2 = n2.children

    const prevShapeFlag = n1.shapeFlag
    const shapeFlag = n2.shapeFlag

    // c2如果是文本
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
      // 3.老的是数组 新的是文本 销毁老的
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        unmountChildren(c1)
      }

      // 4.都是文本
      if (c1 !== c2) {
        hostSetElementText(el, c2)
      }

    } else {
      // c2否则是null 或者 数组
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          // 都是数组
          // 核心diff
          patchKeyedChildren(c1, c2, el)
        } else {
          // 5.null 特殊情况 删除掉老的
          unmountChildren(c1)
        }

      } else {
        // 6.老的是文本 现在是数组
        if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
          hostSetElementText(el, '');
        }

        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          mountChildren(c2, el);
        }

      }

    }

    
  }

比对孩子(子节点) 核心diff算法

孩子都是数组进行比对
vue3采用从头开始比较,两个尾指针
vue2采用的是双指针算法

从头开始(sync form start)

/**
 * @desc 核心diff 比对孩子
 * @param c1 老的孩子
 * @param c2 新的孩子
 * @param el 父元素
 */
const patchKeyedChildren = (c1, c2, el) => {
  // Vue3都是默认从头开始比对
  let i = 0
  let e1 = c1.length - 1
  let e2 = c2.length - 1

  // diff children 1 从头开始比 不同的就停止
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, el)
    } else {
      break;
    }

    i++;
  }

  // ...
}

从尾开始(sync from end)

const patchKeyedChildren = (c1, c2, el) => {
  // ...

  // diff children 2 从尾开始比 不同的就停止
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, el)
    } else {
        break;
    }
    e1--;
    e2--;
  }

  // ...

}

老的少新的多(common sequence + mount)

前提是有一方已经结束
可能是在后面添加也可能是在前面添加
判断有没有下一个节点加在下一个节点前面
没有就是appendchild往后添加

const patchKeyedChildren = (c1, c2, el) => {
  // ...
  
  if (i > e1) {
    // diff children 3 老的少 新的多(有一方比对完成)
    // 两种情况从前往后比时 和 从后往前比时(同一个逻辑)
    if (i <= e2) {
      // 想知道是向前插入 还是向后插入
      const nextPos = e2 + 1
      const anchor = nextPos < c2.length ? c2[nextPos].el : null
      while (i <= e2) {
        patch(null, c2[i], el, anchor)
        i++;
      }
    }
  }

  // ...
}

老的多新的少(common sequence + unmount)

前提是有一方已经结束
直接删除老的节点

const patchKeyedChildren = (c1, c2, el) => {
  // ...

  if (i > e1) {
  } else if (i > e2) {

   // diff children 4 老的多 新的少(有一方比对完成)
    while (i <= e1) {
      unmount(c1[i])
      i++;
    }

  } else {}

  // ...
}

乱序比较(unknown sequence)

步骤一

创建新的虚拟dom{key => index} 映射表
在新的里面去寻找老的key
没有直接删除
如果在新的里面找到进行比对
问题:
位置没有移动, 只是把当前已有的进行了比对

const patchKeyedChildren = (c1, c2, el) => {
  // ...

  if (i > e1) {
  } else if (i > e2) {
  } else {
    // diff children 5 乱序比较
    // 用新的元素做成一个映射表去老的里找
    // 一样的就复用 不一样的要不插入 要不删除
    let s1 = i
    let s2 = i

    // 用的是新的做的映射表
    const keyToNewIndexMap = new Map()

    // 结果如: { e=>2, c=>3, d=>4, h=>5 }
    for (let i = s2; i <= e2; i++) {
      const childVNode = c2[i]
      keyToNewIndexMap.set(childVNode.key, i)
    }

    for (let i = s1; i<=e1 ; i++) {
      const oldVnode = c1[i]
      let newIndex = keyToNewIndexMap.get(oldVnode.key)
      if(newIndex === undefined) {
        // 新的没有 删除老的
        unmount(oldVnode)
      } else {
        // 在老的中找到 做了新老虚拟比较 但是位置没有移动
        patch(oldVnode, c2[newIndex], el)
      }
    }


  }

  // ...
}

步骤二

插入老的不存在的节点
首先创建一个新的索引对应老的位置的索引数组
从后往前插入方法将节点一一插入
问题:
有些节点的位置是没必要移动的如图 c,d
我们只要移动e就好(最长递增长子序列)

const patchKeyedChildren = (c1, c2, el) => {
  // ...

  if (i > e1) {
  } else if (i > e2) {
  } else {
      let s1 = i
      let s2 = i

      const keyToNewIndexMap = new Map()

      for (let i = s2; i <= e2; i++) {
        const childVNode = c2[i]
        keyToNewIndexMap.set(childVNode.key, i)
      }

      // 看这里
      // 剩下的没做比较有几个
      const toBePatched = e2 - s2 + 1
      // 将剩下的封装成一个数组, 并每个都赋值为0 
      // 以比较就将老的对应的虚拟节点 索引 赋值给当前数组的
      // 没有比较的就是0
      // 以上面的图片为例 最终结果是 [5,3,4,0]
      const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

      for (let i = s1; i<=e1 ; i++) {
        const oldVnode = c1[i]
        let newIndex = keyToNewIndexMap.get(oldVnode.key)
        if(newIndex === undefined) {
          // 新的没有 删除老的
          unmount(oldVnode)
        } else {
          // i+1防止是0 明明比较了 还是0
          newIndexToOldIndexMap[newIndex - s2] = i + 1
          // 在老的中找到 做了新老虚拟比较 但是位置没有移动
          patch(oldVnode, c2[newIndex], el)
        }
      }


      // 处理虚拟节点的位置 从后往前依次插入节点
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 找到当前最后一个 和 当前节点
        let currentIndex = i + s2
        let child = c2[currentIndex]

        // 插入的参照物
        let anchor = currentIndex + 1 < c2.length ? c2[currentIndex+1].el  : null

        // 如果是0 说明没有被patch过 直接生成
        if(newIndexToOldIndexMap[i] == 0) {
          patch(null, child, el, anchor)
        } else {

          hostInsert(child.el, el, anchor)

        }

      }


  }

  // ...
}

步骤三

把没必要移动的节点排除掉
最长递增长子序列

const patchKeyedChildren = (c1, c2, el) => {
  // ...

  if (i > e1) {
  } else if (i > e2) {
  } else {
      let s1 = i
      let s2 = i

      const keyToNewIndexMap = new Map()

      for (let i = s2; i <= e2; i++) {
        const childVNode = c2[i]
        keyToNewIndexMap.set(childVNode.key, i)
      }

      // 看这里
      // 剩下的没做比较有几个
      const toBePatched = e2 - s2 + 1
      // 将剩下的封装成一个数组, 并每个都赋值为0 
      // 以比较就将老的对应的虚拟节点 索引 赋值给当前数组的
      // 没有比较的就是0
      // 以上面的图片为例 最终结果是 [5,3,4,0]
      const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

      for (let i = s1; i<=e1 ; i++) {
        const oldVnode = c1[i]
        let newIndex = keyToNewIndexMap.get(oldVnode.key)
        if(newIndex === undefined) {
          // 新的没有 删除老的
          unmount(oldVnode)
        } else {
          // i+1防止是0 明明比较了 还是0
          newIndexToOldIndexMap[newIndex - s2] = i + 1
          // 在老的中找到 做了新老虚拟比较 但是位置没有移动
          patch(oldVnode, c2[newIndex], el)
        }
      }

      // 最长递增长子序列
      // [1,2]对应[3,4] 就是老节点数组2,3位置的节点, 不需要移动的节点
      // [5,3,4,0] => [1,2]
      let increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
      let j = increasingNewIndexSequence.length - 1

      // 处理虚拟节点的位置 从后往前依次插入节点
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 找到当前最后一个 和 当前节点
        let currentIndex = i + s2
        let child = c2[currentIndex]

        // 插入的参照物
        let anchor = currentIndex + 1 < c2.length ? c2[currentIndex+1].el  : null

        // 如果是0 说明没有被patch过 直接生成
        if(newIndexToOldIndexMap[i] == 0) {
          patch(null, child, el, anchor)
        } else {

          // 从后往前查 没有就插入 
          if(i != increasingNewIndexSequence[j]){
            hostInsert(child.el, el, anchor)
          } else {
            j--;
          }

        }

      }


  }

  // ...
}

/**
   * @desc 最长递增子序列
   */
  function getSequence(arr) {
    const len = arr.length
    const result = [0]
    const p = arr.slice(0)
    let start;
    let end;
    let middle;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            let resultLastIndex = result[result.length - 1]
            // 取到索引对应的值
            if (arr[resultLastIndex] < arrI) {
                p[i] = resultLastIndex
                result.push(i)
                continue
            }
            start = 0;
            end = result.length - 1;
            while (start < end) {
                middle = ((start + end) / 2) | 0
                if (arr[result[middle]] < arrI) {
                    start = middle + 1
                } else {
                    end = middle
                }
            }

            if (arrI < arr[result[start]]) {
                if (start > 0) {
                  p[i] = result[start - 1]
                }
                result[start] = i
            }
        }
    }
    let len1 = result.length
    let last = result[len1 - 1]
    while (len1-- > 0) {
        result[len1] = last
        last = p[last]
    }
    return result
  }

最长递增长子序列

[2, 3, 1, 5, 6, 8, 7, 9, 4] => [0, 1, 3, 4, 6, 7]
vue3源码最长递增长子序列地址

* 贪心 + 二分算法如下
* 2 
* 2 3
* 1 3
* 1 3 5
* 1 3 5 6
* 1 3 5 6 8
* 1 3 5 6 7 
* 1 3 5 6 7 9

* 1 3 4 6 7 9  值
* | | | | | |
* 2 1 8 4 6 7  索引(第一步的result)

* 2 3 1 5 6 8 7 9 4  原数组值
* | | | | | | | | |
* X 0 X 1 3 4 4 6 1  push和二分查找的时候对应的上一个索引(p)

* 2 3 5 6 7 9  希望结果值
* | | | | | |
* 0 1 3 4 6 7  希望结果索引(result最终返回结果)

第一步

// 第一步
// 1 3 4 6 7 9  值
// | | | | | |
// 2 1 8 4 6 7  索引
// 贪心 + 二分算法
function getSequence(arr) {
    const len = arr.length

// 存储索引
  const result = [0]
  let start;
  let end;
  let middle;
  for (let i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
        let resultLastIndex = result[result.length - 1]
        // 比前一个数值大 就将对应的索引push进去
        // 取到索引对应的值
        if (arr[resultLastIndex] < arrI) {
            result.push(i)
            continue
        }

        // 通过二分算法 找到比当前值大的 将当前值替代掉大的值
        start = 0
        end = result.length - 1
        while (start < end) {
            // 取中间的索引 用位运算 取整数 如下
            // (0 + 5) / 2 -> 2.5
            // 2.5 | 0 -> 2
            middle = ((start + end) / 2) | 0
            if (arr[result[middle]] < arrI) {
                start = middle + 1
            } else {
                end = middle
            }
        }
        
        // 最后 start == end 就是要找的对应的索引
        // 并将当前的索引替换掉
        result[start] = i

  }
}

return result
}

第二步

// 第二步

// 通过索引中最后一个索引 倒叙 去记录 每次添加的索引前一个值得缩影
// 如上面的图所示(通过9开始追溯 9对应的索引是7)
// 2   3   1   5   6   8   7   9   4   原先值
//     1   2       4       6   7   8   result上一步结果是[2, 1, 8, 4, 6, 7]
// X  0    X   1   3   4   4   6   1   每个索引 对应的上一个值得索引

// 找个中间的数组 记录每一次循环的替换 push的上一个值得索引
// 求p [2,0,1,1,3,4,4,6,1]

function getSequence(arr) {
    const len = arr.length
    const result = [0]
    // copy一个同长度的数组 值无所谓
    const p = arr.slice(0)
    let start;
    let end;
    let middle;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            let resultLastIndex = result[result.length - 1]
            if (arr[resultLastIndex] < arrI) {
                // 要push值得索引 赋值给对应值得 重新赋值上上一个值的索引
                p[i] = resultLastIndex
                result.push(i)
                continue
            }
            start = 0;
            end = result.length - 1;
            while (start < end) {
                middle = ((start + end) / 2) | 0
                if (arr[result[middle]] < arrI) {
                    start = middle + 1
                } else {
                    end = middle
                }
            }

            // 防止相同 或者大于的值
            if (arrI < arr[result[start]]) {
                // 0的前一个值 没有 所以大于0
                if (start > 0) {
                  p[i] = result[start - 1]
                }
                result[start] = i
            }
        }
    }
    
    // [2,0,1,1,3,4,4,6,1]
    console.log('求p', p)
    return result
  }

第三步

// 第三步
// 2   3   1   5   6   8   7   9   4   原先值
// 2   0   1   1   3   4   4   6   1   每个索引 对应的上一个值得索引
//     1   2       4       6   7   8   result上一步结果是[2, 1, 8, 4, 6, 7]
// 求[0, 1, 3, 4, 6, 7]

function getSequence(arr) {
    const len = arr.length
    const result = [0]
    const p = arr.slice(0)
    let start;
    let end;
    let middle;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            let resultLastIndex = result[result.length - 1]
            // 取到索引对应的值
            if (arr[resultLastIndex] < arrI) {
                p[i] = resultLastIndex
                result.push(i)
                continue
            }
            start = 0;
            end = result.length - 1;
            while (start < end) {
                middle = ((start + end) / 2) | 0
                if (arr[result[middle]] < arrI) {
                    start = middle + 1
                } else {
                    end = middle
                }
            }

            if (arrI < arr[result[start]]) {
                if (start > 0) {
                  p[i] = result[start - 1]
                }
                result[start] = i
            }
        }
    }

    // 通过p找上一值 对应的索引
    // 从末尾数索引7(原数组对应的值是9)开始找
    let len1 = result.length
    let last = result[len1 - 1]
    while (len1-- > 0) {
        result[len1] = last
        last = p[last]
    }
    return result
}

shard runtime-dom runtime-core

组件的渲染流程其他模块请看上一章vue3组件渲染流程(简易)

renderer.ts

import { effect } from "@vue/reactivity/src"
import { ShapeFlags } from "@vue/shared/src"
import { createAppAPI } from "./apiCreateApp"
import { createComponentInstance, setupComponent } from "./component"
import { queueJob } from "./scheduler"
import { normalizeVNode ,Text} from "./vnode"

/**
 * @description 创建一个渲染器
 * @param rendererOptions 针对浏览器的一些元素 文本的增删改查
 */
export function createRenderer(rendererOptions) {
  /**
   * @desc 浏览器的操作方法
   */
  const {
    insert: hostInsert,
    remove: hostRemove,
    patchProp: hostPatchProp,
    createElement: hostCreateElement,
    createText: hostCreateText,
    createComment: hostCreateComment,
    setText: hostSetText,
    setElementText: hostSetElementText,
    nextSibling: hostNextSibling,
  } = rendererOptions

  /**
   * @desc 创建组件的effect函数 执行render函数
   */
  const setupRenderEffect = (instance, container) => {
    instance.update = effect(function componentEffect() {
      if (!instance.isMounted) {
        let proxyToUse = instance.proxy
        let subTree = instance.subTree = instance.render.call(proxyToUse, proxyToUse)

        // 用render函数的返回值 继续渲染
        patch(null, subTree, container)
        instance.isMounted = true
      } else {
        // 更新 diff vnode
        const prevTree = instance.subTree
        let proxyToUse = instance.proxy
        const nextTree = instance.render.call(proxyToUse, proxyToUse)

        patch(prevTree, nextTree, container)
      }
    }, {
      scheduler: queueJob
    })

  }

  /**
   * @desc 挂载组件
   * @param initialVNode 初始化vnode
   * @param container    dom
   */
  const mountComponent = (initialVNode, container) => {
    // 1.先有实例
    const instance = (initialVNode.component = createComponentInstance(initialVNode))

    // 2.需要的数据解析到实例上 如 state props attrs render...
    setupComponent(instance)

    // 3.创建effect函数 执行render函数
    setupRenderEffect(instance, container)
  }

  /**
   * @desc 加工组件
   */
  const processComponent = (n1, n2, container) => {
    if (n1 == null) {
      // 初次渲染
      mountComponent(n2, container)
    } else {
      // update...
    }
  }

  /**
   * @desc 挂载孩子
   */
  const mountChildren = (children, container) => {
    for (let i = 0; i < children.length; i++) {
      // 孩子有可能存在的文本数组 如['1', 'a']
      // 创建文本的虚拟节点
      // patch时 创建文本节点 将文本节点插入到元素中
      let child = normalizeVNode(children[i])
      patch(null, child, container)
    }
  }

  /**
   * @desc 挂载元素
   */
  const mountElement = (vnode, container, anchor = null) => {
    const { props, shapeFlag, type, children } = vnode
    let el = (vnode.el = hostCreateElement(type))

    // 属性生成
    if (props) {
      for (const key in props) {
          hostPatchProp(el, key, null, props[key]);
      }
    }

    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
      hostSetElementText(el, children)
    } else if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      mountChildren(children, el)
    }

    hostInsert(el, container, anchor)
  }

  /**
   * @desc 加工元素
   */
  const processElement = (n1, n2, container, anchor) => {
    if (n1 == null) {
      mountElement(n2, container, anchor)
    } else {
      // diff Element
      patchElement(n1, n2, container)

    }
  }

  /**
   * @desc 加工文本
   */
  const processText = (n1, n2, container) => {
    if (n1 == null) {
      hostInsert((n2.el = hostCreateText(n2.children)), container)
    }
  }

  /** ******** diff module ******** */
  /**
   * @param n1          oldVNode
   * @param n2          newVNode
   * @param container   Dom
   * @param anchor      参照物节点
   */
  /**
   * @desc 比较两个虚拟节点 是否一致
   */
  const isSameVNodeType = (n1, n2) => {
    return n1.type === n2.type && n1.key === n2.key
  }

  /**
   * @desc 销毁元素, 组件
   */
  const unmount = (n1) => {
    // 源码中如果是组件(这里就展示)
    // 调用的组件的生命周期 调用组件的销毁方法等
    hostRemove(n1.el)
  }

  /**
   * @desc 销毁孩子元素, 孩子组件
   */
  const unmountChildren = (children) => {
    for (let i = 0; i < children.length; i++) {
      unmount(children[i])
    }
  }

  /**
   * @desc 比对属性
   */
  const patchProps = (oldProps, newProps, el) => {
    if (oldProps !== newProps) {
      for (let key in newProps) {
        const prev = oldProps[key]
        const next = newProps[key]
        if (prev !== next) {
          hostPatchProp(el, key, prev, next)
        }
      }
      for (const key in oldProps) {
        if (!(key in newProps)) {
          hostPatchProp(el, key, oldProps[key], null)
        }
      }
    }
  }

  /**
   * @desc 核心diff 比对孩子
   * @param c1 老的孩子
   * @param c2 新的孩子
   * @param el 父元素
   */
  const patchKeyedChildren = (c1, c2, el) => {
    // Vue3都是默认从头开始比对
    let i = 0
    let e1 = c1.length - 1
    let e2 = c2.length - 1

    // diff children 1 从头开始比 不同的就停止
    while (i <= e1 && i <= e2) {
      const n1 = c1[i]
      const n2 = c2[i]
      if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, el)
      } else {
        break;
      }

      i++;
    }

    // diff children 2 从尾开始比 不同的就停止
    while (i <= e1 && i <= e2) {
      const n1 = c1[e1]
      const n2 = c2[e2]
      if (isSameVNodeType(n1, n2)) {
          patch(n1, n2, el)
      } else {
          break;
      }
      e1--;
      e2--;
    }

    if (i > e1) {
      // diff children 3 老的少 新的多(有一方比对完成)
      // 两种情况从前往后比时 和 从后往前比时(同一个逻辑)
      if (i <= e2) {
        // 想知道是向前插入 还是向后插入
        const nextPos = e2 + 1
        const anchor = nextPos < c2.length ? c2[nextPos].el : null
        while (i <= e2) {
          patch(null, c2[i], el, anchor)
          i++;
        }
      }
    } else if (i > e2) {
      // diff children 4 老的多 新的少(有一方比对完成)
      while (i <= e1) {
        unmount(c1[i])
        i++;
      }
    } else {
      // diff children 5 乱序比较
      // 用新的元素做成一个映射表去老的里找
      // 一样的就复用 不一样的要不插入 要不删除
      let s1 = i
      let s2 = i

      // 用的是新的做的映射表
      const keyToNewIndexMap = new Map()

      // 结果如: { e=>2, c=>3, d=>4, h=>5 }
      for (let i = s2; i <= e2; i++) {
        const childVNode = c2[i]
        keyToNewIndexMap.set(childVNode.key, i)
      }

      // 剩下的没做比较有几个
      const toBePatched = e2 - s2 + 1
      // 将剩下的封装成一个数组, 并每个都赋值为0 
      // 以比较就将老的对应的虚拟节点 索引 赋值给当前数组的
      // 没有比较的就是0
      const newIndexToOldIndexMap = new Array(toBePatched).fill(0)

      for (let i = s1; i<=e1 ; i++) {
        const oldVnode = c1[i]
        let newIndex = keyToNewIndexMap.get(oldVnode.key)
        if(newIndex === undefined) {
          // 新的没有 删除老的
          unmount(oldVnode)
        } else {
          // i+1防止是0 明明比较了 还是0
          newIndexToOldIndexMap[newIndex - s2] = i + 1
          // 在老的中找到 做了新老虚拟比较 但是位置没有移动
          patch(oldVnode, c2[newIndex], el)
        }
      }

      // 最长递增长子序列
      // [1,2]对应[3,4] 就是老节点数组2,3位置的节点, 不需要移动的节点
      // [5,3,4,0] => [1,2]
      let increasingNewIndexSequence = getSequence(newIndexToOldIndexMap)
      let j = increasingNewIndexSequence.length - 1

      // 处理虚拟节点的位置 从后往前依次插入节点
      for (let i = toBePatched - 1; i >= 0; i--) {
        // 找到当前最后一个 和 当前节点
        let currentIndex = i + s2
        let child = c2[currentIndex]

        // 插入的参照物
        let anchor = currentIndex + 1 < c2.length ? c2[currentIndex+1].el  : null

        // 如果是0 说明没有被patch过
        if(newIndexToOldIndexMap[i] == 0) {
          patch(null, child, el, anchor)
        } else {
          
          // 从后往前查 没有就插入 
          if(i != increasingNewIndexSequence[j]){
            hostInsert(child.el, el, anchor)
          } else {
            j--;
          }

        }

      }
      
    }

  }

  /**
   * @desc 比对孩子
   */
  const patchChildren = (n1, n2, el) => {
    const c1 = n1.children
    const c2 = n2.children

    const prevShapeFlag = n1.shapeFlag
    const shapeFlag = n2.shapeFlag

    // c2如果是文本
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
      // 3.老的是数组 新的是文本 销毁老的
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        unmountChildren(c1)
      }

      // 4.都是文本
      if (c1 !== c2) {
        hostSetElementText(el, c2)
      }

    } else {
      // c2否则是null 或者 数组
      if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          // 都是数组
          // 核心diff
          patchKeyedChildren(c1, c2, el)
        } else {
          // 5.null 特殊情况 删除掉老的
          unmountChildren(c1)
        }

      } else {
        // 6.老的是文本 现在是数组
        if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
          hostSetElementText(el, '');
        }

        if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
          mountChildren(c2, el);
        }

      }

    }

    
  }

  /**
   * @desc 比对元素
   */
  const patchElement = (n1, n2, container) => {
    // 相同节点
    let el = (n2.el = n1.el)

    // 2.比对属性
    const oldProps = n1.props || {}
    const newProps = n2.props || {}
    patchProps(oldProps, newProps, el)

    // 比对孩子
    patchChildren(n1, n2, el)
  }

  /**
   * @desc 比对
   * @param n1          老的vnode
   * @param n2          新的vnode
   * @param container   dom
   * @param anchor      参照物节点
   */
  const patch = (n1, n2, container, anchor = null) => {
    const { shapeFlag, type } = n2

    // 1.type 不同直接替换
    if (n1 && !isSameVNodeType(n1, n2)) {
      anchor = hostNextSibling(n1.el)
      unmount(n1)
      n1 = null
    }

    switch (type) {
      case Text:
        processText(n1, n2, container)
        break;
    
      default:
        if (shapeFlag & ShapeFlags.ELEMENT) {
          processElement(n1, n2, container, anchor)
        } else if (shapeFlag & ShapeFlags.STATEFUL_COMPONENT) {
          processComponent(n1, n2, container)
        }

        break;
    }
  }

  /**
   * @desc 渲染
   * @param vnode     vnode
   * @param container dom
   */  
  const render = (vnode, container) => {
    // 核心 根据vnode -> dom
    patch(null, vnode, container)
  }

  /**
   * @desc 最长递增子序列
   */
  function getSequence(arr) {
    const len = arr.length
    const result = [0]
    const p = arr.slice(0)
    let start;
    let end;
    let middle;
    for (let i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            let resultLastIndex = result[result.length - 1]
            // 取到索引对应的值
            if (arr[resultLastIndex] < arrI) {
                p[i] = resultLastIndex
                result.push(i)
                continue
            }
            start = 0;
            end = result.length - 1;
            while (start < end) {
                middle = ((start + end) / 2) | 0
                if (arr[result[middle]] < arrI) {
                    start = middle + 1
                } else {
                    end = middle
                }
            }

            if (arrI < arr[result[start]]) {
                if (start > 0) {
                  p[i] = result[start - 1]
                }
                result[start] = i
            }
        }
    }
    let len1 = result.length
    let last = result[len1 - 1]
    while (len1-- > 0) {
        result[len1] = last
        last = p[last]
    }
    return result
  }

  return {
    createApp: createAppAPI(render)
  }
}

vue3核心组件更新diff算法(简易)

前言

示例

组件更新

新老元素不一样

元素一样

比对属性

比对孩子(子节点)

比对孩子(子节点) 核心diff算法

从头开始(sync form start)

从尾开始(sync from end)

老的少新的多(common sequence + mount)

老的多新的少(common sequence + unmount)

乱序比较(unknown sequence)

步骤一

步骤二

步骤三

最长递增长子序列

第一步

第二步

第三步

shard runtime-dom runtime-core

renderer.ts

完

常见问题FAQ

掘金(小桂summer) SVIP

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

前言

示例

组件更新

新老元素不一样

元素一样

比对属性

比对孩子(子节点)

比对孩子(子节点) 核心diff算法

从头开始(sync form start)

从尾开始(sync from end)

老的少 新的多(common sequence + mount)

老的多 新的少(common sequence + unmount)

乱序比较(unknown sequence)

步骤一

步骤二

步骤三

最长递增长子序列

第一步

第二步

第三步

shard runtime-dom runtime-core

renderer.ts

完

常见问题FAQ

掘金(小桂summer) SVIP

相关推荐

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

请选择支付方式

老的少新的多(common sequence + mount)

老的多新的少(common sequence + unmount)