boundgraph_grant/

disjoint.rs

//! The disjointness proof behind `par`.
//!
//! Two branches may run concurrently only if neither can observe or clobber
//! what the other touches. Stated over grant sets, that is the specification's
//! three-way condition:
//!
//! ```text
//! W(A) ∩ R(B) = ∅   ∧   R(A) ∩ W(B) = ∅   ∧   W(A) ∩ W(B) = ∅
//! ```
//!
//! Read against read is deliberately absent: two branches reading the same file
//! interfere with nothing, and forbidding that would rule out most useful
//! parallelism.
//!
//! Every other framework lets you run branches concurrently and hope. The
//! difference here is that an unprovable `par` is a **build error**, so the
//! race is found in a pull request rather than under production load.

use boundgraph_core::{GrantAtom, GrantSet};

use crate::access::{Access, classify};
use crate::trie::ResourceTrie;

/// Which of the three conditions a conflicting pair violates.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ConflictKind {
    /// Both sides write the same resource.
    WriteWrite,
    /// The left side writes what the right side reads.
    WriteRead,
    /// The left side reads what the right side writes.
    ReadWrite,
}

impl ConflictKind {
    /// A short description for a diagnostic.
    pub fn describe(self) -> &'static str {
        match self {
            Self::WriteWrite => "both branches write it",
            Self::WriteRead => "the left branch writes what the right branch reads",
            Self::ReadWrite => "the left branch reads what the right branch writes",
        }
    }
}

/// The specific pair of atoms that decided the outcome.
///
/// Reported so a diagnostic can name the real problem rather than say "these
/// branches conflict somehow", and so the compiler can suggest a fix: narrow
/// one of these two grants, or degrade the `par` to a `seq`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Conflict {
    /// The atom from the left-hand grant set.
    pub left: GrantAtom,
    /// The atom from the right-hand grant set.
    pub right: GrantAtom,
    /// Which condition it violates.
    pub kind: ConflictKind,
}

/// The result of a disjointness proof.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Disjointness {
    /// Proved: the branches cannot touch the same resource. Safe to run in
    /// parallel.
    Disjoint,
    /// Proved: they can interfere. The offending pair is named.
    Overlapping(Conflict),
    /// Not decided. Treated as a refusal by the compiler — see US-0206.
    Undecided(Conflict),
}

impl Disjointness {
    /// Whether parallel execution is *proved* safe.
    ///
    /// [`Disjointness::Undecided`] is not safe. There is deliberately no
    /// variant of this that accepts an undecided proof.
    pub fn is_proved_disjoint(&self) -> bool {
        matches!(self, Self::Disjoint)
    }

    /// The conflicting pair, if there is one.
    pub fn conflict(&self) -> Option<&Conflict> {
        match self {
            Self::Disjoint => None,
            Self::Overlapping(c) | Self::Undecided(c) => Some(c),
        }
    }
}

/// Split a grant set into the resources it reads and those it writes.
fn partition(set: &GrantSet) -> (Vec<&GrantAtom>, Vec<&GrantAtom>) {
    set.iter()
        .partition(|a| classify(&a.action) == Access::Read)
}

/// Prove — or fail to prove — that two grant sets cannot interfere.
///
/// Returns the first proved overlap if there is one; otherwise the first
/// undecided pair; otherwise [`Disjointness::Disjoint`]. A proved conflict is
/// always preferred over an undecided one, so diagnostics report the real
/// problem rather than a gap in the solver.
pub fn disjoint(a: &GrantSet, b: &GrantSet) -> Disjointness {
    let (a_reads, a_writes) = partition(a);
    let (b_reads, b_writes) = partition(b);

    // The three conditions. Read-vs-read is absent by design.
    let checks = [
        (&a_writes, &b_reads, ConflictKind::WriteRead),
        (&a_reads, &b_writes, ConflictKind::ReadWrite),
        (&a_writes, &b_writes, ConflictKind::WriteWrite),
    ];

    let mut undecided: Option<Conflict> = None;

    for (left, right, kind) in checks {
        let trie = ResourceTrie::build(right.iter().copied());

        for l in left.iter() {
            let probe = trie.probe(l);

            if let Some(index) = probe.hit {
                return Disjointness::Overlapping(Conflict {
                    left: (*l).clone(),
                    right: trie.atom(index).clone(),
                    kind,
                });
            }

            if probe.undecided && undecided.is_none() {
                // Name a plausible counterpart so the diagnostic has something
                // concrete to point at.
                let counterpart = right
                    .iter()
                    .find(|r| r.domain == l.domain)
                    .or_else(|| right.first())
                    .map(|r| (*r).clone())
                    .unwrap_or_else(|| (*l).clone());
                undecided = Some(Conflict {
                    left: (*l).clone(),
                    right: counterpart,
                    kind,
                });
            }
        }
    }

    undecided.map_or(Disjointness::Disjoint, Disjointness::Undecided)
}

/// Prove that every pair in a set of branches is mutually disjoint.
///
/// This is what a `par` node with more than two branches needs: pairwise
/// disjointness, since any two of them may run at the same time.
pub fn all_disjoint<'a>(branches: impl IntoIterator<Item = &'a GrantSet>) -> Disjointness {
    let sets: Vec<&GrantSet> = branches.into_iter().collect();
    let mut undecided: Option<Conflict> = None;

    for i in 0..sets.len() {
        for j in (i + 1)..sets.len() {
            match disjoint(sets[i], sets[j]) {
                Disjointness::Disjoint => {}
                overlapping @ Disjointness::Overlapping(_) => return overlapping,
                Disjointness::Undecided(c) => {
                    undecided.get_or_insert(c);
                }
            }
        }
    }

    undecided.map_or(Disjointness::Disjoint, Disjointness::Undecided)
}

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

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

    #[test]
    fn two_reads_of_the_same_file_are_disjoint() {
        // The whole point of excluding read-vs-read: this must be allowed.
        let a = set(&["fs:read:/src/**"]);
        let b = set(&["fs:read:/src/**"]);
        assert_eq!(disjoint(&a, &b), Disjointness::Disjoint);
    }

    #[test]
    fn two_writes_of_the_same_file_are_not() {
        let a = set(&["fs:write:/build/out"]);
        let b = set(&["fs:write:/build/out"]);
        let result = disjoint(&a, &b);
        assert!(!result.is_proved_disjoint());
        assert_eq!(result.conflict().unwrap().kind, ConflictKind::WriteWrite);
    }

    #[test]
    fn a_write_against_a_read_is_a_race() {
        let writer = set(&["fs:write:/src/a.rs"]);
        let reader = set(&["fs:read:/src/**"]);

        let forward = disjoint(&writer, &reader);
        assert_eq!(forward.conflict().unwrap().kind, ConflictKind::WriteRead);

        let backward = disjoint(&reader, &writer);
        assert_eq!(backward.conflict().unwrap().kind, ConflictKind::ReadWrite);
    }

    #[test]
    fn unrelated_paths_are_disjoint() {
        let a = set(&["fs:write:/build/**"]);
        let b = set(&["fs:write:/dist/**"]);
        assert_eq!(disjoint(&a, &b), Disjointness::Disjoint);
    }

    #[test]
    fn different_domains_never_conflict() {
        let a = set(&["fs:write:/src/a"]);
        let b = set(&["net:egress:api.example.com:443"]);
        assert_eq!(disjoint(&a, &b), Disjointness::Disjoint);
    }

    #[test]
    fn nesting_counts_as_overlap() {
        let a = set(&["fs:write:/src/lib/a.rs"]);
        let b = set(&["fs:read:/src/**"]);
        assert!(!disjoint(&a, &b).is_proved_disjoint());
    }

    #[test]
    fn the_offending_pair_is_reported() {
        let a = set(&["fs:write:/build/out", "fs:read:/src/**"]);
        let b = set(&["fs:read:/build/out", "fs:read:/docs/**"]);

        let c = disjoint(&a, &b)
            .conflict()
            .cloned()
            .expect("should conflict");
        assert_eq!(c.left.to_string(), "fs:write:/build/out");
        assert_eq!(c.right.to_string(), "fs:read:/build/out");
        assert_eq!(c.kind, ConflictKind::WriteRead);
        assert!(!c.kind.describe().is_empty());
    }

    #[test]
    fn an_undecidable_pair_is_undecided_not_disjoint() {
        let a = set(&["fs:write:/src/*.rs"]);
        let b = set(&["fs:read:/src/main.rs"]);
        let result = disjoint(&a, &b);
        assert!(matches!(result, Disjointness::Undecided(_)));
        assert!(
            !result.is_proved_disjoint(),
            "an undecided proof must never read as safe"
        );
    }

    #[test]
    fn a_proved_conflict_outranks_an_undecided_one() {
        let a = set(&["fs:write:/src/*.rs", "fs:write:/build/out"]);
        let b = set(&["fs:read:/build/out"]);
        assert!(matches!(disjoint(&a, &b), Disjointness::Overlapping(_)));
    }

    #[test]
    fn exec_and_egress_are_treated_as_writes() {
        // Two branches running processes are not provably independent.
        let a = set(&["proc:exec:git"]);
        let b = set(&["proc:exec:git"]);
        assert!(!disjoint(&a, &b).is_proved_disjoint());

        let x = set(&["net:egress:api.example.com:443"]);
        let y = set(&["net:egress:api.example.com:443"]);
        assert!(!disjoint(&x, &y).is_proved_disjoint());
    }

    #[test]
    fn two_branches_using_the_same_secret_are_disjoint() {
        let a = set(&["secret:use:stripe_key"]);
        let b = set(&["secret:use:stripe_key"]);
        assert_eq!(disjoint(&a, &b), Disjointness::Disjoint);
    }

    #[test]
    fn empty_grants_are_disjoint_from_everything() {
        let busy = set(&["fs:write:/**"]);
        assert_eq!(disjoint(&GrantSet::EMPTY, &busy), Disjointness::Disjoint);
        assert_eq!(disjoint(&busy, &GrantSet::EMPTY), Disjointness::Disjoint);
    }

    #[test]
    fn disjointness_is_symmetric_in_its_verdict() {
        let cases = [
            (set(&["fs:write:/a"]), set(&["fs:read:/a"])),
            (set(&["fs:write:/a"]), set(&["fs:write:/b"])),
            (set(&["fs:read:/a"]), set(&["fs:read:/a"])),
            (set(&["fs:write:/src/*.rs"]), set(&["fs:read:/src/main.rs"])),
        ];
        for (a, b) in cases {
            assert_eq!(
                disjoint(&a, &b).is_proved_disjoint(),
                disjoint(&b, &a).is_proved_disjoint(),
                "verdict must not depend on argument order: {a:?} vs {b:?}"
            );
        }
    }

    #[test]
    fn a_branch_is_never_disjoint_from_itself_when_it_writes() {
        let w = set(&["fs:write:/build/**"]);
        assert!(!disjoint(&w, &w).is_proved_disjoint());
    }

    // ── many branches ───────────────────────────────────────────────────────

    #[test]
    fn pairwise_disjointness_across_several_branches() {
        let branches = [
            set(&["fs:write:/a/**"]),
            set(&["fs:write:/b/**"]),
            set(&["fs:write:/c/**"]),
        ];
        assert_eq!(all_disjoint(&branches), Disjointness::Disjoint);
    }

    #[test]
    fn one_bad_pair_sinks_the_whole_par() {
        let branches = [
            set(&["fs:write:/a/**"]),
            set(&["fs:write:/b/**"]),
            set(&["fs:read:/a/thing"]), // clashes with the first
        ];
        let result = all_disjoint(&branches);
        assert!(!result.is_proved_disjoint());
        assert_eq!(result.conflict().unwrap().kind, ConflictKind::WriteRead);
    }

    #[test]
    fn fewer_than_two_branches_are_trivially_disjoint() {
        assert_eq!(all_disjoint(std::iter::empty()), Disjointness::Disjoint);
        let single = [set(&["fs:write:/a/**"])];
        assert_eq!(all_disjoint(&single), Disjointness::Disjoint);
    }
}