Ancestry and reachability — what `reachable` actually means

Every history query in Git is a reachability question. “What commits are on this branch but not that one?” “What is the common ancestor of two branches?” “Has this commit been merged yet?” All three reduce to one operation: starting from some commit and following parent edges, can I reach some other commit? The vocabulary and commands in this lesson are how every GitOps controller, every CI diff, and every release script asks that question.

Reachability in the commit DAG

A commit B is reachable from a commit A if there exists a sequence of parent edges starting at A that ends at B. A is reachable from itself (the empty walk), and reachability is a property of the graph, not of any particular ref. Refs are just starting points.

flowchart LR
    A --> C
    A --> B
    B --> D
    C --> D
    D --> E
    E --> F

In the diagram:

• F is reachable from every other node (the graph is connected).
• D is reachable from A, B, C, E, and F but not from any node earlier than A.
• A is reachable only from itself; no edge points into A.

The graph is acyclic, so reachability is a partial order: either A reaches B, B reaches A, neither reaches the other, or both reach each other (which is impossible in a DAG unless they are the same node). This is the foundation of every ancestry question.

# Test ancestry: is $COMMIT_A an ancestor of $COMMIT_B?
git merge-base --is-ancestor "$COMMIT_A" "$COMMIT_B"
echo $?   # 0 if reachable, 1 if not, 128 on error

git merge-base --is-ancestor returns exit code 0 when the first commit is reachable from the second (i.e. is an ancestor of the second), 1 when it is not, and a non-zero status other than 1 if either commit does not exist. This is the cleanest, script-friendliest ancestry test Git offers.

Merge-base: the deepest common ancestor

Given two commits A and B, the merge base is the deepest commit that is an ancestor of both - deepest in the sense of graph distance from the root. There can be more than one merge base if the two commits converged from different roots (the “criss-cross merge” case), in which case Git returns all of them.

git merge-base "$A" "$B"
# 6f4e5a6

flowchart LR
    A --> M["merge-base\n6f4e5a6"]
    B --> M
    M --> P["earlier ancestors"]
    M --> A2["A's later commits"]
    M --> B2["B's later commits"]

The merge base is the natural three-way merge point. To merge A into B, Git computes the merge base of A and B, diffs the base against A (“their changes”), diffs the base against B (“our changes”), and combines the two diffs into a tree that is the merge result. The merge base is therefore not just an informational quantity - it is the input to the merge algorithm.

# Compute merge base and diff against one side
MERGE_BASE=$(git merge-base "$A" "$B")
git diff "$MERGE_BASE" "$A"   # "their" changes (from A's perspective)
git diff "$MERGE_BASE" "$B"   # "our" changes

The two-dot range: A..B

The expression A..B is shorthand for “commits reachable from B but not reachable from A”. It is the canonical way to enumerate “what is on B but not on A”:

# Commits on B but not on A
git log --oneline "$A".."$B"
# 8a3f9d2 bump terraform module to v1.4.0
# 4d2c8e0 Merge branch 'feature/iam-rotation' into main

# Count: how many commits is B ahead of A?
git rev-list --count "$A".."$B"
# 2

The semantics are exact: A..B is the set difference of B’s reachability closure and A’s reachability closure. If A is an ancestor of B, this is “the commits B added after A”. If A and B have diverged, this is “the commits B has that A does not”.

# Reverse range: A's commits not on B
git log --oneline "$B".."$A"
# (empty if B contains A, otherwise A's diverging commits)

The three-dot range: A…B

The expression A...B is shorthand for “commits reachable from either A or B but not from both”. The pivot is the merge base of A and B, and the range includes the commits on each side of the pivot:

# Commits on either side of the merge base
git log --oneline "$A"..."$B"
# 9f3c1d7 (feature/iam-rotation) rotate iam keys
# 7a1b2c3 add rotation cron
# 8a3f9d2 bump terraform module to v1.4.0

flowchart LR
    MB["merge-base"] --> A_only["A's commits"]
    MB --> B_only["B's commits"]

In the diagram, A...B includes both “A-only” commits and “B-only” commits - everything from the merge base forward, excluding the merge base itself and any common ancestors.

The three-dot range is most useful for code review: “show me every commit on either side of the merge base, so the reviewer sees the full divergence”. The two-dot range is most useful for “what’s on B that isn’t on A”: releases, deployments, and pending work.

Symmetric difference versus simple difference

The negation prefix ^ (caret) excludes a set from the result. ^A B means “reachable from B but not from A” - exactly the same as A..B.

rev-list: the underlying traversal

git log is a wrapper around git rev-list. git rev-list walks the DAG and prints every OID that matches the range, with no formatting. It is the right tool for scripts:

# List every OID on B not on A
git rev-list "$A".."$B"
# 8a3f9d2...
# 4d2c8e0...

# Count them
git rev-list --count "$A".."$B"
# 2

# Limit to the trunk (first-parent only)
git rev-list --first-parent --count "$A".."$B"
# 2

git rev-list --count A..B is the canonical “how many commits is B ahead of A” query, and it is the basis for every “is the trunk behind?” alert, “how many commits since last release?” query, and “is feature branch up to date?” check.

Production discipline

1. Use A..B for “what is on B but not A”. Releases, pending work, deployment windows. The two-dot range is the answer.
2. Use A...B for code review. The reviewer wants to see both sides of the divergence. The three-dot range is the answer.
3. Test ancestry with git merge-base --is-ancestor. It is the cleanest exit-code-based ancestry test and is reliable in scripts. Avoid parsing git log output to test ancestry.
4. Always inspect the merge-base before approving a CI plan. A merge-base that is wrong is a CI plan that is wrong.

Cross-course references

• GitOps with Argo CD - Part V (SyncWindows) uses git rev-list --count between the cluster’s last-synced commit and the desired commit to compute drift, the operational signal that something has diverged from Git.
• Terraform for Production Sysadmins - Part XII (State) describes terraform plan against a merge-base as the infrastructure analogue of git diff merge-base branch - both compute the change that a merge would apply.
• CI/CD Pipeline Patterns - Part IV (MergeChecks) requires every merge pipeline to verify the merge-base and to refuse the merge if the merge-base has changed since the plan was approved.

Quiz