crates/nornir-feature-graph/src/bipartite.rs
//! **The bipartite feature↔crate graph** a pane renders, carried on the ONE
//! graph seam (`nornir-graph`) rather than a second graph abstraction.
//!
//! Node ids are opaque strings, which is exactly what [`nornir_graph::MemGraph`]
//! is for. They are namespaced so the two sides cannot collide — a feature
//! called `serde` and a crate called `serde` are different nodes:
//!
//! ```text
//! feat:<name> a root feature the user can click
//! crate:<name> a package that may or may not be in the build
//! and:<n> a CONJUNCTION node — see below
//! ```
//!
//! ## Why there is a third kind of node
//!
//! A plain bipartite graph can only say "these features are connected to this
//! crate". It cannot distinguish *"either of these two features pulls it"* from
//! *"only both together pull it"*. Those need opposite things from the UI:
//! clicking one feature off removes the crate in the second case and does
//! nothing in the first. Drawing them the same way is the `pkg?/feat` lie.
//!
//! So a cause of size ≥ 2 gets its own `and:` node: the features point INTO it,
//! it points at the crate, and a renderer draws it as a join. A cause of size 1
//! is an edge straight from the feature to the crate.
use crate::galois::{CrateAnalysis, Reachability};
use nornir_graph::{EdgeLabel, MemGraph};
use serde::{Deserialize, Serialize};
use std::collections::BTreeMap;
/// What a node is. Rendered as shape/colour.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
pub enum NodeKind {
/// A clickable root feature.
Feature { name: String, enabled: bool },
/// A package. `status` says whether any click can ever remove it.
Crate { name: String, status: Reachability, in_build: bool },
/// A conjunction join. `arity` is how many features must ALL be on.
Conjunction { arity: usize, satisfied: bool },
}
impl NodeKind {
pub fn label(&self) -> String {
match self {
NodeKind::Feature { name, .. } => name.clone(),
NodeKind::Crate { name, .. } => name.clone(),
NodeKind::Conjunction { arity, .. } => format!("AND ×{arity}"),
}
}
}
/// The relation an edge carries. `EdgeLabel` wants a small total codec, so this
/// is a plain enum over a handful of codes with a saturating decode.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
pub enum Rel {
/// feature → crate: this one feature alone pulls it.
#[default]
Pulls,
/// feature → and-node: this feature is one conjunct.
Conjunct,
/// and-node → crate: the conjunction pulls it.
PullsJointly,
/// (root) → crate: pulled with no features on. The ⊥ case.
Unconditional,
}
impl EdgeLabel for Rel {
fn encode(self) -> i64 {
match self {
Rel::Pulls => 0,
Rel::Conjunct => 1,
Rel::PullsJointly => 2,
Rel::Unconditional => 3,
}
}
// Total, as the trait requires: an unknown code saturates rather than
// panicking, so a graph written by a newer version still decodes.
fn decode(code: i64) -> Self {
match code {
1 => Rel::Conjunct,
2 => Rel::PullsJointly,
3 => Rel::Unconditional,
_ => Rel::Pulls,
}
}
}
pub fn feat_id(name: &str) -> String {
format!("feat:{name}")
}
pub fn crate_id(name: &str) -> String {
format!("crate:{name}")
}
pub fn and_id(n: usize) -> String {
format!("and:{n}")
}
/// The rendered graph: the `nornir-graph` store plus the bookkeeping a pane
/// needs (which features are currently off, and what that costs).
pub struct BipartiteBuild {
pub graph: MemGraph<NodeKind, Rel>,
/// Ordered feature ids, for a stable column layout.
pub features: Vec<String>,
/// Ordered crate ids.
pub crates: Vec<String>,
/// Per-crate analysis, keyed by crate NAME (not node id).
pub analyses: BTreeMap<String, CrateAnalysis>,
}
/// Build the bipartite graph from a set of per-crate analyses and the feature
/// universe. `disabled` is the set of features currently clicked OFF.
///
/// The `in_build` flag on each crate node is computed from the analyses'
/// causes — a crate is in the build iff it is unconditional, or some cause has
/// all of its features still enabled. That is the SAME rule the resolver uses,
/// read off the same causes, so the picture and the resolve cannot drift.
pub fn build(
all_features: &[String],
analyses: &BTreeMap<String, CrateAnalysis>,
disabled: &std::collections::BTreeSet<String>,
) -> BipartiteBuild {
use nornir_graph::GraphStore;
let mut graph: MemGraph<NodeKind, Rel> = MemGraph::new();
let mut features = Vec::new();
let mut crates = Vec::new();
let mut and_counter = 0usize;
for f in all_features {
let id = feat_id(f);
let _ = graph.put_node(
&id,
NodeKind::Feature { name: f.clone(), enabled: !disabled.contains(f) },
);
features.push(id);
}
for (name, a) in analyses {
let satisfied_cause = |c: &std::collections::BTreeSet<String>| -> bool {
c.iter().all(|f| !disabled.contains(f))
};
let in_build = match a.status {
Reachability::Unconditional => true,
Reachability::Never => false,
Reachability::Conditional => a.causes.iter().any(satisfied_cause),
};
let cid = crate_id(name);
let _ = graph.put_node(
&cid,
NodeKind::Crate { name: name.clone(), status: a.status.clone(), in_build },
);
crates.push(cid.clone());
match a.status {
Reachability::Unconditional => {
// No incoming feature edge at all — that absence IS the fact,
// and the node's `status` says so explicitly so a renderer never
// has to infer "no edges" as "no data".
}
Reachability::Never => {}
Reachability::Conditional => {
for cause in &a.causes {
if cause.len() == 1 {
let f = cause.iter().next().expect("len 1");
let _ = graph.add_edge(&feat_id(f), &cid, Rel::Pulls);
} else {
and_counter += 1;
let aid = and_id(and_counter);
let _ = graph.put_node(
&aid,
NodeKind::Conjunction {
arity: cause.len(),
satisfied: satisfied_cause(cause),
},
);
for f in cause {
let _ = graph.add_edge(&feat_id(f), &aid, Rel::Conjunct);
}
let _ = graph.add_edge(&aid, &cid, Rel::PullsJointly);
}
}
}
}
}
BipartiteBuild { graph, features, crates, analyses: analyses.clone() }
}
impl BipartiteBuild {
/// **Click a feature off (or on).** Returns the crates whose membership
/// changed — the applied output a test should assert on, not the fact that
/// a setter ran.
pub fn crates_changed_by(
&self,
disabled_before: &std::collections::BTreeSet<String>,
disabled_after: &std::collections::BTreeSet<String>,
) -> Vec<(String, bool, bool)> {
let mut out = Vec::new();
for (name, a) in &self.analyses {
let f = |d: &std::collections::BTreeSet<String>| match a.status {
Reachability::Unconditional => true,
Reachability::Never => false,
Reachability::Conditional => {
a.causes.iter().any(|c| c.iter().all(|x| !d.contains(x)))
}
};
let (b, aft) = (f(disabled_before), f(disabled_after));
if b != aft {
out.push((name.clone(), b, aft));
}
}
out
}
pub fn node_count(&self) -> usize {
use nornir_graph::GraphQuery;
self.graph.node_count()
}
/// Every conjunction node, so a renderer can prove it drew them.
pub fn conjunctions(&self) -> Vec<(String, usize, bool)> {
self.graph
.entries()
.filter_map(|(id, n)| match n {
NodeKind::Conjunction { arity, satisfied } => {
Some((id.clone(), *arity, *satisfied))
}
_ => None,
})
.collect()
}
}