| 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 |
| 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 | May 21 2019, 11:43 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, | ||||
| samplegrowth=1.05): | samplegrowth=1.05): | ||||
| 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__) | ||||