src/mimir_lens/reach_inc.rs
//! **The kept reach** — `system_boundary`, `data_reach` and `reachable_vuln`
//! over a ring room (the dependency universe folded in) that ADVANCED, the
//! shape `trust::incremental` set (v3) and `clone_inc` carried on.
//!
//! The three lenses walk from OUR functions down through std and the
//! dependencies to the system calls (and, for `reachable_vuln`, from the
//! vulnerable crate's entry items) over ~8 M ring nodes. A consume moves the
//! LOCAL repos' rows only; the universe's rows move only with the room's
//! [`mimir_room::Room::universe_key`] (the `universe_manifest` snapshot and
//! the ring owners the scan read). So the lens keeps, per scope, what its last
//! walk read and answered, and on the next ask DIFFS the new room's LOCAL
//! SLICE against it:
//!
//! * the local slice ([`Slice`]) is every node a local edge row leaves
//! ([`mimir_room::Room::local_out`]) with a fingerprint of its CALLS /
//! SYSCALLS out-edges (by moniker key — ordinals are per snapshot);
//! * the local closure `Dl` is the slice, everything that reaches it, and the
//! request's own functions; every other node (`U'`) reaches no local node,
//! so its reach is a function of the universe alone and is CARRIED while
//! the universe key holds. The frontier `F` (the `U'` nodes `Dl` calls into)
//! carries its class mask from the kept walk;
//! * the classes a `Dl` node reaches (`cm`, a bit per [`Class`], the node's
//! own target classes included) are re-derived over the CONE only — the
//! changed nodes and everything in `Dl` that reaches one — as the least
//! fixpoint of `cm(v) = class(v) ∪ ⋃ cm(succ)`, the rest is carried;
//! * which targets our code reaches (`hit`) is the local part (a walk inside
//! `Dl`) plus the universe part, carried while the frontier our code
//! reaches (`FR`) is the same set, extended from the added entries when it
//! only grew, and walked again from `FR` when an entry left;
//! * everything the kept state cannot stand in for — the universe moved, the
//! targets moved, a dependency node now reaches local code — is the FULL
//! walk, and the reason is said ([`Work::path`]).
//!
//! **ZERO-LOSS**: the incremental answer must EQUAL the full recompute. The
//! original per-class walks stay in `boundary.rs` as the REFERENCE
//! ([`set_reference`]) — the oracle the tests diff the lens answers against,
//! byte for byte — and every doubt plans Full.
//!
//! The kept state is in-memory only, keyed by the lake identity, the room's
//! repos and the request's repos: a restart recomputes once, like a cold
//! cache.
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{Arc, Mutex, OnceLock};
use anyhow::Result;
use mimir_ingest::boundary::Class;
use mimir_room::Room;
use mimir_schema::EdgeKind;
pub use super::clone_inc::key_of;
use super::clone_inc::Fp;
/// The kinds the boundary walk follows (`boundary::WALK`).
const WALK: [EdgeKind; 2] = [EdgeKind::Calls, EdgeKind::Syscalls];
/// A class's bit in a class mask.
pub fn class_bit(c: Class) -> u32 {
1u32 << Class::ALL.iter().position(|x| *x == c).unwrap_or(31)
}
// ── the reference switch (tests: the original walks answer) ─────────────────
static REFERENCE: AtomicBool = AtomicBool::new(false);
/// `true` = the lenses answer with the ORIGINAL whole-graph walks (the
/// oracle), no kept state read or written. Also `NORNIR_REACH_INC=0`.
pub fn set_reference(on: bool) {
REFERENCE.store(on, Ordering::SeqCst);
}
pub fn reference() -> bool {
REFERENCE.load(Ordering::SeqCst) || std::env::var("NORNIR_REACH_INC").is_ok_and(|v| v == "0")
}
// ── the local slice of a ring room ───────────────────────────────────────────
/// The nodes local edge rows leave, with their walk out-edges — what a
/// consume can move. Shared by the lenses asking on one room state.
pub struct Slice {
pub state_key: String,
/// Sorted ordinals.
pub local: Vec<u64>,
/// Per local node: its moniker key.
pub keys: Vec<u64>,
/// Per local node: the fingerprint of its CALLS / SYSCALLS out-edges.
pub fps: Vec<u64>,
/// Per local node: its walk out-edges `(to, kind)` (0 = CALLS, 1 = SYSCALLS).
pub out: Vec<Vec<(u64, u8)>>,
}
impl Slice {
pub fn index_of(&self, o: u64) -> Option<usize> {
self.local.binary_search(&o).ok()
}
}
fn slices() -> &'static Mutex<Vec<Arc<Slice>>> {
static S: OnceLock<Mutex<Vec<Arc<Slice>>>> = OnceLock::new();
S.get_or_init(|| Mutex::new(Vec::new()))
}
/// The walk out-edges of `rows` (sorted, distinct): per row, `(to, kind)`.
pub fn out_edges(room: &Room, rows: &[u64]) -> Result<Vec<Vec<(u64, u8)>>> {
let mut out: Vec<Vec<(u64, u8)>> = vec![Vec::new(); rows.len()];
for (k, kind) in WALK.iter().enumerate() {
let pairs = room.out_pairs(*kind, rows)?;
let mut i = 0usize;
for (f, t) in pairs {
while rows[i] != f {
i += 1;
}
out[i].push((t, k as u8));
}
}
for o in &mut out {
o.sort_unstable();
}
Ok(out)
}
/// The local slice of `room` (kept for the last two room states: the three
/// lenses asking on one state compute it once).
pub fn slice(room: &Room, keys: &mut KeyCache) -> Result<Arc<Slice>> {
let sk = format!("{}|{}", room.log_identity(), room.state_key());
if let Some(s) = slices().lock().ok().and_then(|c| c.iter().find(|s| s.state_key == sk).cloned()) {
return Ok(s);
}
let local = room.local_out();
let out = out_edges(room, &local)?;
let ks: Vec<u64> = local.iter().map(|o| keys.key(room, *o)).collect();
let fps: Vec<u64> = out
.iter()
.map(|es| {
let mut v: Vec<(u8, u64)> = es.iter().map(|(t, k)| (*k, keys.key(room, *t))).collect();
v.sort_unstable();
Fp::default().add(&v).fin()
})
.collect();
let s = Arc::new(Slice { state_key: sk, local, keys: ks, fps, out });
if let Ok(mut c) = slices().lock() {
c.retain(|x| x.state_key != s.state_key);
c.push(s.clone());
while c.len() > 2 {
c.remove(0);
}
}
Ok(s)
}
/// Moniker keys by ordinal, computed once per ask.
#[derive(Default)]
pub struct KeyCache(HashMap<u64, u64>);
impl KeyCache {
pub fn key(&mut self, room: &Room, o: u64) -> u64 {
*self.0.entry(o).or_insert_with(|| key_of(room.moniker(o)))
}
}
// ── which path answered, and what the advance did ────────────────────────────
fn counters() -> &'static Mutex<HashMap<&'static str, (u64, u64, u64)>> {
static C: OnceLock<Mutex<HashMap<&'static str, (u64, u64, u64)>>> = OnceLock::new();
C.get_or_init(|| Mutex::new(HashMap::new()))
}
/// `(full, carried, advanced)` per kernel, cumulative — what a test takes
/// deltas of to prove the cheap path fired. Kernels: `boundary` (the class
/// reach `system_boundary` and `data_reach` share), `tables` (`data_reach`'s
/// table reachers), `vuln` (`reachable_vuln`'s per-finding boundary).
pub fn stats(kernel: &str) -> (u64, u64, u64) {
counters().lock().ok().and_then(|c| c.get(kernel).copied()).unwrap_or_default()
}
fn bump(kernel: &'static str, which: usize) {
if let Ok(mut c) = counters().lock() {
let e = c.entry(kernel).or_default();
match which {
0 => e.0 += 1,
1 => e.1 += 1,
_ => e.2 += 1,
}
}
}
/// What the newest walk of a kernel did — the work-reduction evidence.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Work {
pub kernel: &'static str,
/// `full`, `carried` or `advanced`, and the Full reason.
pub path: String,
/// Nodes of the local closure (`Dl`) / touchers / findings.
pub nodes: usize,
/// Nodes whose answer was re-derived (the cone / affected touchers / rows).
pub rewalked: usize,
/// Nodes that moved (changed fingerprint, new, gone).
pub changed: usize,
/// Whole-graph walks run (Full: the class walks and the closure walk).
pub graph_walks: usize,
/// Frontier entries whose reach was walked afresh.
pub new_entries: usize,
}
fn last_work_cell() -> &'static Mutex<HashMap<&'static str, Work>> {
static W: OnceLock<Mutex<HashMap<&'static str, Work>>> = OnceLock::new();
W.get_or_init(|| Mutex::new(HashMap::new()))
}
pub fn last_work(kernel: &str) -> Option<Work> {
last_work_cell().lock().ok()?.get(kernel).cloned()
}
fn record(w: Work) {
let which = match w.path.as_str() {
p if p.starts_with("full") => 0,
"carried" => 1,
_ => 2,
};
bump(w.kernel, which);
if std::env::var("NORNIR_LENS_PROFILE").is_ok_and(|v| v == "1") {
eprintln!("reach_inc: {w:?}");
}
if let Ok(mut l) = last_work_cell().lock() {
l.insert(w.kernel, w);
}
}
// ── the boundary kernel ──────────────────────────────────────────────────────
/// What the class reach of our functions is, per own function (in `own`'s
/// order) and over the targets.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Sets {
/// Per own function: the classes it reaches.
pub cm_own: Vec<u32>,
/// Per own function: the classes a CALLS out of it into a node outside
/// our functions reaches (the border).
pub border: Vec<u32>,
/// The targets our code reaches (ordinals).
pub hit: BTreeSet<u64>,
}
/// What one boundary walk kept so the next can advance.
#[derive(Debug, Clone, Default)]
pub struct KeptBoundary {
pub universe: u64,
pub targets_fp: u64,
/// Local node key → out-edge fingerprint.
pub local: HashMap<u64, u64>,
/// Keys of the local closure `Dl` (slice ∪ what reaches it ∪ own).
pub dl: HashSet<u64>,
/// Monikers of `Dl` nodes outside the slice and own (universe nodes that
/// reach local code).
pub extra: Vec<String>,
/// Key → class mask, for `Dl` and the frontier.
pub cm: HashMap<u64, u32>,
/// Keys of the frontier `F` (outside `Dl`, called from it).
pub frontier: HashSet<u64>,
/// Keys of the frontier our code reaches (`FR`).
pub fr: BTreeSet<u64>,
/// Keys of the targets the universe part reaches from `FR`.
pub hit_u: BTreeSet<u64>,
}
fn boundary_cache() -> &'static Mutex<HashMap<String, Arc<KeptBoundary>>> {
static K: OnceLock<Mutex<HashMap<String, Arc<KeptBoundary>>>> = OnceLock::new();
K.get_or_init(|| Mutex::new(HashMap::new()))
}
/// Forget every kept walk (tests: force the full path).
pub fn forget() {
if let Ok(mut c) = boundary_cache().lock() {
c.clear();
}
if let Ok(mut c) = tables_cache().lock() {
c.clear();
}
if let Ok(mut c) = vuln_cache().lock() {
c.clear();
}
if let Ok(mut c) = slices().lock() {
c.clear();
}
}
/// The scope a kept walk belongs to: the lake, the room's repos, the request's.
pub fn scope_key(room: &Room, repos: &[String]) -> String {
format!("{}|{}|{}", room.log_identity(), room.scope().repos.keys().cloned().collect::<Vec<_>>().join(","), repos.join(","))
}
/// The targets' fingerprint: which nodes are targets of which classes.
pub fn targets_fp(room: &Room, tclass: &BTreeMap<u64, u32>, names: &BTreeMap<u64, (String, bool)>, keys: &mut KeyCache) -> u64 {
let mut v: Vec<(u64, u32, Option<(String, bool)>)> = tclass.iter().map(|(o, b)| (keys.key(room, *o), *b, names.get(o).cloned())).collect();
v.sort();
Fp::default().add(&v).fin()
}
/// The local closure's graph in this room: the nodes (sorted ordinals),
/// their walk out-edges, and the reverse edges inside it.
struct Closure {
nodes: Vec<u64>,
out: Vec<Vec<(u64, u8)>>,
}
impl Closure {
fn at(&self, o: u64) -> Option<usize> {
self.nodes.binary_search(&o).ok()
}
/// Build over `nodes` (sorted, distinct), reusing the slice's edges.
fn build(room: &Room, slice: &Slice, nodes: Vec<u64>) -> Result<Closure> {
let rest: Vec<u64> = nodes.iter().copied().filter(|o| slice.index_of(*o).is_none()).collect();
let rest_out = out_edges(room, &rest)?;
let mut out = Vec::with_capacity(nodes.len());
let mut r = 0usize;
for &o in &nodes {
match slice.index_of(o) {
Some(i) => out.push(slice.out[i].clone()),
None => {
out.push(rest_out[r].clone());
r += 1;
}
}
}
Ok(Closure { nodes, out })
}
fn preds(&self) -> Vec<Vec<usize>> {
let mut p: Vec<Vec<usize>> = vec![Vec::new(); self.nodes.len()];
for (i, es) in self.out.iter().enumerate() {
for (t, _) in es {
if let Some(j) = self.at(*t) {
p[j].push(i);
}
}
}
p
}
/// Everything inside the closure reachable from `seeds` (≥ 1 hop).
fn forward(&self, seeds: &[usize]) -> Vec<bool> {
let mut seen = vec![false; self.nodes.len()];
let mut stack: Vec<usize> = Vec::new();
for &s in seeds {
for (t, _) in &self.out[s] {
if let Some(j) = self.at(*t)
&& !seen[j]
{
seen[j] = true;
stack.push(j);
}
}
}
while let Some(u) = stack.pop() {
for (t, _) in &self.out[u] {
if let Some(j) = self.at(*t)
&& !seen[j]
{
seen[j] = true;
stack.push(j);
}
}
}
seen
}
}
/// The least fixpoint of `cm(v) = class(v) ∪ ⋃ cm(succ)` over `cone` (closure
/// indexes); a successor outside the cone reads `outside` (carried / frontier).
fn fixpoint(cl: &Closure, preds: &[Vec<usize>], cone: &[bool], tclass: &BTreeMap<u64, u32>, cm: &mut [u32], outside: &dyn Fn(usize, u64) -> u32) {
let mut queue: Vec<usize> = Vec::new();
let mut queued = vec![false; cl.nodes.len()];
for i in 0..cl.nodes.len() {
if cone[i] {
cm[i] = tclass.get(&cl.nodes[i]).copied().unwrap_or(0);
queue.push(i);
queued[i] = true;
}
}
while let Some(v) = queue.pop() {
queued[v] = false;
let mut m = tclass.get(&cl.nodes[v]).copied().unwrap_or(0);
for (t, _) in &cl.out[v] {
m |= match cl.at(*t) {
Some(j) if cone[j] => cm[j],
Some(j) => outside(j, *t),
None => outside(usize::MAX, *t),
};
}
if m != cm[v] {
cm[v] = m;
for &p in &preds[v] {
if cone[p] && !queued[p] {
queued[p] = true;
queue.push(p);
}
}
}
}
}
/// The class masks of `nodes` from their own walks (≥ 1 hop) and own class.
fn walk_masks(room: &Room, nodes: &[u64], tclass: &BTreeMap<u64, u32>) -> Result<Vec<u32>> {
let walks = room.reach_each(nodes, &WALK, None, None)?;
Ok(nodes
.iter()
.zip(walks)
.map(|(o, w)| w.value.reached.iter().fold(tclass.get(o).copied().unwrap_or(0), |m, r| m | tclass.get(r).copied().unwrap_or(0)))
.collect())
}
/// The targets of `tclass` in `fr` and everything `fr` reaches.
fn targets_from(room: &Room, fr: &[u64], tclass: &BTreeMap<u64, u32>) -> Result<BTreeSet<u64>> {
if fr.is_empty() {
return Ok(BTreeSet::new());
}
let reached = room.reach(fr, &WALK, None, None)?.value.reached;
Ok(fr.iter().chain(reached.iter()).copied().filter(|o| tclass.contains_key(o)).collect())
}
/// **The class reach of our functions**: per own function the classes it
/// reaches and its border classes, and the targets reached — from the kept
/// walk of `scope` when the diff allows, else the full walk (which is kept).
/// `own` sorted; `tclass` = target ordinal → its class bits.
pub fn boundary_sets(room: &Room, scope: &str, own: &[u64], tclass: &BTreeMap<u64, u32>, tnames: &BTreeMap<u64, (String, bool)>) -> Result<Sets> {
let mut keys = KeyCache::default();
let universe = room.universe_key().unwrap_or(0);
let tfp = targets_fp(room, tclass, tnames, &mut keys);
let kept = boundary_cache().lock().ok().and_then(|c| c.get(scope).cloned());
let full_why: Option<String> = match &kept {
None => Some("no kept boundary walk for this scope".into()),
Some(k) if k.universe != universe => Some("the dependency universe moved (manifest or closure)".into()),
Some(k) if k.targets_fp != tfp => Some("the system-call targets moved".into()),
Some(_) => None,
};
let sl = slice(room, &mut keys)?;
let (sets, new_kept, work) = match (full_why, &kept) {
(None, Some(k)) => match advance_boundary(room, &sl, own, tclass, k, &mut keys)? {
Ok(w) => w,
Err(why) => full_boundary(room, &sl, own, tclass, &mut keys, universe, tfp, format!("full: {why}"))?,
},
(Some(why), _) => full_boundary(room, &sl, own, tclass, &mut keys, universe, tfp, format!("full: {why}"))?,
(None, None) => unreachable!("a plan without a kept walk is full"),
};
if let Ok(mut c) = boundary_cache().lock() {
c.insert(scope.to_string(), Arc::new(new_kept));
}
record(work);
Ok(sets)
}
type Walked = (Sets, KeptBoundary, Work);
/// The sets of the closure's own functions, given every closure node's mask.
fn own_sets(cl: &Closure, own: &[u64], cm_of: &dyn Fn(u64) -> u32) -> (Vec<u32>, Vec<u32>) {
let own_set: HashSet<u64> = own.iter().copied().collect();
let mut cms = Vec::with_capacity(own.len());
let mut border = Vec::with_capacity(own.len());
for &f in own {
cms.push(cm_of(f));
let mut b = 0u32;
if let Some(i) = cl.at(f) {
for (t, k) in &cl.out[i] {
if *k == 0 && !own_set.contains(t) {
b |= cm_of(*t);
}
}
}
border.push(b);
}
(cms, border)
}
#[allow(clippy::too_many_arguments)]
fn full_boundary(room: &Room, sl: &Slice, own: &[u64], tclass: &BTreeMap<u64, u32>, keys: &mut KeyCache, universe: u64, tfp: u64, why: String) -> Result<Walked> {
// the closure: the slice, everything that reaches it, our functions
let anc = room.dependents_by(&sl.local[..], &WALK, None, None)?.value.reached;
let mut nodes: BTreeSet<u64> = sl.local.iter().copied().collect();
nodes.extend(anc);
nodes.extend(own.iter().copied());
let cl = Closure::build(room, sl, nodes.into_iter().collect())?;
// the frontier, and its masks from one backward walk per class
let mut frontier: BTreeSet<u64> = BTreeSet::new();
for es in &cl.out {
for (t, _) in es {
if cl.at(*t).is_none() {
frontier.insert(*t);
}
}
}
let mut by_class: BTreeMap<u32, Vec<u64>> = BTreeMap::new();
for (o, bits) in tclass {
for b in 0..32 {
if bits & (1 << b) != 0 {
by_class.entry(1 << b).or_default().push(*o);
}
}
}
let mut fcm: HashMap<u64, u32> = frontier.iter().map(|o| (*o, tclass.get(o).copied().unwrap_or(0))).collect();
let mut graph_walks = 1usize;
for (bit, seeds) in &by_class {
let back = room.dependents_by(&seeds[..], &WALK, None, None)?.value.reached;
graph_walks += 1;
for o in back {
if let Some(m) = fcm.get_mut(&o) {
*m |= bit;
}
}
}
// the closure's masks: the fixpoint over all of it
let preds = cl.preds();
let cone = vec![true; cl.nodes.len()];
let mut cm = vec![0u32; cl.nodes.len()];
fixpoint(&cl, &preds, &cone, tclass, &mut cm, &|_, t| fcm.get(&t).copied().unwrap_or(0));
// what our code reaches: inside the closure, and the frontier it enters
let own_ix: Vec<usize> = own.iter().filter_map(|o| cl.at(*o)).collect();
let fwd = cl.forward(&own_ix);
let mut fr: BTreeSet<u64> = BTreeSet::new();
for (i, es) in cl.out.iter().enumerate() {
if fwd[i] || own_ix.binary_search(&i).is_ok() {
for (t, _) in es {
if cl.at(*t).is_none() {
fr.insert(*t);
}
}
}
}
let hit_u = targets_from(room, &fr.iter().copied().collect::<Vec<_>>(), tclass)?;
graph_walks += 1;
let mut hit: BTreeSet<u64> = cl.nodes.iter().zip(&fwd).filter(|(o, f)| **f && tclass.contains_key(o)).map(|(o, _)| *o).collect();
hit.extend(hit_u.iter().copied());
let cm_of = |o: u64| match cl.at(o) {
Some(i) => cm[i],
None => fcm.get(&o).copied().unwrap_or_else(|| tclass.get(&o).copied().unwrap_or(0)),
};
let (cm_own, border) = own_sets(&cl, own, &cm_of);
let kept = keep_boundary(room, sl, &cl, &cm, &fcm, &fr, &hit_u, own, keys, universe, tfp);
let work = Work { kernel: "boundary", path: why, nodes: cl.nodes.len(), rewalked: cl.nodes.len(), changed: cl.nodes.len(), graph_walks, new_entries: frontier.len() };
Ok((Sets { cm_own, border, hit }, kept, work))
}
#[allow(clippy::too_many_arguments)]
fn keep_boundary(
room: &Room,
sl: &Slice,
cl: &Closure,
cm: &[u32],
fcm: &HashMap<u64, u32>,
fr: &BTreeSet<u64>,
hit_u: &BTreeSet<u64>,
own: &[u64],
keys: &mut KeyCache,
universe: u64,
tfp: u64,
) -> KeptBoundary {
let own_set: HashSet<u64> = own.iter().copied().collect();
let mut k = KeptBoundary { universe, targets_fp: tfp, ..Default::default() };
k.local = sl.keys.iter().copied().zip(sl.fps.iter().copied()).collect();
for (i, &o) in cl.nodes.iter().enumerate() {
let key = keys.key(room, o);
k.dl.insert(key);
k.cm.insert(key, cm[i]);
if sl.index_of(o).is_none() && !own_set.contains(&o) {
k.extra.push(room.moniker(o).to_string());
}
}
for (o, m) in fcm {
let key = keys.key(room, *o);
k.frontier.insert(key);
k.cm.insert(key, *m);
}
k.fr = fr.iter().map(|o| keys.key(room, *o)).collect();
k.hit_u = hit_u.iter().map(|o| keys.key(room, *o)).collect();
k
}
/// The advance: `Err(reason)` = the kept state cannot stand in (the caller
/// runs the full walk).
fn advance_boundary(room: &Room, sl: &Slice, own: &[u64], tclass: &BTreeMap<u64, u32>, k: &KeptBoundary, keys: &mut KeyCache) -> Result<std::result::Result<Walked, String>> {
// what moved in the slice: a changed or new fingerprint
let mut changed: BTreeSet<u64> = BTreeSet::new();
let mut fresh: Vec<u64> = Vec::new();
for (i, &o) in sl.local.iter().enumerate() {
match k.local.get(&sl.keys[i]) {
Some(fp) if *fp == sl.fps[i] => {}
Some(_) => {
changed.insert(o);
}
None => {
changed.insert(o);
fresh.push(o);
}
}
}
let local_keys: HashSet<u64> = sl.keys.iter().copied().collect();
// a node that is NEW to the slice and has a caller outside the kept
// closure: a universe node now reaches local code — its kept reach is void
if !fresh.is_empty() {
let callers = room.dependents_by(&fresh[..], &WALK, Some(1), None)?.value.reached;
for c in callers {
let ck = keys.key(room, c);
if !k.dl.contains(&ck) && !local_keys.contains(&ck) {
return Ok(Err(format!("a dependency node now reaches local code ({})", room.display_path(c))));
}
}
}
// the closure now: the slice, our functions, the kept extra nodes, and
// every node of the kept closure still in the room that a closure node
// calls (a node that LEFT the slice keeps its place, and is changed)
let mut nodes: BTreeSet<u64> = sl.local.iter().copied().collect();
nodes.extend(own.iter().copied());
for m in &k.extra {
if let Some(o) = room.ordinal(m) {
nodes.insert(o);
}
}
for &f in own {
let fk = keys.key(room, f);
if !k.dl.contains(&fk) {
changed.insert(f); // a new own function
}
}
let mut cl = Closure::build(room, sl, nodes.iter().copied().collect())?;
loop {
let mut pulled: Vec<u64> = Vec::new();
for es in &cl.out {
for (t, _) in es {
if cl.at(*t).is_none() && !nodes.contains(t) && k.dl.contains(&keys.key(room, *t)) {
pulled.push(*t);
}
}
}
if pulled.is_empty() {
break;
}
for p in pulled {
nodes.insert(p);
changed.insert(p); // it left the slice: its out-edges moved
}
cl = Closure::build(room, sl, nodes.iter().copied().collect())?;
}
// a node that LEFT the slice (its local edge rows are gone) but stays in
// the closure (an own function, a kept extra node): its out-edges moved
for &o in &cl.nodes {
if sl.index_of(o).is_none() && k.local.contains_key(&keys.key(room, o)) {
changed.insert(o);
}
}
// the frontier: kept masks, or walked afresh for entries never seen
let mut fcm: HashMap<u64, u32> = HashMap::new();
let mut unknown: BTreeSet<u64> = BTreeSet::new();
for es in &cl.out {
for (t, _) in es {
if cl.at(*t).is_some() || fcm.contains_key(t) {
continue;
}
let tk = keys.key(room, *t);
match k.cm.get(&tk).filter(|_| k.frontier.contains(&tk)) {
Some(m) => {
fcm.insert(*t, *m);
}
None => {
unknown.insert(*t);
}
}
}
}
const NEW_ENTRIES_CAP: usize = 4096;
if unknown.len() > NEW_ENTRIES_CAP {
return Ok(Err(format!("{} new dependency entries: the full walk is cheaper", unknown.len())));
}
let unknown: Vec<u64> = unknown.into_iter().collect();
let mut graph_walks = 0usize;
if !unknown.is_empty() {
for (o, m) in unknown.iter().zip(walk_masks(room, &unknown, tclass)?) {
fcm.insert(*o, m);
}
graph_walks += 1;
}
// the cone: the changed nodes and everything in the closure reaching one
let preds = cl.preds();
let mut cone = vec![false; cl.nodes.len()];
let mut stack: Vec<usize> = Vec::new();
for &c in &changed {
if let Some(i) = cl.at(c)
&& !cone[i]
{
cone[i] = true;
stack.push(i);
}
}
while let Some(v) = stack.pop() {
for &p in &preds[v] {
if !cone[p] {
cone[p] = true;
stack.push(p);
}
}
}
let rewalked = cone.iter().filter(|c| **c).count();
// carried masks outside the cone (every closure node off the cone is a
// kept closure node: new ones are changed)
let mut cm: Vec<u32> = vec![0; cl.nodes.len()];
for (i, &o) in cl.nodes.iter().enumerate() {
if !cone[i] {
let ok = keys.key(room, o);
match k.cm.get(&ok).filter(|_| k.dl.contains(&ok)) {
Some(m) => cm[i] = *m,
None => return Ok(Err(format!("no kept mask for {}", room.display_path(o)))),
}
}
}
let carried = cm.clone();
fixpoint(&cl, &preds, &cone, tclass, &mut cm, &|j, t| if j == usize::MAX { fcm.get(&t).copied().unwrap_or(0) } else { carried[j] });
// what our code reaches
let own_ix: Vec<usize> = own.iter().filter_map(|o| cl.at(*o)).collect();
let fwd = cl.forward(&own_ix);
let mut fr: BTreeSet<u64> = BTreeSet::new();
for (i, es) in cl.out.iter().enumerate() {
if fwd[i] || own_ix.binary_search(&i).is_ok() {
for (t, _) in es {
if cl.at(*t).is_none() {
fr.insert(*t);
}
}
}
}
let fr_keys: BTreeSet<u64> = fr.iter().map(|o| keys.key(room, *o)).collect();
let tkey: HashMap<u64, u64> = tclass.keys().map(|o| (keys.key(room, *o), *o)).collect();
let hit_u: BTreeSet<u64> = if fr_keys == k.fr {
k.hit_u.iter().filter_map(|tk| tkey.get(tk).copied()).collect()
} else if fr_keys.is_superset(&k.fr) {
let added: Vec<u64> = fr.iter().copied().filter(|o| !k.fr.contains(&keys.key(room, *o))).collect();
graph_walks += 1;
let mut h: BTreeSet<u64> = k.hit_u.iter().filter_map(|tk| tkey.get(tk).copied()).collect();
h.extend(targets_from(room, &added, tclass)?);
h
} else {
graph_walks += 1;
targets_from(room, &fr.iter().copied().collect::<Vec<_>>(), tclass)?
};
let mut hit: BTreeSet<u64> = cl.nodes.iter().zip(&fwd).filter(|(o, f)| **f && tclass.contains_key(o)).map(|(o, _)| *o).collect();
hit.extend(hit_u.iter().copied());
let cm_of = |o: u64| match cl.at(o) {
Some(i) => cm[i],
None => fcm.get(&o).copied().unwrap_or_else(|| tclass.get(&o).copied().unwrap_or(0)),
};
let (cm_own, border) = own_sets(&cl, own, &cm_of);
let path = if changed.is_empty() && unknown.is_empty() && graph_walks == 0 { "carried" } else { "advanced" };
let kept = keep_boundary(room, sl, &cl, &cm, &fcm, &fr, &hit_u, own, keys, k.universe, k.targets_fp);
let work = Work { kernel: "boundary", path: path.into(), nodes: cl.nodes.len(), rewalked, changed: changed.len(), graph_walks, new_entries: unknown.len() };
Ok(Ok((Sets { cm_own, border, hit }, kept, work)))
}
// ── data_reach's table reachers ──────────────────────────────────────────────
/// What one table-reacher walk kept: per code node its fingerprint (CALLS
/// out-edges inside the code, readable path, public bit), and per toucher
/// its reacher keys (sorted) with the answer.
#[derive(Debug, Clone, Default)]
pub struct KeptTables {
pub fp: HashMap<u64, u64>,
/// Toucher key → (sorted reacher keys, names, public).
pub reachers: HashMap<u64, (Vec<u64>, Vec<String>, bool)>,
}
fn tables_cache() -> &'static Mutex<HashMap<String, Arc<KeptTables>>> {
static K: OnceLock<Mutex<HashMap<String, Arc<KeptTables>>>> = OnceLock::new();
K.get_or_init(|| Mutex::new(HashMap::new()))
}
/// **Who reaches each toucher** (the backward CALLS walk inside `code`, one
/// per toucher): `(names sorted + dedup, public)` per toucher — the kept
/// answer for every toucher no changed node can reach or could reach, the
/// batched walk for the rest. `api(o)` = the node is public API.
pub fn table_reachers(
room: &Room,
scope: &str,
code: &mimir_room::Mask,
touchers: &[u64],
api: &dyn Fn(u64) -> bool,
first_evidence: &mut dyn FnMut(&mimir_room::Evidence),
) -> Result<BTreeMap<u64, (Vec<String>, bool)>> {
let mut keys = KeyCache::default();
// the code's CALLS inside it, per node, with what a reacher row shows
let nodes = code.ordinals();
let calls = room.out_pairs(EdgeKind::Calls, nodes)?;
let mut fps: Vec<u64> = Vec::with_capacity(nodes.len());
let mut succ: Vec<Vec<u64>> = vec![Vec::new(); nodes.len()];
{
let mut i = 0usize;
for (f, t) in &calls {
while nodes[i] != *f {
i += 1;
}
if code.contains(*t) {
succ[i].push(*t);
}
}
}
for (i, &o) in nodes.iter().enumerate() {
let mut v: Vec<u64> = succ[i].iter().map(|t| keys.key(room, *t)).collect();
v.sort_unstable();
fps.push(Fp::default().add(&v).add(&room.display_path(o)).add(&api(o)).fin());
}
let node_keys: Vec<u64> = nodes.iter().map(|o| keys.key(room, *o)).collect();
let kept = tables_cache().lock().ok().and_then(|c| c.get(scope).cloned());
let mut affected: Vec<u64> = touchers.to_vec();
let mut path = "full: no kept table walk for this scope".to_string();
let mut changed_n = nodes.len();
if let Some(k) = &kept {
// the changed code nodes: a moved fingerprint, new, gone
let now: HashSet<u64> = node_keys.iter().copied().collect();
let mut changed_keys: HashSet<u64> = k.fp.keys().copied().filter(|x| !now.contains(x)).collect();
let mut changed: Vec<u64> = Vec::new();
for (i, &o) in nodes.iter().enumerate() {
if k.fp.get(&node_keys[i]) != Some(&fps[i]) {
changed_keys.insert(node_keys[i]);
changed.push(o);
}
}
changed_n = changed_keys.len();
// a toucher is affected when it changed, a changed node reaches it
// now, or a changed node reached it before
let fwd: HashSet<u64> = if changed.is_empty() { HashSet::new() } else { room.reach(&changed[..], &[EdgeKind::Calls], None, Some(code))?.value.reached.into_iter().collect() };
let changed_set: HashSet<u64> = changed.iter().copied().collect();
affected = touchers
.iter()
.copied()
.filter(|t| {
let tk = keys.key(room, *t);
changed_set.contains(t)
|| fwd.contains(t)
|| match k.reachers.get(&tk) {
Some((rs, _, _)) => rs.iter().any(|r| changed_keys.contains(r)),
None => true,
}
})
.collect();
path = if affected.is_empty() && changed_n == 0 { "carried".into() } else { "advanced".into() };
}
let walks = if affected.is_empty() { Vec::new() } else { room.dependents_by_each(&affected, &[EdgeKind::Calls], None, Some(code))? };
let mut out: BTreeMap<u64, (Vec<String>, bool)> = BTreeMap::new();
let mut keep = KeptTables { fp: node_keys.iter().copied().zip(fps.iter().copied()).collect(), ..Default::default() };
let mut walked: HashMap<u64, Vec<u64>> = HashMap::new();
for (&f, walk) in affected.iter().zip(walks) {
walked.insert(f, walk.value.reached);
if f == touchers[0] {
// the CALLS feed and what the room misses for it
let mut ev = walk.evidence.clone();
ev.notes.clear();
first_evidence(&ev);
}
}
if !walked.contains_key(&touchers.first().copied().unwrap_or(u64::MAX)) && !touchers.is_empty() {
// the first toucher's walk carries the evidence the full path reports
// (one hop: the evidence is the same whatever the depth)
let w = room.dependents_by_each(&touchers[..1], &[EdgeKind::Calls], Some(1), Some(code))?;
let mut ev = w[0].evidence.clone();
ev.notes.clear();
first_evidence(&ev);
}
for &f in touchers {
let fk = keys.key(room, f);
let entry = match walked.get(&f) {
Some(reached) => {
let public = api(f) || reached.iter().any(|o| api(*o));
let mut names: Vec<String> = reached.iter().map(|o| room.display_path(*o)).collect();
names.sort();
names.dedup();
let mut rk: Vec<u64> = reached.iter().map(|o| keys.key(room, *o)).collect();
rk.sort_unstable();
(rk, names, public)
}
None => kept.as_ref().and_then(|k| k.reachers.get(&fk).cloned()).expect("an unaffected toucher has a kept walk"),
};
out.insert(f, (entry.1.clone(), entry.2));
keep.reachers.insert(fk, entry);
}
if let Ok(mut c) = tables_cache().lock() {
c.insert(scope.to_string(), Arc::new(keep));
}
record(Work { kernel: "tables", path, nodes: touchers.len(), rewalked: affected.len(), changed: changed_n, graph_walks: usize::from(!affected.is_empty()), new_entries: 0 });
Ok(out)
}
// ── reachable_vuln's per-finding boundary ─────────────────────────────────────
/// What one finding's boundary walk kept: the entry keys our code calls, the
/// answer's universe half, and whether that half stayed in the universe.
#[derive(Debug, Clone, Default)]
pub struct KeptRow {
pub entries: Vec<u64>,
/// The answer without the caller prefix of its path.
pub value: serde_json::Value,
/// The moniker of the path's first node (the entry our caller calls).
pub first: Option<String>,
/// The walk from the entries met no local node: carried while the
/// universe holds.
pub pure: bool,
}
#[derive(Debug, Clone, Default)]
pub struct KeptVuln {
pub universe: u64,
/// Keys of the local slice the rows were walked over.
pub local: HashSet<u64>,
pub rows: HashMap<(String, String, String), KeptRow>,
}
fn vuln_cache() -> &'static Mutex<HashMap<String, Arc<KeptVuln>>> {
static K: OnceLock<Mutex<HashMap<String, Arc<KeptVuln>>>> = OnceLock::new();
K.get_or_init(|| Mutex::new(HashMap::new()))
}
/// The kept rows of `scope` usable on `room`: `None` = the universe moved,
/// nothing kept, or a node NEW to the local slice has a caller no local
/// edge row describes (a universe node now reaches local code). Returns the
/// kept rows and the room's local keys.
pub fn vuln_kept(room: &Room, scope: &str) -> Result<(Option<Arc<KeptVuln>>, HashSet<u64>, String)> {
let mut keys = KeyCache::default();
let sl = slice(room, &mut keys)?;
let local: HashSet<u64> = sl.keys.iter().copied().collect();
let universe = room.universe_key().unwrap_or(0);
let Some(k) = vuln_cache().lock().ok().and_then(|c| c.get(scope).cloned()) else { return Ok((None, local, "full: no kept finding walks for this scope".into())) };
if k.universe != universe {
return Ok((None, local, "full: the dependency universe moved (manifest or closure)".into()));
}
let fresh: Vec<u64> = sl.local.iter().zip(&sl.keys).filter(|(_, key)| !k.local.contains(key)).map(|(o, _)| *o).collect();
if !fresh.is_empty() {
for c in room.dependents_by(&fresh[..], &WALK, Some(1), None)?.value.reached {
if !room.node(c).repo.is_some_and(|r| r != mimir_ingest::schema::UNIVERSE_REPO) && sl.index_of(c).is_none() {
return Ok((None, local, format!("full: a dependency node now reaches local code ({})", room.display_path(c))));
}
}
}
Ok((Some(k), local, "advanced".into()))
}
pub fn vuln_keep(scope: &str, kept: KeptVuln) {
if let Ok(mut c) = vuln_cache().lock() {
c.insert(scope.to_string(), Arc::new(kept));
}
}
pub fn vuln_record(path: String, rows: usize, rewalked: usize) {
record(Work { kernel: "vuln", path, nodes: rows, rewalked, changed: rewalked, graph_walks: rewalked, new_entries: 0 });
}