• diff算法原理解析

    目录

    diff算法

    1.前提：

    • DOM操作的执行速度 远远不如 javascript的运行速度快；
    • 若是直接渲染真实DOM开销是很大的，比如有时候我们修改了某个数据，如果直接渲染到真实dom上会引起整个dom树的重绘和重排；
    • 若是想要仅是重新渲染修改的那一小块dom而不是重新渲染整个dom树；
      • [1]根据dom树生成虚拟dom;
      • [2]当虚拟dom节点发生变化生成一颗新的虚拟dom;
      • [3]对比新旧虚拟dom差异，发现不一样的地方直接更新在真实dom上；
    • 注：虚拟DOM 并不是Vue独有的，包括React等其他前端框架，只要采用了先计算后操作实体DOM都可以统称为基于虚拟DOM，目的是为了解决浏览器性能问题;

    2.虚拟DOM

    (1)定义

    使用js对象模拟的页面dom结构被称为虚拟DOM；

    (2)组成

    一个dom元素主要包含一下三点

    • 自身标签
    • 自身属性
    • 子节点

    因此使用js对象模拟虚拟dom如下

    • 真实dom

      • <div class="el-select__tags" style="width: 100%; max-width: 178px;">
 <input type="text" autocomplete="off" class="el-select__input" max-width:168px;">
 222
div>

        • 1
        • 2
        • 3
        • 4

    • 虚拟dom

      • const vnode = {
      tag:'div', // 标签
      props:{
        class:'el-select__tags',
        style:'width: 100%; max-width: 178px;'
      }, //属性
      children:[
        {
          tag:'input',
          attrs:{
            type:'text',
            autocomplete:'off',
            class:'el-select__input',
            style:'flex-grow: 1; width: 0.11236%; max-width: 168px;'
          }
        }, // ---元素节点
        '222' // 文本节点
      ] // 子节点
    }

        • 1
        • 2
        • 3
        • 4
        • 5
        • 6
        • 7
        • 8
        • 9
        • 10
        • 11
        • 12
        • 13
        • 14
        • 15
        • 16
        • 17
        • 18
        • 19

    3.使用diff算法对新旧vnode进行比较

    diff算法在vue中是封装在patch方法中；

    比较规则

    只比较同一级，不跨级比较;

    • 在这里插入图片描述

    • 一切以vnode为准，oldVnode为真实dom映射！

    patch方法
    // 公共方法
function isDef (v) {
  return v !== undefined && v !== null
}
function isUndef (v) {
  return v === undefined || v === null
}
// patch方法  -- 找出dom最小差异并进行替换
function patch (oldVnode, vnode, hydrating, removeOnly) {
    // [1]vnode不存在，oldVnode存在 ---> 直接销毁oldVnode(解绑它的指令及事件监听器)
    if (isUndef(vnode)) {
      if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
      return
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []
    // [2]vnode存在，oldVnode不存在 --->依据vnode创建真实dom
    if (isUndef(oldVnode)) {
      isInitialPatch = true
      createElm(vnode, insertedVnodeQueue)
    } else {
      // [3]vnode与oldVnode都存在，调用sameVnode方法判断 oldVnode与vnode是否为同一节点
      const isRealElement = isDef(oldVnode.nodeType)
      // [3.1]oldVnode不是真实dom节点 && oldVnode与vnode为同一节点时，调用patchVnode方法去判断 节点文本或子节点变化
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
      } else {
        const oldElm = oldVnode.elm
        const parentElm = nodeOps.parentNode(oldElm)

        // [3.2]oldVnode不是真实dom节点 && oldVnode与vnode不为同一节点时， 依据vnode创建新的dom节点插入页面中；
        createElm(
          vnode,
          insertedVnodeQueue,
          oldElm._leaveCb ? null : parentElm,
          nodeOps.nextSibling(oldElm)
        )

        // 递归更新父占位符节点元素
        if (isDef(vnode.parent)) {
          let ancestor = vnode.parent
          const patchable = isPatchable(vnode)
          while (ancestor) {
            for (let i = 0; i < cbs.destroy.length; ++i) {
              cbs.destroy[i](ancestor)
            }
            ancestor.elm = vnode.elm
            if (patchable) {
              for (let i = 0; i < cbs.create.length; ++i) {
                cbs.create[i](emptyNode, ancestor)
              }
              // #6513
              // invoke insert hooks that may have been merged by create hooks.
              // e.g. for directives that uses the "inserted" hook.
              const insert = ancestor.data.hook.insert
              if (insert.merged) {
                // start at index 1 to avoid re-invoking component mounted hook
                for (let i = 1; i < insert.fns.length; i++) {
                  insert.fns[i]()
                }
              }
            } else {
              registerRef(ancestor)
            }
            ancestor = ancestor.parent
          }
        }

        // 移除老节点
        if (isDef(parentElm)) {
          removeVnodes([oldVnode], 0, 0)
        } else if (isDef(oldVnode.tag)) {
          invokeDestroyHook(oldVnode)
        }
      }
    }

    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
  }

    • 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

    • vnode 不存在，oldVnode 存在 —> 删掉oldVnode

    • vnode存在, oldVnode不存在—> 创建vnode

    • oldVnode存在，vnode存在—>更新

      • [1]通过sameVnode函数对比是不是同一节点

        • 如果不是同一节点 —> 替换;

        • 如果是同一节点的话，通过 patchVnode 进行后续对比 节点文本变化 或 子节点变化

    sameVnode方法
    // 判断两个节点是否为同一节点
function sameVnode(a, b) {
  return (
    a.key === b.key &&  // key值是否相同
    a.asyncFactory === b.asyncFactory && // 异步工厂方法
    ((a.tag === b.tag && // 标签名
      a.isComment === b.isComment && // 是否为注释节点
      isDef(a.data) === isDef(b.data) && // 是否有属性
      sameInputType(a, b)) || // 是否为input节点&type属性值是否相同
      (isTrue(a.isAsyncPlaceholder) && // 是否为异步占位符节点
       isUndef(b.asyncFactory.error)
      ))
  )
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 注意点：若是元素没有设置key值 --> undefined===undefined ;
      • a.key===b.key同样为true;
    patchVnode方法

    • 作用：对比新旧vnode，找出最小差异；

    • 过程：包含三种类型操作：属性更新、文本更新、子节点更新；

    • 比较过程

      • [1]若是oldVnode与vnode相等
        • 节点没有更新 —> 节点文本以及子节点复用(无需更新)
      • [2]若是新旧节点均为静态节点 && key值相同 && 节点被closed或加了v-once
        • 节点即使更新也不会重新渲染 —> 节点文本以及子节点复用(无需更新)
      • 若不是以上两种情况
        • [1]全量属性更新
        • [2]文本内容以及子节点对比
          • [2.1]若是子节点都存在— > 调用updateChildren对比子节点
          • [2.2]vnode子节点存在，但是oldVnode子节点不存在 —> (oldVnode存在文本则清除文本)向oldVnode添加节点;
          • [2.3]vnode不存在子节点，但是oldVnode子节点存在 —> 销毁oldVode子节点
          • [2.4]子节点都不存在(为文本节点时) —> 比较文本内容进行文本替换；
    •   function patchVnode (
    oldVnode,
    vnode,
    insertedVnodeQueue,
    ownerArray,
    index,
    removeOnly
  ) {

    // [1]若是oldVnode与vnode的引用地址相同，表示该节点无变化 ---> 节点文本以及子节点复用；
    if (oldVnode === vnode) {
      return
    }

    // elm属性存在 --> 该节点被渲染过； ownerArray 存在---> 表示存在子节点；
    // 若是新的虚拟节点被渲染过并且存在子节点则克隆一个虚拟节点；
    if (isDef(vnode.elm) && isDef(ownerArray)) {
      vnode = ownerArray[index] = cloneVNode(vnode)
    }
    const elm = vnode.elm = oldVnode.elm

    // [2]若是oldVnode与vnode均为静态节点 && key值相同 && (vnode被closed || vnode上存在v-once) --> 直接复用
    if (isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }

    let i
    const data = vnode.data
    // [3]进行全量属性更新
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }

    const oldCh = oldVnode.children
    const ch = vnode.children
    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)
    }
    // [4]子节点对比
    if (isUndef(vnode.text)) {
      // [4.1]vnode为元素节点或是text属性为空的文本节点
      if (isDef(oldCh) && isDef(ch)) {
        // [4.1.1]子节点都存在且不相同 --- > 调用updateChildren对比子节点
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // [4.1.2]vnode子节点存在，但是oldVnode子节点不存在 ---> 若是oldVnode存在文本则清除文本；向oldVnode添加节点； 
        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)) {
        // [4.1.3]vnode不存在子节点，但是oldVnode子节点存在 ---> 销毁oldVode子节点
        removeVnodes(oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        // [4.1.4]新旧vnode都不存在子节点，oldVnode存在文本节点---> 清除文本
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // [4.2] 新旧vnode都存在节点但是节点不相同 ---> 替换oldVnode文本
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

      • 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
    静态节点
    • 在编译过程中，会找出模板中的静态节点并做上标记—>isStatic为true
    • 什么样的节点称为静态节点呢
      • (1)节点使用了v-pre指令
      • (2)如果没有使用v-pre指令，那它要成为静态节点必须满足
        • 不能使用动态绑定语法，即标签上不能有v-、@、:开头的属性
        • 不能使用v-if、v-else、v-for指令；
        • 不能是内置组件，即标签名不能是slot和component；
        • 标签名必须是平台保留标签，即不能是组件；
        • 当前节点的父节点不能是带有 v-for 的 template 标签；
        • 节点的所有属性的 key 都必须是静态节点才有的 key，注：静态节点的key是有限的，它只能是type,tag,attrsList,attrsMap,plain,parent,children,attrs之一；
        • 元素的所有子节点必须为静态节点
          • 标记完当前节点是否为静态节点之后，如果该节点是元素节点，那么还要继续去递归判断它的子节点.如果当前节点的子节点有一个不是静态节点，那就把当前节点也标记为非静态节点.
    updateChildren方法
      function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    // [1]定义 旧前、新前、旧后、新后四个指针 进行对比
    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

    const canMove = !removeOnly

    if (process.env.NODE_ENV !== 'production') {
      checkDuplicateKeys(newCh)
    }
    // 若是 旧前>旧后或 新前>新后 则表示已经对比完毕 
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      // 对比顺序  旧前-新前、旧后-新后、旧前-新后、旧后-新后
      if (isUndef(oldStartVnode)) {
        // 跳过空节点
        oldStartVnode = oldCh[++oldStartIdx] 
      } else if (isUndef(oldEndVnode)) {
        // 跳过空节点
        oldEndVnode = oldCh[--oldEndIdx]
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        // [1] 使用sameVnode 对比旧前与新前的节点是否为相同节点 若是相同节点则调用patchVnode方法进行比较更新；指针前移
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // [2] 使用sameVnode 对比旧后与新后的节点是否为相同节点 若是相同节点则调用patchVnode方法进行比较更新；指针前移
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { 
        // Vnode moved right
        // [3]使用sameVnode 对比旧前与新后的节点是否为相同节点 若是相同节点则调用patchVnode方法进行比较更新；
        //   [3.1]操作真实dom:将前指针所指向的子节点 移动到 oldEndIndex所对应真实节点之后（也就是未处理真实节点的尾部）
        //   [3.2]指针前移
        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
        // [4]使用sameVnode 对比旧后与新前的节点是否为相同节点 若是相同节点则调用patchVnode方法进行比较更新；
        //   [4.1]操作真实dom:将前指针所指向的子节点 移动到 oldEndIndex所对应真实节点之后（也就是未处理真实节点的尾部）
        //   [4.2]指针前移
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // [5]四种规则均不匹配
        // [5.1]使用 createKeyToOldIdx 方法 将oldVnode的key值与索引 以 key-value 的形式存储在对象中
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        // [5.2] 在vnode中找出 新前对应的节点的索引
        // [5.2.1]oldVnode存在key值---> 通过key值在oldVnode找到新前对应的节点的索引
        // [5.2.2]oldVnode不存在key值 --> 通过  findIdxInOld方法遍历  +  sameVnode方法对比  在oldVnode找出新前对应的节点的索引
        idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) { 
          // [5.3]索引不存在 ---> 说明节点为新节点 ---> 创建真实dom
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // [5.4]索引存在 ---> sameVnode方法对比是否为同一节点 
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // [5.4.1]若是同一节点
            //   [5.4.1.1]patchVnode方法对比子节点与文本内容
            //   [5.4.1.2]操作真实dom ---> 将前指针所指向的子节点 移动到 oldEndIndex所对应真实节点之后（也就是未处理真实节点的尾部）
            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
            // [5.4.2]若不是同一节点---> 创建真实dom并插入
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      // Vnode元素较多，添加节点
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      // oldVnode节点较多，移除多余节点
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }

    • 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
    findIdxInOld方法
    function findIdxInOld (node, oldCh, start, end) {
    for (let i = start; i < end; i++) {
      const c = oldCh[i]
      if (isDef(c) && sameVnode(node, c)) return i
    }
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
  • 相关阅读:
    国际赛事证书，220G数据集开放下载｜ACCV2022国际细粒度图像分析挑战赛开赛
    【经纬恒润】自动驾驶感知算法岗位一面
    秒杀系统高并发优化
    day36-xml
    内存模型以及如何判定对象已死问题
    Web核心快速学习之Servlet技术(其一)
    工厂设备管理维护系统开发
    JVM【类加载与GC垃圾回收机制】
    How to push branch and tag to remote repository in git
    中学化学教学参考杂志社中学化学教学参考编辑部2022年第12期目录
  • 原文地址：https://blog.csdn.net/qq_43260366/article/details/125893316