こんにちは

多くのフロントエンド開発者は、特にReact.jsで使用されるVDOMテクノロジーはブラックボックスのように機能すると考えています。 また、npmのオープンスペースには、このテクノロジーを実装するライブラリがたくさんありますが、私にとっては、悪魔の足がそれらに侵入します。 VDOMトピック自体に少し前から興味があり、自分で触って実験を始めました。 最終的には、VDOMの実装を作成し、それをデータグリッドフレームワークに組み込んだという事実に終わりました（どうにかしてそれについて説明します）。 簡単ではありませんでしたが、非常にシンプルでした。この記事では、何が、なぜ、なぜかを詳しく説明します。 そして、その仕組みを説明します。 キャットの下に飛び込むと、興味深い体験ができます。

ディスクラマー

私はフロントエンド開発者ではありません。 スリッパで私をhitらないでください。

また、「既成の枠組みを取りなさい、クラブ」と書いてはいけません。 既製のフレームワークがあることは知っていますが、純粋に技術的な理由から、独自の実装が必要です。

なぜそれが必要ですか

TL; DR ： jsfiddleに関するこの記事の ソース

ハブのどこかにVDOMについての記事が既にありましたが 、問題の本質の説明が好きではありません。 それで、指にそれを投げさせます。 それで、あなたがウェブページを持っているとしよう？ 特定のHTML要素（おそらくかなり大きい）をレンダリングしました。 少しのコンテキストを追加するには-この要素は、ビューモデルでテンプレートを引っ張って描画されます。 まあ、誰もがこれを行うフレームワークを使用しましたか？ そこにあるハンドルバー、lodashテンプレート、AngularJS ...要するに、テンプレートがプルされるモデルが変更されたと想像してください。 そして、これらの変更をHTML要素内に描画する必要があります。 問題が発生します-どうやってそれを行い、トラブルに巻き込まれないのですか？ ここでは、いつものように、いくつかのオプションがあります。

innerHTML

テンプレートエンジンを使用してデータモデルを実行し、HTMLを取得して、 element.innerHTML = ourHtmlString;



実行するだけですelement.innerHTML = ourHtmlString;



。 安くて陽気ですが、一部のタスクではかなり良いです。 ここで恐ろしいことは何ですか？

そして、私はあなたに答えます：このオプションは、 element



内にあるすべての子要素がブラウザによって容赦なく殺され、新しい要素に置き換えられるため、主に悪いです。 だから？ はい、したがって、あなたはあなたが持っていた（もちろんあなたの要素内で）イベントへのすべてのサブスクリプションを失います。 新しく作成したアイテムに再度署名する必要があります。 ここでは、正直に認めますが、異なるjsエンジンでガベージコレクションがどのように機能するかはわかりませんが、以前に変数などのコードにいくつかの子要素を保存した場合、これらの要素はツリーから削除されますが、破壊されません。 こんにちはメモリリーク、私たちはあなたを逃した。 さて、これは、たとえばブラウザーがDOM要素の参照カウントを使用することを前提としています。 誰が詳細を知っている-コメントに書いてください。

これに加えて-このオプションは、特に子供が多い場合は非常に遅くなります。 つまり、ブラウザは要素内に描画されたすべてを正直に消去し、再カウントして再描画します。 想像してみてください-あなたはグリシャからカードを引きました。そこには100の異なるフィールドがあります。 また、データでは生年月日のみが変更されています。 そして今、不幸なテキストのために、「すべてのゴミ、グリシャ、新しいやり方でやってくる」ということですか？ グリシャ全体を殺し、数えて再描画しますか？ ブラウザでインターフェースを再描画するのは、実際には長い時間がかかることをご存知ですか？ グリシャが150の要素で構成されている場合、それでも彼はどこへ行っても。 しかし、1000を超える場合（検死によりGrishaが多数の小さな詳細を示している場合）、一部のマシンでは再描画が数秒に達する可能性があり、インターフェイスの応答性が少し低下します。

悲しいことに、すべての要素がinnerHTMLを介して描画されるわけではありません。 例として、IE8 では 、 tbody



要素にinnerHTMLを設定することはできません 。 Google Chromeでは、テーブルヘッダー（ th



）のinnerHTMLによるレンダリングが不十分です。 innerHTMLを介してそこに挿入するものはすべて、私には不明な理由でプレーンテキストに切り捨てられます。 Pruflinkはそうではありません-個人的な経験からの情報。 おそらく今ではすでに修復されていますが、堆積物は残っています。

したがって、innerHTMLは、迅速で汚いハックのようなものです。 一般的なケースでは信頼性が低く、多くの副作用があります。実際、私たちはそのような書き方をするために学校の9年生ではありません。 プロから-膝の上に実装。

HTMLパーサー

率直に言って、このオプションは、最後の悲しい問題であるinnerHTMLのみを解決します-作成された要素には極度の細心の注意が必要です。 しかし、主にVDOMを実装するために必要になるため、言及する価値があります。

どのように機能しますか？ はい、動作します。 HTMLを解析し、各ノードのdocument.createElement



を呼び出してから、属性を設定します。 次にelement.innerHTML = ''



を実行し、受け取った要素をinsertBefore



appendChild



/ insertBefore



呼び出しappendChild



。

まあ...まず、私たちは要素を殺す問題を解決しませんでした。 第二に、HTML解析では、この世界ではすべてがそれほどスムーズではありません。

HTML解析はXMLドキュメントの解析方法に関するものであり、クライアント側のパーサーでは最も頻繁に使用されます 食べ物用 ストリームパーサー。 ダダ、 JavaのStAXに似ています 。 XMLストリームパーサーを食べることは健康に良いことが証明されています。 なんで？ はい、高速かつ簡単に記述できるためです。 XMLの場合のように、このタスクにクラシックウッドパーサーを使用しないでください。 ここでは単に必要ありません。

HTMLパーサーの世界ではすべてが優れていますが、1つだけ例外があります。ブラウザーに組み込まれているものはありません。 MDN はDOMParserに言及していますが 、まだ実験的であり、おそらく出力でツリーを提供します。 ええ、クライアントサイドでは、ツリーを歩き回ってdocument.createElement



を呼び出すだけでは十分ではありませんでした。 一言で言えば、彼は奇妙です。 彼に触れないようにしましょう。 htmlparser2があります-npmにあります 。 イベントストリームパーサーですが、フレームワークのイデオロギーとしてサードパーティの依存関係を使用できないため、私自身は使用しませんでした。 そして、これはJohn Rezigのコードの記事と例です （jQueryから分離してください）。指ですべてを説明し、簡単なパーサーのコードを提供します。 正規表現で機能するため、気に入らない。 このzeloは面倒です。 しかし、それはかなり実行可能です。 私は長い間、TypeScript用に再設計されたこの記事のコードのみを使用しました（私は告白します）。 ただし、文字列の比較を最小限に抑え、仮想要素の作成をサポートするために、単純なステートマシンのストリームパーサーに置き換えました（これについては、今日共有します）（たとえば、Johnはファイルを作成するのに少し不便でした）。

Vdom self

そして、パフォーマンスと要素上のinnerHTMLのうるささの両方の問題を解決する、最もトリッキーなアプローチにたどり着きました。 つまり、HTMLパーサーを使用すると、HTMLを突然解析できますが、 document.createElement



ではなく各要素を呼び出すことができますが、タグ名と属性を格納するオブジェクトを作成するだけです。 このまさにオブジェクトは、 仮想DOM-nodeと呼ばれ、それらの組み合わせ- 仮想DOM-treeまたはVDOMです。 ここで、 var a = {};



してJSで1000個のオブジェクトを作成することに注意してくださいvar a = {};



-それは速いです。 とても速い。 しかし、1000個の実際のDOMノードの作成は遅いです。 この状況から、sobsno、および生産性の向上につながります。

OK、作成しました。 そして、私たちはこの良いことで何をしますか？ ズボンを脱いで走る ズボンを脱ぐ必要はありませんが、実行する必要があります。VDOMツリーの構造を既に描画されているものと比較し、これから何らかの種類の差分パッチを作成します（追加する必要があるもの、削除するもの、属性をドロップする場所、コンテンツを変更する場所）既存のDOMツリーにロールします。 これは、マージ中にお気に入りのgitで発生するのとまったく同じです。 幸いなことに、プログラミングでdiffを作成するタスクは非常によく知られています- 最も一般的なサブシーケンスを見つけることによって、突然グーグルで検索されます。 動的プログラミングによって解決されます。 アルゴリズムには2次の複雑さがあります。 優れた大学では、この問題の解決策は最初のコースで研究されていますが、ここでは論文を説明し、それを木に適応させる方法を説明します。

UPD： コメントで、私はLCSがこのタスクに最適ではないという主題にすでにトマトを投げました。LISを使用する必要がありますが、記事とコードをそれほど速く書き直すことはできません。 そのため、差分の計算を扱う部分をより厳密に最適化できることに注意してください。

その結果、VDOMアプローチは、変更されていない不要な要素を作成しないツリー要素を削除せず、メモリを大幅に節約し、イベントサブスクリプションを節約します（要素が破棄されない場合）。ただし、HTML要素を作成するよりもCPUに比較を強制します。 また、これにより、画面上の1000個の要素のうち1つだけが変更されたときに、パフォーマンスが大幅に向上します。

さあ始めましょう

左側のtextarea



で構成される小さなアプリケーションを作成します。このアプリケーションでは、HTMLを操作および/または変更し、右側のウィンドウで作業結果を確認します。 追加のライブラリはありません-TypeScriptとブラウザだけです。 彼らが言うように、私たちは空から魔法をかけます。

ご存知のように、最初は行ごとの分析でこの記事に多くのコードを追加したかったのですが、以前の記事を念頭に置いて、これをやろうとは思いませんでした。 コード自体が読みやすさを低下させ、悲しくなります。 したがって、許可を得て、Githubへのリンクを提供し、どのように機能するのかを説明します。 VDOMは、HTMLパーサー、直接コンパレーター、バッチ計算機、およびapp.tsの3つの主要コンポーネントで構成され、これらすべてapp.ts



まとめて機能させます。

パーサー

ここで予約する必要があります。 私が理解しているように、React.jsはHTMLパーサーなしで機能します。これは、テンプレート（jsx / tsx）が既に対応するノード作成呼び出しに組み込まれているためです。 これはパフォーマンスを改善する良い動きですが、ご存知のとおり...独自のテンプレート言語を作成し、そのためのコンパイラを作成することは、この記事を書いたときの私の計画にはありませんでした。 したがって、私たちは手で裸のHTMLを解析します。 そのような実装は、私たちにどこにでも工芸を埋め込む能力を保証し、私が意味することを理解していれば、純粋に教育学的な奇妙さを避けることができます:)それでは、行きましょう。

スタック

JavaScriptにはスタックを操作するための効果的なツールが含まれていないため、必要なツールが必要です。 したがって、 単純なスタックを作成します 。 コメントはありません。

ノードコンストラクター

ご存知のように、JavaScriptの観点では、HTMLドキュメントはノードで構成されています。 その一部は、HTMLInputElement（ input



タグ）、HTMLDivElement（ div



タグ）などの非常にHTML要素です。 そして、いくつかはしません（テキスト、コメント）。 使用可能なすべてのノードタイプがMDNにリストされています 。 シンプルなものから始めます-いわゆるインターフェースを宣言します 「ノードのコンストラクター」。 HTMLをハードコードしないために、パーサーにdocument.createElement



を呼び出し、VDOMと同じパーサーをDOMに使用します。 私の実装では、このように見えます。 ご覧のとおり、HTML要素、テキスト（コンテンツ）、コメントの3種類のノードに制限されています。 インターフェイスは非常にシンプルで、3種類すべてのノードを作成する機能を提供します。また、HTML要素に対しては属性のインストールも提供します。 興行から遠く離れないようにするために、実際のHTMLノードにすぐに実装します。 とても簡単です。 子供でもそれを処理できます。

ここで、VDOMノードをどのように保存するかを考えます。 タイプに加えて、ノードについて知っておくべき重要なことは何ですか？ HTML要素の場合、タグと属性。 コメントとテキストの場合-コンテンツ。 他のすべてに加えて、子ノードのリストも同様に重要です。 素晴らしい。 型のインターフェイスとenum



を記述した後、コンストラクタ自体を実装します： このように 。

HTMLパーサー

パーサー-これは、 状態の数が限られているようなものです。 彼女は のんびり 渡されたHTMLを文字ごとに追跡し、現在の文字に応じて状態を変更します。 状態から状態に遷移すると、パーサーはノードコンストラクターメソッドをプルし、適切なアクションを実行します。

たとえば、パーサーの文字を読み取り、誰にも触れません。 Op-met <



、彼が彼を見た場所を記憶し、状態を「注意深く耳を傾け、今はHTMLタグがある」に変更します。 読んで。 Op-空白文字を満たします。 ここでは、タグの名前です。 彼は<



に出会った場所を覚えており、そこから現在の位置までテキストをかぎます-ここにタグ名があります。 したがって、コンストラクターノードをプルし、タグ名を渡してcreateを呼び出す必要があります。 さらに、パーサーはすべての空白文字をスキップし、 >



場合、元の状態に戻ります。 そして、アルファベットの文字を見た場合、属性名=



、引用符で囲まれた属性の値もキャッチし、コンストラクターノードをプルします。

作成したタグをスタックに保存します。 開始タグに到達するたびに、スタックに配置します。 コンストラクターを介して要素を作成する場合、スタックの現在の最上部を親要素として指定します。 つまらない。 大学の最初の数年で電卓を書いたとき、誰もが少なくとも一度は似たようなことをしたと思います。

すべての状態、および遷移中のアクションは、 状態マシンに入れます 。これは技術的には巨大です 辞書、頭の中の血まみれのC＃ 「状態」->「アクションの説明」という形式のハッシュオブジェクト。 この場合のアクションの説明は、3つの部分で構成されています。

• 州の入り口で実行される機能。
• 状態の終了時に実行される関数。
• 次に読み込まれる文字ごとに呼び出される関数。

これら3つの関数をIStateInfoと呼ばれるものに組み合わせました。 そこで、パーサーの考えられるすべての状態を説明しました。 パーサー自体は、いくつかの有用なテスター機能を提供しました（これは、現在の文字を確認するとき、n文字が戻る、現在の文字の次のm文字がそのような単語に追加されるかどうかなどです）。 fix()



関数は特に区別されます：パーサーの状態を変更すると、数文字をさらに移動すると、保存された位置と現在の位置の間のテキストをかじることができるという考えで、現在のシンボルの位置を記憶します。 記憶された位置から現在の位置へのテキストの断片化は、 cut()



関数によって実行されます。 通常、 cut()



呼び出した後、ステートマシンはパーサーに信号を送信します-「ああ、見て、開始タグがキャッチされました。それはその名前です」。 なぜそんなに複雑なのですか？ まあ...私はth約者です。 不必要に余分な行を作成しないパーサーを作成しました。

実は、後で、パーサーの考えられるすべての状態と考えられるすべてのアクションをリストしました-彼らが言うように、ステートマシンをプログラムしました 。 属性名には、属性、自己終了タグ、文字-



および:



を囲む引用符に関連する多くのニュアンスがあります。 ここでは、これらの各ケースの詳細な咀wingを省略します。すべてがコードに含まれているため、必要に応じて自分で確認できます。

別の機能： style



script



とscript



パーサーは個別に切り取りと追加を行い、パーサーユーザーが決定する それらを実行するか、慈悲を持つ それらで次に何をすべきか。 たとえば、スクリプトのeval



を作成できます。 しかし、スタイルをどうするかは、私にとっても不明確な質問です。 私の実装で考慮されていない唯一のものは、これらのタグの可能性のあるトリッキーな構造です。 script



内で、 return '</script>';



スピリットreturn '</script>';



テキストに遭遇したとしましょうreturn '</script>';



、パーサーはこれをscript



タグを閉じると誤って認識しscript



。これは不快ですが、簡単に修復されます 私は怠け者です 。

差を計算する

そのため、現在の段階では、HTMLの一部を渡し、それを実際のDOM要素またはVDOM要素に解析できる有効なHTMLパーサーがあります。 完璧です。

いくつかのHTMLが既に画面にレンダリングされていると想像してください。少し変更したいと思います。 それを受け取り、調整を行い、パーサーにVDOMコンストラクターをフィードします。 VDOMノードのリストを取得します。 次に、画面に表示されるHTMLと、パーサーが解析した事実との差を計算する必要があります。 実際、HTMLが描画される親ノードを取得し、そのすべての子の配列を取得し、HTMLパーサーが作成した仮想子の同じ配列と比較する必要があります。 そして、私が「比較する」と言うとき-私は「一致するかどうか」という質問に答えるだけでなく、いわゆる 「バッチの更新」-古い木材から新しい要素を取得するために追加する要素と削除する要素のリスト。 その後、変更の結果のバンドルは、すでにレンダリングされて変更されていないHTMLを破壊せず、影響を受けたノードのみを巧妙に変更するだけで、すでにレンダリングされたHTMLにロールされます。 この操作はVDOM updateと呼ばれます。 そのようなもの。 しかし、まず最初に。

比較キャッシュ

最初に、HTMLノードとVDOMノードを比較する方法を学ぶ必要があります。 これは比較的簡単に行われます：

1. タイプを比較します。 一致しない場合、ノードは異なります
2. 両方のノードがテキストまたはコメントである場合-コンテンツを比較します。 一致しますか？ 同じです。 一致しませんか？ 違う。
3. 属性の数を比較します。 一致しませんか？ 違う。
4. 属性の存在とその値を比較します。 一致しないものがありましたか？ さて、あなたはポイントを得る。
5. 子孫ノードごとに手順1〜4を実行します。
6. これを読んだ場合、ノードはまだ一致しています。

ご覧のとおり、毎回ノードを最初から比較するのは時間がかかります。 主にステップ5の再帰が原因です。 したがって、1つの更新のフレームワーク内に存在し、ノードの相互の比較結果を保存するキャッシュコンパレーターを作成しました。 したがって、2つのノードが異なるという事実がすでにインストールされている場合、再度インストールされるのではなく、キャッシュから取得されます。 同じコードがたくさん 。

LCS

これは、Longest Common Subsequenceの略です。 このクラスは基本的に、動的プログラミングを使用してLCS問題を解決するためのマトリックスです。 入力に2つの配列（一方は実際のノード、もう一方は仮想ノード）を渡し、上記で説明した比較キャッシュにもフィードします。 次に、 produceModifyBatch



を呼び出して、 バッチエントリの配列（一番下で説明）を取得します 。これは、そのようなノードで何を行う必要があるかを示しています。

まず、 produceModifyBatch



を呼び出した後、LCSは配列の最初と最後から同じ要素を切り捨てます（ doSkips



関数）。 次に、残りのデータは動的プログラミングマトリックスに基づいています- このビデオで説明したとおりです。 次に、それをバイパスして、 削除するノードと追加するノードを決定します（ビデオでも説明されています）。 この段階では、 更新する必要があるノードのリストを取得しないことに注意してください。 結果には削除と追加のみが含まれますが、！ ただし、同じ場所へのノードの削除と追加（または追加と削除）はupdateです。 normalizeBatch



操作は、1回の操作で隣接する追加と削除を折りたたむ- 更新 、バッチエントリのプライマリ配列の再フォーマットを行うだけです。 結果は最終的に幸せなユーザーに返すことができます。

LCSはVDOMの最も難しい部分であり、多くの人にとって恐ろしい魔法のように見えます。 あなたが見ることができるように、彼らが言うように、アルゴリズム自体はトリッキーですが、非常に理解可能です。 ちなみに、その複雑さは二次ですが、心配することはありません。 変更が比較的少なく、要素の束の途中にある場合、それらのほとんどはdoSkips



ステージでdoSkips



られ、その結果、動的プログラミングマトリックスのサイズが3x3を超えることはまれです。 もちろん、ユーザーがお互いの下に立って1万個のボタンを再描画しない場合。 実際には、そのようなケースはまれです。 したがって、要素が2つまたは1つある場合はLCSマトリックスを作成せず、結果を手で処理するのが理にかなっています。 実際には、多くの場合、要素の大きなネストがあります。 ただし、JSの呼び出しスタックを中断するには不十分です（さらに再帰的な処理を行います）。 そして私たちは生きています。 , React.js — . — . .

DOM Differ

, update, parent-, LCS-, HTML- . , , — , . コメントはありません。

! !

update: parent-, VDOM-. LCS, update batch. , , , , — . , — updateAttributes



, update, (, VDOM--). : , — , parent.insertBefore



. , — parent.removeChild



. . .

diff



, update batch-. , .

揃って

HTML- , app.ts , .

まとめ

, VDOM. , , , JS-. -, , HTML- — , .

, .