crates/nornir-feature-graph/tests/monotone_law.rs
//! **The property everything else rests on.**
//!
//! The whole design of [`galois`](nornir_feature_graph::galois) depends on one
//! claim: `{S : c ∈ F(S)}` is UPWARD-CLOSED, so it is exactly the up-set of its
//! minimal elements, so a set of features to turn off is correct iff it hits
//! every minimal cause.
//!
//! That claim follows from `F` being monotone — `S ⊆ T ⟹ F(S) ⊆ F(T)` — and
//! monotonicity was asserted in a doc comment and nowhere else. A resolver that
//! ever REMOVED an activation when a feature was added would break the cause
//! enumeration, the drop plans, and the pane, and every existing test would
//! still pass, because they all check specific answers rather than the law the
//! answers depend on.
//!
//! So: check the law, on real manifests, over many random subsets.
use nornir_feature_graph::{registry, resolve, ResolveConfig, Universe};
use std::collections::BTreeSet;
use std::path::PathBuf;
/// A tiny deterministic LCG. A `rand` dependency in a leaf crate to shuffle
/// forty booleans would not earn its place, and a fixed seed makes a failure
/// reproducible.
struct Lcg(u64);
impl Lcg {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
self.0 >> 33
}
fn subset(&mut self, of: &[String]) -> BTreeSet<String> {
of.iter().filter(|_| self.next().is_multiple_of(2)).cloned().collect()
}
}
fn fixture() -> (Universe, String, Vec<String>) {
const A: &str = r#"
[package]
name = "root"
version = "0.1.0"
[features]
alpha = ["dep:one", "beta"]
beta = ["two?/extra", "dep:two"]
gamma = ["one?/deep", "delta"]
delta = ["dep:three"]
epsilon = ["three/wide"]
[dependencies]
base = "1"
one = { version = "1", optional = true }
two = { version = "1", optional = true }
three = { version = "1", optional = true }
"#;
const ONE: &str = r#"
[package]
name = "one"
version = "1.0.0"
[features]
deep = ["dep:leafa"]
[dependencies]
leafa = { version = "1", optional = true }
"#;
const TWO: &str = r#"
[package]
name = "two"
version = "1.0.0"
[features]
extra = ["dep:leafb"]
[dependencies]
leafb = { version = "1", optional = true }
"#;
const THREE: &str = r#"
[package]
name = "three"
version = "1.0.0"
[features]
wide = ["dep:leafc"]
[dependencies]
leafc = { version = "1", optional = true }
"#;
let mut u = Universe::default();
u.add_manifest_str("t", "root", A).unwrap();
u.add_manifest_str("t", "one", ONE).unwrap();
u.add_manifest_str("t", "two", TWO).unwrap();
u.add_manifest_str("t", "three", THREE).unwrap();
for n in ["base", "leafa", "leafb", "leafc"] {
u.add_manifest_str("t", n, &format!("[package]\nname = \"{n}\"\nversion = \"1.0.0\"\n"))
.unwrap();
}
let feats: Vec<String> =
nornir_feature_graph::root_features(&u, "root").into_iter().collect();
(u, "root".to_string(), feats)
}
/// `S ⊆ T ⟹ F(S) ⊆ F(T)`, on a fixture built to be hostile: weak deps, a
/// feature that both activates a dep and weak-references it, and three levels of
/// optional nesting.
#[test]
fn f_is_monotone_on_a_hostile_fixture() {
let (u, root, feats) = fixture();
let cfg = ResolveConfig::default();
let mut rng = Lcg(0x5EED);
let mut checked = 0usize;
let mut nonconstant = false;
let full = resolve(&u, &root, &feats.iter().cloned().collect(), &cfg);
let empty = resolve(&u, &root, &BTreeSet::new(), &cfg);
assert!(
full.packages.len() > empty.packages.len(),
"the fixture must actually respond to features, or this proves nothing \
({} vs {})",
full.packages.len(),
empty.packages.len()
);
for _ in 0..400 {
let s = rng.subset(&feats);
// Build T ⊇ S by adding a random extra feature.
let mut t = s.clone();
if let Some(extra) = feats.get(rng.next() as usize % feats.len()) {
t.insert(extra.clone());
}
let fs = resolve(&u, &root, &s, &cfg);
let ft = resolve(&u, &root, &t, &cfg);
assert!(
fs.packages.is_subset(&ft.packages),
"MONOTONICITY VIOLATED: S={s:?} T={t:?}\n F(S)={:?}\n F(T)={:?}\n lost={:?}",
fs.packages,
ft.packages,
fs.packages.difference(&ft.packages).collect::<Vec<_>>()
);
if fs.packages != ft.packages {
nonconstant = true;
}
checked += 1;
}
assert_eq!(checked, 400);
assert!(
nonconstant,
"every pair produced the SAME closure — the subset check passed vacuously"
);
}
/// The same law on the REAL constellation, where the manifests are not chosen to
/// be convenient. Skips loudly without a checkout.
#[test]
fn f_is_monotone_on_real_manifests() {
let checkout = std::env::var_os("NORDISK_CHECKOUT_ROOT")
.map(PathBuf::from)
.unwrap_or_else(|| PathBuf::from(std::env::var_os("HOME").unwrap_or_default()).join("git"));
let root = checkout.join("dwarves");
if !root.join("Cargo.lock").is_file() {
eprintln!("SKIPPED ON PURPOSE: no dwarves checkout at {}", root.display());
return;
}
let (u, _l) = registry::universe_for_constellation(&root, &root)
.expect("constellation scan");
let id = registry::id_for(&u, "dwarves").expect("dwarves uniquely locked");
let feats: Vec<String> = nornir_feature_graph::root_features(&u, &id).into_iter().collect();
assert!(feats.len() > 10, "dwarves must declare a real feature set, got {}", feats.len());
let cfg = ResolveConfig::default();
let mut rng = Lcg(0xC0FFEE);
let mut widened = 0usize;
let mut pairs = 0usize;
// EXHAUSTIVE over the ADDED feature, not random. A first pass drew both the
// base set and the added feature at random and checked 40 pairs; a
// deliberately non-monotone resolver keyed on ONE feature survived it,
// because the chance of that feature being the one drawn is ~1/n. Every
// feature must get its turn as the addition.
let bases: Vec<BTreeSet<String>> = (0..3).map(|_| rng.subset(&feats)).collect();
for base in &bases {
for f in &feats {
if base.contains(f) {
continue;
}
let mut t = base.clone();
t.insert(f.clone());
let fs = resolve(&u, &id, base, &cfg);
let ft = resolve(&u, &id, &t, &cfg);
pairs += 1;
assert!(
fs.packages.is_subset(&ft.packages),
"MONOTONICITY VIOLATED on real manifests: adding `{f}` to a {}-feature set \
LOST {:?}",
base.len(),
fs.packages.difference(&ft.packages).take(8).collect::<Vec<_>>()
);
if ft.packages.len() > fs.packages.len() {
widened += 1;
}
}
}
eprintln!(" {pairs} real subset pairs checked, {widened} of them strictly widened");
assert!(pairs > 50, "only {pairs} pairs — too few to mean anything");
assert!(widened > 0, "no pair ever widened — the check passed vacuously");
}
/// The upward-closure corollary, stated as a test because it is the property
/// `drop_crate` actually uses: if a crate is absent under `T`, it is absent
/// under every `S ⊆ T`.
#[test]
fn absence_is_downward_closed() {
let (u, root, feats) = fixture();
let cfg = ResolveConfig::default();
let mut rng = Lcg(0xBEEF);
let mut tested = 0usize;
for _ in 0..300 {
let t = rng.subset(&feats);
let mut s = t.clone();
if let Some(drop) = t.iter().next().cloned() {
s.remove(&drop);
}
let ft = resolve(&u, &root, &t, &cfg);
let fs = resolve(&u, &root, &s, &cfg);
for c in ["leafa", "leafb", "leafc", "one", "two", "three"] {
if !ft.contains(c) {
assert!(
!fs.contains(c),
"{c} is absent under T={t:?} but PRESENT under the smaller S={s:?} — \
absence is not downward-closed, and every drop plan is unsound"
);
tested += 1;
}
}
}
assert!(tested > 50, "only {tested} absence checks fired — too few to mean anything");
}