Fahami dengan cepat algoritma perbezaan Vue2 (penjelasan grafik terperinci)

Algoritma diff ialah algoritma cekap yang membandingkan nod pokok pada tahap yang sama, mengelakkan keperluan untuk mencari dan melintasi pokok lapisan demi lapisan. Jadi berapa banyak yang anda tahu tentang algoritma diff? Artikel berikut akan memberi anda analisis mendalam tentang algoritma perbezaan vue2. Saya harap ia akan membantu anda!

Saya telah lama melihat kod sumber Vue 2 Dari menggunakan aliran hingga kini menggunakan TypeScript, saya akan membuka kod sumbernya dan melihat setiap masa, tetapi setiap kali saya hanya melihat bahagian permulaan data, iaitu peringkat beforeMount saya tidak berhati-hati tentang cara menjana VNode (Visual Dom Node, yang juga boleh dipanggil secara langsung vdom) dan. bagaimana untuk membandingkan VNode (perbezaan) semasa mengemas kini komponen Untuk penyelidikan, saya hanya tahu bahawa algoritma pembezaan berganda digunakan untuk cara permulaan dan pengakhiran dua kali ini, saya tidak pernah melihatnya. jadi saya mengambil kesempatan untuk menulis artikel untuk mengkajinya dengan teliti kali ini. Jika isinya salah, saya harap anda boleh membantu saya menunjukkannya, terima kasih banyak-banyak~

Apa itu diff?

Pada pemahaman saya, diff merujuk kepada differences, iaitu, mengira perbezaan antara kandungan lama dan baharu ; algoritma perbezaan dalam Vue dengan cepat membandingkan tatasusunan nod VNod yang baru dan lama melalui mudah dan cekap kaedah Perbezaan antara adalah supaya mengemas kini kandungan halaman dengan operasi dom yang minimum. [Cadangan berkaitan: tutorial video vuejs, pembangunan bahagian hadapan web]

Pada masa ini terdapat dua prasyarat yang diperlukan:

• Perbandingan ialah tatasusunan VNode

• Terdapat dua set tatasusunan VNode lama dan baharu

pada masa yang sama, jadi. ia biasanya hanya berlaku apabila data dikemas kini Apabila kandungan halaman perlu dikemas kini, laksanakan , iaitu renderWatcher.run().

Mengapa VNode?

Seperti yang dinyatakan di atas, apa yang dibandingkan dalam diff ialah VNode, bukan nod dom sebenar Saya percaya mengapa VNode digunakan? Sudah jelas, biar saya terangkan secara ringkas, bukan?~

Terdapat kira-kira dua sebab untuk menggunakan VNode dalam Vue:

• VNode direka sebagai pereka bentuk rangka kerja mengikut kepada keperluan rangka kerja Objek JavaScript itu sendiri mempunyai sifat yang lebih ringkas daripada nod dom sebenar dan tiada pertanyaan dom diperlukan semasa operasi, yang boleh mengoptimumkan penggunaan prestasi semasa pengiraan

• Pautan ini daripada VNode kepada dom sebenar Proses pemaparan boleh diproses secara berbeza mengikut platform yang berbeza (web, applet WeChat) untuk menjana elemen dom sebenar yang disesuaikan dengan setiap platform

Semasa proses diff, data nod lama dan baharu akan dilalui Sebagai perbandingan, menggunakan VNode boleh membawa peningkatan prestasi yang hebat.

Proses pengisihan

Dalam halaman web, nod dom sebenar wujud dalam bentuk pokok, dan nod akar semuanya , untuk memastikan bahawa nod maya adalah konsisten dengan nod dom sebenar, VNode juga menggunakan struktur pokok.

Jika semua nod VNode perlu dibandingkan apabila komponen dikemas kini, kedua-dua set nod lama dan baharu perlu dilalui secara mendalam dan dibandingkan, yang akan menyebabkan banyak overhed prestasi ; oleh itu, secara lalai dalam Vue Perbandingan nod pada tahap yang sama, iaitu Jika tahap pepohon VNode lama dan baharu adalah berbeza, kandungan tahap tambahan akan dibuat terus atau dibuang, dan hanya operasi perbezaan akan dilakukan pada tahap yang sama.

Secara amnya, operasi diff biasanya berlaku dalam v-for gelung atau objek nod yang mempunyai v-if/v-else dijana secara dinamik component seperti dan (nod statik umumnya tidak berubah, Ia adalah sangat pantas jika dibandingkan), dan proses ini adalah untuk mengemas kini dom, jadi dalam kod sumber, nama kaedah yang sepadan dengan proses ini ialah updateChildren, terletak di src/core/vdom/patch.ts. Seperti yang ditunjukkan di bawah:

Berikut ialah semakan proses penciptaan dan kemas kini contoh komponen Vue:

• Pertama daripada semua, beforeCreate Pada peringkat created, pemprosesan utama ialah data dan status serta beberapa peristiwa dan kaedah asas

• Kemudian, kaedah $mount(vm.$options.el) akan dipanggil untuk memasuki penciptaan dan pemasangan Vnode dan peringkat dom, iaitu antara beforeMount dan mounted (sama seperti di sini apabila komponen dikemas kini)

• $mount pada prototaip akan ditulis semula dalam platforms/web/runtime-with-compiler.ts, dan pelaksanaan asal adalah dalam platforms/web/runtime/index.ts dalam kaedah pelaksanaan asal, kaedah mountComponent sebenarnya dipanggil untuk dilaksanakan render; dan dalam web di bawah runtime-with-compiler, modul kompilasi rentetan templat ditambah, yang akan menghuraikan dan menyusun options dalam template dan menukarnya menjadi fungsi Bind kepada options.render dalam

• mountComponent Di dalam fungsi, mentakrifkan kaedah pemaparan updateComponent = () => (vm._update(vm._render()) dan membuat contoh before dengan konfigurasi watcher ( Iaitu, renderWatcher), dengan mentakrifkan objek pemerhatian watch sebagai kaedah updateComponent yang baru ditakrifkan untuk melaksanakan pemaparan komponen pertama dan pengumpulan kebergantungan pencetus , konfigurasi before hanya mengkonfigurasi kaedah fungsi cangkuk beforeMount/beforeUpdate pencetus ; ini juga sebab mengapa nod dom sebenar tidak boleh diperolehi dalam peringkat beforeMount dan nod dom lama diperoleh dalam peringkat beforeUpdate

• takrif kaedah dan kaedah _update > Di bawah fail yang sama, intinya ialah mountComponent membaca (nod dom lama) dan $el (VNod lama) dalam contoh komponen dan _vnode dijana oleh fungsi _render() untuk melaksanakan operasi vnodepatch

• Fungsi pertama membandingkan sama ada patch mempunyai nod lama , ia mestilah komponen baharu, yang akan dibuat dan dipaparkan secara langsung jika ia mempunyai nod lama, , kemudian bandingkan nod lama dan baharu melalui , patchVnode dan jika nod lama dan baharu adalah konsisten dan kedua-duanya mempunyai nod anak, masukkan logik teras children - diff kemas kini perbandingan nod anak updateChildren, Kaedah ini juga yang sering kita panggil Algoritma diff

Pra-Kandungan

lwn. : , kaedah menambah nod sameNode(a, b), kaedah mengalih keluar nod addVnodes Sudah tentu, walaupun selepas removeVnodes menilai bahawa VNod adalah konsisten, ia akan tetap digunakan sameNode Menjalankan perbandingan mendalam kandungan sesuatu. tunggal VNode lama dan baharu untuk mengesahkan sama ada data dalaman perlu dikemas kini. patchVnode

sameNode(a, b)

Bandingkan sama ada nod lama dan baharu adalah sama.

a dan b adalah sama Inilah sebabnya Vue menyatakan dalam dokumen bahawa nod dinamik seperti key mesti ditetapkan v-for、v-if、v-else. untuk mengenal pasti keunikan, jika key wujud dan sama, anda hanya perlu membandingkan sama ada perubahan dalaman telah berlaku, yang secara amnya boleh mengurangkan banyak operasi DOM jika ia tidak ditetapkan, elemen nod yang sepadan akan; langsung dimusnahkan dan dibina semula. key

Komponen bukan tak segerak: label adalah sama, begitu juga nod anotasi, kedua-duanya mempunyai data dan jenis yang sama kotak input teks
• Komponen tak segerak: Gesaan ralat untuk pemegang tempat nod lama dan nod baharu adalah kedua-duanya
• undefined

addVnodes

elemen induk tatasusunan nod semasa, elemen parentElm pada kedudukan yang ditentukan, refElm vnodes tatasusunan nod maya baharu , baharu nod Kedudukan permulaan elemen yang dimasukkan tatasusunan, startIdx indeks akhir elemen yang dimasukkan tatasusunan nod baharu, endIdx baris gilir nod maya yang akan dimasukkan. Fungsi insertedVnodeQueue

merentasi tatasusunan bermula dari startIdx hingga vnodes kedudukan endIdx, dan kemudian panggil untuk mencipta dan memasukkan createElm yang sepadan sebelum refElm pula elemen. vnodes[idx]

komponen dalam vnodes[idx] ini dan Component juga akan dipanggil untuk mencipta contoh komponen yang sepadan. createComponent

Oleh kerana keseluruhan VNode dan dom adalah struktur pokok, jadi selepas perbandingan pada tahap yang sama, pemprosesan VNode dan dom yang lebih mendalam di bawah tahap semasa perlu diproses .

removeVnodes

Bertentangan dengan addVnodes, kaedah ini digunakan untuk mengalih keluar nod VNode.

Memandangkan kaedah ini hanya mengalih keluar, ia hanya memerlukan tiga parameter: vnodes Tatasusunan nod maya lama , startIdx indeks mula, endIdx indeks penamat. Fungsi

secara dalaman akan merentasi tatasusunan startIdx bermula dari vnodes sehingga kedudukan endIdx Jika vnodes[idx] bukan undefined, ia akan berdasarkan Atribut tag. Pemprosesan terbilang:

• wujud tag, menunjukkan bahawa ia adalah elemen atau komponen dan kandungan perlu vnodes[idx] diproses secara rekursif , mencetuskan remove hooks 与 destroy hooks
• tidak tag wujud, menunjukkan bahawa ia ialah nod teks biasa Anda boleh terus mengalih keluar nod daripada dom

patchVnode

Kaedah perbandingan lengkap sebenar dan kemas kini dom untuk perbandingan nod.

Dalam kaedah ini, ia terutamanya termasuk sembilan pertimbangan parameter utama, dan sepadan dengan logik pemprosesan yang berbeza:

• VNod lama dan baharu adalah kongruen , Ini bermakna tiada perubahan, Keluar terus

• Jika VNode baharu mempunyai pengikatan dom sebenar dan set nod yang perlu dikemas kini ialah tatasusunan, salin VNode semasa ke kedudukan koleksi yang ditentukan

• Jika nod lama ialah komponen tak segerak dan belum selesai dimuatkan, keluar terus , jika tidak, nod yang baharu akan melalui fungsi hydrate VNode ditukar menjadi dom sebenar untuk pemaparan; dalam kedua-dua kes, keluar dari fungsi

• jika yang lama dan baharu nod ialah kedua-duanya nod statik dan key adalah sama, atau jika nod yang ditentukan oleh isOnce tidak dikemas kini, ia akan terus menggunakan semula contoh komponen nod lama dan keluar daripada fungsi

• Jika nod VNode baharu mempunyai atribut data dan dikonfigurasikan dengan fungsi cangkuk prepatch, laksanakan pemberitahuan prepatch(oldVnode, vnode) untuk masuk fasa perbandingan nod. Secara amnya, langkah ini akan mengkonfigurasi pengoptimuman prestasi

• Jika VNode baharu mempunyai atribut data dan secara rekursif menukar vnod contoh subkomponen nod, jika label masih tersedia, fungsi cangkuk cbs dikonfigurasikan dalam objek fungsi panggil balik dan update dikonfigurasikan dalam fungsi data 🎜> Cangkuk update

• Jika yang baharu VNode bukan nod teks, ia akan memasuki peringkat perbandingan teras :

  Jika kedua-dua nod lama dan baru adalah Jika terdapat
  • nod anak, masukkan children kaedah untuk membandingkan nod anak updateChildren
  Jika nod lama tidak mempunyai nod anak, buat terus nod anak baharu yang sepadan dengan VNode
  • Jika nod baharu tidak Jika ada nod anak, alih keluar nod anak VNode lama
  • Jika tiada nod anak dan nod lama mempunyai konfigurasi kandungan teks, kosongkan teks
  • sebelumnya text
• Jika VNode baharu mempunyai teks

  (ia adalah nod teks), bandingkan kandungan teks nod lama dan baharu untuk melihat sama ada ia konsisten, jika tidak, kemas kini kandungan teks text

• Akhir sekali Panggil fungsi cangkuk

  yang dikonfigurasikan dalam data nod baharu untuk memberitahu nod bahawa kemas kini telah selesai postpatch

dilakukan dalam fasa kemas kini nod yang sama sebagai patchVnode Bandingkan kandungan baharu dengan kandungan lama, dan kemas kini kandungan yang sepadan jika terdapat perubahan jika terdapat nod anak, lakukan perbandingan dan kemas kini setiap nod anak "secara rekursif" .

perbandingan dan kemas kini tatasusunan nod anak ialah logik teras perbezaan dan juga merupakan salah satu soalan yang sering disebut semasa temu bual.

~updateChildren

analisis teras berbezaupdateChildren

Bandingkan perbezaan elemen dua tatasusunan objek berdasarkan tatasusunan baharu Apakah kaedahnya?

melalui brute force bermaksud untuk mencari susunan dan perbezaan setiap elemen dalam tatasusunan, iaitu algoritma beza mudah .

merentasi tatasusunan nod baharu, merentasi tatasusunan nod lama sekali lagi dalam setiap kitaran untuk membandingkan sama ada kedua-dua nod itu konsisten dan menentukan sama ada nod baharu itu ditambah, dialih keluar atau dialihkan melalui hasil perbandingan Keseluruhan proses memerlukan m*n perbandingan, jadi kerumitan masa lalai adalah Hidup.

Kaedah perbandingan ini sangat intensif prestasi semasa sejumlah besar kemas kini nod, jadi Vue 2 mengoptimumkannya dan menukarnya kepada 双端对比算法, iaitu 双端 diff.

Algoritma pembezaan dua hujung

Seperti namanya, berakhir dua bermaksud bermula dari kedua-dua hujung dan melintasi ke tengah untuk perbandingan algoritma.

Dalam 双端 diff, ia dibahagikan kepada lima situasi perbandingan:

• Kepala lama dan baharu adalah sama

• Ekor lama dan baru adalah sama

• Kepala lama sama dengan ekor baru

• Ekor lama ialah sama dengan kepala baru

• Empat tidak sama antara satu sama lain

Antaranya, empat yang pertama adalah situasi ideal, manakala yang kelima ialah situasi perbandingan yang paling rumit.

dinilai sama, iaitu sameVnode(a, b) sama dengan true

Mari kita analisanya melalui situasi pratetap.

1. Pratetap keadaan nod baharu dan lama

Untuk menunjukkan lima situasi di atas pada masa yang sama, saya pratetap tatasusunan nod baharu dan lama berikut:

• Sebagai tatasusunan nod lamaoldChildren dalam susunan nod awal, ia mengandungi 7 nod daripada 1 hingga 7 secara keseluruhan
• Sebagai tatasusunan nod baharunewChildren selepas dikocok, ia juga mempunyai 7 nod, tetapi dibandingkan dengan Nod lama dikurangkan dengan satu vnode 3 dan satu ditambah vnode 8

Sebelum membuat perbandingan, anda perlu mentakrifkan indeks dua hujung. daripada dua set nod:

let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

menyalin kod sumber, dengan oldCh ialah oldChildren dalam gambar dan newCh ialah newChildren

Kemudian, kami mentakrifkan perbandingan traversal Keadaan berhenti operasi :

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

Keadaan berhenti di sini ialah Asalkan sama ada nod lama atau baru traversal tatasusunan tamat, traversal akan berhenti serta-merta .

Status nod pada masa ini adalah seperti berikut:

2. Sahkan bahawa vnod wujud sebelum membandingkan

Untuk memastikan tatasusunan nod lama dan baharu tidak akan melakukan perbandingan yang tidak sah semasa perbandingan, dan akan mengecualikan data dahulu di mana bahagian permulaan dan akhir tatasusunan nod lama Undefined adalah berterusan dan mempunyai nilai .

if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[--oldEndIdx]

Sudah tentu ini tidak berlaku dalam contoh kita dan boleh diabaikan.

3. Kepala lama adalah sama dengan kepala baru

Pada masa ini, ia bersamaan dengan dua indeks permulaan nod lama dan baru tatasusunan. Nod yang ditunjuk oleh ialah Pada asasnya konsisten , kemudian patchVnode akan dipanggil untuk melakukan perbandingan mendalam dan kemas kini dom bagi dua vnod, dan dua indeks permulaan akan menjadi bergerak ke belakang . Iaitu:

if (sameVnode(oldStartVnode, newStartVnode)) {
  patchVnode(
    oldStartVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

Perubahan nod dan indeks pada masa ini adalah seperti yang ditunjukkan dalam rajah:

4 adalah sama dengan ekor baharu

adalah serupa dengan kesamaan nod kepala , juga dipanggil untuk membandingkan dua nod ekor dan mengemas kini dom , kemudian menggerakkan dua indeks hujung ke hadapan patchVnode.

if (sameVnode(oldEndVnode, newEndVnode)) {
  patchVnode(
    oldEndVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

Maksudnya ialah

, dan dipanggil dengan cara yang sama untuk memproses dua nod. patchVnodeTetapi perbezaan daripada kedua-dua di atas ialah dalam kes ini, nod

, jadi pada masa ini ia masih akan menjadi selepas tamat. Masukkan semula patchVnode nod kepala lama ke dalam nodeOps.insertBefore selepas nod ekor lama semasa melalui . Kemudian, indeks permulaan

.

tatasusunan nod lama

dialihkan ke sini kerana terdapat atribut dalam nod vnod, yang mana akan menunjuk ke Nod dom sebenar yang sepadan dengan vnod, jadi menggerakkan tatasusunan nod lama di sini sebenarnya mengalihkan urutan nod dom sebenar elm dan ambil perhatian bahawa ini ialah nod ekor semasa indeks ditukar, tidak ada Ia mestilah terakhir tatasusunan nod asal.

即：

if (sameVnode(oldStartVnode, newEndVnode)) {
  patchVnode(
    oldStartVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}

此时状态如下：

6. 旧尾等于新头

这里与上面的 旧头等于新尾 类似，一样要涉及到节点对比和移动，只是调整的索引不同。此时 旧节点的 末尾索引 前移、新节点的 起始索引 后移，当然了，这里的 dom 移动对应的 vnode 操作是 将旧节点数组的末尾索引对应的 vnode 插入到旧节点数组 起始索引对应的 vnode 之前。

if (sameVnode(oldEndVnode, newStartVnode)) {
  patchVnode(
    oldEndVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}

此时状态如下：

7. 四者均不相等

在以上情况都处理之后，就来到了四个节点互相都不相等的情况，这种情况也是 最复杂的情况。

当经过了上面几种处理之后，此时的 索引与对应的 vnode 状态如下：

可以看到四个索引对应的 vnode 分别是：vnode 3、vnode 5、 vnode 4、vnode 8，这几个肯定是不一样的。

此时也就意味着 双端对比结束。

后面的节点对比则是 将旧节点数组剩余的 vnode （oldStartIdx 到 oldEndIdx 之间的节点）进行一次遍历，生成由 vnode.key 作为键，idx 索引作为值的对象 oldKeyToIdx，然后 遍历新节点数组的剩余 vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的 key 在 oldKeyToIdx 进行查找。此时的每个新节点的查找结果只有两种情况：

• 找到了对应的索引，那么会通过 sameVNode 对两个节点进行对比：

  • 相同节点，调用 patchVnode 进行深层对比和 dom 更新，将 oldKeyToIdx 中对应的索引 idxInOld 对应的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将 旧节点数组中 idxInOld 对应的元素设置为 undefined
  • 不同节点，则调用 createElm 重新创建一个新的 dom 节点并将 新的 vnode 插入到对应的位置

• 没有找到对应的索引，则直接 createElm 创建新的 dom 节点并将新的 vnode 插入到对应位置

注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中 idxInOld 中的元素置为 undefined。

最后，会将 新节点数组的 起始索引 向后移动。

if (isUndef(oldKeyToIdx)) {
    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  }
  idxInOld = isDef(newStartVnode.key)
    ? oldKeyToIdx[newStartVnode.key]
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
  if (isUndef(idxInOld)) {
    // New element
    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 {
      // same key but different element. treat as new element
      createElm(
        newStartVnode,
        insertedVnodeQueue,
        parentElm,
        oldStartVnode.elm,
        false,
        newCh,
        newStartIdx
      )
    }
  }
  newStartVnode = newCh[++newStartIdx]
}

大致逻辑如下图：