( )⚙ D6345 rust-discovery: optionally don't randomize at all, for tests

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6345

rust-discovery: optionally don't randomize at all, for tests
AbandonedPublic

Authored by gracinet on May 6 2019, 11:30 AM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Summary

As seen from Python, this is a new randomize kwarg in init of the
discovery object. It replaces random picking by some arbitrary yet
deterministic strategy.

This is the same as what test-setdiscovery.t does, with the added
benefit to be usable both in Python and Rust implementations.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.May 6 2019, 11:30 AM
kevincox accepted this revision.May 10 2019, 9:46 AM

The code and rust style looks fine. I'm not sure that taking the N smallest elements is the best approach for testing though. I can imagine it hiding some issues with larger values.

gracinet added a comment.May 22 2019, 12:36 PM

@kevincox I don't think the potential masking in tests due to this strategy is a big problem. That test is pretty recent, compared to setdiscovery, at least, and doesn't really test that sampling is very relevant. We could do better though by introducing several non random selecting strategies if we need it in the future, but this was good enough for me for the time being.

gracinet abandoned this revision.May 22 2019, 12:38 PM

I'm abandoning this revision because I have to resubmit the whole series after partial incorrect application last week and subsequent droping from the actual repo.

Revision Contents
Changeset List

Diff 15024

mercurial/setdiscovery.py

return return
seen.add(curr) seen.add(curr)
for p in parentfn(curr): for p in parentfn(curr):
if p != nullrev and (not revs or p in revs): if p != nullrev and (not revs or p in revs):
dist.setdefault(p, d + 1) dist.setdefault(p, d + 1)
visit.append(p) visit.append(p)
def _limitsample(sample, desiredlen): def _limitsample(sample, desiredlen, randomize=True):
"""return a random subset of sample of at most desiredlen item""" """return a random subset of sample of at most desiredlen item.
if len(sample) > desiredlen:
sample = set(random.sample(sample, desiredlen)) If randomize is False, though, a deterministic subset is returned.
This is meant for integration tests.
"""
if len(sample) <= desiredlen:
return sample return sample
if randomize:
return set(random.sample(sample, desiredlen))
sample = list(sample)
sample.sort()
return set(sample[:desiredlen])
class partialdiscovery(object): class partialdiscovery(object):
"""an object representing ongoing discovery """an object representing ongoing discovery
Feed with data from the remote repository, this object keep track of the Feed with data from the remote repository, this object keep track of the
current set of changeset in various states: current set of changeset in various states:
- common: revs also known remotely - common: revs also known remotely
- undecided: revs we don't have information on yet - undecided: revs we don't have information on yet
- missing: revs missing remotely - missing: revs missing remotely
(all tracked revisions are known locally) (all tracked revisions are known locally)
""" """
def __init__(self, repo, targetheads): def __init__(self, repo, targetheads, randomize=True):
self._repo = repo self._repo = repo
self._targetheads = targetheads self._targetheads = targetheads
self._common = repo.changelog.incrementalmissingrevs() self._common = repo.changelog.incrementalmissingrevs()
self._undecided = None self._undecided = None
self.missing = set() self.missing = set()
self._childrenmap = None self._childrenmap = None
self.randomize = randomize
def addcommons(self, commons): def addcommons(self, commons):
"""register nodes known as common""" """register nodes known as common"""
self._common.addbases(commons) self._common.addbases(commons)
if self._undecided is not None: if self._undecided is not None:
self._common.removeancestorsfrom(self._undecided) self._common.removeancestorsfrom(self._undecided)
def addmissings(self, missings): def addmissings(self, missings):
:headrevs: set of head revisions in local DAG to consider :headrevs: set of head revisions in local DAG to consider
:size: the maximum size of the sample""" :size: the maximum size of the sample"""
revs = self.undecided revs = self.undecided
if len(revs) <= size: if len(revs) <= size:
return list(revs) return list(revs)
sample = set(self._repo.revs('heads(%ld)', revs)) sample = set(self._repo.revs('heads(%ld)', revs))
if len(sample) >= size: if len(sample) >= size:
return _limitsample(sample, size) return _limitsample(sample, size, randomize=self.randomize)
_updatesample(None, headrevs, sample, self._parentsgetter(), _updatesample(None, headrevs, sample, self._parentsgetter(),
quicksamplesize=size) quicksamplesize=size)
return sample return sample
def takefullsample(self, headrevs, size): def takefullsample(self, headrevs, size):
revs = self.undecided revs = self.undecided
if len(revs) <= size: if len(revs) <= size:
return list(revs) return list(revs)
repo = self._repo repo = self._repo
sample = set(repo.revs('heads(%ld)', revs)) sample = set(repo.revs('heads(%ld)', revs))
parentrevs = self._parentsgetter() parentrevs = self._parentsgetter()
# update from heads # update from heads
revsheads = sample.copy() revsheads = sample.copy()
_updatesample(revs, revsheads, sample, parentrevs) _updatesample(revs, revsheads, sample, parentrevs)
# update from roots # update from roots
revsroots = set(repo.revs('roots(%ld)', revs)) revsroots = set(repo.revs('roots(%ld)', revs))
childrenrevs = self._childrengetter() childrenrevs = self._childrengetter()
_updatesample(revs, revsroots, sample, childrenrevs) _updatesample(revs, revsroots, sample, childrenrevs)
assert sample assert sample
sample = _limitsample(sample, size) sample = _limitsample(sample, size, randomize=self.randomize)
if len(sample) < size: if len(sample) < size:
more = size - len(sample) more = size - len(sample)
sample.update(random.sample(list(revs - sample), more)) takefrom = list(revs - sample)
if self.randomize:
sample.update(random.sample(takefrom, more))
else:
takefrom.sort()
sample.update(takefrom[:more])
return sample return sample
def findcommonheads(ui, local, remote, def findcommonheads(ui, local, remote,
initialsamplesize=100, initialsamplesize=100,
fullsamplesize=200, fullsamplesize=200,
abortwhenunrelated=True, abortwhenunrelated=True,
ancestorsof=None): ancestorsof=None):
'''Return a tuple (common, anyincoming, remoteheads) used to identify '''Return a tuple (common, anyincoming, remoteheads) used to identify

rust/hg-core/src/discovery.rs

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>>,
children_cache: Option<HashMap<Revision, Vec<Revision>>>, children_cache: Option<HashMap<Revision, Vec<Revision>>>,
missing: HashSet<Revision>, missing: HashSet<Revision>,
rng: Rng, rng: Rng,
randomize: bool,
} }
pub struct DiscoveryStats { pub struct DiscoveryStats {
pub undecided: Option<usize>, pub undecided: Option<usize>,
} }
/// Update an existing sample to match the expected size /// Update an existing sample to match the expected size
/// ///
/// 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 { ///
/// The `randomize` boolean affects sampling, and specifically how
/// limiting or last-minute expanding is been done:
///
/// If `true`, both will perform random picking from `self.undecided`.
/// This is currently the best for actual discoveries.
///
/// If `false`, a reproductible picking strategy is performed. This is
/// useful for integration tests.
pub fn new(
graph: G,
target_heads: Vec<Revision>,
randomize: bool,
) -> Self {
let mut seed: [u8; 16] = [0; 16]; let mut seed: [u8; 16] = [0; 16];
if randomize {
thread_rng().fill_bytes(&mut seed); thread_rng().fill_bytes(&mut seed);
Self::new_with_seed(graph, target_heads, seed) }
Self::new_with_seed(graph, target_heads, seed, randomize)
} }
pub fn new_with_seed( pub fn new_with_seed(
graph: G, graph: G,
target_heads: Vec<Revision>, target_heads: Vec<Revision>,
seed: [u8; 16], seed: [u8; 16],
randomize: bool,
) -> Self { ) -> Self {
PartialDiscovery { PartialDiscovery {
undecided: None, undecided: None,
children_cache: None, children_cache: 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), rng: Rng::from_seed(seed),
randomize: randomize,
} }
} }
/// Extract at most `size` random elements from sample and return them /// Extract at most `size` random elements from sample and return them
/// as a vector /// as a vector
fn limit_sample( fn limit_sample(
&mut self, &mut self,
mut sample: Vec<Revision>, mut sample: Vec<Revision>,
size: usize, size: usize,
) -> Vec<Revision> { ) -> Vec<Revision> {
if !self.randomize {
sample.sort();
sample.truncate(size);
return sample
}
let sample_len = sample.len(); let sample_len = sample.len();
if sample_len <= size { if sample_len <= size {
return sample; return sample;
} }
let rng = &mut self.rng; let rng = &mut self.rng;
let dropped_size = sample_len - size; let dropped_size = sample_len - size;
let limited_slice = if size < dropped_size { let limited_slice = if size < dropped_size {
sample.partial_shuffle(rng, size).0 sample.partial_shuffle(rng, size).0
#[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. /// To avoid actual randomness in these tests, we give it a fixed
/// random seed, but by default we'll test the random version.
fn full_disco() -> PartialDiscovery<SampleGraph> { fn full_disco() -> PartialDiscovery<SampleGraph> {
PartialDiscovery::new_with_seed( PartialDiscovery::new_with_seed(
SampleGraph, SampleGraph,
vec![10, 11, 12, 13], vec![10, 11, 12, 13],
[0; 16], [0; 16],
true,
) )
} }
/// A PartialDiscovery as for pushing the 12 head of `SampleGraph` /// A PartialDiscovery as for pushing the 12 head of `SampleGraph`
/// ///
/// To avoid actual randomness in tests, we give it a fixed random seed. /// To avoid actual randomness in tests, we give it a fixed random seed.
fn disco12() -> PartialDiscovery<SampleGraph> { fn disco12() -> PartialDiscovery<SampleGraph> {
PartialDiscovery::new_with_seed(SampleGraph, vec![12], [0; 16]) PartialDiscovery::new_with_seed(SampleGraph, vec![12], [0; 16], true)
} }
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();
} }
#[test] #[test]
fn test_limit_sample_more_than_half() { fn test_limit_sample_more_than_half() {
assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]); assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]);
} }
#[test] #[test]
fn test_limit_sample_no_random() {
let mut disco = full_disco();
disco.randomize = false;
assert_eq!(disco.limit_sample(vec![1, 8, 13, 5, 7, 3], 4),
vec![1, 3, 5, 7]);
}
#[test]
fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> { fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> {
let mut disco = full_disco(); let mut disco = full_disco();
disco.undecided = Some((1..=13).collect()); disco.undecided = Some((1..=13).collect());
let mut sample_vec = disco.take_quick_sample(vec![], 4)?; let mut sample_vec = disco.take_quick_sample(vec![], 4)?;
sample_vec.sort(); sample_vec.sort();
assert_eq!(sample_vec, vec![10, 11, 12, 13]); assert_eq!(sample_vec, vec![10, 11, 12, 13]);
Ok(()) Ok(())

rust/hg-cpython/src/discovery.rs

use std::cell::RefCell; use std::cell::RefCell;
py_class!(pub class PartialDiscovery |py| { py_class!(pub class PartialDiscovery |py| {
data inner: RefCell<Box<CorePartialDiscovery<Index>>>; data inner: RefCell<Box<CorePartialDiscovery<Index>>>;
def __new__( def __new__(
_cls, _cls,
index: PyObject, index: PyObject,
targetheads: PyObject targetheads: PyObject,
randomize: bool = true
) -> PyResult<PartialDiscovery> { ) -> PyResult<PartialDiscovery> {
Self::create_instance( Self::create_instance(
py, py,
RefCell::new(Box::new(CorePartialDiscovery::new( RefCell::new(Box::new(CorePartialDiscovery::new(
Index::new(py, index)?, Index::new(py, index)?,
rev_pyiter_collect(py, &targetheads)?, rev_pyiter_collect(py, &targetheads)?,
randomize,
))) )))
) )
} }
def addcommons(&self, commons: PyObject) -> PyResult<PyObject> { def addcommons(&self, commons: PyObject) -> PyResult<PyObject> {
let mut inner = self.inner(py).borrow_mut(); let mut inner = self.inner(py).borrow_mut();
let commons_vec: Vec<Revision> = rev_pyiter_collect(py, &commons)?; let commons_vec: Vec<Revision> = rev_pyiter_collect(py, &commons)?;
inner.add_common_revisions(commons_vec) inner.add_common_revisions(commons_vec)

tests/test-rust-discovery.py

def testaddinfomissingfirst(self): def testaddinfomissingfirst(self):
idx = self.parseindex() idx = self.parseindex()
disco = PartialDiscovery(idx, [3]) disco = PartialDiscovery(idx, [3])
disco.addinfo([(2, False), (1, True)]) disco.addinfo([(2, False), (1, True)])
self.assertTrue(disco.hasinfo()) self.assertTrue(disco.hasinfo())
self.assertTrue(disco.iscomplete()) self.assertTrue(disco.iscomplete())
self.assertEqual(disco.commonheads(), {1}) self.assertEqual(disco.commonheads(), {1})
def testinitnorandom(self):
idx = self.parseindex()
PartialDiscovery(idx, [3], randomize=False)
if __name__ == '__main__': if __name__ == '__main__':
import silenttestrunner import silenttestrunner
silenttestrunner.main(__name__) silenttestrunner.main(__name__)