Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 78 ยท Git Internals

How Merge, Rebase and Diff Work Inside

Learn the three-way merge algorithm, merge-base, the ort strategy, conflict markers, diff algorithms, rename detection and how rebase replays commits.

Merging and rebasing feel like magic until you know the one rule underneath: Git never merges two files by looking at them alone. It merges two changes against a common starting point. Rebase is the same machinery run in a loop. Diff, which turns two versions into a list of changes, is the tool that makes both possible, and it is not nearly as exact as it looks, because many different diffs describe the same change.

In this lesson you will find the common ancestor with merge-base, run the three-way merge by hand with git merge-file, preview a whole merge without touching your files using git merge-tree, compare diff algorithms on a real example, see how renames are detected rather than recorded, and watch a rebase replay commits one by one. The user-level view is in Merging Branches, Resolving Merge Conflicts and Rebasing; here we look under the hood.

Step one: the merge base

To merge branch topic into main, Git first needs the merge base: the best common ancestor of the two tips. It is the last point where both lines of work still agreed. git merge-base A B prints it.

TEXT
        o---o---o  topic          the merge base is the commit "B"
       /                          where topic split from main
  o---B---o---o    main

If one tip is an ancestor of the other, the merge base is that tip, and the merge is just a fast-forward. If history has criss-cross merges, there can be several equally good bases; git merge-base --all prints them all (more on this under "ort" below).

Bash Finding the merge base

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The merge base here is commit B, the commit both branches share. The exit status of --is-ancestor is what scripts use to ask "is this branch already merged?": 0 means yes. The first call fails with 1 because commit C exists only on topic; the second succeeds because HEAD~1 (commit B) is an ancestor of main.

Step two: the three-way merge

With three versions in hand (base, ours, theirs) Git merges per file, and inside a file per region of lines. The decision table for each region is short:

Base vs ours Base vs theirs Result
unchanged unchanged keep it
changed unchanged take ours
unchanged changed take theirs
changed changed the same way take that change
changed changed differently conflict

That is the entire algorithm, and it explains much about merging. Two branches that change different parts of one file merge cleanly. A line changed on one side and untouched on the other never conflicts. And a conflict only appears where both sides touched the same lines, or lines so close that Git cannot tell their changes apart.

git merge-file runs this algorithm on three plain files, without any repository, in the order current, base, other. With -p it prints the result instead of overwriting the first file.

Bash A three-way merge on plain files with git merge-file

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The first merge combined both edits because they hit different lines. In the second, both sides changed line 1, which produced the familiar markers. The exit status of merge-file is the number of conflicts (capped), so 0 means the merge was clean.

Conflict markers and the base

The markers <<<<<<<, ======= and >>>>>>> are written by the merge. By default you only see ours and theirs. With merge.conflictStyle = diff3 (or the newer zdiff3) Git adds a ||||||| section holding the base text. That third piece is often what you need to decide: you can see what each side changed from. Many experienced developers set git config --global merge.conflictStyle zdiff3 and never go back. zdiff3 additionally moves lines common to both sides out of the conflict, so the marked region stays small.

Previewing a merge: git merge-tree

git merge-tree --write-tree <a> <b> performs a full repository-level merge without touching the index, the working tree or any branch. It writes the resulting tree (or the best attempt, when there are conflicts) into the object database and prints its ID. The exit status is 0 for a clean merge and 1 for conflicts. Hosting platforms use this to answer "can this pull request be merged?" on the server, where there is no working tree.

Bash Preview a clean merge and a conflicting one with merge-tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

For the clean case the printed tree contains the merged f.txt (both edits applied). For the conflicting case merge-tree still writes a tree, now with conflict markers inside the file, and lists the conflicted paths and the messages Git would print. Our working directory and main stay exactly as they were. Without --write-tree the older, harder-to-read form of the command exists; avoid it.

Merge strategies: ort

The merge algorithm that Git runs by default since version 2.34 is called ort ("Ostensibly Recursive's Twin"), a faster, more correct rewrite of the older recursive strategy. What it does for two branches:

  1. Find the merge base. When there are several (a criss-cross merge), merge the bases together first into a virtual merge base, then use that.
  2. Compare base to each side at the tree level (not file by file), skipping any subtree whose ID is the same. This is the speed-up from the content-addressed trees in Git Objects.
  3. Detect renames between the base and each side (see below).
  4. For every path changed on both sides, run the three-way file merge described above.
  5. Write the resulting tree, or stop with conflicts and put the three file versions into the index at stages 1, 2 and 3.

Other strategies exist and are chosen with -s: ours, octopus (merging more than two branches at once; used automatically when you give several branches) and subtree. Do not confuse the strategy -s ours with the option -X ours:

  • git merge -s ours topic records a merge commit that has topic as a parent but takes none of its changes: the tree is exactly ours. It says "treat that history as merged, but discard its content".
  • git merge -X ours topic (or -X theirs) is an option to the normal strategy: do the real merge and resolve only the conflicting regions in favour of our (or their) side. Non-conflicting changes from both sides still arrive.
Bash Strategy ours versus option theirs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

With -s ours, nothing from topic appears in the file, but the history says it was merged, so later merges will not try to bring its commits again. With -X theirs, line 1 conflicted and topic won; line 3, changed only by topic, was applied as in any clean merge.

Diff: finding the changes

Merging and rebasing rest on diff. A diff is a list of changes that turns file A into file B, and the usual question is "which lines stayed the same?". The longest-common-subsequence problem has many solutions of the same length, so different algorithms give different, equally valid diffs. Git offers four, chosen with --diff-algorithm= or diff.algorithm:

  • myers (default): fast and finds a minimal edit script, but may latch onto repeated lines such as } and give confusing alignments.
  • minimal: myers, spending extra time to guarantee the smallest diff.
  • patience: first anchors on lines that appear exactly once in both files (function signatures, unique comments), then diffs the stretches in between. It tends to produce hunks that follow the structure of the code.
  • histogram: an improved patience that handles repeated lines better and is usually just as fast. Many people use it as their default (git config --global diff.algorithm histogram).

None of them changes what the files contain; they only change how the difference is shown and which lines a merge or rebase considers moved or unchanged. The example below moves a function in a C file and edits another. Compare how each algorithm describes the same change.

Bash The same change, three different diffs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The change is "a new function cube was inserted above greet, and one printf was removed". Patience (and histogram) say exactly that: the unique greet line anchors the alignment, so cube appears as one added block and square as one removed block. Myers matches the repeated {, } and return lines and presents the same edit as a tangle of interleaved changes: greet seems to turn into cube, then square into greet. Both are correct, but the second is much harder for a reviewer to read.

Two more display aids: --word-diff marks changes inside lines (see Status and Diff), and --color-moved highlights blocks that were moved rather than rewritten. More ways to compare are in Comparing Commits, Branches and Files.

Renames are detected, not recorded

Git stores snapshots, not operations, so it never records "file X was renamed to Y". When it compares two trees, it sees one path disappear and another appear. Rename detection then pairs them up: first exact matches (identical blob ID, 100% similar), then a similarity score for the rest (the fraction of content two files share). The default threshold is 50%: pairs scoring at least that are shown as renames. Change it with -M<n>%, for example -M90% for strict or -M20% for loose. --no-renames switches detection off, and -C also looks for copies.

Bash Rename detection and its similarity threshold

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The first diff shows R100. After rewriting six of ten lines, the similarity falls to 37%, below the default, so Git reports a deletion plus an addition; at -M20% the same change is shown as R037. The same detection happens when you merge: if one branch renames a file and the other edits it, ort notices the rename and applies the edit to the new path. This is the practical reason to commit a rename separately from big edits: a 100% rename is always recognised, while a rename mixed with a rewrite can fall below the threshold and be handled as delete plus add.

Bash A merge that follows a rename

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

main edited notes.txt; the other branch renamed it. The merge result contains docs.txt with the new line epsilon: the rename was detected on one side, and the edit was carried over to the new name. Without rename detection this would have been a conflict (modified on one side, deleted on the other).

Rebase is merge machinery in a loop

A rebase takes the commits of your branch that are not on the target (git rev-list target..HEAD), remembers them in a todo list, resets to the new base and replays them one by one, as if you were running git cherry-pick for each. Every replayed commit is a new commit with the same author and message but a new parent, so a new hash. The old commits stay in the object database until the reflog lets them go, and ORIG_HEAD points at the old tip. Internally each replay is a three-way merge where the base is the original commit's parent, "ours" is the new branch tip and "theirs" is the commit being replayed. That is why conflicts during a rebase swap the usual meaning of ours and theirs (see Rebasing).

While a rebase is paused on a conflict its state is in .git/rebase-merge/, from which you can read the whole plan.

Bash Peek inside a paused rebase

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with read or cat), it gets the next line from this box.

The conflict arose in the second replayed commit because main and topic both changed a.txt from the same base. The state directory told us everything: step 2 of 3, the branch being rebased and the remaining todo. After resolving, --continue replayed T3 and moved the branch topic to the new tip. This is also the reason a branch that was rebased should not be pushed over a shared copy casually: the commits are new objects, and others who had the old ones must reconcile them.

Because rebase uses the same merge logic, everything in this lesson applies to it: git rebase -X theirs passes the option to each replay, rerere can replay your earlier conflict resolutions automatically, and a missing rename detection makes rebase conflict in the same way a merge would. For a comparison of results, git range-diff shows what changed between the old and new versions of a rebased series.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which three versions does Git need to merge a file?

    A three-way merge compares each side with the merge base, applies changes made on only one side and reports a conflict where both changed the same region differently.
  2. 2. Two branches change different lines of the same file. What happens when you merge?

    Conflicts only occur where both sides changed the same region (or regions too close to separate). Changes in different regions combine automatically.
  3. 3. What is the difference between git merge -s ours topic and git merge -X ours topic?

    -s selects a whole merge strategy ('ours' ignores the other branch's changes). -X passes an option to the default strategy and affects only the conflicting hunks.
  4. 4. Why does Git report a renamed file as delete plus add when you also rewrote most of its content?

    Git stores snapshots, not rename operations. It pairs deleted and added files by content similarity; below the threshold (50% by default) they are not paired. -M<n>% changes the limit.
  5. 5. What does git rebase main do internally?

    Each commit is applied with a three-way merge (base = its original parent) and recreated with a new parent and new ID; the branch then moves to the last one.

Summary

  • A merge starts with the merge base (git merge-base), the best common ancestor; if one tip is an ancestor of the other, the merge is a fast-forward.
  • The three-way algorithm compares base to ours and base to theirs: one-sided changes win, identical changes agree, different changes to the same region conflict. git merge-file runs it on plain files.
  • git merge-tree --write-tree previews a merge without touching branches or the working tree; its exit status tells whether it was clean.
  • The default strategy is ort; -s ours is a strategy that discards the other side's content, -X ours/theirs only decides conflicting hunks. merge.conflictStyle = zdiff3 shows the base text in markers.
  • Diff algorithms (myers, minimal, patience, histogram) produce different but valid diffs; histogram or patience often read better.
  • Renames are never stored; they are detected by content similarity (default 50%, -M<n>%), and merges follow them. Commit renames separately from big edits.
  • Rebase replays commits as a series of cherry-picks, each a three-way merge against the commit's original parent, producing new commits and keeping ORIG_HEAD for undo.

Next: Aliases and Everyday Productivity