diff rust/hg-core/src/revlog/index.rs @ 51225:89ce6a49bfeb

rust-index: implement common_ancestors_heads() and ancestors()

The only differences betwwen `common_ancestors_heads()` and
`find_gca_candidates()` seems to be that:

- the former accepts "overlapping" input revisions (meaning with duplicates).
- limitation to 24 inputs (in the C code), that we translate to using the
  arbitrary size bit sets in the Rust code because we cannot bail to Python.

Given that the input is expected to be small in most cases, we take the
heavy handed approach of going through a HashSet and wait for perfomance
assessment

In case this is used via `hg-cpython`, we can anyway absorb the overhead
by having `commonancestorheads` build a vector of unique values
directly, and introduce a thin wrapper over `find_gca_candidates`, to take
care of bit set type dispatching only.

As far as `ancestors` is concerneed, this is just chaining
`common_ancestors_heads()` with `find_deepest_revs`.

--- a/rust/hg-core/src/revlog/index.rs	Tue Oct 17 22:42:40 2023 +0200
+++ b/rust/hg-core/src/revlog/index.rs	Wed Oct 18 15:35:38 2023 +0200
@@ -1036,14 +1036,40 @@
 
     /// Given a (possibly overlapping) set of revs, return all the
     /// common ancestors heads: `heads(::args[0] and ::a[1] and ...)`
-    pub fn common_ancestor_heads(&self, _revisions: &[Revision]) {
-        todo!()
+    pub fn common_ancestor_heads(
+        &self,
+        revisions: &[Revision],
+    ) -> Result<Vec<Revision>, GraphError> {
+        // given that revisions is expected to be small, we find this shortcut
+        // potentially acceptable, especially given that `hg-cpython` could
+        // very much bypass this, constructing a vector of unique values from
+        // the onset.
+        let as_set: HashSet<Revision> = revisions.iter().copied().collect();
+        // Besides deduplicating, the C version also implements the shortcut
+        // for `NULL_REVISION`:
+        if as_set.contains(&NULL_REVISION) {
+            return Ok(vec![]);
+        }
+
+        let revisions: Vec<Revision> = as_set.into_iter().collect();
+
+        if revisions.len() <= 63 {
+            self.find_gca_candidates::<u64>(&revisions)
+        } else {
+            self.find_gca_candidates::<NonStaticPoisonableBitSet>(&revisions)
+        }
+    }
+
+    pub fn ancestors(
+        &self,
+        revisions: &[Revision],
+    ) -> Result<Vec<Revision>, GraphError> {
+        self.find_deepest_revs(&self.common_ancestor_heads(revisions)?)
     }
 
     /// Given a disjoint set of revs, return all candidates for the
     /// greatest common ancestor. In revset notation, this is the set
     /// `heads(::a and ::b and ...)`
-    #[allow(dead_code)]
     fn find_gca_candidates<BS: PoisonableBitSet + Clone>(
         &self,
         revs: &[Revision],
@@ -1147,7 +1173,6 @@
 
     /// Given a disjoint set of revs, return the subset with the longest path
     /// to the root.
-    #[allow(dead_code)]
     fn find_deepest_revs(
         &self,
         revs: &[Revision],