This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6257

rust-discovery: core implementation for take_quick_sample()
ClosedPublic

Authored by gracinet on Apr 16 2019, 5:51 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGd09bdb2a1f75: rust-discovery: core implementation for take_quick_sample()
Summary

This makes in particular rand no longer a testing dependency.

We keep a seedable random generator on the PartialDiscovery object
itself, to avoid lengthy initialization.

In take_quick_sample() itself, we had to avoid keeping the reference
to self.undecided to cope with the mutable reference introduced
by the the call to limit_sample, but it's still manageable without
resorting to inner mutability.

Sampling being prone to be improved in the mid-term future, testing
is minimal, amounting to checking which code path got executed.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

gracinet created this revision.Apr 16 2019, 5:51 PM
kevincox accepted this revision.Apr 20 2019, 2:52 PM
kevincox added inline comments.
rust/hg-core/src/discovery.rs
70

You can do

if see.insert(current).is_some() {
  continue; // Already present.
}

And avoid the insert below. Alternatively use the entry API which may be a bit more readable.

87

You can pattern match away the reference since Revision is Copy.

for &p in parentsfn(curent)? {
  // ...
}
gracinet marked 2 inline comments as done.May 6 2019, 11:30 AM
gracinet updated this revision to Diff 15021.
gracinet added a comment.May 6 2019, 11:32 AM

@kevincox thanks for the initial review, I think I've implemented the corrections you suggested.

rust/hg-core/src/discovery.rs
70

Ah yes that's right, let this one through.

Since seen is not used in the loop after that check (there's an early return that doesn't matter in this case), I found the boolean return of HashSet::insert() does the job neatly.

Closed by commit rHGd09bdb2a1f75: rust-discovery: core implementation for take_quick_sample() (authored by gracinet). · Explain WhyMay 16 2019, 12:43 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/Cargo.toml (8 lines)
Mrust/hg-core/src/discovery.rs (190 lines)

Diff 15145

rust/hg-core/Cargo.toml

[package] [package]
name = "hg-core" name = "hg-core"
version = "0.1.0" version = "0.1.0"
authors = ["Georges Racinet <gracinet@anybox.fr>"] authors = ["Georges Racinet <gracinet@anybox.fr>"]
description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)" description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
[lib] [lib]
name = "hg" name = "hg"
[dev-dependencies]
rand = "*"
rand_pcg = "*"
[dependencies] [dependencies]
byteorder = "1.3.1"
memchr = "2.2.0" memchr = "2.2.0"
byteorder = "1.3.1" rand = "> 0.6.4"
No newline at end of file rand_pcg = "> 0.1.0"

rust/hg-core/src/discovery.rs

// discovery.rs // discovery.rs
// //
// Copyright 2019 Georges Racinet <georges.racinet@octobus.net> // Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Discovery operations //! Discovery operations
//! //!
//! This is a Rust counterpart to the `partialdiscovery` class of //! This is a Rust counterpart to the `partialdiscovery` class of
//! `mercurial.setdiscovery` //! `mercurial.setdiscovery`
use super::{Graph, GraphError, Revision}; extern crate rand;
extern crate rand_pcg;
use self::rand::seq::SliceRandom;
use self::rand::{thread_rng, RngCore, SeedableRng};
use super::{Graph, GraphError, Revision, NULL_REVISION};
use crate::ancestors::MissingAncestors; use crate::ancestors::MissingAncestors;
use crate::dagops; use crate::dagops;
use std::collections::HashSet; use std::collections::{HashMap, HashSet, VecDeque};
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>,
undecided: Option<HashSet<Revision>>, undecided: Option<HashSet<Revision>>,
missing: HashSet<Revision>, missing: HashSet<Revision>,
rng: Rng,
} }
pub struct DiscoveryStats { pub struct DiscoveryStats {
pub undecided: Option<usize>, pub undecided: Option<usize>,
} }
/// Update an existing sample to match the expected size
///
/// The sample is updated with revisions exponentially distant from each
/// element of `heads`.
///
/// If a target size is specified, the sampling will stop once this size is
/// reached. Otherwise sampling will happen until roots of the <revs> set are
/// reached.
///
/// - `revs`: set of revs we want to discover (if None, `assume` the whole dag
/// represented by `parentfn`
/// - `heads`: set of DAG head revs
/// - `sample`: a sample to update
/// - `parentfn`: a callable to resolve parents for a revision
/// - `quicksamplesize`: optional target size of the sample
fn update_sample(
revs: Option<&HashSet<Revision>>,
heads: impl IntoIterator<Item = Revision>,
sample: &mut HashSet<Revision>,
parentsfn: impl Fn(Revision) -> Result<[Revision; 2], GraphError>,
quicksamplesize: Option<usize>,
) -> Result<(), GraphError> {
let mut distances: HashMap<Revision, u32> = HashMap::new();
let mut visit: VecDeque<Revision> = heads.into_iter().collect();
let mut factor: u32 = 1;
let mut seen: HashSet<Revision> = HashSet::new();
loop {
let current = match visit.pop_front() {
None => {
break;
}
Some(r) => r,
};
if !seen.insert(current) {
kevincoxUnsubmitted
Done

You can do

if see.insert(current).is_some() {
  continue; // Already present.
}

And avoid the insert below. Alternatively use the entry API which may be a bit more readable.

kevincox: You can do ``` if see.insert(current).is_some() { continue; // Already present. } ``` And…
gracinetAuthorUnsubmitted
Not Done

Ah yes that's right, let this one through.

Since seen is not used in the loop after that check (there's an early return that doesn't matter in this case), I found the boolean return of HashSet::insert() does the job neatly.

gracinet: Ah yes that's right, let this one through. Since `seen` is not used in the loop after that…
continue;
}
let d = *distances.entry(current).or_insert(1);
if d > factor {
factor *= 2;
}
if d == factor {
sample.insert(current);
if let Some(sz) = quicksamplesize {
if sample.len() >= sz {
return Ok(());
}
}
}
for &p in &parentsfn(current)? {
if p == NULL_REVISION {
kevincoxUnsubmitted
Done

You can pattern match away the reference since Revision is Copy.

for &p in parentsfn(curent)? {
  // ...
}
kevincox: You can pattern match away the reference since `Revision` is `Copy`. ``` for &p in parentsfn…
continue;
}
if let Some(revs) = revs {
if !revs.contains(&p) {
continue;
}
}
distances.entry(p).or_insert(d + 1);
visit.push_back(p);
}
}
Ok(())
}
impl<G: Graph + Clone> PartialDiscovery<G> { impl<G: Graph + Clone> PartialDiscovery<G> {
/// Create a PartialDiscovery object, with the intent /// Create a PartialDiscovery object, with the intent
/// of comparing our `::<target_heads>` revset to the contents of another /// of comparing our `::<target_heads>` revset to the contents of another
/// repo. /// repo.
/// ///
/// For now `target_heads` is passed as a vector, and will be used /// For now `target_heads` is passed as a vector, and will be used
/// at the first call to `ensure_undecided()`. /// at the first call to `ensure_undecided()`.
/// ///
/// If we want to make the signature more flexible, /// If we want to make the signature more flexible,
/// we'll have to make it a type argument of `PartialDiscovery` or a trait /// we'll have to make it a type argument of `PartialDiscovery` or a trait
/// object since we'll keep it in the meanwhile /// object since we'll keep it in the meanwhile
pub fn new(graph: G, target_heads: Vec<Revision>) -> Self { pub fn new(graph: G, target_heads: Vec<Revision>) -> Self {
let mut seed: [u8; 16] = [0; 16];
thread_rng().fill_bytes(&mut seed);
Self::new_with_seed(graph, target_heads, seed)
}
pub fn new_with_seed(
graph: G,
target_heads: Vec<Revision>,
seed: [u8; 16],
) -> Self {
PartialDiscovery { PartialDiscovery {
undecided: None, undecided: None,
target_heads: Some(target_heads), target_heads: Some(target_heads),
graph: graph.clone(), graph: graph.clone(),
common: MissingAncestors::new(graph, vec![]), common: MissingAncestors::new(graph, vec![]),
missing: HashSet::new(), missing: HashSet::new(),
rng: Rng::from_seed(seed),
} }
} }
/// Extract at most `size` random elements from sample and return them
/// as a vector
fn limit_sample(
&mut self,
mut sample: Vec<Revision>,
size: usize,
) -> Vec<Revision> {
let sample_len = sample.len();
if sample_len <= size {
return sample;
}
let rng = &mut self.rng;
let dropped_size = sample_len - size;
let limited_slice = if size < dropped_size {
sample.partial_shuffle(rng, size).0
} else {
sample.partial_shuffle(rng, dropped_size).1
};
limited_slice.to_owned()
}
/// Register revisions known as being common /// Register revisions known as being common
pub fn add_common_revisions( pub fn add_common_revisions(
&mut self, &mut self,
common: impl IntoIterator<Item = Revision>, common: impl IntoIterator<Item = Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
self.common.add_bases(common); self.common.add_bases(common);
if let Some(ref mut undecided) = self.undecided { if let Some(ref mut undecided) = self.undecided {
self.common.remove_ancestors_from(undecided)?; self.common.remove_ancestors_from(undecided)?;
} }
/// 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: self.undecided.as_ref().map(|s| s.len()), undecided: self.undecided.as_ref().map(|s| s.len()),
} }
} }
pub fn take_quick_sample(
&mut self,
headrevs: impl IntoIterator<Item = Revision>,
size: usize,
) -> Result<Vec<Revision>, GraphError> {
self.ensure_undecided()?;
let mut sample = {
let undecided = self.undecided.as_ref().unwrap();
if undecided.len() <= size {
return Ok(undecided.iter().cloned().collect());
}
dagops::heads(&self.graph, undecided.iter())?
};
if sample.len() >= size {
return Ok(self.limit_sample(sample.into_iter().collect(), size));
}
update_sample(
None,
headrevs,
&mut sample,
|r| self.graph.parents(r),
Some(size),
)?;
Ok(sample.into_iter().collect())
}
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use crate::testing::SampleGraph; use crate::testing::SampleGraph;
/// A PartialDiscovery as for pushing all the heads of `SampleGraph` /// A PartialDiscovery as for pushing all the heads of `SampleGraph`
///
/// To avoid actual randomness in tests, we give it a fixed random seed.
fn full_disco() -> PartialDiscovery<SampleGraph> { fn full_disco() -> PartialDiscovery<SampleGraph> {
PartialDiscovery::new(SampleGraph, vec![10, 11, 12, 13]) PartialDiscovery::new_with_seed(
SampleGraph,
vec![10, 11, 12, 13],
[0; 16],
)
}
/// A PartialDiscovery as for pushing the 12 head of `SampleGraph`
///
/// To avoid actual randomness in tests, we give it a fixed random seed.
fn disco12() -> PartialDiscovery<SampleGraph> {
PartialDiscovery::new_with_seed(SampleGraph, vec![12], [0; 16])
} }
fn sorted_undecided( fn sorted_undecided(
disco: &PartialDiscovery<SampleGraph>, disco: &PartialDiscovery<SampleGraph>,
) -> Vec<Revision> { ) -> Vec<Revision> {
let mut as_vec: Vec<Revision> = let mut as_vec: Vec<Revision> =
disco.undecided.as_ref().unwrap().iter().cloned().collect(); disco.undecided.as_ref().unwrap().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
disco.add_common_revisions(vec![5])?; disco.add_common_revisions(vec![5])?;
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]
fn test_limit_sample_no_need_to() {
let sample = vec![1, 2, 3, 4];
assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]);
}
#[test]
fn test_limit_sample_less_than_half() {
assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]);
}
#[test]
fn test_limit_sample_more_than_half() {
assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]);
}
#[test]
fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> {
let mut disco = full_disco();
disco.undecided = Some((1..=13).collect());
let mut sample_vec = disco.take_quick_sample(vec![], 4)?;
sample_vec.sort();
assert_eq!(sample_vec, vec![10, 11, 12, 13]);
Ok(())
}
#[test]
fn test_quick_sample_climbing_from_12() -> Result<(), GraphError> {
let mut disco = disco12();
disco.ensure_undecided()?;
let mut sample_vec = disco.take_quick_sample(vec![12], 4)?;
sample_vec.sort();
// r12's only parent is r9, whose unique grand-parent through the
// diamond shape is r4. This ends there because the distance from r4
// to the root is only 3.
assert_eq!(sample_vec, vec![4, 9, 12]);
Ok(())
}
} }