src/code_room/reader/wired/affected.rs
//! `Test.Affected` — **the tests a commit can break**, read from the room.
//!
//! Given a repo, the commit under test (`to`) and the commit it is compared
//! with (`from`; by default the newest commit before `to` whose Runa test
//! run was green), the answer names the tests whose reach holds something
//! the commit changed, and the tests a runner may SKIP:
//!
//! 1. **what changed** — the text diff of the two commits placed on the
//! room's items at `to` (each touched line → the innermost item whose span
//! holds it), and the graph's own diff between the two consumed seqs
//! ([`mimir_ingest::EventLog::interval_diff`]: nodes added / changed, the
//! caller end of every edge that came, went or moved);
//! 2. **what that reaches** — [`mimir_room::Room::dependents`] (the Jikes
//! walk: CALLS, USES_TYPE, IMPLEMENTS, FOR_TYPE backwards, down from every
//! impl reached), widened where the producer records no edge: a changed
//! method of a trait impl seeds the trait's own method (a call through the
//! trait, generic or `dyn`) and — for a trait of another crate (operators,
//! `Drop`, `Display` …, called by syntax) — the impl's self type; a field
//! seeds its readers (READS_FIELD); a fn used as a VALUE (`.map(f)`, no
//! call edge) seeds the item that uses it, to a fixpoint;
//! 3. **the tests** — every `is_test` node of the repo in that reach, every
//! test that names a reached item (TESTS), and every test whose own file
//! spawns the crate's binary (its reach crosses a process boundary).
//!
//! The skip list is every OTHER test the graph knows, by the name the runner
//! prints — minus a name another, selected test shares. A test the graph
//! does not know (a doc test, a target the consumer did not compile) is on
//! no list, so it runs: the answer can only ever cost more tests, never
//! fewer. When it cannot be sure at all — a manifest, the lock, a build
//! script, a toolchain pin, a `cfg`, a macro, code no item spans, a non-Rust
//! file a test may read, a commit the room has not read — `mode` is `all`
//! and `why` says which, in one line.
use std::collections::{BTreeMap, BTreeSet, HashMap};
use mimir_room::{EdgeSel, MaskSpec, Room, Scope};
use mimir_schema::{EdgeKind, Origin, kind as nk};
use serde_json::{Value, json};
use super::{Paths, envelope, internal, invalid, miss, note, settle, text};
use crate::code_room::{Reach, Refusal, State};
use crate::test_select::{self, BlockKind, CfgTarget, FileChange, FileDiff, LineKind, PathRule, Snapshot, Wanted};
/// Selected tests whose `reaches` (one changed item they stand on) is named.
const REASONS_CAP: usize = 200;
/// Value-use rounds before the selection gives up and runs all (each round
/// only grows the set: it settles; the cap is a guard, not a budget).
const MENTION_ROUNDS: usize = 64;
/// Changed fns no test reaches an answer lists.
const CHANGED_CAP: usize = 500;
/// Kinds an item of the room is (what a changed line is placed on).
const ITEM_KINDS: [&str; 18] = [
nk::FN,
nk::METHOD,
nk::STRUCT,
nk::ENUM,
nk::UNION,
nk::TRAIT,
nk::TRAIT_ALIAS,
nk::IMPL,
nk::CONST,
nk::STATIC,
nk::TYPE,
nk::MACRO,
nk::ASSOC_CONST,
nk::ASSOC_TYPE,
nk::FIELD,
nk::VARIANT,
nk::FFI,
nk::FOREIGN_TYPE,
];
/// The graph's own diff of the window, by moniker.
#[derive(Debug, Default, Clone)]
pub struct GraphDiff {
/// Nodes added or changed (the `to` side).
pub nodes: BTreeSet<String>,
/// The `from` end of every edge added, removed or changed.
pub callers: BTreeSet<String>,
}
/// Why an item is in the changed set.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum How {
/// A touched line lies in it.
Lines,
/// The graph's diff names it (added, changed payload, an edge of it moved).
Graph,
/// A changed method of a trait impl: the trait's own method / the self type.
Dispatch,
/// It uses a changed fn as a value, or reads a changed field.
Uses,
}
impl How {
fn as_str(self) -> &'static str {
match self {
How::Lines => "lines",
How::Graph => "graph",
How::Dispatch => "dispatch",
How::Uses => "value-use",
}
}
}
/// What the selection made of one window.
#[derive(Debug, Default, Clone)]
pub struct Selection {
/// `Some(why)`: every test runs.
pub all: Option<String>,
/// The changed items, and why each is.
pub changed: BTreeMap<u64, How>,
/// Ordinals of the selected tests.
pub selected: BTreeSet<u64>,
/// Ordinals of every test of the repo the room knows.
pub tests: Vec<u64>,
/// Runner names a runner may skip.
pub skip: Vec<String>,
/// Tests selected because their file spawns the binary.
pub spawners: usize,
/// Changed items no test reaches.
pub unreached: Vec<u64>,
/// Lines of the answer's evidence.
pub notes: Vec<String>,
/// Package dirs whose every test runs (a lock change, a file the consumer
/// did not compile, a change no item can be placed on — and the packages
/// that depend on them).
pub packages: Vec<String>,
}
impl Selection {
fn all(why: impl Into<String>) -> Self {
Self { all: Some(why.into()), ..Default::default() }
}
}
/// **Select the tests of `repo` in `room` (the room at `to`) that `files`
/// (the text diff `from → to`) and `graph` (the graph's diff, `None` = not
/// read) can break.** `snap` is the tree at `to`, `before` the tree at
/// `from` (`None` = not readable: a lock change then runs every test).
pub fn select(room: &Room, repo: &str, files: &[FileDiff], snap: &Snapshot, before: Option<&Snapshot>, graph: Option<&GraphDiff>) -> Result<Selection, Refusal> {
select_with_lock(room, repo, files, snap, before, Some(snap), graph)
}
/// [`select`] with the lock files read from `lock_before` / `lock_after`
/// instead of the source trees (a test seam: the lock of a scratch repo
/// against a room's own sources).
pub fn select_with_lock(room: &Room, repo: &str, files: &[FileDiff], snap: &Snapshot, lock_before: Option<&Snapshot>, lock_after: Option<&Snapshot>, graph: Option<&GraphDiff>) -> Result<Selection, Refusal> {
let mut sel = Selection::default();
let packages = snap.packages();
// whole packages whose every test runs: dir → (why, and the packages that depend on it too)
let mut whole: BTreeMap<String, (String, bool)> = BTreeMap::new();
// packages the consumer did not compile a changed file of: (dir, name, file)
let mut uncompiled: Vec<(String, String, String)> = Vec::new();
// ---- the paths the graph cannot see through
let mut others: Vec<(&FileDiff, bool)> = Vec::new();
for f in files {
match test_select::classify_path(&f.path) {
PathRule::All(_) if f.path.rsplit('/').next() == Some("Cargo.lock") => {
if let Err(why) = lock_rule(f, lock_after, lock_before, &packages, &mut whole) {
return Ok(Selection::all(why));
}
}
PathRule::All(why) => return Ok(Selection::all(why)),
PathRule::Rust => {}
PathRule::Other { doc_like } => others.push((f, doc_like)),
}
}
let rust_changed = files.iter().any(|f| f.path.ends_with(".rs"));
let mut changed: BTreeMap<u64, How> = BTreeMap::new();
// ---- touched lines → the innermost item that holds each
for f in files.iter().filter(|f| f.path.ends_with(".rs")) {
let in_file = room.nodes_in_file(Some(repo), &f.path);
let items: Vec<(u64, u32, u32, &str)> = in_file
.iter()
.filter_map(|o| {
let v = room.node(*o);
let k = v.kind?;
(ITEM_KINDS.contains(&k) && v.origin == Some(Origin::Local)).then_some((*o, v.start_line?, v.end_line.or(v.start_line)?, k))
})
.collect();
match f.change {
FileChange::Deleted => {
// its items are gone: whoever called them changed too (the graph's diff)
if graph.is_none() {
return Ok(Selection::all(format!("{} was deleted and the graph's own diff was not read: its former callers are not known", f.path)));
}
continue;
}
FileChange::Added | FileChange::Modified if in_file.is_empty() => {
// not a file of any unit the consumer compiled
let text = snap.text(&f.path).unwrap_or_default();
if text.lines().all(|l| matches!(test_select::line_kind(l), LineKind::Blank | LineKind::Comment)) {
continue;
}
// a target the consumer did not compile (a feature that is off, an
// example, a crate the workspace excludes): every test of ITS package
// runs — and of the packages that link it, when it is library code
let Some((dir, name)) = packages.of_file(&f.path) else {
return Ok(Selection::all(format!("{} holds no item of the room at this commit and belongs to no package of the tree: the graph cannot see what it changes", f.path)));
};
let lib = !test_select::is_non_lib_target(dir, &f.path);
let why = format!("{} holds no item of the room (a target the consumer did not compile): every test of package `{name}` runs{}", f.path, if lib { ", and of the packages that depend on it" } else { "" });
widen_whole(&mut whole, dir, why, lib);
uncompiled.push((dir.to_string(), name.to_string(), f.path.clone()));
continue;
}
_ => {}
}
let text = snap.text(&f.path).unwrap_or_default();
let lines: Vec<&str> = text.lines().collect();
let mut gated: Option<BTreeMap<u32, Vec<u64>>> = None;
// a change no item of the room can be found for: every test of the file's package (and its dependents)
let fallback = |whole: &mut BTreeMap<String, (String, bool)>, why: String| -> Result<(), String> {
match packages.of_file(&f.path) {
Some((dir, name)) => {
widen_whole(whole, dir, format!("{why}: every test of package `{name}` and of the packages that depend on it runs"), true);
Ok(())
}
None => Err(format!("{why}, and {} belongs to no package of the tree", f.path)),
}
};
for line in f.each_line() {
let holder = items
.iter()
.filter(|(_, s, e, _)| *s <= line && line <= *e)
.max_by(|a, b| a.1.cmp(&b.1).then(b.2.cmp(&a.2)))
.copied();
let src = lines.get(line as usize - 1).copied().unwrap_or("");
if test_select::line_kind(src) == LineKind::Cfg {
// a cfg: the items it gates (GATED_BY's attribute sites, else the item after it)
let gated = gated.get_or_insert_with(|| gated_sites(room, repo, &f.path, &in_file));
let mut seeds: Vec<u64> = gated.get(&line).cloned().unwrap_or_default();
let mut unsure: Option<String> = None;
let target = test_select::cfg_target(&lines, line);
match &target {
CfgTarget::Inner => {
seeds.extend(items.iter().map(|i| i.0));
if items.is_empty() {
unsure = Some(format!("a module-wide cfg changed at {}:{line} (`{}`)", f.path, src.trim()));
}
}
CfgTarget::Item(at) => {
let at = *at;
// the items that start between the attribute and the item's
// first line, and the innermost one that holds that line (a
// span that starts at a doc comment above the attribute)
let mut found: Vec<u64> = in_file.iter().copied().filter(|o| is_local_item(room, *o) && room.node(*o).start_line.is_some_and(|s| s >= line && s <= at)).collect();
let holds_at = in_file
.iter()
.copied()
.filter(|o| is_local_item(room, *o))
.filter_map(|o| {
let v = room.node(o);
let (s, e) = (v.start_line?, v.end_line.or(v.start_line)?);
(s <= at && at <= e).then_some((o, s, e))
})
.max_by(|a, b| a.1.cmp(&b.1).then(b.2.cmp(&a.2)))
.map(|x| x.0);
if let Some(o) = holds_at
&& holder.map(|h| h.0) != Some(o)
&& !(room.node(o).kind == Some(nk::MOD) && room.node(o).start_line.is_some_and(|s| s < line))
{
found.push(o);
}
if found.is_empty() {
// an item the room holds no node of (a module): the items
// of the block it opens
if let Some(b) = test_select::enclosing_blocks(&text, at).into_iter().find(|b| b.header == at && b.kind != BlockKind::Expr) {
found.extend(in_file.iter().copied().filter(|o| is_local_item(room, *o) && room.node(*o).start_line.is_some_and(|s| s >= b.header && s <= b.close)));
}
}
if found.is_empty() && seeds.is_empty() {
// compiled out at `to` (or a kind the room does not hold)
unsure = Some(format!("a cfg changed at {}:{line} (`{}`) on an item the room does not hold", f.path, src.trim()));
}
seeds.extend(found);
}
CfgTarget::ModFile(name) => {
let mut found = Vec::new();
for cand in mod_file_candidates(&f.path, name) {
found.extend(room.nodes_in_file(Some(repo), &cand).into_iter().filter(|o| is_local_item(room, *o)));
}
if found.is_empty() && seeds.is_empty() {
unsure = Some(format!("a cfg changed at {}:{line} (`{}`) on a module the room does not hold", f.path, src.trim()));
}
seeds.extend(found);
}
CfgTarget::Use => {
// a name moved: the graph's own diff carries what it moves
if graph.is_none() {
unsure = Some(format!("a cfg on a `use` changed at {}:{line} and the graph's own diff was not read", f.path));
}
}
CfgTarget::Body => {}
}
// the item the line stands in changes with it (a gate on a statement, a field …)
if let Some((o, ..)) = holder {
seeds.push(o);
} else if seeds.is_empty() && unsure.is_none() && target != CfgTarget::Use {
unsure = Some(format!("a cfg changed at {}:{line} (`{}`) outside any item the room holds", f.path, src.trim()));
}
for o in seeds {
if room.node(o).kind == Some(nk::MACRO) {
return Ok(Selection::all(format!("a cfg on macro `{}` changed ({}:{line}): its expansions are not in the graph", room.node(o).name.unwrap_or("?"), f.path)));
}
for x in expand_mod(room, repo, o) {
add(&mut changed, x, How::Lines);
}
}
if let Some(why) = unsure
&& let Err(why) = fallback(&mut whole, why)
{
return Ok(Selection::all(why));
}
continue;
}
if let Some((o, _, _, k)) = holder {
if k == nk::MACRO {
return Ok(Selection::all(format!(
"macro `{}` changed ({}:{line}): its expansions are not in the graph",
room.node(o).name.unwrap_or("?"),
f.path
)));
}
add(&mut changed, o, How::Lines);
if k == nk::IMPL && !matches!(test_select::line_kind(src), LineKind::Blank | LineKind::Comment | LineKind::Delimiter) {
// a line of an impl no item of it holds (a header, a where
// clause, an item macro): its items and its self type
for x in impl_items(room, repo, o) {
add(&mut changed, x, How::Lines);
}
}
continue;
}
match test_select::line_kind(src) {
LineKind::Blank | LineKind::Comment | LineKind::Delimiter => {}
LineKind::Use | LineKind::ModDecl if graph.is_some() => {}
LineKind::Use | LineKind::ModDecl => {
return Ok(Selection::all(format!("{}:{line} (`{}`) moved a name and the graph's own diff was not read", f.path, src.trim())));
}
LineKind::Cfg => unreachable!("placed above"),
LineKind::Attr => {
// an attribute belongs to the item that follows it
if let Some(&(o, _, _, _)) = items.iter().filter(|(_, s, _, _)| *s > line && *s <= line + 8).min_by_key(|(_, s, _, _)| *s) {
add(&mut changed, o, How::Lines);
} else if let Err(why) = fallback(&mut whole, format!("an attribute changed at {}:{line} (`{}`) and no item of the room follows it", f.path, src.trim())) {
return Ok(Selection::all(why));
}
}
LineKind::Code => {
// code between the items of a block (an impl's header or where
// clause, a line of a module or trait no item spans): every item
// of the innermost item block that holds it — for an impl its
// methods and its self type
let mut placed = false;
for b in test_select::enclosing_blocks(&text, line) {
if b.kind == BlockKind::Expr {
continue;
}
let inside: Vec<u64> = in_file
.iter()
.copied()
.filter(|o| is_local_item(room, *o) && room.node(*o).start_line.is_some_and(|s| s >= b.header && s <= b.close))
.collect();
if inside.is_empty() {
continue;
}
for o in inside {
if room.node(o).kind == Some(nk::MACRO) {
return Ok(Selection::all(format!("{}:{line} lies in a block that defines macro `{}`: its expansions are not in the graph", f.path, room.node(o).name.unwrap_or("?"))));
}
// an impl (the block's, or a method's own) → its self type too
let imp = if room.node(o).kind == Some(nk::IMPL) { Some(o) } else { room.node(o).parent.filter(|p| room.node(*p).kind == Some(nk::IMPL)) };
if let Some(imp) = imp {
add(&mut changed, imp, How::Lines);
if let Some(ty) = room.impl_self(imp) {
add(&mut changed, ty, How::Lines);
}
}
for x in expand_mod(room, repo, o) {
add(&mut changed, x, How::Lines);
}
}
placed = true;
break;
}
if !placed && let Err(why) = fallback(&mut whole, format!("{}:{line} holds code no item of the graph spans (`{}`)", f.path, src.trim())) {
return Ok(Selection::all(why));
}
}
}
}
}
// ---- non-Rust files: inert only when no .rs file names them
for (f, doc_like) in &others {
let base = f.path.rsplit('/').next().unwrap_or(&f.path);
let mut named_at: Vec<(String, u32)> = Vec::new();
for (path, text) in snap.rust_files() {
if !text.contains(base) {
continue;
}
for (i, l) in text.lines().enumerate() {
if l.contains(base) {
named_at.push((path.clone(), i as u32 + 1));
}
}
}
if named_at.is_empty() {
if *doc_like {
continue;
}
return Ok(Selection::all(format!("{} changed and no .rs file names it: a test may read it at run time", f.path)));
}
for (path, line) in named_at {
match innermost(room, repo, &path, line) {
Some(o) => add(&mut changed, o, How::Lines),
None => {
return Ok(Selection::all(format!("{} changed and {path}:{line} names it outside any item the graph knows", f.path)));
}
}
}
}
// ---- a package the consumer did not compile is reached across a process
// boundary (a test that builds or runs it) only through a string that names
// it: its dir, its package name, the target's name
for (dir, name, file) in &uncompiled {
let mut terms: BTreeSet<String> = [name.clone()].into();
if !dir.is_empty() {
terms.insert(dir.clone());
terms.insert(dir.rsplit('/').next().unwrap_or(dir).to_string());
}
if test_select::is_non_lib_target(dir, file)
&& let Some(stem) = file.rsplit('/').next().and_then(|n| n.strip_suffix(".rs"))
&& !matches!(stem, "main" | "lib" | "mod" | "build")
{
terms.insert(stem.to_string());
}
let terms: Vec<String> = terms.into_iter().filter(|t| !t.is_empty()).collect();
for (path, line) in test_select::named_in_strings(snap.rust_files(), &terms) {
if !dir.is_empty() && path.starts_with(&format!("{dir}/")) {
continue;
}
match innermost(room, repo, &path, line) {
Some(o) => add(&mut changed, o, How::Uses),
None if room.nodes_in_file(Some(repo), &path).is_empty() => {}
None => {
return Ok(Selection::all(format!("{file} is not compiled and {path}:{line} names its package outside any item the graph knows")));
}
}
}
}
// ---- the graph's own diff: own code only (a toolchain item, a dependency
// item is no change of this repo — a dependency that moved is the lock's)
let lock_to = snap.text("Cargo.lock").and_then(|t| test_select::parse_lock(&t).ok());
if let Some(g) = graph {
let (mut dropped, mut crate_nodes) = (0usize, 0usize);
for m in g.nodes.iter().chain(g.callers.iter()) {
if let Some(o) = room.ordinal(m)
&& room.node(o).repo == Some(repo)
{
if !own_code(room, o) {
dropped += 1;
continue;
}
match room.node(o).kind {
// a module node moved (its cfg, its doc …): its items, never the node
Some(k) if k == nk::MOD => {
for x in expand_mod(room, repo, o) {
add(&mut changed, x, How::Graph);
}
}
// a crate node carries its manifest's say (version, dependencies,
// the features it was built with): the manifest and lock rules own
// that; its items come in the diff themselves
Some(k) if k == nk::CRATE => crate_nodes += 1,
_ => add(&mut changed, o, How::Graph),
}
}
}
if crate_nodes > 0 {
sel.notes.push(format!("{crate_nodes} crate node(s) of the graph's own diff stand for their manifests (the manifest and lock rules): their items are placed one by one"));
}
if dropped > 0 {
sel.notes.push(format!("{dropped} node(s) of the graph's own diff are toolchain or dependency items, not this repo's code: left out (a dependency that moved is the lock's)"));
}
} else {
sel.notes.push("the graph's own diff (interval_diff) was not read: changes are placed by the text diff alone".into());
}
// ---- widen: fields, trait dispatch, value uses — to a fixpoint
let tests_mask = room
.mask(&MaskSpec { repos: vec![repo.to_string()], is_test: Some(true), ..Default::default() })
.map_err(super::internal)?
.value;
let mut reached: BTreeSet<u64> = BTreeSet::new();
let mut looked: BTreeSet<u64> = BTreeSet::new();
for round in 0..=MENTION_ROUNDS {
widen(room, &mut changed)?;
let seeds: Vec<u64> = changed.keys().copied().collect();
let walk = room.dependents(&seeds[..], None).map_err(internal)?.value;
reached = walk.reached.iter().copied().chain(seeds.iter().copied()).collect();
// fns used as a value: a use of one seeds the item that holds it
let fresh: Vec<u64> = reached.iter().copied().filter(|o| !looked.contains(o) && matches!(room.node(*o).kind, Some(k) if k == nk::FN || k == nk::METHOD)).collect();
if fresh.is_empty() {
break;
}
looked.extend(fresh.iter().copied());
let wanted = wanted_of(room, repo, &fresh);
let mut grew = false;
for (path, line, _) in test_select::mentions(snap.rust_files(), &wanted) {
if let Some(o) = innermost(room, repo, &path, line)
&& !reached.contains(&o)
&& !changed.contains_key(&o)
{
add(&mut changed, o, How::Uses);
grew = true;
}
}
if !grew {
break;
}
if round == MENTION_ROUNDS {
return Ok(Selection::all(format!("the fns used as values do not settle after {MENTION_ROUNDS} rounds: every test runs")));
}
}
// ---- the tests
let mut selected: BTreeSet<u64> = tests_mask.ordinals().iter().copied().filter(|t| reached.contains(t)).collect();
if !reached.is_empty() {
let reached_v: Vec<u64> = reached.iter().copied().collect();
let to = room.mask_of(&reached_v);
let named = room.edges(&EdgeSel { from: Some(&tests_mask), to: Some(&to), ..EdgeSel::kinds(&[EdgeKind::Tests]) }).map_err(internal)?;
selected.extend(named.value.edges.iter().map(|e| e.from));
}
if rust_changed {
let mut spawn_file: HashMap<String, bool> = HashMap::new();
for t in tests_mask.ordinals() {
let Some(file) = room.node(*t).file else { continue };
let spawns = *spawn_file.entry(file.to_string()).or_insert_with(|| snap.text(file).is_some_and(|x| test_select::spawns_binary(&x)));
if spawns && selected.insert(*t) {
sel.spawners += 1;
}
}
}
// whole packages (a lock change, a file the consumer did not compile, a change
// no item can be found for): with the packages that depend on them, every test
if !whole.is_empty() {
let dirs = whole_dirs(snap, &packages, &whole, lock_to.as_deref());
let names: BTreeSet<String> = dirs.iter().filter_map(|d| packages.by_dir.get(d)).map(|n| test_select::norm_crate(n)).collect();
for t in tests_mask.ordinals() {
let v = room.node(*t);
let by_file = v.file.and_then(|f| packages.of_file(f)).is_some_and(|(d, _)| dirs.contains(d));
let by_crate = v.krate.is_some_and(|k| names.contains(&test_select::norm_crate(k)));
if by_file || by_crate {
selected.insert(*t);
}
}
for (dir, (why, _)) in &whole {
sel.notes.push(why.clone());
sel.packages.push(dir.clone());
}
sel.packages.extend(dirs.into_iter().filter(|d| !whole.contains_key(d)));
sel.packages.sort();
sel.packages.dedup();
}
// ---- what a runner may skip: every other test, by the name it prints,
// unless a selected test prints the same name
let mut paths = Paths::new(room);
let mut by_name: BTreeMap<String, bool> = BTreeMap::new();
for t in tests_mask.ordinals() {
let v = room.node(*t);
let Some(name) = v.name else { continue };
let module = v.parent.map(|x| paths.of(x)).unwrap_or_default();
let runner = test_select::runner_name(&module, name);
*by_name.entry(runner).or_insert(false) |= selected.contains(t);
}
sel.skip = by_name.into_iter().filter(|(_, sel)| !sel).map(|(n, _)| n).collect();
// the changed fns no selected test stands on: ONE forward walk from them all
let sel_v: Vec<u64> = selected.iter().copied().collect();
let stood_on: BTreeSet<u64> = if sel_v.is_empty() {
BTreeSet::new()
} else {
room.reach(&sel_v[..], &[EdgeKind::Calls, EdgeKind::Tests], None, None).map_err(internal)?.value.reached.into_iter().chain(sel_v.iter().copied()).collect()
};
sel.unreached = changed.keys().copied().filter(|o| is_code(room, *o) && !stood_on.contains(o)).take(CHANGED_CAP).collect();
sel.tests = tests_mask.ordinals().to_vec();
sel.selected = selected;
sel.changed = changed;
Ok(sel)
}
/// Mark the package in `dir` whole (every test runs), `dependents` = the
/// packages that depend on it too.
fn widen_whole(whole: &mut BTreeMap<String, (String, bool)>, dir: &str, why: String, dependents: bool) {
let e = whole.entry(dir.to_string()).or_insert((why, dependents));
e.1 |= dependents;
}
/// **A `Cargo.lock` change**: the packages whose resolution moved, and every
/// package of the tree that depends on one, run whole. `Err(why)` = the lock
/// cannot be read on both sides: every test runs.
fn lock_rule(f: &FileDiff, after: Option<&Snapshot>, before: Option<&Snapshot>, packages: &test_select::Packages, whole: &mut BTreeMap<String, (String, bool)>) -> Result<(), String> {
let all = |what: &str| format!("{} changed — {what}: every test runs", f.path);
let (Some(before), Some(snap)) = (before, after) else { return Err(all("the tree before it is not readable")) };
let read = |s: &Snapshot| -> Result<Vec<test_select::LockPkg>, String> {
match s.text(&f.path) {
Some(t) => test_select::parse_lock(&t).map_err(|e| all(&format!("it does not parse ({e})"))),
None => Err(all("it is added or removed")),
}
};
let (a, b) = (read(before)?, read(snap)?);
let moved = test_select::lock_moved(&a, &b);
if moved.is_empty() {
return Ok(());
}
let reach = test_select::lock_dependents(&[&a, &b], &moved);
let moved_list: Vec<&str> = moved.iter().map(String::as_str).take(6).collect();
let more = if moved.len() > 6 { format!(" and {} more", moved.len() - 6) } else { String::new() };
for (dir, name) in &packages.by_dir {
if reach.iter().any(|r| test_select::norm_crate(r) == test_select::norm_crate(name)) {
widen_whole(whole, dir, format!("{} moved {}{more}: every test of package `{name}` (it depends on them) runs", f.path, moved_list.join(", ")), false);
}
}
Ok(())
}
/// The dirs of every package to run whole: `whole`, and for an entry that
/// says so the packages of the tree that depend on it (by their manifests'
/// dependencies, and the lock's).
fn whole_dirs(snap: &Snapshot, packages: &test_select::Packages, whole: &BTreeMap<String, (String, bool)>, lock: Option<&[test_select::LockPkg]>) -> BTreeSet<String> {
let mut out: BTreeSet<String> = whole.keys().cloned().collect();
let seeds: BTreeSet<String> = whole.iter().filter(|(_, (_, deps))| *deps).filter_map(|(d, _)| packages.by_dir.get(d).cloned()).collect();
if seeds.is_empty() {
return out;
}
let from_manifests = test_select::manifest_deps(snap.manifests());
let mut reach = test_select::lock_dependents(&[&from_manifests], &seeds);
if let Some(l) = lock {
reach.extend(test_select::lock_dependents(&[l], &seeds));
}
for (dir, name) in &packages.by_dir {
if reach.iter().any(|r| test_select::norm_crate(r) == test_select::norm_crate(name)) {
out.insert(dir.clone());
}
}
out
}
/// Own code: an item of a workspace package (`local`) — never the
/// toolchain's or a dependency's (a dump re-describes those; a dependency that
/// moved is the lock's).
fn own_code(room: &Room, o: u64) -> bool {
room.node(o).origin == Some(Origin::Local)
}
/// An impl block's own items (its methods, assoc consts / types, by span and
/// by parent) and its self type.
fn impl_items(room: &Room, repo: &str, imp: u64) -> Vec<u64> {
let mut out: Vec<u64> = expand_spans(room, repo, imp);
if let Some(ty) = room.impl_self(imp)
&& room.node(ty).origin == Some(Origin::Local)
{
out.push(ty);
}
out
}
/// A local item of the room a change can be placed on (an item kind, or a module).
fn is_local_item(room: &Room, o: u64) -> bool {
let v = room.node(o);
v.origin == Some(Origin::Local) && matches!(v.kind, Some(k) if ITEM_KINDS.contains(&k) || k == nk::MOD)
}
/// A module → itself and every local item its spans hold; an impl → its
/// items and self type; anything else → itself.
fn expand_mod(room: &Room, repo: &str, o: u64) -> Vec<u64> {
match room.node(o).kind {
// never the module itself: a backward walk from a module climbs its
// CONTAINS to the crate and reaches everything
Some(k) if k == nk::MOD => expand_spans(room, repo, o).into_iter().filter(|x| *x != o).collect(),
Some(k) if k == nk::IMPL => impl_items(room, repo, o),
_ => vec![o],
}
}
/// `o` and every local item its spans hold, or whose parent it is.
fn expand_spans(room: &Room, repo: &str, o: u64) -> Vec<u64> {
let mut out = vec![o];
for s in room.spans_of(o) {
out.extend(
room.nodes_in_file(Some(repo), s.file)
.into_iter()
.filter(|x| *x != o && is_local_item(room, *x) && (room.node(*x).parent == Some(o) || room.node(*x).start_line.is_some_and(|l| l >= s.start_line && l <= s.end_line))),
);
}
out.sort_unstable();
out.dedup();
out
}
/// The files `mod name;` in `file` may load: `<dir>/name.rs`, `<dir>/name/mod.rs`
/// — `<dir>` the file's own dir for `lib.rs` / `main.rs` / `mod.rs`, else the
/// dir named after the file.
fn mod_file_candidates(file: &str, name: &str) -> Vec<String> {
let (dir, base) = file.rsplit_once('/').unwrap_or(("", file));
let stem = base.strip_suffix(".rs").unwrap_or(base);
let d = if matches!(stem, "lib" | "main" | "mod") { dir.to_string() } else if dir.is_empty() { stem.to_string() } else { format!("{dir}/{stem}") };
let j = |p: &str| if d.is_empty() { p.to_string() } else { format!("{d}/{p}") };
vec![j(&format!("{name}.rs")), j(&format!("{name}/mod.rs"))]
}
/// GATED_BY's attribute sites in `file`: line → the items the attribute there gates.
fn gated_sites(room: &Room, repo: &str, file: &str, in_file: &[u64]) -> BTreeMap<u32, Vec<u64>> {
let mut out: BTreeMap<u32, Vec<u64>> = BTreeMap::new();
if in_file.is_empty() {
return out;
}
let m = room.mask_of(in_file);
let Ok(edges) = room.edges(&EdgeSel { from: Some(&m), ..EdgeSel::kinds(&[EdgeKind::GatedBy]) }) else { return out };
for e in &edges.value.edges {
for s in room.sites(e.from, e.to, EdgeKind::GatedBy) {
if s.file == file && s.repo == repo {
out.entry(s.start_line).or_default().push(e.from);
}
}
}
out
}
/// Mark `o` changed (the strongest reason wins).
fn add(changed: &mut BTreeMap<u64, How>, o: u64, how: How) {
let e = changed.entry(o).or_insert(how);
*e = (*e).min(how);
}
/// A fn / method of local code (what "a changed function no test reaches"
/// names).
fn is_code(room: &Room, o: u64) -> bool {
let v = room.node(o);
!v.is_test && v.origin == Some(Origin::Local) && matches!(v.kind, Some(k) if k == nk::FN || k == nk::METHOD)
}
/// The innermost item of `repo` whose span holds `path:line`.
fn innermost(room: &Room, repo: &str, path: &str, line: u32) -> Option<u64> {
room.nodes_in_file(Some(repo), path)
.into_iter()
.filter_map(|o| {
let v = room.node(o);
let k = v.kind?;
let (s, e) = (v.start_line?, v.end_line.or(v.start_line)?);
(ITEM_KINDS.contains(&k) && s <= line && line <= e).then_some((o, s, e))
})
.max_by(|a, b| a.1.cmp(&b.1).then(b.2.cmp(&a.2)))
.map(|(o, _, _)| o)
}
/// The fns `fresh` as names to look for as values: qualified by their
/// parent's name always, unqualified when no other fn of the repo has it.
fn wanted_of(room: &Room, repo: &str, fresh: &[u64]) -> Vec<Wanted> {
let fns = room.mask(&MaskSpec { repos: vec![repo.to_string()], node_kinds: vec![nk::FN.into(), nk::METHOD.into()], ..Default::default() });
let mut count: HashMap<&str, usize> = HashMap::new();
if let Ok(fns) = &fns {
for o in fns.value.ordinals() {
if let Some(n) = room.node(*o).name {
*count.entry(n).or_default() += 1;
}
}
}
let mut out: BTreeSet<Wanted> = BTreeSet::new();
for o in fresh {
let v = room.node(*o);
let Some(name) = v.name else { continue };
if v.is_test || name.len() < 2 {
continue;
}
let parent = v.parent.and_then(|p| impl_self_name(room, p).or_else(|| room.node(p).name.map(str::to_string))).unwrap_or_default();
out.insert(Wanted { name: name.to_string(), parent, unique: count.get(name).copied().unwrap_or(0) <= 1 });
}
out.into_iter().collect()
}
/// The self type's name of an impl block (`Point` for `impl Point` /
/// `impl Tr for Point`) — what a method is qualified by at a use.
fn impl_self_name(room: &Room, imp: u64) -> Option<String> {
if room.node(imp).kind != Some(nk::IMPL) {
return None;
}
let m = room.mask_of(&[imp]);
let e = room.edges(&EdgeSel { from: Some(&m), ..EdgeSel::kinds(&[EdgeKind::ForType]) }).ok()?;
e.value.edges.first().and_then(|e| room.node(e.to).name.map(str::to_string))
}
/// Widen the changed set where the producer records no edge: a field or a
/// variant → its readers (READS_FIELD) and its type; a method of a trait
/// impl → the trait's own method of that name, and — the trait being
/// another crate's (an operator, `Drop`, `Display` …, called by syntax) —
/// the impl's self type.
fn widen(room: &Room, changed: &mut BTreeMap<u64, How>) -> Result<(), Refusal> {
let mut more: Vec<(u64, How)> = Vec::new();
for (&o, _) in changed.iter() {
let v = room.node(o);
match v.kind {
Some(k) if k == nk::FIELD || k == nk::VARIANT || k == nk::ASSOC_CONST || k == nk::ASSOC_TYPE => {
if let Some(p) = v.parent {
more.push((p, How::Uses));
}
let m = room.mask_of(&[o]);
let readers = room.edges(&EdgeSel { to: Some(&m), ..EdgeSel::kinds(&[EdgeKind::ReadsField]) }).map_err(internal)?;
more.extend(readers.value.edges.iter().map(|e| (e.from, How::Uses)));
}
Some(k) if k == nk::METHOD || k == nk::FN => {
let Some(imp) = v.parent.filter(|p| room.node(*p).kind == Some(nk::IMPL)) else { continue };
let im = room.mask_of(&[imp]);
let traits = room.edges(&EdgeSel { from: Some(&im), ..EdgeSel::kinds(&[EdgeKind::Implements]) }).map_err(internal)?;
for t in traits.value.edges.iter().map(|e| e.to) {
let tm = room.mask_of(&[t]);
let items = room.edges(&EdgeSel { from: Some(&tm), ..EdgeSel::kinds(&[EdgeKind::Contains]) }).map_err(internal)?;
more.extend(items.value.edges.iter().filter(|e| room.node(e.to).name == v.name).map(|e| (e.to, How::Dispatch)));
if room.node(t).origin != Some(Origin::Local) {
let self_ty = room.edges(&EdgeSel { from: Some(&im), ..EdgeSel::kinds(&[EdgeKind::ForType]) }).map_err(internal)?;
more.extend(self_ty.value.edges.iter().map(|e| (e.to, How::Dispatch)));
}
}
}
_ => {}
}
}
for (o, how) in more {
changed.entry(o).or_insert(how);
}
Ok(())
}
/// The graph's diff of `repo` over `(from, to]`, read from the READ-FAST
/// zone (nodes added / changed; the caller end of every edge that moved).
#[cfg(feature = "code-room")]
pub fn graph_diff(log: &mimir_ingest::EventLog, repo: &str, from: i64, to: i64) -> anyhow::Result<GraphDiff> {
use mimir_ingest::Kind;
let nodes = log.block_on(log.interval_diff(Kind::Nodes, repo, from, to))?;
let edges = log.block_on(log.interval_diff(Kind::Edges, repo, from, to))?;
let mut g = GraphDiff::default();
for &(bi, ri) in nodes.added.iter().chain(nodes.changed.iter()) {
if let Some(id) = cell(&nodes.batches[bi as usize], "id", ri as usize) {
g.nodes.insert(id);
}
}
for &(bi, ri) in edges.added.iter().chain(edges.removed.iter()).chain(edges.changed.iter()) {
let b = &edges.batches[bi as usize];
if cell(b, "kind", ri as usize).as_deref() == Some(EdgeKind::Contains.as_str()) {
continue;
}
if let Some(from) = cell(b, "from", ri as usize) {
g.callers.insert(from);
}
}
Ok(g)
}
/// One text cell of a diff row, cast to text whatever the column's type.
#[cfg(feature = "code-room")]
fn cell(b: &skade::arrow_array::RecordBatch, name: &str, i: usize) -> Option<String> {
use skade::arrow_array::Array;
let c = b.column_by_name(name)?;
let c = skade::arrow_cast::cast(c, &skade::arrow_schema::DataType::Utf8).ok()?;
let c = c.as_any().downcast_ref::<skade::arrow_array::StringArray>()?;
(!c.is_null(i)).then(|| c.value(i).to_string())
}
/// The commits of `repo` whose Runa test run was green (at least one case
/// passed and none failed), read from `test_outcomes`.
fn green_commits(reach: &Reach<'_>, repo: &str, ev: &mut mimir_room::Evidence) -> BTreeSet<String> {
let Some(wh) = reach.warehouse else {
miss(ev, "test_outcomes", Some(repo), "this front door reaches no warehouse: no green run can be found to compare with");
return BTreeSet::new();
};
let rows = match wh.scan_preview_bounded("test_outcomes", 5_000_000, 1 << 30) {
Ok((p, _)) => crate::mimir_lens::rows::parse_test_outcomes(&crate::mimir_lens::rows::Table::new(p.columns, p.rows)),
Err(e) => {
miss(ev, "test_outcomes", Some(repo), format!("not read: {}", format!("{e:#}").lines().next().unwrap_or("")));
return BTreeSet::new();
}
};
let mut verdict: BTreeMap<String, (bool, bool)> = BTreeMap::new();
for r in rows.iter().filter(|r| r.repo == repo && !r.commit.is_empty()) {
let e = verdict.entry(r.commit.clone()).or_default();
match r.status.as_str() {
"pass" => e.0 = true,
"fail" => e.1 = true,
_ => {}
}
}
verdict.into_iter().filter(|(_, (pass, fail))| *pass && !*fail).map(|(c, _)| c).collect()
}
/// An `all` answer: every test runs, and why.
fn all_answer(repo: &str, to: &str, from: &str, baseline: &str, why: String, mut ev: mimir_room::Evidence) -> Value {
ev.query = format!("the tests of `{repo}` a commit can break");
note(&mut ev, "mode `all`: the selection cannot be sure, so every test runs");
settle(&mut ev, false);
envelope(
json!({
"repo": repo, "to": to, "from": from, "baseline": baseline,
"mode": "all", "why": why,
"tests_total": 0, "selected": [], "skip": [], "changed": [], "changed_unreached": [],
}),
&ev,
)
}
/// **`Test.Affected`** — `{repo, to?, from?}`.
pub(super) fn affected_tests(reach: &Reach<'_>, p: &Value) -> Result<Value, Refusal> {
let repo = text(p, "repo");
if repo.is_empty() {
return Err(invalid("Test.Affected: `repo` is empty — name the workspace member whose tests are asked about"));
}
let (to_spec, from_spec) = (text(p, "to"), text(p, "from"));
let handle = reach.code_room()?;
let log = handle.log()?;
let runs = log.block_on(log.runs(repo)).map_err(internal)?;
if runs.is_empty() {
return Err(Refusal::new(State::NotConsumed, format!("Test.Affected: `{repo}` has no consumed commit — the room never read it")));
}
let tip = runs.iter().map(|r| r.seq).max().unwrap_or(0);
// a sha (or a prefix of ≥ 7) → its newest ledger row
let find = |spec: &str| runs.iter().rev().find(|r| spec.len() >= 7 && r.sha.starts_with(spec)).cloned();
let mut ev = mimir_room::Evidence::default();
let short = |s: &str| s.chars().take(12).collect::<String>();
let to = if to_spec.is_empty() { runs.iter().rev().find(|r| r.seq == tip).cloned() } else { find(to_spec) };
let Some(to) = to else {
let why = format!(
"the room has not read {} of `{repo}` yet (its newest is {} at seq {tip}) — a BuildWorkspace step in a stage before the tests reads it first",
short(to_spec),
short(&runs.last().map(|r| r.sha.clone()).unwrap_or_default())
);
return Ok(all_answer(repo, to_spec, from_spec, "none", why, ev));
};
if to.status == mimir_ingest::schema::STATUS_ERROR || to.status == mimir_ingest::schema::STATUS_PARTIAL {
let why = format!("the consumer read {} with status `{}`: the graph is not wholly this commit's", short(&to.sha), to.status);
return Ok(all_answer(repo, &to.sha, from_spec, "none", why, ev));
}
// the baseline: named, or the newest green commit before `to`
let (from, baseline) = if !from_spec.is_empty() {
match find(from_spec) {
Some(r) => (r, "named"),
None => {
let why = format!("the room never read the `from` commit {} of `{repo}`", short(from_spec));
return Ok(all_answer(repo, &to.sha, from_spec, "named", why, ev));
}
}
} else {
let green = green_commits(reach, repo, &mut ev);
match runs.iter().rev().find(|r| r.seq < to.seq && green.contains(&r.sha)) {
Some(r) => (r.clone(), "previous_green"),
None => {
let why = format!("no green test run of `{repo}` before {} in the warehouse: nothing to compare with", short(&to.sha));
return Ok(all_answer(repo, &to.sha, "", "none", why, ev));
}
}
};
if from.seq > to.seq {
return Err(invalid(format!("Test.Affected: `from` {} (seq {}) comes after `to` {} (seq {})", short(&from.sha), from.seq, short(&to.sha), to.seq)));
}
let room = handle.room(&Scope::repo(repo, Some(to.seq)))?;
let clone = handle.layout().clone_of(repo);
let before = Snapshot::at(&clone, &from.sha).ok();
let (files, snap) = match (test_select::commit_diff(&clone, &from.sha, &to.sha), Snapshot::at(&clone, &to.sha)) {
(Ok(f), Ok(s)) => (f, s),
(Err(e), _) | (_, Err(e)) => {
let why = format!("the commits cannot be diffed in the consumer's clone {}: {}", clone.display(), format!("{e:#}").lines().next().unwrap_or(""));
return Ok(all_answer(repo, &to.sha, &from.sha, baseline, why, ev));
}
};
let graph = if from.seq < to.seq {
match graph_diff(&log, repo, from.seq, to.seq) {
Ok(g) => Some(g),
Err(e) => {
miss(&mut ev, "interval_diff", Some(repo), format!("the graph's own diff was not read: {}", format!("{e:#}").lines().next().unwrap_or("")));
None
}
}
} else {
Some(GraphDiff::default())
};
let sel = select(&room, repo, &files, &snap, before.as_ref(), graph.as_ref())?;
if let Some(why) = sel.all {
return Ok(all_answer(repo, &to.sha, &from.sha, baseline, why, ev));
}
let mut paths = Paths::new(&room);
let place = |o: u64, paths: &mut Paths<'_>| {
let v = room.node(o);
(paths.of(o), v.file.unwrap_or("").to_string(), v.start_line.unwrap_or(0), v.end_line.unwrap_or(0))
};
let changed: Vec<Value> = sel
.changed
.iter()
.filter(|(o, _)| room.node(**o).repo == Some(repo))
.map(|(o, how)| {
let (fqn, file, line, end_line) = place(*o, &mut paths);
json!({ "fqn": fqn, "kind": room.node(*o).kind, "file": file, "line": line, "end_line": end_line, "how": how.as_str() })
})
.collect();
let seeds: BTreeSet<u64> = sel.changed.keys().copied().collect();
let selected: Vec<Value> = sel
.selected
.iter()
.enumerate()
.map(|(i, t)| {
let v = room.node(*t);
let module = v.parent.map(|x| paths.of(x)).unwrap_or_default();
let mut row = json!({
"name": test_select::runner_name(&module, v.name.unwrap_or("")),
"crate": v.krate, "file": v.file, "line": v.start_line,
});
if i < REASONS_CAP {
let reaches = if seeds.contains(t) {
Some(paths.of(*t))
} else {
room.reach(&[*t][..], &[EdgeKind::Calls, EdgeKind::UsesType, EdgeKind::Tests, EdgeKind::ReadsField], None, None)
.ok()
.and_then(|w| w.value.reached.iter().find(|r| seeds.contains(r)).map(|r| paths.of(*r)))
};
row["reaches"] = json!(reaches.unwrap_or_else(|| "a changed type / trait (the impl walk), or the binary it spawns".into()));
}
row
})
.collect();
let unreached: Vec<String> = sel.unreached.iter().map(|o| paths.of(*o)).collect();
let (n, m) = (sel.selected.len(), sel.tests.len());
let fns: Vec<&str> = changed.iter().filter_map(|c| c["fqn"].as_str()).take(3).collect();
let why = if sel.changed.is_empty() {
format!("nothing the graph places changed between {} and {}", short(&from.sha), short(&to.sha))
} else {
format!(
"{} changed item(s) since {} ({}{}): {n} of {m} test(s) reach one{}",
sel.changed.len(),
short(&from.sha),
fns.join(", "),
if sel.changed.len() > fns.len() { ", …" } else { "" },
if sel.spawners > 0 { format!(" ({} spawn the binary)", sel.spawners) } else { String::new() }
)
};
ev.query = format!("the tests of `{repo}` {} can break", short(&to.sha));
for n in &sel.notes {
note(&mut ev, n);
}
note(&mut ev, "a test the graph does not know (a doc test, a target the consumer did not compile) is on no list: it runs");
note(&mut ev, "`skip` = every other test the graph knows, by the name the runner prints, unless a selected test prints the same name");
settle(&mut ev, false);
Ok(envelope(
json!({
"repo": repo,
"to": to.sha, "to_seq": to.seq,
"from": from.sha, "from_seq": from.seq,
"baseline": baseline,
"mode": "affected",
"why": why,
"tests_total": m,
"selected": selected,
"skip": sel.skip,
"changed": changed,
"changed_unreached": unreached,
"whole_packages": sel.packages,
"notes": sel.notes,
"room": super::panes::identity(handle, &room),
}),
&ev,
))
}
#[cfg(test)]
mod tests {
use std::path::Path;
use serde_json::{Value, json};
use crate::code_room::Reach;
use crate::code_room::reader::fixture;
fn edit(dir: &Path, file: &str, from: &str, to: &str) {
let p = dir.join(file);
let t = std::fs::read_to_string(&p).unwrap();
assert!(t.contains(from), "{file} holds no `{from}`");
std::fs::write(&p, t.replacen(from, to, 1)).unwrap();
}
/// The driver's fixture with three more tests in `a` (`norms` → Point::norm1,
/// `triples` → tiny, `applies` → apply, handing it `tiny` AS A VALUE), then:
/// c1 changes the BODY of `tiny` (same lines), c2 its crate's manifest, c3 the
/// `twice!` macro.
fn history() -> &'static (fixture::Workspace, Vec<String>) {
static WS: std::sync::LazyLock<(fixture::Workspace, Vec<String>)> = std::sync::LazyLock::new(|| {
fixture::real_history(&[
&|d: &Path| {
edit(
d,
"a/src/lib.rs",
"/// called by nothing: the linker drops it",
"/// `f` applied to `x`: a fn handed on as a value.\npub fn apply(f: fn(i32) -> i32, x: i32) -> i32 {\n f(x)\n}\n\n/// called by nothing: the linker drops it",
);
edit(
d,
"a/src/lib.rs",
" // ---- attributes (schema 3): `#[ignore]`, bare and with a reason",
" #[test]\n fn norms() {\n assert_eq!(super::Point::new(1, -2).norm1(), 3);\n }\n\n #[test]\n fn triples() {\n assert_eq!(super::tiny(2), 6);\n }\n\n #[test]\n fn applies() {\n assert_eq!(super::apply(super::tiny, 1), 3);\n }\n\n // ---- attributes (schema 3): `#[ignore]`, bare and with a reason",
);
},
&|d: &Path| edit(d, "a/src/lib.rs", " x * 3\n", " 3 * x\n"),
&|d: &Path| {
let p = d.join("a/Cargo.toml");
let t = std::fs::read_to_string(&p).unwrap();
std::fs::write(&p, format!("{t}\n# touched\n")).unwrap();
},
&|d: &Path| edit(d, "a/src/lib.rs", " $e + $e\n", " $e * 2\n"),
])
});
&WS
}
fn ask(from: &str, to: &str) -> Value {
let (ws, _) = history();
crate::code_room::reader::wired::answer("Test.Affected", &Reach::room_only(&ws.handle), &json!({ "repo": "fixture", "from": from, "to": to })).unwrap()
}
fn names(v: &Value, key: &str) -> Vec<String> {
v[key].as_array().unwrap().iter().map(|x| x.as_str().map(str::to_string).unwrap_or_else(|| x["name"].as_str().unwrap().to_string())).collect()
}
/// The owner's case: a change to `tiny` (its body only — no signature, no
/// edge, no line count moves) selects EXACTLY the tests that reach it — the
/// one that calls it and the one that hands it on as a value — and the
/// others are on the skip list by the name the runner prints.
#[test]
fn a_change_to_a_fn_selects_exactly_the_tests_that_reach_it() {
let (_, shas) = history();
let v = ask(&shas[0], &shas[1]);
assert_eq!(v["mode"], "affected", "{v:#}");
let mut selected = names(&v, "selected");
selected.sort();
assert_eq!(selected, vec!["tests::applies".to_string(), "tests::triples".to_string()], "{v:#}");
let skip = names(&v, "skip");
for t in ["tests::adds", "tests::norms", "tests::slow", "tests::slow_with_reason"] {
assert!(skip.contains(&t.to_string()), "{t} reaches nothing that changed: skipped — {skip:?}");
}
assert!(!skip.iter().any(|s| s == "tests::triples" || s == "tests::applies"), "{skip:?}");
let changed: Vec<&str> = v["changed"].as_array().unwrap().iter().filter_map(|c| c["fqn"].as_str()).collect();
assert!(changed.iter().any(|f| f.ends_with("tiny")), "{changed:?}");
assert_eq!(v["tests_total"].as_u64(), Some(selected.len() as u64 + skip.len() as u64), "{v:#}");
assert!(v["why"].as_str().unwrap().contains("2 of"), "{}", v["why"]);
}
/// A manifest change, and a macro change: the graph cannot see what they
/// change — every test runs, and the one line says why.
#[test]
fn a_cargo_toml_change_or_a_macro_change_runs_every_test() {
let (_, shas) = history();
let v = ask(&shas[1], &shas[2]);
assert_eq!(v["mode"], "all", "{v:#}");
assert!(v["why"].as_str().unwrap().starts_with("a/Cargo.toml changed"), "{}", v["why"]);
assert!(v["skip"].as_array().unwrap().is_empty());
let v = ask(&shas[2], &shas[3]);
assert_eq!(v["mode"], "all", "{v:#}");
assert!(v["why"].as_str().unwrap().contains("macro `twice`"), "{}", v["why"]);
}
/// A commit the room never read is not guessed at: every test runs.
#[test]
fn a_commit_the_room_has_not_read_runs_every_test() {
let (_, shas) = history();
let v = ask(&shas[0], "deadbeefdeadbeef");
assert_eq!(v["mode"], "all", "{v:#}");
assert!(v["why"].as_str().unwrap().contains("has not read"), "{}", v["why"]);
}
/// The driver's fixture with tests that each stand on ONE thing — `gates`
/// → `gated_on` (a `#[cfg(feature = "on")]` fn), `norms` → `Point::norm1`,
/// `triples` → `tiny`, `more_tests::other` (a second `#[cfg(test)]`
/// module) → `hidden_api`, `file_tests::in_file` (a `#[cfg(test)] mod
/// file_tests;` in its own file) → `add` — and a `noop!` macro; then one
/// commit per rule: c1 the cfg of `gated_on`, c2 the cfg of `more_tests`,
/// c3 the cfg of `mod file_tests;`, c4 a line inside `impl Point` that no
/// fn holds, c5 crate `c` (never compiled), c6 `a/src/extra_mod.rs`
/// (compiled only with `extra`).
fn precise() -> &'static (fixture::Workspace, Vec<String>) {
static WS: std::sync::LazyLock<(fixture::Workspace, Vec<String>)> = std::sync::LazyLock::new(|| {
fixture::real_history(&[
&|d: &Path| {
edit(d, "a/src/lib.rs", "pub trait Greet {", "macro_rules! noop {\n () => {};\n}\n\npub trait Greet {");
edit(
d,
"a/src/lib.rs",
" // ---- attributes (schema 3): `#[ignore]`, bare and with a reason",
" #[test]\n fn gates() {\n assert_eq!(super::gated_on(), 1);\n }\n\n #[test]\n fn norms() {\n assert_eq!(super::Point { x: 1, y: -2 }.norm1(), 3);\n }\n\n #[test]\n fn triples() {\n assert_eq!(super::tiny(2), 6);\n }\n\n // ---- attributes (schema 3): `#[ignore]`, bare and with a reason",
);
edit(
d,
"a/src/lib.rs",
"// ---- attributes (schema 3): `#[doc(hidden)]`",
"#[cfg(test)]\nmod more_tests {\n #[test]\n fn other() {\n assert_eq!(super::hidden_api(), 7);\n }\n}\n\n#[cfg(test)]\nmod file_tests;\n\n// ---- attributes (schema 3): `#[doc(hidden)]`",
);
std::fs::write(d.join("a/src/file_tests.rs"), "#[test]\nfn in_file() {\n assert_eq!(super::add(1, 1), 2);\n}\n").unwrap();
},
&|d: &Path| edit(d, "a/src/lib.rs", "#[cfg(feature = \"on\")]\npub fn gated_on", "#[cfg(any(feature = \"on\", test))]\npub fn gated_on"),
&|d: &Path| edit(d, "a/src/lib.rs", "#[cfg(test)]\nmod more_tests", "#[cfg(all(test, not(miri)))]\nmod more_tests"),
&|d: &Path| edit(d, "a/src/lib.rs", "#[cfg(test)]\nmod file_tests;", "#[cfg(all(test, not(miri)))]\nmod file_tests;"),
&|d: &Path| edit(d, "a/src/lib.rs", "impl Point {\n", "impl Point {\n noop!();\n"),
&|d: &Path| edit(d, "c/src/lib.rs", "cfg!(feature = \"turbo\")", "cfg!(feature = \"turbo\") && true"),
&|d: &Path| edit(d, "a/src/extra_mod.rs", " 7\n", " 7 + 0\n"),
])
});
&WS
}
fn ask_precise(i: usize) -> Value {
let (ws, shas) = precise();
crate::code_room::reader::wired::answer("Test.Affected", &Reach::room_only(&ws.handle), &json!({ "repo": "fixture", "from": shas[i - 1], "to": shas[i] })).unwrap()
}
fn selected_sorted(v: &Value) -> Vec<String> {
let mut s = names(v, "selected");
s.sort();
s
}
/// (b) A `cfg` on an item selects the tests that reach THAT item — not
/// every test.
#[test]
fn a_cfg_on_an_item_selects_the_tests_of_the_item_it_gates() {
let v = ask_precise(1);
assert_eq!(v["mode"], "affected", "{v:#}");
assert_eq!(selected_sorted(&v), vec!["tests::gates".to_string()], "{v:#}");
}
/// (b) A `cfg(test)` module's own cfg selects the tests of that module.
#[test]
fn a_cfg_test_module_change_selects_the_tests_in_that_module() {
let v = ask_precise(2);
assert_eq!(v["mode"], "affected", "{v:#}");
assert_eq!(selected_sorted(&v), vec!["more_tests::other".to_string()], "{v:#}");
}
/// (b) The cfg of a `mod x;` declaration selects the tests of x's file.
#[test]
fn a_cfg_on_a_mod_declaration_selects_the_tests_of_its_file() {
let v = ask_precise(3);
assert_eq!(v["mode"], "affected", "{v:#}");
assert_eq!(selected_sorted(&v), vec!["file_tests::in_file".to_string()], "{v:#}");
}
/// (c) A line inside an impl block that no fn holds stands for the impl's
/// items and its type: every test of `Point`'s methods runs, no other.
#[test]
fn an_impl_line_no_fn_holds_selects_the_tests_of_the_impl() {
let v = ask_precise(4);
assert_eq!(v["mode"], "affected", "{v:#}");
let s = selected_sorted(&v);
assert!(s.contains(&"tests::norms".to_string()), "{v:#}");
for t in ["tests::triples", "tests::gates", "more_tests::other", "file_tests::in_file", "tests::adds"] {
assert!(!s.contains(&t.to_string()), "{t} stands on nothing of the impl: {v:#}");
}
}
/// (a) A file the consumer did not compile costs the tests of ITS crate
/// (and of the crates on it), not the workspace: crate `c` is never
/// compiled and nothing compiled depends on it — no known test runs; a
/// feature-off file of `a` runs every test of `a`.
#[test]
fn a_file_not_compiled_selects_the_tests_of_its_crate_only() {
let v = ask_precise(5);
assert_eq!(v["mode"], "affected", "{v:#}");
assert!(selected_sorted(&v).is_empty(), "{v:#}");
let v = ask_precise(6);
assert_eq!(v["mode"], "affected", "{v:#}");
let s = selected_sorted(&v);
assert_eq!(s.len() as u64, v["tests_total"].as_u64().unwrap(), "every test of `a` (the fixture's only tests): {v:#}");
assert!(s.contains(&"tests::gates".to_string()) && s.contains(&"file_tests::in_file".to_string()), "{v:#}");
}
fn room_at_tip() -> (mimir_room::Room, std::path::PathBuf) {
let (ws, _) = precise();
(ws.handle.room(&mimir_room::Scope::repo("fixture", None)).unwrap(), ws.handle.layout().clone_of("fixture"))
}
fn test_names(room: &mimir_room::Room, sel: &super::Selection) -> Vec<String> {
let mut v: Vec<String> = sel.selected.iter().map(|t| room.node(*t).name.unwrap_or("").to_string()).collect();
v.sort();
v
}
/// (d) A lock change selects the tests of the crates that depend on what
/// moved — here every test is in `a`: a package only `b` uses selects
/// none; one `a` uses selects all of `a`'s; an unreadable lock runs all.
#[test]
fn a_lock_change_selects_the_tests_of_the_crates_on_what_moved() {
let (room, clone) = room_at_tip();
let snap = super::Snapshot::at(&clone, "HEAD").unwrap();
let dir = tempfile::tempdir().unwrap();
let d = dir.path();
crate::gitio::init(d).unwrap();
let lock = |zed: &str, yon: &str| format!("version = 4\n\n[[package]]\nname = \"a\"\nversion = \"0.1.0\"\ndependencies = [\"zed\"]\n\n[[package]]\nname = \"b\"\nversion = \"0.2.0\"\ndependencies = [\"a\", \"yon\"]\n\n[[package]]\nname = \"yon\"\nversion = \"{yon}\"\nsource = \"registry+https://github.com/rust-lang/crates.io-index\"\n\n[[package]]\nname = \"zed\"\nversion = \"{zed}\"\nsource = \"registry+https://github.com/rust-lang/crates.io-index\"\n");
let mut shas = Vec::new();
for text in [lock("1.0.0", "1.0.0"), lock("1.0.0", "2.0.0"), lock("1.1.0", "2.0.0"), "[[package]\n".to_string()] {
std::fs::write(d.join("Cargo.lock"), text).unwrap();
shas.push(crate::gitio::commit_all(d, "lock").unwrap());
}
let lockdiff = [crate::test_select::FileDiff { path: "Cargo.lock".into(), change: crate::test_select::FileChange::Modified, lines: vec![] }];
let at = |i: usize| super::Snapshot::at(d, &shas[i]).unwrap();
// the lock is read from the trees; the room's own files stay the fixture's
let sel_of = |i: usize| {
let (b, a) = (at(i - 1), at(i));
super::select_with_lock(&room, "fixture", &lockdiff, &snap, Some(&b), Some(&a), Some(&super::GraphDiff::default())).unwrap()
};
let s = sel_of(1);
assert!(s.all.is_none(), "{:?}", s.all);
assert!(s.selected.is_empty(), "{:?}", test_names(&room, &s));
let s = sel_of(2);
assert!(s.all.is_none(), "{:?}", s.all);
assert_eq!(s.selected.len(), s.tests.len(), "every test is a's: {:?}", test_names(&room, &s));
assert!(sel_of(3).all.is_some());
// no tree to compare with: every test
assert!(super::select(&room, "fixture", &lockdiff, &snap, None, Some(&super::GraphDiff::default())).unwrap().all.is_some());
}
/// (e) The changed items are the repo's OWN code: a dependency's or the
/// toolchain's node in the graph's diff (a std item the dump re-described)
/// is no changed item and selects nothing.
#[test]
fn a_dependency_node_in_the_graph_diff_is_no_change() {
let (room, clone) = room_at_tip();
let snap = super::Snapshot::at(&clone, "HEAD").unwrap();
let ext: Vec<String> = (0..room.len() as u64)
.filter(|o| {
let v = room.node(*o);
v.origin.is_some_and(|x| x != mimir_schema::Origin::Local) && v.repo == Some("fixture")
})
.map(|o| room.moniker(o).to_string())
.collect();
let ext_any: Vec<String> = (0..room.len() as u64).filter(|o| room.node(*o).origin.is_some_and(|x| x != mimir_schema::Origin::Local)).map(|o| room.moniker(o).to_string()).collect();
assert!(!ext_any.is_empty(), "the fixture's room holds std / dependency nodes");
let g = super::GraphDiff { nodes: ext.iter().chain(ext_any.iter()).cloned().collect(), callers: ext_any.iter().cloned().collect() };
let s = super::select(&room, "fixture", &[], &snap, None, Some(&g)).unwrap();
assert!(s.all.is_none(), "{:?}", s.all);
let foreign: Vec<&str> = s.changed.keys().filter(|o| room.node(**o).origin != Some(mimir_schema::Origin::Local)).map(|o| room.moniker(*o)).collect();
assert!(foreign.is_empty(), "{foreign:?}");
assert!(s.selected.is_empty(), "{:?}", test_names(&room, &s));
}
/// **The zero-loss safety check on a real lake**: for each `from:to` pair
/// of `$NORNIR_INCTEST_PAIRS` the selection is recomputed with
/// [`super::select`], and every test it did NOT select is walked forward
/// on its own (`reach_each` over CALLS, USES_TYPE, TESTS, READS_FIELD —
/// the evidence walk, a different path than the selection's backward
/// `dependents`): one whose reach holds a changed item is a DROPPED test,
/// and the law says there may be none. Over-selection is never flagged.
/// An `all` answer (every test runs) and a `partial` commit are zero-loss
/// by construction. The verdict of each pair is written to
/// `$NORNIR_INCTEST_OUT/zero-loss-<to12>.json`.
#[test]
#[ignore = "a safety check over a real lake: set NORNIR_INCTEST_{BUILDS,REPO,PAIRS,OUT}"]
fn zero_loss_superset_on_a_real_lake() {
use mimir_schema::EdgeKind;
let env = |k: &str| std::env::var(k).unwrap_or_else(|_| panic!("${k} is not set"));
let (builds, repo, pairs, out) = (env("NORNIR_INCTEST_BUILDS"), env("NORNIR_INCTEST_REPO"), env("NORNIR_INCTEST_PAIRS"), env("NORNIR_INCTEST_OUT"));
let handle = crate::code_room::CodeRoom::new("zeroloss", Path::new(&builds));
std::fs::create_dir_all(&out).unwrap();
let log = handle.log().unwrap();
let runs = log.block_on(log.runs(&repo)).unwrap();
let find = |spec: &str| runs.iter().rev().find(|r| spec.len() >= 7 && r.sha.starts_with(spec)).unwrap_or_else(|| panic!("`{spec}` is not a consumed commit of `{repo}`")).clone();
let clone = handle.layout().clone_of(&repo);
for pair in pairs.split(',').filter(|p| !p.is_empty()) {
let (from_spec, to_spec) = pair.split_once(':').unwrap();
let (from, to) = (find(from_spec), find(to_spec));
let t0 = std::time::Instant::now();
let mut v = json!({ "repo": repo, "from": from.sha, "to": to.sha, "zero_loss": "PASS" });
let verdict = loop {
if to.status == mimir_ingest::schema::STATUS_ERROR || to.status == mimir_ingest::schema::STATUS_PARTIAL {
break format!("trivially (`{}` consumed with status `{}`: every test runs)", &to.sha[..12], to.status);
}
let room = handle.room(&mimir_room::Scope::repo(&repo, Some(to.seq))).unwrap();
let before = super::Snapshot::at(&clone, &from.sha).ok();
let files = crate::test_select::commit_diff(&clone, &from.sha, &to.sha).unwrap();
let snap = super::Snapshot::at(&clone, &to.sha).unwrap();
let graph = if from.seq < to.seq { super::graph_diff(&log, &repo, from.seq, to.seq).ok() } else { Some(super::GraphDiff::default()) };
let sel = super::select(&room, &repo, &files, &snap, before.as_ref(), graph.as_ref()).unwrap();
if let Some(why) = &sel.all {
break format!("trivially (mode `all`: {why})");
}
let changed: std::collections::BTreeSet<u64> = sel.changed.keys().copied().collect();
let unselected: Vec<u64> = sel.tests.iter().copied().filter(|t| !sel.selected.contains(t)).collect();
let kinds = [EdgeKind::Calls, EdgeKind::UsesType, EdgeKind::Tests, EdgeKind::ReadsField];
let walks = room.reach_each(&unselected, &kinds, None, None).unwrap();
let dropped: Vec<String> = unselected
.iter()
.zip(&walks)
.filter(|(t, w)| w.value.reached.iter().chain([**t].iter()).any(|r| changed.contains(r)))
.map(|(t, _)| room.moniker(*t).to_string())
.collect();
v["tests_total"] = json!(sel.tests.len());
v["selected"] = json!(sel.selected.len());
v["unselected_walked"] = json!(unselected.len());
v["changed"] = json!(changed.len());
v["dropped"] = json!(dropped);
if !dropped.is_empty() {
v["zero_loss"] = json!("FAIL");
std::fs::write(Path::new(&out).join(format!("zero-loss-{}.json", &to.sha[..12])), serde_json::to_string_pretty(&v).unwrap()).unwrap();
panic!("ZERO-LOSS VIOLATION {repo} {from_spec:.12}→{to_spec:.12}: {} unselected test(s) reach a changed item: {dropped:?}", dropped.len());
}
break format!("checked ({} unselected test(s) walked, none reaches one of {} changed)", unselected.len(), changed.len());
};
v["verdict"] = json!(verdict);
v["check_ms"] = json!(t0.elapsed().as_millis() as u64);
eprintln!("{repo} {from_spec:.12}→{to_spec:.12}: zero-loss {} · {} · {} ms", v["zero_loss"], verdict, v["check_ms"]);
std::fs::write(Path::new(&out).join(format!("zero-loss-{}.json", &to.sha[..12])), serde_json::to_string_pretty(&v).unwrap()).unwrap();
}
}
/// **The measurement on a real lake** (not a check): `Test.Affected` over
/// each `from:to` pair of `$NORNIR_INCTEST_PAIRS` (comma-separated), for
/// `$NORNIR_INCTEST_REPO` in the code room under `$NORNIR_INCTEST_BUILDS`
/// (`<builds>/mimir_v2/{lake,clones}`), each answer written to
/// `$NORNIR_INCTEST_OUT/<to12>.json` with the time it took.
#[test]
#[ignore = "a measurement over a real lake: set NORNIR_INCTEST_{BUILDS,REPO,PAIRS,OUT}"]
fn measure_test_affected_on_a_real_lake() {
let env = |k: &str| std::env::var(k).unwrap_or_else(|_| panic!("${k} is not set"));
let (builds, repo, pairs, out) = (env("NORNIR_INCTEST_BUILDS"), env("NORNIR_INCTEST_REPO"), env("NORNIR_INCTEST_PAIRS"), env("NORNIR_INCTEST_OUT"));
let handle = crate::code_room::CodeRoom::new("measure", Path::new(&builds));
let reach = Reach::room_only(&handle);
std::fs::create_dir_all(&out).unwrap();
// the ledger first: every consumed commit of the repo, oldest first
{
let log = handle.log().unwrap();
let runs = log.block_on(log.runs(&repo)).unwrap();
let rows: Vec<String> = runs.iter().map(|r| format!("{} {} {}", r.seq, r.sha, r.status)).collect();
std::fs::write(Path::new(&out).join(format!("runs-{repo}.txt")), rows.join("\n")).unwrap();
}
for pair in pairs.split(',').filter(|p| !p.is_empty()) {
let (from, to) = pair.split_once(':').unwrap();
let t0 = std::time::Instant::now();
let mut v = crate::code_room::reader::wired::answer("Test.Affected", &reach, &json!({ "repo": repo, "from": from, "to": to }))
.unwrap_or_else(|r| json!({ "refused": r.note, "state": r.state.as_str() }));
v["measure_ms"] = json!(t0.elapsed().as_millis() as u64);
eprintln!(
"{repo} {from:.12}→{to:.12}: mode {} · {} of {} selected · {} skip · {} ms · {}",
v["mode"], v["selected"].as_array().map_or(0, |a| a.len()), v["tests_total"], v["skip"].as_array().map_or(0, |a| a.len()), v["measure_ms"], v["why"]
);
std::fs::write(Path::new(&out).join(format!("{}.json", &to[..to.len().min(12)])), serde_json::to_string_pretty(&v).unwrap()).unwrap();
}
}
}