月: 2025年8月

前回までで、3-way-merge が実装できました。
今回は、記載できなかった小さなテクニックを2つお話しします。

---

deltas の一部をapplyTo() として適用する方法

前回 (2) の時に試した通りdiff() メソッドの戻り値から、差分の一覧を取得できます。

val patch = DiffUtils.diff(base, local)
patch.detlas <-- List型の差分

この差分を全てではなく一部のみを、applyTo するやり方があります。

// 差分の一部を抜き出し
val newDeltas = listOf(patch.deltas[3], patch.deltas[5], …)
// Patch オブジェクトを新規作成
val patch = Patch()
// 抜き出した差分を登録
patch.deltas.addAll(deltas)
// 元文章にパッチを適用
val applied = patch.applyTo(base)

このように新たにPatch を作成してそこにdelta を登録することでapplyTo が使えます。
ただし、delta は修正対象を行番号で管理しているため、base を変更すると整合性が合わなくなりエラーになになる点は注意する必要があります。

---

差分が適用された範囲を抜き出す方法

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

修正後の文章 (local)
A B x D x F G

ここから、差分を適用して x D x を抽出するには、下の手順が必要です。

1. 元文章から範囲の後半部分を削除
   A B C D E F G からF Gを削除します
   –> A B C D E
2. applyTo を使用して差分を適用
   後半部分(F G)に差分はないので問題なく適用できます
   –> A B x D x
3. 適用後の文章から前半部分を削除
   A B x D x からA B を削除
   –> x D x

こうすることで、整合性を合わせつつ、修正後の文字列が取得できます。
はじめに後半を削除しないと、2. でINSERT が行われた場合、後半部分が何文字目から始まるのか算出するのが困難になります。
また、先に前半を削除すると、source.position が合わなくなり、applyTo でエラーが起きてしまいます。

前回は簡易な実装で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

---

次回予告

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

前回、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

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

次回予告

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

前回はiPhone メモアプリの挙動とマージの難しさを確認しました。
今回は実際に JavaDiffUtils を使い、テキスト差分の取得と適用の基本を押さえます。そして、次回の 3-way-merge 実装につなげます。

まずは、今回のマージ機能の要件を整理します。

---

要件の整理

今回のマージ機能はメモアプリでの利用を前提にしています。Git等のソース管理で行われているマージとは要件が異なります。

• ユーザ操作なしで自動マージする
• コンフリクト時は両方の修正版を残す

要件の例

このように、eとf の両方の変更を残すことで、必要な情報が失われるのを防ぎます。最終的な判断はユーザに委ねますが、情報が消えるよりはマシという方針です。

JavaDiffUtils の基本

使い方はとても簡単です。

kotlin
val base = listOf("AAA", "BBB", "CCC")
val local = listOf("AAA", "BeB", "CCC")
val patch = DiffUtils.diff(base, local)

DiffUtils.diff() を実行するだけで、差分を算出してくれます。
patch の中身を見てみます。

patch:
  deltas:
    0:
      type: CHANGE    <-- 他に、INSERT, DELETEがある
      source:
        position: 1   <-- 修正元の行番号（0始まり）
        lines: [BBB]  <-- 修正前の内容
      target:
        position: 1
        lines: [BeB]  <-- 修正後の内容

• type: CHANGE（変更）、INSERT（追加）とDELETE（削除）がある
• source: 修正前の行情報（位置と内容）
• target: 修正後の行情報

さらに、patch.applyTo(base) を使えば、差分を元文章に適用できます。便利ですね。

val applied = patch.applyTo(base)
println(applied)
// AAA
// BeB
// CCC

注意点として、deltas は修正行番号で管理しているため、base を変更するとパッチが適用できずにエラーになることがあります。

---

次回予告

ここまでで、JavaDiffUtils を使った差分取得と適用の基本がわかりました。次回はこの仕組みを使い、自動で両方の変更を残す 3-way-merge を実装していきます。