Virtual DOMでなく生のDocumentFragmentを与えてDOMを差分更新したいって話

[この記事は自サイトとのクロスポストです。](https://piro.sakura.ne.jp/latest/blosxom/webtech/javascript/2020-03-09_dom-updater.htm)

# 概要

FirefoxのアドオンやChromeの拡張機能向けに、名前空間をまたいでDOMに変更を差分適用したい場面で使える、Virtual DOMでないReal DOMで差分適用する、`webextensions-lib-dom-updater`という名前のライブラリをつくりました。

* [リポジトリ](https://github.com/piroor/webextensions-lib-dom-updater)
* [npmモジュールの公開ページ](https://www.npmjs.com/package/webextensions-lib-dom-updater)

# どう使うの？

クライアント側でタブの情報を取得して、サーバー側でそれをレンダリングする、という場面であれば以下のようになります。

```javascript:クライアント側（制御担当）
// IDからタブのオブジェクトを得る（WebExtensionsのAPI）
const tab = await browser.tabs.get(tabId);
// プロセスをまたいで、レンダリングして欲しい内容を送る
browser.runtime.sendMessage(
  '受信側の識別子',
  // ↓テンプレート記法でHTMLのコード片をそのまま生成
  `
    <span id="tab"
          class="${tab.active ? 'active' : ''}">
      <span id="throbber"
            class="${tab.status}">
        <span id="throbber-image"
              class="${tab.status}"></span>
      </span>
      <img id="favicon"
           class="${tab.status}"
           src="${tab.favIconUrl}">
      <span id="label">${tab.title}</span>
    </span>
  `.trim()
);
```

```javascript:サーバー側（画面描画担当）
import { DOMUpdater } = './dom-updater.js';

// 他のプロセスからのメッセージを待ち受ける（WebExtensionsのAPI）
browser.runtime.onMessageExternal(message => {
  // 反映先の要素
  const before = document.getElementById('container');

  // 反映する内容をDocumentFragmentにする
  const range = document.createRange();
  range.setStart(document.body, 0);
  const after = range.createContextualFragment(message);
  range.detach();

  // DocumentFragmentの内容でbeforeと異なる部分があれば、
  // それをbeforeに差分適用する
  DOMUpdater.update(before, after); // ←これを作った。
});
```

# どの辺に新規性があるの？

Virtual DOMでなく生のReal DOMを更新内容として指定する[^not-only-document-fragment]ので、**Virtual DOMの独自記法を覚えなくていい**です。利点はそれだけです。

[^not-only-document-fragment]: 例ではDocumentFragmentを使ってますが、普通のElementでも構いません。

既に同じ事をするライブラリが世の中にはあったのかもしれませんが、自分には見つけられませんでした。どなたかご存じでしたら教えてください……

→と書いていたら、[morphdom](https://github.com/patrick-steele-idem/morphdom)という似た趣旨のライブラリが既にあると教えて頂きました。今回実装したものとの比較を最後に追記しました。

# なんで作ったの？

[Tree Style Tab](https://addons.mozilla.org/firefox/addon/tree-style-tab/)というFirefox用アドオンで、「他のアドオンから指示して、タブの中に任意のUI要素を追加する」という事をやるために作りました。

![（スクリーンショット：Tree Style Tabでの利用例）](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/61387/21759431-a51b-5823-af73-7ea448314c7a.png)
見た目を元々のタブに合わせているのでちょっと分かりにくいですが、このスクリーンショットの左側で「Add-ons - Mozilla | MDN」というラベルを伴って表示されている「細いタブっぽい物」が、**別のアドオンから指示された通りの内容を、このライブラリによる差分適用で埋め込んだ**部分です。

アドオン間での通信ではJSONオブジェクト形式のメッセージしか扱えないため、こういう事をやろうとすると

* 挿入するUI要素の内容を、どんな書式でどうやって指定させるか
* 挿入されたUI要素を、どんな書式でどうやって指定して更新させるか

ということを決める必要があります。

## Virtual DOM使えばいいやん

DOMの変更の差分適用といえば既存のVirtual DOM専用のライブラリは既にいくつもあって、

* https://github.com/Matt-Esch/virtual-dom/
* https://github.com/snabbdom/snabbdom
* https://github.com/yelouafi/petit-dom

このあたりの記法をそのまま使えばいいといえばいい話です。

が、どれもべつに「スタンダード」というわけではないようなので、どれを選んでも後で文句を言われそうな気がします。宗教戦争がもしあるなら、そこに参戦したくはないですし、ただでさえ「Tree Style Tabが他のアドオン向けに提供する独自のAPI」というめちゃめちゃニッチな場面なので、こんな限定された場面のために新たに（もし普段から使っている物があるなら、それとは別のライブラリ由来の）独自の記法を覚えてもらうのは忍びないです。というか、自分がこれ以上覚えたくありません。

その点、HTMLのソースを文字列で指定してDOMの標準的な機能でNodeやDocumentFragmentにするという事にしておけば、多少冗長ではあるものの、「デジュールスタンダードなんで」と言ってしまえます。**技術選択で悩まなくてもよくするためだけの選択**というわけです。

# どうやってるの？

技術的には、[タブの効率のいい並べ替え処理](https://qiita.com/piroor/items/e9b0a815231619b7e905)でも使ったdiffのアルゴリズムの応用となっています。具体的には、[Pythonから移植されたdiffの実装](https://github.com/piroor/webextensions-lib-dom-updater/blob/master/src/diff.js)に含まれている`SequenceMatcher`という機能を使って、以下の要領で差分を愚直に反映しています。

1. `nodeValue`を比較して、`null`でなく、値が異なっていれば、`after`の`nodeValue`を`before`のそれに代入する。
2. `childNodes`を比較して、追加、削除、置換を反映する。同値の物があれば、再起的に反映する。
3. `attributes`を比較して、追加、削除、置換を反映する。

以下の説明に登場するコード片は、特に説明が無い限りは、前述の例の`DOMUpdater.update(before, after)`の実装の中身と解釈して下さい。

## `nodeValue`の比較

これは単純に比較演算子で比較するだけです。

```javascript
if (before.nodeValue !== null ||
    after.nodeValue !== null) {
  if (before.nodeValue != after.nodeValue)
    before.nodeValue = after.nodeValue;
  return;
}
```

[`nodeValue`は、`Element`や`DocumentFragment`では常に`null`ですが、`Text`や`CDATA`では値を持つ](https://developer.mozilla.org/docs/Web/API/Node/nodeValue)ので、これで内容テキストの変化を反映しています。

## `childNodes`の反映

ここで`SequenceMatcher`が登場します。これは[unified diffなどの形式に成形される前のdiff結果の内部表現](https://qiita.com/piroor/items/e9b0a815231619b7e905#javascript%E3%81%A7%E3%81%AEdiff%E3%81%AE%E5%AE%9F%E8%A3%85)を得る物で、今回使ったPython由来の実装では以下のような結果を得られます。

```javascript
const before = 'abcdfg'.split('');
const after  = 'acdefh'.split('');
const matcher = new SequenceMatcher(before, after);
console.log(matcher.operations()); // 差分を計算
/*
  [
    // tag, fromStart, fromEnd, toStart, toEnd
    ["equal",0,1,0,1],
    ["delete",1,2,1,1],
    ["equal",2,4,1,3],
    ["insert",4,4,3,4],
    ["equal",4,5,4,5],
    ["replace",5,6,5,6]
  ]
*/
```

結果の数字は要素のインデックスですが、カーソル位置と解釈すると分かりやすいです。

|カーソル位置|0| |1| |2| |3| |4| |5| |6|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|before| |a| |b| |c| |d| |f| |g| |
|after| |a| |c| |d| |e| |f| |h| |

そうすると、`matcher`が返した各operationの意味は以下のようになります。

|operation|意味|
|---|---|
|`["equal",0,1,0,1]`|`before`のカーソル位置0から1の内容（`a`）と、`after`のカーソル位置0から1の内容（`a`）が同値|
|`["delete",1,2,1,1]`|`before`のカーソル位置1から2の内容（`b`）が、`after`のカーソル位置1の場所（`a`と`c`の間）から削除された|
|`["equal",2,4,1,3]`|`before`のカーソル位置2から4の内容（`c`, `d`）と、`after`のカーソル位置1から3の内容（`c`, `d`）が同値|
|`["insert",4,4,3,4]`|`before`のカーソル位置4の場所（`d`と`f`の間）に、`after`のカーソル位置3から4の内容（`e`）が挿入された|
|`["equal",4,5,4,5]`|`before`のカーソル位置4から5の内容（`f`）と、`after`のカーソル位置4から5の内容（`f`）が同値|
|`["replace",5,6,5,6]`|`before`のカーソル位置5から6の内容（`g`）が、`after`のカーソル位置5から6の内容（`h`）に入れ替わった|

`SequenceMatcher`はこのように、

* 配列っぽい形式で与えられて
* 各要素同士の一致・不一致を比較できる

物であれば、何でも差分を求められます。

ただ、[DOMの`Node`同士が同値かどうかは`Node.isEqualNode`で比較できます](https://developer.mozilla.org/docs/Web/API/Node/isEqualNode)が、今回は「属性値や内容が変わったらそこだけ差分適用したい」「ノード自体はなるべく使い回したい」という状況です。なので、以下のようなメソッドを通して単純化した物を比較するようにしました。

```javascript
_getDiffableNodeString(node) {
  if (node.nodeType == node.ELEMENT_NODE)
    return `element:${node.tagName}#${node.id}`;
  else
    return `node:${node.nodeType}`;
}
```

この結果を使って、

```javascript
const beforeNodes = Array.from(before.childNodes, this._getDiffableNodeString);
const afterNodes = Array.from(after.childNodes, this._getDiffableNodeString);
const nodeOerations = (new SequenceMatcher(beforeNodes, afterNodes)).operations();
```

と差分を計算し、

```javascript
for (const operation of nodeOerations.reverse()) {
  const [tag, fromStart, fromEnd, toStart, toEnd] = operation;
  switch (tag) {
    case 'equal':
      ...
      break;
    case 'delete':
      ...
      break;
    case 'insert':
      ...
      break;
    case 'replace':
      ...
      break;
  }
}
```

と、operationの種類ごとに処理を振り分けます。

なお、ここでは`nodeOerations.reverse()`として、後ろから前へと逆順にオペレーションを反映するようにしています。これは、そうしないと挿入や削除の処理でカーソル位置がずれていってしまうからです[^reversed-order]。

[^reversed-order]: カーソル位置のオフセットを適宜計算する方法もありますが、面倒なのでラクな方にしてしまいました。なお、「後ろからやるといい」というのは[Reef.jsという計量フレームワーク](https://github.com/cferdinandi/reef)の作者の人による[DOM diffing with vanilla JS: part 2 | Go Make Things](https://gomakethings.com/dom-diffing-with-vanilla-js-part-2/)という記事を参考にしました。

それぞれのオペレーションは、前述のカーソル位置とDOM Rangeを愚直に対応させると簡単に反映できます。一番複雑な`replace`の場合でも、以下の通りです。

```javascript
const beforeRange = before.ownerDocument.createRange();
const afterRange = after.ownerDocument.createRange();

...

case 'replace':
  beforeRange.setStart(before, fromStart);
  beforeRange.setEnd(before, fromEnd);
  beforeRange.deleteContents();
  afterRange.setStart(after, toStart);
  afterRange.setEnd(after, toEnd);
  beforeRange.insertNode(afterRange.cloneContents());
  break;
```

`equal`の場合は、差分適用処理を再帰的に反映します。これは前からやっても構いません。

```javascript
case 'equal':
  for (let i = 0, maxi = fromEnd - fromStart; i < maxi; i++) {
    this.update(
      before.childNodes[fromStart + i],
      after.childNodes[toStart + i]
    );
  }
  break;
```

## `attributes`の反映

要素ノードの場合は属性も差分適用します。属性同士も同値かどうか比較しやすくするために、`"属性名:属性値"`という文字列にして、内容でソートしてから差分を求める事にします。

```javascript
if (before.nodeType == before.ELEMENT_NODE &&
    after.nodeType == after.ELEMENT_NODE) {
  const beforeAttrs = Array.from(before.attributes, attr => `${attr.name}:${attr.value}`).sort();
  const afterAttrs = Array.from(after.attributes, attr => `${attr.name}:${attr.value}`).sort();
  const attrOerations = (new SequenceMatcher(beforeAttrs, afterAttrs)).operations();
  ...
}
```

属性の場合、`equal`では特にやる事はありませんし、それ以外の操作ではノードと違って順番を気にしなくてもいいので、やることはだいぶ単純になります。`replace`でも以下の通りです。

```javascript
case 'replace':
  const insertedAttrs = new Set();
  // まず最初に、追加・上書き分の属性値を反映する。
  for (let i = toStart; i < toEnd; i++) {
    const attr = afterAttrs[i].split(':');
    const name = attr[0];
    const value = attr.slice(1).join(':');
    before.setAttribute(name, value);
    // 追加・上書き済みの属性のリストを持っておく。
    insertedAttrs.add(name);
  }
  // 次に、削除された属性値のうち、
  // 追加・上書き済みの属性のリストにないものだけ削除する。
  for (let i = fromStart; i < fromEnd; i++) {
    const name = beforeAttrs[i].split(':')[0];
    if (insertedAttrs.has(name))
      continue;
    before.removeAttribute(name);
  }
  break;
```

# テストについて

今回、地味に困ったのが自動テストの仕方についてです。

元々このライブラリはTree Style Tabの一部として実装していたので、当初はTSTの単体テストの仕組みの中で実行していたのですが、この記事を書くにあたってnpmパッケージにしようとして、いろいろつまずく羽目になってしまいました。

TSTはFirefox ESR68以降を想定して開発しているので、Firefoxが実装してるJavaScriptの新しい機能はガンガン使うようにしてます。モジュールの定義もESModulesの書式に則っています。

ということは、テスト対象である`DOMUpdater`を読み込む**テストファイルの方もESModulesの書き方にしないといけません**。ですが、そうなるとNodeでのテストでおなじみのMochaがESModulesのテストに対応しておらず、そこで詰んでしまったわけです。

Node.jsでもESModulesが使えるようになってからそこそこ時間が経っているので、ESModules対応のテスティングフレームワークがありそうなものだとは思ったのですが、Node.jsの動向に疎く、探し方が悪いのかMochaとBabelを組み合わせて無理矢理テストするという話しか見つけられませんでした……

せっかくネイティブにESModulesで書いてるのに、テストのためだけにトランスパイラを噛ますというのもあほらしかったので、現在は、とりあえずCIだけ回せればいいかなということで、TSTの単体テストのために書いた単純なテストランナーを持ってきて、failやerrorがあれば`process.exit(1)`するようなスクリプトを実行するようにしてお茶を濁しています。いいやり方をご存じの方がいらっしゃいましたら、どなたかフィードバックを頂けると助かります。

~~同様の理由で、ESLintも実行できない状態になってしまっています。`package.json`で`"type":"module"`と書いてあると**ESLint自身の実行時にエラーになってしまって**、しかしどこで詰まってるのかもよく分からず……どういうエラーになってるかは[Travis CIでの結果](https://travis-ci.org/piroor/webextensions-lib-dom-updater/builds/659980250?utm_medium=notification&utm_source=email)をご覧頂けると幸いです。実行環境によってはこのエラーが起こらなくて、謎は深まるばかりです。~~

~~ESLintについては、とりあえず自動テストが走るなら文法エラーということはなかろう、という雑な判断で今のところはほったらかし状態です。こちらも識者の方のフィードバックを頂けると非常に嬉しいです。~~

当初ESLintがエラーになると書いてたんですが、[ESLintが古い＆Node.jsが新しいという組み合わせだとハマる](https://twitter.com/saneyuki_s/status/1237011249944096769)と教えて頂いて、[`.eslint.cjs`という名前で明示的にCommonJS形式の設定ファイルを指定できるようになったバージョン6.8.0](https://eslint.org/blog/2019/12/eslint-v6.8.0-released)をESLintの最低バージョンに指定し直したら、無事通るようになりました。よかったよかった。


# まとめ

ということで、既存のライブラリを見つけられなかったので、DOMのDocumentFragmentで差分適用するライブラリを作ってみた、という話でした。

蓋を開けてみれば難しいことは何もしてません（難しいことは全部diffのライブラリがやってくれてる……）し、誰得すぎて詳しく解説する意味もなかったような気がものすごくします。ここまで読んで下さった方、Virtual DOMに馴染めないロートルおじさんの戯れにお付き合い頂きありがとうございました。

ESModulesなnpmモジュールの~~lintと~~テストについて知見をお持ちの識者の方のツッコミお待ちしております。


# 追記：[morphdom](https://github.com/patrick-steele-idem/morphdom)との比較

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">細かい要件に合うかまで見ていないのですが、既存ライブラリだと <a href="https://t.co/QHdPLltM63">https://t.co/QHdPLltM63</a> が近いように感じましたがどうでしょうか。</p>&mdash; ofk (@ofk) <a href="https://twitter.com/ofk/status/1236862834480304128?ref_src=twsrc%5Etfw">March 9, 2020</a></blockquote>

ということで、先行実装として[morphdom](https://github.com/patrick-steele-idem/morphdom)という物があると教えて頂きました。やっぱりあった……そりゃそうですよね……

中を見てみたところ、morphdomはDOMUpdaterとは異なり、diffのアルゴリズムは特に使っていないようでした。そうなると、気になるのは差分の計算やDOM Range操作のオーバーヘッドがどのくらいあるのかです。[テストケース](https://github.com/piroor/treestyletab/blob/86a697e3afb0045a0d53b5cbb7cd06f6cfa050cb/webextensions/tests/test-dom-updater.js)でベンチマークを取ってみた[^benchmark]ところ、以下のような結果になりました。

[^benchmark]: どうも、後に実行する物ほど遅くなるらしく、公平にするために毎回実行順をシャッフルするとか色々工夫が必要でした。

|実装|5000回の実行の所要時間の合計|1回あたり平均所要時間|
|---|---|---|
|DOMUpdater（DocumentFragmentを与える）|15030ミリ秒|約3.01ミリ秒|
|morphdom（文字列を与える）|18899ミリ秒|約3.78ミリ秒|
|morphdom（DocumentFragmentを与える）|18496ミリ秒|約3.70ミリ秒|

* Runtime: Firefox Nightly 75.0a1 (2020.3.9)
* OS: Windows 10
* CPU: Intel Core i5-8250U 1.80GHz
* RAM: 16.0GB

一応この中ではDOMUpdaterが最速という結果になりました。とはいえ、1回あたりにすると誤差みたいなものですし、比較するノードの規模が小さければdiff計算のオーバーヘッドの方が大きくなるだろうとは思いますので、参考程度に見て頂くのがよさそうです。