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

この記事は自サイトとのクロスポストです。

概要

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

• リポジトリ
• npmモジュールの公開ページ

どう使うの？

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

クライアント側（制御担当）

// 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()
);

サーバー側（画面描画担当）

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を更新内容として指定する¹ので、Virtual DOMの独自記法を覚えなくていいです。利点はそれだけです。

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

→と書いていたら、morphdomという似た趣旨のライブラリが既にあると教えて頂きました。今回実装したものとの比較を最後に追記しました。

なんで作ったの？

Tree Style TabというFirefox用アドオンで、「他のアドオンから指示して、タブの中に任意のUI要素を追加する」という事をやるために作りました。

見た目を元々のタブに合わせているのでちょっと分かりにくいですが、このスクリーンショットの左側で「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にするという事にしておけば、多少冗長ではあるものの、「デジュールスタンダードなんで」と言ってしまえます。技術選択で悩まなくてもよくするためだけの選択というわけです。

どうやってるの？

技術的には、タブの効率のいい並べ替え処理でも使ったdiffのアルゴリズムの応用となっています。具体的には、Pythonから移植されたdiffの実装に含まれているSequenceMatcherという機能を使って、以下の要領で差分を愚直に反映しています。

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

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

nodeValueの比較

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

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

nodeValueは、ElementやDocumentFragmentでは常にnullですが、TextやCDATAでは値を持つので、これで内容テキストの変化を反映しています。

childNodesの反映

ここでSequenceMatcherが登場します。これはunified diffなどの形式に成形される前のdiff結果の内部表現を得る物で、今回使ったPython由来の実装では以下のような結果を得られます。

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で比較できますが、今回は「属性値や内容が変わったらそこだけ差分適用したい」「ノード自体はなるべく使い回したい」という状況です。なので、以下のようなメソッドを通して単純化した物を比較するようにしました。

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

この結果を使って、

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

と差分を計算し、

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()として、後ろから前へと逆順にオペレーションを反映するようにしています。これは、そうしないと挿入や削除の処理でカーソル位置がずれていってしまうからです²。

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

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の場合は、差分適用処理を再帰的に反映します。これは前からやっても構いません。

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

attributesの反映

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

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でも以下の通りです。

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での結果をご覧頂けると幸いです。実行環境によってはこのエラーが起こらなくて、謎は深まるばかりです。

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

当初ESLintがエラーになると書いてたんですが、ESLintが古い＆Node.jsが新しいという組み合わせだとハマると教えて頂いて、.eslint.cjsという名前で明示的にCommonJS形式の設定ファイルを指定できるようになったバージョン6.8.0をESLintの最低バージョンに指定し直したら、無事通るようになりました。よかったよかった。

まとめ

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

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

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

追記：morphdomとの比較

細かい要件に合うかまで見ていないのですが、既存ライブラリだと https://t.co/QHdPLltM63 が近いように感じましたがどうでしょうか。

— ofk (@ofk) March 9, 2020

ということで、先行実装としてmorphdomという物があると教えて頂きました。やっぱりあった……そりゃそうですよね……

中を見てみたところ、morphdomはDOMUpdaterとは異なり、diffのアルゴリズムは特に使っていないようでした。そうなると、気になるのは差分の計算やDOM Range操作のオーバーヘッドがどのくらいあるのかです。テストケースでベンチマークを取ってみた³ところ、以下のような結果になりました。

実装	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計算のオーバーヘッドの方が大きくなるだろうとは思いますので、参考程度に見て頂くのがよさそうです。

1. 例ではDocumentFragmentを使ってますが、普通のElementでも構いません。 ↩

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

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