D6231: rust-discovery: starting core implementation

gracinet (Georges Racinet) phabricator at mercurial-scm.org
Fri Apr 12 14:34:20 EDT 2019


gracinet created this revision.
Herald added subscribers: mercurial-devel, mjpieters, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  Once exposed to the Python side, this core object will avoid
  costly roundtrips with potentially big sets of revisions.
  
  This changeset implements the core logic of the object only, i.e.,
  manipulation of the missing, common and undefined set-like revision
  attributes.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6231

AFFECTED FILES
  rust/hg-core/src/discovery.rs
  rust/hg-core/src/lib.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs
+++ b/rust/hg-core/src/lib.rs
@@ -6,6 +6,7 @@
 pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
 pub mod testing;  // unconditionally built, for use from integration tests
+pub mod discovery;
 
 /// Mercurial revision numbers
 ///
diff --git a/rust/hg-core/src/discovery.rs b/rust/hg-core/src/discovery.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/src/discovery.rs
@@ -0,0 +1,191 @@
+// discovery.rs
+//
+// Copyright 2019 Georges Racinet <georges.racinet at 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.
+
+//! Discovery operations
+//!
+//! This is a Rust counterpart to the `partialdiscovery` class of
+//! `mercurial.setdiscovery`
+
+use super::{Graph, GraphError, Revision};
+use crate::ancestors::MissingAncestors;
+use crate::dagops;
+use std::collections::HashSet;
+
+pub struct PartialDiscovery<G: Graph + Clone> {
+    target_heads: Option<Vec<Revision>>,
+    graph: G, // plays the role of self._repo
+    common: MissingAncestors<G>,
+    undecided: Option<HashSet<Revision>>,
+    missing: HashSet<Revision>,
+}
+
+impl<G: Graph + Clone> PartialDiscovery<G> {
+    /// Create a PartialDiscovery object, with the intent
+    /// of comparing our `::<target_heads>` revset to the contents of another
+    /// repo.
+    ///
+    /// For now `target_heads` is passed as a vector, and will be used
+    /// at the first call to `ensure_undecided()`.
+    ///
+    /// If we want to make the signature more flexible,
+    /// we'll have to make it a type argument of `PartialDiscovery` or a trait
+    /// object since we'll keep it in the meanwhile
+    pub fn new(graph: G, target_heads: Vec<Revision>) -> Self {
+        PartialDiscovery {
+            undecided: None,
+            target_heads: Some(target_heads),
+            graph: graph.clone(),
+            common: MissingAncestors::new(graph, vec![]),
+            missing: HashSet::new(),
+        }
+    }
+
+    /// Register revisions known as being common
+    pub fn add_common_revisions(
+        &mut self,
+        common: impl IntoIterator<Item = Revision>,
+    ) -> Result<(), GraphError> {
+        self.common.add_bases(common);
+        if self.undecided.is_none() {
+            return Ok(());
+        }
+        self.common
+            .remove_ancestors_from(self.undecided.as_mut().unwrap())?;
+        Ok(())
+    }
+
+    /// Register revisions known as being missing
+    pub fn add_missing_revisions(
+        &mut self,
+        missing: impl IntoIterator<Item = Revision>,
+    ) -> Result<(), GraphError> {
+        self.ensure_undecided()?;
+        let range = dagops::range(
+            &self.graph,
+            missing,
+            self.undecided.as_ref().unwrap().iter().cloned(),
+        )?;
+        let undecided_mut = self.undecided.as_mut().unwrap();
+        for missrev in range.into_iter() {
+            self.missing.insert(missrev);
+            undecided_mut.remove(&missrev);
+        }
+        Ok(())
+    }
+
+    /// Do we have any information about the peer?
+    pub fn has_info(&self) -> bool {
+        self.common.has_bases()
+    }
+
+    /// Did we acquire full knowledge of our Revisions that the peer has?
+    pub fn is_complete(&self) -> bool {
+        self.undecided.as_ref().map_or(false, |s| s.is_empty())
+    }
+
+    /// Return the heads of the common set of revisions
+    ///
+    /// This is the end goal of the discovery process seeks,
+    /// once `self.is_complete()` returns `true`.
+    pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> {
+        self.common.bases_heads()
+    }
+
+    /// Force first computation of `self.undecided`
+    ///
+    /// After this, `self.undecided.as_ref()` and `.as_mut()` can be
+    /// unwrapped to get workable immutable or mutable references without
+    /// any panic.
+    ///
+    /// This is an imperative call instead of an access with added lazyness
+    /// to reduce easily the scope of mutable borrow for the caller,
+    /// compared to undecided(&'a mut self) -> &'a… that would keep it
+    /// as long as the resulting immutable one.
+    fn ensure_undecided(&mut self) -> Result<(), GraphError> {
+        if self.undecided.is_some() {
+            return Ok(());
+        }
+        let tgt = self.target_heads.take().unwrap();
+        self.undecided =
+            Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
+        Ok(())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::testing::SampleGraph;
+
+    /// A PartialDiscovery as for pushing all the heads of `SampleGraph`
+    fn full_disco() -> PartialDiscovery<SampleGraph> {
+        PartialDiscovery::new(SampleGraph, vec![10, 11, 12, 13])
+    }
+
+    fn sorted_undecided(
+        disco: &PartialDiscovery<SampleGraph>,
+    ) -> Vec<Revision> {
+        let mut as_vec: Vec<Revision> =
+            disco.undecided.as_ref().unwrap().iter().cloned().collect();
+        as_vec.sort();
+        as_vec
+    }
+
+    fn sorted_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> {
+        let mut as_vec: Vec<Revision> =
+            disco.missing.iter().cloned().collect();
+        as_vec.sort();
+        as_vec
+    }
+
+    fn sorted_common_heads(
+        disco: &PartialDiscovery<SampleGraph>,
+    ) -> Result<Vec<Revision>, GraphError> {
+        let mut as_vec: Vec<Revision> =
+            disco.common_heads()?.iter().cloned().collect();
+        as_vec.sort();
+        Ok(as_vec)
+    }
+
+    #[test]
+    fn test_add_common_get_undecided() -> Result<(), GraphError> {
+        let mut disco = full_disco();
+        assert_eq!(disco.undecided, None);
+        assert!(!disco.has_info());
+
+        disco.add_common_revisions(vec![11, 12])?;
+        assert!(disco.has_info());
+        assert!(!disco.is_complete());
+        assert!(disco.missing.is_empty());
+
+        // add_common_revisions did not trigger a premature computation
+        // of `undecided`, let's check that and ask for them
+        assert_eq!(disco.undecided, None);
+        disco.ensure_undecided()?;
+        assert_eq!(sorted_undecided(&disco), vec![5, 8, 10, 13]);
+        Ok(())
+    }
+
+    /// in this test, we pretend that our peer misses exactly (8+10)::
+    /// and we're comparing all our repo to it (as in a bare push)
+    #[test]
+    fn test_discovery() -> Result<(), GraphError> {
+        let mut disco = full_disco();
+        disco.add_common_revisions(vec![11, 12])?;
+        disco.add_missing_revisions(vec![8, 10])?;
+        assert_eq!(sorted_undecided(&disco), vec![5]);
+        assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
+        assert!(!disco.is_complete());
+
+        disco.add_common_revisions(vec![5])?;
+        assert_eq!(sorted_undecided(&disco), vec![]);
+        assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
+        assert!(disco.is_complete());
+        assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]);
+        Ok(())
+    }
+}



To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mjpieters, mercurial-devel


More information about the Mercurial-devel mailing list