boundgraph_grant/
normalize.rs

1//! Normalisation to an antichain.
2//!
3//! A grant set is *normal* when no atom in it is permitted by another. Without
4//! that, `{fs:read:/src/**, fs:read:/src/lib/**}` and `{fs:read:/src/**}` are
5//! different values with identical meaning, and every downstream comparison
6//! has to re-derive that fact.
7//!
8//! Normalising once makes equality structural: two sets that permit the same
9//! things become the same value, and therefore share a digest.
10
11use boundgraph_core::{GrantAtom, GrantSet};
12
13use crate::order::atom_leq;
14use crate::pattern::Tri;
15
16/// Remove every atom that another atom in the set already permits.
17///
18/// Only a **definite** containment removes an atom. Where the solver returns
19/// [`Tri::Unknown`] both atoms are kept: dropping one on an undecided answer
20/// would silently narrow the set, and quietly losing a permission is as much a
21/// bug as quietly gaining one.
22///
23/// This is why templates survive alongside concrete atoms — `fs:read:{path}`
24/// and `fs:read:/src/**` are undecidable against each other, so neither
25/// absorbs the other.
26pub fn normalize(set: &GrantSet) -> GrantSet {
27    let atoms: Vec<&GrantAtom> = set.iter().collect();
28
29    let kept = atoms.iter().enumerate().filter_map(|(i, a)| {
30        let dominated = atoms.iter().enumerate().any(|(j, b)| {
31            if i == j {
32                return false;
33            }
34            match (atom_leq(a, b), atom_leq(b, a)) {
35                // Equal denotations spelled differently (`/src` and `/src/`).
36                // Keep exactly one: the first in the set's own ordering.
37                (Tri::Yes, Tri::Yes) => j < i,
38                // Strictly permitted by `b`, so `a` adds nothing.
39                (Tri::Yes, _) => true,
40                _ => false,
41            }
42        });
43        (!dominated).then(|| (*a).clone())
44    });
45
46    GrantSet::new(kept)
47}
48
49/// Whether the set is already an antichain.
50pub fn is_normal(set: &GrantSet) -> bool {
51    normalize(set) == *set
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use crate::order::set_eq;
58
59    fn set(atoms: &[&str]) -> GrantSet {
60        GrantSet::parse(atoms.iter().copied()).expect("test set should parse")
61    }
62
63    #[test]
64    fn a_contained_atom_is_removed() {
65        let g = set(&["fs:read:/src/**", "fs:read:/src/lib/a.rs"]);
66        assert_eq!(normalize(&g), set(&["fs:read:/src/**"]));
67    }
68
69    #[test]
70    fn unrelated_atoms_all_survive() {
71        let g = set(&[
72            "fs:read:/src/**",
73            "fs:write:/build/**",
74            "net:egress:api.example.com:443",
75        ]);
76        assert_eq!(normalize(&g), g);
77    }
78
79    #[test]
80    fn normalisation_is_idempotent() {
81        let g = set(&[
82            "fs:read:/src/**",
83            "fs:read:/src/lib/a.rs",
84            "fs:read:/src/lib",
85            "fs:write:/build/**",
86        ]);
87        let once = normalize(&g);
88        assert_eq!(normalize(&once), once);
89        assert!(is_normal(&once));
90    }
91
92    #[test]
93    fn meaning_is_preserved() {
94        let g = set(&["fs:read:/src/**", "fs:read:/src/lib/a.rs"]);
95        assert_eq!(set_eq(&normalize(&g), &g), Tri::Yes);
96    }
97
98    #[test]
99    fn equal_denotations_collapse_to_exactly_one() {
100        // `/src` and `/src/` mean the same thing; keeping both would leave a
101        // set that is not an antichain, keeping neither would lose the grant.
102        let g = set(&["fs:read:/src", "fs:read:/src/"]);
103        assert_eq!(g.len(), 2, "they are distinct as strings");
104
105        let n = normalize(&g);
106        assert_eq!(n.len(), 1, "but one denotation, so one atom survives");
107        assert_eq!(set_eq(&n, &g), Tri::Yes);
108        assert!(is_normal(&n));
109    }
110
111    #[test]
112    fn templates_are_never_merged_with_concrete_atoms() {
113        // Undecidable against each other, so neither may absorb the other.
114        let g = set(&["fs:read:/src/**", "fs:read:{path}"]);
115        assert_eq!(
116            normalize(&g),
117            g,
118            "an undecided comparison must not drop a permission"
119        );
120    }
121
122    #[test]
123    fn an_undecidable_pair_keeps_both_atoms() {
124        let g = set(&["fs:read:/src/*.rs", "fs:read:/src/main.rs"]);
125        assert_eq!(normalize(&g).len(), 2);
126    }
127
128    #[test]
129    fn the_empty_set_normalises_to_itself() {
130        assert_eq!(normalize(&GrantSet::EMPTY), GrantSet::EMPTY);
131        assert!(is_normal(&GrantSet::EMPTY));
132    }
133
134    #[test]
135    fn read_and_write_of_the_same_path_both_survive() {
136        // Different actions are incomparable, so neither absorbs the other.
137        let g = set(&["fs:read:/src/**", "fs:write:/src/**"]);
138        assert_eq!(normalize(&g), g);
139    }
140
141    #[test]
142    fn a_chain_collapses_to_its_top() {
143        let g = set(&[
144            "fs:read:/**",
145            "fs:read:/src/**",
146            "fs:read:/src/lib/**",
147            "fs:read:/src/lib/a.rs",
148        ]);
149        assert_eq!(normalize(&g), set(&["fs:read:/**"]));
150    }
151
152    #[test]
153    fn ordering_is_deterministic() {
154        let a = set(&["fs:read:/b", "fs:read:/a", "fs:read:/c"]);
155        let b = set(&["fs:read:/c", "fs:read:/a", "fs:read:/b"]);
156        assert_eq!(normalize(&a), normalize(&b));
157        assert_eq!(
158            normalize(&a).iter().collect::<Vec<_>>(),
159            normalize(&b).iter().collect::<Vec<_>>()
160        );
161    }
162}
boundgraph_grant/normalize.rs

boundgraph_grant/
normalize.rs
