boundgraph-grant 0.1.0

//! Normalisation to an antichain.
//!
//! A grant set is *normal* when no atom in it is permitted by another. Without
//! that, `{fs:read:/src/**, fs:read:/src/lib/**}` and `{fs:read:/src/**}` are
//! different values with identical meaning, and every downstream comparison
//! has to re-derive that fact.
//!
//! Normalising once makes equality structural: two sets that permit the same
//! things become the same value, and therefore share a digest.

use boundgraph_core::{GrantAtom, GrantSet};

use crate::order::atom_leq;
use crate::pattern::Tri;

/// Remove every atom that another atom in the set already permits.
///
/// Only a **definite** containment removes an atom. Where the solver returns
/// [`Tri::Unknown`] both atoms are kept: dropping one on an undecided answer
/// would silently narrow the set, and quietly losing a permission is as much a
/// bug as quietly gaining one.
///
/// This is why templates survive alongside concrete atoms — `fs:read:{path}`
/// and `fs:read:/src/**` are undecidable against each other, so neither
/// absorbs the other.
pub fn normalize(set: &GrantSet) -> GrantSet {
    let atoms: Vec<&GrantAtom> = set.iter().collect();

    let kept = atoms.iter().enumerate().filter_map(|(i, a)| {
        let dominated = atoms.iter().enumerate().any(|(j, b)| {
            if i == j {
                return false;
            }
            match (atom_leq(a, b), atom_leq(b, a)) {
                // Equal denotations spelled differently (`/src` and `/src/`).
                // Keep exactly one: the first in the set's own ordering.
                (Tri::Yes, Tri::Yes) => j < i,
                // Strictly permitted by `b`, so `a` adds nothing.
                (Tri::Yes, _) => true,
                _ => false,
            }
        });
        (!dominated).then(|| (*a).clone())
    });

    GrantSet::new(kept)
}

/// Whether the set is already an antichain.
pub fn is_normal(set: &GrantSet) -> bool {
    normalize(set) == *set
}

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

    fn set(atoms: &[&str]) -> GrantSet {
        GrantSet::parse(atoms.iter().copied()).expect("test set should parse")
    }

    #[test]
    fn a_contained_atom_is_removed() {
        let g = set(&["fs:read:/src/**", "fs:read:/src/lib/a.rs"]);
        assert_eq!(normalize(&g), set(&["fs:read:/src/**"]));
    }

    #[test]
    fn unrelated_atoms_all_survive() {
        let g = set(&[
            "fs:read:/src/**",
            "fs:write:/build/**",
            "net:egress:api.example.com:443",
        ]);
        assert_eq!(normalize(&g), g);
    }

    #[test]
    fn normalisation_is_idempotent() {
        let g = set(&[
            "fs:read:/src/**",
            "fs:read:/src/lib/a.rs",
            "fs:read:/src/lib",
            "fs:write:/build/**",
        ]);
        let once = normalize(&g);
        assert_eq!(normalize(&once), once);
        assert!(is_normal(&once));
    }

    #[test]
    fn meaning_is_preserved() {
        let g = set(&["fs:read:/src/**", "fs:read:/src/lib/a.rs"]);
        assert_eq!(set_eq(&normalize(&g), &g), Tri::Yes);
    }

    #[test]
    fn equal_denotations_collapse_to_exactly_one() {
        // `/src` and `/src/` mean the same thing; keeping both would leave a
        // set that is not an antichain, keeping neither would lose the grant.
        let g = set(&["fs:read:/src", "fs:read:/src/"]);
        assert_eq!(g.len(), 2, "they are distinct as strings");

        let n = normalize(&g);
        assert_eq!(n.len(), 1, "but one denotation, so one atom survives");
        assert_eq!(set_eq(&n, &g), Tri::Yes);
        assert!(is_normal(&n));
    }

    #[test]
    fn templates_are_never_merged_with_concrete_atoms() {
        // Undecidable against each other, so neither may absorb the other.
        let g = set(&["fs:read:/src/**", "fs:read:{path}"]);
        assert_eq!(
            normalize(&g),
            g,
            "an undecided comparison must not drop a permission"
        );
    }

    #[test]
    fn an_undecidable_pair_keeps_both_atoms() {
        let g = set(&["fs:read:/src/*.rs", "fs:read:/src/main.rs"]);
        assert_eq!(normalize(&g).len(), 2);
    }

    #[test]
    fn the_empty_set_normalises_to_itself() {
        assert_eq!(normalize(&GrantSet::EMPTY), GrantSet::EMPTY);
        assert!(is_normal(&GrantSet::EMPTY));
    }

    #[test]
    fn read_and_write_of_the_same_path_both_survive() {
        // Different actions are incomparable, so neither absorbs the other.
        let g = set(&["fs:read:/src/**", "fs:write:/src/**"]);
        assert_eq!(normalize(&g), g);
    }

    #[test]
    fn a_chain_collapses_to_its_top() {
        let g = set(&[
            "fs:read:/**",
            "fs:read:/src/**",
            "fs:read:/src/lib/**",
            "fs:read:/src/lib/a.rs",
        ]);
        assert_eq!(normalize(&g), set(&["fs:read:/**"]));
    }

    #[test]
    fn ordering_is_deterministic() {
        let a = set(&["fs:read:/b", "fs:read:/a", "fs:read:/c"]);
        let b = set(&["fs:read:/c", "fs:read:/a", "fs:read:/b"]);
        assert_eq!(normalize(&a), normalize(&b));
        assert_eq!(
            normalize(&a).iter().collect::<Vec<_>>(),
            normalize(&b).iter().collect::<Vec<_>>()
        );
    }
}