boundgraph-grant 0.1.0

//! Meet (`⊓`) and join (`⊔`).
//!
//! Both operations exist to serve the compiler:
//!
//! - **Join** computes an authority *envelope*. A `route` node's envelope is
//!   the join of its arms' grants, fixed before the run so a dynamic branch
//!   choice can never exceed what was approved (US-0405).
//! - **Meet** *clamps*. When a template atom resolves at runtime, the resolved
//!   value is met with the static envelope, so the dynamic value can only ever
//!   narrow the grant, never widen it. That is Law I as a mechanism.
//!
//! # Both operations are exact
//!
//! Join is exact for the obvious reason: the union of two sets of permissions
//! is itself a set of permissions, and normalising it loses nothing.
//!
//! Meet is exact for a less obvious one — the decidable pattern fragment turns
//! out to be **closed under intersection**. A literal meets `*` as that
//! literal, `*` meets `*` as `*`, and a trailing `**` contributes whatever the
//! other side still requires. So `/a/*` and `/*/b` intersect to exactly
//! `/a/b`, with nothing approximated away.
//!
//! That matters more than it looks. An earlier version took the narrower of
//! two comparable atoms and dropped everything else, which is a sound lower
//! bound but **not associative**: `/*` and `/a/**` are incomparable yet share
//! `/a`, so grouping the operands differently gave different answers. The
//! property suite in `tests/lattice_laws.rs` found it, and the counterexample
//! is kept in the regression corpus there.
//!
//! Undecidable pairs are still dropped rather than guessed at, so meet remains
//! sound in the fragment's blind spots: a clamp that is too tight fails closed.

use boundgraph_core::{GrantAtom, GrantSet};

use crate::normalize::normalize;
use crate::pattern::intersect;

/// The join `a ⊔ b` — the least upper bound.
///
/// Everything either set permits, and nothing more.
pub fn join(a: &GrantSet, b: &GrantSet) -> GrantSet {
    normalize(&GrantSet::new(a.iter().chain(b.iter()).cloned()))
}

/// Join a sequence of sets, e.g. to compute a `route` node's envelope.
///
/// Joining nothing yields [`GrantSet::EMPTY`], the identity.
pub fn join_all<'a>(sets: impl IntoIterator<Item = &'a GrantSet>) -> GrantSet {
    sets.into_iter()
        .fold(GrantSet::EMPTY, |acc, s| join(&acc, s))
}

/// The meet `a ⊓ b` — the greatest lower bound.
///
/// Permits exactly what **both** sets permit. Exact inside the decidable
/// fragment; undecidable pairs are dropped, which errs downward.
pub fn meet(a: &GrantSet, b: &GrantSet) -> GrantSet {
    let pairs = a
        .iter()
        .flat_map(|x| b.iter().filter_map(move |y| meet_atom(x, y)));
    normalize(&GrantSet::new(pairs))
}

/// Meet a sequence of sets.
///
/// Meeting nothing yields [`GrantSet::EMPTY`]: with no constraint to satisfy
/// there is nothing to grant, which is the conservative reading.
pub fn meet_all<'a>(sets: impl IntoIterator<Item = &'a GrantSet>) -> GrantSet {
    let mut iter = sets.into_iter();
    let Some(first) = iter.next() else {
        return GrantSet::EMPTY;
    };
    iter.fold(first.clone(), |acc, s| meet(&acc, s))
}

/// The exact intersection of two atoms.
///
/// Returns `None` when they share no resource, when their domain or action
/// differ, or when the pair is undecidable — all three are safe to drop from a
/// lower bound.
///
/// This computes a real intersection rather than picking the narrower side.
/// Picking a side looks equivalent and is not: `/*` and `/a/**` are
/// incomparable yet share `/a`, so a "narrower side or nothing" rule discards
/// a genuine overlap and breaks associativity. The property suite found
/// exactly that (see the regression corpus in `tests/lattice_laws.rs`).
fn meet_atom(x: &GrantAtom, y: &GrantAtom) -> Option<GrantAtom> {
    if x.domain != y.domain || x.action != y.action {
        return None;
    }
    intersect(&x.resource, &y.resource)
        .map(|resource| GrantAtom::new(&x.domain, &x.action, resource))
}

/// Clamp a resolved grant to a statically computed envelope.
///
/// This is the runtime half of Law I: whatever a template resolves to, the
/// effective grant is the meet of that value with the envelope the compiler
/// already approved. A resolved value can only narrow.
pub fn clamp(resolved: &GrantSet, envelope: &GrantSet) -> GrantSet {
    meet(resolved, envelope)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::normalize::is_normal;
    use crate::order::{set_eq, set_leq};
    use crate::pattern::Tri;

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

    // ── join ────────────────────────────────────────────────────────────────

    #[test]
    fn join_is_an_upper_bound_of_both_sides() {
        let a = set(&["fs:read:/src/**"]);
        let b = set(&["fs:write:/build/**"]);
        let j = join(&a, &b);
        assert_eq!(set_leq(&a, &j), Tri::Yes);
        assert_eq!(set_leq(&b, &j), Tri::Yes);
    }

    #[test]
    fn join_is_the_least_upper_bound() {
        let a = set(&["fs:read:/src/lib/**"]);
        let b = set(&["fs:read:/src/bin/**"]);
        let j = join(&a, &b);
        // Anything above both must be above the join.
        let above = set(&["fs:read:/src/**"]);
        assert_eq!(set_leq(&j, &above), Tri::Yes);
    }

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

    #[test]
    fn join_with_empty_is_the_identity() {
        let a = set(&["fs:read:/src/**"]);
        assert_eq!(join(&a, &GrantSet::EMPTY), a);
        assert_eq!(join(&GrantSet::EMPTY, &a), a);
    }

    #[test]
    fn join_all_folds_an_envelope() {
        let arms = [
            set(&["fs:read:/a/**"]),
            set(&["fs:read:/b/**"]),
            set(&["net:egress:api.example.com:443"]),
        ];
        let envelope = join_all(&arms);
        for arm in &arms {
            assert_eq!(set_leq(arm, &envelope), Tri::Yes);
        }
        assert_eq!(join_all(std::iter::empty()), GrantSet::EMPTY);
    }

    // ── meet ────────────────────────────────────────────────────────────────

    #[test]
    fn meet_is_a_lower_bound_of_both_sides() {
        let a = set(&["fs:read:/src/**", "fs:write:/build/**"]);
        let b = set(&["fs:read:/src/lib/**"]);
        let m = meet(&a, &b);
        assert_eq!(set_leq(&m, &a), Tri::Yes);
        assert_eq!(set_leq(&m, &b), Tri::Yes);
    }

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

    #[test]
    fn meet_of_disjoint_sets_is_empty() {
        let a = set(&["fs:read:/src/**"]);
        let b = set(&["fs:read:/etc/**"]);
        assert!(meet(&a, &b).is_empty());
    }

    #[test]
    fn meet_with_empty_is_empty() {
        let a = set(&["fs:read:/src/**"]);
        assert!(meet(&a, &GrantSet::EMPTY).is_empty());
        assert!(meet(&GrantSet::EMPTY, &a).is_empty());
    }

    #[test]
    fn meet_finds_an_overlap_between_incomparable_patterns() {
        // Neither contains the other, yet they share exactly `/a/b`. A rule
        // that picked the narrower side would find nothing here.
        let a = set(&["fs:read:/a/*"]);
        let b = set(&["fs:read:/*/b"]);
        assert_eq!(meet(&a, &b), set(&["fs:read:/a/b"]));
    }

    #[test]
    fn meet_of_a_single_glob_and_a_recursive_one_is_their_shared_root() {
        // The counterexample that broke associativity: `/*` and `/a/**` are
        // incomparable but both admit `/a`.
        let a = set(&["secret:read:/*"]);
        let b = set(&["secret:read:/a/**"]);
        assert_eq!(meet(&a, &b), set(&["secret:read:/a"]));
    }

    #[test]
    fn meet_stays_a_sound_lower_bound() {
        let a = set(&["fs:read:/a/*"]);
        let b = set(&["fs:read:/*/b"]);
        let m = meet(&a, &b);
        assert_eq!(set_leq(&m, &a), Tri::Yes);
        assert_eq!(set_leq(&m, &b), Tri::Yes);
    }

    #[test]
    fn meet_drops_undecidable_pairs_rather_than_guessing() {
        let a = set(&["fs:read:/src/*.rs"]);
        let b = set(&["fs:read:/src/main.rs"]);
        assert!(
            meet(&a, &b).is_empty(),
            "an undecided pair must not contribute to a lower bound"
        );
    }

    // ── lattice laws ────────────────────────────────────────────────────────

    fn samples() -> Vec<GrantSet> {
        vec![
            GrantSet::EMPTY,
            set(&["fs:read:/src/**"]),
            set(&["fs:read:/src/lib/a.rs"]),
            set(&["fs:write:/build/**"]),
            set(&["fs:read:/src/**", "net:egress:api.example.com:443"]),
        ]
    }

    #[test]
    fn both_operations_are_idempotent() {
        for a in samples() {
            assert_eq!(join(&a, &a), normalize(&a));
            assert_eq!(meet(&a, &a), normalize(&a));
        }
    }

    #[test]
    fn both_operations_are_commutative() {
        for a in samples() {
            for b in samples() {
                assert_eq!(join(&a, &b), join(&b, &a));
                assert_eq!(meet(&a, &b), meet(&b, &a));
            }
        }
    }

    #[test]
    fn both_operations_are_associative() {
        for a in samples() {
            for b in samples() {
                for c in samples() {
                    assert_eq!(join(&join(&a, &b), &c), join(&a, &join(&b, &c)));
                    assert_eq!(meet(&meet(&a, &b), &c), meet(&a, &meet(&b, &c)));
                }
            }
        }
    }

    #[test]
    fn absorption_holds() {
        for a in samples() {
            for b in samples() {
                // a ⊓ (a ⊔ b) = a
                assert_eq!(set_eq(&meet(&a, &join(&a, &b)), &a), Tri::Yes);
                // a ⊔ (a ⊓ b) = a
                assert_eq!(set_eq(&join(&a, &meet(&a, &b)), &a), Tri::Yes);
            }
        }
    }

    #[test]
    fn results_are_always_normalised() {
        for a in samples() {
            for b in samples() {
                assert!(is_normal(&join(&a, &b)));
                assert!(is_normal(&meet(&a, &b)));
            }
        }
    }

    // ── clamping ────────────────────────────────────────────────────────────

    #[test]
    fn a_resolved_template_can_only_narrow_its_envelope() {
        let envelope = set(&["fs:read:/src/**"]);

        // Resolves inside the envelope: allowed, and narrowed to the value.
        let inside = set(&["fs:read:/src/lib/a.rs"]);
        assert_eq!(clamp(&inside, &envelope), inside);

        // Resolves outside: clamped away entirely rather than granted.
        let outside = set(&["fs:read:/etc/passwd"]);
        assert!(
            clamp(&outside, &envelope).is_empty(),
            "a template must never resolve to authority outside its envelope"
        );

        // Resolves wider: clamped back down to the envelope.
        let wider = set(&["fs:read:/**"]);
        assert_eq!(clamp(&wider, &envelope), envelope);
    }

    #[test]
    fn clamping_never_exceeds_the_envelope() {
        let envelope = set(&["fs:read:/src/**"]);
        for resolved in samples() {
            let clamped = clamp(&resolved, &envelope);
            assert_eq!(
                set_leq(&clamped, &envelope),
                Tri::Yes,
                "clamped grant escaped its envelope"
            );
        }
    }

    #[test]
    fn meet_all_of_nothing_grants_nothing() {
        assert_eq!(meet_all(std::iter::empty()), GrantSet::EMPTY);
    }
}