Detaillierte Analyse des Diff-Algorithmus in React

Verständnis des Diff-Algorithmus in React

diff -Algorithmus wird verwendet, um den geänderten Teil Virtual DOM zu berechnen und dann DOM -Operationen an diesem Teil durchzuführen, ohne die gesamte Seite erneut darzustellen. Das Rendern der gesamten DOM Struktur ist sehr aufwändig und der Browser muss DOM Struktur neu zeichnen und neu umfließen. Der diff Algorithmus kann während der Operation nur den geänderten Teil DOM Struktur aktualisieren, ohne das gesamte DOM zu aktualisieren. Dadurch können die Operationen an DOM Struktur minimiert und der Umfang des Neuzeichnens und Umfließens durch den Browser minimiert werden.

Virtueller DOM

Die Grundlage des diff -Algorithmus ist Virtual DOM . Virtual DOM ist ein Baum, der auf JavaScript Objekten basiert. In React wird es normalerweise über JSX kompiliert. Jeder Knoten wird VNode genannt und der Knoten wird durch Objekteigenschaften beschrieben. Tatsächlich ist es eine Abstraktion des realen DOM . Letztendlich kann dieser Baum durch Rendering-Operationen auf die reale Umgebung abgebildet werden. Einfach ausgedrückt ist Virtual DOM ein Js Objekt, das das gesamte Dokument beschreibt.
Wenn Sie eine Seite in einem Browser erstellen, müssen Sie DOM Knoten verwenden, um das gesamte Dokument zu beschreiben.

<div Klasse="Wurzel" Name="Wurzel">
    <p>1</p>
    <div>11</div>
</div>

Wenn Sie Js Objekte verwenden, um die oben genannten Knoten und Dokumente zu beschreiben, sieht es wie folgt aus. Dies ist natürlich nicht das Objekt, das zum Beschreiben von Knoten in React verwendet wird. Der Quellcode zum Erstellen eines React Elements in React befindet sich in react/src/ReactElement.js . Die React Version in diesem Artikel ist 16.10.2 .

{
    Typ: "div",
    Requisiten: {
        Klassenname: "root"
        Name: "root",
        Kinder: [{
            Typ: "p",
            Requisiten: {
                Kinder: [{
                    Typ: "Text",
                    Requisiten: {
                        Text 1"
                    }
                    
                }]
            }    
        },{
            Typ: "div",
            Requisiten: {
                Kinder: [{
                    Typ: "Text",
                    Requisiten: {
                        Text: "11"
                    }
                }]
            }
        }]
    }
}

Tatsächlich ist requestIdleCallback neue Fiber in React16 VDOM . Das größte Problem Fiber Fiber 16 Fiber React16 dass DOM nicht diff + patch diff Mount . DOM DOM Fiber VDOM . Fiber führt in diff Phase die folgenden Vorgänge aus, was tatsächlich der Durchführung der Steuerung der Prioritätsaufgabenplanung in diff -Algorithmus-Phase von 15 entspricht.

• Teilen Sie unterbrechbare Arbeit in kleinere Aufgaben auf.
• Passen Sie die Priorität der laufenden Arbeiten an, wiederholen Sie die vorherige (unvollendete) Arbeit und verwenden Sie sie erneut.
• Steuerung der Priorität der Aufgabenplanung in diff Phase.

Vergleich zwischen dem Betrieb von virtuellem DOM und dem Betrieb von nativem DOM

Ich zitiere hier direkt Youdas Worte (die Antwort war vom 2016-02-08 , als Vue2.0 noch nicht veröffentlicht war. Vue2.0 wurde um 2016-10-01 veröffentlicht Vue2.0 hat virtuelles DOM hinzugefügt). Der entsprechende Link ist https://www.zhihu.com/question/31809713 . Es wird empfohlen, ihn in Verbindung mit der Frage im Link zu lesen, und Sie können sich auch die Vergleichsbeispiele in der Frage ansehen. Darüber hinaus sind auch die folgenden Antworten sehr wichtig.

Native DOM-Operationen vs. von Frameworks gekapselte Operationen

Dies ist ein Kompromiss zwischen Leistung vs Wartbarkeit. Der Zweck des Frameworks besteht darin, die zugrunde liegenden DOM Operationen für Sie zu verbergen, sodass Sie Ihre Ziele deklarativer beschreiben können, sodass Ihr Code einfacher zu warten ist. Kein Framework kann schneller sein als eine rein manuelle Optimierung von DOM Operationen, da DOM Operationsebene des Frameworks alle Operationen verarbeiten muss, die von der API der höheren Ebene generiert werden können, und ihre Implementierung universell sein muss. Ich kann für jeden benchmark manuelle Optimierungen schreiben, die schneller sind als jedes Framework, aber was bringt das? Wenn Sie eine echte Anwendung erstellen, führen Sie dann an jeder Stelle eine manuelle Optimierung durch? Aus Gründen der Wartbarkeit ist dies offensichtlich unmöglich. Die Garantie, die Ihnen das Framework gibt, besteht darin, dass ich Ihnen auch ohne manuelle Optimierung eine anständige Leistung bieten kann.

Missverständnisse über Reacts virtuellen DOM

React hat nie behauptet, dass React schneller als native DOM -Operationen ist. Die grundlegende Denkweise von React besteht darin, die gesamte Anwendung bei jeder Änderung neu zu rendern. Wenn kein Virtual DOM vorhanden ist, kann man sich das einfach als direktes Zurücksetzen innerHTML vorstellen. Viele Leute erkennen nicht, dass das Zurücksetzen von innerHTML im Fall einer großen Liste, bei der sich alle Daten geändert haben, tatsächlich eine sinnvolle Operation ist. Das eigentliche Problem besteht darin, dass bei der Denkweise, alles neu zu rendern, selbst wenn sich nur eine Datenzeile geändert hat, auch das gesamte innerHTML zurückgesetzt werden muss, was offensichtlich eine Menge Verschwendung ist.
Wir können den Leistungsverbrauch beim Neuzeichnen von innerHTML vs Virtual DOM vergleichen:

• innerHTML : render html string O(template size) + alle DOM Elemente neu erstellen O(DOM size)
• Virtual DOM : render Virtual DOM + diff O(template size) + erforderliches DOM -Update O(DOM change) .

Virtual DOM render + diff ist offensichtlich langsamer als das Rendern html Strings, aber! Es handelt sich immer noch um reine js Berechnungen, die viel günstiger sind als nachfolgende DOM Operationen. Sie können sehen, dass die Gesamtberechnung von innerHTML , egal ob es sich um js -Berechnungen oder DOM Operationen handelt, mit der Größe der gesamten Schnittstelle zusammenhängt, aber von den Berechnungen von Virtual DOM hängt nur js Berechnung mit der Größe der Schnittstelle zusammen und DOM Operation mit der Menge der Datenänderungen. Wie bereits erwähnt, sind js -Berechnungen im Vergleich zu DOM Operationen extrem günstig. Aus diesem Grund Virtual DOM: Es garantiert 1) unabhängig davon, wie stark sich Ihre Daten ändern, eine akzeptable Leistung bei jedem Neuzeichnen; 2) Sie können beim Schreiben Ihrer Anwendung immer noch Ideen verwenden, die innerHTML ähneln.

MVVM vs. virtueller DOM

Im Vergleich zu React verwenden andere MVVM Frameworks wie Angular, Knockout , Vue und Avalon alle Datenbindung : Über Directive/Binding Objekte werden Datenänderungen beobachtet, Verweise auf tatsächliche DOM Elemente beibehalten und bei Datenänderungen entsprechende Vorgänge ausgeführt. Die Änderungserkennung von MVVM erfolgt auf Datenebene, während die Prüfung von React auf DOM Strukturebene erfolgt. Die Leistung von MVVM variiert auch je nach Implementierungsprinzip der Änderungserkennung: Angular Dirty Check bewirkt, dass jede Änderung mit festen O(watcher count) verbunden ist; Knockout/Vue/Avalon verwenden alle Abhängigkeitssammlungen, die sowohl auf js als auch auf DOM Ebene O(change) sind:

• Dirty-Check: scope digest O(watcher count) + erforderliches DOM -Update O(DOM change) .
• Abhängigkeitssammlung: erneutes Sammeln von Abhängigkeiten O(data change) + erforderliches DOM O(DOM change) .

Wie Sie sehen, besteht der ineffizienteste Aspekt von Angular darin, dass jede kleine Änderung Leistungseinbußen in Bezug auf die Anzahl der watcher verursacht. Wenn sich jedoch alle Daten geändert haben, ist Angular nicht wirklich im Nachteil. Die Abhängigkeitssammlung muss während der Initialisierung und bei Datenänderungen erneut erfasst werden. Diese Kosten sind fast vernachlässigbar, wenn nur wenige Aktualisierungen vorgenommen werden, aber sie verursachen auch einen gewissen Verbrauch, wenn die Datenmenge riesig ist.
Wenn MVVM eine Liste rendert, hat jede Zeile, da jede Zeile ihren eigenen Datenbereich hat, normalerweise eine entsprechende ViewModel Instanz oder ein etwas leichteres scope , das Prototypvererbung verwendet. Dies hat jedoch auch gewisse Kosten, sodass die Initialisierung des MVVM -Listen-Renderings mit ziemlicher Sicherheit langsamer ist als die von React , da das Erstellen ViewModel / scope Bereichsinstanzen viel teurer ist als das von Virtual DOM . Ein allgemeines Problem aller MVVM Implementierungen besteht hier darin, wie ViewModel Instanzen und DOM Elemente effektiv wiederverwendet werden können, wenn sich die Datenquelle des Listen-Renderings ändert, insbesondere wenn die Daten ein brandneues Objekt sind. Wenn keine Optimierung für die Wiederverwendung vorliegt, muss MVVM , da die Daten brandneu sind, tatsächlich alle vorherigen Instanzen zerstören, alle Instanzen neu erstellen und schließlich erneut rendern! Aus diesem Grund sind die im Titel verlinkten angular/knockout -Implementierungen relativ langsam. Im Gegensatz dazu erfolgt die Änderungsprüfung von React auf DOM Struktur. Selbst wenn es sich also um brandneue Daten handelt, muss keine unnötige Arbeit geleistet werden, solange sich das endgültige Rendering-Ergebnis nicht ändert.
Übrigens: Wenn React eine Liste rendert, muss es auch eine spezielle prop namens key bereitstellen, die im Wesentlichen dasselbe ist wie track-by .

Leistungsvergleich hängt auch vom Anlass ab

Beim Vergleich der Leistung ist es wichtig, zwischen verschiedenen Szenarien wie anfänglichem Rendering, kleinen Datenaktualisierungen und großen Datenaktualisierungen zu unterscheiden. Virtual DOM , Dirty Check MVVM und Datensammlungs MVVM haben in verschiedenen Szenarien unterschiedliche Leistungen und unterschiedliche Optimierungsanforderungen. Um die Leistung kleiner Datenaktualisierungen zu verbessern, erfordert Virtual DOM auch gezielte Optimierungen wie shouldComponentUpdate oder immutable data .

• Erstes Rendern: Virtual DOM > Dirty-Check >= Abhängigkeitssammlung.
• Kleines Datenupdate: Abhängigkeitssammlung >> Virtual DOM + Optimierung > Dirty Check (kann nicht optimiert werden) > Virtual DOM ohne Optimierung.
• Große Datenaktualisierungen: Dirty Checking + Optimierung >= Abhängigkeitssammlung + Optimierung > Virtual DOM (kann/muss nicht optimiert werden) >> MVVM ohne Optimierung.

Seien Sie nicht so naiv zu glauben, dass Virtual DOM schnell ist. diff ist nicht kostenlos, batching kann auch mit MVVM durchgeführt werden und der letzte patch erfordert immer noch die Verwendung nativer API . Meiner Meinung nach war der wahre Wert von Virtual DOM nie die Leistung, sondern dass es 1) die Tür zur funktionalen UI Programmierung öffnet; 2) auf anderen backend als DOM gerendert werden kann, wie z. B. ReactNative .

Zusammenfassen

Die obigen Vergleiche dienen eher dazu, Framework-Entwicklern und -Forschern einige Referenzen zu bieten. Das Mainstream-Framework + angemessene Optimierung reicht aus, um die Leistungsanforderungen der meisten Anwendungen zu erfüllen. In Sonderfällen mit extremen Leistungsanforderungen sollte ein Teil der Wartbarkeit zugunsten manueller Optimierung geopfert werden : Beispielsweise hat der Atom Editor bei der Implementierung der Dateidarstellung auf React verzichtet und seine eigene tile-based rendering übernommen; auf dem mobilen Endgerät ist beispielsweise virtuelles Scrollen DOM-pooling erforderlich, und die Reihenfolgeänderung muss nicht berücksichtigt werden, sodass Sie die integrierte Implementierung des Frameworks umgehen und selbst eine erstellen können.

Diff-Algorithmus

React verwaltet einen virtuellen DOM Baum im Speicher. Wenn sich die Daten ändern ( state & props ), wird der virtuelle DOM automatisch aktualisiert, um einen neuen virtuellen DOM Baum zu erhalten. Anschließend vergleicht es mithilfe des Diff -Algorithmus den alten und den neuen virtuellen DOM Baum, um den am wenigsten geänderten Teil zu finden, fügt den Patch mit dem geänderten Teil der Warteschlange hinzu und aktualisiert diese Patch schließlich stapelweise im tatsächlichen DOM .

Zeitliche Komplexität

Zunächst einmal erfordert ein vollständiger diff eine Zeitkomplexität O(n^3) , was ein Problem der minimalen Editierdistanz ist. Beim Vergleich der minimalen Editierdistanz von Zeichenfolgen beträgt die Zeitkomplexität bei Verwendung dynamischer Programmierung O(mn) . DOM ist jedoch eine Baumstruktur, und die Zeitkomplexität des Problems der minimalen Editierdistanz der Baumstruktur hat sich in mehr als 30 Jahren Entwicklung von O(m^3n^3) auf O(n^3) entwickelt. Wenn Sie an diesem Thema interessiert sind, können Sie das Dokument https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf lesen.
Für den diff Algorithmus, der ursprünglich zur Verbesserung der Effizienz eingeführt wurde, ist eine Zeitkomplexität von O(n^3) offensichtlich nicht angemessen. Wenn es 1000 Knotenelemente gibt, sind eine Milliarde Vergleiche erforderlich. Dies ist ein teurer Algorithmus, daher müssen einige Kompromisse eingegangen werden, um den Prozess zu beschleunigen. Der Vergleich wird durch einige Strategien vereinfacht und die Zeitkomplexität auf O(n) reduziert. Obwohl dies nicht die minimale Editierdistanz ist, ist es eine bessere Lösung, wenn Editierdistanz und Zeitleistung umfassend berücksichtigt werden, und es ist ein besserer Kompromiss.

Diff-Strategie

O(n) -Zeitkomplexität wird durch eine bestimmte Strategie erreicht. React Dokumentation werden zwei Annahmen erwähnt:

• Zwei Elemente unterschiedlichen Typs erzeugen unterschiedliche Bäume.
• Durch Anhängen eines key an den Renderer können Entwickler angeben, welche untergeordneten Elemente stabil sein können.

Einfach ausgedrückt:

• Es werden nur Vergleiche auf derselben Ebene durchgeführt und Verschiebungen zwischen Ebenen werden als Erstellungs- und Löschvorgänge betrachtet.
• Wenn die Elemente unterschiedlichen Typs sind, wird davon ausgegangen, dass ein neues Element erstellt wurde, und ihre untergeordneten Elemente werden nicht rekursiv verglichen.
• Bei ähnlichen Inhalten, wie etwa Listenelementen, lässt sich anhand key eindeutig feststellen, ob es sich um eine Verschiebe-, Erstell- oder Löschoperation handelt.

Nach dem Vergleich treten verschiedene Situationen auf und dann werden entsprechende Vorgänge ausgeführt:

• Dieser Knoten wird hinzugefügt oder entfernt -> Neue Knoten hinzufügen oder entfernen.
• Attribute werden geändert -> alte Attribute werden in neue Attribute geändert.
• Der Textinhalt wird geändert -> der alte Inhalt wird durch den neuen Inhalt ersetzt.
• Ob sich das Knoten tag oder key ändert -> Falls geändert, entfernen Sie es und erstellen Sie ein neues Element.

analysieren

In der Analyse werden wir kurz den Quellcode von React zitieren, der eine Hilfsrolle spielt. Der eigentliche Quellcode ist sehr kompliziert, und wir zitieren einige Fragmente, um ihn besser zu verstehen. Der Quellcode TAG dieses Artikels lautet 16.10.2 .
Der Code im Zusammenhang mit if (__DEV__){...} wurde eigentlich für ein besseres Entwicklererlebnis geschrieben. Benutzerfreundliche Fehlerberichterstattung, render und andere Codes in React werden alle in if (__DEV__) geschrieben. Diese Codes werden während production build nicht gepackt, sodass wir Entwicklern ohne Bedenken Code zur Verfügung stellen können. Eine der Best Practices von React besteht darin, development build während der Entwicklung und den production build in der Produktionsumgebung zu verwenden, sodass wir diesen Teil des Codes tatsächlich überspringen und uns auf das Verständnis der grundlegenderen Teile konzentrieren können.
Unsere Analyse des diff -Algorithmus beginnt mit reconcileChildren . Wir werden die zugehörigen Teile von setState -> enqueueSetState(UpdateQueue) -> scheduleUpdate -> performWork -> workLoop -> beginWork -> finishClassComponent -> reconcileChildren nicht im Detail vorstellen. Es ist zu beachten, dass beginWork jede Fiber einzeln diff und die Periode unterbrechbar ist, da bei jedem Vergleich der nächsten Fiber zuerst bestimmt wird, ob die verbleibende Zeit dieses Frames ausreicht. Jeder Knoten der verknüpften Liste ist Fiber , kein virtueller DOM Knoten vor 16 Jede Fiber hat eine React16 diff Strategie, die einen Algorithmus verwendet, der den Vergleich am Kopf der verknüpften Liste beginnt. Es handelt sich um eine kettenartige Tiefendurchquerung, d. h. sie hat sich von einer Baumstruktur in eine verknüpfte Listenstruktur geändert, was tatsächlich der Steuerung der Prioritätsaufgabenplanung in diff -Algorithmus von 15 entspricht. Außerdem besitzt jede Fiber drei Attribute: child , sibling und return die als Zeiger auf die Vorderseite und die Rückseite des Linkbaums dienen; child ist ein Strukturzeiger, der die Baumstruktur simuliert; effectTag ist ein sehr interessantes Tag, mit dem der Typ des effect aufgezeichnet wird. effect bezieht sich auf die Art und Weise der Bedienung DOM , wie z. B. Ändern, Löschen und andere Vorgänge, die später zum commit verwendet werden (ähnlich einer Datenbank); firstEffect , lastEffect usw. werden verwendet, um den Status effect vor und nach der Unterbrechung zu speichern, und der Benutzer kann den vorherigen Vorgang nach der Unterbrechung wiederherstellen, und tag wird zum Markieren verwendet.
reconcileChildren implementiert das weit verbreitete Virtul DOM diff , das eigentlich nur eine Eingabefunktion ist. Wenn es sich um das erste Rendering handelt, ist current null und Fiber Instanz des untergeordneten Knotens wird über mountChildFibers erstellt. Wenn es sich nicht um das erste Rendering handelt, wird reconcileChildFibers aufgerufen, um diff auszuführen, und dann wird effect list abgerufen.

// react-reconciler/src/ReactChildFiber.js Zeile 1246
Exportfunktion reconcileChildren(
  aktuell: Fiber | null,
  workInProgress: Faser,
  nextChildren: beliebig,
  renderExpirationTime: Ablaufzeit,
) {
  if (current === null) { // Das erste Rendern erstellt eine `Fiber`-Instanz eines untergeordneten Knotens workInProgress.child = mountChildFibers(
      in Arbeit,
      null,
      nächsteKinder,
      Renderablaufzeit,
    );
  } else { // Andernfalls rufen Sie `reconcileChildFibers` auf, um `diff` auszuführen
    workInProgress.child = Kinderfasern abgleichen(
      in Arbeit,
      aktuelles Kind,
      nächsteKinder,
      Renderablaufzeit,
    );
  }
}

Wenn wir die Unterschiede zwischen mountChildFibers und reconcileChildFibers vergleichen, können wir sehen, dass sie beide aus der ChildReconciler -Factory-Funktion stammen, aber die übergebenen Parameter sind unterschiedlich. Dieser Parameter heißt shouldTrackSideEffects . Seine Funktion besteht darin, zu bestimmen, ob einige effectTag hinzugefügt werden sollen. Er wird hauptsächlich verwendet, um das anfängliche Rendering zu optimieren, da beim anfänglichen Rendering kein Aktualisierungsvorgang stattfindet. ChildReconciler ist eine superlange Factory-Funktion (Wrapper-Funktion) mit vielen darin enthaltenen helper . Die schließlich zurückgegebene Funktion heißt reconcileChildFibers und implementiert reconciliation von untergeordneten fiber .

// react-reconciler/src/ReactChildFiber.js Zeile 1370
exportiere const reconcileChildFibers = ChildReconciler(true);
exportiere const mountChildFibers = ChildReconciler(false);

Funktion ChildReconciler(sollteNebeneffekte verfolgen) { 
  // ...
  Funktion „Kind löschen“ () {
      // ...
  }
  Funktion useFiber(){
      // ...
  }
  Funktion OrtKind(){
      // ...
  }
  Funktion platziereEinzelkind(){
      // ...
  }
  Funktion updateTextNode(){
      // ...
  }
  Funktion updateElement(){
      // ...
  }
  Funktion updatePortal(){
      // ...
  }
  Funktion updateFragment(){
      // ...
  }
  Funktion erstelleKind(){
      // ...
  }
  Funktion updateSlot(){
      // ...
  }
  Funktion updateFromMap(){
      // ...
  }
  Funktion warnenBeiUngültigemSchlüssel(){
      // ...
  }
  Funktion reconcileChildrenArray(){
      // ...
  }
  Funktion reconcileChildrenIterator(){
      // ...
  }
  Funktion reconcileSingleTextNode(){
      // ...
  }
  Funktion reconcileSingleElement(){
      // ...
  }
  Funktion reconcileSinglePortal(){
      // ...
  }
  Funktion reconcileChildFibers(){
      // ...
  }
  gib reconcileChildFibers zurück;
}

reconcileChildFibers ist der Hauptcode diff Teils. Die zugehörigen Operationen befinden sich alle in der Funktion ChildReconciler . Die relevanten Parameter in dieser Funktion sind: returnFiber ist der übergeordnete Knoten der zu diff Ebene, currentFirstChild ist der erste Fiber Knoten der aktuellen Ebene und newChild ist der zu aktualisierende vdom Knoten (der TextNode , ReactElement oder ein Array sein kann), kein Fiber Knoten. expirationTime ist die Ablaufzeit. Dieser Parameter bezieht sich auf die Planung und hat wenig mit diff zu tun. Darüber hinaus ist zu beachten, dass reconcileChildFibers eine Schichtstruktur von reconcile(diff) ist.

Schauen wir uns zunächst TextNode diff an, der am einfachsten ist. Es gibt zwei Fälle für diff TextNode :

• currentFirstNode ist TextNode .
• currentFirstNode ist kein TextNode .

Aufgrund der Knotenwiederverwendung gibt es zwei Fälle. Im ersten Fall ist xxx ein TextNode , was bedeutet, dass dieser Knoten wiederverwendet werden kann. Wiederverwendete Knoten sind sehr hilfreich für die Leistungsoptimierung. Da das neue child nur einen TextNode hat, kann der verbleibende aaa Knoten nach der Wiederverwendung des Knotens gelöscht und child von div zu workInProgress hinzugefügt werden. useFiber ist eine Methode zum Wiederverwenden von Knoten deleteRemainingChildren ist eine Methode zum Löschen verbleibender Knoten. Hier beginnt das Löschen bei currentFirstChild.sibling .

wenn (aktuellesErstesKind !== null && aktuellesErstesKind.tag === HostText) {
  // Wir haben bereits einen vorhandenen Knoten, also aktualisieren wir ihn einfach und löschen
  // der Rest.
  deleteRemainingChildren(returnFiber, currentFirstChild.sibling); // Geschwister löschen const existing = useFiber(currentFirstChild, textContent, expirationTime);
  bestehend.return = returnFiber;
  returniere vorhandenes; // wiederverwenden }

Im zweiten Fall ist xxx kein TextNode , was bedeutet, dass dieser Knoten nicht wiederverwendet werden kann. Daher werden die verbleibenden Knoten beginnend mit currentFirstChild gelöscht. createFiberFromText ist eine Methode zum Erstellen von Knoten basierend auf textContent . Darüber hinaus wird durch das Löschen eines Knotens der Knoten tag delete . Er wird tatsächlich gelöscht, wenn commit ausgeführt wird.

// Das vorhandene erste Kind ist kein Textknoten, also müssen wir eines erstellen
// und lösche die vorhandenen.
// Einen neuen Fiber-Knoten erstellen und den alten Knoten und seine Brüder löschen deleteRemainingChildren(returnFiber, currentFirstChild);
const erstellt = createFiberFromText(
  Textinhalt,
  returnFiber.mode,
  Ablaufzeit,
);

Als nächstes folgt diff von React Element . Derzeit haben wir es mit einer Situation zu tun, in der der übergeordnete Knoten des Knotens nur dieser Knoten ist. Ähnlich wie diff von TextNode oben sind die Ideen dieselben. Finden Sie zunächst heraus, ob es einen Knoten gibt, der wiederverwendet werden kann. Wenn nicht, erstellen Sie einen anderen. Zu diesem Zeitpunkt werden die beiden oben genannten Annahmen verwendet, um zu bestimmen, ob der Knoten wiederverwendet werden kann, d. h. ob key derselbe ist und ob der Knotentyp derselbe ist. Wenn die oben genannten Annahmen gleich sind, kann davon ausgegangen werden, dass der Knoten nur seinen Inhalt geändert hat und kein neuer Knoten erstellt werden muss, sodass er wiederverwendet werden kann. Wenn die Knoten unterschiedlichen Typs sind, löschen Sie die verbleibenden Knoten, beginnend beim aktuellen Knoten. Bei der Suche nach wiederverwendbaren Knoten wird nicht nur darauf geachtet, ob der erste Knoten wiederverwendbar ist, sondern es wird weiter in der Ebene nach wiederverwendbaren Knoten gesucht. Das „ while auf oberster Ebene und das child = child.sibling; auf unterer Ebene dienen dazu, weiterhin nach wiederverwendbaren Knoten mit demselben key und tag von den untergeordneten Knoten zu suchen. Darüber hinaus wird durch das Löschen eines Knotens der Knoten nicht wirklich aus der verknüpften Liste gelöscht, sondern nur ein delete hinzugefügt, und er wird tatsächlich gelöscht tag wenn commit ausgeführt wird.

// react-reconciler/src/ReactChildFiber.js Zeile 1132
const Schlüssel = Element.Schlüssel;
let child = aktuellesErstesKind;
während (Kind !== null) {
  // TODO: Wenn key === null und child.key === null, dann gilt dies nur für
  // das erste Element in der Liste.
  wenn (Kind.Schlüssel === Schlüssel) {
    Wenn (
      untergeordnetes Tag === Fragment
        ? Elementtyp === REACT_FRAGMENT_TYPE
        : untergeordnetes Elementtyp === Elementtyp ||
          // Lassen Sie diese Prüfung inline, damit sie nur auf dem falschen Pfad ausgeführt wird:
          (__DEV__
            ? isCompatibleFamilyForHotReloading(Kind, Element)
            : FALSCH)
    ) {
      deleteRemainingChildren(returnFiber, child.sibling); // Weil der aktuelle Knoten nur einen Knoten hat und der alte Geschwisterknoten hat, die gelöscht werden müssen, was redundant ist const existing = useFiber(
        Kind,
        element.typ === REACT_FRAGMENT_TYPE
          ? element.props.children
          : element.props,
        Ablaufzeit,
      );
      bestehend.ref = coerceRef(returnFiber, Kind, Element);
      bestehend.return = returnFiber;
      // ...
      bestehende zurückgeben;
    } anders {
      löscheRestKinder(returnFiber, Kind);
      brechen;
    }
  } anders {
    deleteChild(returnFiber, child); // Beginne mit dem Löschen vom untergeordneten Element
  }
  child = child.sibling; // Weiter mit der Suche nach einem wiederverwendbaren Knoten aus den untergeordneten Knoten}

Der nächste Schritt besteht darin, einen Knoten zu erstellen, da kein wiederverwendbarer Knoten gefunden wurde. Die Vorgehensweise zum Erstellen Fragment unterscheidet sich von der eines allgemeinen Element , da Fragment ursprünglich ein bedeutungsloser Knoten ist. Fiber es wirklich erstellen muss, sind seine children , nicht sich selbst. Daher übergibt createFiberFromFragment element.props.children anstelle von element .

// react-reconciler/src/ReactChildFiber.js Zeile 1178
wenn (Element.Typ === REACT_FRAGMENT_TYPE) {
  const erstellt = createFiberFromFragment(
    element.props.children,
    returnFiber.mode,
    Ablaufzeit,
    Element.Schlüssel,
  );
  erstellt.return = returnFiber;
  Rückgabe erstellt;
} anders {
  const erstellt = createFiberFromElement(
    Element,
    returnFiber.mode,
    Ablaufzeit,
  );
  erstellt.ref = coerceRef(returnFiber, aktuellesErstesKind, Element);
  erstellt.return = returnFiber;
  Rückgabe erstellt;
}

diff Array ist der komplizierteste Teil diff , und es wurden viele Optimierungen vorgenommen. Da Fiber Baum eine einzelne verknüpfte Listenstruktur ist, gibt es keine Datenstruktur wie ein untergeordnetes Knotenarray und keinen Endcursor für den gleichzeitigen Vergleich beider Enden. Daher ist der React -Algorithmus eine vereinfachte doppelseitige Vergleichsmethode, die nur vom Kopf aus vergleicht. diff Algorithmus in Vue2.0 wird beim patch direkt unter Verwendung der doppelseitigen Vergleichsmethode implementiert.
Betrachten Sie zunächst den Vergleich derselben Positionen. Dies ist eine relativ einfache Möglichkeit, sich das vorzustellen. Das heißt, wenn Sie diff ausführen, können Sie die neuen und alten Arrays nacheinander anhand des Index vergleichen. Wenn es wiederverwendet werden kann, löschen Sie diesen Knoten aus der alten verknüpften Liste. Wenn es nicht wiederverwendet werden kann, verwenden Sie andere Wiederverwendungsstrategien. Zu diesem Zeitpunkt ist newChildren -Array ein VDOM Array, daher wird hier updateSlot verwendet, um es in newFiber zu packen.

// react-reconciler/src/ReactChildFiber.js Zeile 756
Funktion reconcileChildrenArray(
    returnFiber: Faser,
    currentFirstChild: Fiber | null,
    neueUntergeordnete: Array<*>,
    Ablaufzeit: Ablaufzeit,
  ): Faser | null {
    // Kommentare zur maschinellen Übersetzung // Dieser Algorithmus kann nicht durch eine Suche an beiden Enden optimiert werden, da wir keine Rückzeiger auf der Faser haben. Ich wollte sehen, wie weit wir mit diesem Modell kommen können. Wenn sich der Kompromiss am Ende nicht lohnt, können wir es später immer noch wieder hinzufügen.
    // Auch bei Dual-End-Optimierungen möchten wir optimieren, wenn es nur wenige Änderungen gibt und einen Vergleich erzwingen, anstatt nach einer Karte zu suchen. Es möchte den Weg zunächst im Vorwärtsmodus erkunden und erst dann auf die Karte wechseln, wenn wir merken, dass wir weit nach vorne schauen müssen. Umkehrungen werden dadurch nicht so gut gehandhabt wie Suchen mit zwei Enden, aber das ist ungewöhnlich. Damit die Optimierung an beiden Enden bei Iterables funktioniert, müssen wir außerdem die gesamte Sammlung kopieren.
    // In der ersten Iteration stoßen wir bei jedem Einfügen/Verschieben einfach auf den schlechten Fall (alles zur Karte hinzufügen).
    // Wenn Sie diesen Code ändern, müssen Sie auch reconcileChildrenIterator() aktualisieren, das denselben Algorithmus verwendet.
    lass alteFiber = aktuellesErstesKind;
    lass lastPlacedIndex = 0;
    sei newIdx = 0;
    let nextOldFiber = null;
     // Die erste for-Schleife vergleicht die neuen und alten Knoten nacheinander entsprechend dem Index. Wenn die neuen und alten Knoten inkonsistent sind, wird die Schleife beendet und der Knoten und der oldFiber-Knoten zum Zeitpunkt des Beendens werden aufgezeichnet for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) { // Positionskonflikt nextOldFiber = oldFiber; // Nächster alter Knoten zum Vergleichen oldFiber = null; // Wenn newFiber ebenfalls null ist (kann nicht wiederverwendet werden), beenden Sie den aktuellen Eins-zu-eins-Vergleich for-Schleife} else {
        nextOldFiber = oldFiber.sibling; //Unter normalen Umständen wird für den nächsten Zyklus der Wert des Geschwisterknotens abgerufen und oldFiber zugewiesen.
      }
      // //Wenn der Knoten wiederverwendet werden kann (Schlüsselwert stimmt überein), aktualisiere und gib den neuen Knoten zurück, andernfalls gib null zurück, was bedeutet, dass der Knoten nicht wiederverwendet werden kann const newFiber = updateSlot( // Bestimme, ob der Knoten wiederverwendet werden kann returnFiber,
        alteFaser,
        neueKinder[neueIdx],
        Ablaufzeit,
      );
      // Der Knoten kann nicht wiederverwendet werden, um aus der Schleife auszusteigen, if (newFiber === null) { 
        // TODO: Dies bricht bei leeren Slots wie Null-Children ab. Das ist
        // bedauerlich, weil es ständig den langsamen Pfad auslöst. Wir brauchen
        // eine bessere Möglichkeit zu kommunizieren, ob dies ein Fehler oder ein Nullwert war,
        // Boolesch, undefiniert usw.
        wenn (alteFaser === null) {
          oldFiber = nextOldFiber; //Knoten aufzeichnen, die nicht wiederverwendet werden können, und Vergleich beenden}
        break; // die Schleife verlassen }
      wenn (sollteNebeneffekte verfolgen) {
        // Wenn Sie vorhandene Knoten nicht wiederverwenden, löschen Sie die vorhandenen Knoten, wenn (oldFiber && newFiber.alternate === null) {
          // Wir haben den Steckplatz angepasst, aber die vorhandene Faser nicht wiederverwendet.
          // muss das vorhandene untergeordnete Element löschen.
          löscheKind(returnFiber, oldFiber);
        }
      }
      // Diese Durchquerung markiert die neu hinzugefügten Knoten als eingefügt lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      wenn (vorherigeNeueFiber === null) {
        // TODO: Aus der Schleife herausgehen. Dies geschieht nur beim ersten Durchlauf.
        resultierendesErstesKind = neueFaser;
      } anders {
        // TODO: Geschwister zurückstellen, wenn wir nicht am richtigen Index für diesen Slot sind.
        // Dh wenn wir vorher Nullwerte hatten, dann wollen wir das verschieben
        // für jeden Nullwert. Allerdings möchten wir updateSlot auch nicht aufrufen
        // mit dem vorherigen.
        vorherigeNeueFiber.geschwister = neueFiber;
      }
      vorherigeNeueFiber = neueFiber;
      oldFiber = nextOldFiber; // oldFiber neu zuweisen und Durchlauf fortsetzen}

updateSlot definiert, ob sie wiederverwendet werden kann. Bei Textknoten bedeutet key ungleich null , dass der alte Knoten kein TextNode ist und der neue Knoten TextNode ist. Daher wird null zurückgegeben und er kann nicht wiederverwendet werden. Andernfalls kann er wiederverwendet werden. Rufen Sie die Methode updateTextNode auf. Beachten Sie, dass updateTextNode die Logik des ersten Renderings enthält. Während des ersten Renderings wird ein TextNode eingefügt, anstatt wiederverwendet zu werden.

// react-reconciler/src/ReactChildFiber.js Zeile 544
Funktion updateSlot(
    returnFiber: Faser,
    oldFiber: Faser | null,
    neues Kind: beliebig,
    Ablaufzeit: Ablaufzeit,
  ): Faser | null {
    // Aktualisieren Sie die Faser, wenn die Schlüssel übereinstimmen, andernfalls geben Sie null zurück.

    const key = oldFiber !== null ? oldFiber.key : null;

    wenn (Typ des neuen Kindes === 'Zeichenfolge' || Typ des neuen Kindes === 'Zahl') {
      // Für neue Knoten gilt: Wenn es sich um Zeichenfolgen oder Zahlen handelt, haben sie keine Schlüssel.
      // Wenn der alte Knoten einen Schlüssel hat, kann er nicht wiederverwendet werden und gibt direkt null zurück.
      // Wenn der alte Knotenschlüssel null ist, bedeutet dies, dass der alte Knoten ein Textknoten ist. Sie können also if (key !== null) { wiederverwenden.
        gibt null zurück;
      }
      returniere updateTextNode(
        Rückkehrfaser,
        alteFaser,
        '' + neues Kind,
        Ablaufzeit,
      );
    }

    // ...

    gibt null zurück;
}

Wenn newChild Object ist, ähnelt es grundsätzlich diff von ReactElement , außer dass es kein while gibt. Es bestimmt, ob der Typ von key und Element gleich ist, um zu bestimmen, ob es wiederverwendet werden kann. Um zunächst zu bestimmen, ob es sich um ein Objekt handelt, verwenden Sie typeof newChild === object && newChild!== null . Beachten Sie, dass !== null hinzugefügt werden sollte, da typeof null auch object ist. Verwenden Sie dann $$typeof , um zu bestimmen, ob es sich um REACT_ELEMENT_TYPE oder REACT_PORTAL_TYPE handelt, und rufen Sie jeweils unterschiedliche Wiederverwendungslogiken auf. Da Arrays auch Object sind, gibt es in diesem if auch eine Array-Wiederverwendungslogik.

// react-reconciler/src/ReactChildFiber.js Zeile 569
wenn (Typ von neuem Kind === 'Objekt' und neues Kind !== null) {
  Schalter (neuesKind.$$Typvon) {
    Fall REACT_ELEMENT_TYPE: { // ReactElement 
      wenn (neuesKind.Schlüssel === Schlüssel) {
        wenn (neuesUnterelement.Typ === REACT_FRAGMENT_TYPE) {
          returniere UpdateFragment(
            Rückkehrfaser,
            alteFaser,
            neuesKind.Eigenschaften.Kinder,
            Ablaufzeit,
            Schlüssel,
          );
        }
        returniere updateElement(
          Rückkehrfaser,
          alteFaser,
          neues Kind,
          Ablaufzeit,
        );
      } anders {
        gibt null zurück;
      }
    }
    Fall REACT_PORTAL_TYPE: {
      //UpdatePortal aufrufen
      // ...
    }
  }

  wenn (istArray(neuesKind) || getIteratorFn(neuesKind)) {
    wenn (Schlüssel !== null) {
      gibt null zurück;
    }

    returniere UpdateFragment(
      Rückkehrfaser,
      alteFaser,
      neues Kind,
      Ablaufzeit,
      null,
    );
  }
}

Kehren wir zur ersten Durchquerung zurück. Wenn wir die Durchquerung abgeschlossen haben, gibt es zwei Situationen: Entweder wurden die alten Knoten durchlaufen oder die neuen Knoten wurden durchlaufen. Wenn wir zu diesem Zeitpunkt die neuen Knoten durchlaufen haben, d. h. es gibt nichts zu aktualisieren, bedeutet diese Situation im Allgemeinen, dass die Elemente aus dem ursprünglichen Array gelöscht werden. Löschen Sie dann einfach die verbleibenden alten Knoten. Wenn die alten Knoten im ersten Zyklus wiederverwendet werden, aber neue Knoten vorhanden sind, ist es sehr wahrscheinlich, dass neue Knoten hinzugefügt wurden. In diesem Fall müssen Sie Fiber nur direkt basierend auf den verbleibenden neuen Knoten erstellen.

// react-reconciler/src/ReactChildFiber.js Zeile 839
// Der neue Knoten wurde aktualisiert, löschen
  // Wir haben das Ende der neuen Kinder erreicht.
  DeleterMainingChildren (returnfiber, Oldfiber);
  Rückgabe resultierende Firstchild;
}

// Der neue Knoten wurde aktualisiert, löschen Sie die redundanten alten Knoten, wenn (oldfiber === null) {
  // Wenn wir keine mehr vorhandenen Kinder haben, können wir einen schnellen Weg wählen
  // Da der Rest alle Einfügungen sein werden.
  für (; Newidx <NewChildren.length; Newidx ++) {
    const newfiber = createchild (
      returnfiber,
      New Children [Newidx],
      Ablaufzeit,
    );
    if (newfiber === null) {
      weitermachen;
    }
    lastplacedIndex = landechild (newfiber, lastplacedIndex, Newidx);
    if (vorhernewfiber === null) {
      // TODO: Bewegen Sie sich aus der Schleife.
      resultingFirstchild = newfiber;
    } anders {
      vorhernewfiber.sibling = newfiber;
    }
    VorherigesNewfiber = Neufaser;
  }
  Rückgabe resultierende Firstchild;
}

接下來考慮移動的情況如何進行節點復用，即如果老的數組和新的數組里面都有這個元素，而且位置不相同這種情況下的復用， React把所有老數組元素按key或者是index放Map里，然后遍歷新數組，根據新數組的key或者index快速找到老數組里面是否有可復用的，元素有key就Map的鍵就存key ，沒有key就存index 。

// React-Reconciler/src/reactchildfiber.js Zeile 872
// Fügen Sie alle Kinder zu einer Schlüsselkarte für schnelle Lookups hinzu.
// Fügen Sie den Schlüssel oder den Index des vorhandenen Knotens der Kartenstruktur aus oldfiber const vorhandenen und MapRemainingChildren (returnfiber, Oldfiber) hinzu;

// SCROCKEN SIE UND DIE MAP, um gelöschte Elemente als Bewegungen wiederherzustellen.
// Vergleichen Sie für die verbleibenden neuen Knoten, die nicht verglichen wurden, sie nacheinander auf der Karte der alten Knoten mit dem Schlüssel oder in den Index, um festzustellen, ob sie wiederverwendet werden können.
für (; Newidx <NewChildren.length; Newidx ++) {
  // Überprüfen Sie hauptsächlich, ob der Schlüssel oder der Index der neuen und alten Knoten gleich sind, und überprüfen Sie dann, ob sie wiederverwendet werden können.
  const newfiber = updateFrommap (
    bestehende Children,
    returnfiber,
    Newidx,
    New Children [Newidx],
    Ablaufzeit,
  );
  if (newfiber! == null) {
    if (Sollte -Stracksideffects) {
      if (newfiber.Alternate! == null) {
        // Die neue Faser ist eine laufende Arbeit, aber wenn es a
        // Strom, das bedeutet, dass wir die Faser wiederverwendet haben.
        // es aus der Kinderliste, damit wir es nicht zum Löschen hinzufügen
        // Liste.
        Bestehende Children.delete (// den Schlüssel oder den Index des wiederverwendeten Knotens in der Karte löschen
          newfiber.key === null?
        );
      }
    }
    lastplacedIndex = landechild (newfiber, lastplacedIndex, Newidx);
    // Neufaser der aktualisierten Neufaserstruktur Neufaser hinzufügen.
    if (vorhernewfiber === null) {
      resultingFirstchild = newfiber;
    } anders {
      vorhernewfiber.sibling = newfiber;
    }
    VorherigesNewfiber = Neufaser;
  }
}

// React-Reconciler/SRC/Reactchildfiber.js Zeile 299
// Speichern Sie den Schlüssel oder den Index des alten Knotens und des alten Knotens in der Kartenstruktur, so dass es bequem ist, nach Schlüssel- oder Indexfunktion MapRemainingChildren zu erhalten ((
    returnfiber: faser,
    CurrentFirstChild: Faser,
  ): Karte <String |.
    // Fügen Sie die verbleibenden Kinder einer vorübergehenden Karte hinzu, damit wir sie finden können
    // Tasten schnell.
    // stattdessen.
    const bestehende kinder: map <string |

    lass existentChild = currentFirstchild;
    while (vorhandeneChild! == null) {
      if (existentChild.key! == null) {
        vorhandeneChildren.set (vorhandeneChild.Key, vorhandeneChild);
      } anders {
        vorhandeneChildren.set (vorhandeneChild.Index, vorhandeneChild);
      }
      existentChild = vorhandeneChild.Sibling;
    }
    Return bestehende Children;
  }

Zu diesem Zeitpunkt ist der Neuanfang -Traversal abgeschlossen, dh der diff -Prozess in derselben Schicht ist abgeschlossen.

• Überfahren Sie zunächst das neue Array updateSlot vergleichen Sie die neuen und alten Arrays mit demselben index .
• Nach Abschluss des ersten Traverses werden die verbleibenden alten Knoten gelöscht und die verbleibenden ; Knoten werden angehängt.
• Setzen Sie alle alten Array -Elemente in Map nach key oder index , und durchqueren Sie das neue Array und setzen Sie die Elemente des alten Arrays ein.

Frage des Tages

https://github.com/WindrunnerMax/EveryDay

siehe

https://zhuanlan.zhihu.com/p/89363990
https://zhuanlan.zhihu.com/p/137251397
https://github.com/sisteran/blog/issues/22
https://github.com/hujiulong/blog/issues/6
https://juejin.cn/post/6844904165026562056
https://www.cnblogs.com/forcheng/p/13246874.html
https://zh-hans.reactjs.org/docs/reconciliation.html
https://zxc0328.github.io/2017/09/28/react-16-source/
https://blog.csdn.net/halations/article/details/109284050
https://blog.csdn.net/susuzhe123/article/details/107890118
https://github.com/advanced-frontend/daily-interview-question/issues/47
https://github.com/jianjiachenghub/react-teeplearn/blob/master/%E5%AD%A6%E4%B9%A0. BC%8FDIFF%E7%AE%97%E6%B3%95,md

Das obige ist eine detaillierte Analyse des Diff -Algorithmus in React.