Commit graph traversal — ancestors/3 and merge_base/2.
Ordering
:date(default) — yields commits by descending author timestamp. A gb_sets-backed priority queue keeps the frontier in order.:topo— Kahn-style topological order. A commit is never emitted before any of its descendants. Implementation: we first compute indegrees over the reachable subgraph (with respect to outgoing "parent" edges — i.e. a commit's indegree counts how many of its known descendants have not yet been emitted); then we drain commits with indegree zero and decrement parents.
Merge base
merge_base/2 uses a frontier-marking BFS (git's classic
"paint-down" algorithm). No ancestor set is materialized in full;
the search stops as soon as the frontier is dominated by known
common ancestors. This is O(commits until first LCA found), not
O(|ancestors(a)| + |ancestors(b)|).
Summary
Functions
Find a single lowest-common-ancestor (LCA) commit for the given SHAs.
Find all lowest-common-ancestor commits for a pair of SHAs.
Types
@type repo() :: %{object_store: term()}
Functions
@spec ancestors(repo(), binary(), keyword()) :: Enumerable.t()
Find a single lowest-common-ancestor (LCA) commit for the given SHAs.
When multiple LCAs exist (a criss-cross merge has two), merge_base/2
picks one deterministically:
- newest by author timestamp, wins
- ties broken by SHA (ascending)
This is not identical to git merge-base's tie-break in every
case: git uses a traversal-order-dependent choice that can be hard
to replicate without cloning git's exact implementation. Both
libraries return a semantically-correct LCA; for workflows that
need the full set (e.g. a three-way merge), use
merge_base_all/2.
Returns {:ok, sha} on success or {:error, :none} when the
commits share no common ancestor.
Find all lowest-common-ancestor commits for a pair of SHAs.
Equivalent to git merge-base --all — returns every commit that
is an ancestor of both inputs AND is not an ancestor of any other
such commit. Most histories return a singleton list; criss-cross
merges return 2+.
Currently only supports pairs. For N > 2, compose pairwise.