planarian_diagnose/
lib.rs

1//! Deterministic diagnoser (SPEC §13): root-cause over the typed graph, then
2//! enumerate the known transitions that could close the divergence, safest
3//! and least disruptive first. Pure.
4//!
5//! Only `Requires` edges, and `Diagnostic` edges with confidence ≥ 0.7, are
6//! walked. `Ordering` and `Wants` never are, so a failed wanted or ordered-
7//! before unit is never blamed for another unit's failure. Cycles are
8//! collapsed into strongly connected components first.
9
10use planarian_incident::divergent;
11use planarian_schema::spec::{precondition, predict};
12use planarian_schema::{
13    ChangeId, Confidence, DriverRef, EdgeKind, Expectation, Incident, ProbeResult, ProbeRole, SystemState, Timestamp,
14    Transition, UnitDefs, UnitId, UnitKind, UnitStatus, Value,
15};
16use std::collections::{BTreeMap, BTreeSet};
17
18pub const DIAGNOSTIC_EDGE_MIN: Confidence = Confidence(700);
19
20pub struct Inputs<'a> {
21    pub state: &'a SystemState,
22    pub defs: &'a UnitDefs,
23    /// When each unit was first observed definitely Failed (tie-break in a cycle).
24    pub failed_since: &'a BTreeMap<UnitId, Timestamp>,
25    /// The driver each device was last seen bound to.
26    pub known_drivers: &'a BTreeMap<UnitId, DriverRef>,
27    /// The running generation was built by a Planarian transaction. Owner-built
28    /// generations are never rolled back autonomously (owner decision Q3).
29    pub current_planarian_built: bool,
30    /// For each runtime option a unit names as its repair (`runtime_repair`),
31    /// the other values available now (for Wi-Fi: known networks in range).
32    pub alternatives: &'a BTreeMap<String, Vec<Value>>,
33    /// For a unit, the catalog change last committed for it whose
34    /// assignments the override file no longer carries (§13, P22).
35    pub lost_changes: &'a BTreeMap<UnitId, (ChangeId, BTreeMap<String, Value>)>,
36}
37
38#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct Candidate {
40    pub target: UnitId,
41    pub transition: Transition,
42    pub expected: Expectation,
43    pub reason: String,
44}
45
46fn diverges(u: &UnitId, i: &Inputs<'_>) -> bool {
47    let Some(def) = i.defs.get(u) else { return false };
48    i.state.expected(u, i.defs) && divergent(def.desired.status, &i.state.status(u, i.defs))
49}
50
51fn walkable(kind: &EdgeKind) -> bool {
52    match kind {
53        EdgeKind::Requires => true,
54        EdgeKind::Diagnostic { confidence } => *confidence >= DIAGNOSTIC_EDGE_MIN,
55        EdgeKind::Ordering | EdgeKind::Wants => false,
56    }
57}
58
59/// The divergent units reachable from `target` through walkable edges, with
60/// their walkable edges among themselves.
61fn subgraph(target: &UnitId, i: &Inputs<'_>) -> BTreeMap<UnitId, Vec<UnitId>> {
62    let mut g: BTreeMap<UnitId, Vec<UnitId>> = BTreeMap::new();
63    let mut frontier = vec![target.clone()];
64    while let Some(u) = frontier.pop() {
65        if g.contains_key(&u) {
66            continue;
67        }
68        let next: Vec<UnitId> = i
69            .defs
70            .get(&u)
71            .map(|d| d.edges.iter().filter(|e| walkable(&e.kind) && diverges(&e.to, i)).map(|e| e.to.clone()).collect())
72            .unwrap_or_default();
73        frontier.extend(next.iter().cloned());
74        g.insert(u, next);
75    }
76    g
77}
78
79/// Tarjan's algorithm. Returns the components and each node's component index.
80fn sccs(g: &BTreeMap<UnitId, Vec<UnitId>>) -> (Vec<Vec<UnitId>>, BTreeMap<UnitId, usize>) {
81    struct T<'g> {
82        g: &'g BTreeMap<UnitId, Vec<UnitId>>,
83        index: BTreeMap<UnitId, usize>,
84        low: BTreeMap<UnitId, usize>,
85        on: BTreeSet<UnitId>,
86        stack: Vec<UnitId>,
87        comps: Vec<Vec<UnitId>>,
88        n: usize,
89    }
90    fn visit(t: &mut T<'_>, v: &UnitId) {
91        t.index.insert(v.clone(), t.n);
92        t.low.insert(v.clone(), t.n);
93        t.n += 1;
94        t.stack.push(v.clone());
95        t.on.insert(v.clone());
96        for w in t.g.get(v).cloned().unwrap_or_default() {
97            if !t.index.contains_key(&w) {
98                visit(t, &w);
99                let lw = t.low[&w];
100                let lv = t.low.get_mut(v).expect("visited");
101                *lv = (*lv).min(lw);
102            } else if t.on.contains(&w) {
103                let iw = t.index[&w];
104                let lv = t.low.get_mut(v).expect("visited");
105                *lv = (*lv).min(iw);
106            }
107        }
108        if t.low[v] == t.index[v] {
109            let mut comp = vec![];
110            while let Some(w) = t.stack.pop() {
111                t.on.remove(&w);
112                comp.push(w.clone());
113                if &w == v {
114                    break;
115                }
116            }
117            comp.sort();
118            t.comps.push(comp);
119        }
120    }
121    let mut t =
122        T { g, index: BTreeMap::new(), low: BTreeMap::new(), on: BTreeSet::new(), stack: vec![], comps: vec![], n: 0 };
123    for v in g.keys() {
124        if !t.index.contains_key(v) {
125            visit(&mut t, v);
126        }
127    }
128    let mut of = BTreeMap::new();
129    for (ci, c) in t.comps.iter().enumerate() {
130        for u in c {
131            of.insert(u.clone(), ci);
132        }
133    }
134    (t.comps, of)
135}
136
137/// Tie-break (§13): earliest definite Failed, then most failed Readiness
138/// probes, then lexical order. Smaller key wins.
139fn rank(u: &UnitId, i: &Inputs<'_>) -> (u64, std::cmp::Reverse<usize>, UnitId) {
140    let failed_at = i.failed_since.get(u).map(|t| t.0).unwrap_or(u64::MAX);
141    let failed_probes = match (i.defs.get(u), i.state.units.get(u)) {
142        (Some(d), Some((_, ev))) => d
143            .probes
144            .iter()
145            .filter(|p| p.role == ProbeRole::Readiness)
146            .filter(|p| ev.iter().any(|e| e.probe == p.id && matches!(e.result, ProbeResult::Fail(_))))
147            .count(),
148        _ => 0,
149    };
150    (failed_at, std::cmp::Reverse(failed_probes), u.clone())
151}
152
153/// The deepest divergent unit below `target` (§13 step 1).
154pub fn root_cause(target: &UnitId, i: &Inputs<'_>) -> UnitId {
155    let g = subgraph(target, i);
156    let (comps, of) = sccs(&g);
157    // Sinks of the condensation: components with no edge to another component.
158    let sinks: Vec<usize> =
159        (0..comps.len()).filter(|ci| comps[*ci].iter().all(|u| g[u].iter().all(|w| of[w] == *ci))).collect();
160    sinks.iter().flat_map(|ci| comps[*ci].iter()).min_by_key(|u| rank(u, i)).cloned().unwrap_or_else(|| target.clone())
161}
162
163/// Coarse ordering key standing in for the policy tier (§13 step 3); the
164/// executor's policy decision remains authoritative.
165fn est_tier(t: &Transition) -> u8 {
166    match t {
167        Transition::RestartUnit(_) | Transition::CollectGarbage { .. } | Transition::SetRuntimeOption { .. } => 1,
168        Transition::BindDriver { .. } | Transition::ApplyChange { .. } => 2,
169        _ => 3,
170    }
171}
172
173/// Candidate transitions for an incident, in the order to try them (§13 steps 2–3).
174pub fn candidates(incident: &Incident, i: &Inputs<'_>) -> Vec<Candidate> {
175    let root = root_cause(&incident.target, i);
176    if i.state.overridden(&root) {
177        return vec![]; // I13
178    }
179    let Some(def) = i.defs.get(&root) else { return vec![] };
180    let status = i.state.status(&root, i.defs);
181    let mut out: Vec<(Transition, String)> = vec![];
182    let via = if root == incident.target { String::new() } else { format!(" (root cause of {})", incident.target) };
183
184    // A unit restored by choosing another value of a runtime option (§12a):
185    // Wi-Fi to another known network in range. The unit says its health
186    // depends on that value, so when another is available it comes before a
187    // restart (which cannot bring a network back). It drops connectivity, so
188    // the policy floors make it AskFirst.
189    if let Some(opt) = &def.runtime_repair
190        && divergent(def.desired.status, &status)
191        && let Some(v) = i.alternatives.get(opt).and_then(|a| a.first())
192    {
193        let shown = match v {
194            Value::Str(s) => s.clone(),
195            other => format!("{other:?}"),
196        };
197        out.push((
198            Transition::SetRuntimeOption { path: opt.clone(), value: v.clone() },
199            format!("{root} is {status:?}; switch {opt} to {shown}{via}"),
200        ));
201    }
202
203    match def.id.kind {
204        UnitKind::Device if root.name.starts_with("fs-") => {
205            let emergency = root.name == "fs-journal" || root.name == "fs-nix";
206            out.push((Transition::CollectGarbage { emergency }, format!("{root} is low on space{via}")));
207        }
208        UnitKind::Device => {
209            if let Some(driver) = i.known_drivers.get(&root)
210                && matches!(status, UnitStatus::Detected | UnitStatus::Failed(_))
211            {
212                out.push((
213                    Transition::BindDriver { device: root.clone(), driver: driver.clone() },
214                    format!("{root} lost its driver {}{via}", driver.name),
215                ));
216            }
217        }
218        _ if root.name.starts_with("external:") => {
219            // Nothing local repairs an external dependency; report it.
220        }
221        _ => match status {
222            UnitStatus::Failed(_) | UnitStatus::Stopped | UnitStatus::Degraded(_) => {
223                out.push((Transition::RestartUnit(root.clone()), format!("{root} is {status:?}{via}")));
224            }
225            UnitStatus::Absent => out.push((
226                Transition::ApplyChange {
227                    change: ChangeId("repair:reenable-predicted".into()),
228                    args: [("service".to_string(), Value::Str(root.name.clone()))].into(),
229                },
230                format!("{root} is missing though the manifest predicts it{via}"),
231            )),
232            _ => {}
233        },
234    }
235
236    // §13 (P22): the change committed for this unit is gone from the
237    // override file: put it back.
238    if divergent(def.desired.status, &status)
239        && let Some((change, args)) = i.lost_changes.get(&root)
240    {
241        let mut a = args.clone();
242        a.insert("change".into(), Value::Str(change.0.clone()));
243        out.push((
244            Transition::ApplyChange { change: ChangeId("repair:reapply".into()), args: a },
245            format!("{root} is {status:?} and the change {} committed for it is no longer applied{via}", change.0),
246        ));
247    }
248
249    if i.current_planarian_built && i.state.generation != i.state.known_good {
250        out.push((Transition::Rollback, format!("roll back to the known-good generation{via}")));
251    }
252
253    out.retain(|(t, _)| precondition(t, i.state, i.defs));
254    out.sort_by_key(|(t, _)| {
255        let rollback = matches!(t, Transition::Rollback);
256        (rollback, est_tier(t), def.restart_disruption)
257    });
258    out.into_iter()
259        .map(|(t, reason)| Candidate {
260            target: root.clone(),
261            expected: predict(&t, i.state, i.defs),
262            transition: t,
263            reason,
264        })
265        .collect()
266}
267
268/// The candidate for this attempt: candidates are tried in order across the
269/// incident's attempts, wrapping around (so a lone restart is retried until the
270/// budget is spent). `None`: the diagnoser is exhausted.
271pub fn next(incident: &Incident, i: &Inputs<'_>) -> Option<Candidate> {
272    let c = candidates(incident, i);
273    if c.is_empty() {
274        return None;
275    }
276    let n = incident.attempts.len() % c.len();
277    c.into_iter().nth(n)
278}
279
280#[cfg(test)]
281mod tests;
planarian_diagnose/lib.rs

planarian_diagnose/
lib.rs
