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>,
by_offset: HashMap<usize, usize>,
by_key: HashMap<u64, usize>,
next: u64,
}
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])
}
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)
}
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)
}
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 {
pub fn keys(&self) -> Vec<u64> {
self.slots.iter().map(|s| s.key).collect()
}
pub fn next_key(&self) -> u64 {
self.next
}
pub fn position(&self, offset: usize) -> Option<usize> {
self.by_offset.get(&offset).copied()
}
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)
}
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())
}