Markdownを変換したHTML同士の差分を生成する

編集履歴が見やすくなりました - Qiita Blog で紹介したように、編集履歴の差分をより分かりやすく表示できるようにしました。この記事では、この差分表示の実装方法について説明します。

Markdiff

差分表示のための実装は、r7kamura/markdiff というライブラリの形で公開しています。Markdiffという名前には、Markdownのdiffという意味を込めています。Markdownへの変換は increments/qiita-markdown が行ってくれるので、変換後のHTMLを2つ渡すと、差分を表示するためのHTMLを返してくれるという仕組みです。差分表示において、このライブラリがCSSによる装飾以外のほぼ全ての仕事を担っています。

使用例

簡単な例で使い方を説明します。以下のように、まず Markdiff::Differ のインスタンスをつくり、Markdiff::Differ#render に変更前と変更後のHTMLの文字列を渡すと、Nokogiri::XML::Node のインスタンスが返ってきます。

require "markdiff"

differ = Markdiff::Differ.new
node = differ.render("<p>x x x</p>", "<p>x y x</p>")
node.to_html #=> '<div class="changed"><p>x <del class="del">x</del><ins>y</ins> x</p></div>'

出力形式

削除された部分はdel要素で囲まれ、追加された部分はins要素で囲まれて挿入されます。これは赤色背景の打ち消し線の部分と、緑色背景の部分を表示するための処理です。また、変更を含む段落はdiv要素で囲まれます。これは、変更を含む箇所の左側に黄色い縦線を引くためです。

<div class="changed">
  <p>x <del class="del">x</del><ins>y</ins> x</p>
</div>

仕組み

2つのHTMLから差分として Nokogiri::XML::Node を出力するための仕組みを説明します。大枠としては、以下の2つの手順を踏みます。これは、React などのVirtual DOMの実装を参考にしました。

  1. 変更前と変更後のHTMLを比較して適用すべきパッチを取り出す
  2. 変更前のHTMLにパッチを適用する

パッチの抽出

Markdiff::Operations::Base というクラスがあり、この配列がパッチとして抽出されます。変更前のノードと変更後のノードが渡されたとき、ノード同士とノードの子要素同士で比較操作を行う、という処理を再帰的に行うことで、HTMLツリー内を探索しながらパッチを抽出していきます。

  1. ノード同士を文字列化して比較し、もし完全に一致していればパッチとして空配列を返して処理を終える
  2. 子ノード同士を比較し、同一なノードを記録する
  3. 要素名だけが同じで子要素が異なるノードがあれば、それらを再帰的に比較してパッチを抽出する
  4. 記録と照合し、変更前にしか存在しないものがあればパッチに削除命令を追加する
  5. 記録と照合し、変更後にしか存在しないものがあればパッチに挿入命令を追加する

先ほどと同じくここでもVirtual DOMを参考にしており、同じ親を持つノード同士しか比較しないようにサボることで、計算コストを下げています。Markdownでは「ある要素が変更されて何らかの要素に囲まれた」というようなケースは起こりにくいため、この方法を取りました。Performance Calendar » React’s diff algorithm が参考になります。

最長共通部分列

差分のパッチをつくるだけで良ければ、変更前の全てのノードを削除する命令と、変更後の全てのノードを追加する命令をそれぞれまとめたものをパッチとして用意すれば良いということになります。しかしながら、できるだけ少なく小さな処理の組み合わせで表現できるほうが、より分かりやすい差分になると推測できます。そのためには、先述した手順で子ノード同士を比較するとき、できるかぎり多く共通しているノードを見つけ出す必要があります。そこで、最長共通部分列と呼ばれる考え方を適用することにしました。

最長共通部分列については、diffの動作原理を知る～どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社 が参考になります。要するに、何らかの比較可能な要素の配列同士を与えて、2つの要素列の中で共通する部分で最も長い列を取り出す、というものです。Rubyでは halostatue/diff-lcs という実装があるため、これを利用しました。このライブラリはRSpecでのテスト結果の差分表示などに利用されています。

パッチの適用

パッチを抽出したら、今度は変更前のHTMLに対してパッチを適用し、最終的な結果を生成します。パッチは命令の配列になっており、ある命令は基本的には以下の情報を含んでいます。

  • 命令の種類
  • 操作対象のノード
  • 新たに挿入あるいは置換されるノード

現在のところ、以下の6種類の命令があります。

  • add_child_operation
  • add_data_before_href_operation
  • add_data_before_tag_name_operation
  • add_previous_sibling_operation
  • remove_operation
  • text_diff_operation

命令にはノードへの参照が含まれているため、例えばある命令を適用するときに参照先のノードを取り除いたり置換したりしてしまうと、次の命令で参照先のノードが既に存在しなくなってしまっていた、などということが起こりえます。そのため、命令の適用順序に気を付ける必要があります。今回は、まず最初にノードの追加を行う命令を全て処理し、次にノードを削除あるいは置換する命令を処理する、という順序にしました。

なお、優先順位が同じ命令間の順序は保存しておかなければ、適用結果がおかしくなってしまいます。例えば、Rubyの Enumerable#sort_by は安定ソートではないため、優先順位だけで雑にソートしてしまうと不具合が生じてしまうので、注意しましょう。

おわり

差分表示の実装方法について、重要そうなところを説明しました。コード自体は大した分量ではないので、更に詳しく知りたい人は r7kamura/markdiff の実装を読んでみてください。