| Alphare | |
| baymax |
| hg-reviewers |
As of 8c9a6adec67a, we were actually using
the children cache right away in add_missing_revisions,
the method that also triggers the undecided set computation
(see that changeset description for the corresponding
performance discussion).
This means we don't need a third typestate for the children
cache: WithUndecided can always have it.
It is clear that compute_children_cache does not have
to be tied to the WithUndecided struct anymore. We may
move it to hg::dagops in a later move.
| No Linters Available |
| No Unit Test Coverage |
There seems to have been no activities on this Diff for the past 3 Months.
By policy, we are automatically moving it out of the need-review state.
Please, move it back to need-review without hesitation if this diff should still be discussed.
:baymax:need-review-idle:
| Path | Packages | |||
|---|---|---|---|---|
| M | rust/hg-core/src/discovery.rs (63 lines) |
| Commit | Parents | Author | Summary | Date |
|---|---|---|---|---|
| 063afa06415a | 2ac80bf5f8bd | Georges Racinet | Dec 24 2019, 5:43 AM |
| randomize: bool, | randomize: bool, | ||||
| seed: Seed, | seed: Seed, | ||||
| } | } | ||||
| pub struct WithUndecided<G: Graph + Clone> { | pub struct WithUndecided<G: Graph + Clone> { | ||||
| graph: G, // plays the role of self._repo | graph: G, // plays the role of self._repo | ||||
| common: MissingAncestors<G>, | common: MissingAncestors<G>, | ||||
| undecided: HashSet<Revision>, | undecided: HashSet<Revision>, | ||||
| children_cache: Option<FastHashMap<Revision, Vec<Revision>>>, | children_cache: FastHashMap<Revision, Vec<Revision>>, | ||||
| missing: HashSet<Revision>, | missing: HashSet<Revision>, | ||||
| rng: Rng, | rng: Rng, | ||||
| respect_size: bool, | respect_size: bool, | ||||
| randomize: bool, | randomize: bool, | ||||
| } | } | ||||
| pub struct DiscoveryStats { | pub struct DiscoveryStats { | ||||
| pub undecided: Option<usize>, | pub undecided: Option<usize>, | ||||
| self.common.add_bases(common); | self.common.add_bases(common); | ||||
| } | } | ||||
| pub fn stats(&self) -> DiscoveryStats { | pub fn stats(&self) -> DiscoveryStats { | ||||
| DiscoveryStats { undecided: None } | DiscoveryStats { undecided: None } | ||||
| } | } | ||||
| fn compute_undecided(mut self) -> Result<WithUndecided<G>, GraphError> { | fn compute_undecided(mut self) -> Result<WithUndecided<G>, GraphError> { | ||||
| self.common | let undecided = self | ||||
| .missing_ancestors(self.target_heads.iter().cloned()) | .common | ||||
| .map(|undecided| WithUndecided::new(self, undecided)) | .missing_ancestors(self.target_heads.iter().cloned())?; | ||||
| let children = WithUndecided::compute_children_cache( | |||||
| &self.graph, | |||||
| undecided.iter().cloned(), | |||||
| )?; | |||||
| Ok(WithUndecided::new(self, undecided, children)) | |||||
| } | } | ||||
| } | } | ||||
| impl<G: Graph + Clone> WithUndecided<G> { | impl<G: Graph + Clone> WithUndecided<G> { | ||||
| fn new( | fn new( | ||||
| disco: OnlyCommon<G>, | disco: OnlyCommon<G>, | ||||
| undecided: impl IntoIterator<Item = Revision>, | undecided: impl IntoIterator<Item = Revision>, | ||||
| children_cache: FastHashMap<Revision, Vec<Revision>>, | |||||
| ) -> Self { | ) -> Self { | ||||
| WithUndecided { | WithUndecided { | ||||
| undecided: undecided.into_iter().collect(), | undecided: undecided.into_iter().collect(), | ||||
| children_cache: None, | children_cache: children_cache, | ||||
| rng: Rng::from_seed(disco.seed), | rng: Rng::from_seed(disco.seed), | ||||
| graph: disco.graph.clone(), | graph: disco.graph.clone(), | ||||
| missing: HashSet::new(), | missing: HashSet::new(), | ||||
| respect_size: disco.respect_size, | respect_size: disco.respect_size, | ||||
| randomize: disco.randomize, | randomize: disco.randomize, | ||||
| common: disco.common, | common: disco.common, | ||||
| } | } | ||||
| } | } | ||||
| /// `tovisit` is provided as a `VecDeque` already so that a potential | /// `tovisit` is provided as a `VecDeque` already so that a potential | ||||
| /// caller from `PartialDiscovery` can avoid the undecided set in case | /// caller from `PartialDiscovery` can avoid the undecided set in case | ||||
| /// it turns out to be empty (hence restrain | /// it turns out to be empty (hence restrain | ||||
| /// from performing the transition to `WithUndecided`) | /// from performing the transition to `WithUndecided`) | ||||
| pub fn add_missing_revisions( | pub fn add_missing_revisions( | ||||
| &mut self, | &mut self, | ||||
| mut tovisit: VecDeque<Revision>, | mut tovisit: VecDeque<Revision>, | ||||
| ) -> Result<(), GraphError> { | ) -> Result<(), GraphError> { | ||||
| self.ensure_children_cache()?; | |||||
| let children = self.children_cache.as_ref().unwrap(); | |||||
| let mut seen: HashSet<Revision> = HashSet::new(); | let mut seen: HashSet<Revision> = HashSet::new(); | ||||
| let undecided_mut = &mut self.undecided; | let undecided_mut = &mut self.undecided; | ||||
| let children = &self.children_cache; | |||||
| while let Some(rev) = tovisit.pop_front() { | while let Some(rev) = tovisit.pop_front() { | ||||
| if !self.missing.insert(rev) { | if !self.missing.insert(rev) { | ||||
| // either it's known to be missing from a previous | // either it's known to be missing from a previous | ||||
| // invocation, and there's no need to iterate on its | // invocation, and there's no need to iterate on its | ||||
| // children (we now they are all missing) | // children (we now they are all missing) | ||||
| // or it's from a previous iteration of this loop | // or it's from a previous iteration of this loop | ||||
| // and its children have already been queued | // and its children have already been queued | ||||
| continue; | continue; | ||||
| /// | /// | ||||
| /// We may introduce in the future an `into_common_heads` call that | /// We may introduce in the future an `into_common_heads` call that | ||||
| /// would be more appropriate for normal Rust callers, dropping `self` | /// would be more appropriate for normal Rust callers, dropping `self` | ||||
| /// if it is complete. | /// if it is complete. | ||||
| pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> { | pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> { | ||||
| self.common.bases_heads() | self.common.bases_heads() | ||||
| } | } | ||||
| fn ensure_children_cache(&mut self) -> Result<(), GraphError> { | fn compute_children_cache( | ||||
| if self.children_cache.is_some() { | graph: &G, | ||||
| return Ok(()); | undecided: impl Iterator<Item = Revision>, | ||||
| } | ) -> Result<(FastHashMap<Revision, Vec<Revision>>), GraphError> { | ||||
| let mut children: FastHashMap<Revision, Vec<Revision>> = | let mut children: FastHashMap<Revision, Vec<Revision>> = | ||||
| FastHashMap::default(); | FastHashMap::default(); | ||||
| for rev in self.undecided.iter() { | for rev in undecided.into_iter() { | ||||
| for p in ParentsIterator::graph_parents(&self.graph, *rev)? { | for p in ParentsIterator::graph_parents(graph, rev)? { | ||||
| children.entry(p).or_insert_with(|| Vec::new()).push(*rev); | children.entry(p).or_insert_with(|| Vec::new()).push(rev); | ||||
| } | } | ||||
| } | } | ||||
| self.children_cache = Some(children); | Ok(children) | ||||
| Ok(()) | |||||
| } | } | ||||
| /// Provide statistics about the current state of the discovery process | /// Provide statistics about the current state of the discovery process | ||||
| pub fn stats(&self) -> DiscoveryStats { | pub fn stats(&self) -> DiscoveryStats { | ||||
| DiscoveryStats { | DiscoveryStats { | ||||
| undecided: Some(self.undecided.len()), | undecided: Some(self.undecided.len()), | ||||
| } | } | ||||
| } | } | ||||
| fn bidirectional_sample( | fn bidirectional_sample( | ||||
| &mut self, | &mut self, | ||||
| size: usize, | size: usize, | ||||
| ) -> Result<(HashSet<Revision>, usize), GraphError> { | ) -> Result<(HashSet<Revision>, usize), GraphError> { | ||||
| if self.undecided.len() <= size { | if self.undecided.len() <= size { | ||||
| return Ok((self.undecided.clone(), size)); | return Ok((self.undecided.clone(), size)); | ||||
| } | } | ||||
| self.ensure_children_cache()?; | |||||
| let revs = &self.undecided; | let revs = &self.undecided; | ||||
| let mut sample: HashSet<Revision> = revs.clone(); | let mut sample: HashSet<Revision> = revs.clone(); | ||||
| // it's possible that leveraging the children cache would be more | // it's possible that leveraging the children cache would be more | ||||
| // efficient here | // efficient here | ||||
| dagops::retain_heads(&self.graph, &mut sample)?; | dagops::retain_heads(&self.graph, &mut sample)?; | ||||
| let revsheads = sample.clone(); // was again heads(revs) in python | let revsheads = sample.clone(); // was again heads(revs) in python | ||||
| // update from heads | // update from heads | ||||
| update_sample( | update_sample( | ||||
| Some(revs), | Some(revs), | ||||
| revsheads.iter().cloned(), | revsheads.iter().cloned(), | ||||
| &mut sample, | &mut sample, | ||||
| |r| ParentsIterator::graph_parents(&self.graph, r), | |r| ParentsIterator::graph_parents(&self.graph, r), | ||||
| None, | None, | ||||
| )?; | )?; | ||||
| // update from roots | // update from roots | ||||
| let revroots: HashSet<Revision> = | let revroots: HashSet<Revision> = | ||||
| dagops::roots(&self.graph, revs)?.into_iter().collect(); | dagops::roots(&self.graph, revs)?.into_iter().collect(); | ||||
| let prescribed_size = max(size, min(revroots.len(), revsheads.len())); | let prescribed_size = max(size, min(revroots.len(), revsheads.len())); | ||||
| let children = self.children_cache.as_ref().unwrap(); | let children = &self.children_cache; | ||||
| let empty_vec: Vec<Revision> = Vec::new(); | let empty_vec: Vec<Revision> = Vec::new(); | ||||
| update_sample( | update_sample( | ||||
| Some(revs), | Some(revs), | ||||
| revroots, | revroots, | ||||
| &mut sample, | &mut sample, | ||||
| |r| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()), | |r| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()), | ||||
| None, | None, | ||||
| )?; | )?; | ||||
| fn force_undecided( | fn force_undecided( | ||||
| disco: &mut PartialDiscovery<SampleGraph>, | disco: &mut PartialDiscovery<SampleGraph>, | ||||
| undecided: impl IntoIterator<Item = Revision>, | undecided: impl IntoIterator<Item = Revision>, | ||||
| ) { | ) { | ||||
| let undecided_set: HashSet<Revision> = undecided.into_iter().collect(); | let undecided_set: HashSet<Revision> = undecided.into_iter().collect(); | ||||
| disco | disco | ||||
| .mutate_undecided( | .mutate_undecided( | ||||
| |oc| Ok(WithUndecided::new(oc, Vec::new())), | |oc| { | ||||
| Ok(WithUndecided::new( | |||||
| oc, | |||||
| Vec::new(), | |||||
| FastHashMap::default(), | |||||
| )) | |||||
| }, | |||||
| |wu| { | |wu| { | ||||
| wu.undecided = undecided_set; | WithUndecided::compute_children_cache( | ||||
| Ok(()) | &wu.graph, | ||||
| undecided_set.iter().cloned(), | |||||
| ) | |||||
| .map(|children| wu.children_cache = children) | |||||
| .map(|_| wu.undecided = undecided_set) | |||||
| }, | }, | ||||
| ) | ) | ||||
| .unwrap() | .unwrap() | ||||
| } | } | ||||
| fn sorted_undecided( | fn sorted_undecided( | ||||
| disco: &PartialDiscovery<SampleGraph>, | disco: &PartialDiscovery<SampleGraph>, | ||||
| ) -> Vec<Revision> { | ) -> Vec<Revision> { | ||||
| // r12's only parent is r9, whose unique grand-parent through the | // r12's only parent is r9, whose unique grand-parent through the | ||||
| // diamond shape is r4. This ends there because the distance from r4 | // diamond shape is r4. This ends there because the distance from r4 | ||||
| // to the root is only 3. | // to the root is only 3. | ||||
| assert_eq!(sample_vec, vec![4, 9, 12]); | assert_eq!(sample_vec, vec![4, 9, 12]); | ||||
| Ok(()) | Ok(()) | ||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_children_cache() -> Result<(), GraphError> { | fn test_children_cache() { | ||||
| let mut disco = full_disco_with_undecided(); | let cache = full_disco_with_undecided().children_cache; | ||||
| disco.ensure_children_cache()?; | |||||
| let cache = disco.children_cache.unwrap(); | |||||
| assert_eq!(cache.get(&2).cloned(), Some(vec![4])); | assert_eq!(cache.get(&2).cloned(), Some(vec![4])); | ||||
| assert_eq!(cache.get(&10).cloned(), None); | assert_eq!(cache.get(&10).cloned(), None); | ||||
| let mut children_4 = cache.get(&4).cloned().unwrap(); | let mut children_4 = cache.get(&4).cloned().unwrap(); | ||||
| children_4.sort(); | children_4.sort(); | ||||
| assert_eq!(children_4, vec![5, 6, 7]); | assert_eq!(children_4, vec![5, 6, 7]); | ||||
| let mut children_7 = cache.get(&7).cloned().unwrap(); | let mut children_7 = cache.get(&7).cloned().unwrap(); | ||||
| children_7.sort(); | children_7.sort(); | ||||
| assert_eq!(children_7, vec![9, 11]); | assert_eq!(children_7, vec![9, 11]); | ||||
| Ok(()) | |||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_complete_sample() { | fn test_complete_sample() { | ||||
| let mut disco = full_disco_with_undecided(); | let mut disco = full_disco_with_undecided(); | ||||
| disco.undecided = vec![4, 7, 9, 2, 3].into_iter().collect(); | disco.undecided = vec![4, 7, 9, 2, 3].into_iter().collect(); | ||||
| let mut sample = vec![0]; | let mut sample = vec![0]; | ||||