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 +// +// 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 { + target_heads: Option>, + graph: G, // plays the role of self._repo + common: MissingAncestors, + undecided: Option>, + missing: HashSet, +} + +impl PartialDiscovery { + /// Create a PartialDiscovery object, with the intent + /// of comparing our `::` 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) -> 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, + ) -> 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, + ) -> 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, 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 { + PartialDiscovery::new(SampleGraph, vec![10, 11, 12, 13]) + } + + fn sorted_undecided( + disco: &PartialDiscovery, + ) -> Vec { + let mut as_vec: Vec = + disco.undecided.as_ref().unwrap().iter().cloned().collect(); + as_vec.sort(); + as_vec + } + + fn sorted_missing(disco: &PartialDiscovery) -> Vec { + let mut as_vec: Vec = + disco.missing.iter().cloned().collect(); + as_vec.sort(); + as_vec + } + + fn sorted_common_heads( + disco: &PartialDiscovery, + ) -> Result, GraphError> { + let mut as_vec: Vec = + 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(()) + } +} 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 ///