Analyse approfondie du principe de l'algorithme diff dans vue2.x

L'algorithme diff est un algorithme efficace qui compare les nœuds d'arbre au même niveau, évitant ainsi d'avoir à rechercher et parcourir l'arbre couche par couche. Cet article vous donnera une analyse approfondie des principes de l'algorithme diff dans vue2.x. J'espère qu'il vous sera utile !

J'ai lu beaucoup d'articles sur l'analyse du code source et j'ai lu le code source au moins deux fois. Après tout, je veux toujours l'écrire moi-même comme une sorte de disque et l'étudier par moi-même. Concentrez-vous sur les commentaires et le résumé, ne vous souciez pas trop du reste, vous gagnerez plus en revoyant la démarche et les commentaires en comparant le résumé avec le code source

Mettre à jour la définition de la méthode

Une fois la fonction de rendu générée, la méthode de montage sera appelée. Le calcul Diff sera effectué lors du montage, puisqu'il n'y a pas d'ancien nœud virtuel, le nœud dom réel sera comparé pour la première fois. le nœud virtuel n'est pas un nœud natif, un nouveau sera créé pour la première fois. (Partage vidéo d'apprentissage : tutoriel vidéo 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)
    }
   ...
  }

L'algorithme diff a deux branches principales

Le corps principal sera composé de deux branches principales : les nœuds virtuels avant et arrière sont cohérents, et les nœuds virtuels avant et arrière sont incohérent

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

les nœuds virtuels avant et arrière sont incohérents

Il est divisé en trois étapes : 1. Créer un nouveau nœud, 2. Mettre à jour le nœud d'espace réservé parent, 3. Supprimer l'ancien nœud
Les deux sont différents lorsque le composant est monté pour la première fois. Plus tard, il sera jugé s'il s'agit d'un vrai dom. Il sera converti en nœud virtuel et remplacé

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)
}

Les nœuds virtuels avant et après sont cohérents

• Déterminez d'abord. si le nouveau nœud est du texte, si c'est le cas, définissez le texte directement, sinon, continuez à déterminer
• Les nouveaux et anciens nœuds ont des enfants, Comparaison approfondie (point clé)
• Le nouveau nœud a des enfants, l'ancien nœud ne le fait pas, ajoutez de nouveaux nœuds dans une boucle
• Le nouveau nœud n'a pas d'enfants, l'ancien nœud a des enfants, supprimez l'ancien nœud directement

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)
    }
  }

Comparaison entre les anciens et les nouveaux nœuds ayant des enfants

// /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)
    }
  }

Remarque

• Dans certains cas, l'index ne peut pas être utilisé pour la clé, car l'index avant et après le changement est le même lors de l'ajout d'un élément à l'en-tête, si l'index est utilisé comme clé, une erreur de mise à jour se produira. le comprendra comme Ajouter un élément à la fin (car les clés avant et après sont toutes à 0)
• Dans diverses situations de comparaison, tant que les deux sont identiques, les enfants seront comparés de manière récursive
• Dans le désordre comparaisons, le rôle de clé est grand. Sans clé, des erreurs de mise à jour se produiront et l'effet de réutilisation ne sera pas obtenu. La comparaison différentielle est
la profondeur d'abord, comparaison de même couche

Résumé

Le modèle sera mis à jour après l'algorithme différentiel lors du montage. Pour la première fois, le nœud DOM réel sera comparé au nœud virtuel généré, et le nœud virtuel généré sera stocké pour une mise à jour et une comparaison ultérieures. L'algorithme diff n'a besoin d'être divisé qu'en deux branches, les nœuds virtuels avant et arrière sont cohérents et les nœuds virtuels avant et arrière sont incohérents. Lorsque les nœuds virtuels avant et arrière sont incohérents, un nouveau nœud sera créé, l'espace réservé parent sera mis à jour et l'ancien nœud sera supprimé. Si l'ancien nœud est un nœud réel, convertissez-le en nœud virtuel, récupérez le nœud parent de l'ancien nœud et remplacez l'ancien nœud. Lorsque les nœuds virtuels avant et arrière sont cohérents, il déterminera d'abord si le nouveau nœud est du texte, et si la valeur est ajoutée directement, sinon comparera d'abord les attributs, puis déterminera si le nouveau nœud a des enfants et l'ancien nœud n'en a pas. enfants, puis ajoutez directement les nouveaux enfants du nœud. Si le nouveau nœud a des enfants, alors il sera directement ajouté si le nœud n'existe pas mais que l'ancien nœud existe, les enfants de l'ancien nœud seront supprimés. les nouveaux nœuds ont des enfants, des pointeurs doubles seront utilisés pour comparer la même couche, via une comparaison tête-à-tête, une comparaison queue-à-queue, une comparaison tête-à-queue, une comparaison queue-à-tête et hors-de- Comparaison des ordres. Jugez-les et mettez-les à jour de manière itérative en permanence pour maximiser l'utilisation des anciens nœuds. S'il y a de nouveaux nœuds redondants, ils seront ajoutés et les anciens nœuds redondants seront supprimés. Enfin, les nœuds virtuels comparés seront renvoyés et stockés. la prochaine fois Ancien nœud auquel comparer.

• Comparaison face-à-face
  Si les nouveaux et anciens éléments de démarrage se trouvent dans le même vnode, appelez récursivement la méthode patchVnode pour une comparaison approfondie, puis déplacez l'index vers l'élément suivantpatchVnode方法进行深层对比,之后移动索引至下一个元素
• 尾尾对比
  如果新旧结束元素是相同vnode,递归调用patchVnode方法进行深层对比,之后移动索引至上一个元素
• 头尾对比
  将老节点开始元素和旧节点尾元素进行对比,相同就递归调用patchVnode方法进行深层对比,之后将旧节点元素移动至最后,旧节点头指针移动到下一个,新节点的尾指针移动至上一个。例如旧:A,B,C,新:C,B,A,第一次对比将旧A移动到C后边
• 尾头对比
  将老节点尾元素和旧节点开始元素进行对比,相同就递归调用patchVnode
Tail Comparaison de bout en bout
• Si les anciens et les nouveaux éléments finaux sont dans le même vnode, récursez Appelez la méthode patchVnode pour une comparaison approfondie, puis déplacez l'index vers l'élément précédent
  
De tête à- comparaison de queue

Comparez l'élément de début de l'ancien nœud avec l'élément de queue de l'ancien nœud. Si c'est le même cas, appelez patchVnodede manière récursive > La méthode effectue une comparaison approfondie, puis déplace l'ancien élément de nœud vers la fin, se déplace le pointeur de tête de l'ancien nœud vers le suivant, et déplace le pointeur de queue du nouveau nœud vers le précédent. Par exemple, ancien : A, B, C, nouveau : C, B, A. Pour la première comparaison, déplacez l'ancien A à l'arrière de C

Comparaison de queue et de têteComparez l'élément de queue de l'ancien nœud avec le Élément de départ de l'ancien nœud. S'ils sont identiques, recurse Appelez la méthode patchVnode pour une comparaison approfondie, puis déplacez l'ancien élément de nœud vers l'avant, le pointeur de queue de l'ancien nœud vers le précédent, et le pointeur principal du nouveau nœud vers le suivant. Par exemple, ancien : A, B, C, nouveau : C, B, A, D. La première comparaison déplacera l'ancien C vers l'avant de AComparaison dans le désordre

L'ancien nœud sera généré en fonction sur la clé et l'index correspondant avant comparaison. Lors d'une comparaison dans le désordre, la clé actuelle sera utilisée pour trouver la clé de l'ancien nœud. Si elle peut être réutilisée, le nœud sera déplacé au début de l'ancien nœud et les enfants seront comparés de manière récursive. il ne peut pas être réutilisé, un nouveau sera créé et inséré dans l'ancien au début du nœud. Déplacez ensuite le nouvel index vers l'élément suivant🎜🎜🎜 (Partage de vidéos d'apprentissage : 🎜développement web front-end🎜, 🎜Vidéo de programmation de base🎜)🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!