Patchwork D5417: rust: translated random test of missingancestors

login
register
mail settings
Submitter phabricator
Date Feb. 13, 2019, 12:51 p.m.
Message ID <ebceb4b0b6146f61df4be5416a815866@localhost.localdomain>
Download mbox | patch
Permalink /patch/38716/
State Not Applicable
Headers show

Comments

phabricator - Feb. 13, 2019, 12:51 p.m.
This revision was automatically updated to reflect the committed changes.
Closed by commit rHG9370f4843084: rust: translated random test of missingancestors (authored by gracinet, committed by ).

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5417?vs=14044&id=14067

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/lib.rs
  rust/hg-core/tests/test_missing_ancestors.rs

CHANGE DETAILS




To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel

Patch

diff --git a/rust/hg-core/tests/test_missing_ancestors.rs b/rust/hg-core/tests/test_missing_ancestors.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/tests/test_missing_ancestors.rs
@@ -0,0 +1,340 @@ 
+extern crate hg;
+extern crate rand;
+extern crate rand_pcg;
+
+use hg::testing::VecGraph;
+use hg::Revision;
+use hg::*;
+use rand::distributions::{Distribution, LogNormal, Uniform};
+use rand::{thread_rng, Rng, RngCore, SeedableRng};
+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([0, NULL_REVISION])
+        } else if rng.gen_bool(mergeprob) {
+            let p1 = {
+                if i == 2 || rng.gen_bool(prevprob) {
+                    (i - 1) as Revision
+                } else {
+                    rng.gen_range(0, i - 1) as Revision
+                }
+            };
+            // p2 is a random revision lower than i and different from p1
+            let mut p2 = rng.gen_range(0, i - 1) as Revision;
+            if p2 >= p1 {
+                p2 = p2 + 1;
+            }
+            vg.push([p1, p2]);
+        } else if rng.gen_bool(prevprob) {
+            vg.push([(i - 1) as Revision, NULL_REVISION])
+        } else {
+            vg.push([rng.gen_range(0, i - 1) as Revision, 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();
+    for i in 0..vg.len() {
+        let mut ancs_i = HashSet::new();
+        ancs_i.insert(i as Revision);
+        for p in vg[i].iter().cloned() {
+            if p != NULL_REVISION {
+                ancs_i.extend(&ancs[p as usize]);
+            }
+        }
+        ancs.push(ancs_i);
+    }
+    ancs
+}
+
+#[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: ancestors_sets,
+            bases: bases.clone(),
+            graph: 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 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 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 as usize] {
+                    missing.remove(&rev);
+                }
+            }
+        }
+        let mut res: Vec<Revision> = missing.iter().cloned().collect();
+        res.sort();
+        res
+    }
+
+    fn assert_eq<T>(&self, left: T, right: T)
+    where
+        T: PartialEq + Debug,
+    {
+        if left == right {
+            return;
+        }
+        panic!(format!(
+            "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);
+    let nb = min(maxrev as usize, log_normal.sample(rng).floor() as usize);
+
+    let dist = Uniform::from(NULL_REVISION..maxrev);
+    return rng.sample_iter(&dist).take(nb).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 = graph.len() as Revision;
+        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);
+                }
+            }
+        }
+    }
+}
diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs
+++ b/rust/hg-core/src/lib.rs
@@ -5,8 +5,7 @@ 
 mod ancestors;
 pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
-#[cfg(test)]
-pub mod testing;
+pub mod testing;  // unconditionally built, for use from integration tests
 
 /// Mercurial revision numbers
 ///
diff --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,7 @@ 
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
+rand_pcg = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -7,11 +7,29 @@ 
 ]
 
 [[package]]
+name = "autocfg"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "bitflags"
+version = "1.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "cfg-if"
 version = "0.1.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "cloudabi"
+version = "0.0.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "cpython"
 version = "0.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -23,8 +41,17 @@ 
 ]
 
 [[package]]
+name = "fuchsia-cprng"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
+dependencies = [
+ "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "hg-cpython"
@@ -89,6 +116,110 @@ 
 ]
 
 [[package]]
+name = "rand"
+version = "0.6.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_jitter 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_os 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "rand_hc"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_isaac"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_jitter"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_os"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fuchsia-cprng 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_pcg"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rand_xorshift"
+version = "0.1.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "rdrand"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "regex"
 version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -109,6 +240,27 @@ 
 ]
 
 [[package]]
+name = "rustc_version"
+version = "0.2.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "semver"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "semver-parser"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "thread_local"
 version = "0.3.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -131,19 +283,59 @@ 
 version = "0.1.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
+[[package]]
+name = "winapi"
+version = "0.3.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "winapi-i686-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "winapi-x86_64-pc-windows-gnu"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [metadata]
 "checksum aho-corasick 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "1e9a933f4e58658d7b12defcf96dc5c720f20832deebe3e0a19efd3b6aaeeb9e"
+"checksum autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a6d640bee2da49f60a4068a7fae53acde8982514ab7bae8b8cea9e88cbcfd799"
+"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
 "checksum cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "082bb9b28e00d3c9d39cc03e64ce4cea0f1bb9b3fde493f0cbc008472d22bdf4"
+"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b489034e723e7f5109fecd19b719e664f89ef925be785885252469e9822fa940"
+"checksum fuchsia-cprng 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "81f7f8eb465745ea9b02e2704612a9946a59fa40572086c6fd49d6ddcf30bf31"
 "checksum lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a374c89b9db55895453a74c1e38861d9deec0b01b405a82516e9d5de4820dea1"
 "checksum libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)" = "2d2857ec59fadc0773853c664d2d18e7198e83883e7060b63c924cb077bd5c74"
 "checksum memchr 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "db4c41318937f6e76648f42826b1d9ade5c09cafb5aef7e351240a70f39206e9"
 "checksum num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "0b3a5d7cc97d6d30d8b9bc8fa19bf45349ffe46241e8816f50f62f6d6aaabee1"
 "checksum python27-sys 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "56114c37d4dca82526d74009df7782a28c871ac9d36b19d4cb9e67672258527e"
 "checksum python3-sys 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "61e4aac43f833fd637e429506cb2ac9d7df672c4b68f2eaaa163649b7fdc0444"
+"checksum rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca"
+"checksum rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef"
+"checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b"
+"checksum rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d0e7a549d590831370895ab7ba4ea0c1b6b011d106b5ff2da6eee112615e6dc0"
+"checksum rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4"
+"checksum rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08"
+"checksum rand_jitter 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "080723c6145e37503a2224f801f252e14ac5531cb450f4502698542d188cb3c0"
+"checksum rand_os 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "b7c690732391ae0abafced5015ffb53656abfaec61b342290e5eb56b286a679d"
+"checksum rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05"
+"checksum rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cbf7e9e623549b0e21f6e97cf8ecf247c1a8fd2e8a992ae265314300b2455d5c"
+"checksum rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2"
 "checksum regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "37e7cbbd370869ce2e8dff25c7018702d10b21a20ef7135316f8daecd6c25b7f"
 "checksum regex-syntax 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)" = "4e47a2ed29da7a9e1960e1639e7a982e6edc6d49be308a3b02daf511504a16d1"
+"checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a"
+"checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403"
+"checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
 "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b"
 "checksum ucd-util 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "535c204ee4d8434478593480b8f86ab45ec9aae0e83c568ca81abf0fd0e88f86"
 "checksum utf8-ranges 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "796f7e48bef87609f7ade7e06495a87d5cd06c7866e6a5cbfceffc558a243737"
 "checksum version_check 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "914b1a6776c4c929a602fafd8bc742e06365d4bcbe48c30f9cca5824f70dc9dd"
+"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
+"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
+"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"