Amey Pawar (ameyypawar) · Oct 2, 2026 · Oct 2, 2026 · Oct 9, 2026 · Oct 9, 2026
diff --git a/crate-status.md b/crate-status.md
@@ -810,6 +810,7 @@ Make it the best-performing implementation and the most convenient one.
 * [x] `describe()` (similar to `git name-rev`)
 * [x] merge-base
 * [x] merge-base octopus
+* [x] ahead/behind commit counts
 * parse specifications
     * [x] parsing and navigation
     * [x] revision ranges

diff --git a/gix-revision/Cargo.toml b/gix-revision/Cargo.toml
@@ -24,7 +24,7 @@ sha256 = ["gix-hash/sha256"]
 ## `git describe` functionality
 describe = ["dep:gix-trace", "dep:gix-hashtable"]
 
-## `git merge-base` functionality
+## `git merge-base` functionality and ahead/behind commit counts
 merge_base = ["dep:gix-trace", "dep:bitflags"]
 
 ## Data structures implement `serde::Serialize` and `serde::Deserialize`.

diff --git a/gix-revision/src/ahead_behind.rs b/gix-revision/src/ahead_behind.rs
@@ -0,0 +1,100 @@
+use gix_error::{Result, ResultExt, message};
+use gix_hash::ObjectId;
+use gix_revwalk::graph;
+
+use crate::{
+    Graph, PriorityQueue,
+    merge_base::{
+        Flags,
+        function::{GenThenTime, insert_input_commits},
+    },
+};
+
+/// Commit counts for a tip relative to a base.
+#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
+#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
+pub struct AheadBehind {
+    /// Commits reachable from the tip, but not from the base.
+    pub ahead: usize,
+    /// Commits reachable from the base, but not from the tip.
+    pub behind: usize,
+}
+
+/// Count commits reachable exclusively from `tip_commit_id` or `base_commit_id`, matching
+/// `git rev-list --left-right --count tip...base`. Equal commits return zero for both counts.
+/// All input commits must exist. Missing parents are treated as the end of the available history.
+///
+/// # Performance
+///
+/// Reuse `graph` to retain cached commits between calls. Its flags are automatically cleared.
+/// With nonzero, unsaturated commit-graph generations, traversal stops once only shared history remains.
+/// Otherwise, the walk may visit all available ancestors to account for colors arriving at already visited commits.
+/// Exact counts can require substantially more traversal than [`is_ancestor()`](crate::merge_base::is_ancestor()).
+pub fn ahead_behind(
+    tip_commit_id: ObjectId,
+    base_commit_id: ObjectId,
+    graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
+) -> Result<AheadBehind> {
+    let _span = gix_trace::coarse!("gix_revision::ahead_behind()", ?tip_commit_id, ?base_commit_id);
+    insert_input_commits(tip_commit_id, &[base_commit_id], graph)?;
+    if tip_commit_id == base_commit_id {
+        return Ok(AheadBehind::default());
+    }
+
+    graph.clear_commit_data(|flags| *flags = Flags::empty());
+    let both = Flags::COMMIT1 | Flags::COMMIT2;
+    let mut queue = PriorityQueue::new();
+    let mut pending_exclusive = 2;
+    let mut pending_uncached = 0;
+    let mut unreliable_generations = false;
+    for (commit_id, color) in [(tip_commit_id, Flags::COMMIT1), (base_commit_id, Flags::COMMIT2)] {
+        let commit = graph.get_mut(&commit_id).expect("input commits were inserted");
+        let info = GenThenTime::from(&*commit);
+        pending_uncached += usize::from(info.is_outside_commit_graph());
+        unreliable_generations |= !info.has_reliable_generation() && !info.is_outside_commit_graph();
+        commit.data = color | Flags::ENQUEUED;
+        queue.insert(info, commit_id);
+    }
+
+    // Uncached commits sort before cached ones; zero or saturated generations can violate parent ordering.
+    while pending_exclusive != 0 || pending_uncached != 0 || unreliable_generations {
+        let Some((info, commit_id)) = queue.pop() else {
+            break;
+        };
+        pending_uncached -= usize::from(info.is_outside_commit_graph());
+        let commit = graph.get_mut(&commit_id).expect("everything queued is in graph");
+        let colors = commit.data & both;
+        pending_exclusive -= usize::from(colors != both);
+        commit.data.remove(Flags::ENQUEUED);
+        for parent_commit_id in commit.parents.clone() {
+            graph
+                .get_or_insert_full_commit(parent_commit_id, |parent| {
+                    if parent.data.contains(colors) {
+                        return;
+                    }
+                    let info = GenThenTime::from(&*parent);
+                    unreliable_generations |= !info.has_reliable_generation() && !info.is_outside_commit_graph();
+                    if parent.data.contains(Flags::ENQUEUED) {
+                        pending_exclusive -= usize::from((parent.data & both) != both);
+                    } else {
+                        pending_uncached += usize::from(info.is_outside_commit_graph());
+                        queue.insert(info, parent_commit_id);
+                        parent.data |= Flags::ENQUEUED;
+                    }
+                    parent.data |= colors;
+                    pending_exclusive += usize::from((parent.data & both) != both);
+                })
+                .or_raise(|| message("could not insert parent commit into graph for ahead/behind traversal"))?;
+        }
+    }
+
+    // Date ordering can revisit commits, so count only after their colors have settled.
+    let mut counts = AheadBehind::default();
+    graph.clear_commit_data(|flags| {
+        let colors = *flags & both;
+        counts.ahead += usize::from(colors == Flags::COMMIT1);
+        counts.behind += usize::from(colors == Flags::COMMIT2);
+        *flags = Flags::empty();
+    });
+    Ok(counts)
+}
diff --git a/gix-revision/src/lib.rs b/gix-revision/src/lib.rs
@@ -13,7 +13,12 @@
 pub mod describe;
 #[cfg(feature = "describe")]
 pub use describe::function::describe;
-/// Find common ancestors of commits.
+/// Count commits exclusive to either side of a pair of revisions.
+#[cfg(feature = "merge_base")]
+pub mod ahead_behind;
+#[cfg(feature = "merge_base")]
+pub use ahead_behind::{AheadBehind, ahead_behind};
+/// Find common ancestors of commits, or check if a commit is an ancestor of another one.
 #[cfg(feature = "merge_base")]
 pub mod merge_base;
 #[cfg(feature = "merge_base")]

diff --git a/gix-revision/src/merge_base/function.rs b/gix-revision/src/merge_base/function.rs
@@ -36,14 +36,63 @@ pub fn merge_base(
     }
 
     graph.clear_commit_data(|f| *f = Flags::empty());
-    let bases = paint_down_to_common(first, others, graph)?;
+    let bases = paint_down_to_common(first, others, None, graph)?;
 
     let bases = remove_redundant(&bases, graph)?;
     Ok(nonempty::NonEmpty::from_vec(bases))
 }
 
+/// Return `true` if `ancestor_commit_id` can be reached from `descendant_commit_id` by following parents, similar to
+/// `git merge-base --is-ancestor`. A commit is its own ancestor, and commits of unrelated histories aren't ancestors
+/// of each other.
+///
+/// All input commits must exist.
+///
+/// # Performance
+///
+/// For repeated calls, be sure to re-use `graph` as its content will be kept and reused for a great speed-up. The contained flags
+/// will automatically be cleared.
+/// With a commit-graph, there is no traversal if `descendant_commit_id` is in it but `ancestor_commit_id` isn't, or if
+/// both have nonzero, unsaturated generations and the one of `ancestor_commit_id` isn't lower. Otherwise, such a
+/// generation of `ancestor_commit_id` stops the walk once only commits with a lower generation remain.
+pub fn is_ancestor(
+    ancestor_commit_id: ObjectId,
+    descendant_commit_id: ObjectId,
+    graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
+) -> Result<bool> {
+    let _span = gix_trace::coarse!(
+        "gix_revision::merge_base::is_ancestor()",
+        ?ancestor_commit_id,
+        ?descendant_commit_id
+    );
+    insert_input_commits(ancestor_commit_id, &[descendant_commit_id], graph)?;
+    if ancestor_commit_id == descendant_commit_id {
+        return Ok(true);
+    }
+
+    let ancestor = GenThenTime::from(graph.get(&ancestor_commit_id).expect("input commits were inserted"));
+    let descendant = GenThenTime::from(graph.get(&descendant_commit_id).expect("input commits were inserted"));
+    // A commit-graph contains all ancestors of its commits, and parents have lower generations than their children.
+    if (ancestor.is_outside_commit_graph() && !descendant.is_outside_commit_graph())
+        || (ancestor.has_reliable_generation()
+            && descendant.has_reliable_generation()
+            && ancestor.generation >= descendant.generation)
+    {
+        return Ok(false);
+    }
+
+    graph.clear_commit_data(|f| *f = Flags::empty());
+    let min_generation = ancestor.has_reliable_generation().then_some(ancestor.generation);
+    paint_down_to_common(ancestor_commit_id, &[descendant_commit_id], min_generation, graph)?;
+    Ok(graph
+        .get(&ancestor_commit_id)
+        .expect("input commits were inserted")
+        .data
+        .contains(Flags::COMMIT2))
+}
+
 /// Validate input tips even when a shortcut or unrelated histories would otherwise stop traversal early.
-pub(super) fn insert_input_commits(
+pub(crate) fn insert_input_commits(
     first_commit_id: ObjectId,
     others: &[ObjectId],
     graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
@@ -52,7 +101,7 @@ pub(super) fn insert_input_commits(
         graph
             .get_or_insert_full_commit(*commit_id, |_| {})
             .or_raise(|| message("could not insert commit into graph"))?
-            .ok_or_raise(|| message!("Commit {commit_id} could not be found for merge-base traversal").not_found())?;
+            .ok_or_raise(|| message!("Commit {commit_id} could not be found for revision traversal").not_found())?;
     }
     Ok(())
 }
@@ -205,11 +254,7 @@ impl PaintQueue {
         // Keep this commit counted until after the exit check so the last pending candidate is processed.
         // Side exhaustion is only final when children are visited before parents. Missing, zero, or saturated
         // generations fall back to date ordering, which can propagate a color to an already visited commit.
-        if self.non_stale == [0, 0]
-            || (self.non_stale.contains(&0)
-                && info.generation > 0
-                && info.generation < gix_commitgraph::GENERATION_NUMBER_MAX)
-        {
+        if self.non_stale == [0, 0] || (self.non_stale.contains(&0) && info.has_reliable_generation()) {
             return None;
         }
         let commit = graph.get_mut(&commit_id).expect("everything queued is in graph");
@@ -219,9 +264,13 @@ impl PaintQueue {
     }
 }
 
+/// Paint the histories of `first` and `others` in their own color and return the merge-base candidates found on the way.
+/// With `min_generation`, stop once only commits with a lower reliable generation remain, as these can't reach a commit
+/// of that generation. The returned candidates are incomplete then.
 fn paint_down_to_common(
     first: ObjectId,
     others: &[ObjectId],
+    min_generation: Option<graph::Generation>,
     graph: &mut Graph<'_, '_, graph::Commit<Flags>>,
 ) -> Result<Vec<(ObjectId, GenThenTime)>> {
     let mut queue = PaintQueue {
@@ -244,6 +293,12 @@ fn paint_down_to_common(
 
     let mut out = Vec::new();
     while let Some((info, commit_id)) = queue.pop(graph) {
+        if let Some(min_generation) = min_generation
+            && info.has_reliable_generation()
+            && info.generation < min_generation
+        {
+            break;
+        }
         let commit = graph.get_mut(&commit_id).expect("everything queued is in graph");
         let mut flags_without_result = commit.data & (Flags::COMMIT1 | Flags::COMMIT2 | Flags::STALE);
         if flags_without_result == (Flags::COMMIT1 | Flags::COMMIT2) {
@@ -270,7 +325,7 @@ fn paint_down_to_common(
 
 // TODO(ST): Should this type be used for `describe` as well?
 #[derive(Debug, Clone, Copy)]
-struct GenThenTime {
+pub(crate) struct GenThenTime {
     /// Note that the special [`GENERATION_NUMBER_INFINITY`](gix_commitgraph::GENERATION_NUMBER_INFINITY) is used to indicate
     /// that no commitgraph is available.
     generation: gix_revwalk::graph::Generation,
@@ -286,6 +341,19 @@ impl From<&graph::Commit<Flags>> for GenThenTime {
     }
 }
 
+impl GenThenTime {
+    /// Return `true` if the commit has no generation as it isn't in a commit-graph.
+    pub(crate) fn is_outside_commit_graph(&self) -> bool {
+        self.generation == gix_commitgraph::GENERATION_NUMBER_INFINITY
+    }
+
+    /// Return `true` if the generation is from a commit-graph and neither zero nor saturated, as only then all parents
+    /// of the commit are known to have a lower generation.
+    pub(crate) fn has_reliable_generation(&self) -> bool {
+        self.generation > 0 && self.generation < gix_commitgraph::GENERATION_NUMBER_MAX
+    }
+}
+
 impl Eq for GenThenTime {}
 
 impl PartialEq<Self> for GenThenTime {

diff --git a/gix-revision/src/merge_base/mod.rs b/gix-revision/src/merge_base/mod.rs
@@ -1,5 +1,6 @@
 bitflags::bitflags! {
-    /// The flags used in the graph for finding [merge bases](crate::merge_base()).
+    /// The flags used in the graph for finding [merge bases](crate::merge_base()),
+    /// [ancestors](crate::merge_base::is_ancestor()), and [ahead/behind counts](crate::ahead_behind()).
     #[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
     pub struct Flags: u8 {
         /// The commit belongs to the graph reachable by the first commit
@@ -17,6 +18,7 @@ bitflags::bitflags! {
 }
 
 pub(crate) mod function;
+pub use function::is_ancestor;
 
 mod octopus {