Three-way merge

Deep dive

How it works

Parts:

• merge base — common ancestor O of A and B in the version DAG, or a stored last-synced copy
• diff O→A, O→B — which units each side changed (Myers diff for lines)
• stable anchors — O units that both sides kept; they cut the files into chunks
• chunk rule — per chunk: unchanged side loses, equal edits collapse, otherwise conflict
• conflict block — ours, base and theirs kept together for a human or policy

Steps:

1. Find O: the lowest common ancestor of the two commits. Criss-cross history has several; git's ort (default; recursive is a synonym) first merges them into a virtual base.
2. Diff O→A and O→B into matching pairs (an LCS).
3. Anchors are O lines matched on both sides. Between consecutive anchors lie one chunk of O, A and B.
4. Apply the chunk rule. Adjacent edits from both sides share a chunk and conflict.
5. Emit a conflict as <<<<<<< ours, ||||||| base, ======= theirs, >>>>>>>. Without the base section (git's default style) a reader cannot tell which side deleted.
6. Structured data skips the diff: recurse into maps with the unit rule per key; scalars compare whole; lists need element ids or a sequence merge, else count as scalars.

        O ── edit ──► A ──┐
         \                ├─► merge(O, A, B) = M
          └── edit ──► B ─┘
 chunk:  A==O → B | B==O → A | A==B → A | else  <<< A ||| O === B >>>

Khanna, Kunal and Pierce give the formal account of this chunk algorithm (diff3).

Code

Both merges in std Rust; the line merge uses an O(n·m) LCS table to stay short.

use std::collections::BTreeMap;

#[derive(Clone, PartialEq, Debug)]
pub enum Value { Leaf(String), Map(BTreeMap<String, Value>) } // leaves are atomic

#[derive(Debug, PartialEq)]
pub struct Conflict { pub path: String, pub base: Option<Value>, pub ours: Option<Value>, pub theirs: Option<Value> }

/// None = key absent. Returns the merged value; conflicts are collected, `ours` kept as placeholder.
pub fn merge_val(o: Option<&Value>, a: Option<&Value>, b: Option<&Value>, path: &str, out: &mut Vec<Conflict>) -> Option<Value> {
    if a == b { return a.cloned(); }          // same change (or no change)
    if a == o { return b.cloned(); }          // only theirs changed
    if b == o { return a.cloned(); }          // only ours changed
    if let (Some(Value::Map(ma)), Some(Value::Map(mb))) = (a, b) {
        let empty = BTreeMap::new();          // both added a map: base is "empty"
        let mo = match o { Some(Value::Map(m)) => m, _ => &empty };
        let mut keys: Vec<&String> = mo.keys().chain(ma.keys()).chain(mb.keys()).collect();
        keys.sort();
        keys.dedup();
        let mut res = BTreeMap::new();
        for k in keys {
            let p = format!("{path}/{k}");
            if let Some(v) = merge_val(mo.get(k), ma.get(k), mb.get(k), &p, out) { res.insert(k.clone(), v); }
        }
        return Some(Value::Map(res));
    }
    out.push(Conflict { path: path.into(), base: o.cloned(), ours: a.cloned(), theirs: b.cloned() });
    a.cloned()
}

/// O(n·m) LCS table: matching index pairs (i, j), increasing in both.
pub fn dp(a: &[&str], b: &[&str]) -> Vec<(usize, usize)> {
    let (n, m, w) = (a.len(), b.len(), b.len() + 1);
    let mut t = vec![0u32; (n + 1) * w];
    for i in (0..n).rev() {
        for j in (0..m).rev() {
            t[i * w + j] = if a[i] == b[j] { t[(i + 1) * w + j + 1] + 1 } else { t[(i + 1) * w + j].max(t[i * w + j + 1]) };
        }
    }
    let (mut i, mut j, mut r) = (0, 0, vec![]);
    while i < n && j < m {
        if a[i] == b[j] { r.push((i, j)); i += 1; j += 1; }
        else if t[(i + 1) * w + j] >= t[i * w + j + 1] { i += 1 } else { j += 1 }
    }
    r
}

/// Trim the common prefix and suffix, run the DP on the middle only.
pub fn lcs(a: &[&str], b: &[&str]) -> Vec<(usize, usize)> {
    let p = a.iter().zip(b).take_while(|(x, y)| x == y).count();
    let s = a[p..].iter().rev().zip(b[p..].iter().rev()).take_while(|(x, y)| x == y).count();
    let mut r: Vec<_> = (0..p).map(|i| (i, i)).collect();
    r.extend(dp(&a[p..a.len() - s], &b[p..b.len() - s]).into_iter().map(|(i, j)| (i + p, j + p)));
    r.extend((0..s).map(|k| (a.len() - s + k, b.len() - s + k)));
    r
}

/// diff3: returns merged lines (with diff3-style conflict blocks) and the number of conflicts.
pub fn merge_lines<'a>(o: &[&'a str], a: &[&'a str], b: &[&'a str]) -> (Vec<&'a str>, usize) {
    let (mut ma, mut mb) = (vec![None; o.len()], vec![None; o.len()]);
    for (i, j) in lcs(o, a) { ma[i] = Some(j); }
    for (i, k) in lcs(o, b) { mb[i] = Some(k); }
    // stable lines: base lines kept by both sides; they cut the files into chunks
    let stable = (0..o.len()).filter_map(|i| Some((i, ma[i]?, mb[i]?))).chain([(o.len(), a.len(), b.len())]);
    let (mut out, mut nconf, mut st) = (vec![], 0, (0, 0, 0));
    for (i, j, k) in stable {
        let (co, ca, cb) = (&o[st.0..i], &a[st.1..j], &b[st.2..k]);
        if ca == co { out.extend(cb); }                       // only theirs changed
        else if cb == co || ca == cb { out.extend(ca); }      // only ours, or same change
        else {
            nconf += 1;
            out.push("<<<<<<< ours"); out.extend(ca);
            out.push("||||||| base"); out.extend(co);
            out.push("======="); out.extend(cb);
            out.push(">>>>>>> theirs");
        }
        if i < o.len() { out.push(o[i]); }
        st = (i + 1, j + 1, k + 1);
    }
    (out, nconf)
}

Asserts passed: merge(O,A,O)=A, merge(O,O,B)=B, merge(O,X,X)=X, disjoint line edits merge, same-line edits give one base-showing block, delete versus modify reported, nested edits merge.

Complexity and constants

Two diffs plus one linear pass over the chunks. The LCS table has N·M cells: 10,000 × 10,000 u32 is 400 MB, so it suits small inputs only. Myers needs O((N+M)·D) time. Per-field merge is O(keys).

Efficiency

• Cost: the two diffs dominate. Measured on an Apple M4 Pro, 10,000 lines, 1 % edited per side: two LCS-table diffs 0.3-0.45 s (three runs); the same two with Myers on interned line ids 0.2-0.5 ms. Bound: memory for the table, compute for Myers.
• Levers:
  • Myers O(ND) instead of the table — about 1,000x here (measured) — when the sides are similar to the base.
  • Intern lines to integers — integer instead of string compares — always.
  • Trim common prefix/suffix — clustered edits: 0.3 s to about 0.15 ms (measured); spread edits: no gain.
  • Per-field merge — no text diff at all — for maps and records.
  • Cache the merge base — skips the ancestor walk — repeated merges of the same pair.
• Naive → standard → state of the art: full N×M table, string compares · O(N·M) time and memory; Myers on interned lines, trimmed (git, GNU diff) · O((N+M)·D); plus histogram anchors (git ort default) · same order, better alignment.

Implementation notes

• Keep the base per peer, written atomically with the synced state.
• Normalise line endings first and keep a final-newline flag; blank-line anchors misalign (histogram or patience anchors help).
• Keep ours as placeholder beside the conflict list; refuse to commit while conflicts remain.
• Delete versus modify is a conflict: otherwise the modifier's edit is lost.
• Git picks a per-path merge via merge=<driver> in .gitattributes and merge.<driver>.driver in config (placeholders %O %A %B).

Pitfalls

• Clean merge, broken program: one side renames what the other newly uses, or both add the same function.
• Moves look like delete plus insert; move versus edit conflicts or duplicates.
• A wrong base after a criss-cross merge changes results silently; use a virtual base.
• kubectl apply reports no conflicts: the config file wins fields it names.

Variants and alternatives

In production

• git: git merge, git merge-file, ort with virtual merge bases.
• GNU diffutils diff3 -m, Mercurial's :merge3 tool, the Python merge3 package.
• kubectl apply: config file, live object and kubectl.kubernetes.io/last-applied-configuration as base; a key applied before but now absent is deleted.
• CouchDB: conflicting revisions stay in the revision tree; a deterministic winner is served, the application resolves.

Implementations

Sources

• Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, A Formal Investigation of Diff3, FSTTCS 2007. paper · PDF
• Git docs: merge-strategies, git-merge-file, gitattributes, git-config
• GNU diffutils manual, Comparing Three Files
• Apache CouchDB, Replication and conflict model
• Kubernetes, Declarative Management Using Configuration Files