前回は簡易な実装で3-way-merge を行ないました。
前回の途中で、コンフリクト時に問題があることが分かりましたので、そこからお話ししていきます。

---

両方修正の場合に進める行数が正しくない

local とremote で元文章の変更範囲が異なる可能性があります。
具体例はこちらです。

元の文章 (base)
A B C D E

修正後の文章1 (local)
A x C D E

修正後の文章2 (remote)
A y y y E

※見易くするために、1行1文字の文章をスペース区切りで横に並べています。

local では、元文章の修正がB のみの1行ですが、リモートではB C D の3行です。
前回のマージを適用するとこのような結果になります。

A x y y y C D E

これは悪くないかもしれません。
しかし、local とremote を逆にするとこうなります。

A y y y x E

この場合、C D が消えてしまいます。
置き換えた後にsouce.lines.size 行数分ループを進めることが理由です。

前回掲載のコードから抜粋

else -> {
    // 両方修正
    result += localDelta!!.target.lines
    result += remoteDelta!!.target.lines
    index += localDelta.source.lines.size // <-- ここ！
}

要件である、「コンフリクト時はその箇所についての両方の文章を残す」に合わなくなります。
もし、C D がユーザにとって必要なメモである場合、消えてしまうと困ってしまいます。

理想は修正1と修正2のそれぞれを並べることです。下の形にしたいです。

A x C D y y y E

これを実現するためには、両方の差分をひとつにまとめる必要があります。

---

差分の範囲

差分をまとめるにはどうすれば良いのでしょうか。
もう一度、先ほどのケースについてdiff を取得し差分を細かく見てみます。

val base   = listOf("A", "B", "C", "D", "E")
val local  = listOf("A", "x", "C", "D", "E")
val remote = listOf("A", "y", "y", "y", "E")
val localPatch = DiffUtils.diff(base, local)
val remotePatch = DiffUtils.diff(base, remote)

localPatch.deltas
  0:
    source:
      position: 1
      lines: [B]

remotePatch.deltas
  0:
    source:
      position: 1
      lines: [BCD]

よく見ると、source.position とsource.lines.size を使うことで、元文章の修正範囲が取得できることが分かります。
これを使って、local と remote で修正範囲が重複している部分を特定すれば、連続する差分が求められそうです。

ここで、もう少し複雑なケースを考えてみます。

---

複雑な差分の範囲が連続するケース

下の例を考えてみます。

元の文章 (base)
A B C D E F G

修正後の文章1 (local)
A x x D z z G

修正後の文章2 (remote)
A B y y y F G

この場合、元文章のB C D E F が修正範囲となります。
local がB C を修正し、remote が C D E を修正し、local がE F を修正しています。
一連の修正範囲を繋げると、B C D E F となります。

実際に実装する時は、差分の修正範囲が相手側、つまりlocal ならremote側に、修正が入っているかどうか判定する必要があります。
差分が見つかったらさらに、反対側を同じように判定するというロジックを繰り返します。

こうして求められた修正範囲に対して、local の差分とremote の差分を適用します。

以上を盛り込むと、目的のマージ処理を行うことができます。

---

ソース

ソースはこちらです。よかったら覗いてみてください。

マージ本体
テスト
build.gradle

---

次回予告

小さなテクニックを紹介します。