use std::collections::{HashMap, HashSet};
use std::fmt::Write as _;
use crate::bson::{self, Element, ARRAY, BINARY, BOOL, DOCUMENT, DOUBLE, NULL, STRING};
use crate::datatree;
use crate::error::Result;
use crate::ids;
use crate::typetable;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Difference {
pub path: String,
pub item: String,
pub left: Option<String>,
pub right: Option<String>,
}
pub fn compare(a: &[u8], b: &[u8]) -> Result<Vec<Difference>> {
let left = describe(a)?;
let right = describe(b)?;
let right_map: HashMap<(&str, &str), &str> = right
.iter()
.map(|(p, i, v)| ((p.as_str(), i.as_str()), v.as_str()))
.collect();
let left_keys: HashSet<(&str, &str)> = left
.iter()
.map(|(p, i, _)| (p.as_str(), i.as_str()))
.collect();
let mut out = Vec::new();
for (p, i, v) in &left {
match right_map.get(&(p.as_str(), i.as_str())) {
Some(r) if *r == v => {}
other => out.push(Difference {
path: p.clone(),
item: i.clone(),
left: Some(v.clone()),
right: other.map(|r| r.to_string()),
}),
}
}
for (p, i, v) in &right {
if !left_keys.contains(&(p.as_str(), i.as_str())) {
out.push(Difference {
path: p.clone(),
item: i.clone(),
left: None,
right: Some(v.clone()),
});
}
}
Ok(out)
}
type Entry = (String, String, String);
pub fn describe(buf: &[u8]) -> Result<Vec<Entry>> {
let types = datatree::read_types(buf)?;
let root = datatree::root_slot_offset(buf)?;
let mut slots: Vec<(usize, String)> = Vec::new();
collect_slots(
buf,
root,
datatree::read_string_field(buf, root, "Name")?.unwrap_or_default(),
&mut slots,
)?;
let mut targets: HashMap<String, String> = HashMap::new();
for (off, path) in &slots {
for el in bson::elements(buf, *off)? {
match (el.key, el.ty) {
("Children", _) | ("Components", _) => {}
(k, STRING) if ids::is_id_key(k) => {
let s = bson::decode_string(el.value)?.to_string();
let at = if k == "ID" {
format!("slot {path}")
} else {
format!("slot {path} {k}")
};
targets.insert(s, at);
}
(k, DOCUMENT | ARRAY) => {
name_ids(buf, el.value_at, &format!("slot {path}"), k, &mut targets)?;
}
_ => {}
}
}
for (i, c) in datatree::components_of_slot(buf, *off, &types)?
.iter()
.enumerate()
{
if let Some(data) = datatree::field(buf, c.offset, "Data")? {
if data.ty == DOCUMENT {
let ctx = format!("component {path} #{i} {}", c.type_name);
name_ids(buf, data.value_at, &ctx, "", &mut targets)?;
}
}
}
}
let mut raw_assets: Vec<(usize, String, Option<String>, u64)> = Vec::new();
if let Some(arr) = datatree::asset_array(buf)? {
if arr.ty == ARRAY {
for el in bson::elements(buf, arr.value_at)?.iter() {
if el.ty != DOCUMENT {
continue;
}
let type_name = match datatree::field(buf, el.value_at, "Type")? {
Some(t) if typetable::is_int(t.ty) => {
let ix = bson::decode_int(t.value, t.ty)?;
typetable::type_name(&types, ix).unwrap_or("?").to_string()
}
_ => "?".to_string(),
};
let url = first_url(buf, el.value_at)?;
let hash = match datatree::field(buf, el.value_at, "Data")? {
Some(d) if d.ty == DOCUMENT => content_hash(buf, d.value_at)?,
_ => 0,
};
raw_assets.push((el.value_at, type_name, url, hash));
}
}
}
let mut assets: Vec<(usize, String)> = Vec::new();
for (off, t, url, hash) in &raw_assets {
let ctx = match url {
Some(u) => format!("asset {t} {u} {hash:016x}"),
None => format!("asset {t} {hash:016x}"),
};
if let Some(data) = datatree::field(buf, *off, "Data")? {
if data.ty == DOCUMENT {
name_ids(buf, data.value_at, &ctx, "", &mut targets)?;
}
}
assets.push((*off, ctx));
}
let mut d = Describer {
buf,
types: &types,
targets: &targets,
out: Vec::new(),
referenced: HashSet::new(),
};
if let Some(el) = datatree::field(buf, 0, "VersionNumber")? {
let v = d.scalar(&el, None)?;
d.push("document", "VersionNumber", v);
}
for key in ["FeatureFlags", "TypeVersions"] {
if let Some(el) = datatree::field(buf, 0, key)? {
if el.ty == DOCUMENT {
for f in bson::elements(buf, el.value_at)? {
let v = d.scalar(&f, None)?;
d.push("document", &format!("{key}.{}", f.key), v);
}
}
}
}
for (off, path) in &slots {
d.push(path, "slot", String::new());
for el in bson::elements(buf, *off)? {
match el.key {
"Children" | "Components" => {}
k if ids::is_id_key(k) && el.ty == STRING => {}
_ => d.value(path, el.key, &el, None)?,
}
}
for (i, c) in datatree::components_of_slot(buf, *off, &types)?
.iter()
.enumerate()
{
d.push(path, &format!("#{i} type"), c.type_name.clone());
if let Some(data) = datatree::field(buf, c.offset, "Data")? {
if data.ty == DOCUMENT {
for f in bson::elements(buf, data.value_at)? {
if ids::is_id_key(f.key) && f.ty == STRING {
continue;
}
d.value(path, &format!("#{i} {}", f.key), &f, Some(&c.type_name))?;
}
}
}
}
}
let mut asset_entries = Vec::new();
let mut described: HashSet<&str> = HashSet::new();
for (off, ctx) in &assets {
if described.contains(ctx.as_str()) {
continue;
}
if !d.referenced.iter().any(|t| {
t == ctx
|| t.strip_prefix(ctx.as_str())
.is_some_and(|r| r.starts_with(' '))
}) {
continue;
}
let mut sub = Describer {
buf,
types: &types,
targets: &targets,
out: Vec::new(),
referenced: HashSet::new(),
};
if let Some(data) = datatree::field(buf, *off, "Data")? {
if data.ty == DOCUMENT {
for f in bson::elements(buf, data.value_at)? {
if ids::is_id_key(f.key) && f.ty == STRING {
continue;
}
sub.value(ctx, f.key, &f, None)?;
}
}
}
described.insert(ctx.as_str());
asset_entries.extend(sub.out);
}
d.out.extend(asset_entries);
Ok(d.out)
}
fn collect_slots(
buf: &[u8],
off: usize,
path: String,
out: &mut Vec<(usize, String)>,
) -> Result<()> {
let children = datatree::child_slot_offsets(buf, off)?;
out.push((off, path.clone()));
for (i, c) in children.into_iter().enumerate() {
let name = datatree::read_string_field(buf, c, "Name")?.unwrap_or_default();
collect_slots(buf, c, format!("{path}/{i}:{name}"), out)?;
}
Ok(())
}
fn name_ids(
buf: &[u8],
off: usize,
ctx: &str,
rel: &str,
targets: &mut HashMap<String, String>,
) -> Result<()> {
for el in bson::elements(buf, off)? {
let here = if rel.is_empty() {
el.key.to_string()
} else {
format!("{rel}.{}", el.key)
};
match el.ty {
STRING if ids::is_id_key(el.key) => {
let s = bson::decode_string(el.value)?.to_string();
let at = match (el.key, rel.is_empty()) {
("ID", true) => ctx.to_string(),
("ID", false) => format!("{ctx} {rel}"),
_ => format!("{ctx} {here}"),
};
targets.insert(s, at);
}
DOCUMENT | ARRAY => name_ids(buf, el.value_at, ctx, &here, targets)?,
_ => {}
}
}
Ok(())
}
fn content_hash(buf: &[u8], off: usize) -> Result<u64> {
fn eat(bytes: &[u8], h: &mut u64) {
for b in bytes {
*h ^= u64::from(*b);
*h = h.wrapping_mul(0x0100_0000_01b3);
}
}
fn walk(buf: &[u8], off: usize, h: &mut u64) -> Result<()> {
for el in bson::elements(buf, off)? {
let v = match el.ty {
STRING => {
let s = bson::decode_string(el.value)?;
if ids::is_id_key(el.key) || looks_like_guid(s) {
continue;
}
format!("{s:?}")
}
DOCUMENT | ARRAY => {
eat(el.key.as_bytes(), h);
eat(b"{", h);
walk(buf, el.value_at, h)?;
eat(b"}", h);
continue;
}
_ => number_or_raw(&el)?,
};
eat(el.key.as_bytes(), h);
eat(b"=", h);
eat(v.as_bytes(), h);
eat(b";", h);
}
Ok(())
}
let mut h = 0xcbf2_9ce4_8422_2325u64;
walk(buf, off, &mut h)?;
Ok(h)
}
fn number_or_raw(el: &Element<'_>) -> Result<String> {
Ok(match el.ty {
DOUBLE => {
let f = bson::decode_f64(el.value)?;
if f.fract() == 0.0
&& f.abs() < 9_007_199_254_740_992.0
&& !(f == 0.0 && f.is_sign_negative())
{
format!("{}", f as i64)
} else {
format!("{f:?}")
}
}
BOOL => bson::decode_bool(el.value)?.to_string(),
NULL => "null".to_string(),
t if typetable::is_int(t) => bson::decode_int(el.value, t)?.to_string(),
BINARY => {
let mut h = 0xcbf2_9ce4_8422_2325u64;
for b in el.value {
h ^= u64::from(*b);
h = h.wrapping_mul(0x0100_0000_01b3);
}
format!("binary {} bytes {h:016x}", el.value.len())
}
t => {
let mut s = format!("bson {t:#04x} ");
for b in el.value {
let _ = write!(s, "{b:02x}");
}
s
}
})
}
fn first_url(buf: &[u8], off: usize) -> Result<Option<String>> {
for el in bson::elements(buf, off)? {
match el.ty {
STRING => {
let s = bson::decode_string(el.value)?;
if s.contains("://") {
return Ok(Some(s.to_string()));
}
}
DOCUMENT | ARRAY => {
if let Some(u) = first_url(buf, el.value_at)? {
return Ok(Some(u));
}
}
_ => {}
}
}
Ok(None)
}
struct Describer<'a> {
buf: &'a [u8],
types: &'a [String],
targets: &'a HashMap<String, String>,
out: Vec<Entry>,
referenced: HashSet<String>,
}
impl Describer<'_> {
fn push(&mut self, path: &str, item: &str, value: String) {
self.out.push((path.to_string(), item.to_string(), value));
}
fn value(
&mut self,
path: &str,
item: &str,
el: &Element<'_>,
component: Option<&str>,
) -> Result<()> {
match el.ty {
DOCUMENT | ARRAY => {
let els = bson::elements(self.buf, el.value_at)?;
let wrapper = el.ty == DOCUMENT
&& els.iter().any(|e| e.key == "ID" && e.ty == STRING)
&& els.iter().any(|e| e.key == "Data");
if wrapper {
let data = els.iter().find(|e| e.key == "Data").copied();
let field = item.rsplit(' ').next().unwrap_or(item);
let field = field.rsplit('.').next().unwrap_or(field);
let type_field = component
.map(|c| typetable::is_type_field(c, field))
.unwrap_or(false);
if let Some(data) = data {
if type_field && typetable::is_int(data.ty) {
let ix = bson::decode_int(data.value, data.ty)?;
let name = typetable::type_name(self.types, ix).unwrap_or("?");
self.push(path, item, format!("type {name}"));
} else {
self.value(path, item, &data, component)?;
}
}
for other in els.iter().filter(|e| e.key != "ID" && e.key != "Data") {
self.value(path, &format!("{item}.{}", other.key), other, component)?;
}
return Ok(());
}
if els.is_empty() {
self.push(
path,
item,
if el.ty == ARRAY { "[]" } else { "{}" }.to_string(),
);
}
for e in &els {
if ids::is_id_key(e.key) && e.ty == STRING {
continue;
}
self.value(path, &format!("{item}.{}", e.key), e, component)?;
}
Ok(())
}
_ => {
let v = self.scalar(el, component)?;
self.push(path, item, v);
Ok(())
}
}
}
fn scalar(&mut self, el: &Element<'_>, _component: Option<&str>) -> Result<String> {
Ok(match el.ty {
STRING => {
let s = bson::decode_string(el.value)?;
match self.targets.get(s) {
Some(t) => {
self.referenced.insert(t.clone());
format!("→ {t}")
}
None if looks_like_guid(s) => "→ (id not in this file)".to_string(),
None => format!("{s:?}"),
}
}
_ => number_or_raw(el)?,
})
}
}
fn looks_like_guid(s: &str) -> bool {
let b = s.as_bytes();
b.len() == 36
&& b.iter().enumerate().all(|(i, c)| match i {
8 | 13 | 18 | 23 => *c == b'-',
_ => c.is_ascii_hexdigit(),
})
}