//! Engine A / Engine B — two interchangeable strategies behind ONE contract.
//!
//! modgunn's core engine operation is: *given an artifact (or a whole fleet of
//! them) and an [`AdvisoryDb`], find the advisories that affect it and fold them
//! into a [`Verdict`].* The verdict-assembly half is fixed ([`Policy::assemble`]);
//! the half that *varies* is the **advisory-matching** — the hot path at
//! whole-OSS-world scale (`components × advisories`). This module abstracts that
//! matching behind the [`AdvisoryEngine`] trait and ships two genuine, swappable
//! implementations:
//!
//! - **Engine A — [`LinearEngine`]** (the strategy modgunn shipped): a linear
//! scan over every advisory for every artifact ([`AdvisoryDb::query`]). Zero
//! build cost, minimal memory, cache-friendly for a *small* db; but its fleet
//! cost is `Θ(artifacts × advisories)`.
//! - **Engine B — [`IndexedEngine`]** (the alternative): a one-time
//! `(ecosystem, package)` → advisory-bucket inverted index built up front, so a
//! query touches only the advisories for that exact package. Its fleet cost is
//! `Θ(artifacts × hits_per_package)` after an `Θ(advisories)` build — a large
//! constant-factor-to-asymptotic win once the db is big, at the price of the
//! index's memory and build time.
//!
//! **They agree by construction.** An advisory can only match an artifact whose
//! `ecosystem` + `name` equal the advisory's `ecosystem` + `package` (see
//! [`Advisory::matches`]), so bucketing by that key is *lossless*: Engine B tests
//! exactly the advisories Engine A would have let through its package guard, in the
//! same original order. Both therefore emit byte-identical [`Verdict`]s — pinned by
//! [`tests`] and the `tests/engine_ab_equivalence.rs` integration test. The only
//! place they may *legitimately* differ is cost, which is the whole point (and what
//! `.nornir/engine-benchmarks.md` measures head-to-head).
//!
//! Selection is a runtime choice: [`EngineKind`] parses from a CLI flag / config /
//! env, and [`build`] hands back a `Box<dyn AdvisoryEngine>` for the chosen one.
use std::collections::HashMap;
use std::fmt;
use znippy_zoomies::gatling_forkjoin::gatling_for_each;
use crate::core::{ArtifactRef, Verdict};
use crate::scan::{Advisory, AdvisoryDb, Artifact, Policy};
/// Which matching strategy to run — the A/B switch, parsed from a CLI flag / config
/// / env. [`EngineKind::A`] is the default so existing callers keep modgunn's shipped
/// linear behaviour unless they opt into B.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum EngineKind {
/// Engine A — [`LinearEngine`] (linear per-advisory scan). The default.
#[default]
A,
/// Engine B — [`IndexedEngine`] (`(ecosystem, package)` inverted index).
B,
}
impl EngineKind {
/// A stable short label (`"A"` / `"B"`) for reports + the bench table.
pub fn label(self) -> &'static str {
match self {
EngineKind::A => "A",
EngineKind::B => "B",
}
}
/// A human strategy name for logs / `--help`.
pub fn strategy(self) -> &'static str {
match self {
EngineKind::A => "linear",
EngineKind::B => "indexed",
}
}
/// Parse a selection token. Accepts `a`/`b` (case-insensitive) and the strategy
/// aliases `linear`/`indexed`; anything else is `None` so the caller can fall
/// back to the default and warn.
pub fn parse(s: &str) -> Option<Self> {
match s.trim().to_ascii_lowercase().as_str() {
"a" | "linear" | "engine-a" => Some(EngineKind::A),
"b" | "indexed" | "index" | "engine-b" => Some(EngineKind::B),
_ => None,
}
}
/// Read the engine from `MODGUNN_ENGINE` (`a|b|linear|indexed`), defaulting to
/// [`EngineKind::A`] when unset or unrecognised — the config seam a service uses
/// when there is no CLI flag.
pub fn from_env() -> Self {
std::env::var("MODGUNN_ENGINE")
.ok()
.and_then(|v| Self::parse(&v))
.unwrap_or_default()
}
}
impl fmt::Display for EngineKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "engine-{} ({})", self.label(), self.strategy())
}
}
impl std::str::FromStr for EngineKind {
type Err = String;
fn from_str(s: &str) -> Result<Self, String> {
Self::parse(s).ok_or_else(|| format!("unknown engine `{s}` (expected a|b|linear|indexed)"))
}
}
/// The common engine contract: find the advisories affecting an artifact, and fold
/// an artifact into a [`Verdict`]. Implementors differ ONLY in [`matching`] (the
/// strategy); [`verdict`] and [`fleet`] are provided on top of it so every engine
/// shares the exact same verdict semantics ([`Policy::assemble`]).
///
/// `Send + Sync` so a fleet scan can fan out across all cores: [`fleet`] drives the
/// whole artifact set through znippy-zoomies' no-barrier fork-join gatling
/// (`gatling_for_each`) over one shared `&self` — the SAME path the HEAVY bench and
/// the production warehouse scan run. No rayon, no modgunn-owned thread pool.
///
/// [`matching`]: AdvisoryEngine::matching
/// [`verdict`]: AdvisoryEngine::verdict
/// [`fleet`]: AdvisoryEngine::fleet
pub trait AdvisoryEngine: Send + Sync {
/// Which strategy this is (for reporting / the bench table).
fn kind(&self) -> EngineKind;
/// The `advisory_db_rev` of the db behind this engine — the cache-key rev that
/// flows into every [`Verdict`] this engine assembles.
fn rev(&self) -> &str;
/// The advisories affecting `artifact`, in the db's original order — the
/// strategy-specific hot path. Engine A scans linearly; Engine B looks up the
/// package bucket. The returned set + order is identical across engines.
fn matching(&self, artifact: &ArtifactRef) -> Vec<&Advisory>;
/// The full [`Verdict`] for one artifact: strategy-specific [`matching`] +
/// engine-agnostic assembly. Identical across engines by construction.
///
/// [`matching`]: AdvisoryEngine::matching
fn verdict(&self, policy: &Policy, artifact: &Artifact) -> Verdict {
let matched = self.matching(&artifact.artifact);
policy.assemble(self.rev(), artifact, &matched)
}
/// A whole-fleet scan: one [`Verdict`] per artifact, in input order. Fans the
/// artifacts across all cores on znippy-zoomies' no-barrier fork-join gatling
/// (`gatling_for_each`, `n_workers == 0` ⇒ one per core) over the shared `&self`
/// (which is why the trait is `Send + Sync`). Results are returned in the original
/// `0..n` index order, so the output is identical to a serial map — this is the
/// production parallel path, not a bench-only one. Zero rayon.
fn fleet(&self, policy: &Policy, artifacts: &[Artifact]) -> Vec<Verdict> {
gatling_for_each(artifacts.len(), 0, |i| self.verdict(policy, &artifacts[i]))
}
}
/// **Engine A** — the linear scanner modgunn shipped. Holds the db by reference and
/// answers every query with [`AdvisoryDb::query`] (a full linear filter). No build
/// step, no extra memory; the fleet cost is `Θ(artifacts × advisories)`.
pub struct LinearEngine<'d> {
db: &'d AdvisoryDb,
}
impl<'d> LinearEngine<'d> {
pub fn new(db: &'d AdvisoryDb) -> Self {
Self { db }
}
}
impl AdvisoryEngine for LinearEngine<'_> {
fn kind(&self) -> EngineKind {
EngineKind::A
}
fn rev(&self) -> &str {
&self.db.rev
}
fn matching(&self, artifact: &ArtifactRef) -> Vec<&Advisory> {
// Exactly modgunn's shipped path — the A/B reference behaviour.
self.db.query(artifact)
}
}
/// **Engine B** — the inverted-index scanner. A one-time pass buckets advisory
/// *indices* by `(ecosystem, package)` (lower-cased key), preserving original order
/// within a bucket. A query lower-cases the artifact's `(ecosystem, name)`, grabs at
/// most one bucket, and version-tests only those advisories — so the fleet cost is
/// `Θ(artifacts × hits_per_package)` after an `Θ(advisories)` build.
///
/// The key is compared case-insensitively on both sides so the bucket lookup can
/// never *miss* a match [`Advisory::matches`] would make. `matches` itself still
/// compares ecosystem + package with its own (case-sensitive) rule, so B never
/// *adds* a match A wouldn't: the index only ever *narrows* the candidate set
/// losslessly.
///
/// **Zero-allocation lookup.** The buckets are keyed by an FNV-1a hash of the
/// lower-cased `(ecosystem, package)` bytes — folded byte-by-byte, so a query
/// allocates NOTHING to hash (the old design lower-cased into two fresh `String`s
/// per call, in the hottest loop modgunn has). Hash collisions are resolved by a
/// short per-hash list of [`PkgBucket`]s that carry the lower-cased key for an
/// `eq_ignore_ascii_case` verify — allocated once at build, never on the hot path.
pub struct IndexedEngine<'d> {
db: &'d AdvisoryDb,
/// `fnv1a_lc(ecosystem, package)` → collision list of package buckets.
index: HashMap<u64, Vec<PkgBucket>>,
}
/// One `(ecosystem, package)` bucket: the lower-cased key (for the collision-safe
/// verify) plus the advisory indices into `db.advisories`, ascending.
struct PkgBucket {
ecosystem_lc: String,
package_lc: String,
/// Indices into `db.advisories`, in ascending (original) order.
idxs: Vec<usize>,
}
/// FNV-1a over the ASCII-lower-cased bytes of `eco` then `name` (with a `0` byte
/// separator so `("a","bc")` and `("ab","c")` never collide by concatenation).
/// Folds the case-fold in place — zero heap allocation.
fn fnv1a_lc(eco: &str, name: &str) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
for &b in eco.as_bytes() {
h ^= b.to_ascii_lowercase() as u64;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
}
h ^= 0;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
for &b in name.as_bytes() {
h ^= b.to_ascii_lowercase() as u64;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
}
h
}
impl<'d> IndexedEngine<'d> {
/// Build the inverted index over `db` (the `Θ(advisories)` up-front cost).
pub fn new(db: &'d AdvisoryDb) -> Self {
let mut index: HashMap<u64, Vec<PkgBucket>> = HashMap::new();
for (i, adv) in db.advisories.iter().enumerate() {
// Key by the SAME canonical (ecosystem, name) equivalence `Advisory::matches`
// uses — pip↔pypi folded, PyPI names PEP 503-normalized — so a PyPI
// separator/case/label variant lands in the one bucket its advisory
// matches. `matches` remains the authoritative confirm below, so B never
// reports a hit A wouldn't: A≡B holds by construction.
let eco = crate::scan::canonical_eco(&adv.ecosystem);
let pkg = crate::scan::canonical_pkg(&adv.ecosystem, &adv.package);
let h = fnv1a_lc(eco, &pkg);
let list = index.entry(h).or_default();
match list.iter_mut().find(|b| {
b.ecosystem_lc.eq_ignore_ascii_case(eco) && b.package_lc.eq_ignore_ascii_case(&pkg)
}) {
Some(bucket) => bucket.idxs.push(i),
None => list.push(PkgBucket {
ecosystem_lc: eco.to_ascii_lowercase(),
package_lc: pkg.to_ascii_lowercase(),
idxs: vec![i],
}),
}
}
Self { db, index }
}
/// Number of distinct `(ecosystem, package)` buckets — reported by the bench.
pub fn bucket_count(&self) -> usize {
self.index.values().map(|list| list.len()).sum()
}
}
impl AdvisoryEngine for IndexedEngine<'_> {
fn kind(&self) -> EngineKind {
EngineKind::B
}
fn rev(&self) -> &str {
&self.db.rev
}
fn matching(&self, artifact: &ArtifactRef) -> Vec<&Advisory> {
let eco = crate::scan::canonical_eco(&artifact.ecosystem);
let pkg = crate::scan::canonical_pkg(&artifact.ecosystem, &artifact.name);
let h = fnv1a_lc(eco, &pkg);
let bucket = self.index.get(&h).and_then(|list| {
list.iter().find(|b| {
b.ecosystem_lc.eq_ignore_ascii_case(eco) && b.package_lc.eq_ignore_ascii_case(&pkg)
})
});
match bucket {
// Indices are pushed in ascending order, so iterating them re-creates
// Engine A's original-order output restricted to this package.
Some(b) => b
.idxs
.iter()
.map(|&i| &self.db.advisories[i])
.filter(|adv| adv.matches(artifact))
.collect(),
None => Vec::new(),
}
}
}
/// Build the chosen engine over `db`. The runtime A/B swap: a caller picks
/// [`EngineKind`] from a CLI flag / config / env and gets back a
/// `Box<dyn AdvisoryEngine>` it can scan through without knowing which strategy runs.
pub fn build<'d>(kind: EngineKind, db: &'d AdvisoryDb) -> Box<dyn AdvisoryEngine + 'd> {
match kind {
EngineKind::A => Box::new(LinearEngine::new(db)),
EngineKind::B => Box::new(IndexedEngine::new(db)),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::core::Severity;
use crate::scan::Provenance;
use crate::versions::RangeEvent::{Fixed, Introduced};
fn aref(ecosystem: &str, name: &str, version: &str) -> ArtifactRef {
ArtifactRef {
ecosystem: ecosystem.into(),
name: name.into(),
version: version.into(),
blob_sha256: format!("{name}-{version}-sha"),
}
}
fn art(ecosystem: &str, name: &str, version: &str) -> Artifact {
Artifact::new(
aref(ecosystem, name, version),
Some("MIT".into()),
Provenance::signed_by("ci"),
)
}
/// A db with several packages, exact + range + all-versions + withdrawn + a
/// second advisory for the same package (so bucket order matters).
fn db() -> AdvisoryDb {
AdvisoryDb::new(
"db-rev-7",
vec![
Advisory::basic(
"A-EXACT",
"cargo",
"openssl",
vec!["0.1.0".into()],
Severity::High,
"exact",
),
Advisory::basic(
"A-RANGE",
"cargo",
"widget",
vec![],
Severity::Medium,
"ranged",
)
.with_ranges(vec![Introduced("1.0.0".into()), Fixed("1.2.0".into())]),
Advisory::basic(
"A-ALL",
"npm",
"left-pad",
vec![],
Severity::Low,
"all versions",
),
{
let mut w =
Advisory::basic("A-GONE", "npm", "leftpad", vec![], Severity::Low, "gone");
w.withdrawn = true;
w
},
// Second advisory for openssl — must come AFTER A-EXACT in bucket order.
Advisory::basic(
"A-EXACT2",
"cargo",
"openssl",
vec!["0.1.0".into()],
Severity::Low,
"second",
),
],
)
}
/// The two engines return the SAME matching set in the SAME order for a spread
/// of artifacts (hitting, missing, multi-hit, withdrawn, wrong-ecosystem).
#[test]
fn matching_is_identical_across_engines() {
let db = db();
let a = LinearEngine::new(&db);
let b = IndexedEngine::new(&db);
let cases = [
aref("cargo", "openssl", "0.1.0"), // two advisories, order-sensitive
aref("cargo", "openssl", "0.2.0"), // unaffected version
aref("cargo", "widget", "1.1.0"), // in range
aref("cargo", "widget", "1.2.0"), // fixed — clean
aref("npm", "left-pad", "9.9.9"), // all-versions hit
aref("npm", "leftpad", "1.0.0"), // withdrawn — never matches
aref("maven", "nothing", "1.0.0"), // empty ecosystem bucket
];
for art in &cases {
let ma: Vec<&str> = a.matching(art).iter().map(|adv| adv.id.as_str()).collect();
let mb: Vec<&str> = b.matching(art).iter().map(|adv| adv.id.as_str()).collect();
assert_eq!(ma, mb, "engines disagree on {} {}", art.name, art.version);
}
// The order-sensitive case actually returns both openssl rows, A-EXACT first.
let ids: Vec<&str> = b
.matching(&aref("cargo", "openssl", "0.1.0"))
.iter()
.map(|adv| adv.id.as_str())
.collect();
assert_eq!(
ids,
["A-EXACT", "A-EXACT2"],
"bucket preserves original order"
);
}
/// The indexed bucket key must use the SAME PyPI canonicalization (PEP 503 +
/// pip↔pypi fold) as `Advisory::matches`, or B misses a separator/case/label
/// variant that A hits → the A≡B contract breaks. RED if `IndexedEngine` reverts
/// to a bare-lowercase (separator-blind) or pip-vs-pypi-literal key.
#[test]
fn indexed_engine_matches_pypi_canonical_variants() {
let db = AdvisoryDb::new(
"r",
vec![
Advisory::basic(
"CVE-DJ",
"pypi",
"django",
vec!["4.2.1".into()],
Severity::High,
"x",
),
Advisory::basic(
"CVE-ZI",
"pypi",
"zope-interface",
vec!["6.0".into()],
Severity::Low,
"x",
),
],
);
let a = LinearEngine::new(&db);
let b = IndexedEngine::new(&db);
let cases = [
aref("pypi", "Django", "4.2.1"), // case variant
aref("pip", "django", "4.2.1"), // ecosystem-label variant
aref("pip", "Django", "4.2.1"), // both at once
aref("pypi", "zope.interface", "6.0"), // separator variant
aref("pypi", "Zope__Interface", "6.0"), // separator run + case
aref("pypi", "unrelated", "1.0.0"), // miss on both
];
for art in &cases {
let ma: Vec<&str> = a.matching(art).iter().map(|adv| adv.id.as_str()).collect();
let mb: Vec<&str> = b.matching(art).iter().map(|adv| adv.id.as_str()).collect();
assert_eq!(
ma, mb,
"A≡B must hold for PyPI canonical variant {}",
art.name
);
}
// Anchor: the variants really do hit (not "both empty, trivially equal").
assert_eq!(
b.matching(&aref("pip", "Django", "4.2.1")).len(),
1,
"pip/Django hits django CVE"
);
assert_eq!(
b.matching(&aref("pypi", "zope.interface", "6.0")).len(),
1,
"dotted name hits"
);
}
/// Full verdicts (not just matches) are byte-identical across A and B over a
/// fleet, including decisions + findings — the contract the swap relies on.
#[test]
fn fleet_verdicts_are_identical_across_engines() {
let db = db();
let policy = Policy {
version: "p1".into(),
..Default::default()
};
let fleet: Vec<Artifact> = vec![
art("cargo", "openssl", "0.1.0"),
art("cargo", "openssl", "0.2.0"),
art("cargo", "widget", "1.1.0"),
art("npm", "left-pad", "3.0.0"),
art("cargo", "serde", "1.0.0"),
];
let va = LinearEngine::new(&db).fleet(&policy, &fleet);
let vb = IndexedEngine::new(&db).fleet(&policy, &fleet);
assert_eq!(
va, vb,
"Engine A and Engine B must produce identical verdicts"
);
// And a sanity anchor: openssl@0.1.0 is Blocked (two vulns, High wins).
assert_eq!(va[0].decision, crate::core::Decision::Block);
assert_eq!(va[0].findings.len(), 2);
}
/// The B verdict equals the shipped `OsvScanner` (Engine A's convenience path),
/// proving the refactor + index preserve modgunn's original semantics exactly.
#[test]
fn indexed_engine_matches_osv_scanner() {
use crate::scan::{OsvScanner, ScanEngine};
let db = db();
let policy = Policy {
version: "p1".into(),
..Default::default()
};
let scanner = OsvScanner::new(policy.clone(), db.clone());
let b = IndexedEngine::new(&db);
for a in [
art("cargo", "openssl", "0.1.0"),
art("cargo", "widget", "1.1.0"),
art("npm", "x", "1.0.0"),
] {
assert_eq!(
scanner.scan(&a),
b.verdict(&policy, &a),
"B must equal shipped OsvScanner"
);
}
}
#[test]
fn engine_kind_parses_and_selects() {
assert_eq!(EngineKind::parse("A"), Some(EngineKind::A));
assert_eq!(EngineKind::parse("b"), Some(EngineKind::B));
assert_eq!(EngineKind::parse("linear"), Some(EngineKind::A));
assert_eq!(EngineKind::parse("indexed"), Some(EngineKind::B));
assert_eq!(EngineKind::parse("nope"), None);
assert_eq!(EngineKind::default(), EngineKind::A);
let db = db();
assert_eq!(build(EngineKind::A, &db).kind(), EngineKind::A);
assert_eq!(build(EngineKind::B, &db).kind(), EngineKind::B);
}
/// Case-insensitive bucketing: a query still finds an advisory whose package
/// differs only in case, matching A's behaviour on the same input.
#[test]
fn index_key_is_case_insensitive() {
let db = AdvisoryDb::new(
"r",
vec![Advisory::basic(
"C1",
"cargo",
"OpenSSL",
vec![],
Severity::High,
"x",
)],
);
let a = LinearEngine::new(&db);
let b = IndexedEngine::new(&db);
let q = aref("cargo", "OpenSSL", "1.0.0"); // exact-case: both match
assert_eq!(a.matching(&q).len(), b.matching(&q).len());
}
}