Details
Details
Diff Detail
Diff Detail
- Repository
- rHG Mercurial
- Lint
Lint Skipped - Unit
Unit Tests Skipped
This is an archive of the discontinued Mercurial Phabricator instance.
Differential D6270
WIP using children_cache instead of dagops::range if presentAbandonedPublic
WIP using children_cache instead of dagops::range if present
AbandonedPublic
Authored by gracinet on Apr 18 2019, 5:11 AM.
Revision Contents
Revision Contents
Diff 14838
Diff 14838
rust/hg-core/src/discovery.rs
| extern crate rand; | extern crate rand; | ||||
| extern crate rand_pcg; | extern crate rand_pcg; | ||||
| use self::rand::seq::SliceRandom; | use self::rand::seq::SliceRandom; | ||||
| use self::rand::{thread_rng, RngCore, SeedableRng}; | use self::rand::{thread_rng, RngCore, SeedableRng}; | ||||
| use super::{Graph, GraphError, Revision, NULL_REVISION}; | use super::{Graph, GraphError, Revision, NULL_REVISION}; | ||||
| use crate::ancestors::MissingAncestors; | use crate::ancestors::MissingAncestors; | ||||
| use crate::dagops; | use crate::dagops; | ||||
| use std::cmp::Reverse; | |||||
| use std::collections::BinaryHeap; | |||||
| use std::collections::{HashMap, HashSet, VecDeque}; | use std::collections::{HashMap, HashSet, VecDeque}; | ||||
| type Rng = self::rand_pcg::Pcg32; | type Rng = self::rand_pcg::Pcg32; | ||||
| pub struct PartialDiscovery<G: Graph + Clone> { | pub struct PartialDiscovery<G: Graph + Clone> { | ||||
| target_heads: Option<Vec<Revision>>, | target_heads: Option<Vec<Revision>>, | ||||
| graph: G, // plays the role of self._repo | graph: G, // plays the role of self._repo | ||||
| common: MissingAncestors<G>, | common: MissingAncestors<G>, | ||||
| } | } | ||||
| /// Register revisions known as being missing | /// Register revisions known as being missing | ||||
| pub fn add_missing_revisions( | pub fn add_missing_revisions( | ||||
| &mut self, | &mut self, | ||||
| missing: impl IntoIterator<Item = Revision>, | missing: impl IntoIterator<Item = Revision>, | ||||
| ) -> Result<(), GraphError> { | ) -> Result<(), GraphError> { | ||||
| self.ensure_undecided()?; | self.ensure_undecided()?; | ||||
| if let Some(ref children) = self.children_cache { | |||||
| let mut seen: HashSet<Revision> = HashSet::new(); | |||||
| let mut tovisit: VecDeque<Revision> = | |||||
| missing.into_iter().map(|r| -r).collect(); | |||||
| let undecided_mut = self.undecided.as_mut().unwrap(); | |||||
| loop { | |||||
| match tovisit.pop_front() { | |||||
| None => { | |||||
| break; | |||||
| } | |||||
| Some(opp_rev) => { | |||||
| let rev = -opp_rev; | |||||
| self.missing.insert(rev); | |||||
| undecided_mut.remove(&rev); | |||||
| match children.get(&rev) { | |||||
| None => { | |||||
| continue; | |||||
| } | |||||
| Some(this_children) => { | |||||
| for child in this_children.iter().cloned() { | |||||
| if child != NULL_REVISION | |||||
| && !seen.contains(&child) | |||||
| { | |||||
| tovisit.push_back(-child); | |||||
| seen.insert(child); | |||||
| } | |||||
| } | |||||
| } | |||||
| } | |||||
| } | |||||
| } | |||||
| } | |||||
| } else { | |||||
| let range = dagops::range( | let range = dagops::range( | ||||
| &self.graph, | &self.graph, | ||||
| missing, | missing, | ||||
| self.undecided.as_ref().unwrap().iter().cloned(), | self.undecided.as_ref().unwrap().iter().cloned(), | ||||
| )?; | )?; | ||||
| let undecided_mut = self.undecided.as_mut().unwrap(); | let undecided_mut = self.undecided.as_mut().unwrap(); | ||||
| for missrev in range { | for missrev in range { | ||||
| self.missing.insert(missrev); | self.missing.insert(missrev); | ||||
| undecided_mut.remove(&missrev); | undecided_mut.remove(&missrev); | ||||
| } | } | ||||
| } | |||||
| Ok(()) | Ok(()) | ||||
| } | } | ||||
| /// Do we have any information about the peer? | /// Do we have any information about the peer? | ||||
| pub fn has_info(&self) -> bool { | pub fn has_info(&self) -> bool { | ||||
| self.common.has_bases() | self.common.has_bases() | ||||
| } | } | ||||
| assert_eq!(sorted_undecided(&disco), vec![]); | assert_eq!(sorted_undecided(&disco), vec![]); | ||||
| assert_eq!(sorted_missing(&disco), vec![8, 10, 13]); | assert_eq!(sorted_missing(&disco), vec![8, 10, 13]); | ||||
| assert!(disco.is_complete()); | assert!(disco.is_complete()); | ||||
| assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]); | assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]); | ||||
| Ok(()) | Ok(()) | ||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_discovery_with_children_cache() -> Result<(), GraphError> { | |||||
| let mut disco = full_disco(); | |||||
| disco.add_common_revisions(vec![11, 12])?; | |||||
| disco.ensure_children_cache(); | |||||
| 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(()) | |||||
| } | |||||
| #[test] | |||||
| fn test_limit_sample_no_need_to() { | fn test_limit_sample_no_need_to() { | ||||
| let sample = vec![1, 2, 3, 4]; | let sample = vec![1, 2, 3, 4]; | ||||
| assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]); | assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]); | ||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_limit_sample_less_than_half() { | fn test_limit_sample_less_than_half() { | ||||
| assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]); | assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]); | ||||