openlatch-client 0.6.6

//! The classification catalogue — AZ-4 D-I16-28, D-I16-29, spec §6.11 and §6.13.
//!
//! The evaluator holds **no lookup table**. What a tool, a program and a target
//! mean arrives in the bundle as one catalogue of three kinds of entry, merged
//! here by union and read by the interpreter in [`super`] and [`super::shell`].
//! What stays in code is logic that is not a lookup (D-I16-30): wrappers, `sudo`
//! recursion, redirections, SQL parsing, the `git` / `gh` / `find` / `docker`
//! rows, shape detection, and the resolver rows that read `Event.env` or facts.
//!
//! # One classification, a filter per artifact
//!
//! The classifier runs **once per action** against the whole catalogue and tags
//! everything it records with the entries that produced it — a [`Tag`]. A tuple
//! can need several entries at once (`cat` and the pattern that makes
//! `~/.ssh/id_rsa` a secret), so a tag is a list of *alternative derivations*,
//! each a conjunction of [`Origin`]s. An artifact then sees a
//! [`Classification::view`]: a tuple counts when one of its derivations lies
//! wholly inside the artifact's [`Scope`]. For every tool or program that has
//! entries the classifier also computes the **fallback** it would get without
//! them (`unknown × shell` and the located tuples), tagged with the origins of
//! those entries; a view includes a fallback only when none of those origins is
//! in scope.
//!
//! The spec's table (§6.13) is the reference for the rule: `tar -cf - ~/.ssh/id_rsa`
//! is `read × secret_material` for an artifact that holds the `tar` entry and
//! `unknown` for one that holds only the seed pattern — so a tuple needs **all**
//! the entries of one derivation, not any one of them.
//!
//! # Merge (D-I16-29)
//!
//! Monotone: for one key the effects and operand roles of every entry are
//! unioned, a path matching several target patterns carries every class, and an
//! entry flagged `narrow` is the only subtraction. A narrow entry applies in
//! every scope and its id is recorded on what remains (`Tag::extra`), never
//! counted as a scope member.

use std::collections::BTreeSet;

use crate::generated::types::{
    CatalogueProgramEntry, CatalogueProgramEntryOperandsValue, CatalogueTargetEntry,
    CatalogueToolEntry, EffectClassEntry, PolicyArtifactCatalogueScope,
    PolicyArtifactCatalogueScopeEntries, PolicyArtifactCatalogueScopeSeedRev,
    PolicyBundleCatalogue, PolicyBundleEffectClasses, T1Leaf,
};

use super::super::types::{
    Classification, ClassifiedPath, Effect, SkippedItem, UnknownCommand, SKIP_BODY_PARSE_ERROR,
};

/// `SkippedItem.kind` for a dropped `catalogue.{tools,programs,targets}[]` entry.
pub const SKIP_KIND_CATALOGUE_ENTRY: &str = "catalogue_entry";

/// Derived verb marker: read from the statement operand by the SQL classifier.
pub const VERB_STATEMENT: &str = "@statement";
/// Derived verb marker: read from the subcommand words of an infrastructure CLI.
pub const VERB_MUTATION: &str = "@mutation";

/// The roles an operand selector may fill (spec §6.11, closed).
pub const ROLES: &[&str] = &["file", "url", "host", "statement", "command"];

/// The roles an `input_map` pointer may map to. The schema lists them as known
/// values, an open set: a role this engine does not know is ignored, never a reason
/// to drop the entry.
pub const INPUT_ROLES: &[&str] = &["url", "file_path", "statement", "command"];

// ── Origins and tags ─────────────────────────────────────────────────

/// What produced an entry: the seed at the revision that added it, or an
/// organization entry by id.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Origin {
    Seed(i64),
    Entry(String),
}

impl Origin {
    /// `seed@<since_rev>` or the entry id — the spelling `oleffects` reports.
    pub fn label(&self) -> String {
        match self {
            Origin::Seed(rev) => format!("seed@{rev}"),
            Origin::Entry(id) => id.clone(),
        }
    }
}

/// One way a recorded item can have come about: every origin in it was needed.
pub type Derivation = Vec<Origin>;
/// Alternative derivations — the item exists if any one of them is in scope.
pub type Derivations = Vec<Derivation>;

/// The derivation of an item that needs no entry at all (a code row).
pub fn always() -> Derivations {
    vec![Vec::new()]
}

/// The product of two alternative sets: each of `a` extended by each of `b`.
pub fn compose(a: &Derivations, b: &Derivations) -> Derivations {
    let mut out: Derivations = Vec::new();
    for left in a {
        for right in b {
            let mut merged: BTreeSet<Origin> = left.iter().cloned().collect();
            merged.extend(right.iter().cloned());
            let merged: Derivation = merged.into_iter().collect();
            if !out.contains(&merged) {
                out.push(merged);
            }
        }
    }
    out
}

/// Alternatives for "needs exactly one of these origins".
pub fn one_of(origins: &[Origin]) -> Derivations {
    if origins.is_empty() {
        return always();
    }
    origins.iter().map(|o| vec![o.clone()]).collect()
}

/// Where one recorded item came from.
#[derive(Debug, Clone, PartialEq)]
pub struct Tag {
    pub derivations: Derivations,
    /// Origins recorded for the report but never needed for the item to count:
    /// the id of a `narrow` entry (D-I16-29), which applies in every scope.
    pub extra: Vec<Origin>,
    /// A located unknown tuple (D-I16-30): recomputed for every view, never copied.
    pub located: bool,
}

impl Default for Tag {
    fn default() -> Self {
        Tag {
            derivations: always(),
            extra: Vec::new(),
            located: false,
        }
    }
}

impl Tag {
    /// Merge another way of producing the same item.
    fn merge(&mut self, other: &Tag) {
        for derivation in &other.derivations {
            if !self.derivations.contains(derivation) {
                self.derivations.push(derivation.clone());
            }
        }
        for origin in &other.extra {
            if !self.extra.contains(origin) {
                self.extra.push(origin.clone());
            }
        }
    }

    /// Whether some derivation lies wholly inside `scope`.
    pub fn in_scope(&self, scope: &Scope) -> bool {
        self.derivations
            .iter()
            .any(|derivation| derivation.iter().all(|origin| scope.contains(origin)))
    }

    /// Every origin involved, sorted and deduplicated — what `oleffects` reports.
    pub fn origins(&self) -> Vec<Origin> {
        let mut all: BTreeSet<Origin> = BTreeSet::new();
        for derivation in &self.derivations {
            all.extend(derivation.iter().cloned());
        }
        all.extend(self.extra.iter().cloned());
        all.into_iter().collect()
    }
}

/// The fallback a tool or program would get without its entries, tagged with the
/// origins of those entries.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct Fallback {
    pub stands_for: Vec<Origin>,
    pub items: Classification,
}

/// Provenance of everything a [`Classification`] holds, parallel to its vectors.
///
/// A missing tag is "needs nothing", so a classification built by hand (tests)
/// behaves as it always did.
#[derive(Debug, Clone, PartialEq)]
pub struct Provenance {
    /// What the item being recorded right now derives from. Set by the
    /// interpreter around the code that records an entry's tuples.
    pub current: Derivations,
    pub current_extra: Vec<Origin>,
    pub effects: Vec<Tag>,
    pub unknown: Vec<Tag>,
    pub paths: Vec<Tag>,
    pub fallbacks: Vec<Fallback>,
}

impl Default for Provenance {
    fn default() -> Self {
        Provenance {
            current: always(),
            current_extra: Vec::new(),
            effects: Vec::new(),
            unknown: Vec::new(),
            paths: Vec::new(),
            fallbacks: Vec::new(),
        }
    }
}

impl Provenance {
    /// The tag a record made now gets.
    pub fn tag_now(&self) -> Tag {
        Tag {
            derivations: self.current.clone(),
            extra: self.current_extra.clone(),
            located: false,
        }
    }

    /// Record `item` under `tag`, merging into an equal item already present.
    pub fn record<T: PartialEq>(items: &mut Vec<T>, tags: &mut Vec<Tag>, item: T, tag: Tag) {
        while tags.len() < items.len() {
            tags.push(Tag::default());
        }
        if let Some(index) = items.iter().position(|existing| *existing == item) {
            tags[index].merge(&tag);
            return;
        }
        items.push(item);
        tags.push(tag);
    }
}

/// What `f` records is tagged as also needing `needs` (alternatives).
pub fn within<R>(
    cls: &mut Classification,
    needs: &Derivations,
    extra: &[Origin],
    f: impl FnOnce(&mut Classification) -> R,
) -> R {
    let saved = (
        cls.provenance.current.clone(),
        cls.provenance.current_extra.clone(),
    );
    cls.provenance.current = compose(&saved.0, needs);
    for origin in extra {
        if !cls.provenance.current_extra.contains(origin) {
            cls.provenance.current_extra.push(origin.clone());
        }
    }
    let out = f(cls);
    cls.provenance.current = saved.0;
    cls.provenance.current_extra = saved.1;
    out
}

// ── Scope ────────────────────────────────────────────────────────────

/// Which seed revision an artifact sees.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SeedRev {
    Latest,
    Rev(i64),
}

/// Which organization entries an artifact sees.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Entries {
    All,
    Ids(Vec<String>),
}

/// An artifact's `catalogue_scope` (spec §6.13).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Scope {
    pub seed_rev: SeedRev,
    pub entries: Entries,
}

impl Scope {
    /// Everything: the scope of an artifact that names none.
    pub fn all() -> Scope {
        Scope {
            seed_rev: SeedRev::Latest,
            entries: Entries::All,
        }
    }

    pub fn from_artifact(scope: Option<&PolicyArtifactCatalogueScope>) -> Scope {
        let Some(scope) = scope else {
            return Scope::all();
        };
        let seed_rev = match &scope.seed_rev {
            Some(PolicyArtifactCatalogueScopeSeedRev::Integer(rev)) => SeedRev::Rev(*rev),
            // `"latest"`, or anything else a future writer spells: the widest
            // reading, which is what an artifact that names no pin gets.
            Some(PolicyArtifactCatalogueScopeSeedRev::String(_)) | None => SeedRev::Latest,
        };
        let entries = match &scope.entries {
            Some(PolicyArtifactCatalogueScopeEntries::Array(ids)) => Entries::Ids(ids.clone()),
            Some(PolicyArtifactCatalogueScopeEntries::String(_)) | None => Entries::All,
        };
        Scope { seed_rev, entries }
    }

    /// Whether this scope sees everything — the view is then the classification.
    pub fn is_all(&self) -> bool {
        self.seed_rev == SeedRev::Latest && self.entries == Entries::All
    }

    pub fn contains(&self, origin: &Origin) -> bool {
        match origin {
            Origin::Seed(rev) => match self.seed_rev {
                SeedRev::Latest => true,
                SeedRev::Rev(pinned) => *rev <= pinned,
            },
            Origin::Entry(id) => match &self.entries {
                Entries::All => true,
                Entries::Ids(ids) => ids.iter().any(|candidate| candidate == id),
            },
        }
    }
}

// ── Entries ──────────────────────────────────────────────────────────

/// `{verb, target_class}` — the class may be `@target` or `@<role>`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EffectSpec {
    pub verb: String,
    pub target_class: String,
}

#[derive(Debug, Clone, PartialEq)]
pub struct ToolEntry {
    pub id: String,
    pub origin: Origin,
    pub key: String,
    pub effects: Vec<EffectSpec>,
    /// `(rfc6901 pointer, role)`, in key order.
    pub input_map: Vec<(String, String)>,
    /// A v2 feed entry's conditions. v3 tool entries carry none.
    pub selectors: Vec<T1Leaf>,
    /// A matching v2 feed entry **claims** the tool: nothing else classifies it.
    /// v3 entries add; they never claim.
    pub claims: bool,
    pub narrow: bool,
}

/// How an operand selector picks values out of a simple command.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Pick {
    All,
    AllButLast,
    Last,
    Nth(usize),
    Flag(String),
    Kv(String),
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Selector {
    pub pick: Pick,
    pub at_file: bool,
    pub local: bool,
}

#[derive(Debug, Clone, PartialEq)]
pub struct ProgramEntry {
    pub id: String,
    pub origin: Origin,
    /// The program followed by its subcommand words.
    pub key: Vec<String>,
    pub effects: Vec<EffectSpec>,
    pub operands: Vec<(String, Vec<Selector>)>,
    pub global_flags: Vec<String>,
    pub narrow: bool,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PatternKind {
    Path,
    Host,
}

#[derive(Debug, Clone, PartialEq)]
pub struct TargetEntry {
    pub id: String,
    pub origin: Origin,
    pub kind: PatternKind,
    pub pattern: String,
    pub target_class: String,
    pub narrow: bool,
}

/// The classification catalogue of one bundle: seed entries and organization
/// entries, in document order.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct Catalogue {
    pub rev: String,
    pub seed_rev: i64,
    pub required_engine_version: Option<String>,
    pub tools: Vec<ToolEntry>,
    pub programs: Vec<ProgramEntry>,
    pub targets: Vec<TargetEntry>,
}

fn origin_of(origin: Option<&str>, since_rev: Option<i64>, id: &str) -> Origin {
    if origin == Some("seed") {
        Origin::Seed(since_rev.unwrap_or(1))
    } else {
        Origin::Entry(id.to_string())
    }
}

fn effect_specs(effects: &[crate::generated::types::CatalogueEffect]) -> Option<Vec<EffectSpec>> {
    effects
        .iter()
        .map(|effect| {
            Some(EffectSpec {
                verb: effect.verb.as_ref()?.0.clone(),
                target_class: effect.target_class.as_ref()?.0.clone(),
            })
        })
        .collect()
}

/// The closed operand grammar of spec §6.11. `None` is anything else.
pub fn parse_selector(text: &str) -> Option<Selector> {
    let mut parts = text.split('+');
    let base = parts.next()?;
    let mut at_file = false;
    let mut local = false;
    for modifier in parts {
        match modifier {
            "at_file" => at_file = true,
            "local" => local = true,
            _ => return None,
        }
    }
    let pick = match base {
        "positional_all" => Pick::All,
        "positional_all_but_last" => Pick::AllButLast,
        "positional_last" => Pick::Last,
        _ => {
            if let Some(n) = base.strip_prefix("positional:") {
                Pick::Nth(n.parse().ok()?)
            } else if let Some(name) = base.strip_prefix("flag:").filter(|n| !n.is_empty()) {
                Pick::Flag(name.to_string())
            } else {
                let key = base.strip_prefix("kv:").filter(|k| !k.is_empty())?;
                Pick::Kv(key.to_string())
            }
        }
    };
    Some(Selector {
        pick,
        at_file,
        local,
    })
}

fn skip(skipped: &mut Vec<SkippedItem>, id: &str) {
    skipped.push(SkippedItem {
        kind: SKIP_KIND_CATALOGUE_ENTRY.to_string(),
        id: id.to_string(),
        reason: SKIP_BODY_PARSE_ERROR.to_string(),
    });
}

impl Catalogue {
    /// Read the bundle's `catalogue` (v3) and its v2 `effect_classes` feed into
    /// one catalogue. An entry the grammar does not allow is skipped into
    /// `skipped[]` and the rest stays active, exactly as a bad artifact is.
    ///
    /// The v2 feed is read as organization `tool` entries (D-2): it keeps its
    /// selectors and its claim-the-tool behaviour, which a v3 entry does not have.
    pub fn from_bundle(
        catalogue: Option<&PolicyBundleCatalogue>,
        feed: Option<&PolicyBundleEffectClasses>,
        skipped: &mut Vec<SkippedItem>,
    ) -> Option<Catalogue> {
        if catalogue.is_none() && feed.is_none() {
            return None;
        }
        let mut out = Catalogue::default();
        if let Some(raw) = catalogue {
            out.rev = raw.catalogue_rev.clone().unwrap_or_default();
            out.seed_rev = raw.seed_rev.unwrap_or(0);
            out.required_engine_version = raw.required_engine_version.clone();
            for (index, entry) in raw.tools.iter().enumerate() {
                match tool_entry(entry, index) {
                    Some(parsed) => out.tools.push(parsed),
                    None => skip(skipped, entry.id.as_deref().unwrap_or("")),
                }
            }
            for (index, entry) in raw.programs.iter().enumerate() {
                match program_entry(entry, index) {
                    Some(parsed) => out.programs.push(parsed),
                    None => skip(skipped, entry.id.as_deref().unwrap_or("")),
                }
            }
            for (index, entry) in raw.targets.iter().enumerate() {
                match target_entry(entry, index) {
                    Some(parsed) => out.targets.push(parsed),
                    None => skip(skipped, entry.id.as_deref().unwrap_or("")),
                }
            }
        }
        if let Some(feed) = feed {
            for (index, entry) in feed.entries.iter().enumerate() {
                if let Some(parsed) = feed_entry(entry, index) {
                    out.tools.push(parsed);
                }
            }
        }
        Some(out)
    }

    /// Every tool entry for `tool`, in catalogue order (narrow ones included).
    pub fn tool_entries<'a>(&'a self, tool: &str) -> Vec<&'a ToolEntry> {
        self.tools
            .iter()
            .filter(|entry| entry.key == tool)
            .collect()
    }
}

fn tool_entry(raw: &CatalogueToolEntry, index: usize) -> Option<ToolEntry> {
    let key = raw.key.clone().filter(|k| !k.is_empty())?;
    let id = raw
        .id
        .clone()
        .unwrap_or_else(|| format!("tool:{key}#{index}"));
    let mut input_map: Vec<(String, String)> = Vec::new();
    for (pointer, role) in &raw.input_map {
        if INPUT_ROLES.contains(&role.as_str()) {
            input_map.push((pointer.clone(), role.clone()));
        }
    }
    input_map.sort();
    Some(ToolEntry {
        origin: origin_of(raw.origin.as_deref(), raw.since_rev, &id),
        id,
        key,
        effects: effect_specs(&raw.effects)?,
        input_map,
        selectors: Vec::new(),
        claims: false,
        narrow: raw.narrow.unwrap_or(false),
    })
}

fn feed_entry(raw: &EffectClassEntry, index: usize) -> Option<ToolEntry> {
    let key = raw.tool_key.clone().filter(|k| !k.is_empty())?;
    let id = raw
        .id
        .clone()
        .filter(|id| !id.is_empty())
        .unwrap_or_else(|| format!("feed:{key}#{index}"));
    // The feed's own tuples default a missing verb to `unknown` and a missing
    // class to `shell`, as the lookup always did.
    let effects = raw
        .effects
        .iter()
        .map(|tuple| EffectSpec {
            verb: tuple
                .verb
                .as_ref()
                .map(|v| v.0.clone())
                .unwrap_or_else(|| "unknown".to_string()),
            target_class: tuple
                .target_class
                .as_ref()
                .map(|t| t.0.clone())
                .unwrap_or_else(|| "shell".to_string()),
        })
        .collect();
    Some(ToolEntry {
        origin: Origin::Entry(id.clone()),
        id,
        key,
        effects,
        input_map: Vec::new(),
        selectors: raw.selectors.clone(),
        claims: true,
        narrow: false,
    })
}

fn program_entry(raw: &CatalogueProgramEntry, index: usize) -> Option<ProgramEntry> {
    let key_text = raw.key.clone().filter(|k| !k.trim().is_empty())?;
    let key: Vec<String> = key_text.split_whitespace().map(str::to_string).collect();
    let id = raw
        .id
        .clone()
        .unwrap_or_else(|| format!("prog:{key_text}#{index}"));
    let mut operands: Vec<(String, Vec<Selector>)> = Vec::new();
    for (role, value) in &raw.operands {
        if !ROLES.contains(&role.as_str()) {
            return None;
        }
        let texts: Vec<&String> = match value {
            CatalogueProgramEntryOperandsValue::String(text) => vec![text],
            CatalogueProgramEntryOperandsValue::Array(items) => items.iter().collect(),
        };
        let selectors: Option<Vec<Selector>> =
            texts.iter().map(|text| parse_selector(text)).collect();
        operands.push((role.clone(), selectors?));
    }
    operands.sort_by(|a, b| a.0.cmp(&b.0));
    Some(ProgramEntry {
        origin: origin_of(raw.origin.as_deref(), raw.since_rev, &id),
        id,
        key,
        effects: effect_specs(&raw.effects)?,
        operands,
        global_flags: raw.global_flags.clone(),
        narrow: raw.narrow.unwrap_or(false),
    })
}

fn target_entry(raw: &CatalogueTargetEntry, index: usize) -> Option<TargetEntry> {
    let pattern = raw.key.clone().filter(|k| !k.is_empty())?;
    let target_class = raw.target_class.as_ref()?.0.clone();
    let id = raw
        .id
        .clone()
        .unwrap_or_else(|| format!("tgt:{pattern}#{index}"));
    let kind = match raw.pattern_kind.as_deref() {
        Some("path") => PatternKind::Path,
        Some("host") => PatternKind::Host,
        _ => return None,
    };
    Some(TargetEntry {
        origin: origin_of(raw.origin.as_deref(), raw.since_rev, &id),
        id,
        kind,
        pattern,
        target_class,
        narrow: raw.narrow.unwrap_or(false),
    })
}

// ── Program lookup and merge ─────────────────────────────────────────

/// One merged effect: the spec and every entry that declared it.
#[derive(Debug, Clone, PartialEq)]
pub struct MergedEffect {
    pub spec: EffectSpec,
    pub origins: Vec<Origin>,
}

/// One merged operand selector and the entry it came from.
#[derive(Debug, Clone, PartialEq)]
pub struct MergedSelector {
    pub selector: Selector,
    pub origin: Origin,
}

/// What a program key resolved to once its entries are merged.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct ProgramHit {
    pub effects: Vec<MergedEffect>,
    pub operands: Vec<(String, Vec<MergedSelector>)>,
    /// Every entry of the key, narrow ones included.
    pub stands_for: Vec<Origin>,
    /// The ids of `narrow` entries, applied in every scope.
    pub narrowed_by: Vec<Origin>,
    /// An entry that says *nothing but* "this program is benign" — no effect, no
    /// operand, no flag. An entry that only carries `global_flags` classifies
    /// nothing and must not silence the unknown it would otherwise be.
    pub benign: bool,
}

/// The result of looking a simple command up among the program entries.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct ProgramLookup {
    pub hit: Option<ProgramHit>,
    /// Entries of a multi-word key that was abandoned at an option that is not a
    /// listed global flag: the action is unreadable and carries its located
    /// unknown tuples.
    pub unlisted_option: Vec<Origin>,
}

enum KeyMatch {
    Matched,
    Missed,
    UnlistedOption,
}

/// Match the subcommand words of `key[1..]` against `argv`, skipping the listed
/// global flags (`-f v`, `--flag v`, `--flag=v`) and any `--flag=v` token.
fn match_key(key: &[String], argv: &[String], global_flags: &[&str]) -> KeyMatch {
    let mut at = 0usize;
    for word in &key[1..] {
        loop {
            let Some(token) = argv.get(at) else {
                return KeyMatch::Missed;
            };
            if !token.starts_with('-') {
                break;
            }
            if token.contains('=') {
                at += 1;
                continue;
            }
            if global_flags.contains(&token.as_str()) {
                at += 2;
                continue;
            }
            return KeyMatch::UnlistedOption;
        }
        if &argv[at] != word {
            return KeyMatch::Missed;
        }
        at += 1;
    }
    KeyMatch::Matched
}

impl Catalogue {
    /// Look a simple command up: the longest matching key wins, and the entries
    /// of that exact key are merged by union with `narrow` entries subtracted.
    pub fn lookup_program(&self, program: &str, argv: &[String]) -> ProgramLookup {
        let of_program: Vec<&ProgramEntry> = self
            .programs
            .iter()
            .filter(|entry| entry.key.first().map(String::as_str) == Some(program))
            .collect();
        if of_program.is_empty() {
            return ProgramLookup::default();
        }
        let mut flags: Vec<&str> = Vec::new();
        for entry in &of_program {
            for flag in &entry.global_flags {
                if !flags.contains(&flag.as_str()) {
                    flags.push(flag);
                }
            }
        }
        let mut keys: Vec<&Vec<String>> = Vec::new();
        for entry in &of_program {
            if !keys.contains(&&entry.key) {
                keys.push(&entry.key);
            }
        }
        // Longest first; document order breaks ties so two implementations agree.
        let mut ordered: Vec<(usize, &Vec<String>)> = keys.into_iter().enumerate().collect();
        ordered.sort_by(|a, b| b.1.len().cmp(&a.1.len()).then(a.0.cmp(&b.0)));

        let mut unlisted: Vec<Origin> = Vec::new();
        for (_, key) in ordered {
            match match_key(key, argv, &flags) {
                KeyMatch::Matched => {
                    let entries: Vec<&ProgramEntry> = of_program
                        .iter()
                        .copied()
                        .filter(|e| &e.key == key)
                        .collect();
                    return ProgramLookup {
                        hit: Some(merge_programs(&entries)),
                        unlisted_option: unlisted,
                    };
                }
                KeyMatch::UnlistedOption => {
                    for entry in of_program.iter().filter(|e| &e.key == key) {
                        if !unlisted.contains(&entry.origin) {
                            unlisted.push(entry.origin.clone());
                        }
                    }
                }
                KeyMatch::Missed => {}
            }
        }
        ProgramLookup {
            hit: None,
            unlisted_option: unlisted,
        }
    }
}

fn merge_programs(entries: &[&ProgramEntry]) -> ProgramHit {
    let mut hit = ProgramHit::default();
    let narrow_specs: Vec<&EffectSpec> = entries
        .iter()
        .filter(|e| e.narrow)
        .flat_map(|e| e.effects.iter())
        .collect();
    for entry in entries {
        if !hit.stands_for.contains(&entry.origin) {
            hit.stands_for.push(entry.origin.clone());
        }
        if entry.narrow {
            if !hit.narrowed_by.contains(&entry.origin) {
                hit.narrowed_by.push(entry.origin.clone());
            }
            continue;
        }
        if entry.effects.is_empty() && entry.operands.is_empty() && entry.global_flags.is_empty() {
            hit.benign = true;
        }
        for spec in &entry.effects {
            if narrow_specs.contains(&spec) {
                continue;
            }
            match hit.effects.iter_mut().find(|m| m.spec == *spec) {
                Some(existing) => {
                    if !existing.origins.contains(&entry.origin) {
                        existing.origins.push(entry.origin.clone());
                    }
                }
                None => hit.effects.push(MergedEffect {
                    spec: spec.clone(),
                    origins: vec![entry.origin.clone()],
                }),
            }
        }
        for (role, selectors) in &entry.operands {
            let slot = match hit.operands.iter().position(|(name, _)| name == role) {
                Some(index) => &mut hit.operands[index],
                None => {
                    hit.operands.push((role.clone(), Vec::new()));
                    hit.operands.last_mut().expect("just pushed")
                }
            };
            for selector in selectors {
                let merged = MergedSelector {
                    selector: selector.clone(),
                    origin: entry.origin.clone(),
                };
                if !slot.1.contains(&merged) {
                    slot.1.push(merged);
                }
            }
        }
    }
    hit
}

/// Merge the effects of the tool entries that claimed one call (narrow ones
/// subtract, in every scope).
pub fn merge_tool_effects(entries: &[&ToolEntry]) -> (Vec<MergedEffect>, Vec<Origin>) {
    let narrow_specs: Vec<&EffectSpec> = entries
        .iter()
        .filter(|e| e.narrow)
        .flat_map(|e| e.effects.iter())
        .collect();
    let narrowed_by: Vec<Origin> = entries
        .iter()
        .filter(|e| e.narrow)
        .map(|e| e.origin.clone())
        .collect();
    let mut merged: Vec<MergedEffect> = Vec::new();
    for entry in entries.iter().filter(|e| !e.narrow) {
        for spec in &entry.effects {
            if narrow_specs.contains(&spec) {
                continue;
            }
            match merged.iter_mut().find(|m| m.spec == *spec) {
                Some(existing) => {
                    if !existing.origins.contains(&entry.origin) {
                        existing.origins.push(entry.origin.clone());
                    }
                }
                None => merged.push(MergedEffect {
                    spec: spec.clone(),
                    origins: vec![entry.origin.clone()],
                }),
            }
        }
    }
    (merged, narrowed_by)
}

// ── Operand selection ────────────────────────────────────────────────

/// The non-flag arguments — the positional operands of a command.
pub fn positionals(argv: &[String]) -> Vec<String> {
    argv.iter()
        .filter(|a| !a.starts_with('-'))
        .cloned()
        .collect()
}

/// Every value of `--flag value`, `-f value` and `--flag=value` in `argv`.
fn flag_values(argv: &[String], name: &str) -> Vec<String> {
    let mut out = Vec::new();
    let prefix = format!("{name}=");
    for (i, arg) in argv.iter().enumerate() {
        if arg == name {
            if let Some(value) = argv.get(i + 1) {
                out.push(value.clone());
            }
        } else if let Some(value) = arg.strip_prefix(&prefix) {
            out.push(value.to_string());
        }
    }
    out
}

/// A value after a leading `@` or `<`, or after `key=@` / `key=<`.
fn at_file_target(value: &str) -> Option<String> {
    let after = match value.split_once('=') {
        Some((_, rest)) if rest.starts_with('@') || rest.starts_with('<') => rest,
        _ => value,
    };
    after
        .strip_prefix('@')
        .or_else(|| after.strip_prefix('<'))
        .filter(|rest| !rest.is_empty())
        .map(str::to_string)
}

/// `host:path` and URL values — what `+local` skips.
fn is_remote(value: &str) -> bool {
    if value.contains("://") {
        return true;
    }
    match value.split_once(':') {
        Some((head, _)) => !head.is_empty() && !head.contains('/') && !head.starts_with('.'),
        None => false,
    }
}

/// The values one selector picks out of `argv`.
pub fn select(argv: &[String], selector: &Selector) -> Vec<String> {
    let positional = positionals(argv);
    let mut values: Vec<String> = match &selector.pick {
        Pick::All => positional,
        Pick::AllButLast => positional[..positional.len().saturating_sub(1)].to_vec(),
        Pick::Last => positional.last().cloned().into_iter().collect(),
        Pick::Nth(n) => positional.get(*n).cloned().into_iter().collect(),
        Pick::Flag(name) => flag_values(argv, name),
        Pick::Kv(key) => {
            let prefix = format!("{key}=");
            positional
                .iter()
                .filter_map(|p| p.strip_prefix(&prefix).map(str::to_string))
                .collect()
        }
    };
    if selector.at_file {
        values = values.iter().filter_map(|v| at_file_target(v)).collect();
    }
    if selector.local {
        values.retain(|v| !is_remote(v));
    }
    values
}

// ── Host patterns ────────────────────────────────────────────────────

/// A host pattern against a host, case-insensitively; `*` matches any run.
pub fn host_matches(pattern: &str, host: &str) -> bool {
    super::path::glob_match(&pattern.to_lowercase(), &host.to_lowercase())
}

// ── The view ─────────────────────────────────────────────────────────

impl Classification {
    /// What an artifact whose catalogue scope is `scope` sees of this
    /// classification (spec §6.13): the tuples whose derivation lies inside the
    /// scope, plus the fallback of every tool or program whose entries are all
    /// outside it, and the located unknown tuples recomputed over the result.
    pub fn view(&self, scope: &Scope) -> Classification {
        let mut out = Classification {
            simple: self.simple.clone(),
            urls: self.urls.clone(),
            ..Classification::default()
        };
        self.merge_into(&mut out, scope);
        for fallback in &self.provenance.fallbacks {
            if fallback
                .stands_for
                .iter()
                .any(|origin| scope.contains(origin))
            {
                continue;
            }
            fallback.items.merge_into(&mut out, scope);
            for url in &fallback.items.urls {
                if !out.urls.contains(url) {
                    out.urls.push(url.clone());
                }
            }
        }
        super::add_located_unknown(&mut out);
        out
    }

    fn merge_into(&self, out: &mut Classification, scope: &Scope) {
        let tag_of = |tags: &[Tag], i: usize| tags.get(i).cloned().unwrap_or_default();
        for (i, effect) in self.effects.iter().enumerate() {
            let tag = tag_of(&self.provenance.effects, i);
            if tag.located || !tag.in_scope(scope) {
                continue;
            }
            record_effect(out, effect.clone(), Tag::default());
        }
        for (i, unknown) in self.unknown.iter().enumerate() {
            let tag = tag_of(&self.provenance.unknown, i);
            if !tag.in_scope(scope) {
                continue;
            }
            record_unknown(out, unknown.clone(), Tag::default());
        }
        for (i, path) in self.paths.iter().enumerate() {
            let tag = tag_of(&self.provenance.paths, i);
            if !tag.in_scope(scope) {
                continue;
            }
            record_path_tagged(out, path.clone(), Tag::default());
        }
    }

    /// Every tuple with the origins that produced it, for the decision event's
    /// `oleffects` — the full classification, whatever scope decided.
    pub fn tuples_with_origins(&self) -> Vec<(Effect, Vec<Origin>)> {
        self.effects
            .iter()
            .enumerate()
            .map(|(i, effect)| {
                let origins = self
                    .provenance
                    .effects
                    .get(i)
                    .map(Tag::origins)
                    .unwrap_or_default();
                (effect.clone(), origins)
            })
            .collect()
    }
}

/// Append `effect` to `cls`, merging into an equal tuple.
pub fn record_effect(cls: &mut Classification, effect: Effect, tag: Tag) {
    Provenance::record(&mut cls.effects, &mut cls.provenance.effects, effect, tag);
}

pub fn record_unknown(cls: &mut Classification, unknown: UnknownCommand, tag: Tag) {
    Provenance::record(&mut cls.unknown, &mut cls.provenance.unknown, unknown, tag);
}

pub fn record_path_tagged(cls: &mut Classification, path: ClassifiedPath, tag: Tag) {
    Provenance::record(&mut cls.paths, &mut cls.provenance.paths, path, tag);
}

/// Test-only: the seed-r1 fixture the tables used to be, read as a catalogue.
#[cfg(test)]
pub mod fixtures {
    use super::*;

    /// `schemas/contracts/policy_bundle/seed-r1.json`, parsed once.
    pub fn seed_r1() -> &'static Catalogue {
        static SEED: std::sync::OnceLock<Catalogue> = std::sync::OnceLock::new();
        SEED.get_or_init(|| {
            let raw: PolicyBundleCatalogue = serde_json::from_str(include_str!(
                "../../../schemas/contracts/policy_bundle/seed-r1.json"
            ))
            .expect("the fixture parses");
            Catalogue::from_bundle(Some(&raw), None, &mut Vec::new()).expect("a catalogue")
        })
    }

    /// The fixture plus `extra` entries, as a leaked reference a test can hold.
    pub fn seed_r1_plus(extra: serde_json::Value) -> &'static Catalogue {
        let mut doc: serde_json::Value = serde_json::from_str(include_str!(
            "../../../schemas/contracts/policy_bundle/seed-r1.json"
        ))
        .expect("the fixture parses");
        for kind in ["tools", "programs", "targets"] {
            if let Some(items) = extra.get(kind).and_then(serde_json::Value::as_array) {
                doc[kind]
                    .as_array_mut()
                    .expect("a list")
                    .extend(items.iter().cloned());
            }
        }
        let raw: PolicyBundleCatalogue = serde_json::from_value(doc).expect("parses");
        let catalogue =
            Catalogue::from_bundle(Some(&raw), None, &mut Vec::new()).expect("a catalogue");
        Box::leak(Box::new(catalogue))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn strings(items: &[&str]) -> Vec<String> {
        items.iter().map(|s| s.to_string()).collect()
    }

    #[test]
    fn the_operand_grammar_is_closed() {
        for ok in [
            "positional_all",
            "positional_all_but_last+local",
            "positional_last",
            "positional:2",
            "flag:-d+at_file",
            "flag:--post-file",
            "kv:if",
        ] {
            assert!(parse_selector(ok).is_some(), "{ok}");
        }
        for bad in [
            "positional",
            "flag:",
            "kv:",
            "positional:x",
            "all",
            "flag:-d+x",
        ] {
            assert!(parse_selector(bad).is_none(), "{bad}");
        }
    }

    #[test]
    fn a_flag_takes_three_spellings_and_at_file_keeps_only_marked_values() {
        let argv = strings(&[
            "-d",
            "@a.json",
            "--data=@b.json",
            "-d",
            "plain",
            "-F",
            "f=@c",
        ]);
        let at = |flag: &str| Selector {
            pick: Pick::Flag(flag.to_string()),
            at_file: true,
            local: false,
        };
        assert_eq!(select(&argv, &at("-d")), vec!["a.json"]);
        assert_eq!(select(&argv, &at("--data")), vec!["b.json"]);
        assert_eq!(select(&argv, &at("-F")), vec!["c"]);
    }

    #[test]
    fn local_skips_host_paths_and_urls() {
        let argv = strings(&["./a", "deploy@h:/srv", "https://x/y", "/tmp/b", "h2:b"]);
        let sel = parse_selector("positional_all+local").unwrap();
        assert_eq!(select(&argv, &sel), vec!["./a", "/tmp/b"]);
    }

    #[test]
    fn positionals_count_from_zero_and_the_last_is_the_last() {
        let argv = strings(&["-n", "a", "b", "c"]);
        let pick = |text: &str| select(&argv, &parse_selector(text).unwrap());
        assert_eq!(pick("positional:0"), vec!["a"]);
        assert_eq!(pick("positional:2"), vec!["c"]);
        assert_eq!(pick("positional_last"), vec!["c"]);
        assert_eq!(pick("positional_all_but_last"), vec!["a", "b"]);
    }

    #[test]
    fn an_origin_counts_inside_its_pinned_scope_only() {
        let scope = Scope {
            seed_rev: SeedRev::Rev(2),
            entries: Entries::Ids(vec!["a".to_string()]),
        };
        assert!(scope.contains(&Origin::Seed(1)));
        assert!(scope.contains(&Origin::Seed(2)));
        assert!(!scope.contains(&Origin::Seed(3)));
        assert!(scope.contains(&Origin::Entry("a".into())));
        assert!(!scope.contains(&Origin::Entry("b".into())));
        assert!(Scope::all().contains(&Origin::Seed(99)));
    }

    #[test]
    fn a_derivation_needs_every_origin_in_it() {
        let tag = Tag {
            derivations: vec![vec![Origin::Seed(1), Origin::Entry("tar".into())]],
            extra: Vec::new(),
            located: false,
        };
        let strict = Scope {
            seed_rev: SeedRev::Rev(2),
            entries: Entries::Ids(Vec::new()),
        };
        assert!(!tag.in_scope(&strict), "the tar entry is out of scope");
        assert!(tag.in_scope(&Scope::all()));
    }

    #[test]
    fn composing_alternatives_is_a_product() {
        let a = vec![vec![Origin::Seed(1)], vec![Origin::Entry("x".into())]];
        let b = vec![vec![Origin::Seed(2)]];
        assert_eq!(
            compose(&a, &b),
            vec![
                vec![Origin::Seed(1), Origin::Seed(2)],
                vec![Origin::Seed(2), Origin::Entry("x".into())],
            ]
        );
        assert_eq!(compose(&always(), &b), b);
    }
}