| kevincox |
| hg-reviewers |
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.
| Lint Skipped |
| Unit Tests Skipped |
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.
@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.
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.
| Path | Packages | |||
|---|---|---|---|---|
| M | mercurial/setdiscovery.py (32 lines) | |||
| M | rust/hg-core/src/discovery.rs (43 lines) | |||
| M | rust/hg-cpython/src/discovery.rs (4 lines) | |||
| M | tests/test-rust-discovery.py (4 lines) |
| Commit | Parents | Author | Summary | Date |
|---|---|---|---|---|
| Georges Racinet | Apr 28 2019, 9:47 AM |
| 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 | ||||
| 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(()) | ||||
| 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) | ||||
| 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__) | ||||