frdt 0.3.0

Edit and inspect Resonite FrDT (.brson) documents without expanding them to JSON
Documentation
//! Renumber every identifier of a document from a seed.
//!
//! The new ids depend only on the seed and on the order in which the ids are
//! defined in the document, so the same document always comes out the same.
//! Ids made at random along the way (`Document::empty`, `add_slot`,
//! `add_component`, `import`) stop mattering once this runs before writing.
//!
//! - Ids are taken in BSON order: the root slot tree depth first (each slot's
//!   own fields, its components, then its children), then `Assets`.
//! - Every other string equal to a renamed id is a reference and is rewritten.
//! - The root slot's `ParentReference` names nothing in the file; when it is
//!   a GUID it gets the next generated id too, so it does not stay random,
//!   and every other string equal to it is rewritten with it.
//! - A string that names an id this document does not define is left as is.
//! - A generated id never equals any string already in the document.

use std::collections::{HashMap, HashSet};

use crate::bson::{self, ARRAY, DOCUMENT, STRING};
use crate::datatree;
use crate::error::Result;
use crate::ids;

/// Rewrite `buf` with renumbered ids. Returns how many ids were renumbered.
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)
}

/// Copy the document at `off`, mapping strings.
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)
}

/// Version 4 GUIDs from SplitMix64 over a counter. The same seed gives the
/// same sequence on every platform.
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"));
        }
        // Pinned so that a change to the sequence is noticed: outputs written
        // with one frdt version must stay byte-identical with the next.
        assert_eq!(Generator::new(0).next_guid(), PINNED_SEED0_FIRST);
    }

    const PINNED_SEED0_FIRST: &str = "e220a839-7b1d-4daf-ad0f-28c7e7e786b2";
}