「ソースコード解析」仮想DOMアルゴリズムの実装方法

[[378869]]

前回の記事「仮想 DOM が実際の DOM に進化する方法」では、仮想 DOM ツリーを実際の DOM に変換してページにレンダリングする方法について説明しました。ただし、レンダリング プロセス中に、新しい仮想 DOM ツリーを実際の DOM に直接変換して、古い DOM 構造を置き換えます。実際の DOM の状態またはコンテンツが変更された場合、新しい仮想 DOM ツリーを再レンダリングして古いものを置き換えることは非常に無力になります。 DOM 構造全体の中の小さなデータや句読点だけを変更するシナリオ、あるいはデータ量が非常に大きい場合に、古い DOM 構造全体を置き換える必要があり、コンピューターのパフォーマンスが無駄になるシナリオを想像してみてください。

したがって、更新中に新しくレンダリングされた仮想 DOM ツリーと古い仮想 DOM ツリーを比較し、2 つのツリー間の違いを記録することが望まれます。記録される違いは、ページ上で実際の DOM 操作を実行し、それを実際の DOM 構造でレンダリングする必要があり、それに応じてページが変更される点です。これにより、ビュー全体の構造が最新の状態にレンダリングされたように見えますが、最終的に DOM 構造を操作すると、元の構造との差分のみが変更されるという効果が得られます。

つまり、仮想 DOM 差分アルゴリズムの主な考え方は次のとおりです。

1. 仮想 DOM 構造を実際の DOM 構造に変換し、古い DOM (最初は古いものは未定義) に置き換えて、ページにレンダリングします。

2. 状態が変化すると、新しい仮想 DOM ツリーがレンダリングされ、古い仮想 DOM ツリーと比較され、比較後に差異が記録されます。

3. 最終的な差異部分は実際の DOM 構造に変換され、ページ上にレンダリングされます。

成し遂げる

古い仮想ノードと新しい仮想ノードの比較中に、次の状況が発生する可能性があります。Vue を例に、Vue2.0 で Diff アルゴリズムがどのように実装されているかを見てみましょう。

2つの要素のラベルを比較する

タグが異なる場合は、直接置き換えてください。例: div は p になります。

 div->p 
 
 <<<<<<<<ヘッド
<p>フロントエンドブリーフィング</p> 
 
 ========= 
 
 <div>フロントエンドの説明</div>
 >>>>>>>>

仮想ノードのタグ属性が等しいかどうかを判断します。等しくない場合は、新しい仮想 DOM ツリーを実際の DOM 構造に変換し、元のノードを置き換えます。

 (oldVnode.tag != vnode.tag) の場合 {
 oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el)を返します。
 }

効果画像:

2つの要素のテキストを比較します

タグが同じ場合は、テキストが同じかどうかを比較します。テキストが異なる場合は、テキストの内容を置き換えるだけです。

 <<<<<<<<ヘッド
<div>フロントエンド</div>
 =========
 <div>ニュースレター</div>
 >>>>>>>>

両ノードのタグはdivなので、子の仮想DOMツリーが同じかどうかを比較します。子タグは未定義なので、テキストノードであることを意味します。この時点で、テキストコンテンツが一貫しているかどうかを比較できます。

 if (!oldVnode.tag) {
    //テキスト比較
    (oldVnode.text != vnode.text) の場合 {
戻り値(oldVnode.el.textContent = vnode.text);
    }
  }

効果画像:

タグ属性の比較

2 つのタグが同じ場合は、タグの属性を比較します。属性が更新されると、新しい属性と古い属性を比較することで、次の状況が発生する可能性があります。

1. 属性の比較

古い仮想ノードに属性があり、新しい仮想ノードにない場合は、古い仮想ノードの属性を削除する必要があります。

 let newProps = vnode.data || {}; //新しいプロパティ
el = vnode.el とします。
 // 古いものにはありますが、新しいものにはありません。属性を削除する必要があります。
 for (letキー  oldProps内）{
  if (!newProps[キー]) {
    el.removeAttribute( key ); //実際のDOM属性を削除します
  }
 }

逆に、古い仮想ノードには属性がなく、新しい仮想ノードには属性がある場合は、新しい属性を設定するだけです。

 // 新しいものがある場合は、新しいものに更新するだけです
for (letキー  newProps内）{
    el.setAttribute(キー, newProps[キー] );
 }

• 対応するソースコード アドレス: src\platforms\web\runtime\modules\attrs.js

2. スタイル処理

新しいスタイルが古いスタイル内に存在する場合は、古いスタイルを削除します。

 - スタイル={色:赤}
 + スタイル = {背景:赤}

 newStyle を newProps.style とします || {};
 oldStyle を oldProps.style とします || {};
 // 古いスタイルにはありますが、新しいスタイルにはありません。古いスタイルを削除します。
 for (letキー 旧スタイル）{
  if (!newStyle[キー]) {
    el.style[キー] = "" ;
  }
 }

逆に、古いスタイルが存在せず、新しいスタイルが存在する場合は、新しいスタイルを直接更新するだけです。

 for (letキー  newProps内）{
  if (キー== "スタイル " ) {
 for (let styleName in newProps.style) {
      el.style[スタイル名] = newProps.style[スタイル名];
    }
  }
 }

• 対応するソースコード アドレス: src\platforms\web\runtime\modules\style.js

3. クラス名の処理

クラス名の処理には、新しいノードのクラス名を使用します。

 - クラス = "タイトル ant-title"  
 + クラス = "タイトル ant-mian-title"  

 for (letキー  newProps内）{
 if (キー== "クラス " ) {
    el.className = newProps.class;
 }

• 対応するソースコードアドレスは src\platforms\web\runtime\modules\class.js です。

息子の比較

息子を比較する過程では、次のような状況に分けられます。

1. 古いノードには息子がいますが、新しいノードには息子がいません。古いノードの息子を削除するだけです。

 if (isDef(oldCh)) {
  Vnodesを削除します(oldCh, 0, oldCh.length - 1)
 }
 =========================================
 (oldChildren.length > 0) の場合 {
     el.innerHTML = "" ;
 }

2. 古いノードには子がなく、新しいノードには子があります。子を走査して実際の DOM 構造に変換し、ページに追加します。

 if (isDef(ch)) {
  if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '' )
  addVnodes(elm, null , ch, 0, ch.length - 1, 挿入されたVnodeQueue)
 }
 ===============================================================
 (newChildren.length > 0) の場合 {
 ( i = 0 とします; i < newChildren.length; i++) {
     子をnewChildren[i]とします。
     el.appendChild(Elm(child) を作成します);
  }
 }

3. 古いノードには息子がおり、新しいノードにも息子がいる

古いノードの子と新しいノードの子の両方が存在し、それらが等しくない場合、この状況はさらに複雑になり、diff アルゴリズムの中核にもなります。

vue2.0 では、古いノードと新しいノードを比較するためにダブルポインター方式が使用されています。古いノードと新しいノードは同時に同じ方向にループされます。1 つのノードのループが完了すると、ループは終了します。古いノードが先に終了した場合は、新しいノードの残りの要素をレンダリング リストに追加します。新しいノードが先に終了した場合は、古いノードの残りの要素を削除します。

古いノードの開始位置と終了位置、および新しいノードの開始位置と終了位置を含む開始ポインターを定義します。

 let oldStartIndex = 0; //古いインデックス
 let oldStartVnode = oldChildren[0]; //古いインデックスが指すノード
 oldEndIndex = oldChildren.length - 1 とします。
 oldEndVnode = oldChildren[oldEndIndex]とします。 
 
 let newStartIndex = 0; //新しいインデックス
 let newStartVnode = newChildren[0]; //新しいインデックスが指すノード
 newEndIndex = newChildren.length - 1 とします。
 newEndVnode = newChildren[newEndIndex]とします。

2つのノードのキーとタグが等しいかどうかを判断して同じ要素を判別する

関数sameVnode(a, b) {
戻る（
    a.キー=== b.キー&& (
      （
        a.タグ === b.タグ &&
        ...
      ) || (
        ...
      ）
    ）
  ）
 }

肯定的な順序で並べる

追加ノードが右側にある場合は、左から右に、古い開始ノードと新しい開始ノードが同じノードであるかどうかを判断します。同じノードである場合は、patchVode メソッドを呼び出して子ノードを再帰的に返し、古いノードと新しいノードの添字に 1 を追加して、添字が子の長さよりも大きくなるまで右に移動します。

同じVnodeの場合(古い開始Vnode、新しい開始Vnode)) {
  パッチVnode(古い開始Vnode、新しい開始Vnode、挿入されたVnodeQueue、新しいCh、新しい開始Idx)
  古い開始Vノード = 古いCh[++古い開始Idx]
  新しい開始Vノード = 新しいCh[++新しい開始Idx]
 }

効果画像:

上図のように、レンダリング ビューに新しいノードが過剰に追加された場合、左から右に比較すると、g ノードの次の el は null になり、insertBefore は appendChild メソッドを使用して後方に挿入することと同等になります。右から左の場合、g ノードの次の el は a になり、insertBefore を使用することは a の前にノードを挿入することと同等になります。

 if (古い開始インデックス > 古い終了インデックス) {
 (i = newStartIndex; i <= newEndIndex; i++)の場合{
      ele = とする
        新しい子[新しい終了インデックス + 1] == null  
          ?ヌル 
          : newChildren[newEndIndex + 1].el;
      親要素をcreateElm(newChildren[i]), eleの前に挿入します。
    }
 }

古いノードが冗長である場合、これらのノードは不要であり、削除できることを意味します。削除プロセス中に null が表示される場合、ノードは処理済みであり、スキップできることを意味します。

 (新しい開始ID > 新しい終了ID) の場合 {
 (i = oldStartIndex; i <= oldEndIndex; i++)の場合{
     子を oldChildren[i] とします。
     if (child!= undefined) {
       親要素を削除します。
     }
  }
 }

追加ノードが左側にある場合、新しいノードと古いノードの終了ノードから始まって、添え字が 1 ずつ減ります。

同じVnodeの場合(古いEndVnode、新しいEndVnode) {
  パッチVnode(古い終了Vnode、新しい終了Vnode、挿入されたVnodeQueue、新しいCh、新しい終了Idx)
  oldEndVnode = oldCh[ --oldEndIdx]  
  newEndVnode = newCh[ --newEndIdx]  
 }

順序を逆にする

新しいノードと古いノードが逆になっている場合は、古いノードの開始ノードを新しいノードの終了ノードと比較するか、古いノードと終了ノードを新しいノードの開始ノードと比較します。

古いノードの開始ノードと新しいノードの終了ノードが同じノードである場合、古い終了ノードの次のノードの前に古い開始ノードを挿入し、ノードの対応する添字をそれぞれ右と左に移動し、対応する値を取得してトラバーサルを続行します。

 if (sameVnode(oldStartVnode, newEndVnode)) { // Vnodeが右に移動しました 
  パッチVnode(古い開始Vnode、新しい終了Vnode、挿入されたVnodeQueue、新しいCh、新しい終了Idx)
  canMove && nodeOps.insertBefore(親Elm、oldStartVnode.elm、nodeOps.nextSibling(oldEndVnode.elm))
  古い開始Vノード = 古いCh[++古い開始Idx]
  newEndVnode = newCh[ --newEndIdx]  
 }

古いノードの終了ノードと新しいノードの開始ノードが同じノードである場合、古いノードの終了ノードを古いノードの開始ノードの前に挿入し、ノードの対応する添字をそれぞれ左と右に移動し、対応する値を取得してトラバーサルを続行します。

 if (sameVnode(oldEndVnode, newStartVnode)) { // Vnodeが左に移動しました 
  パッチVnode(古い終了Vnode、新しい開始Vnode、挿入されたVnodeQueue、新しいCh、新しい開始Idx)
  canMove && nodeOps.insertBefore(親Elm、古い終了Vnode.elm、古い開始Vnode.elm)
  oldEndVnode = oldCh[ --oldEndIdx]  
  新しい開始Vノード = 新しいCh[++新しい開始Idx]
 }

関係なし

比較処理中に子ノード間に関係がない場合は、新しいノードの開始ノードから始めて、古いノードのすべてのノードと順番に比較します。同じものがない場合は、新しいノードを作成し、古いノードの開始ノードの前に挿入します。ループ中に同じ要素が見つかった場合は、古い要素を直接再利用し、新しいノードと同じ古いノードを古いノードの開始ノードの前に挿入します。配列の崩壊を防ぐために、削除された古いノードの位置を未定義に設定し、最後に冗長な古いノードをすべて削除します。

キャッシュ グループを設定して、古いノードのキーとインデックスを使用してマッピング テーブルを作成します。新しいノードのキーは、古いマッピング テーブルでフィルタリングされます。見つからない場合は再利用されず、新しいノードが作成され、古いノードの開始ノードの前に挿入されます。

関数createKeyToOldIdx（子）{
  let i、キー 
  定数マップ = {}
   children.forEach((item, index ) => {
      if (isDef（ item.key ）) {
        map[ item.key ] = index ; //{a:0,b:1,c:2,d:3,e:4,f:5,g:6}
      }
戻る地図
}

古いノードで見つかった場合は、古いノードを古いノードの開始ノードの前に移動

マップをcreateKeyToOldIdx(oldChildren)にします。
 //息子たちの間には関係はない
let moveIndex = map[newStartVnode. key ]; //最初の仮想ノードのキーを取得し、古いものを検索します
 
移動インデックス == 未定義の場合{
  親.insertBefore(createElm(newStartVnode),oldStartVnode.el);
 }それ以外{
  let moveVNode = oldChildren[moveIndex]; //この古い仮想ノードを移動する必要がある
  oldChildren[moveIndex] = null ;
  親.insertBefore(moveVNode.el、oldStartVnode.el);
  patch(moveVNode,newStartVnode) //プロパティをsonと比較する
}
 newStartVnode = newChildren[++newStartIndex] //新しいものを使用して古いものを検索し続けます

移動処理中、開始ポインターと終了ポインターが null を指している可能性があります。これらが null を指している場合は比較が行えず、ポインターをスキップして次の要素を指すことができます。

 if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx] // Vnodeが左に移動されました 
 }そうでない場合 (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[ --oldEndIdx]  
 }

ソースコードアドレス: src/core/vdom/patch.js

なぜキーを使用するのですか?

私は醜いので多くは語りません、まずは写真を見てみましょう

キー付き

キーなし

上図に示すように、最初の図はキーがある場合、2 番目の図はキーがない場合を示しています。表示されるコンテンツにキーがある場合、キー A、B、C、D を持つ 4 つのノードが再利用されることが明確にわかります。その結果、新しく作成された E ノードが C ノードの前に挿入されるだけで、レンダリングが完了します。キーがない場合、3 つのノード E、C、D が作成され、再利用率が低下し、パフォーマンスはキーがある場合ほど高くなりません。

なぜインデックスをキーとして使用できないのですか?

通常の開発プロセスでは、ページの静的レンダリングのみを使用する場合は、インデックスをキーとして使用できます。ページに複雑な論理的な変更がある場合、インデックスをキーとして使用することは、キーがないのと同じです。

 <li index =0>あ</li> <li index =0>こ</li>
 <li index =1>B</li> <li index =1>B</li>
 <li index =2>C</li> <li index =2>A</li>

上記のコードに示すように、添え字 0 と 2 で A と C の位置を変更した後、ノード A と C を再作成する必要があります。このとき、C の添え字は 0 で、A の添え字は 2 です。 id または一意の識別子をキーとして使用することは、要素 A と C の位置をシフトすることと同じです。翻訳のパフォーマンスはノード作成のパフォーマンスよりも高くなります。

インデックスをキーとして使用すると、予期しない問題が発生する可能性があります。ノード B を削除すると、初期値は B ですが、C になります。

要約する

Vue2.0 の diff アルゴリズム pathVode メソッドの基本的な考え方は、次のようにまとめることができます。

1. oldVode と newVode が同じオブジェクトであるかどうかを判断します。同じ場合は、直接戻ります。 2. 実際の DOM を el として定義します。

3. oldVode と newVode の両方にテキスト ノードがあり、それらが等しくない場合は、oldVode のテキスト ノードを newVode のテキスト ノードに設定します。

4. oldVode に子ノードがあり、newVode にない場合は、子ノードを削除します。

5. oldVode に子ノードがない場合、newVode には子ノードがあります。次に、子ノードを実際の DOM に変換し、el に追加します。 6. 両方に子ノードがある場合は、updateChildren関数を実行して子ノードを比較します。

上記は、Vue レンダリング プロセス全体のパフォーマンスに重要な役割を果たす Diff アルゴリズムのプロセス全体です。