Mercurial > hg
view rust/hg-core/tests/test_missing_ancestors.rs @ 51801:62b25293b620 default tip
typing: correct a type hint in `mercurial.manifest`
Obvious typo that was flagged by PyCharm.
author | Matt Harbison <matt_harbison@yahoo.com> |
---|---|
date | Wed, 14 Aug 2024 03:25:16 -0400 |
parents | 76c44ae8862e |
children |
line wrap: on
line source
use hg::testing::VecGraph; use hg::Revision; use hg::*; use rand::distributions::{Distribution, Uniform}; use rand::{thread_rng, Rng, RngCore, SeedableRng}; use rand_distr::LogNormal; use std::cmp::min; use std::collections::HashSet; use std::env; use std::fmt::Debug; fn build_random_graph( nodes_opt: Option<usize>, rootprob_opt: Option<f64>, mergeprob_opt: Option<f64>, prevprob_opt: Option<f64>, ) -> VecGraph { let nodes = nodes_opt.unwrap_or(100); let rootprob = rootprob_opt.unwrap_or(0.05); let mergeprob = mergeprob_opt.unwrap_or(0.2); let prevprob = prevprob_opt.unwrap_or(0.7); let mut rng = thread_rng(); let mut vg: VecGraph = Vec::with_capacity(nodes); for i in 0..nodes { if i == 0 || rng.gen_bool(rootprob) { vg.push([NULL_REVISION, NULL_REVISION]) } else if i == 1 { vg.push([Revision(0), NULL_REVISION]) } else if rng.gen_bool(mergeprob) { let p1 = { if i == 2 || rng.gen_bool(prevprob) { Revision((i - 1) as BaseRevision) } else { Revision(rng.gen_range(0..i - 1) as BaseRevision) } }; // p2 is a random revision lower than i and different from p1 let mut p2 = Revision(rng.gen_range(0..i - 1) as BaseRevision); if p2 >= p1 { p2.0 += 1; } vg.push([p1, p2]); } else if rng.gen_bool(prevprob) { vg.push([Revision((i - 1) as BaseRevision), NULL_REVISION]) } else { vg.push([ Revision(rng.gen_range(0..i - 1) as BaseRevision), NULL_REVISION, ]) } } vg } /// Compute the ancestors set of all revisions of a VecGraph fn ancestors_sets(vg: &VecGraph) -> Vec<HashSet<Revision>> { let mut ancs: Vec<HashSet<Revision>> = Vec::new(); (0..vg.len()).for_each(|i| { let mut ancs_i = HashSet::new(); ancs_i.insert(Revision(i as BaseRevision)); for p in vg[i].iter().cloned() { if p != NULL_REVISION { ancs_i.extend(&ancs[p.0 as usize]); } } ancs.push(ancs_i); }); ancs } #[allow(unused)] // Useful when debugging #[derive(Clone, Debug)] enum MissingAncestorsAction { InitialBases(HashSet<Revision>), AddBases(HashSet<Revision>), RemoveAncestorsFrom(HashSet<Revision>), MissingAncestors(HashSet<Revision>), } /// An instrumented naive yet obviously correct implementation /// /// It also records all its actions for easy reproduction for replay /// of problematic cases struct NaiveMissingAncestors<'a> { ancestors_sets: &'a Vec<HashSet<Revision>>, graph: &'a VecGraph, // used for error reporting only bases: HashSet<Revision>, history: Vec<MissingAncestorsAction>, // for error reporting, assuming we are in a random test random_seed: String, } impl<'a> NaiveMissingAncestors<'a> { fn new( graph: &'a VecGraph, ancestors_sets: &'a Vec<HashSet<Revision>>, bases: &HashSet<Revision>, random_seed: &str, ) -> Self { Self { ancestors_sets, bases: bases.clone(), graph, history: vec![MissingAncestorsAction::InitialBases(bases.clone())], random_seed: random_seed.into(), } } fn add_bases(&mut self, new_bases: HashSet<Revision>) { self.bases.extend(&new_bases); self.history .push(MissingAncestorsAction::AddBases(new_bases)) } fn remove_ancestors_from(&mut self, revs: &mut HashSet<Revision>) { revs.remove(&NULL_REVISION); self.history .push(MissingAncestorsAction::RemoveAncestorsFrom(revs.clone())); for base in self.bases.iter().cloned() { if base != NULL_REVISION { for rev in &self.ancestors_sets[base.0 as usize] { revs.remove(rev); } } } } fn missing_ancestors( &mut self, revs: impl IntoIterator<Item = Revision>, ) -> Vec<Revision> { let revs_as_set: HashSet<Revision> = revs.into_iter().collect(); let mut missing: HashSet<Revision> = HashSet::new(); for rev in revs_as_set.iter().cloned() { if rev != NULL_REVISION { missing.extend(&self.ancestors_sets[rev.0 as usize]) } } self.history .push(MissingAncestorsAction::MissingAncestors(revs_as_set)); for base in self.bases.iter().cloned() { if base != NULL_REVISION { for rev in &self.ancestors_sets[base.0 as usize] { missing.remove(rev); } } } let mut res: Vec<Revision> = missing.iter().cloned().collect(); res.sort_unstable(); res } fn assert_eq<T>(&self, left: T, right: T) where T: PartialEq + Debug, { if left == right { return; } panic!( "Equality assertion failed (left != right) left={:?} right={:?} graph={:?} current bases={:?} history={:?} random seed={} ", left, right, self.graph, self.bases, self.history, self.random_seed, ); } } /// Choose a set of random revisions /// /// The size of the set is taken from a LogNormal distribution /// with default mu=1.1 and default sigma=0.8. Quoting the Python /// test this is taken from: /// the default mu and sigma give us a nice distribution of mostly /// single-digit counts (including 0) with some higher ones /// The sample may include NULL_REVISION fn sample_revs<R: RngCore>( rng: &mut R, maxrev: Revision, mu_opt: Option<f64>, sigma_opt: Option<f64>, ) -> HashSet<Revision> { let mu = mu_opt.unwrap_or(1.1); let sigma = sigma_opt.unwrap_or(0.8); let log_normal = LogNormal::new(mu, sigma).unwrap(); let nb = min(maxrev.0 as usize, log_normal.sample(rng).floor() as usize); let dist = Uniform::from(NULL_REVISION.0..maxrev.0); rng.sample_iter(&dist).take(nb).map(Revision).collect() } /// Produces the hexadecimal representation of a slice of bytes fn hex_bytes(bytes: &[u8]) -> String { let mut s = String::with_capacity(bytes.len() * 2); for b in bytes { s.push_str(&format!("{:x}", b)); } s } /// Fill a random seed from its hexadecimal representation. /// /// This signature is meant to be consistent with `RngCore::fill_bytes` fn seed_parse_in(hex: &str, seed: &mut [u8]) { if hex.len() != 32 { panic!("Seed {} is too short for 128 bits hex", hex); } for i in 0..8 { seed[i] = u8::from_str_radix(&hex[2 * i..2 * (i + 1)], 16) .unwrap_or_else(|_e| panic!("Seed {} is not 128 bits hex", hex)); } } /// Parse the parameters for `test_missing_ancestors()` /// /// Returns (graphs, instances, calls per instance) fn parse_test_missing_ancestors_params(var: &str) -> (usize, usize, usize) { let err_msg = "TEST_MISSING_ANCESTORS format: GRAPHS,INSTANCES,CALLS"; let params: Vec<usize> = var .split(',') .map(|n| n.trim().parse().expect(err_msg)) .collect(); if params.len() != 3 { panic!("{}", err_msg); } (params[0], params[1], params[2]) } #[test] /// This test creates lots of random VecGraphs, /// and compare a bunch of MissingAncestors for them with /// NaiveMissingAncestors that rely on precomputed transitive closures of /// these VecGraphs (ancestors_sets). /// /// For each generater graph, several instances of `MissingAncestors` are /// created, whose methods are called and checked a given number of times. /// /// This test can be parametrized by two environment variables: /// /// - TEST_RANDOM_SEED: must be 128 bits in hexadecimal /// - TEST_MISSING_ANCESTORS: "GRAPHS,INSTANCES,CALLS". The default is /// "100,10,10" /// /// This is slow: it runs on my workstation in about 5 seconds with the /// default parameters with a plain `cargo --test`. /// /// If you want to run it faster, especially if you're changing the /// parameters, use `cargo test --release`. /// For me, that gets it down to 0.15 seconds with the default parameters fn test_missing_ancestors_compare_naive() { let (graphcount, testcount, inccount) = match env::var("TEST_MISSING_ANCESTORS") { Err(env::VarError::NotPresent) => (100, 10, 10), Ok(val) => parse_test_missing_ancestors_params(&val), Err(env::VarError::NotUnicode(_)) => { panic!("TEST_MISSING_ANCESTORS is invalid"); } }; let mut seed: [u8; 16] = [0; 16]; match env::var("TEST_RANDOM_SEED") { Ok(val) => { seed_parse_in(&val, &mut seed); } Err(env::VarError::NotPresent) => { thread_rng().fill_bytes(&mut seed); } Err(env::VarError::NotUnicode(_)) => { panic!("TEST_RANDOM_SEED must be 128 bits in hex"); } } let hex_seed = hex_bytes(&seed); eprintln!("Random seed: {}", hex_seed); let mut rng = rand_pcg::Pcg32::from_seed(seed); eprint!("Checking MissingAncestors against brute force implementation "); eprint!("for {} random graphs, ", graphcount); eprintln!( "with {} instances for each and {} calls per instance", testcount, inccount, ); for g in 0..graphcount { if g != 0 && g % 100 == 0 { eprintln!("Tested with {} graphs", g); } let graph = build_random_graph(None, None, None, None); let graph_len = Revision(graph.len() as BaseRevision); let ancestors_sets = ancestors_sets(&graph); for _testno in 0..testcount { let bases: HashSet<Revision> = sample_revs(&mut rng, graph_len, None, None); let mut inc = MissingAncestors::<VecGraph>::new( graph.clone(), bases.clone(), ); let mut naive = NaiveMissingAncestors::new( &graph, &ancestors_sets, &bases, &hex_seed, ); for _m in 0..inccount { if rng.gen_bool(0.2) { let new_bases = sample_revs(&mut rng, graph_len, None, None); inc.add_bases(new_bases.iter().cloned()); naive.add_bases(new_bases); } if rng.gen_bool(0.4) { // larger set so that there are more revs to remove from let mut hrevs = sample_revs(&mut rng, graph_len, Some(1.5), None); let mut rrevs = hrevs.clone(); inc.remove_ancestors_from(&mut hrevs).unwrap(); naive.remove_ancestors_from(&mut rrevs); naive.assert_eq(hrevs, rrevs); } else { let revs = sample_revs(&mut rng, graph_len, None, None); let hm = inc.missing_ancestors(revs.iter().cloned()).unwrap(); let rm = naive.missing_ancestors(revs.iter().cloned()); naive.assert_eq(hm, rm); } } } } }