src/mimir_lens/trust.rs
//! **Lens — `Mimir.Trust`: the bottleneck trust semiring over the call graph.**
//!
//! Gemini pillar 2A (`mimir-gemini-spec-2026-07-26.md`). Where [`super::villa`] and
//! [`super::data_reach`] report *where* impurity and sensitive-data touches live,
//! **Trust answers the decision** modgunn's gate wants: *given the provenance chain
//! from a known entry point to a function, do we ACT on it, HOLD it, or REFUSE it?*
//!
//! ## The semiring
//! Trust is scored in the **bottleneck (max, min) semiring** over `[0,1]`:
//! - `⊕ = max` — combine ALTERNATIVE provenance paths: the most-trustworthy route
//! wins (identity [`Trust::ZERO`] = 0.0 = no path / no trust).
//! - `⊗ = min` — extend a path by one HOP: a chain is only as strong as its
//! WEAKEST hop (identity [`Trust::ONE`] = 1.0 = full trust).
//! `min` distributes over `max`, so `(Trust, ⊕, ⊗)` is a (bounded, idempotent)
//! commutative semiring — the same algebra as widest-path / max-capacity routing,
//! and the same algebra a web-of-trust uses to fold transitive recommendations.
//!
//! ## What is scored
//! Each function is a node of the code room. Its **local trust** ([`local_trust`])
//! starts at 1.0 and is docked by the evidence about it:
//! - **impurity** (its CALLS edges into the impure items, via
//! [`super::villa::classify`]): a node that shells out (`Command::new`,
//! `exec`/`system`, `process::exit`) is untrusted,
//! - **sensitive-data touch** (`TOUCHES_TABLE` via
//! [`super::data_reach::sensitivity_of`]): a WRITE to a pii/secret/credential
//! table docks more than a read. No producer writes those edges today (P3): the
//! term is kept in the fold and the lens says it was not applied,
//! - **untested** (the test-reachable set): a node no test reaches is docked mildly.
//!
//! **Provenance** flows FORWARD from the entry surface (a node with no caller — the
//! boundary execution enters through). The walk is the room's
//! (`Room::bottleneck`, the (max, min) semiring over node weights). A function's
//! **inherited trust** is `⊕` over every entry→node path of the `⊗` (min) of the local
//! trust along it — the best provenance chain, bottlenecked by its weakest hop. A
//! function reachable only *through* an impure or sensitive hop cannot out-trust that
//! hop, however clean it is itself. A function no entry can reach scores
//! [`Trust::ZERO`] — no provenance is itself a refuse.
//!
//! The verdict maps inherited trust through [`Bounds`] to [`Decision`] (act / hold /
//! refuse) and names the **weakest hop** — the single node that caps the best route,
//! the one thing to fix to raise the verdict. The `refuse`/`hold` set is the output.
//!
//! Anti-silent-empty (the lens contract): a room without CALLS edges reports a
//! MISSING FEED via [`evidence_note`], never a false "everything is trusted". An
//! absent coverage input drops the untested penalty and says so, so a thin verdict
//! never reads as strong.
use std::cmp::Ordering;
use std::collections::BTreeMap;
use serde::{Deserialize, Serialize};
use super::data_reach::sensitivity_of;
use super::sources::{Feed, evidence_note};
use super::villa::Kind;
// ─── the semiring ────────────────────────────────────────────────────────────
/// A trust value in `[0,1]`, the carrier of the bottleneck `(max, min)` semiring.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct Trust(pub f64);
impl Trust {
/// `⊕` additive identity — no path / no trust. `a ⊕ ZERO = a`, and `ZERO ⊗ a = ZERO`.
pub const ZERO: Trust = Trust(0.0);
/// `⊗` multiplicative identity — full trust. `a ⊗ ONE = a`.
pub const ONE: Trust = Trust(1.0);
/// Clamp a raw score into the carrier set `[0,1]`.
pub fn clamp01(x: f64) -> Trust {
Trust(if x < 0.0 {
0.0
} else if x > 1.0 {
1.0
} else {
x
})
}
/// `⊕` — combine two ALTERNATIVE provenance paths: the more-trustworthy wins.
pub fn oplus(self, other: Trust) -> Trust {
if self.0 >= other.0 { self } else { other }
}
/// `⊗` — extend a path by one HOP: the chain is only as strong as its weakest hop.
pub fn otimes(self, other: Trust) -> Trust {
if self.0 <= other.0 { self } else { other }
}
}
/// Total order over the `[0,1]` carrier (NaN never enters — every constructor
/// clamps), so trust can key a max-heap and sort a ranked list.
fn cmp_trust(a: Trust, b: Trust) -> Ordering {
a.0.total_cmp(&b.0)
}
// ─── the decision ────────────────────────────────────────────────────────────
/// What a gate should DO with a function, given its inherited trust. The
/// code-provenance twin of modgunn's `Decision{Pass,Warn,Block}` (which gates
/// ARTIFACTS); here we gate whether the CALL-GRAPH provenance is strong enough to
/// act on. Declaration order is `Refuse < Hold < Act` so the *strictest* decision
/// across a set is their `min()` (the dual of modgunn's `max()` fold — there the
/// worst finding wins; here the weakest provenance wins).
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum Decision {
/// The best provenance chain is too weak — do not promote / act.
Refuse,
/// Serve, but surface the weak hop (advisory).
Hold,
/// Provenance is strong end-to-end — act freely.
Act,
}
impl Decision {
pub fn as_str(self) -> &'static str {
match self {
Decision::Refuse => "refuse",
Decision::Hold => "hold",
Decision::Act => "act",
}
}
}
/// The trust cut-points that map an inherited-trust score to a [`Decision`].
/// `act_at`/`hold_at` are the FLOORS: `t ≥ act_at ⇒ act`, `t ≥ hold_at ⇒ hold`,
/// else `refuse`. Kept as data so the CLI/gRPC can move the policy without touching
/// the fold.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct Bounds {
pub act_at: f64,
pub hold_at: f64,
}
impl Default for Bounds {
fn default() -> Self {
// A single impure/process hop (penalty 0.5 ⇒ local 0.5) lands in HOLD; a
// shell-out or sensitive-write hop (local ≤ 0.5, often ≤ 0.2) lands in REFUSE.
Bounds {
act_at: 0.66,
hold_at: 0.33,
}
}
}
impl Bounds {
/// Map an inherited-trust score to its verdict.
pub fn decide(&self, t: Trust) -> Decision {
if t.0 >= self.act_at {
Decision::Act
} else if t.0 >= self.hold_at {
Decision::Hold
} else {
Decision::Refuse
}
}
}
// ─── evidence → local trust ──────────────────────────────────────────────────
/// Trust docked from a node that constructs a process / shells out (worst wins).
fn impurity_penalty(kind: Kind) -> f64 {
match kind {
Kind::ExternalTool | Kind::Shell => 0.8,
Kind::Process => 0.5,
Kind::ProcessControl => 0.3,
}
}
/// Trust docked from a node that touches a sensitive table (write dominates read).
fn sensitivity_penalty(access: &str) -> f64 {
if access == "write" { 0.5 } else { 0.25 }
}
/// Trust docked from a node no test reaches (only applied when a coverage feed exists).
const PENALTY_UNTESTED: f64 = 0.2;
/// Trust on the room's integer weight scale (the walk compares integers, so
/// equal trusts compare equal): thousandths, plus one — no trust is still a
/// weight, so a node reached with trust 0 is told apart from one not reached.
pub const SCALE: f64 = 1000.0;
impl Trust {
/// The weight the room's bottleneck walk carries for this trust (≥ 1).
pub fn weight(self) -> u64 {
(self.0 * SCALE).round() as u64 + 1
}
/// The trust a walk weight stands for.
pub fn from_weight(w: u64) -> Trust {
Trust::clamp01(w.saturating_sub(1) as f64 / SCALE)
}
}
// ─── the reading ─────────────────────────────────────────────────────────────
/// One function's trust verdict.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TrustVerdict {
/// The function's path (the graph node).
pub func: String,
pub crate_name: String,
pub decision: Decision,
/// Inherited trust — `⊕` over provenance paths of the `⊗` (min) along each.
pub inherited_trust: f64,
/// This node's own local trust before propagation (1.0 = clean).
pub local_trust: f64,
/// The single node that caps the best provenance chain (its weakest hop) — the
/// one thing to fix to raise the verdict. Equals `func` when the node itself is
/// the weakest link.
pub weakest_hop: String,
/// Why the weakest hop is docked (impurity / sensitive-write / untested / …).
pub reason: String,
/// Fewest call hops from the entry surface.
pub depth: usize,
}
impl TrustVerdict {
pub fn explain(&self) -> String {
format!(
"{} `{}` (trust {:.2}): best provenance chain from an entry point is capped at \
`{}` — {}",
self.decision.as_str(),
self.func,
self.inherited_trust,
self.weakest_hop,
self.reason,
)
}
}
/// The whole reading.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TrustReport {
pub nodes_seen: usize,
pub entry_points: usize,
pub act: usize,
pub hold: usize,
pub refuse: usize,
/// Nodes an entry point cannot reach (inherited trust ZERO) — no provenance.
pub unreachable: usize,
pub bounds: Bounds,
/// The lowest-trust functions (refuse first, then hold) — the actionable set.
pub worst: Vec<TrustVerdict>,
pub coverage_fed: bool,
pub feeds: Vec<Feed>,
pub evidence_note: String,
pub model_attribution: String,
}
pub const ATTRIBUTION: &str = "Composition of nornir primitives: the code room's CALLS \
graph (rustc-resolved node ids, so same-named fns never merge) walked FORWARD from the \
entry surface (a node with no caller) under the bottleneck (max,min) trust semiring — \
⊕=max over alternative provenance paths, ⊗=min weakest-hop along a path. Local trust is \
docked by villa impurity, data_reach sensitivity (TOUCHES_TABLE) and test coverage. Maps \
inherited trust to act/hold/refuse and names the weakest hop that caps each verdict — \
the code-provenance decision modgunn's gate wants.";
impl TrustReport {
pub fn state_json(&self) -> serde_json::Value {
serde_json::json!({
"kind": "trust",
"nodes_seen": self.nodes_seen,
"entry_points": self.entry_points,
"act": self.act,
"hold": self.hold,
"refuse": self.refuse,
"unreachable": self.unreachable,
"bounds": self.bounds,
"coverage_fed": self.coverage_fed,
"evidence_note": self.evidence_note,
"model_attribution": self.model_attribution,
"feeds": self.feeds,
"worst": self.worst.iter().map(|v| serde_json::json!({
"func": v.func,
"crate_name": v.crate_name,
"decision": v.decision.as_str(),
"inherited_trust": v.inherited_trust,
"local_trust": v.local_trust,
"weakest_hop": v.weakest_hop,
"reason": v.reason,
"depth": v.depth,
"explain": v.explain(),
})).collect::<Vec<_>>(),
})
}
}
/// One function of the trust graph: who it is and the evidence about it.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TrustNode {
/// The function's path.
pub func: String,
pub crate_name: String,
/// The impure callees it calls, classified ([`super::villa::classify`]).
pub impure: Vec<(Kind, String)>,
/// The sensitive tables it touches: `(access, table)`.
pub access: Vec<(String, String)>,
/// A test reaches it (meaningful only when a coverage input exists).
pub covered: bool,
}
/// A node's local trust plus the reason it is docked (for the weakest-hop witness).
#[derive(Debug, Clone, PartialEq)]
pub struct Local {
pub trust: Trust,
pub reason: String,
}
impl Default for Local {
fn default() -> Self {
Local {
trust: Trust::ONE,
reason: "clean".to_string(),
}
}
}
/// **A node's own trust**, before any walk: 1.0 docked by its worst impure
/// call, then by each sensitive touch (independent risks stack), then — only
/// when a coverage input exists — by being untested.
pub fn local_trust(n: &TrustNode, coverage_fed: bool) -> Local {
let mut slot = Local::default();
// Impurity is a property of the CALLER (the fn that contains the impure call).
for (kind, callee) in &n.impure {
let docked = Trust::clamp01(1.0 - impurity_penalty(*kind));
if cmp_trust(docked, slot.trust) == Ordering::Less {
slot.trust = docked;
slot.reason = format!("impure hop — {} ({callee})", kind.label());
}
}
for (access, table) in &n.access {
let Some(sens) = sensitivity_of(table) else {
continue;
};
// Compound with any impurity penalty already docked.
let docked = Trust::clamp01(slot.trust.0 - sensitivity_penalty(access));
if cmp_trust(docked, slot.trust) == Ordering::Less {
slot.trust = docked;
slot.reason = format!("{access} to sensitive table `{table}` ({sens})");
}
}
if coverage_fed && !n.covered {
let docked = Trust::clamp01(slot.trust.0 - PENALTY_UNTESTED);
if cmp_trust(docked, slot.trust) == Ordering::Less {
slot.trust = docked;
if slot.reason == "clean" {
slot.reason = "no test reaches this node".to_string();
}
}
}
slot
}
/// One node after the walk: its local trust and what it inherits (`None` =
/// no entry point reaches it).
#[derive(Debug, Clone, PartialEq)]
pub struct Scored {
pub node: TrustNode,
pub local: Local,
pub inherited: Option<Trust>,
}
/// The counts, and which nodes are reported (indexes into the scored list,
/// strictest first).
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Ranking {
pub act: usize,
pub hold: usize,
pub refuse: usize,
pub unreachable: usize,
pub worst: Vec<usize>,
}
fn inherited_of(s: &Scored) -> Trust {
s.inherited.unwrap_or(Trust::ZERO)
}
/// **Decide every node and pick the actionable tail** — the non-`act`
/// verdicts, strictest decision first, then lowest trust, then name.
pub fn rank(scored: &[Scored], bounds: Bounds, top_n: usize) -> Ranking {
let mut r = Ranking::default();
let mut tail: Vec<(Decision, f64, &str, usize)> = Vec::new();
for (i, s) in scored.iter().enumerate() {
if s.inherited.is_none() {
// No entry point reaches this node — no provenance is a refuse.
r.unreachable += 1;
}
let t = inherited_of(s);
let decision = bounds.decide(t);
match decision {
Decision::Act => r.act += 1,
Decision::Hold => r.hold += 1,
Decision::Refuse => r.refuse += 1,
}
if decision != Decision::Act {
tail.push((decision, t.0, &s.node.func, i));
}
}
tail.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.total_cmp(&b.1)).then_with(|| a.2.cmp(b.2)).then_with(|| a.3.cmp(&b.3)));
tail.truncate(top_n);
r.worst = tail.into_iter().map(|t| t.3).collect();
r
}
/// Where a reported node's verdict comes from: the node that caps its best
/// provenance chain, and its distance from the entry surface.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Witness {
/// Index (into the scored list) of the weakest hop.
pub weakest: usize,
pub depth: usize,
}
/// **Assemble the report.** `witness` carries the weakest hop of each ranked
/// node; a ranked node without one names itself.
pub fn report(
scored: &[Scored],
ranking: &Ranking,
witness: &BTreeMap<usize, Witness>,
entry_points: usize,
coverage_fed: bool,
bounds: Bounds,
feeds: Vec<Feed>,
) -> TrustReport {
let worst: Vec<TrustVerdict> = ranking
.worst
.iter()
.map(|&i| {
let s = &scored[i];
let inherited = inherited_of(s);
let (weakest_hop, reason, depth) = match (s.inherited, witness.get(&i)) {
(None, _) => (s.node.func.clone(), "unreachable from any entry point".to_string(), 0),
(Some(_), Some(w)) => (scored[w.weakest].node.func.clone(), scored[w.weakest].local.reason.clone(), w.depth),
(Some(_), None) => (s.node.func.clone(), s.local.reason.clone(), 0),
};
TrustVerdict {
func: s.node.func.clone(),
crate_name: s.node.crate_name.clone(),
decision: bounds.decide(inherited),
inherited_trust: inherited.0,
local_trust: s.local.trust.0,
weakest_hop,
reason,
depth,
}
})
.collect();
let mut note = evidence_note(&feeds, "Trust (provenance semiring)");
if !coverage_fed {
note.push_str(
" Coverage feed absent — the untested penalty was NOT applied, so trust is an \
UPPER bound.",
);
}
TrustReport {
nodes_seen: scored.len(),
entry_points,
act: ranking.act,
hold: ranking.hold,
refuse: ranking.refuse,
unreachable: ranking.unreachable,
bounds,
worst,
coverage_fed,
evidence_note: note,
model_attribution: ATTRIBUTION.to_string(),
feeds,
}
}
// ─── the incremental walk ─────────────────────────────────────────────────────
/// **The kept walk and its delta** — the trust lens over a room that ADVANCED.
///
/// The bottleneck walk is the lens's cost on a big room. Its inputs are the
/// node set, each node's LOCAL trust, the entry surface and the CALLS edges —
/// and a lake delta rarely moves more than a few of them. So the lens keeps,
/// per scope, what its last walk read ([`Kept`]) and what it answered, and on
/// the next ask DIFFS the new room against it ([`plan`]):
///
/// * nothing the walk reads changed → the kept inherited vector IS the answer
/// ([`Plan::Carry`]);
/// * locals rose, nodes appeared, edges appeared → monotone: re-seed the
/// frontier at the changed nodes over their new values and propagate over
/// the affected region ([`Plan::Advance`], the raise pass);
/// * any local FELL → everything its node reaches may stand on it: take the
/// forward-reachable cone, invalidate it, and re-walk it from its boundary
/// (the cone pass), then the raise pass for any rises beside it;
/// * anything the kept vector cannot stand in for — the entry surface moved,
/// a node or edge is GONE, two nodes share a key so the remap is ambiguous
/// → the full walk, and the reason is said ([`Plan::Full`]).
///
/// **ZERO-LOSS**: the incremental answer must EQUAL the full recompute. The
/// full path (the room's `bottleneck`) stays in the lens as the oracle; the
/// tests diff the two on every fixture and on hundreds of random mutations,
/// and every path the diff cannot classify falls back to full.
///
/// Ordinals are per-snapshot and NOT stable across advances: everything kept
/// is keyed by MONIKER hash ([`key_of`]), and the new room's ordinals are
/// remapped through it. The kept state is in-memory only (keyed by workspace
/// and scope): a restart recomputes once, exactly like a cold cache.
pub mod incremental {
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap};
use std::hash::{Hash, Hasher};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex, OnceLock};
/// A node's stable key across room advances: its moniker, hashed. Two
/// monikers colliding makes the remap ambiguous and [`plan`] says so.
pub fn key_of(moniker: &str) -> u64 {
let mut h = std::collections::hash_map::DefaultHasher::new();
moniker.hash(&mut h);
h.finish()
}
/// What one walk kept so the next can advance instead of recompute —
/// every input the walk read and the vector it answered, by node key.
#[derive(Debug, Clone, Default)]
pub struct Kept {
/// The room state the walk was computed from (for the eye; the diff
/// itself never trusts it — equal inputs carry, whatever the state).
pub state_key: String,
/// Node key → local-trust weight.
pub local: BTreeMap<u64, u64>,
/// Node key → inherited weight. Absent = no entry reaches it.
pub inherited: BTreeMap<u64, u64>,
/// The entry surface, by node key.
pub entries: BTreeSet<u64>,
/// The CALLS edges inside the scope, by node key.
pub edges: BTreeSet<(u64, u64)>,
}
/// The new room's trust graph, in ITS ordinal space (`index` below), each
/// node named by its stable key.
#[derive(Debug, Default)]
pub struct Now {
/// index → node key.
pub keys: Vec<u64>,
/// index → local-trust weight.
pub local: Vec<u64>,
/// The entry surface, by index.
pub entries: BTreeSet<usize>,
/// Forward adjacency (callees per index).
pub forward: Vec<Vec<usize>>,
/// Backward adjacency (callers per index).
pub backward: Vec<Vec<usize>>,
/// The edge set by node key (what the NEXT walk diffs against).
pub edge_keys: BTreeSet<(u64, u64)>,
/// Two nodes share a key: the remap is ambiguous.
pub ambiguous: bool,
}
impl Now {
/// `edges` are `(from, to)` index pairs; duplicates are fine.
pub fn new(keys: Vec<u64>, local: Vec<u64>, entries: BTreeSet<usize>, edges: &[(usize, usize)]) -> Now {
let n = keys.len();
let mut seen: BTreeSet<u64> = BTreeSet::new();
let ambiguous = keys.iter().any(|k| !seen.insert(*k));
let mut forward: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut backward: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut edge_keys: BTreeSet<(u64, u64)> = BTreeSet::new();
for &(f, t) in edges {
if f < n && t < n && edge_keys.insert((keys[f], keys[t])) {
forward[f].push(t);
backward[t].push(f);
}
}
Now { keys, local, entries, forward, backward, edge_keys, ambiguous }
}
/// The [`Kept`] of this graph once `best` is its walk's answer.
pub fn keep(&self, state_key: String, best: &[Option<u64>]) -> Kept {
Kept {
state_key,
local: self.keys.iter().zip(&self.local).map(|(k, w)| (*k, *w)).collect(),
inherited: self.keys.iter().zip(best).filter_map(|(k, b)| b.map(|w| (*k, w))).collect(),
entries: self.entries.iter().map(|&i| self.keys[i]).collect(),
edges: self.edge_keys.clone(),
}
}
}
/// What the diff says the next walk must do.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Plan {
/// Nothing the walk reads changed: the kept vector IS the answer.
Carry,
/// The changes map: advance the kept vector over the affected region.
Advance {
/// Indexes whose local trust FELL (the cone pass).
decreased: Vec<usize>,
/// Indexes whose value may RISE: locals that rose, new nodes,
/// targets of new edges (the raise pass re-seeds them).
raised: Vec<usize>,
},
/// The kept vector cannot stand in: the full walk, and why.
Full(&'static str),
}
/// **Diff the new graph against the kept walk.** Every unmappable change
/// is a [`Plan::Full`] — the fallback is the correctness valve: a moved
/// entry surface reseeds everything; a node or edge that is GONE can only
/// LOWER values along paths that used it, and the kept vector cannot say
/// which; everything else is a rise (monotone) or a fall (a bounded cone).
pub fn plan(kept: &Kept, now: &Now) -> Plan {
if now.ambiguous {
return Plan::Full("two nodes share a key: the remap is ambiguous");
}
let entries_now: BTreeSet<u64> = now.entries.iter().map(|&i| now.keys[i]).collect();
if entries_now != kept.entries {
return Plan::Full("the entry surface moved");
}
let have: BTreeSet<u64> = now.keys.iter().copied().collect();
if kept.local.keys().any(|k| !have.contains(k)) {
return Plan::Full("a node is gone");
}
if kept.edges.difference(&now.edge_keys).next().is_some() {
return Plan::Full("an edge is gone");
}
let mut decreased: Vec<usize> = Vec::new();
let mut raised: BTreeSet<usize> = BTreeSet::new();
for (i, (k, w)) in now.keys.iter().zip(&now.local).enumerate() {
match kept.local.get(k) {
None => {
raised.insert(i); // a new node
}
Some(old) if w > old => {
raised.insert(i); // its local rose
}
Some(old) if w < old => decreased.push(i), // its local fell
Some(_) => {}
}
}
// a new edge can only RAISE its target
let index_of: HashMap<u64, usize> = now.keys.iter().enumerate().map(|(i, k)| (*k, i)).collect();
for (_, t) in now.edge_keys.difference(&kept.edges) {
if let Some(&i) = index_of.get(t) {
raised.insert(i);
}
}
if decreased.is_empty() && raised.is_empty() {
return Plan::Carry;
}
Plan::Advance { decreased, raised: raised.into_iter().collect() }
}
/// **Advance the kept vector**: the inherited weight per NEW index, EQUAL
/// to what the full walk computes (the widest-path fixpoint is unique; the
/// tests hold the two equal). The CONE pass first: everything
/// forward-reachable of a fallen local may stand on it, so the cone is
/// invalidated and re-walked from its boundary — an edge entering it
/// carries its source's kept value; a cone entry seeds its own local
/// (nothing else can reach an entry, so an entry is in the cone only when
/// it fell itself). The RAISE pass then re-seeds every node that may rise
/// — new nodes, risen locals, targets of new edges — from its callers'
/// values and propagates. Both are the pop-the-max greedy the reference
/// walk runs, started mid-way: values only fall along a path (⊗ = min),
/// so the largest pending candidate is final when popped.
pub fn advance(kept: &Kept, now: &Now, decreased: &[usize], raised: &[usize]) -> Vec<Option<u64>> {
let n = now.keys.len();
let mut best: Vec<Option<u64>> = carry(kept, now);
let mut heap: BinaryHeap<(u64, usize)> = BinaryHeap::new();
if !decreased.is_empty() {
// the cone: everything forward-reachable from a fallen local
let mut cone = vec![false; n];
let mut stack: Vec<usize> = Vec::new();
for &d in decreased {
if !cone[d] {
cone[d] = true;
stack.push(d);
}
}
while let Some(u) = stack.pop() {
for &v in &now.forward[u] {
if !cone[v] {
cone[v] = true;
stack.push(v);
}
}
}
// a cone over half the graph costs more to re-walk from its
// boundary than the whole graph does: run the whole walk — the
// same unique fixpoint, from the entry surface (measured: one
// fall on a dense random 200k graph was 1.6 s coned, 0.6 s whole)
if cone.iter().filter(|c| **c).count() * 2 > n {
let mut whole: Vec<Option<u64>> = vec![None; n];
for &e in &now.entries {
heap.push((now.local[e], e));
}
relax(&mut heap, &mut whole, now);
return whole;
}
for (i, in_cone) in cone.iter().enumerate() {
if *in_cone {
best[i] = None;
}
}
for (i, in_cone) in cone.iter().enumerate() {
if !in_cone {
continue;
}
if now.entries.contains(&i) {
heap.push((now.local[i], i));
}
for &u in &now.backward[i] {
if !cone[u] {
if let Some(b) = best[u] {
heap.push((b.min(now.local[i]), i));
}
}
}
}
// the cone is forward-closed: this relaxation cannot leave it
relax(&mut heap, &mut best, now);
}
// the raise pass: re-seed every risen node from its callers (and from
// itself, when it is an entry), then propagate
for &v in raised {
let mut cand = now.entries.contains(&v).then_some(now.local[v]);
for &u in &now.backward[v] {
if let Some(b) = best[u] {
let c = b.min(now.local[v]);
if cand.is_none_or(|x| c > x) {
cand = Some(c);
}
}
}
if let Some(c) = cand {
if best[v].is_none_or(|b| c > b) {
heap.push((c, v));
}
}
}
relax(&mut heap, &mut best, now);
best
}
/// Pop-the-max widest-path relaxation from whatever candidates are on the
/// heap (lazy: a stale candidate is skipped on pop).
fn relax(heap: &mut BinaryHeap<(u64, usize)>, best: &mut [Option<u64>], now: &Now) {
while let Some((w, u)) = heap.pop() {
if best[u].is_some_and(|b| b >= w) {
continue;
}
best[u] = Some(w);
for &v in &now.forward[u] {
let c = w.min(now.local[v]);
if best[v].is_none_or(|b| c > b) {
heap.push((c, v));
}
}
}
}
/// The kept vector mapped into the new ordinal space (the Carry answer).
pub fn carry(kept: &Kept, now: &Now) -> Vec<Option<u64>> {
now.keys.iter().map(|k| kept.inherited.get(k).copied()).collect()
}
// ── the kept walks of this process, by workspace + scope ────────────────
fn cache() -> &'static Mutex<HashMap<String, Arc<Kept>>> {
static KEPT: OnceLock<Mutex<HashMap<String, Arc<Kept>>>> = OnceLock::new();
KEPT.get_or_init(|| Mutex::new(HashMap::new()))
}
/// The kept walk of `scope_key`, if any.
pub fn kept_for(scope_key: &str) -> Option<Arc<Kept>> {
cache().lock().ok()?.get(scope_key).cloned()
}
/// Keep `kept` as the walk of `scope_key` (replacing any older one).
pub fn keep(scope_key: String, kept: Kept) {
if let Ok(mut c) = cache().lock() {
c.insert(scope_key, Arc::new(kept));
}
}
/// Forget every kept walk (tests: force the full path).
pub fn forget() {
if let Ok(mut c) = cache().lock() {
c.clear();
}
}
static FULL: AtomicU64 = AtomicU64::new(0);
static CARRIED: AtomicU64 = AtomicU64::new(0);
static ADVANCED: AtomicU64 = AtomicU64::new(0);
/// Which path answered, cumulative: `(full, carried, advanced)` — what a
/// test takes deltas of to prove the cheap path actually fired.
pub fn stats() -> (u64, u64, u64) {
(FULL.load(Ordering::Relaxed), CARRIED.load(Ordering::Relaxed), ADVANCED.load(Ordering::Relaxed))
}
pub fn count_full() {
FULL.fetch_add(1, Ordering::Relaxed);
}
pub fn count_carried() {
CARRIED.fetch_add(1, Ordering::Relaxed);
}
pub fn count_advanced() {
ADVANCED.fetch_add(1, Ordering::Relaxed);
}
}
/// The reference walk — widest-path (best bottleneck) Dijkstra from the entry
/// surface: `min` is monotone, so pop-the-max greedy settles each node at its
/// true ⊕/⊗ value. The production walk is the room's `bottleneck`; the tests
/// drive the fold with this one, and the room-fixture test holds the two equal.
#[cfg(test)]
pub(crate) mod reference {
use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap};
use super::{Trust, Witness, cmp_trust};
struct HeapItem {
trust: Trust,
node: usize,
}
impl PartialEq for HeapItem {
fn eq(&self, o: &Self) -> bool {
self.trust.0 == o.trust.0 && self.node == o.node
}
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
fn cmp(&self, o: &Self) -> Ordering {
cmp_trust(self.trust, o.trust).then_with(|| o.node.cmp(&self.node))
}
}
impl PartialOrd for HeapItem {
fn partial_cmp(&self, o: &Self) -> Option<Ordering> {
Some(self.cmp(o))
}
}
/// `(inherited trust, witness)` per reached node. `local[i]` is node `i`'s
/// own trust; `forward` its callees; the entry surface is every node with
/// no caller (every node, when the graph has none).
pub fn widest_paths(local: &[Trust], forward: &BTreeMap<usize, BTreeSet<usize>>) -> (BTreeMap<usize, (Trust, Witness)>, usize) {
let has_caller: BTreeSet<usize> = forward.iter().flat_map(|(f, ts)| ts.iter().filter(move |t| *t != f)).copied().collect();
let mut entries: Vec<usize> = (0..local.len()).filter(|n| !has_caller.contains(n)).collect();
if entries.is_empty() {
entries = (0..local.len()).collect();
}
let mut best: BTreeMap<usize, (Trust, Witness)> = BTreeMap::new();
let mut heap: BinaryHeap<HeapItem> = BinaryHeap::new();
for &e in &entries {
best.insert(e, (local[e], Witness { weakest: e, depth: 0 }));
heap.push(HeapItem { trust: local[e], node: e });
}
let mut settled: BTreeSet<usize> = BTreeSet::new();
while let Some(HeapItem { trust, node }) = heap.pop() {
if settled.contains(&node) || best.get(&node).is_none_or(|b| b.0.0 != trust.0) {
continue;
}
settled.insert(node);
let (cur, cur_w) = best[&node];
for &c in forward.get(&node).into_iter().flatten() {
if settled.contains(&c) {
continue;
}
// ⊗: extend the caller's chain by this hop, capped at the callee's local.
let cand = cur.otimes(local[c]);
if best.get(&c).is_none_or(|b| cmp_trust(cand, b.0) == Ordering::Greater) {
// The weakest hop is whichever of (chain-so-far, this node) is lower.
let weakest = if cmp_trust(local[c], cur) != Ordering::Greater { c } else { cur_w.weakest };
best.insert(c, (cand, Witness { weakest, depth: cur_w.depth + 1 }));
heap.push(HeapItem { trust: cand, node: c });
}
}
}
(best, entries.len())
}
}
#[cfg(test)]
mod tests {
use std::collections::BTreeSet;
use super::*;
/// A graph by name: `impure[name]` = the impure callees it calls,
/// `access[name]` = its table touches, `covered` = the test-reached names
/// (`None` = no coverage input), `calls` = the call edges.
#[derive(Default)]
struct G<'a> {
nodes: Vec<&'a str>,
calls: Vec<(&'a str, &'a str)>,
impure: Vec<(&'a str, &'a str, &'a str)>,
access: Vec<(&'a str, &'a str, &'a str)>,
covered: Option<Vec<&'a str>>,
}
fn run(g: &G<'_>, bounds: Bounds) -> TrustReport {
let coverage_fed = g.covered.is_some();
let idx = |name: &str| g.nodes.iter().position(|n| *n == name).unwrap_or_else(|| panic!("node `{name}` is not declared"));
let nodes: Vec<TrustNode> = g
.nodes
.iter()
.map(|name| TrustNode {
func: name.to_string(),
crate_name: name.split("::").next().unwrap_or("").to_string(),
impure: g.impure.iter().filter(|(f, _, _)| f == name).map(|(_, callee, kind)| (crate::mimir_lens::villa::classify(callee, kind).expect("an impure callee"), callee.to_string())).collect(),
access: g.access.iter().filter(|(f, _, _)| f == name).map(|(_, table, access)| (access.to_string(), table.to_string())).collect(),
covered: g.covered.as_ref().is_some_and(|c| c.contains(name)),
})
.collect();
let locals: Vec<Local> = nodes.iter().map(|n| local_trust(n, coverage_fed)).collect();
let mut forward: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new();
for (f, t) in &g.calls {
forward.entry(idx(f)).or_default().insert(idx(t));
}
let (walked, entries) = reference::widest_paths(&locals.iter().map(|l| l.trust).collect::<Vec<_>>(), &forward);
let scored: Vec<Scored> = nodes.into_iter().zip(locals).enumerate().map(|(i, (node, local))| Scored { node, local, inherited: walked.get(&i).map(|w| w.0) }).collect();
let ranking = rank(&scored, bounds, 50);
let witness: BTreeMap<usize, Witness> = walked.iter().map(|(i, w)| (*i, w.1)).collect();
let feeds = vec![Feed { table: "code_edges:CALLS".into(), rows: g.calls.len(), root: "code room".into(), missing: g.calls.is_empty() }];
report(&scored, &ranking, &witness, entries, coverage_fed, bounds, feeds)
}
fn verdict<'a>(r: &'a TrustReport, func: &str) -> &'a TrustVerdict {
r.worst.iter().find(|v| v.func == func).unwrap_or_else(|| panic!("`{func}` is not in the refuse/hold tail: {:?}", r.worst))
}
#[test]
fn semiring_identities_and_annihilator() {
let a = Trust(0.7);
// ⊕ identity is ZERO, ⊗ identity is ONE.
assert_eq!(a.oplus(Trust::ZERO).0, 0.7);
assert_eq!(a.otimes(Trust::ONE).0, 0.7);
// ZERO annihilates under ⊗ (min): the weakest hop of a no-trust link is no trust.
assert_eq!(a.otimes(Trust::ZERO).0, 0.0);
// ⊕ with ONE saturates (best possible path), ⊗ with ZERO bottoms out.
assert_eq!(a.oplus(Trust::ONE).0, 1.0);
}
#[test]
fn min_distributes_over_max() {
// a ⊗ (b ⊕ c) == (a ⊗ b) ⊕ (a ⊗ c) — the law that makes (max,min) a semiring.
// If ⊕/⊗ were swapped (min over paths, max over hops) this identity still holds
// BUT the identities test above pins the orientation, and the decision test
// below pins the semantics — together they are red-when-reverted.
for &(a, b, c) in &[(0.6, 0.9, 0.3), (0.2, 0.5, 0.8), (1.0, 0.0, 0.4)] {
let (a, b, c) = (Trust(a), Trust(b), Trust(c));
let lhs = a.otimes(b.oplus(c));
let rhs = a.otimes(b).oplus(a.otimes(c));
assert!((lhs.0 - rhs.0).abs() < 1e-12, "{lhs:?} != {rhs:?}");
}
}
#[test]
fn every_local_trust_survives_the_integer_weight_scale() {
for t in [1.0, 0.8, 0.75, 0.7, 0.5, 0.3, 0.25, 0.2, 0.0] {
assert!((Trust::from_weight(Trust(t).weight()).0 - t).abs() < 1e-9, "{t}");
}
assert!(Trust(0.2).weight() < Trust(0.25).weight());
assert!(Trust::ZERO.weight() > 0, "no trust is still a weight: reached-with-0 is not unreached");
}
/// **Red-when-reverted decision test.** A pure leaf reachable through a raw
/// shell-out wrapper cannot out-trust the wrapper: the best provenance chain is
/// bottlenecked at the weakest hop (⊗=min), and the verdict is REFUSE. Swap ⊗ to
/// `max` and the leaf inherits full trust → ACT, flipping this assertion; reverse
/// the bound comparison and refuse↔act flip too.
#[test]
fn a_pure_leaf_behind_a_shellout_hop_is_refused_not_acted() {
// main → spawn_shell (raw libc::system escape) → format_arg (pure).
let g = G {
nodes: vec!["app::main", "app::spawn_shell", "app::format_arg"],
calls: vec![("app::main", "app::spawn_shell"), ("app::spawn_shell", "app::format_arg")],
impure: vec![("app::spawn_shell", "libc::system", "ffi")],
..Default::default()
};
let r = run(&g, Bounds::default());
// `main` is the sole entry point (nothing calls it).
assert_eq!(r.entry_points, 1);
// spawn_shell makes a raw shell escape ⇒ local trust 0.2 ⇒ refuse.
let shell = verdict(&r, "app::spawn_shell");
assert_eq!(shell.decision, Decision::Refuse, "{}", shell.explain());
assert!((shell.local_trust - 0.2).abs() < 1e-9, "shell penalty 0.8 ⇒ local 0.2");
// format_arg is PURE (local 1.0) but only reachable THROUGH spawn_shell, so its
// inherited trust is min(chain) = 0.2 and its weakest hop is spawn_shell.
let fmt = verdict(&r, "app::format_arg");
assert!((fmt.local_trust - 1.0).abs() < 1e-9, "the leaf itself is pure");
assert!((fmt.inherited_trust - 0.2).abs() < 1e-9, "bottlenecked at the shell-out hop, not its own 1.0: {}", fmt.explain());
assert_eq!(fmt.weakest_hop, "app::spawn_shell", "names the hop to fix, as an identity");
assert!(fmt.reason.contains("libc::system"), "{}", fmt.reason);
assert_eq!(fmt.decision, Decision::Refuse, "a pure leaf is refused for its provenance");
assert_eq!(fmt.depth, 2);
}
/// A bare `Command::new` (binary unknown) is the softer `Process` impurity —
/// penalty 0.5 ⇒ local 0.5 ⇒ HOLD, not refuse. Policy parity with villa severity
/// (Process=medium, Shell/ExternalTool=high).
#[test]
fn a_bare_command_new_is_hold_not_refuse() {
let g = G {
nodes: vec!["app::main", "app::run"],
calls: vec![("app::main", "app::run")],
impure: vec![("app::run", "std::process::Command::new", "method")],
..Default::default()
};
let r = run(&g, Bounds::default());
let run = verdict(&r, "app::run");
assert_eq!(run.decision, Decision::Hold, "{}", run.explain());
assert!((run.local_trust - 0.5).abs() < 1e-9, "process penalty 0.5 ⇒ local 0.5");
}
/// `⊕ = max` picks the BEST provenance path: a node reachable by a clean route AND
/// a dirty route inherits the clean route's trust.
#[test]
fn max_over_paths_takes_the_cleaner_route() {
// clean_entry → target (pure). dirty_entry → shell → target.
let g = G {
nodes: vec!["app::clean_entry", "app::dirty_entry", "app::shell", "app::target"],
calls: vec![("app::clean_entry", "app::target"), ("app::dirty_entry", "app::shell"), ("app::shell", "app::target")],
impure: vec![("app::shell", "std::process::Command::new", "method")],
..Default::default()
};
let r = run(&g, Bounds::default());
// target is pure and has a clean provenance chain (clean_entry→target), so ⊕
// takes 1.0 over the 0.5 dirty route ⇒ ACT ⇒ not in the worst (non-act) tail.
assert!(!r.worst.iter().any(|v| v.func == "app::target"), "target has a clean route ⇒ act ⇒ absent from the refuse/hold tail");
assert!(r.act >= 1);
}
/// Nodes are ids, not names: an impure `main` must NOT taint a `helper` reached
/// only through ANOTHER `main` — the two share a name and nothing else.
#[test]
fn same_named_fns_are_different_nodes() {
let g = G {
nodes: vec!["a::main", "a::helper", "b::main", "b::helper"],
calls: vec![("a::main", "a::helper"), ("b::main", "b::helper")],
impure: vec![("a::main", "libc::system", "ffi")],
..Default::default()
};
let r = run(&g, Bounds::default());
assert_eq!(verdict(&r, "a::helper").weakest_hop, "a::main");
assert!(!r.worst.iter().any(|v| v.func == "b::helper" || v.func == "b::main"), "{:?}", r.worst);
assert_eq!((r.refuse, r.act), (2, 2));
}
#[test]
fn a_sensitive_write_is_less_trusted_than_a_read() {
// act_at raised so the 0.75 read lands in HOLD (in the ranked tail) beside the
// 0.5 write — otherwise a read at 0.75 is `act` and filtered out.
let bounds = Bounds { act_at: 0.9, hold_at: 0.3 };
let g = G {
nodes: vec!["app::main", "app::write_secret", "app::read_secret"],
calls: vec![("app::main", "app::write_secret"), ("app::main", "app::read_secret")],
access: vec![("app::write_secret", "vault_tokens", "write"), ("app::read_secret", "vault_tokens", "read")],
..Default::default()
};
let r = run(&g, bounds);
let (w, rd) = (verdict(&r, "app::write_secret"), verdict(&r, "app::read_secret"));
assert!((w.local_trust - 0.5).abs() < 1e-9, "write penalty 0.5");
assert!((rd.local_trust - 0.75).abs() < 1e-9, "read penalty 0.25");
assert!(w.inherited_trust < rd.inherited_trust, "a write is less trusted than a read");
assert!(w.reason.contains("vault_tokens"), "{}", w.reason);
}
/// With a coverage input, a node no test reaches is docked 0.2 — and only then.
#[test]
fn an_untested_node_is_docked_only_when_coverage_exists() {
let mut g = G { nodes: vec!["app::main", "app::helper"], calls: vec![("app::main", "app::helper")], covered: Some(vec!["app::main"]), ..Default::default() };
let r = run(&g, Bounds { act_at: 0.9, hold_at: 0.3 });
let h = verdict(&r, "app::helper");
assert!((h.local_trust - 0.8).abs() < 1e-9);
assert_eq!(h.reason, "no test reaches this node");
assert!(r.coverage_fed);
g.covered = None;
assert!(run(&g, Bounds { act_at: 0.9, hold_at: 0.3 }).worst.is_empty());
}
/// A node no entry point reaches has no provenance: refuse, and it says why.
#[test]
fn a_node_no_entry_reaches_is_refused_as_unreachable() {
let node = |f: &str| TrustNode { func: f.into(), ..Default::default() };
let scored = vec![
Scored { node: node("app::main"), local: Local::default(), inherited: Some(Trust::ONE) },
Scored { node: node("app::island"), local: Local::default(), inherited: None },
];
let ranking = rank(&scored, Bounds::default(), 50);
assert_eq!((ranking.unreachable, ranking.refuse, ranking.act), (1, 1, 1));
let r = report(&scored, &ranking, &BTreeMap::new(), 1, false, Bounds::default(), vec![]);
assert_eq!(r.worst[0].reason, "unreachable from any entry point");
assert_eq!(r.worst[0].inherited_trust, 0.0);
}
/// Anti-silent-empty: a room without CALLS reads as a MISSING FEED, not "all trusted".
#[test]
fn an_empty_graph_reads_as_missing_not_all_trusted() {
let r = run(&G::default(), Bounds::default());
assert_eq!(r.nodes_seen, 0);
assert!(r.evidence_note.contains("MISSING FEEDS"), "{}", r.evidence_note);
assert!(r.evidence_note.contains("code_edges:CALLS"), "names the missing input: {}", r.evidence_note);
}
// ── the incremental walk ──────────────────────────────────────────────
/// A plain relaxation to the fixpoint in weight space — the oracle the
/// incremental walk is diffed against (`ops.rs`'s random-graph style).
fn full_weights(n: usize, w: &[u64], entries: &BTreeSet<usize>, edges: &std::collections::BTreeSet<(usize, usize)>) -> Vec<Option<u64>> {
let mut best: Vec<Option<u64>> = vec![None; n];
for &e in entries {
best[e] = Some(w[e]);
}
loop {
let mut moved = false;
for &(f, t) in edges {
if let Some(b) = best[f] {
let c = b.min(w[t]);
if best[t].is_none_or(|old| c > old) {
best[t] = Some(c);
moved = true;
}
}
}
if !moved {
break;
}
}
best
}
/// The entry surface the lens computes: no caller, or (fully cyclic) every node.
fn entries_of(n: usize, edges: &std::collections::BTreeSet<(usize, usize)>) -> BTreeSet<usize> {
let has_caller: BTreeSet<usize> = edges.iter().filter(|(f, t)| f != t).map(|(_, t)| *t).collect();
let e: BTreeSet<usize> = (0..n).filter(|i| !has_caller.contains(i)).collect();
if e.is_empty() { (0..n).collect() } else { e }
}
/// The diff names what moved: carry on nothing, advance on mapped rises /
/// falls / additions, full (with the reason) on everything the kept vector
/// cannot stand in for.
#[test]
fn the_plan_classifies_the_delta() {
use super::incremental as inc;
let edges: std::collections::BTreeSet<(usize, usize)> = [(0, 1), (1, 2)].into();
let build = |keys: Vec<u64>, w: Vec<u64>, edges: &std::collections::BTreeSet<(usize, usize)>| {
inc::Now::new(keys.clone(), w, entries_of(keys.len(), edges), &edges.iter().copied().collect::<Vec<_>>())
};
let now = build(vec![10, 11, 12], vec![9, 5, 7], &edges);
let best = full_weights(3, &now.local, &now.entries, &edges);
assert_eq!(best, vec![Some(9), Some(5), Some(5)]);
let kept = now.keep("s1".into(), &best);
// nothing moved → carry; and the carried vector is the kept one
assert_eq!(inc::plan(&kept, &now), inc::Plan::Carry);
assert_eq!(inc::carry(&kept, &now), best);
// a local rises → the raise pass
assert_eq!(inc::plan(&kept, &build(vec![10, 11, 12], vec![9, 8, 7], &edges)), inc::Plan::Advance { decreased: vec![], raised: vec![1] });
// a local falls → the cone pass
assert_eq!(inc::plan(&kept, &build(vec![10, 11, 12], vec![9, 3, 7], &edges)), inc::Plan::Advance { decreased: vec![1], raised: vec![] });
// a node appears, called from the scope → raised (and only it)
let mut plus: std::collections::BTreeSet<(usize, usize)> = edges.clone();
plus.insert((2, 3));
assert_eq!(inc::plan(&kept, &build(vec![10, 11, 12, 13], vec![9, 5, 7, 6], &plus)), inc::Plan::Advance { decreased: vec![], raised: vec![3] });
// a new edge between kept nodes → its target is raised
let mut cross: std::collections::BTreeSet<(usize, usize)> = edges.clone();
cross.insert((0, 2));
assert_eq!(inc::plan(&kept, &build(vec![10, 11, 12], vec![9, 5, 7], &cross)), inc::Plan::Advance { decreased: vec![], raised: vec![2] });
// a node is GONE → full
let two: std::collections::BTreeSet<(usize, usize)> = [(0, 1)].into();
assert!(matches!(inc::plan(&kept, &build(vec![10, 11], vec![9, 5], &two)), inc::Plan::Full(_)));
// an edge is GONE → full
let cut: std::collections::BTreeSet<(usize, usize)> = [(0, 1)].into();
assert!(matches!(inc::plan(&kept, &build(vec![10, 11, 12], vec![9, 5, 7], &cut)), inc::Plan::Full(_)));
// the entry surface moved (a new node with no caller) → full
let mut hang: std::collections::BTreeSet<(usize, usize)> = edges.clone();
hang.insert((3, 1));
assert!(matches!(inc::plan(&kept, &build(vec![10, 11, 12, 13], vec![9, 5, 7, 6], &hang)), inc::Plan::Full(_)));
// two nodes share a key → the remap is ambiguous, said on the graph itself
assert!(build(vec![10, 11, 11], vec![9, 5, 7], &edges).ambiguous);
}
/// ZERO-LOSS on random graphs: hundreds of random mutations — locals up
/// and down, nodes and edges added and removed — each diffed, advanced
/// where the plan maps it, and EVERY answer equal to the plain full
/// relaxation. The carry, advance and full paths must all fire.
#[test]
fn incremental_equals_the_full_walk_over_hundreds_of_random_mutations() {
use super::incremental as inc;
let mut x = 0x9e37_79b9_7f4a_7c15u64;
let mut rnd = move |m: usize| {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
(x % m.max(1) as u64) as usize
};
// nodes: (stable key, local weight); edges by INDEX into `nodes`
let mut nodes: Vec<(u64, u64)> = (0..12u64).map(|i| (i, 1)).collect();
for n in nodes.iter_mut() {
n.1 = 1 + rnd(1001) as u64;
}
let mut next_key = 12u64;
let mut edges: std::collections::BTreeSet<(usize, usize)> = std::collections::BTreeSet::new();
for _ in 0..24 {
edges.insert((rnd(12), rnd(12)));
}
let build = |nodes: &[(u64, u64)], edges: &std::collections::BTreeSet<(usize, usize)>| {
inc::Now::new(
nodes.iter().map(|n| n.0).collect(),
nodes.iter().map(|n| n.1).collect(),
entries_of(nodes.len(), edges),
&edges.iter().copied().collect::<Vec<_>>(),
)
};
let now = build(&nodes, &edges);
let mut kept = now.keep("0".into(), &full_weights(nodes.len(), &now.local, &now.entries, &edges));
let (mut carried, mut advanced, mut full) = (0u32, 0u32, 0u32);
for round in 0..400 {
match rnd(8) {
0 | 1 => {
// a local moves, either way
let i = rnd(nodes.len());
nodes[i].1 = 1 + rnd(1001) as u64;
}
2 => {
// a new node, called by an existing one (off the entry surface)
let caller = rnd(nodes.len());
nodes.push((next_key, 1 + rnd(1001) as u64));
next_key += 1;
edges.insert((caller, nodes.len() - 1));
if rnd(2) == 0 {
edges.insert((nodes.len() - 1, rnd(nodes.len())));
}
}
3 => {
// a new edge
edges.insert((rnd(nodes.len()), rnd(nodes.len())));
}
4 => {
// an edge goes
if !edges.is_empty() {
let e = *edges.iter().nth(rnd(edges.len())).unwrap();
edges.remove(&e);
}
}
5 => {
// a node goes, with its edges; indexes shift down past it
if nodes.len() > 3 {
let gone = rnd(nodes.len());
nodes.remove(gone);
edges = edges
.iter()
.filter(|(f, t)| *f != gone && *t != gone)
.map(|(f, t)| (*f - usize::from(*f > gone), *t - usize::from(*t > gone)))
.collect();
}
}
_ => {} // nothing moves: the carry case
}
let now = build(&nodes, &edges);
let want = full_weights(nodes.len(), &now.local, &now.entries, &edges);
assert!(!now.ambiguous, "round {round}");
let got = match inc::plan(&kept, &now) {
inc::Plan::Carry => {
carried += 1;
inc::carry(&kept, &now)
}
inc::Plan::Advance { decreased, raised } => {
advanced += 1;
inc::advance(&kept, &now, &decreased, &raised)
}
inc::Plan::Full(_) => {
full += 1;
want.clone()
}
};
assert_eq!(got, want, "round {round}: {} node(s), edges {edges:?}", nodes.len());
kept = now.keep(format!("{round}"), &got);
}
assert!(carried > 0 && advanced > 0 && full > 0, "every path fired: carried {carried}, advanced {advanced}, full {full}");
}
/// Numbers for the record, not an assertion of speed (`--ignored` to run;
/// debug profile): the pure walk at scale — the from-scratch heap walk
/// (what the full path costs), the carry, and the advance after one fall
/// and one rise. Also ZERO-LOSS at scale: every result equals the plain
/// relaxation oracle.
#[test]
#[ignore = "measurement, run by hand: prints full / carry / advance ms at 200k nodes"]
fn incremental_measured_at_scale() {
use std::time::Instant;
use super::incremental as inc;
let n: usize = 200_000;
let mut x = 0xabcd_ef12_3456_789fu64;
let mut rnd = move |m: usize| {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
(x % m.max(1) as u64) as usize
};
let mut nodes: Vec<(u64, u64)> = (0..n as u64).map(|i| (i, 1)).collect();
for nd in nodes.iter_mut() {
nd.1 = 1 + rnd(1001) as u64;
}
let mut edges: std::collections::BTreeSet<(usize, usize)> = std::collections::BTreeSet::new();
for u in 0..n {
for _ in 0..4 {
edges.insert((u, rnd(n)));
}
}
let build = |nodes: &[(u64, u64)], edges: &std::collections::BTreeSet<(usize, usize)>| {
inc::Now::new(
nodes.iter().map(|nd| nd.0).collect(),
nodes.iter().map(|nd| nd.1).collect(),
entries_of(nodes.len(), edges),
&edges.iter().copied().collect::<Vec<_>>(),
)
};
let now = build(&nodes, &edges);
let t = Instant::now();
let want = full_weights(n, &now.local, &now.entries, &edges);
let oracle_ms = t.elapsed().as_millis();
// the full walk from scratch: an empty kept vector with the right
// entry surface plans every node raised — the heap walk end to end
let empty = inc::Kept { entries: now.entries.iter().map(|&i| now.keys[i]).collect(), ..Default::default() };
let all: Vec<usize> = (0..n).collect();
let t = Instant::now();
let full = inc::advance(&empty, &now, &[], &all);
let full_ms = t.elapsed().as_millis();
assert_eq!(full, want, "the from-scratch heap walk IS the oracle");
let kept = now.keep("scale".into(), &full);
// carry: nothing moved
let now2 = build(&nodes, &edges);
let t = Instant::now();
assert_eq!(inc::plan(&kept, &now2), inc::Plan::Carry);
let carried = inc::carry(&kept, &now2);
let carry_ms = t.elapsed().as_millis();
assert_eq!(carried, want);
// one local FALLS (the cone pass)
let mut fell = nodes.clone();
fell[n / 2].1 = 1;
let now3 = build(&fell, &edges);
let t = Instant::now();
let inc::Plan::Advance { decreased, raised } = inc::plan(&kept, &now3) else { panic!("a fall advances") };
let got = inc::advance(&kept, &now3, &decreased, &raised);
let fall_ms = t.elapsed().as_millis();
assert_eq!(got, full_weights(n, &now3.local, &now3.entries, &edges));
// one local RISES (the raise pass)
let mut rose = nodes.clone();
rose[n / 3].1 = 1001;
let now4 = build(&rose, &edges);
let t = Instant::now();
let inc::Plan::Advance { decreased, raised } = inc::plan(&kept, &now4) else { panic!("a rise advances") };
let got = inc::advance(&kept, &now4, &decreased, &raised);
let rise_ms = t.elapsed().as_millis();
assert_eq!(got, full_weights(n, &now4.local, &now4.entries, &edges));
eprintln!(
"trust incremental at {n} nodes / {} edges (debug profile): oracle relaxation {oracle_ms} ms · full heap walk {full_ms} ms · carry {carry_ms} ms · one fall advanced {fall_ms} ms · one rise advanced {rise_ms} ms",
edges.len()
);
}
/// An absent coverage feed skips the untested penalty and says the score is an
/// UPPER bound — a thin verdict never reads as strong.
#[test]
fn absent_coverage_is_flagged_as_an_upper_bound() {
let g = G { nodes: vec!["app::main", "app::helper"], calls: vec![("app::main", "app::helper")], ..Default::default() };
let r = run(&g, Bounds::default());
assert!(!r.coverage_fed);
assert!(r.evidence_note.contains("UPPER bound"), "{}", r.evidence_note);
// With no penalties and coverage off, everything is fully trusted ⇒ act.
assert_eq!(r.refuse, 0);
assert_eq!(r.hold, 0);
}
}