エンジニアリンググループの冨岡(@jooohn1234)です。年末までM3USAの開発をサポートするため、USに滞在しています。

f:id:jooohn:20181119052101j:plain — とにかくハンバーガーがうまい

現在、M3USAが運営するMDLinxにて利用するCMSサービス(Contentful)をサポートする内部向け機能を作成しています。その一環で、Contentfulが提供するRichTextのバージョン間の差分を検出・表示するというエンジニアっぽいことをやったのでそれを紹介します。

背景

エムスリーUSAでは、医療従事者に向けた記事等を発信しています。この記事を作成するバックエンドとしてSaaS CMS (Contentful)の利用を検討しています。

www.m3tech.blog

M3USAのワークフローでは、世界各国のコントリビューターに執筆依頼、レビュー、修正依頼などをしながら一つの記事を作成していきます。これを補助する機能の１つとして、各編集者による変更の履歴・差分を表示する機能が強く望まれています。GitHubのコミットやレビュー機能のようですね。

一方、Contentfulがビルトインで提供するワークフロー機能はやや貧弱です。特に私たちのユースケースで致命的なのが以下です。

RichTextの差分表示がひどい(２つのJSONが、全く同じであるかどうかだけを教えてくれる)
Publish前の変更履歴を保持していない

(* RichTextは、(汚い)HTMLの代わりにJSONを格納するContentfulのキラー機能の一つ　

私たちのワークフローを実現する場合、Contentfulからの提案としては、以下のようでした。

ある記事の編集によってトリガーされるwebhookの通知を受け、そのときの内容を自前で保存する
自前でdiffを表示する

基本的にContentfulはCMSインフラを提供する立場であるため、表示に関してはこちらに任されている節があります。（プレビューなども自前のサイトを用意する。）

ここで、RichTextの差分を表示するという要求が出てきました。

"変更"を検出する

ということがあったので、差分を検出するarray-diff-itemsというライブラリを自作しました。よければ使ってみてください！

github.com

リポジトリのMotivationの項にも書きましたが、一番のモチベーションは"変更"を検知することです。RichTextの差分を表示する際に、文章の一部を変えただけで以下のように差分が表示されるのはあまりUXがいいとは言えませんよね。

f:id:jooohn:20181119062128p:plain — "abc" という文字列を追加しただけで全く別のparagraphとして差分が表示される

一方、全く違う文章を頑張ってマッチングされるのも困り者です。

f:id:jooohn:20181119062551p:plain — 全く別の文章の差分

ContentfulのRichTextは、トップレベルにいくつかのブロック要素（Paragraph, Asset, UnorderedList など）が配列として並ぶのですが、これを"いい感じに"差分を検出して表示させたい、というモチベーションでこのライブラリを作成しました。

以下のように二つの要素間のコスト関数を与えることで、コストが最小になるような差分を検出します。

const left  = ['Banana', 'Apple', 'Orange',          'Grape'];
const right = [          'Apple', 'Orange', 'Melon', 'Grape Fruit'];

arrayDiffItems(left, right)((a, b) => {
  // Return the cost to change "a" to "b".
  // When cost is less than 1, that means changing "a" to "b" is preferable to removing "a" and then adding "a".
  if (a === b) return 0;
  if (a.startsWith(b) || b.startsWith(a)) return 0.5;
  return 2;
});
// [
//   {"type":"Removed","item":"Banana"},
//   {"type":"Unchanged","item":"Apple"},
//   {"type":"Unchanged","item":"Orange"},
//   {"type":"Added","item":"Melon"},
//   {"type":"Changed","left":"Grape","right":"Grape Fruit"}
// ]

このコスト関数を調整することで、"ほどよく"差分を検出することができます。

f:id:jooohn:20181119051457p:plain — ParagraphからH2へは[削除,追加], Paragraph内の差分は[変更]

触れるデモも用意しました。

https://array-diff-items-example.netlify.com/

TypeScriptを使っている場合は、DescriminationUnionの機能で型安全に返却された各dIff項目の処理ができます。

switch (diffItem.type) {
  case 'Added': return <Added key={index} item={diffItem.item}/>;
  case 'Removed': return <Removed key={index} item={diffItem.item}/>;
  case 'Changed': return <Changed key={index} left={diffItem.left} right={diffItem.right} />;
  case 'Unchanged': return <Unchanged key={index} item={diffItem.item}/>;
}

https://github.com/jooohn/array-diff-items/blob/b514a8a639dcab4931daac7e81791514690baecb/example/src/Diff.tsx#L95-L100

差分検出の問題設定の話

基本的なdiff検出の考え方は、こちらの論文で紹介されているようにEdit Graphをベースにしています。

[(元の列長+1) * (変更後の列長+1)]のNodeが存在するGraphの中で、下への移動は元の要素の削除を、右への移動は変更後の要素の追加を意味します。左上が未変更、右下が全て変更後の状態を示すことになります。

f:id:jooohn:20181119080515p:plain

今回は右下への斜めの変更にコスト関数を用いました。このコストが0の場合は"変更なし"を意味します。また、0でないとしても右・下というパス（追加・削除）のコストにくらべて変更のコストが低い場合は、変更のほうが好ましいパスといえます。（ほとんど同じ文章のparagraphブロックは、追加・削除よりも変更したい、という意図をここで反映できます）

そのコストも考慮に入れた上でこの左上のノードから右下のノードへの最短経路を解くという、比較的シンプルな問題です。