하나의 기사로 vue2 diff 알고리즘 이해하기(그림 포함)

vue2 diff 프로세스

• 비교 방법: 동일 수준 비교, 수준 간 비교 없음

다음 소스 코드는 vue/patch.ts에서 가져온 것입니다. 일부 추출이 있습니다. , 관련 기능은 링크가 첨부되어 있습니다. [관련 권장사항: vuejs 동영상 튜토리얼, 웹 프론트엔드 개발]

patch function

• diff 프로세스는 patch를 호출하는 것입니다. 이전 노드와 새 노드를 비교하는 함수, 실제 DOM을 비교하고 패치하는 동안 먼저 patch 함수를 살펴보겠습니다. diff过程就是调用 patch函数，比较新旧节点，一边比较一边给真实DOM打补丁，那么我们就先来看一下patch函数:
• 源码地址：  patch函数，isUndef()函数，isDef()函数， emptyNodeAt函数

  return function patch(oldVnode, vnode, hydrating, removeOnly) {
      if (isUndef(vnode)) {  //新的节点不存在
          if (isDef(oldVnode)) //旧的节点存在
          invokeDestroyHook(oldVnode)   //销毁旧节点
          return
       }
         .........
      //isRealElement就是为处理初始化定义的,组件初始化的时候，没有oldVnode，那么Vue会传入一个真实dom
      if (!isRealElement && sameVnode(oldVnode, vnode)) { -----判断是否值得去比较
        patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly) ---打补丁,后面会详细讲
      } else {
        ......
         if (isRealElement) 
         ......
          oldVnode = emptyNodeAt(oldVnode) //转化为Vnode，并赋值给oldNode
        }
        // replacing existing element
        const oldElm = oldVnode.elm      ----找到oldVnode对应的真实节点
        const parentElm = nodeOps.parentNode(oldElm)  ------找到它的父节点
        createElm(.....) --------创建新节点
        ....递归地去更新节点
    return vnode.elm
  }

sameNode函数

• 其中出现了sameNode，判断是否值得我们去给他打补丁，不值得的话就按照上述步骤进行替换，我们还是去寻找一下这个函数
• 源码地址： sameNode函数

function sameVnode(a, b) {
  return (
        a.key === b.key &&  ----------------------key值相等， 这就是为什么我们推荐要加上key，可以让判断更准确
    a.asyncFactory === b.asyncFactory && 
    ((a.tag === b.tag && ---------------------标签相等
      a.isComment === b.isComment && ---------是否为注释节点
      isDef(a.data) === isDef(b.data) &&  ----比较data是否都不为空
      sameInputType(a, b)) ||  ---------------当标签为input的时候，需要比较type属性
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}

• 如果值得我们去给他打补丁，则进入我们patchVNode函数

patchVNode

• 源码地址： patchVNode函数
• 这个函数有点长，也是做了一下删减

  function patchVnode(...
  ) {
    if (oldVnode === vnode) {  //两个节点一致，啥也不用管，直接返回
      return
    }
    ....
    if (
    //新旧节点都是静态节点，且key值相等，则明整个组件没有任何变化，还在之前的实例，赋值一下后直接返回
      isTrue(vnode.isStatic) &&
      isTrue(oldVnode.isStatic) &&
      vnode.key === oldVnode.key &&
      (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
      vnode.componentInstance = oldVnode.componentInstance
      return
    }
    const oldCh = oldVnode.children  //获取旧节点孩子
    const ch = vnode.children //获取新节点孩子
    if (isUndef(vnode.text)) { //新节点没有文本
      if (isDef(oldCh) && isDef(ch)) {  //旧节点孩子和新节点孩子都不为空
        if (oldCh !== ch) //旧节点孩子不等于新节点孩子
          updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) //重点----比较双方的孩子进行diff算法 
      } else if (isDef(ch)) {  //新节点孩子不为空，旧节点孩子为空
         ....
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) //新增节点
       } else if (isDef(oldCh)) {  //新节点孩子为空，旧节点孩子不为空
        removeVnodes(oldCh, 0, oldCh.length - 1)  //移除旧节点孩子节点
      } else if (isDef(oldVnode.text)) {  //旧节点文本为不为空
        nodeOps.setTextContent(elm, '')  //将节点文本清空
      }
    } else if (oldVnode.text !== vnode.text) { //新节点有文本，但是和旧节点文本不相等
      nodeOps.setTextContent(elm, vnode.text) //设置为新节点的文本
    }
  }

• 这里的判断很多，所以我也加了个流程图

updateChildren（diff算法的体现）

• 源码地址：updateChildren函数
• 这里采用四步走的形式，我把代码都拆分出来了

初始化

• 采用的四个指针分别指向四个节点
  • oldStartIdx，newStartIdx 指向旧节点头，新节点头， 初始值为0
  • oldEndIdx， newEndIdx
  소스 코드 주소: 패치 기능
  , isUndef() 함수
, isDef() 함수

    let oldStartIdx = 0 //旧头指针
    let newStartIdx = 0 //新头指针
    let oldEndIdx = oldCh.length - 1  //旧尾指针
    let newEndIdx = newCh.length - 1 //新尾指针
    let oldStartVnode = oldCh[0] //旧头结点
    let oldEndVnode = oldCh[oldEndIdx] //旧尾结点
    let newStartVnode = newCh[0] //新头结点
    let newEndVnode = newCh[newEndIdx]  //新尾结点

sameNode 기능

sameNode< /code>가 나타나면 패치할 가치가 있는지 판단하세요. 그럴 가치가 없다면 위 단계에 따라 교체하세요.<li></li>소스 코드 주소: <a href="https://www. .php.cn/link/a0e50a390f3e2ff0e2c6f535d86a23ba" target ="_blank" title="">sameNode function<li></li><li><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;"> function updateChildren(){ ·.... //好戏从这里开始看 //只要满足 旧头指针&lt;=旧尾指针 同时 新头指针&lt;= 新尾指针 -- 也可以理解为不能交叉 while (oldStartIdx &lt;= oldEndIdx &amp;&amp; newStartIdx &lt;= newEndIdx) { //这里进行一个矫正，是应该在循环的过程中，如果进入key表查询的话复用后会将旧节点置空（后面会说），所以这里会对其进行一个处理 if (isUndef(oldStartVnode)) { //旧头结点为空 oldStartVnode = oldCh[++oldStartIdx] // 往右边走 } else if (isUndef(oldEndVnode)) { //旧尾结点为空 oldEndVnode = oldCh[--oldEndIdx] //往左边走 //step1 } else if (sameVnode(oldStartVnode, newStartVnode)) { //比较旧头和新头，判断是否值得打补丁 patchVnode(...) //打补丁 oldStartVnode = oldCh[++oldStartIdx] //齐头并进向右走 newStartVnode = newCh[++newStartIdx] //齐头并进向右走 //step2 } else if (sameVnode(oldEndVnode, newEndVnode)) { //比较旧尾和新尾， 判断是否值得打补丁 patchVnode(...) //打补丁 oldEndVnode = oldCh[--oldEndIdx] //齐头并进向左走 newEndVnode = newCh[--newEndIdx] //齐头并进向左走 //step3 } else if (sameVnode(oldStartVnode, newEndVnode)) { //比较旧头和新尾，判断是否值得打补丁 patchVnode(...) //打补丁 //补完移动节点 canMove &amp;&amp; nodeOps.insertBefore(parentElm,oldStartVnode.elm,nodeOps.nextSibling(oldEndVnode.elm)) oldStartVnode = oldCh[++oldStartIdx] //旧头向右走 newEndVnode = newCh[--newEndIdx] //新尾向左走 //step4 } else if (sameVnode(oldEndVnode, newStartVnode)) { //比较旧尾和新头，判断是否值得打补丁 patchVnode(...) //打补丁 //补完移动节点 canMove &amp;&amp; nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] //旧尾向左走 newStartVnode = newCh[++newStartIdx] //新头向右走 }</pre><div class="contentsignin">로그인 후 복사</div></div></li></ul>패칭할 가치가 있다면 <code>patchVNode 함수를 입력하세요

patchVNode

소스 코드 주소: patchVNode function
이 함수는 좀 길어요

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}  //初始化一个对象
  for (i = beginIdx; i <= endIdx; ++i) { //从头到尾
    key = children[i].key  //提取每一项的key
    if (isDef(key)) map[key] = i  //key不为空的时候，存入对象，键为key，值为下标
  }
  return map  //返回对象
}
//所以该函数的作用其实就是生成了一个节点的键为key，值为下标的一个表

로그인 후 복사

로그인 후 복사

여기서 판단이 많아 순서도도 추가했습니다



updateChildren ( diff 알고리즘 구현)

소스 코드 주소: updateChildren 함수

이것은 4단계 프로세스를 통해 코드를 분할했습니다

🎜

🎜Initialization🎜🎜🎜🎜사용된 4개의 포인터는 각각 4개의 노드를 가리킵니다🎜🎜oldStartIdx, newStartIdx는 이전 노드 헤드, 새 노드 헤드를 가리키고, 초기 값은 0🎜🎜oldEndIdx이고, newEndIdx는 이전 노드 테일, 새 노드를 가리킵니다. tail, 초기 값은 길이-1🎜🎜🎜🎜

  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  //判断是否有值得打补丁的节点，有则返回
    }
  }

로그인 후 복사

로그인 후 복사

🎜🎜🎜🎜🎜4가지 비교 - 루프에서🎜🎜🎜🎜old head와 new head🎜🎜old tail과 new tail🎜🎜old head와 new tail🎜🎜old tail and new head🎜🎜🎜🎜참고: 여기서만 하나 맞힐 수 있으면 그냥 🎜다시 시작🎜 하면 됩니다. 계속 하나씩 판단하지 말고 다음 링크로 가세요🎜🎜🎜

 let oldKeyToIdx, idxInOld, vnodeToMove, refElm；
 ....
else {
        if (isUndef(oldKeyToIdx))
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) //传入的是旧节点孩子，所以生成了一个旧节点孩子的key表
          //使用三目运算符--- 这里也是要使用key的原因，key有效的话可以通过表获取，无效的话则得进行比遍历比较
        idxInOld = isDef(newStartVnode.key)  //判断新头结点的key是否不为空--是否有效
          ? oldKeyToIdx[newStartVnode.key]  //不为空的的话就到key表寻找该key值对象的旧节点的下标
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) //遍历寻找旧节点数组中是否有和新头结点值得打补丁的节点，有的话则赋值其下标给idxInOld（不通过key）
        if (isUndef(idxInOld)) {  //发现找不到了就直接创建新真实节点
          createElm(...)
        } else { //找到了
          vnodeToMove = oldCh[idxInOld] //找到该下标对应的节点
          if (sameVnode(vnodeToMove, newStartVnode)) { //进行一个比较判断是否值得打补丁
            patchVnode(...) //打补丁 
            oldCh[idxInOld] = undefined  //置空，下次生成表就不会把它加进去
            canMove &&nodeOps.insertBefore( parentElm, vnodeToMove.elm,oldStartVnode.elm ) //移动节点
          } else {
          //不值得打补丁，创建节点
            createElm(...)
          }
        }
        newStartVnode = newCh[++newStartIdx]  //新头指针向前一步走
      }
    } //--- while循环到这里

로그인 후 복사

로그인 후 복사

🎜연습하세요. , 위의 임의의 예를 선택하세요🎜🎜🎜step1, step2🎜🎜 🎜🎜🎜🎜🎜🎜step3, 🎜step4 (hit)🎜🎜🎜🎜🎜🎜🎜

• 在step4进行处理，移动节点到正确位置（插在旧头的前面）
• 旧尾向左走，新头向右走
• 处理完后就重开，从step1开始，到step2再次命中，此时oldEndInx和newEndInx齐头并进向左走(注意这里是不用去移动节点的哦)（左）， 然后重开，在step2再次命中...（右）



• 重开， 这次在step3命中，然后将旧头结点结点的真实节点插在旧尾结点的后面，到这里其实真实节点就已经是我们所期望的了



• 上述处理完后，旧头向右走，新尾向左走，命中step1，新头和旧头都向左走，出现交叉情况，至此退出循环



• 通过上面这个例子，我们把四种情况都命中了一下（一开始随便画的图没想到都命中了哈哈哈），也成功通过复用节点将真实结点变为预期结果，这里便是双端diff一个核心体现了
• 但是如果四种情况都没有命中的呢(如图下)
• 则会走向我们最后一个分支，也就是后面介绍的列表寻找

列表寻找-循环中

• 先来看懂里面涉及到的createKeyToOldIdx函数
• 源码地址： createKeyToOldIdx函数

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}  //初始化一个对象
  for (i = beginIdx; i <= endIdx; ++i) { //从头到尾
    key = children[i].key  //提取每一项的key
    if (isDef(key)) map[key] = i  //key不为空的时候，存入对象，键为key，值为下标
  }
  return map  //返回对象
}
//所以该函数的作用其实就是生成了一个节点的键为key，值为下标的一个表

로그인 후 복사

로그인 후 복사
• 再来看一下里面涉及到的findIdxInOld函数
• 源码地址：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  //判断是否有值得打补丁的节点，有则返回
    }
  }

로그인 후 복사

로그인 후 복사
• 进入正文

 let oldKeyToIdx, idxInOld, vnodeToMove, refElm；
 ....
else {
        if (isUndef(oldKeyToIdx))
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) //传入的是旧节点孩子，所以生成了一个旧节点孩子的key表
          //使用三目运算符--- 这里也是要使用key的原因，key有效的话可以通过表获取，无效的话则得进行比遍历比较
        idxInOld = isDef(newStartVnode.key)  //判断新头结点的key是否不为空--是否有效
          ? oldKeyToIdx[newStartVnode.key]  //不为空的的话就到key表寻找该key值对象的旧节点的下标
          : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) //遍历寻找旧节点数组中是否有和新头结点值得打补丁的节点，有的话则赋值其下标给idxInOld（不通过key）
        if (isUndef(idxInOld)) {  //发现找不到了就直接创建新真实节点
          createElm(...)
        } else { //找到了
          vnodeToMove = oldCh[idxInOld] //找到该下标对应的节点
          if (sameVnode(vnodeToMove, newStartVnode)) { //进行一个比较判断是否值得打补丁
            patchVnode(...) //打补丁 
            oldCh[idxInOld] = undefined  //置空，下次生成表就不会把它加进去
            canMove &&nodeOps.insertBefore( parentElm, vnodeToMove.elm,oldStartVnode.elm ) //移动节点
          } else {
          //不值得打补丁，创建节点
            createElm(...)
          }
        }
        newStartVnode = newCh[++newStartIdx]  //新头指针向前一步走
      }
    } //--- while循环到这里

로그인 후 복사

로그인 후 복사
• 看完源码其实可以总结一下，就是前面四个都没有命中后，就会生成旧节点孩子的key表
• 新头节点的key有效的话，就拿新头节点的key去旧节点的key表找，找不到就创建新的真实节点， 找得到的话就判断是否值得打补丁，值得的话就打补丁后复用节点，然后将该旧节点孩子值置空，不值得就创建新节点
• 新头节点的key无效的话，则去遍历旧节点数组挨个进行判断是否值得打补丁，后续跟上述一样
• 新头指针向前一步走

也使用一下上面的例子运用一下这个步骤，以下都为key有效的情况

(重新放一下图，方便看)

• 生成了一个旧节点的key表（key为键，值为下标）， 然后newStartVnode的key值为B，找到旧节点孩子该节点下标为1，则去判断是否直接打补丁，值得的话将该旧节点孩子置空再在A前面插入B



右图的表中B没有变为undefined是因为表示一开始就生成的，在下次进入循环的时候生成的表才会没有B

• 然后将新头向右走一步，然后重开，发现前四步依旧没有命中，此时新头结点为B，但是生成的旧节点表没有B，故创建新的节点，然后插入



• 新头继续向右走，重开，命中step1（如图左）， 之后新头和旧头齐头并进向右走， 此时，旧头指向的undefined（图右），直接向右走，重开



• 发现此时又都没有命中， 此时也是生成一个key表，发现找不到，于是创建新节点M插入



• 然后新头继续向前走，依旧都没有命中，通过key表去寻找,找到了D，于是移动插入，旧节点孩子的D置空，同时新头向前一步走



• 走完这一步其实就出现交叉情况了，退出循环，此时如下图，你会发现，诶，前面确实得到预期了，可是后面还有一串呢



• 别急，这就来处理

处理

    if (oldStartIdx > oldEndIdx) { //旧的交叉了，说明新增的节点可能还没加上呢
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(....) //新增
    } else if (newStartIdx > newEndIdx) {  //新的交叉了，说明旧节点多余的可能还没删掉呢
      removeVnodes(oldCh, oldStartIdx, oldEndIdx) //把后面那一段删掉
    }

로그인 후 복사
• 对于上面这个例子，就是把后面那一段，通过遍历的方式，挨个删除

到这里updateChildren函数就结束喽，自己推导一下节点的变化就会很清晰啦

（学习视频分享：编程基础视频）


위 내용은 하나의 기사로 vue2 diff 알고리즘 이해하기(그림 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!