crates/mimir-room/src/diff.rs
//! Time travel: what changed between two rooms (two scopes of one log —
//! seq N vs N-1, two repos' heads, universe on vs off). Nodes by moniker;
//! edges per kind as algebra in the UNION node space: both snapshots'
//! ordinals are lexicographic, so the map into the union is monotone and
//! the sorted CSR stays sorted; `added = B⟨¬A⟩`, `removed = A⟨¬B⟩`.
use std::collections::BTreeMap;
use anyhow::Result;
use mimir_graph::arrow::from_edge_chunks;
use mimir_graph::ops;
use mimir_schema::{EdgeKind, Provenance};
use crate::evidence::{Answer, Emptiness, Evidence};
use crate::snapshot::kind_bit;
use crate::Room;
/// Edges of one kind that appeared / disappeared, as (from, to) monikers.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct EdgeDiff {
pub added: Vec<(String, String)>,
pub removed: Vec<(String, String)>,
}
/// `older → newer`.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Diff {
pub added_nodes: Vec<String>,
pub removed_nodes: Vec<String>,
/// Nodes in both whose semantic payload changed (signature, type, kind …
/// — the node's payload hash; positions are not payload).
pub changed: Vec<String>,
/// Only kinds with a change.
pub edges: BTreeMap<EdgeKind, EdgeDiff>,
/// Nodes in both whose DERIVED provenance moved (the binary_drift fact:
/// same node, the binary twin appeared or went): (moniker, older, newer).
pub provenance_changed: Vec<(String, Option<Provenance>, Option<Provenance>)>,
}
impl Emptiness for Diff {
fn is_empty_answer(&self) -> bool {
self.added_nodes.is_empty() && self.removed_nodes.is_empty() && self.changed.is_empty() && self.edges.is_empty() && self.provenance_changed.is_empty()
}
}
impl Room {
/// What changed from `self` (older) to `newer`.
pub fn diff(&self, newer: &Room) -> Result<Answer<Diff>> {
let (a, b) = (self, newer);
let kinds: Vec<EdgeKind> = {
let mut k: Vec<EdgeKind> = a.snap.edge_counts.keys().chain(b.snap.edge_counts.keys()).copied().collect();
k.sort();
k.dedup();
k
};
let mut ev = Evidence {
query: "diff(older → newer)".into(),
scope: format!("{} → {}", a.snap.scope, b.snap.scope),
..Default::default()
};
for (side, r) in [("older", a), ("newer", b)] {
let e = r.evidence(String::new(), false, &[]);
ev.inputs.extend(e.inputs);
for m in e.missing {
ev.miss(format!("{side}: {}", m.input), m.repo.as_deref(), m.why);
}
}
ev.note("inputs: the older room's tables first, then the newer room's");
if a.snap.scope.universe != b.snap.scope.universe {
ev.note("the two rooms differ in universe on/off: the diff mostly measures the ring");
}
if a.snap.scope.repos.keys().ne(b.snap.scope.repos.keys()) {
ev.note("the two rooms hold different repos");
}
// ---- union node space (merge of two sorted moniker lists)
let (na, nb) = (a.len() as u64, b.len() as u64);
let mut map_a = Vec::with_capacity(na as usize);
let mut map_b = Vec::with_capacity(nb as usize);
// union ordinal → (side 0 = a, 1 = b, ordinal there)
let mut back: Vec<(u8, u64)> = Vec::with_capacity((na.max(nb)) as usize);
let (mut added_nodes, mut removed_nodes) = (Vec::new(), Vec::new());
let mut provenance_changed = Vec::new();
let mut changed = Vec::new();
let (mut i, mut j) = (0u64, 0u64);
while i < na || j < nb {
let u = back.len() as u64;
let ord = match (i < na, j < nb) {
(true, true) => a.moniker(i).cmp(b.moniker(j)),
(true, false) => std::cmp::Ordering::Less,
_ => std::cmp::Ordering::Greater,
};
match ord {
std::cmp::Ordering::Less => {
removed_nodes.push(a.moniker(i).to_string());
map_a.push(u);
back.push((0, i));
i += 1;
}
std::cmp::Ordering::Greater => {
added_nodes.push(b.moniker(j).to_string());
map_b.push(u);
back.push((1, j));
j += 1;
}
std::cmp::Ordering::Equal => {
let (pa, pb) = (a.snap.nodes.provenance(i as usize), b.snap.nodes.provenance(j as usize));
if a.snap.nodes.phash[i as usize] != b.snap.nodes.phash[j as usize] {
changed.push(a.moniker(i).to_string());
}
if pa != pb {
provenance_changed.push((a.moniker(i).to_string(), pa, pb));
}
map_a.push(u);
map_b.push(u);
back.push((0, i));
i += 1;
j += 1;
}
}
}
let nu = back.len() as u64;
let name = |u: u64| -> String {
let (side, o) = back[u as usize];
if side == 0 { a.moniker(o).to_string() } else { b.moniker(o).to_string() }
};
// ---- per kind: A and B in the union space, diff as algebra
let in_union = |r: &Room, map: &[u64], k: EdgeKind| -> Result<mimir_graph::Matrix<bool>> {
let pairs = {
let mut g = r.graphs();
match g.get(kind_bit(k), false)? {
Some(m) => m.edges()?,
None => Vec::new(),
}
};
let from: Vec<u64> = pairs.iter().map(|(f, _)| map[*f as usize]).collect();
let to: Vec<u64> = pairs.iter().map(|(_, t)| map[*t as usize]).collect();
Ok(from_edge_chunks(&[(&from[..], &to[..])], nu)?.0)
};
let mut edges = BTreeMap::new();
for k in kinds {
let (ax, bx) = (in_union(a, &map_a, k)?, in_union(b, &map_b, k)?);
let (plus, minus) = ops::diff(&ax, &bx)?;
let d = EdgeDiff {
added: plus.edges()?.into_iter().map(|(f, t)| (name(f), name(t))).collect(),
removed: minus.edges()?.into_iter().map(|(f, t)| (name(f), name(t))).collect(),
};
ev.kinds.push((k, b.snap.edge_counts.get(&k).copied().unwrap_or(0)));
if !d.added.is_empty() || !d.removed.is_empty() {
edges.insert(k, d);
}
}
Ok(Answer::new(Diff { added_nodes, removed_nodes, changed, edges, provenance_changed }, ev))
}
}