# HG changeset patch
# User Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
# Date 1547456868 -3600
# Node ID 47881d2a9d99f2de0a391e2f00229b5bb7b9c149
# Parent  168041fa6d5f2ad57d5f3ab093e5fc2192859508
rust: dagop.headrevs() Rust counterparts

This introduces two Rust implementations for `mercurial.dagop.headrevs`.
The algorithm is identical to the Python version.
Depending on the caller, one or the other could be the most practical, or
the most performant, by minimizing the amount of memory copy and allocations.

Differential Revision: https://phab.mercurial-scm.org/D5580

diff -r 168041fa6d5f -r 47881d2a9d99 rust/hg-core/src/dagops.rs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/hg-core/src/dagops.rs	Mon Jan 14 10:07:48 2019 +0100
@@ -0,0 +1,136 @@
+// dagops.rs
+//
+// Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
+//
+// This software may be used and distributed according to the terms of the
+// GNU General Public License version 2 or any later version.
+
+//! Miscellaneous DAG operations
+//!
+//! # Terminology
+//! - By *relative heads* of a collection of revision numbers (`Revision`),
+//!   we mean those revisions that have no children among the collection.
+//! - Similarly *relative roots* of a collection of `Revision`, we mean
+//!   those whose parents, if any, don't belong to the collection.
+use super::{Graph, GraphError, Revision, NULL_REVISION};
+use std::collections::HashSet;
+
+fn remove_parents(
+    graph: &impl Graph,
+    rev: Revision,
+    set: &mut HashSet<Revision>,
+) -> Result<(), GraphError> {
+    for parent in graph.parents(rev)?.iter() {
+        if *parent != NULL_REVISION {
+            set.remove(parent);
+        }
+    }
+    Ok(())
+}
+
+/// Relative heads out of some revisions, passed as an iterator.
+///
+/// These heads are defined as those revisions that have no children
+/// among those emitted by the iterator.
+///
+/// # Performance notes
+/// Internally, this clones the iterator, and builds a `HashSet` out of it.
+///
+/// This function takes an `Iterator` instead of `impl IntoIterator` to
+/// guarantee that cloning the iterator doesn't result in cloning the full
+/// construct it comes from.
+pub fn heads<'a>(
+    graph: &impl Graph,
+    iter_revs: impl Clone + Iterator<Item = &'a Revision>,
+) -> Result<HashSet<Revision>, GraphError> {
+    let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect();
+    heads.remove(&NULL_REVISION);
+    for rev in iter_revs {
+        remove_parents(graph, *rev, &mut heads)?;
+    }
+    Ok(heads)
+}
+
+/// Retain in `revs` only its relative heads.
+///
+/// This is an in-place operation, so that control of the incoming
+/// set is left to the caller.
+/// - a direct Python binding would probably need to build its own `HashSet`
+///   from an incoming iterable, even if its sole purpose is to extract the
+///   heads.
+/// - a Rust caller can decide whether cloning beforehand is appropriate
+///
+/// # Performance notes
+/// Internally, this function will store a full copy of `revs` in a `Vec`.
+pub fn retain_heads(
+    graph: &impl Graph,
+    revs: &mut HashSet<Revision>,
+) -> Result<(), GraphError> {
+    revs.remove(&NULL_REVISION);
+    // we need to construct an iterable copy of revs to avoid itering while
+    // mutating
+    let as_vec: Vec<Revision> = revs.iter().cloned().collect();
+    for rev in as_vec {
+        remove_parents(graph, rev, revs)?;
+    }
+    Ok(())
+}
+
+#[cfg(test)]
+mod tests {
+
+    use super::*;
+    use crate::testing::SampleGraph;
+
+    /// Apply `retain_heads()` to the given slice and return as a sorted `Vec`
+    fn retain_heads_sorted(
+        graph: &impl Graph,
+        revs: &[Revision],
+    ) -> Result<Vec<Revision>, GraphError> {
+        let mut revs: HashSet<Revision> = revs.iter().cloned().collect();
+        retain_heads(graph, &mut revs)?;
+        let mut as_vec: Vec<Revision> = revs.iter().cloned().collect();
+        as_vec.sort();
+        Ok(as_vec)
+    }
+
+    #[test]
+    fn test_retain_heads() -> Result<(), GraphError> {
+        assert_eq!(retain_heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
+        assert_eq!(
+            retain_heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
+            vec![1, 6, 12]
+        );
+        assert_eq!(
+            retain_heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
+            vec![3, 5, 8, 9]
+        );
+        Ok(())
+    }
+
+    /// Apply `heads()` to the given slice and return as a sorted `Vec`
+    fn heads_sorted(
+        graph: &impl Graph,
+        revs: &[Revision],
+    ) -> Result<Vec<Revision>, GraphError> {
+        let heads = heads(graph, revs.iter())?;
+        let mut as_vec: Vec<Revision> = heads.iter().cloned().collect();
+        as_vec.sort();
+        Ok(as_vec)
+    }
+
+    #[test]
+    fn test_heads() -> Result<(), GraphError> {
+        assert_eq!(heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
+        assert_eq!(
+            heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
+            vec![1, 6, 12]
+        );
+        assert_eq!(
+            heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
+            vec![3, 5, 8, 9]
+        );
+        Ok(())
+    }
+
+}
diff -r 168041fa6d5f -r 47881d2a9d99 rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs	Mon Jan 14 20:42:25 2019 +0100
+++ b/rust/hg-core/src/lib.rs	Mon Jan 14 10:07:48 2019 +0100
@@ -3,6 +3,7 @@
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 mod ancestors;
+pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
 #[cfg(test)]
 pub mod testing;