二人で同じ日の日記を書き換えたら、どうマージするか。
Whatcha は、夫婦や家族で一冊の日記を書くアプリです。同じ日のページを二人がそれぞれ編集することがあり、そのたびに「どちらの書き換えを残すか」を決める必要があります。
最初は JavaScript の diff ライブラリ（jsdiff）で 3-way マージをしていましたが、「自動でマージできませんでした」が多すぎました。git merge-file に替えて、それでも足りない部分を jsdiff に戻す二段構えにしたところ、ランダムに作った 4,000 通りの編集で、自動解決できる割合が 50.9% から 68.8% に上がりました。
この記事は、その計測と、二つの道具が「どこで」食い違うかの話です。
前提：日記を commit の列として持つ
1件の日記（entry）は、保存のたびに commit を1つ積みます。commit は差分ではなくその時点の全体のスナップショットで、親 commit を指します。
ブランチは日記1件ごとに持ち、先頭の commit を指します。ここで効いたのが 複合外部キーです。commit 表に (entry_id, id) の一意制約を置き、ブランチ側から (entry_id, head_commit_id) で参照するようにすると、別の日記の commit をブランチの先頭に置くことが DB の制約で不可能になります。アプリ側のチェックに頼らずに済みます。
書き込みは楽観ロックです。クライアントは「自分が見ていた head」を送り、サーバー側の head と違えば書き込まずに返します。git push が non-fast-forward で拒否されるのと同じ振る舞いです。
何をマージするか：項目ごとに規則が違う
日記1件には、本文のほかに「タイトル・気分・場所・時刻・表紙」といった単一の値と、「タグ」があります。これらは同じ規則ではマージしません。
単一の値：動いた側が勝つ
規則は古典的な 3-way そのままで、4行で書けます。
- 片方が base から動かしていなければ、もう片方の値を採る
- 逆も同じ
- 両方が同じ値に変えたなら、衝突ではない（これが地味に効きます）
- 別々の値に変えたときだけ衝突
「両方が同じ値に変えた」を衝突にしないだけで、実際の衝突はかなり減ります。二人で同じ場所に行って、二人とも場所欄に同じ地名を入れる、はよくあります。
タグ：集合として足し引きする。衝突させない
タグは集合として扱います。base の並びを保ったまま、どちらかが消したものを落とし、それぞれが足したものを後ろに足す。この規則だと衝突が定義上発生しません。
二人がそれぞれタグを1つずつ足す、は一番よくある操作です。これで「衝突しました」と言われたら使い物になりません。
本文：ここが本題
本文は複数行のテキストなので、行単位の 3-way マージ（diff3）になります。
計測：git と jsdiff は、別々のところで失敗する
ランダムに作った 4,000 通りの「base と二人の編集」に対して、両方の道具で自動マージを試しました。
| 結果 | 割合 |
|---|---|
| 両方とも解決できた | 34.3% |
| git だけ解決できた | 17.9% |
| jsdiff だけ解決できた | 16.6% |
| どちらも解決できなかった | 30.9% |
どちらか一方だけを使うと:
| 方式 | 自動解決 |
|---|---|
| jsdiff のみ（以前） | 50.9% |
| git のみ | 52.2% |
| git → だめなら jsdiff | 68.8% |
片方がもう片方の上位互換ではありません。 失敗する場所が違うので、重ねると伸びます。
git が衝突にするのは「隣り合った行」
git の 3-way マージは、変更箇所の前後の文脈を含めてひとかたまりとして扱います。なので、二人が隣の行をそれぞれ直すと、重なっていなくても衝突になります。
--diff-algorithm を myers / minimal / patience / histogram のどれに変えても同じだったので、設定の問題ではなく git の性質です。
コードなら妥当な判断ですが、共有日記では「同じ段落を二人で少しずつ直す」がむしろ普通です。ここを拾えるのが jsdiff でした。
jsdiff は「書いた行が消える」ことがある
一方で jsdiff には、マージ結果からどちらかが足した行が落ちるケースがありました。日記で他人の書いた文章が黙って消えるのは、衝突よりずっと悪い失敗です。
そこで jsdiff の結果には、事後条件の検査をかけています。
検査の内容は一文で書けます。「各側が base に対して足した行は、マージ結果に同じ回数以上残っていなければならない」。残っていなければ、そのマージは採用せず衝突として返します。
これはヒューリスティックではなく事後条件です。diff3 が内部で何をしていようと、健全な 3-way の結果は、両側が足した行を含んでいるはずだからです。比較は行の**重複度（多重集合）**で行います。同じ行をもう1回足した場合も「1行足した」と数える必要があるためです。
git の経路はこの失敗を起こさないので、検査は jsdiff 側にだけかけています。
git merge-file は「リポジトリの要らない純粋関数」
git merge-file は、ファイルを3つ受け取ってマージ結果を返すだけのコマンドです。リポジトリも index も作業ツリーも要らず、状態を残しません。欲しいのは git のアルゴリズムであって、git をもう一つのデータ置き場にすることではないので、これがちょうど合います。
呼び出しは、一時ディレクトリに3つのファイルを書いて git merge-file -p ours base theirs を実行し、標準出力を受け取るだけです。気をつけた点:
- 終了コードがそのまま衝突数（1〜127、255 は git 自体の失敗）。0 以外なら衝突として扱う
- git が入っていないのを「衝突」と扱わない。 そうすると、イメージの作り間違い1つで全マージが黙って衝突になる。例外にして落とす（API の Dockerfile に git を入れている）
-
stderr を捨てる。 衝突は正常な結果なのに、git は非ゼロ終了を stderr に書くので、二人が同じ段落を直すたびにログに
fatal:が並ぶ
ほかにハマったところ
- 改行コード。 片方のクライアントが CRLF で送ると、jsdiff には「全行を書き換えた」ように見えて、その（実質空の）変更が本文全体に勝ち、相手の文章の改行コードまで黙って変わる。マージ中は LF にそろえ、結果はマージ先のブランチの改行コードに戻す
-
base が空。 新しく作ったばかりの日記は本文が
""で、共通の祖先が無い。二人が別の文章を足したら、それは本物の add/add 衝突として返す（jsdiff は空の base をそもそも受け付けない） -
完全に同じなら何もしない。 先に
threeWayPickをバイト単位で試し、マージが要らない本文は保存されたとおりに返す
まとめ
- テキストの 3-way マージは、道具によって失敗する場所が違う。一つに決めず、重ねる
- 速さや賢さより、誰かが書いた文章を消さないことを事後条件で保証する
- git は「アルゴリズムだけ借りる」使い方ができる。
git merge-fileはそのための入口
最後に、お願いがあります。
この記事のマージを実際に動かしているのが Whatcha です。一度だけ、ブラウザで開いて一行書いてみてもらえませんか。 登録もメールアドレスも要りません。30秒で終わります。
二人で同じ日のページを書くとどうなるかは、コードの説明を読むより、実際に触ったほうが早いです。相手がいなくても、自分ひとりで開いて書いてみるだけで構いません。触ってみて「ここが変」と思ったら、そのまま教えてください。 それが次に直すところになります。