use std::collections::{HashMap, HashSet};
use crate::bson::{self, Element, ARRAY, DOCUMENT, STRING};
use crate::datatree;
use crate::error::{Error, Result};
use crate::ids;
use crate::index::Index;
use crate::typetable;
pub struct Outcome {
pub roots: Vec<String>,
pub ids: HashMap<String, String>,
pub unresolved: Vec<String>,
pub assets: usize,
}
pub fn import_slots(
dest: &mut Vec<u8>,
dest_index: &Index,
parent_off: usize,
src: &[u8],
src_slots: &[(usize, usize)],
) -> Result<Outcome> {
check_disjoint(src_slots)?;
let mut defined: Vec<&str> = Vec::new();
let mut queue: Vec<&str> = Vec::new();
for &(off, _) in src_slots {
ids::visit_defined(src, off, &mut |id| defined.push(id))?;
for el in bson::elements(src, off)? {
if el.key == "ParentReference" {
continue;
}
if el.ty == STRING && !ids::is_id_key(el.key) {
queue.push(bson::decode_string(el.value)?);
} else if el.ty == DOCUMENT || el.ty == ARRAY {
ids::visit_strings(src, el.value_at, &mut |s| queue.push(s))?;
}
}
}
let asset_offs = asset_offsets(src)?;
let mut asset_by_id: HashMap<&str, usize> = HashMap::new();
for (i, &off) in asset_offs.iter().enumerate() {
ids::visit_defined(src, off, &mut |id| {
asset_by_id.entry(id).or_insert(i);
})?;
}
let mut included = vec![false; asset_offs.len()];
let mut seen: HashSet<&str> = HashSet::new();
while let Some(s) = queue.pop() {
if !seen.insert(s) {
continue;
}
if let Some(&ai) = asset_by_id.get(s) {
if !included[ai] {
included[ai] = true;
ids::visit_defined(src, asset_offs[ai], &mut |id| defined.push(id))?;
ids::visit_strings(src, asset_offs[ai], &mut |s| queue.push(s))?;
}
}
}
let mut id_map: HashMap<String, String> = HashMap::new();
let mut fresh: HashSet<String> = HashSet::new();
for old in &defined {
if !id_map.contains_key(*old) {
let id = loop {
let id = ids::new_guid()?;
if !seen.contains(id.as_str()) && fresh.insert(id.clone()) {
break id;
}
};
id_map.insert((*old).to_string(), id);
}
}
let mut clash = false;
ids::visit_defined(dest, 0, &mut |id| clash |= fresh.contains(id))?;
let mut unresolved: HashSet<&str> = HashSet::new();
ids::visit_defined(src, 0, &mut |id| {
clash |= fresh.contains(id);
if seen.contains(id) && !id_map.contains_key(id) {
unresolved.insert(id);
}
})?;
if clash {
return Err(Error::Invalid("a generated id is already in use".into()));
}
let mut unresolved: Vec<String> = unresolved.into_iter().map(str::to_string).collect();
unresolved.sort();
let parent_id = datatree::read_string_field(dest, parent_off, "ID")?
.ok_or_else(|| Error::Invalid("parent slot has no ID".into()))?;
let src_types = datatree::read_types(src)?;
let mut rw = Rewriter {
src,
ids: &id_map,
src_types: &src_types,
dest_types: datatree::read_types(dest)?,
added: Vec::new(),
used_names: Vec::new(),
};
let dest_type_count = rw.dest_types.len();
let mut roots = Vec::with_capacity(src_slots.len());
let mut slot_bytes = Vec::with_capacity(src_slots.len());
for &(off, _) in src_slots {
let old = datatree::read_string_field(src, off, "ID")?
.ok_or_else(|| Error::Invalid("imported slot has no ID".into()))?;
roots.push(id_map[&old].clone());
let bytes = rw.slot(off, Some(&parent_id))?;
bson::validate(&bytes)?;
slot_bytes.push(bytes);
}
let mut asset_bytes = Vec::new();
for (i, &off) in asset_offs.iter().enumerate() {
if included[i] {
asset_bytes.push(rw.component(off)?);
}
}
let version_extra = type_versions_to_add(dest, src, &rw.used_names)?;
let mut ops: Vec<(usize, Vec<u8>, Vec<usize>)> = Vec::new();
let mut root_tail = Vec::new();
let parent = dest_index
.slot_by_offset(parent_off)
.ok_or(Error::NotFound)?;
let arr = parent
.children_array
.ok_or_else(|| Error::Invalid("parent slot has no Children array".into()))?;
let mut lengths = vec![arr];
lengths.extend_from_slice(&parent.container_lengths);
ops.push((
array_end(dest, arr)?,
numbered(dest, arr, DOCUMENT, &slot_bytes)?,
lengths,
));
if !rw.added.is_empty() {
let names: Vec<Vec<u8>> = rw.added.iter().map(|n| bson::string_value(n)).collect();
match datatree::field(dest, 0, "Types")? {
Some(t) if t.ty == ARRAY => ops.push((
array_end(dest, t.value_at)?,
numbered(dest, t.value_at, STRING, &names)?,
vec![t.value_at, 0],
)),
Some(_) => return Err(Error::Invalid("Types is not an array".into())),
None => {
debug_assert_eq!(dest_type_count, 0);
let refs: Vec<&str> = rw.added.iter().map(String::as_str).collect();
bson::push_element(
&mut root_tail,
ARRAY,
"Types",
&bson::array_of_strings(&refs),
);
}
}
}
if !version_extra.is_empty() {
match datatree::field(dest, 0, "TypeVersions")? {
Some(tv) if tv.ty == DOCUMENT => ops.push((
array_end(dest, tv.value_at)?,
version_extra,
vec![tv.value_at, 0],
)),
Some(_) => return Err(Error::Invalid("TypeVersions is not a document".into())),
None => bson::push_element(
&mut root_tail,
DOCUMENT,
"TypeVersions",
&bson::finish_doc(&version_extra)?,
),
}
}
if !asset_bytes.is_empty() {
match datatree::asset_array(dest)? {
Some(a) if a.ty == ARRAY => ops.push((
array_end(dest, a.value_at)?,
numbered(dest, a.value_at, DOCUMENT, &asset_bytes)?,
vec![a.value_at, 0],
)),
Some(_) => return Err(Error::Invalid("Assets is not an array".into())),
None => {
let mut body = Vec::new();
for (i, a) in asset_bytes.iter().enumerate() {
bson::push_element(&mut body, DOCUMENT, &i.to_string(), a);
}
bson::push_element(&mut root_tail, ARRAY, "Assets", &bson::finish_doc(&body)?);
}
}
}
if !root_tail.is_empty() {
ops.push((bson::doc_end(dest, 0)? - 1, root_tail, vec![0]));
}
ops.sort_by_key(|op| std::cmp::Reverse(op.0));
for (at, bytes, lengths) in ops {
bson::splice(dest, at, at, &bytes, &lengths)?;
}
Ok(Outcome {
roots,
ids: id_map,
unresolved,
assets: asset_bytes.len(),
})
}
fn check_disjoint(spans: &[(usize, usize)]) -> Result<()> {
for (i, a) in spans.iter().enumerate() {
for b in spans.iter().skip(i + 1) {
if a.0 < b.1 && b.0 < a.1 {
return Err(Error::Invalid(
"imported slots overlap; pass each subtree once".into(),
));
}
}
}
Ok(())
}
fn asset_offsets(buf: &[u8]) -> Result<Vec<usize>> {
let Some(assets) = datatree::asset_array(buf)? else {
return Ok(Vec::new());
};
if assets.ty != ARRAY {
return Err(Error::Invalid("Assets is not an array".into()));
}
let mut out = Vec::new();
for el in bson::elements(buf, assets.value_at)? {
if el.ty != DOCUMENT {
return Err(Error::Invalid("Assets entry is not a document".into()));
}
out.push(el.value_at);
}
Ok(out)
}
fn type_versions_to_add(dest: &[u8], src: &[u8], names: &[String]) -> Result<Vec<u8>> {
let Some(src_tv) = datatree::field(src, 0, "TypeVersions")? else {
return Ok(Vec::new());
};
if src_tv.ty != DOCUMENT {
return Err(Error::Invalid("TypeVersions is not a document".into()));
}
let have: HashSet<String> = match datatree::field(dest, 0, "TypeVersions")? {
Some(tv) if tv.ty == DOCUMENT => bson::elements(dest, tv.value_at)?
.into_iter()
.map(|e| e.key.to_string())
.collect(),
Some(_) => return Err(Error::Invalid("TypeVersions is not a document".into())),
None => HashSet::new(),
};
let src_els = bson::elements(src, src_tv.value_at)?;
let mut out = Vec::new();
for name in names {
if have.contains(name) {
continue;
}
if let Some(el) = src_els.iter().find(|e| e.key == name) {
out.extend_from_slice(el.raw);
}
}
Ok(out)
}
fn array_end(buf: &[u8], off: usize) -> Result<usize> {
Ok(bson::doc_end(buf, off)? - 1)
}
fn numbered(buf: &[u8], arr: usize, ty: u8, values: &[Vec<u8>]) -> Result<Vec<u8>> {
let existing = bson::elements(buf, arr)?.len();
let mut out = Vec::new();
for (i, v) in values.iter().enumerate() {
bson::push_element(&mut out, ty, &(existing + i).to_string(), v);
}
Ok(out)
}
struct Rewriter<'a> {
src: &'a [u8],
ids: &'a HashMap<String, String>,
src_types: &'a [String],
dest_types: Vec<String>,
added: Vec<String>,
used_names: Vec<String>,
}
impl Rewriter<'_> {
fn remap_type(&mut self, index: i64) -> Result<i64> {
let name = typetable::type_name(self.src_types, index)?.to_string();
if !self.used_names.contains(&name) {
self.used_names.push(name.clone());
}
if let Some(pos) = self.dest_types.iter().position(|t| *t == name) {
return Ok(pos as i64);
}
self.dest_types.push(name.clone());
self.added.push(name);
Ok(self.dest_types.len() as i64 - 1)
}
fn slot(&mut self, off: usize, new_parent: Option<&str>) -> Result<Vec<u8>> {
let mut body = Vec::new();
let mut saw_parent = false;
for el in bson::elements(self.src, off)? {
match (el.key, el.ty) {
("ParentReference", _) if new_parent.is_some() => {
saw_parent = true;
let p = new_parent.unwrap_or_default();
bson::push_element(&mut body, STRING, el.key, &bson::string_value(p));
}
("Children", ARRAY) => {
let mut arr = Vec::new();
for child in bson::elements(self.src, el.value_at)? {
if child.ty != DOCUMENT {
return Err(Error::Invalid(
"Children entry is not a slot document".into(),
));
}
let bytes = self.slot(child.value_at, None)?;
bson::push_element(&mut arr, DOCUMENT, child.key, &bytes);
}
bson::push_element(&mut body, ARRAY, el.key, &bson::finish_doc(&arr)?);
}
("Components", DOCUMENT) => {
let mut ptr = Vec::new();
for part in bson::elements(self.src, el.value_at)? {
if part.key == "Data" && part.ty == ARRAY {
let mut arr = Vec::new();
for comp in bson::elements(self.src, part.value_at)? {
if comp.ty != DOCUMENT {
return Err(Error::Invalid(
"component is not a document".into(),
));
}
let bytes = self.component(comp.value_at)?;
bson::push_element(&mut arr, DOCUMENT, comp.key, &bytes);
}
bson::push_element(&mut ptr, ARRAY, part.key, &bson::finish_doc(&arr)?);
} else {
self.element(&part, None, &mut ptr)?;
}
}
bson::push_element(&mut body, DOCUMENT, el.key, &bson::finish_doc(&ptr)?);
}
_ => self.element(&el, None, &mut body)?,
}
}
if let (Some(p), false) = (new_parent, saw_parent) {
bson::push_element(&mut body, STRING, "ParentReference", &bson::string_value(p));
}
bson::finish_doc(&body)
}
fn component(&mut self, off: usize) -> Result<Vec<u8>> {
let els = bson::elements(self.src, off)?;
let type_el = els
.iter()
.find(|e| e.key == "Type")
.ok_or_else(|| Error::Invalid("component has no Type".into()))?;
if !typetable::is_int(type_el.ty) {
return Err(Error::Invalid("component Type is not an integer".into()));
}
let old = bson::decode_int(type_el.value, type_el.ty)?;
let name = typetable::type_name(self.src_types, old)?.to_string();
let mut body = Vec::new();
for el in &els {
if el.key == "Type" {
let new = self.remap_type(old)?;
bson::push_element(&mut body, el.ty, el.key, &typetable::int_bytes(el.ty, new)?);
} else {
self.element(el, Some(&name), &mut body)?;
}
}
bson::finish_doc(&body)
}
fn container(&mut self, off: usize, component: Option<&str>) -> Result<Vec<u8>> {
let mut body = Vec::new();
for el in bson::elements(self.src, off)? {
self.element(&el, component, &mut body)?;
}
bson::finish_doc(&body)
}
fn element(
&mut self,
el: &Element<'_>,
component: Option<&str>,
out: &mut Vec<u8>,
) -> Result<()> {
match el.ty {
STRING => {
let s = bson::decode_string(el.value)?;
match self.ids.get(s) {
Some(mapped) => {
bson::push_element(out, STRING, el.key, &bson::string_value(mapped))
}
None => out.extend_from_slice(el.raw),
}
}
DOCUMENT => {
let bytes = match component {
Some(c) if typetable::is_type_field(c, el.key) => {
self.type_field(el.value_at, c)?
}
_ => self.container(el.value_at, component)?,
};
bson::push_element(out, DOCUMENT, el.key, &bytes);
}
ARRAY => {
let bytes = self.container(el.value_at, component)?;
bson::push_element(out, ARRAY, el.key, &bytes);
}
_ => out.extend_from_slice(el.raw),
}
Ok(())
}
fn type_field(&mut self, off: usize, component: &str) -> Result<Vec<u8>> {
let els = bson::elements(self.src, off)?;
let is_ref = els.iter().any(|e| e.key == "ID" && e.ty == STRING);
let mut body = Vec::new();
for el in &els {
if is_ref && el.key == "Data" && typetable::is_int(el.ty) {
let old = bson::decode_int(el.value, el.ty)?;
if typetable::type_name(self.src_types, old).is_ok() {
let new = self.remap_type(old)?;
bson::push_element(
&mut body,
el.ty,
el.key,
&typetable::int_bytes(el.ty, new)?,
);
continue;
}
}
self.element(el, Some(component), &mut body)?;
}
bson::finish_doc(&body)
}
}