前回、JavaDiffUtils の基本動作を確認しました。
今回は簡易な実装で3-way-merge を行なっていきます。

---

3-way-merge 基本方針

applyTo() は便利ですが、「両方の変更を残す」という要件は満たせません。そこで、source.lines とtarget.lines を使って、自前でマージを行います。

方針

• 修正なし –> base の行をそのまま採用
• 片方のみ修正 –> その修正版を採用
• 両方修正 –> 両方の修正を採用

実装例

kotlin
fun merge(base: List<String>, local: List<String>, remote: List<String>): List<String> {
    val localPatch = DiffUtils.diff(base, local)
    val remotePatch = DiffUtils.diff(base, remote)

    // 元文章の何行目に関する修正かMap 型に変換しておく
    // 適用済み管理と速度向上が目的なのでmutable
    val localDeltasFirstPositionMap = localPatch.deltas.associateBy { it.source.position }.toMutableMap()
    val remoteDeltasFirstPositionMap = remotePatch.deltas.associateBy { it.source.position }.toMutableMap()

    val result = mutableListOf<String>()
    var index = 0
    // 文末に行を追加した場合、source.position がbase 最終行+1 となるので、base.size までループ
    while (index <= base.size) {
        val localDelta = localDeltasFirstPositionMap.remove(index)
        val remoteDelta = remoteDeltasFirstPositionMap.remove(index)

        when {
            localDelta == null && remoteDelta == null -> {
                // 修正なし
                if (index < base.size) result += base[index]
                index++
            }
            localDelta != null && remoteDelta == null -> {
                // 片方修正（local）
                result += localDelta.target.lines
                index += localDelta.source.lines.size
            }
            localDelta == null && remoteDelta != null -> {
                // 片方修正（remote）
                result += remoteDelta.target.lines
                index += remoteDelta.source.lines.size
            }
            else -> {
                // 両方修正
                result += localDelta!!.target.lines
                result += remoteDelta!!.target.lines
                index += localDelta.source.lines.size
            }
        }
    }
    return result
}

動かすとこのようになります。

val base = listOf("AAA", "BBB", "CCC")
val local = listOf("AAA", "BeB", "CCC")
val remote = listOf("AAA", "BfB", "CCC")
val result = merge(base, local, remote)
result shouldBe listOf("AAA", "BeB", "BfB", "CCC")

AAA
BeB
BfB
CCC

行単位でのマージはこれでバッチリです。
ですが、厳密にはコンフリクト時に問題があり、このロジックでは一部の文字が失われる可能性があります（詳細は次回説明します）。
一方で、コンフリクトが発生した行を文字単位に分解し、同じロジックを適用すれば目的の結果を得られそうです。

上のロジックのまま、文字単位でのマージを試してみます。

文字単位でマージ

2行目を文字単位で分解して、先ほどのロジックを適用してみます。

val base = listOf("B", "B", "B")
val local = listOf("B", "e", "B")
val remote = listOf("B", "f", "B")
val result = merge(base, local, remote)
result shouldBe listOf("B", "e", "f", "B")

BefB

期待通りの結果が得られました。
行単位でマージを試みて、コンフリクトが発生した行は文字単位でマージを行う方針が良さそうです。

次回予告

コンフリクト時の問題についてお話しします。