frdt 0.2.2

Edit and inspect Resonite FrDT (.brson) documents without expanding them to JSON
Documentation
//! Structural edits inside one document: new slots, new components, field
//! values, moving and removing slots.
//!
//! Every edit works on a copy of the BSON buffer and returns where it put
//! things; the caller rebuilds the index and commits. New elements are written
//! the way Resonite writes them: `{ID, Data}` fields, int64 integers, and double
//! arrays for `float3` / `floatQ`.

use std::collections::HashSet;

use crate::bson::{self, Element, ARRAY, BOOL, DOCUMENT, DOUBLE, INT64, NULL, STRING};
use crate::datatree::{self, SlotLoc};
use crate::empty;
use crate::error::{Error, Result};
use crate::ids::{self, new_guid};
use crate::index::Index;
use crate::value::Value;

/// `(BSON type, value bytes)` of a field's `Data` in Resonite's layout.
pub fn encode_data(value: Option<&Value>) -> Result<(u8, Vec<u8>)> {
    Ok(match value {
        None => (NULL, Vec::new()),
        Some(Value::F64(v)) => (DOUBLE, bson::f64_value(*v).to_vec()),
        Some(Value::I64(v)) => (INT64, bson::i64_value(*v).to_vec()),
        Some(Value::Bool(v)) => (BOOL, vec![u8::from(*v)]),
        Some(Value::String(v)) => (STRING, bson::string_value(v)),
        Some(Value::Float3(v)) => (ARRAY, empty::doubles(&[v.x, v.y, v.z])),
        Some(Value::FloatQ(v)) => (ARRAY, empty::doubles(&[v.x, v.y, v.z, v.w])),
    })
}

fn slot_loc(index: &Index, offset: usize) -> Result<&SlotLoc> {
    index.slot_by_offset(offset).ok_or(Error::NotFound)
}

fn slot_id(buf: &[u8], offset: usize) -> Result<String> {
    datatree::read_string_field(buf, offset, "ID")?
        .ok_or_else(|| Error::Invalid("slot has no ID".into()))
}

/// Append `slot` (a complete slot document) to the end of the parent's
/// `Children`.
pub fn insert_child(
    buf: &mut Vec<u8>,
    index: &Index,
    parent_off: usize,
    slot: &[u8],
) -> Result<()> {
    let parent = slot_loc(index, parent_off)?;
    let arr = parent
        .children_array
        .ok_or_else(|| Error::Invalid("parent slot has no Children array".into()))?;
    let existing = bson::elements(buf, arr)?.len();
    let mut element = Vec::new();
    bson::push_element(&mut element, DOCUMENT, &existing.to_string(), slot);
    let mut lengths = vec![arr];
    lengths.extend_from_slice(&parent.container_lengths);
    let at = bson::doc_end(buf, arr)? - 1;
    bson::splice(buf, at, at, &element, &lengths)
}

/// A new empty slot named `name` under `parent_off`. Returns its id.
pub fn add_slot(buf: &mut Vec<u8>, index: &Index, parent_off: usize, name: &str) -> Result<String> {
    let parent_id = slot_id(buf, parent_off)?;
    let slot = empty::new_slot(name, &parent_id)?;
    let id = datatree::read_string_field(&slot, 0, "ID")?.expect("new slot has an ID");
    insert_child(buf, index, parent_off, &slot)?;
    Ok(id)
}

/// Append a component to the slot at `slot_off`. Each field is written as
/// `{ID, Data}`. The type name is added to `Types` when missing; `version`
/// is added to `TypeVersions` when given and the name has no entry yet.
/// Returns the component's position in the slot and its id.
pub fn add_component(
    buf: &mut Vec<u8>,
    index: &Index,
    slot_off: usize,
    type_name: &str,
    version: Option<i64>,
    fields: &[(&str, Option<Value>)],
) -> Result<(usize, String)> {
    let mut seen = HashSet::new();
    for (key, _) in fields {
        if ids::is_id_key(key) {
            return Err(Error::Invalid(format!("{key} is written by add_component")));
        }
        if !seen.insert(*key) {
            return Err(Error::Invalid(format!("field {key} is given twice")));
        }
    }
    let slot = slot_loc(index, slot_off)?;
    let comps = datatree::field(buf, slot_off, "Components")?
        .ok_or_else(|| Error::Invalid("slot has no Components".into()))?;
    if comps.ty != DOCUMENT {
        return Err(Error::Invalid(
            "Components is not a UniquePtr document".into(),
        ));
    }
    let data = datatree::field(buf, comps.value_at, "Data")?
        .ok_or_else(|| Error::Invalid("Components has no Data".into()))?;
    if data.ty != ARRAY {
        return Err(Error::Invalid("Components.Data is not an array".into()));
    }
    let position = bson::elements(buf, data.value_at)?.len();

    let types = datatree::read_types(buf)?;
    let (type_index, new_type) = match types.iter().position(|t| t == type_name) {
        Some(i) => (i, false),
        None => (types.len(), true),
    };

    let id = new_guid()?;
    let mut body = Vec::new();
    bson::push_element(&mut body, STRING, "ID", &bson::string_value(&id));
    bson::push_element(
        &mut body,
        STRING,
        "persistent-ID",
        &bson::string_value(&new_guid()?),
    );
    for (key, value) in fields {
        let (ty, bytes) = encode_data(value.as_ref())?;
        let mut field = Vec::new();
        bson::push_element(&mut field, STRING, "ID", &bson::string_value(&new_guid()?));
        bson::push_element(&mut field, ty, "Data", &bytes);
        bson::push_element(&mut body, DOCUMENT, key, &bson::finish_doc(&field)?);
    }
    let mut comp = Vec::new();
    bson::push_element(
        &mut comp,
        INT64,
        "Type",
        &bson::i64_value(type_index as i64),
    );
    bson::push_element(&mut comp, DOCUMENT, "Data", &bson::finish_doc(&body)?);
    let mut element = Vec::new();
    bson::push_element(
        &mut element,
        DOCUMENT,
        &position.to_string(),
        &bson::finish_doc(&comp)?,
    );

    // Highest offset first: the component, then TypeVersions, then Types.
    let mut lengths = vec![data.value_at, comps.value_at];
    lengths.extend_from_slice(&slot.container_lengths);
    let at = bson::doc_end(buf, data.value_at)? - 1;
    let mut ops: Vec<(usize, Vec<u8>, Vec<usize>)> = vec![(at, element, lengths)];
    let mut root_tail = Vec::new();

    if let Some(v) = version {
        match datatree::field(buf, 0, "TypeVersions")? {
            Some(tv) if tv.ty == DOCUMENT => {
                let has = bson::elements(buf, tv.value_at)?
                    .iter()
                    .any(|e| e.key == type_name);
                if !has {
                    let mut el = Vec::new();
                    bson::push_element(&mut el, INT64, type_name, &bson::i64_value(v));
                    ops.push((
                        bson::doc_end(buf, tv.value_at)? - 1,
                        el,
                        vec![tv.value_at, 0],
                    ));
                }
            }
            Some(_) => return Err(Error::Invalid("TypeVersions is not a document".into())),
            None => {
                let mut doc = Vec::new();
                bson::push_element(&mut doc, INT64, type_name, &bson::i64_value(v));
                bson::push_element(
                    &mut root_tail,
                    DOCUMENT,
                    "TypeVersions",
                    &bson::finish_doc(&doc)?,
                );
            }
        }
    }
    if new_type {
        match datatree::field(buf, 0, "Types")? {
            Some(t) if t.ty == ARRAY => {
                let mut el = Vec::new();
                bson::push_element(
                    &mut el,
                    STRING,
                    &type_index.to_string(),
                    &bson::string_value(type_name),
                );
                ops.push((bson::doc_end(buf, t.value_at)? - 1, el, vec![t.value_at, 0]));
            }
            Some(_) => return Err(Error::Invalid("Types is not an array".into())),
            None => bson::push_element(
                &mut root_tail,
                ARRAY,
                "Types",
                &bson::array_of_strings(&[type_name]),
            ),
        }
    }
    if !root_tail.is_empty() {
        ops.push((bson::doc_end(buf, 0)? - 1, root_tail, vec![0]));
    }
    ops.sort_by_key(|op| std::cmp::Reverse(op.0));
    for (at, bytes, lengths) in ops {
        bson::splice(buf, at, at, &bytes, &lengths)?;
    }
    Ok((position, id))
}

/// Where an element sits, owned so the buffer can be edited afterwards.
pub struct Spot {
    pub start: usize,
    pub ty: u8,
    pub key: String,
    pub value_at: usize,
    pub value_end: usize,
}

impl From<&Element<'_>> for Spot {
    fn from(el: &Element<'_>) -> Self {
        Spot {
            start: el.start,
            ty: el.ty,
            key: el.key.to_string(),
            value_at: el.value_at,
            value_end: el.value_at + el.value.len(),
        }
    }
}

/// Replace the value at `spot`. When it is `{ID, Data}`, only `Data` changes
/// and the wrapper keeps its id; `value` is then written in Resonite's
/// layout. Otherwise the element itself is replaced with the v1 encoding
/// (`{x, y, z}` for `float3`). `lengths` are the documents that contain it.
pub fn replace_value(
    buf: &mut Vec<u8>,
    spot: &Spot,
    value: Option<&Value>,
    lengths: &[usize],
) -> Result<()> {
    if spot.ty == DOCUMENT {
        let inner: Vec<Spot> = bson::elements(buf, spot.value_at)?
            .iter()
            .map(Spot::from)
            .collect();
        if inner.iter().any(|e| e.key == "ID") {
            let data = inner
                .iter()
                .find(|e| e.key == "Data")
                .ok_or_else(|| Error::Invalid(format!("{} has no Data", spot.key)))?;
            let (ty, bytes) = encode_data(value)?;
            let mut new = Vec::new();
            bson::push_element(&mut new, ty, "Data", &bytes);
            let mut all = vec![spot.value_at];
            all.extend_from_slice(lengths);
            return bson::splice(buf, data.start, data.value_end, &new, &all);
        }
    }
    let (ty, bytes) = match value {
        Some(v) => (bson::value_type(v), bson::encode_value(v)?),
        None => (NULL, Vec::new()),
    };
    let mut new = Vec::new();
    bson::push_element(&mut new, ty, &spot.key, &bytes);
    bson::splice(buf, spot.start, spot.value_end, &new, lengths)
}

/// Set a field in the `component`-th component's `Data`.
pub fn set_component_value(
    buf: &mut Vec<u8>,
    index: &Index,
    slot_off: usize,
    component: usize,
    field: &str,
    value: Option<&Value>,
) -> Result<()> {
    if ids::is_id_key(field) {
        return Err(Error::Invalid(format!("{field} cannot be set")));
    }
    let slot = slot_loc(index, slot_off)?;
    let comps = datatree::field(buf, slot_off, "Components")?
        .ok_or_else(|| Error::Invalid("slot has no Components".into()))?;
    let arr = datatree::field(buf, comps.value_at, "Data")?
        .ok_or_else(|| Error::Invalid("Components has no Data".into()))?;
    let comp = bson::elements(buf, arr.value_at)?
        .into_iter()
        .nth(component)
        .ok_or_else(|| Error::Invalid(format!("no component at {component}")))?;
    let data = datatree::field(buf, comp.value_at, "Data")?
        .ok_or_else(|| Error::FieldNotFound("Data".into()))?;
    if data.ty != DOCUMENT {
        return Err(Error::Invalid("component Data is not a document".into()));
    }
    let spot = Spot::from(
        &datatree::field(buf, data.value_at, field)?
            .ok_or_else(|| Error::FieldNotFound(field.to_string()))?,
    );
    let mut lengths = vec![data.value_at, comp.value_at, arr.value_at, comps.value_at];
    lengths.extend_from_slice(&slot.container_lengths);
    replace_value(buf, &spot, value, &lengths)
}

/// Take the slot at `slot_off` out of its parent's `Children`. The remaining
/// children are renumbered. Returns the removed slot document.
pub fn remove_slot(buf: &mut Vec<u8>, index: &Index, slot_off: usize) -> Result<Vec<u8>> {
    if slot_off == index.root_slot {
        return Err(Error::Invalid(
            "the root slot cannot be removed or moved".into(),
        ));
    }
    let pos = index.position(slot_off).ok_or(Error::NotFound)?;
    // The parent is the closest earlier slot whose span contains this one.
    let parent = index.slots[..pos]
        .iter()
        .rev()
        .find(|s| s.offset < slot_off && slot_off < s.end)
        .ok_or_else(|| Error::Invalid("slot has no parent".into()))?;
    let arr = parent
        .children_array
        .ok_or_else(|| Error::Invalid("parent slot has no Children array".into()))?;
    let mut removed = None;
    let mut body = Vec::new();
    let mut n = 0usize;
    for el in bson::elements(buf, arr)? {
        if el.ty == DOCUMENT && el.value_at == slot_off {
            removed = Some(el.value.to_vec());
            continue;
        }
        bson::push_element(&mut body, el.ty, &n.to_string(), el.value);
        n += 1;
    }
    let removed = removed.ok_or(Error::NotFound)?;
    let new_arr = bson::finish_doc(&body)?;
    let end = bson::doc_end(buf, arr)?;
    bson::splice(buf, arr, end, &new_arr, &parent.container_lengths)?;
    Ok(removed)
}

/// A copy of a slot document with its own `ParentReference` replaced.
pub fn with_parent(slot: &[u8], parent_id: &str) -> Result<Vec<u8>> {
    let mut body = Vec::new();
    let mut saw = false;
    for el in bson::elements(slot, 0)? {
        if el.key == "ParentReference" {
            saw = true;
            bson::push_element(&mut body, STRING, el.key, &bson::string_value(parent_id));
        } else {
            body.extend_from_slice(el.raw);
        }
    }
    if !saw {
        bson::push_element(
            &mut body,
            STRING,
            "ParentReference",
            &bson::string_value(parent_id),
        );
    }
    bson::finish_doc(&body)
}

/// Keys in depth-first order after moving the subtree at old position
/// `moved` to be the last child of the slot at old position `parent`.
pub fn keys_after_move(index: &Index, moved: usize, parent: usize) -> Vec<u64> {
    let keys = index.keys();
    let (ms, me) = index.subtree(moved);
    let (_, pe) = index.subtree(parent);
    let moved_keys = keys[ms..me].to_vec();
    let mut rest: Vec<u64> = keys[..ms].iter().chain(&keys[me..]).copied().collect();
    // End of the new parent's subtree among the remaining slots.
    let insert_at = if pe > ms { pe - (me - ms) } else { pe };
    rest.splice(insert_at..insert_at, moved_keys);
    rest
}

/// Keys in depth-first order after removing the subtree at old position `pos`.
pub fn keys_after_remove(index: &Index, pos: usize) -> Vec<u64> {
    let keys = index.keys();
    let (s, e) = index.subtree(pos);
    keys[..s].iter().chain(&keys[e..]).copied().collect()
}

/// Keys after a new leaf slot becomes the last child of the slot at `parent`.
pub fn keys_after_add(index: &Index, parent: usize, new_key: u64) -> Vec<u64> {
    let mut keys = index.keys();
    let (_, pe) = index.subtree(parent);
    keys.insert(pe, new_key);
    keys
}

/// Whether the slot at `inner_off` is `outer_off` or inside it.
pub fn contains(index: &Index, outer_off: usize, inner_off: usize) -> Result<bool> {
    let outer = slot_loc(index, outer_off)?;
    Ok(outer.offset <= inner_off && inner_off < outer.end)
}