vue2.x의 diff 알고리즘 원리에 대한 심층 분석

diff 알고리즘은 동일한 수준의 트리 노드를 비교하는 효율적인 알고리즘으로, 트리를 계층별로 검색하고 탐색할 필요가 없습니다. 이 글은 vue2.x의 diff 알고리즘 원리에 대한 심층 분석을 제공할 것입니다. 도움이 되기를 바랍니다.

저는 소스코드 분석 기사를 많이 읽었고 소스코드를 두 번 이상 읽었습니다. 결국엔 그래도 일종의 기록으로 직접 쓰고 싶고, 나 자신을 위한 공부도 하고 싶다. 댓글과 요약에 집중하고 나머지는 너무 걱정하지 마세요, 요약과 소스 코드를 비교하여 프로세스와 댓글을 검토하면 더 많은 것을 얻을 수 있습니다

메서드 정의 업데이트

렌더 함수가 생성된 후 마운팅 중에 Diff 계산이 수행됩니다. 초기화 중에는 이전 가상 노드가 없으므로 처음으로 실제 DOM 노드와 비교됩니다. 가상 노드가 기본 노드가 아닌 경우 처음으로 교체 작업이 수행됩니다. (학습 영상 공유: vue 영상 튜토리얼)

// /src/core/instance/lifecycle.js
Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const restoreActiveInstance = setActiveInstance(vm)
    vm._vnode = vnode // 当前render函数产生的虚拟节点,保存后以便下次做对比
    if (!prevVnode) {
      vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染
    } else {
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
   ...
  }

diff 알고리즘에는 두 개의 주요 분기가 있습니다

본체는 두 개의 주요 분기로 구성됩니다. 전면 및 후면 가상 노드는 일관성이 있고 전면 및 후면 가상 노드는 동일합니다. 불일치

// /src/core/vdom/patch.js
export function createPatchFunction (backend) {
  ...
  return function patch (oldVnode, vnode, hydrating, removeOnly) {
    ...
      if (!isRealElement && sameVnode(oldVnode, vnode)) {
        ...// 前后虚拟节点一致的方法
      } else {
        ...// 前后虚拟节点不一致的方法
      }
  }
}

전면 및 후면 가상 노드가 불일치합니다

3단계로 나뉩니다: 1. 새 노드 생성, 2. 상위 자리 표시자 노드 업데이트, 3. 이전 노드 삭제
두 단계는 다음과 같은 경우에 다릅니다. 컴포넌트가 처음 마운트되면 실제 DOM인지 판단됩니다. 가상 노드로 변환되어 교체됩니다

if (isRealElement) {
  ...
  //需要diff 所以将第一次的真实节点转换成虚拟节点
  oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div>
}
// 拿到父类的dom节点
const oldElm = oldVnode.elm //app
const parentElm = nodeOps.parentNode(oldElm) // body
//创建新dom节点 内部包含组件逻辑
createElm(
  vnode,
  insertedVnodeQueue,
  oldElm._leaveCb ? null : parentElm,
  nodeOps.nextSibling(oldElm)
)
//更新父的占位符节点 (组件更新相关)
if (isDef(vnode.parent)) {
  // 在生成render函数时会生成占位符节点<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符节点
  let ancestor = vnode.parent
  // 判断是否可挂载
  const patchable = isPatchable(vnode)
  while (ancestor) {
    for (let i = 0; i < cbs.destroy.length; ++i) {
      cbs.destroy[i](ancestor)
    }
    //更新父占位符的element
    ancestor.elm = vnode.elm
    if (patchable) {
      ...
    } else {
      registerRef(ancestor)
    }
    ancestor = ancestor.parent
  }
}
// 删除旧节点
if (isDef(parentElm)) {
  removeVnodes([oldVnode], 0, 0)
} else if (isDef(oldVnode.tag)) {
  invokeDestroyHook(oldVnode)
}

전후의 가상 노드가 일치하는지

• 먼저 확인하세요. 새 노드가 텍스트인지, 그렇다면 텍스트를 직접 설정하고, 그렇지 않다면 계속해서 결정하세요
• 새 노드와 이전 노드에 자식이 있습니다. 심층 비교(핵심)
• 새 노드에는 자식이 있고, 이전 노드는 그렇지 않습니다. 루프에 새 노드를 추가하세요
• 새 노드에 자식이 없고, 이전 노드에 자식이 있습니다. 이전 노드를 직접 삭제하세요

function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) {
    const elm = vnode.elm = oldVnode.elm

    let i
    const data = vnode.data 
    // 是组件vnode,在组件更新会调用组件的prepatch方法
    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)
    }
    // 是否是text
    if (isUndef(vnode.text)) {
      // 新旧节点都有children
      if (isDef(oldCh) && isDef(ch)) {
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      // 新有 老没有 children 循环创建新节点
      } else if (isDef(ch)) {
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, &#39;&#39;)
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      // 新没有 老有 children 直接删除老节点
      } else if (isDef(oldCh)) {
        removeVnodes(oldCh, 0, oldCh.length - 1)
      // 新老都没有 children 老的是文本 就置为空
      } else if (isDef(oldVnode.text)) {
        nodeOps.setTextContent(elm, &#39;&#39;)
      }
    // 是text 直接设置文本
    } else if (oldVnode.text !== vnode.text) {
      nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

자식이 있는 이전 노드와 새 노드의 비교

// /src/core/vdom/patch.js
 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
    const canMove = !removeOnly
    // 满足新节点开始索引小于新节点结束索引,旧节点开始索引小于旧节点结束索引
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (isUndef(oldStartVnode)) { // 是否定义老节点开始元素
        oldStartVnode = oldCh[++oldStartIdx]
      } else if (isUndef(oldEndVnode)) {// 是否定义老节点结束元素
        oldEndVnode = oldCh[--oldEndIdx]
        // 头(旧节点开始元素)头(新节点开始元素)对比 例如四个li,末尾新增一个li,这种情况头头对比性能高
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // sameVnode判断key和tag是否相同
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾对比 例如四个li,头部新增一个li,这种情况尾尾对比性能高
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) {// 头尾对比 节点反转优化 reverse
        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)) { // 尾头对比
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else { // 乱序对比(核心diff,其他方式为优化)
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
        if (isUndef(idxInOld)) {
          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)
          } else {
            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(oldCh, oldStartIdx, oldEndIdx)
    }
  }

Note

• 헤드에 요소를 추가할 때 인덱스를 키로 사용하면 업데이트 오류가 발생하기 때문에 인덱스를 키로 사용할 수 없는 경우가 있습니다. 끝에 요소를 추가한다고 이해하게 될 것입니다(이전과 이후의 키가 모두 0이기 때문입니다)
• 다양한 비교 상황에서 둘이 동일하다면 자식은 재귀적으로 비교됩니다
• 비순서적으로 비교해보면 키의 역할이 굉장하네요. 키가 없으면 업데이트 오류가 발생하고 재사용 효과를 얻을 수 없습니다. diff 비교는
깊이 우선, 동일 레이어 비교

요약

템플릿은 마운트 시 diff 알고리즘 이후에 업데이트됩니다. 처음으로 실제 DOM 노드가 생성된 가상 노드와 비교되고 생성된 가상 노드는 나중에 업데이트 및 비교를 위해 저장됩니다. diff 알고리즘은 두 개의 분기로만 분할하면 됩니다. 전면 및 후면 가상 노드는 일관성이 있고 전면 및 후면 가상 노드는 일관성이 없습니다. 전면 및 후면 가상 노드가 일치하지 않으면 새 노드가 생성되고 상위 자리 표시자가 업데이트되며 이전 노드가 삭제됩니다. 이전 노드가 실제 노드인 경우 가상 노드로 변환하고 이전 노드의 상위 노드를 가져와 이전 노드를 교체합니다. 전면 및 후면 가상 노드가 일치하는 경우 먼저 새 노드가 텍스트인지 확인하고 값이 직접 추가된 경우 속성을 먼저 비교한 다음 새 노드에 자식이 있는지, 이전 노드에 있는지 확인합니다. 자식이 없으면 새 노드 자식이 직접 추가됩니다. 새 노드에 자식이 있으면 새 노드가 직접 추가됩니다. 노드가 없지만 이전 노드가 있으면 이전 노드의 자식이 제거됩니다. 이전 노드와 새 노드에 자식이 있으면 이중 포인터를 사용하여 정면 비교, 꼬리 비교, 꼬리 비교, 꼬리 비교를 통해 동일한 레이어를 비교합니다. 오래된 노드의 활용을 극대화하기 위해 지속적으로 반복적으로 판단하고 업데이트하며, 중복된 새 노드가 있으면 추가되고, 마지막으로 비교된 가상 노드는 삭제됩니다. 비교할 다음 번 이전 노드로 반환되어 저장됩니다.

• 직접 비교
  새 시작 요소와 이전 시작 요소가 동일한 vnode에 있는 경우 patchVnode 메서드를 재귀적으로 호출하여 심층 비교를 한 후 인덱스를 다음 요소로 이동합니다.patchVnode方法进行深层对比,之后移动索引至下一个元素
• 尾尾对比
  如果新旧结束元素是相同vnode,递归调用patchVnode方法进行深层对比,之后移动索引至上一个元素
• 头尾对比
  将老节点开始元素和旧节点尾元素进行对比,相同就递归调用patchVnode方法进行深层对比,之后将旧节点元素移动至最后,旧节点头指针移动到下一个,新节点的尾指针移动至上一个。例如旧:A,B,C,新:C,B,A,第一次对比将旧A移动到C后边
• 尾头对比
  将老节点尾元素和旧节点开始元素进行对比,相同就递归调用patchVnode
Tail -to-tail 비교
• 이전 끝 요소와 새 끝 요소가 동일한 vnode에 있는 경우 심층 비교를 위해 patchVnode 메서드를 재귀적으로 호출한 다음 인덱스를 이전 요소로 이동합니다
  
Head-to- tail 비교

이전 노드의 시작 요소와 이전 노드의 tail 요소를 비교합니다. 동일하면 patchVnode를 재귀적으로 호출합니다. > 메서드는 심층 비교를 수행한 다음 이전 노드 요소를 끝으로 이동합니다. 이전 노드의 헤드 포인터를 다음 노드로 이동하고, 새 노드의 테일 포인터를 이전 노드로 이동합니다. 예를 들어 old: A, B, C, new: C, B, A. 첫 번째 비교를 위해 이전 A를 C의 뒤로 이동

Tail 및 헤드 비교 이전 노드의 꼬리 요소를 이전 노드의 시작 요소가 동일하면 재귀적으로 patchVnode 메서드를 호출하여 심층 비교를 한 다음 이전 노드 요소를 앞으로 이동하고 이전 노드의 꼬리 포인터를 이전 요소로 이동합니다. 그리고 새 노드의 헤드 포인터는 다음 노드를 가리킵니다. 예를 들어 이전: A, B, C, 새: C, B, A, D입니다. 첫 번째 비교는 이전 C를 A의 앞으로 이동합니다.비순차 비교

이전 노드는 다음을 기반으로 생성됩니다. 매핑 테이블 전에 키와 해당 인덱스에 대해. 비순차적 비교 중에는 현재 키를 사용하여 이전 노드의 키를 찾습니다. 재사용이 가능한 경우 노드는 이전 노드의 시작 부분으로 이동되고 하위 노드는 재귀적으로 비교됩니다. 재사용할 수 없으며 새 노드가 생성되어 노드 시작 부분에 삽입됩니다. 그런 다음 새 인덱스를 다음 요소로 이동🎜🎜🎜 (학습 영상 공유: 🎜웹 프론트엔드 개발🎜, 🎜기본 프로그래밍 영상🎜)🎜

위 내용은 vue2.x의 diff 알고리즘 원리에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!