frdt 0.3.0

Edit and inspect Resonite FrDT (.brson) documents without expanding them to JSON
Documentation
//! Slot and component index over one decompressed BSON buffer.
//!
//! The index is rebuilt after every edit. The work file stores a copy so the
//! next open can skip the walk when the copy still matches the BSON.

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

use crate::bson;
use crate::datatree::{self, SlotLoc};
use crate::error::{Error, Result};

pub const INDEX_VERSION: u32 = 1;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ComponentRec {
    pub offset: usize,
    pub type_index: i64,
    pub slot_offset: usize,
}

#[derive(Debug, Clone)]
pub struct Index {
    pub root_slot: usize,
    pub types: Vec<String>,
    pub slots: Vec<SlotLoc>,
    pub components: Vec<ComponentRec>,
    /// Slot offset to position in `slots`. Derived; not written to `FRWK`.
    by_offset: HashMap<usize, usize>,
    /// Slot key to position in `slots`. Derived.
    by_key: HashMap<u64, usize>,
    /// The next key to hand out. It only grows for the life of a document,
    /// so a key that belonged to a removed slot is never given to another
    /// slot, and a handle to a removed slot keeps failing with `NotFound`.
    next: u64,
}

/// The lookup maps are derived from `slots`, and `next` is allocation state,
/// so equality ignores them.
impl PartialEq for Index {
    fn eq(&self, other: &Self) -> bool {
        self.root_slot == other.root_slot
            && self.types == other.types
            && self.slots == other.slots
            && self.components == other.components
    }
}

impl Eq for Index {}

impl Index {
    pub fn slot_by_offset(&self, offset: usize) -> Option<&SlotLoc> {
        self.by_offset.get(&offset).map(|&i| &self.slots[i])
    }

    pub fn slot_by_key(&self, key: u64) -> Option<&SlotLoc> {
        self.by_key.get(&key).map(|&i| &self.slots[i])
    }

    /// Recompute the lookup maps after `slots` or their keys change.
    fn relink(&mut self) {
        self.by_offset = self
            .slots
            .iter()
            .enumerate()
            .map(|(i, s)| (s.offset, i))
            .collect();
        self.by_key = self
            .slots
            .iter()
            .enumerate()
            .map(|(i, s)| (s.key, i))
            .collect();
    }
}

pub fn build(buf: &[u8]) -> Result<Index> {
    let mut index = build_unkeyed(buf)?;
    for (i, slot) in index.slots.iter_mut().enumerate() {
        slot.key = (i as u64) + 1;
    }
    index.next = index.slots.len() as u64 + 1;
    index.relink();
    Ok(index)
}

/// Rebuild after an edit, keeping each existing slot's [`SlotLoc::key`].
///
/// A field edit does not add or remove slots, so keys follow depth-first order
/// and stay valid even when `ID` itself is rewritten. An `append` adds slots.
/// Existing slots are matched by id, and each id keeps a queue of keys in
/// depth-first order so a duplicated id does not collapse two slots onto one
/// key. Slots with no remaining key receive a fresh one.
pub fn rebuild(buf: &[u8], previous: &Index) -> Result<Index> {
    let mut index = build_unkeyed(buf)?;
    if previous.slots.len() == index.slots.len() {
        for (old, new) in previous.slots.iter().zip(index.slots.iter_mut()) {
            new.key = old.key;
        }
        index.next = previous.next;
        index.relink();
        return Ok(index);
    }
    let mut old_keys: HashMap<&str, VecDeque<u64>> = HashMap::new();
    for slot in &previous.slots {
        old_keys
            .entry(slot.id.as_str())
            .or_default()
            .push_back(slot.key);
    }
    let mut next = previous.next;
    for slot in &mut index.slots {
        let reused = old_keys
            .get_mut(slot.id.as_str())
            .and_then(VecDeque::pop_front);
        if let Some(key) = reused {
            slot.key = key;
        } else {
            slot.key = next;
            next += 1;
        }
    }
    index.next = next;
    index.relink();
    Ok(index)
}

/// Rebuild after an edit whose effect on slot order the caller knows.
/// `keys[i]` is the key of the i-th slot in depth-first order. `next` is the
/// next key to hand out afterwards; it never goes below `previous.next`.
pub fn rebuild_keys(buf: &[u8], previous: &Index, keys: &[u64], next: u64) -> Result<Index> {
    let mut index = build_unkeyed(buf)?;
    if index.slots.len() != keys.len() {
        return Err(Error::Invalid("slot count changed unexpectedly".into()));
    }
    for (slot, key) in index.slots.iter_mut().zip(keys) {
        slot.key = *key;
    }
    index.next = next.max(previous.next);
    index.relink();
    Ok(index)
}

impl Index {
    /// Keys in depth-first order.
    pub fn keys(&self) -> Vec<u64> {
        self.slots.iter().map(|s| s.key).collect()
    }

    /// A key no slot of this document has had.
    pub fn next_key(&self) -> u64 {
        self.next
    }

    /// Position in depth-first order of the slot at `offset`.
    pub fn position(&self, offset: usize) -> Option<usize> {
        self.by_offset.get(&offset).copied()
    }

    /// Positions `[start, end)` of the slot at `pos` and its descendants.
    /// Depth-first order keeps a subtree contiguous.
    pub fn subtree(&self, pos: usize) -> (usize, usize) {
        let root = &self.slots[pos];
        let mut end = pos + 1;
        while end < self.slots.len() && self.slots[end].offset < root.end {
            end += 1;
        }
        (pos, end)
    }
}

fn build_unkeyed(buf: &[u8]) -> Result<Index> {
    bson::validate(buf)?;
    let types = datatree::read_types(buf)?;
    let slots = datatree::all_slots(buf)?;
    let root_slot = slots
        .first()
        .map(|s| s.offset)
        .ok_or_else(|| Error::Invalid("no slots".into()))?;
    let mut components = Vec::new();
    for slot in &slots {
        for comp in datatree::components_of_slot(buf, slot.offset, &types)? {
            components.push(ComponentRec {
                offset: comp.offset,
                type_index: comp.type_index,
                slot_offset: slot.offset,
            });
        }
    }
    let mut index = Index {
        root_slot,
        types,
        slots,
        components,
        by_offset: HashMap::new(),
        by_key: HashMap::new(),
        next: 0,
    };
    index.relink();
    Ok(index)
}

pub fn write_index(index: &Index, out: &mut Vec<u8>) {
    out.extend_from_slice(&INDEX_VERSION.to_le_bytes());
    write_u32(out, index.types.len() as u32);
    for t in &index.types {
        write_str(out, t);
    }
    write_u64(out, index.root_slot as u64);
    write_u32(out, index.slots.len() as u32);
    for slot in &index.slots {
        write_u64(out, slot.offset as u64);
        write_u64(out, slot.end as u64);
        write_str(out, &slot.id);
        match &slot.parent_ref {
            Some(p) => {
                out.push(1);
                write_str(out, p);
            }
            None => out.push(0),
        }
        write_str(out, &slot.name);
        match slot.children_array {
            Some(off) => {
                out.push(1);
                write_u64(out, off as u64);
            }
            None => out.push(0),
        }
        write_u32(out, slot.container_lengths.len() as u32);
        for off in &slot.container_lengths {
            write_u64(out, *off as u64);
        }
    }
    write_u32(out, index.components.len() as u32);
    for comp in &index.components {
        write_u64(out, comp.offset as u64);
        out.extend_from_slice(&comp.type_index.to_le_bytes());
        write_u64(out, comp.slot_offset as u64);
    }
}

pub fn read_index(mut input: &[u8]) -> Result<Index> {
    let version = read_u32(&mut input)?;
    if version != INDEX_VERSION {
        return Err(Error::Invalid(format!("index version {version}")));
    }
    let type_count = {
        let count = read_u32(&mut input)?;
        capped_count(input, count)?
    };
    let mut types = Vec::with_capacity(type_count);
    for _ in 0..type_count {
        types.push(read_str(&mut input)?);
    }
    let root_slot = read_usize(&mut input)?;
    let slot_count = {
        let count = read_u32(&mut input)?;
        capped_count(input, count)?
    };
    let mut slots = Vec::with_capacity(slot_count);
    for _ in 0..slot_count {
        let offset = read_usize(&mut input)?;
        let end = read_usize(&mut input)?;
        let id = read_str(&mut input)?;
        let parent_ref = if read_u8(&mut input)? == 1 {
            Some(read_str(&mut input)?)
        } else {
            None
        };
        let name = read_str(&mut input)?;
        let children_array = if read_u8(&mut input)? == 1 {
            Some(read_usize(&mut input)?)
        } else {
            None
        };
        let n = {
            let count = read_u32(&mut input)?;
            capped_count(input, count)?
        };
        let mut container_lengths = Vec::with_capacity(n);
        for _ in 0..n {
            container_lengths.push(read_usize(&mut input)?);
        }
        slots.push(SlotLoc {
            key: 0,
            offset,
            end,
            id,
            parent_ref,
            name,
            children_array,
            container_lengths,
        });
    }
    let comp_count = {
        let count = read_u32(&mut input)?;
        capped_count(input, count)?
    };
    let mut components = Vec::with_capacity(comp_count);
    for _ in 0..comp_count {
        let offset = read_usize(&mut input)?;
        let type_index = read_i64(&mut input)?;
        let slot_offset = read_usize(&mut input)?;
        components.push(ComponentRec {
            offset,
            type_index,
            slot_offset,
        });
    }
    if !input.is_empty() {
        return Err(Error::Invalid("trailing index bytes".into()));
    }
    let mut index = Index {
        root_slot,
        types,
        slots,
        components,
        by_offset: HashMap::new(),
        by_key: HashMap::new(),
        next: 0,
    };
    index.relink();
    Ok(index)
}

fn write_u32(out: &mut Vec<u8>, v: u32) {
    out.extend_from_slice(&v.to_le_bytes());
}
fn write_u64(out: &mut Vec<u8>, v: u64) {
    out.extend_from_slice(&v.to_le_bytes());
}
fn write_str(out: &mut Vec<u8>, s: &str) {
    write_u32(out, s.len() as u32);
    out.extend_from_slice(s.as_bytes());
}

fn read_u8(input: &mut &[u8]) -> Result<u8> {
    if input.is_empty() {
        return Err(Error::Truncated);
    }
    let b = input[0];
    *input = &input[1..];
    Ok(b)
}
fn read_u32(input: &mut &[u8]) -> Result<u32> {
    if input.len() < 4 {
        return Err(Error::Truncated);
    }
    let v = u32::from_le_bytes(input[..4].try_into().unwrap());
    *input = &input[4..];
    Ok(v)
}
fn read_u64(input: &mut &[u8]) -> Result<u64> {
    if input.len() < 8 {
        return Err(Error::Truncated);
    }
    let v = u64::from_le_bytes(input[..8].try_into().unwrap());
    *input = &input[8..];
    Ok(v)
}

fn read_usize(input: &mut &[u8]) -> Result<usize> {
    usize::try_from(read_u64(input)?).map_err(|_| Error::TooLarge)
}

/// Reject a count that cannot fit in the remaining bytes before allocating.
fn capped_count(input: &[u8], count: u32) -> Result<usize> {
    let count = count as usize;
    if count > input.len() {
        return Err(Error::TooLarge);
    }
    Ok(count)
}
fn read_i64(input: &mut &[u8]) -> Result<i64> {
    Ok(read_u64(input)? as i64)
}
fn read_str(input: &mut &[u8]) -> Result<String> {
    let n = read_u32(input)? as usize;
    if input.len() < n {
        return Err(Error::Truncated);
    }
    let s = std::str::from_utf8(&input[..n]).map_err(|_| Error::Invalid("index string".into()))?;
    *input = &input[n..];
    Ok(s.to_string())
}