crates/mimir-room/tests/room/queries.rs
use mimir_graph::arrow::ImportPath;
use mimir_room::{JIKES_KINDS, MaskSpec, Room, Scope};
use mimir_schema::{EdgeKind, Origin, Provenance};
use super::common::*;
fn names(room: &Room, ords: &[u64]) -> Vec<String> {
room.monikers(ords).into_iter().map(str::to_string).collect()
}
fn named<T: Copy>(room: &Room, v: &[(u64, T)]) -> Vec<(String, T)> {
v.iter().map(|(o, x)| (room.moniker(*o).to_string(), *x)).collect()
}
fn s(v: &[&str]) -> Vec<String> {
v.iter().map(|x| x.to_string()).collect()
}
async fn room(log: &mimir_ingest::EventLog, scope: Scope) -> Room {
Room::at(log, &scope).await.unwrap()
}
/// room@seq + plain@1
fn both(seq: i64) -> Scope {
Scope { repos: [(ROOM.to_string(), Some(seq)), (PLAIN.to_string(), None)].into(), universe: false }
}
#[tokio::test(flavor = "current_thread")]
async fn snapshot_holds_exactly_the_folded_graph() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
assert_eq!(r.scope().repos, [(PLAIN.to_string(), 1), (ROOM.to_string(), 3)].into());
let all: Vec<u64> = (0..r.len() as u64).collect();
assert_eq!(
names(&r, &all),
s(&[
"dep", "dep h", "dep2", "extern write", "k", "k I", "k T", "k a", "k b", "k c", "k e", "k m", "k t", "k t<u32>", "k tr", "k u", "k x", "p p1",
"p p2", "rt unwind"
]),
"k d closed at seq 3; dep w / dep2 z only with the universe ring"
);
let st = r.stats();
use EdgeKind::*;
assert_eq!(st.edges, [(Calls, 8), (Contains, 1), (DependsOn, 2), (Implements, 1), (ForType, 1), (UsesType, 1), (InstanceOf, 1)].into());
assert!(st.build.import_paths.values().all(|p| *p == ImportPath::SortedPack), "{:?}", st.build.import_paths);
assert_eq!(st.endpoint_only, 0);
assert_eq!(st.repo_rows[ROOM].source, 15 + 12, "15 open nodes + 12 open edges at seq 3");
assert_eq!(st.repo_rows[PLAIN].binary, 0);
// node attributes: the definition wins over a stub (plain's `k a` stub says Library)
let a = r.node(r.ordinal("k a").unwrap());
assert_eq!((a.kind, a.krate, a.repo, a.origin, a.defined, a.stub_only), (Some("fn"), Some("k"), Some(ROOM), Some(Origin::Local), true, false));
let dh = r.node(r.ordinal("dep h").unwrap());
assert!(dh.defined && !dh.stub_only, "defined in the ring (provenance lookup): {dh:?}");
let u = room(&log, Scope::current().with_universe(true)).await;
assert_eq!(u.len(), 23, "+ dep w, dep2 z, and the linked ring crate rt's crate node");
assert!(u.ordinal("dep w").is_some() && u.ordinal("dep2 z").is_some() && u.ordinal("rt").is_some());
assert_eq!(u.stats().edges[&Calls], 9);
assert_eq!(u.stats().universe_rows, 8, "dep, dep h, dep w, dep h→dep w; dep2, dep2 z; rt, rt unwind");
// ring on and ring off agree on every linked item's provenance (rt: in
// scope because linked, though no DEPENDS_ON names it)
let flips = r.diff(&u).unwrap().value.provenance_changed;
assert!(flips.iter().all(|(_, a, b)| a.is_none() && *b == Some(mimir_schema::Provenance::SourceOnly)), "{flips:?}");
assert_eq!(u.node(u.ordinal("rt unwind").unwrap()).provenance, Some(mimir_schema::Provenance::Both));
}
/// Ring time travel: a scope at seq N holds only the ring crates its local
/// crates depend on AT N (DEPENDS_ON closure), not every crate dumped later.
#[tokio::test(flavor = "current_thread")]
async fn the_ring_of_a_past_seq_holds_only_what_that_seq_depended_on() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let u2 = room(&log, both(2).with_universe(true)).await;
assert!(u2.ordinal("dep2").is_none() && u2.ordinal("dep2 z").is_none(), "dep2 is first depended on at seq 3");
assert!(u2.ordinal("dep w").is_some(), "dep is depended on from seq 1");
let ev = u2.reach(&["k a"], &[EdgeKind::Calls], None, None).unwrap().evidence;
assert!(ev.notes.iter().any(|n| n.contains("ring: 2 of 3 dumped ring crates")), "{ev}");
let u3 = room(&log, both(3).with_universe(true)).await;
assert!(u3.ordinal("dep2 z").is_some());
// a scope with no local DEPENDS_ON (plain) gets no ring at all
let p = room(&log, Scope::repo(PLAIN, None).with_universe(true)).await;
assert!(p.ordinal("dep w").is_none() && p.stats().universe_rows == 0);
}
#[tokio::test(flavor = "current_thread")]
async fn reach_and_dependents_are_exact() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
use EdgeKind::*;
let w = r.reach(&["k a"], &[Calls], None, None).unwrap();
assert_eq!(names(&r, &w.value.reached), s(&["dep h", "k b", "k c"]), "c→x closed at seq 2");
assert!(w.evidence.is_complete(), "{}", w.evidence);
let w1 = r.reach(&["k a"], &[Calls], Some(1), None).unwrap();
assert_eq!(names(&r, &w1.value.reached), s(&["dep h", "k b"]));
let d = r.dependents(&["k T"], None).unwrap();
assert_eq!(
names(&r, &d.value.reached),
s(&["k I", "k a", "k b", "k e", "k m", "k u", "p p1", "p p2"]),
"I is impl for T → DOWN to its method m → m's caller u"
);
assert_eq!(d.evidence.kinds, vec![(Calls, 8), (UsesType, 1), (Implements, 1), (ForType, 1), (Contains, 1)]);
// the plain backward walk does not step down into impls
let back = r.dependents_by(&["k T"], &JIKES_KINDS, None, None).unwrap();
assert_eq!(names(&r, &back.value.reached), s(&["k I", "k a", "k b", "k e", "p p1", "p p2"]));
// CONTAINS is followed DOWN from impls only: a changed method does not
// reach its impl block or siblings
let m = r.dependents(&["k m"], None).unwrap();
assert_eq!(names(&r, &m.value.reached), s(&["k u"]));
let d = r.dependents(&["k a"], None).unwrap();
assert_eq!(names(&r, &d.value.reached), s(&["k e", "p p1", "p p2"]), "across repos");
let only_room = r.mask(&MaskSpec { repos: vec![ROOM.into()], ..Default::default() }).unwrap().value;
let d = r.dependents(&["k a"], Some(&only_room)).unwrap();
assert_eq!(names(&r, &d.value.reached), s(&["k e"]));
// time travel: at seq 1, T's dependents are d (USES_TYPE) and I (FOR_TYPE)
let r1 = room(&log, both(1)).await;
let d = r1.dependents(&["k T"], None).unwrap();
assert_eq!(names(&r1, &d.value.reached), s(&["k I", "k d", "k m", "k u"]));
}
/// The batched walks: one answer per seed, each the very answer (walk and
/// evidence) the single-seed call gives — every node of the room as a seed,
/// forward and backward, bounded and not, inside a mask and not, at batch
/// sizes that split the seeds unevenly.
#[tokio::test(flavor = "current_thread")]
async fn each_walk_is_the_single_seed_walk() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
use EdgeKind::*;
let mut seeds: Vec<u64> = (0..r.len() as u64).collect();
seeds.push(r.len() as u64 + 3); // an ordinal past the room: MISSING, like the single call
seeds.push(0);
let only_room = r.mask(&MaskSpec { repos: vec![ROOM.into()], ..Default::default() }).unwrap().value;
for batch in ["1", "3", "64"] {
// SAFETY: the room tests run serially (`serial()`), nothing reads the env concurrently
unsafe { std::env::set_var("NORNIR_BFS_BATCH", batch) };
for kinds in [&[Calls][..], &JIKES_KINDS[..], &[TouchesTable][..]] {
for hops in [None, Some(1)] {
for within in [None, Some(&only_room)] {
let fwd = r.reach_each(&seeds, kinds, hops, within).unwrap();
let back = r.dependents_by_each(&seeds, kinds, hops, within).unwrap();
assert_eq!((fwd.len(), back.len()), (seeds.len(), seeds.len()));
for (i, s) in seeds.iter().enumerate() {
let one = r.reach(&[*s][..], kinds, hops, within).unwrap();
assert_eq!(format!("{:?}", fwd[i]), format!("{one:?}"), "reach from {s} ({kinds:?}, {hops:?}, batch {batch})");
let one = r.dependents_by(&[*s][..], kinds, hops, within).unwrap();
assert_eq!(format!("{:?}", back[i]), format!("{one:?}"), "dependents of {s} ({kinds:?}, {hops:?}, batch {batch})");
}
}
}
}
}
unsafe { std::env::remove_var("NORNIR_BFS_BATCH") };
}
/// The batched Jikes walks: one answer per seed set, each the very answer
/// `dependents` gives that set — single nodes, neighbouring pairs, the whole
/// room, an empty set and unknown monikers, inside a mask and not.
#[tokio::test(flavor = "current_thread")]
async fn each_dependents_walk_is_the_set_walk() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
let n = r.len() as u64;
let mut sets: Vec<Vec<u64>> = (0..n).map(|o| vec![o]).collect();
sets.extend((0..n.saturating_sub(1)).map(|o| vec![o, o + 1]));
sets.push((0..n).collect());
sets.push(Vec::new());
let unknown: Vec<&str> = vec!["k T", "no such node"];
let only_room = r.mask(&MaskSpec { repos: vec![ROOM.into()], ..Default::default() }).unwrap().value;
for batch in ["1", "3", "64"] {
// SAFETY: the room tests run serially (`serial()`), nothing reads the env concurrently
unsafe { std::env::set_var("NORNIR_BFS_BATCH", batch) };
for within in [None, Some(&only_room)] {
let mut seeds: Vec<mimir_room::Seeds<'_>> = sets.iter().map(|s| mimir_room::Seeds::Ordinals(s)).collect();
seeds.push(mimir_room::Seeds::Monikers(&unknown));
let each = r.dependents_each(&seeds, within).unwrap();
assert_eq!(each.len(), seeds.len());
for (i, s) in seeds.iter().enumerate() {
let one = r.dependents(*s, within).unwrap();
assert_eq!(format!("{:?}", each[i]), format!("{one:?}"), "dependents of {s:?} (batch {batch})");
}
}
}
unsafe { std::env::remove_var("NORNIR_BFS_BATCH") };
}
#[tokio::test(flavor = "current_thread")]
async fn fan_in_fan_out_similarity() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
let fi = r.fan_in(EdgeKind::Calls, None).unwrap();
assert_eq!(
named(&r, &fi.value),
vec![("k a".into(), 2), ("k b".into(), 2), ("dep h".into(), 1), ("k c".into(), 1), ("k m".into(), 1), ("p p2".into(), 1)]
);
let fo = r.fan_out(EdgeKind::Calls, Some(2)).unwrap();
assert_eq!(named(&r, &fo.value), vec![("k a".into(), 2), ("k e".into(), 2)]);
let fns = r.mask(&MaskSpec::kinds(&["fn"])).unwrap().value;
let sim = r.similarity(&fns, EdgeKind::Calls, 1, None).unwrap();
let got: Vec<(String, String, u64)> = sim.value.iter().map(|(i, j, x)| (r.moniker(*i).into(), r.moniker(*j).into(), *x)).collect();
assert_eq!(got, vec![("k a".into(), "k e".into(), 1), ("k e".into(), "p p2".into(), 1)], "a,e share b; e,p2 share a");
}
#[tokio::test(flavor = "current_thread")]
async fn min_hops_to_the_ffi_border() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let ffi = MaskSpec::kinds(&["ffi"]);
let calls = [EdgeKind::Calls];
// ring off, seq 3: nothing calls k x any more and dep w is outside
let r = room(&log, Scope::current()).await;
let h = r.min_hops_to(&ffi, &calls, None).unwrap();
assert!(h.value.is_empty());
assert!(h.evidence.is_complete(), "{}", h.evidence);
assert!(h.evidence.notes.iter().any(|n| n.contains("empty answer with every input present")), "{}", h.evidence);
assert!(h.evidence.notes.iter().any(|n| n.contains("universe ring off")), "{}", h.evidence);
// ring on: dep h → dep w
let u = room(&log, Scope::current().with_universe(true)).await;
let h = u.min_hops_to(&ffi, &calls, None).unwrap();
assert_eq!(named(&u, &h.value), vec![("dep h".into(), 1), ("k a".into(), 2), ("k e".into(), 3), ("p p2".into(), 3), ("p p1".into(), 4)]);
// seq 1, ring on: c → x still there
let u1 = room(&log, both(1).with_universe(true)).await;
let h = u1.min_hops_to(&ffi, &calls, None).unwrap();
assert_eq!(
named(&u1, &h.value),
vec![("dep h".into(), 1), ("k c".into(), 1), ("k a".into(), 2), ("k b".into(), 2), ("p p2".into(), 3), ("p p1".into(), 4)]
);
let none = u.min_hops_to(&MaskSpec::kinds(&["no_such_kind"]), &calls, None).unwrap();
assert!(none.value.is_empty() && !none.evidence.missing_input("targets").is_empty(), "{}", none.evidence);
}
#[tokio::test(flavor = "current_thread")]
async fn instances_and_derived_provenance() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
assert!(log.bin_offsets(ROOM).await.unwrap().contains_key(ARTIFACT));
let r = room(&log, Scope::current()).await;
let i = r.instances_of("k t").unwrap();
assert_eq!(names(&r, &i.value), s(&["k t<u32>"]));
assert!(i.evidence.missing_input("binary stream").iter().all(|m| m.repo.as_deref() == Some(PLAIN)), "{}", i.evidence);
let p = |id: &str| r.node(r.ordinal(id).unwrap()).provenance;
assert_eq!(p("k a"), Some(Provenance::Both));
assert_eq!(p("k b"), Some(Provenance::SourceOnly), "no longer linked at seq 3");
assert_eq!(p("k t"), Some(Provenance::Both), "generic with a linked instance");
assert_eq!(p("k t<u32>"), Some(Provenance::BinaryOnly));
assert_eq!(p("extern write"), Some(Provenance::BinaryOnly));
assert_eq!(p("dep h"), Some(Provenance::Both), "linked universe item, ring off");
assert_eq!(p("p p1"), Some(Provenance::SourceOnly));
// the room's provenance is THE derived one: same as EventLog::provenance, every seq
for seq in 1..=3 {
let view = log.provenance(ROOM, Some(seq)).await.unwrap();
let rr = room(&log, Scope::repo(ROOM, Some(seq))).await;
for (id, want) in &view.by_id {
let o = rr.ordinal(id).unwrap_or_else(|| panic!("{id} missing from the room at seq {seq}"));
assert_eq!(rr.node(o).provenance, Some(*want), "{id} at seq {seq}");
}
let with: usize = (0..rr.len() as u64).filter(|o| rr.node(*o).provenance.is_some()).count();
assert_eq!(with, view.by_id.len(), "seq {seq}");
}
let m = r.mask(&MaskSpec { provenances: vec![Provenance::Both], ..Default::default() }).unwrap();
assert_eq!(names(&r, m.value.ordinals()), s(&["dep h", "k a", "k t", "rt unwind"]));
let gaps = m.evidence.missing_input("binary stream");
assert_eq!(gaps.len(), 1, "{}", m.evidence);
assert_eq!(gaps[0].repo.as_deref(), Some(PLAIN));
let solo = room(&log, Scope::repo(ROOM, None)).await;
let m = solo.mask(&MaskSpec { provenances: vec![Provenance::Both], ..Default::default() }).unwrap();
assert!(m.evidence.is_complete(), "{}", m.evidence);
}
#[tokio::test(flavor = "current_thread")]
async fn masks_by_repo_crate_origin_kind() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
let m = |spec: MaskSpec| names(&r, r.mask(&spec).unwrap().value.ordinals());
assert_eq!(m(MaskSpec { repos: vec![PLAIN.into()], ..Default::default() }), s(&["p p1", "p p2"]));
assert_eq!(m(MaskSpec { crates: vec!["dep".into()], ..Default::default() }), s(&["dep", "dep h"]));
assert_eq!(m(MaskSpec { crates: vec!["dep@1.0.0".into()], ..Default::default() }), s(&["dep", "dep h"]));
assert_eq!(m(MaskSpec { origins: vec![Origin::Library], ..Default::default() }), s(&["dep", "dep h", "dep2", "extern write"]), "rt unwind is Lang");
assert_eq!(m(MaskSpec::kinds(&["ffi", "ffi_import"])), s(&["extern write", "k x"]));
assert_eq!(m(MaskSpec { node_kinds: vec!["fn".into()], repos: vec![ROOM.into()], ..Default::default() }), s(&["k a", "k b", "k c", "k e", "k t", "k u"]));
let nope = r.mask(&MaskSpec { crates: vec!["nope".into()], ..Default::default() }).unwrap();
assert!(nope.value.is_empty() && !nope.evidence.missing_input("crate `nope`").is_empty(), "{}", nope.evidence);
}
#[tokio::test(flavor = "current_thread")]
async fn time_travel_diff_across_three_seqs() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let at = |n: i64| Scope::repo(ROOM, Some(n));
let (r1, r2, r3) = (room(&log, at(1)).await, room(&log, at(2)).await, room(&log, at(3)).await);
use EdgeKind::*;
let pair = |f: &str, t: &str| (f.to_string(), t.to_string());
let d = r1.diff(&r2).unwrap().value;
assert_eq!((d.added_nodes.clone(), d.removed_nodes.clone()), (s(&["k e"]), vec![]));
assert_eq!(d.edges.keys().copied().collect::<Vec<_>>(), vec![Calls]);
assert_eq!(d.edges[&Calls].added, vec![pair("k e", "k a"), pair("k e", "k b")]);
assert_eq!(d.edges[&Calls].removed, vec![pair("k c", "k x")]);
assert!(d.provenance_changed.is_empty() && d.changed.is_empty());
let d = r2.diff(&r3).unwrap().value;
assert_eq!((d.added_nodes.clone(), d.removed_nodes.clone()), (s(&["dep2"]), s(&["k d"])));
assert_eq!(d.changed, s(&["k c"]), "k c's type changed: payload, not graph");
assert_eq!(d.edges.keys().copied().collect::<Vec<_>>(), vec![DependsOn, UsesType]);
assert_eq!(d.edges[&DependsOn].added, vec![pair("k", "dep2")]);
assert_eq!(d.edges[&UsesType].added, vec![pair("k b", "k T")]);
assert_eq!(d.edges[&UsesType].removed, vec![pair("k d", "k T")]);
assert_eq!(d.provenance_changed, vec![("k b".to_string(), Some(Provenance::Both), Some(Provenance::SourceOnly))]);
let d = r1.diff(&r3).unwrap().value;
assert_eq!((d.added_nodes.clone(), d.removed_nodes.clone()), (s(&["dep2", "k e"]), s(&["k d"])));
assert_eq!(d.changed, s(&["k c"]));
assert_eq!(d.edges[&Calls].added.len() + d.edges[&Calls].removed.len(), 3);
assert_eq!(d.edges[&UsesType].added, vec![pair("k b", "k T")]);
// backwards is the mirror image
let back = r3.diff(&r1).unwrap().value;
assert_eq!((back.added_nodes, back.removed_nodes, back.changed), (s(&["k d"]), s(&["dep2", "k e"]), s(&["k c"])));
let same = r2.diff(&r2).unwrap();
assert!(same.value.added_nodes.is_empty() && same.value.edges.is_empty() && same.value.changed.is_empty());
assert!(same.evidence.notes.iter().any(|n| n.contains("empty answer")), "{}", same.evidence);
}
#[tokio::test(flavor = "current_thread")]
async fn evidence_never_lets_an_empty_answer_pass_silently() {
let _g = serial().await;
let tmp = tempfile::tempdir().unwrap();
let log = fixture(tmp.path()).await;
let r = room(&log, Scope::current()).await;
// a kind this scope holds no edge of: the two reasons it can be empty are named
let g = r.reach(&["k a"], &[EdgeKind::GatedBy], None, None).unwrap();
assert!(g.value.reached.is_empty());
let m = g.evidence.missing_input("GATED_BY edges");
assert!(m.len() == 1 && m[0].why.contains("nothing here is behind a cargo feature") && m[0].why.contains("mimir-schema 2"), "{}", g.evidence);
// TOUCHES_TABLE has a producer (the driver, mimir-schema 4): none here
// means no fn of this scope reaches the engine with a table — or an old log
let t = r.reach(&["k a"], &[EdgeKind::TouchesTable], None, None).unwrap();
let why = &t.evidence.missing_input("TOUCHES_TABLE edges")[0].why;
assert!(why.contains("storage engine") && why.contains("mimir-schema 4") && !why.contains("another producer"), "{}", t.evidence);
// a kind with no producer at all
let c = r.reach(&["k a"], &[EdgeKind::Compatible], None, None).unwrap();
assert!(c.evidence.missing_input("COMPATIBLE edges")[0].why.contains("another producer"), "{}", c.evidence);
// a seed the room does not know
let u = r.dependents(&["k nope"], None).unwrap();
assert!(u.value.reached.is_empty() && u.value.seeds.is_empty());
assert!(u.evidence.missing_input("seed").iter().any(|m| m.why.contains("k nope")), "{}", u.evidence);
assert!(u.evidence.notes.iter().any(|n| n.contains("may be the gap")), "{}", u.evidence);
// binary-dependent query on a repo without a binary stream
let p = room(&log, Scope::repo(PLAIN, None)).await;
let i = p.instances_of("k a").unwrap();
assert!(i.value.is_empty());
let gaps = i.evidence.missing_input("binary stream");
assert!(gaps.len() == 1 && gaps[0].repo.as_deref() == Some(PLAIN) && gaps[0].why.contains("ABSENT"), "{}", i.evidence);
assert!(!i.evidence.missing_input("INSTANCE_OF edges").is_empty(), "{}", i.evidence);
// a source-only question on the same repo is complete
let d = p.dependents(&["k a"], None).unwrap();
assert_eq!(names(&p, &d.value.reached), s(&["p p1", "p p2"]));
assert!(d.evidence.missing.iter().all(|m| m.input.ends_with("edges")), "only kinds plain lacks: {}", d.evidence);
// asking for a state never consumed is an error, not an empty room
assert!(Room::at(&log, &Scope::repo(ROOM, Some(9))).await.is_err());
assert!(Room::at(&log, &Scope::repo("nobody", None)).await.is_err());
}