# `Exgit.Walk`
[🔗](https://github.com/ivarvong/exgit/blob/v0.1.0/lib/exgit/walk.ex#L1)

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)|).

# `repo`

```elixir
@type repo() :: %{object_store: term()}
```

# `ancestors`

```elixir
@spec ancestors(repo(), binary(), keyword()) :: Enumerable.t()
```

# `merge_base`

```elixir
@spec merge_base(repo(), [binary()]) :: {:ok, binary()} | {:error, :none}
```

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.

# `merge_base_all`

```elixir
@spec merge_base_all(repo(), [binary()]) :: {:ok, [binary()]} | {:error, :none}
```

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.

---

*Consult [api-reference.md](api-reference.md) for complete listing*