use std::collections::{HashMap, HashSet};
use crate::bson::{self, ARRAY, DOCUMENT, STRING};
use crate::datatree;
use crate::error::Result;
use crate::ids;
pub fn renumber(buf: &mut Vec<u8>, seed: u64) -> Result<usize> {
let mut defined: Vec<&str> = Vec::new();
let mut seen_defined: HashSet<&str> = HashSet::new();
ids::visit_defined(buf, 0, &mut |id| {
if seen_defined.insert(id) {
defined.push(id);
}
})?;
let mut others: HashSet<&str> = HashSet::new();
ids::visit_strings(buf, 0, &mut |s| {
others.insert(s);
})?;
let root_off = datatree::root_slot_offset(buf)?;
let root_parent = datatree::read_string_field(buf, root_off, "ParentReference")?;
let mut gen = Generator::new(seed);
let mut used: HashSet<String> = HashSet::new();
let mut fresh = |gen: &mut Generator| -> String {
loop {
let id = gen.next_guid();
if !others.contains(id.as_str())
&& !seen_defined.contains(id.as_str())
&& used.insert(id.clone())
{
return id;
}
}
};
let mut map: HashMap<String, String> = HashMap::with_capacity(defined.len());
for old in &defined {
let id = fresh(&mut gen);
map.insert((*old).to_string(), id);
}
let count = map.len();
if let Some(p) = root_parent {
if !map.contains_key(&p) && is_guid(&p) {
let id = fresh(&mut gen);
map.insert(p, id);
}
}
let rewritten = rewrite(buf, 0, &map)?;
bson::validate(&rewritten)?;
*buf = rewritten;
Ok(count)
}
fn rewrite(buf: &[u8], off: usize, map: &HashMap<String, String>) -> Result<Vec<u8>> {
let mut body = Vec::new();
for el in bson::elements(buf, off)? {
match el.ty {
STRING => {
let s = bson::decode_string(el.value)?;
match map.get(s) {
Some(new) => {
bson::push_element(&mut body, STRING, el.key, &bson::string_value(new))
}
None => body.extend_from_slice(el.raw),
}
}
DOCUMENT | ARRAY => {
let inner = rewrite(buf, el.value_at, map)?;
bson::push_element(&mut body, el.ty, el.key, &inner);
}
_ => body.extend_from_slice(el.raw),
}
}
bson::finish_doc(&body)
}
struct Generator {
seed: u64,
counter: u64,
}
impl Generator {
fn new(seed: u64) -> Self {
Generator { seed, counter: 0 }
}
fn next_guid(&mut self) -> String {
let n = self.counter;
self.counter += 1;
let base = self.seed ^ n.wrapping_mul(0x9E37_79B9_7F4A_7C15);
let a = splitmix64(base);
let b = splitmix64(base ^ 0xD1B5_4A32_D192_ED03);
let mut bytes = [0u8; 16];
bytes[..8].copy_from_slice(&a.to_be_bytes());
bytes[8..].copy_from_slice(&b.to_be_bytes());
bytes[6] = (bytes[6] & 0x0f) | 0x40;
bytes[8] = (bytes[8] & 0x3f) | 0x80;
let hex: String = bytes.iter().map(|x| format!("{x:02x}")).collect();
format!(
"{}-{}-{}-{}-{}",
&hex[0..8],
&hex[8..12],
&hex[12..16],
&hex[16..20],
&hex[20..32]
)
}
}
fn is_guid(s: &str) -> bool {
let b = s.as_bytes();
b.len() == 36
&& b.iter().enumerate().all(|(i, c)| match i {
8 | 13 | 18 | 23 => *c == b'-',
_ => c.is_ascii_hexdigit(),
})
}
fn splitmix64(x: u64) -> u64 {
let mut z = x.wrapping_add(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn generator_is_fixed_for_a_seed() {
let mut a = Generator::new(7);
let mut b = Generator::new(7);
let mut c = Generator::new(8);
let xs: Vec<String> = (0..4).map(|_| a.next_guid()).collect();
let ys: Vec<String> = (0..4).map(|_| b.next_guid()).collect();
let zs: Vec<String> = (0..4).map(|_| c.next_guid()).collect();
assert_eq!(xs, ys);
assert_ne!(xs, zs);
assert_eq!(xs.iter().collect::<HashSet<_>>().len(), 4);
for id in &xs {
assert_eq!(id.len(), 36);
assert_eq!(&id[14..15], "4");
assert!(matches!(&id[19..20], "8" | "9" | "a" | "b"));
}
assert_eq!(Generator::new(0).next_guid(), PINNED_SEED0_FIRST);
}
const PINNED_SEED0_FIRST: &str = "e220a839-7b1d-4daf-ad0f-28c7e7e786b2";
}