frdt 0.2.3

Edit and inspect Resonite FrDT (.brson) documents without expanding them to JSON
Documentation
//! Graft one slot subtree onto another document.
//!
//! Identifiers are remapped, the grafted root's `ParentReference` points at the
//! destination slot, and component `Type` indexes are rewritten against the
//! merged `Types` array. Unchanged strings and binaries are copied as ranges.

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

use crate::bson::{self, Element, ARRAY, DOCUMENT, INT32, INT64, STRING};
use crate::datatree;
use crate::error::{Error, Result};

#[derive(Clone, Copy, PartialEq, Eq)]
enum Kind {
    /// The slot that is being attached. Its `ParentReference` is replaced.
    GraftRoot,
    Slot,
    /// Immediate `IComponent` or asset element. Only its own `Type` is remapped.
    Component,
    Generic,
}

#[derive(Clone, Copy)]
struct Rewrite<'a> {
    id_map: &'a HashMap<String, String>,
    type_map: &'a HashMap<i64, i64>,
    kind: Kind,
    /// Set only while emitting the grafted root's `ParentReference`.
    parent_id: &'a str,
}

/// Insert `child_bson`'s slot at `child_slot` under the destination slot
/// `parent_off`. Returns the offset of the grafted slot in `dest`.
pub fn append_slot(
    dest: &mut Vec<u8>,
    parent_off: usize,
    child_bson: &[u8],
    child_slot: usize,
) -> Result<usize> {
    let parent_id = datatree::read_string_field(dest, parent_off, "ID")?
        .ok_or_else(|| Error::Invalid("parent slot has no ID".into()))?;

    let mut child_ids = Vec::new();
    datatree::collect_ids(child_bson, child_slot, &mut child_ids)?;
    if let Some(asset) = datatree::field(child_bson, 0, "Asset")? {
        if asset.ty == ARRAY {
            datatree::collect_ids(child_bson, asset.value_at, &mut child_ids)?;
        }
    }

    let dest_ids: HashSet<String> = datatree::document_ids(dest)?.into_iter().collect();
    let id_map = assign_ids(&dest_ids, &child_ids)?;
    let (extra_types, type_map) = merge_type_map(
        &datatree::read_types(dest)?,
        &datatree::read_types(child_bson)?,
    )?;

    let grafted = rewrite_doc(
        child_bson,
        child_slot,
        &Rewrite {
            id_map: &id_map,
            type_map: &type_map,
            kind: Kind::GraftRoot,
            parent_id: &parent_id,
        },
    )?;
    bson::validate(&grafted)?;
    let new_root_id = datatree::read_string_field(&grafted, 0, "ID")?
        .ok_or_else(|| Error::Invalid("grafted slot has no ID".into()))?;

    if !extra_types.is_empty() {
        append_type_names(dest, &extra_types)?;
    }
    merge_document_fields(dest, child_bson, "FeatureFlags")?;
    merge_document_fields(dest, child_bson, "TypeVersions")?;
    append_assets(dest, child_bson, &id_map, &type_map)?;

    // Earlier splices move the parent. Find it again by the original id.
    let parent = datatree::find_slot_by_id(dest, &parent_id)?
        .ok_or_else(|| Error::Invalid("parent slot disappeared during merge".into()))?;
    insert_child(dest, &parent, &grafted)?;
    let grafted_slot = datatree::find_slot_by_id(dest, &new_root_id)?
        .ok_or_else(|| Error::Invalid("grafted slot disappeared during merge".into()))?;
    Ok(grafted_slot.offset)
}

fn assign_ids(used: &HashSet<String>, needed: &[String]) -> Result<HashMap<String, String>> {
    let mut used = used.clone();
    let mut map = HashMap::new();
    for old in needed {
        if map.contains_key(old) {
            continue;
        }
        let fresh = loop {
            let id = random_id()?;
            if !used.contains(&id) {
                break id;
            }
        };
        used.insert(fresh.clone());
        map.insert(old.clone(), fresh);
    }
    Ok(map)
}

fn random_id() -> Result<String> {
    let mut bytes = [0u8; 16];
    getrandom::getrandom(&mut bytes).map_err(|e| Error::Invalid(format!("random: {e}")))?;
    let mut s = String::with_capacity(32);
    for b in bytes {
        s.push_str(&format!("{b:02x}"));
    }
    Ok(s)
}

/// Same canonical name reuses the destination index. New names append.
pub fn merge_type_map(
    dest: &[String],
    child: &[String],
) -> Result<(Vec<String>, HashMap<i64, i64>)> {
    let mut extra = Vec::new();
    let mut map = HashMap::new();
    for (i, name) in child.iter().enumerate() {
        let dest_index = if let Some(pos) = dest.iter().position(|d| d == name) {
            pos
        } else if let Some(pos) = extra.iter().position(|d| d == name) {
            dest.len() + pos
        } else {
            let pos = dest.len() + extra.len();
            extra.push(name.clone());
            pos
        };
        map.insert(i as i64, dest_index as i64);
    }
    Ok((extra, map))
}

fn rewrite_doc(buf: &[u8], doc_off: usize, ctx: &Rewrite<'_>) -> Result<Vec<u8>> {
    let mut body = Vec::new();
    let mut saw_parent = false;
    for el in bson::elements(buf, doc_off)? {
        if ctx.kind == Kind::GraftRoot && el.key == "ParentReference" {
            saw_parent = true;
        }
        rewrite_element(buf, &el, ctx, &mut body)?;
    }
    if ctx.kind == Kind::GraftRoot && !saw_parent {
        bson::push_element(
            &mut body,
            STRING,
            "ParentReference",
            &bson::string_value(ctx.parent_id),
        );
    }
    bson::finish_doc(&body)
}

fn rewrite_element(
    buf: &[u8],
    el: &Element<'_>,
    ctx: &Rewrite<'_>,
    body: &mut Vec<u8>,
) -> Result<()> {
    if ctx.kind == Kind::GraftRoot && el.key == "ParentReference" {
        bson::push_element(body, STRING, el.key, &bson::string_value(ctx.parent_id));
        return Ok(());
    }
    if ctx.kind == Kind::Component && el.key == "Type" && (el.ty == INT32 || el.ty == INT64) {
        let old = bson::decode_int(el.value, el.ty)?;
        let new = ctx.type_map.get(&old).copied().unwrap_or(old);
        match el.ty {
            INT32 => {
                let v = i32::try_from(new).map_err(|_| Error::TooLarge)?;
                bson::push_element(body, INT32, el.key, &bson::i32_value(v));
            }
            _ => bson::push_element(body, INT64, el.key, &bson::i64_value(new)),
        }
        return Ok(());
    }
    if el.ty == STRING {
        let s = bson::decode_string(el.value)?;
        if let Some(mapped) = ctx.id_map.get(s) {
            bson::push_element(body, STRING, el.key, &bson::string_value(mapped));
        } else {
            body.extend_from_slice(el.raw);
        }
        return Ok(());
    }
    let in_slot = ctx.kind == Kind::GraftRoot || ctx.kind == Kind::Slot;
    if in_slot && el.key == "Children" && el.ty == ARRAY {
        let rewritten = rewrite_array(buf, el.value_at, Kind::Slot, ctx)?;
        bson::push_element(body, ARRAY, el.key, &rewritten);
        return Ok(());
    }
    if in_slot && el.key == "Components" && el.ty == DOCUMENT {
        let rewritten = rewrite_components(buf, el.value_at, ctx)?;
        bson::push_element(body, DOCUMENT, el.key, &rewritten);
        return Ok(());
    }
    if el.ty == DOCUMENT || el.ty == ARRAY {
        let generic = Rewrite {
            kind: Kind::Generic,
            ..*ctx
        };
        let rewritten = if el.ty == ARRAY {
            rewrite_array(buf, el.value_at, Kind::Generic, &generic)?
        } else {
            rewrite_doc(buf, el.value_at, &generic)?
        };
        bson::push_element(body, el.ty, el.key, &rewritten);
        return Ok(());
    }
    // Unchanged double, binary, bool, int, null: copy the original element bytes.
    body.extend_from_slice(el.raw);
    Ok(())
}

/// `Components` is `UniquePtr(Array(IComponent))`: `{ID, Data: [component, ...]}`.
fn rewrite_components(buf: &[u8], doc_off: usize, ctx: &Rewrite<'_>) -> Result<Vec<u8>> {
    let generic = Rewrite {
        kind: Kind::Generic,
        ..*ctx
    };
    let mut body = Vec::new();
    for el in bson::elements(buf, doc_off)? {
        if el.key == "Data" && el.ty == ARRAY {
            let rewritten = rewrite_array(buf, el.value_at, Kind::Component, ctx)?;
            bson::push_element(&mut body, ARRAY, el.key, &rewritten);
        } else {
            rewrite_element(buf, &el, &generic, &mut body)?;
        }
    }
    bson::finish_doc(&body)
}

fn rewrite_array(
    buf: &[u8],
    arr_off: usize,
    element_kind: Kind,
    ctx: &Rewrite<'_>,
) -> Result<Vec<u8>> {
    let mut body = Vec::new();
    for el in bson::elements(buf, arr_off)? {
        if el.ty == DOCUMENT && element_kind != Kind::Generic {
            let rewritten = rewrite_doc(
                buf,
                el.value_at,
                &Rewrite {
                    kind: element_kind,
                    ..*ctx
                },
            )?;
            bson::push_element(&mut body, DOCUMENT, el.key, &rewritten);
        } else if el.ty == DOCUMENT || el.ty == ARRAY {
            rewrite_element(
                buf,
                &el,
                &Rewrite {
                    kind: Kind::Generic,
                    ..*ctx
                },
                &mut body,
            )?;
        } else {
            rewrite_element(buf, &el, ctx, &mut body)?;
        }
    }
    bson::finish_doc(&body)
}

fn append_type_names(dest: &mut Vec<u8>, names: &[String]) -> Result<()> {
    let types = datatree::field(dest, 0, "Types")?
        .ok_or_else(|| Error::Invalid("destination has no Types".into()))?;
    if types.ty != ARRAY {
        return Err(Error::Invalid("Types is not an array".into()));
    }
    let existing = bson::elements(dest, types.value_at)?.len();
    let mut extra = Vec::new();
    for (i, name) in names.iter().enumerate() {
        bson::push_element(
            &mut extra,
            STRING,
            &(existing + i).to_string(),
            &bson::string_value(name),
        );
    }
    insert_before_terminator(dest, types.value_at, &extra, &[types.value_at, 0])
}

/// Copy child fields whose keys are absent on the destination. Destination wins.
fn merge_document_fields(dest: &mut Vec<u8>, child: &[u8], field_name: &str) -> Result<()> {
    let Some(src) = datatree::field(child, 0, field_name)? else {
        return Ok(());
    };
    if src.ty != DOCUMENT {
        return Err(Error::Invalid(format!("{field_name} is not a document")));
    }
    let Some(dst) = datatree::field(dest, 0, field_name)? else {
        return Ok(());
    };
    if dst.ty != DOCUMENT {
        return Err(Error::Invalid(format!("{field_name} is not a document")));
    }
    let have: HashSet<String> = bson::elements(dest, dst.value_at)?
        .into_iter()
        .map(|e| e.key.to_string())
        .collect();
    let mut extra = Vec::new();
    for el in bson::elements(child, src.value_at)? {
        if !have.contains(el.key) {
            extra.extend_from_slice(el.raw);
        }
    }
    if extra.is_empty() {
        return Ok(());
    }
    insert_before_terminator(dest, dst.value_at, &extra, &[dst.value_at, 0])
}

fn append_assets(
    dest: &mut Vec<u8>,
    child: &[u8],
    id_map: &HashMap<String, String>,
    type_map: &HashMap<i64, i64>,
) -> Result<()> {
    let Some(src) = datatree::field(child, 0, "Asset")? else {
        return Ok(());
    };
    if src.ty != ARRAY {
        return Err(Error::Invalid("Asset is not an array".into()));
    }
    let src_elems = bson::elements(child, src.value_at)?;
    if src_elems.is_empty() {
        return Ok(());
    }
    let Some(dst) = datatree::field(dest, 0, "Asset")? else {
        return Ok(());
    };
    if dst.ty != ARRAY {
        return Err(Error::Invalid("Asset is not an array".into()));
    }
    let existing = bson::elements(dest, dst.value_at)?.len();
    let ctx = Rewrite {
        id_map,
        type_map,
        kind: Kind::Generic,
        parent_id: "",
    };
    let mut extra = Vec::new();
    for (i, el) in src_elems.iter().enumerate() {
        if el.ty != DOCUMENT {
            return Err(Error::Invalid("Asset entry is not a document".into()));
        }
        let rewritten = rewrite_doc(
            child,
            el.value_at,
            &Rewrite {
                kind: Kind::Component,
                ..ctx
            },
        )?;
        bson::push_element(
            &mut extra,
            DOCUMENT,
            &(existing + i).to_string(),
            &rewritten,
        );
    }
    insert_before_terminator(dest, dst.value_at, &extra, &[dst.value_at, 0])
}

fn insert_child(dest: &mut Vec<u8>, parent: &datatree::SlotLoc, grafted: &[u8]) -> Result<()> {
    let arr = parent
        .children_array
        .ok_or_else(|| Error::Invalid("parent slot has no Children array".into()))?;
    let existing = bson::elements(dest, arr)?.len();
    let mut element = Vec::new();
    bson::push_element(&mut element, DOCUMENT, &existing.to_string(), grafted);
    let mut lengths = vec![arr];
    lengths.extend_from_slice(&parent.container_lengths);
    insert_before_terminator(dest, arr, &element, &lengths)
}

fn insert_before_terminator(
    buf: &mut Vec<u8>,
    doc_off: usize,
    bytes: &[u8],
    length_offs: &[usize],
) -> Result<()> {
    let len = bson::doc_len(buf, doc_off)?;
    let insert_at = doc_off + len - 1;
    bson::splice(buf, insert_at, insert_at, bytes, length_offs)
}