Three-way merge

A three-way merge combines two versions of a document, $A$ and $B$ , that were edited independently from a common ancestor $O$ , the base. Each version is compared with the base to find out which regions it changed. A region that only one side changed is taken from that side; a region both sides changed in the same way is taken once; and a region both sides changed differently is a conflict, which the merge reports for a person to resolve^[1]^[5]. The base is what makes the merge possible. Given only $A$ and $B$ , a line present in one and absent from the other could have been added by one side or deleted by the other, and no rule can tell which. The line-based algorithm diff3 has been part of Unix since 1979^[7], and version control systems from RCS to Git merge files with it^[4]^[6].

§ 01

The merge rule

Suppose the three versions have been aligned into regions, so that $O_{i}$ , $A_{i}$ and $B_{i}$ are corresponding regions of the base and the two sides. The merged region is

M_{i} = ⎩ ⎨ ⎧ B_{i} A_{i} conflict if A_{i} = O_{i} if B_{i} \in {O_{i}, A_{i}} otherwise

The rule has the properties one expects: merging a side with an unchanged copy of the base returns the side, $merge (O, A, O) = A$ ; merging a version with itself returns it, $merge (O, A, A) = A$ ; and the result does not depend on which side is called $A$ , apart from the order in which a conflict lists the two sides. All the difficulty lies in the alignment.

§ 02

The diff3 algorithm

diff3 aligns the three versions using two two-way diffs. It computes a longest common subsequence of $O$ and $A$ , and one of $O$ and $B$ , each a monotone matching of lines^[2]^[3]. A line of the base that is matched in both diffs is a synchronization point: all three versions agree on it, and it is copied to the output. Between two consecutive synchronization points lies an unstable region, which may be empty in some versions, and the merge rule is applied to it^[1].

Left: a three-way merge takes the base O and the two sides A and B and produces M. Right: a criss-cross history, in which A₂ and B₂ each merged the other branch; they have two best common ancestors, and neither is a good base on its own.

diff3 on arrays of lines, with a quadratic longest-common-subsequence diff and output in Git's diff3 conflict style.

(* Longest common subsequence of two line arrays, as the list of matched
   index pairs in increasing order. *)
let lcs (x : string array) (y : string array) =
  let n = Array.length x and m = Array.length y in
  let t = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = n - 1 downto 0 do
    for j = m - 1 downto 0 do
      t.(i).(j) <- if x.(i) = y.(j) then t.(i+1).(j+1) + 1
                   else max t.(i+1).(j) t.(i).(j+1)
    done
  done;
  let rec walk i j =
    if i = n || j = m then []
    else if x.(i) = y.(j) then (i, j) :: walk (i + 1) (j + 1)
    else if t.(i+1).(j) >= t.(i).(j+1) then walk (i + 1) j
    else walk i (j + 1)
  in
  walk 0 0
 
type chunk =
  | Stable of string list
  | Changed of string list                         (* merged cleanly *)
  | Conflict of string list * string list * string list   (* a, base, b *)
 
let slice a i j = Array.to_list (Array.sub a i (j - i))
 
(* diff3: a base line matched in both a and b is a sync point. Between two
   consecutive sync points lies an unstable region, which is taken from
   whichever side changed it, or is a conflict if both did, differently. *)
let merge (o : string array) (a : string array) (b : string array) =
  let ma = Hashtbl.of_seq (List.to_seq (lcs o a))
  and mb = Hashtbl.of_seq (List.to_seq (lcs o b)) in
  let syncs =
    List.filter_map
      (fun i -> match Hashtbl.find_opt ma i, Hashtbl.find_opt mb i with
         | Some j, Some k -> Some (i, j, k) | _ -> None)
      (List.init (Array.length o) Fun.id)
    @ [ (Array.length o, Array.length a, Array.length b) ]   (* sentinel *)
  in
  let rec go (i0, j0, k0) = function
    | [] -> []
    | (i, j, k) :: rest ->
      let so = slice o i0 i and sa = slice a j0 j and sb = slice b k0 k in
      let region =
        if so = sa && so = sb then []
        else if sa = so then [ Changed sb ]
        else if sb = so || sa = sb then [ Changed sa ]
        else [ Conflict (sa, so, sb) ]
      in
      let line = if i < Array.length o then [ Stable [ o.(i) ] ] else [] in
      region @ line @ go (i + 1, j + 1, k + 1) rest
  in
  go (0, 0, 0) syncs
 
(* Print the result the way Git does with merge.conflictStyle = diff3. *)
let print chunks =
  List.iter
    (function
      | Stable l | Changed l -> List.iter print_endline l
      | Conflict (a, o, b) ->
        print_endline "<<<<<<< ours";   List.iter print_endline a;
        print_endline "||||||| base";   List.iter print_endline o;
        print_endline "=======";        List.iter print_endline b;
        print_endline ">>>>>>> theirs")
    chunks

Two independent edits to different parts of a file.

open Diff3
let lines s = Array.of_list (String.split_on_char '\n' s)
 
let base = lines "let area r =\n  let pi = 3.14 in\n  pi *. r *. r\n\nlet perimeter r =\n  2. *. 3.14 *. r"
let ours = lines "let area r =\n  let pi = Float.pi in\n  pi *. r *. r\n\nlet perimeter r =\n  2. *. 3.14 *. r"
let theirs = lines "let area r =\n  let pi = 3.14 in\n  pi *. r *. r\n\nlet perimeter r =\n  2. *. 3.14 *. r\n\nlet diameter r = 2. *. r"

The merge takes both.

let area r =
  let pi = Float.pi in
  pi *. r *. r
let perimeter r =
  2. *. 3.14 *. r
let diameter r = 2. *. r

Conflicting, identical and adjacent edits.

open Diff3
let lines s = Array.of_list (String.split_on_char '\n' s)
let show title o a b = print_endline ("-- " ^ title); print (merge (lines o) (lines a) (lines b))

Running it.

-- both sides change the same line
x = 1
<<<<<<< ours
y = 20
||||||| base
y = 2
=======
y = 200
>>>>>>> theirs
z = 3
-- both make the same change
x = 1
y = 20
z = 3
-- changes to adjacent lines
w = 0
<<<<<<< ours
x = 10
y = 2
||||||| base
x = 1
y = 2
=======
x = 1
y = 20
>>>>>>> theirs
z = 3
-- the same changes, one line apart
w = 0
x = 10
k = 5
y = 20
z = 3

On these inputs the output is the same as GNU diff3 -m and git merge-file --diff3. The third case shows a property that surprises people: changes to adjacent lines conflict even though they do not overlap, because no base line lies between them to synchronize on, so the two changes fall into one unstable region. With one unchanged line between them, the same two edits merge cleanly. The section between the ||||||| and ======= markers shows the base version of the conflicting region, which Git prints when merge.conflictStyle is set to diff3 or zdiff3^[12].

§ 03

Properties

Khanna, Kunal and Pierce gave the first formal account of diff3 in 2007^[1]. They showed that it is idempotent and that it is stable when the two sides edit regions of the base separated by enough unchanged lines, so that the merged result then contains both sides' changes. They also showed that in general it has fewer guarantees than one might hope. The result depends on which longest common subsequences the two-way diffs choose, and with repeated lines, such as closing braces or blank lines, a different but equally long choice can move a change into a different place or turn a clean merge into a conflict. diff3 is not a function of the edits the two sides made but of the three texts, and different edit histories that produce the same texts give the same merge.

Clean is not correct

A line-based merge knows nothing about the language of the file. Two changes can touch different lines and merge without conflict while being incompatible, as when one side renames a function and the other adds a new call to it under its old name.

One side renames area, the other adds a use of it.

open Diff3
let lines s = Array.of_list (String.split_on_char '\n' s)
 
(* Ours renames area to disc_area; theirs adds a new use of area. *)
let base = lines "let area r = Float.pi *. r *. r\nlet total = area 1. +. area 2.\n\nlet () = print_float total"
let ours = lines "let disc_area r = Float.pi *. r *. r\nlet total = disc_area 1. +. disc_area 2.\n\nlet () = print_float total"
let theirs = lines "let area r = Float.pi *. r *. r\nlet total = area 1. +. area 2.\n\nlet () = print_float total\nlet ring = area 3. -. area 2."

The merge is clean.

let disc_area r = Float.pi *. r *. r
let total = disc_area 1. +. disc_area 2.
let () = print_float total
let ring = area 3. -. area 2.

And the result does not compile.

File "merged.ml", line 5, characters 11-15:
5 | let ring = area 3. -. area 2.
               ^^^^
Error: Unbound value area

Such semantic conflicts are found only by building and testing the merged result. Merge tools that parse the files first, called structured or semistructured merge, can resolve some textual conflicts, such as two independent additions to a list of declarations, and report others more precisely^[5]^[11].

§ 04

Choosing the base

In a version control system, the base is a common ancestor of the two commits being merged. Git uses a best common ancestor, one that is not an ancestor of any other common ancestor^[6]. In a linear branch-and-merge history there is exactly one. In a criss-cross history, where each of two branches has merged the other, there can be several, and picking one arbitrarily can reintroduce conflicts that were already resolved or silently drop changes. Git's recursive strategy, and its successor ort, which became Git's default in 2021, first merge the common ancestors into a virtual base and then use it for the final three-way merge; according to Git's documentation, tests on the Linux kernel's history found that this gives fewer conflicts without causing mismerges^[6].

Merges are also applied to trees of files, not only to lines. A file added on one side, or deleted on one side and unchanged on the other, follows the same rule as a line, and renames are detected by comparing file contents on each side with the base.

§ 05

Alternatives

Operation-based systems record the edits themselves rather than comparing states. The patch theory of Darcs and Pijul treats a merge as combining two patches with a common origin, which Mimram and Di Giusto described as a pushout in a category of files and patches^[9]. Conflict-free replicated data types design the data type so that concurrent operations always commute, so that every merge succeeds by construction^[10]. Both give a merge with stronger guarantees than diff3 at the cost of a richer representation than plain text.

§ 06

History

Hunt and McIlroy's diff appeared in 1976^[2], and diff3, which compares three files and can produce a merged script, was part of Version 7 Unix in 1979^[7]. Tichy's RCS provided a merge command built on diff3 in 1985^[4], and CVS, begun by Dick Grune in 1986 and rewritten by Berliner, made concurrent editing followed by a three-way merge the normal way to work on shared code^[8]. Myers's $O (N D)$ algorithm made the underlying diffs fast^[3]. Mens surveyed textual, syntactic and semantic merging in 2002^[5], and Khanna, Kunal and Pierce gave diff3 its first formal specification in 2007^[1]. Git, released in 2005, uses the same line-level algorithm inside merge strategies that choose the base and handle whole trees^[6].