boundgraph_grant/

require.rs

//! Turning an undecided answer into a refusal.
//!
//! The lattice reports three values; the compiler acts on two. This module is
//! the boundary, and it collapses [`Tri::Unknown`] into an error every time.
//!
//! # There is no permissive mode
//!
//! Deliberately, there is no flag, feature, or alternate entry point that lets
//! an `Unknown` through as a pass. That is Goal G5 — if a property cannot be
//! *proved*, reject or degrade, never assume — and it only holds if there is no
//! escape hatch. An escape hatch would be used, and it would be used on the day
//! someone is in a hurry.
//!
//! The cost of that strictness is a build error on a pattern the solver cannot
//! decide. The cost of the alternative is a permission granted on a guess. The
//! two are not comparable, so the strict reading wins.
//!
//! Every refusal names the offending pair and says *why*, so the fix is
//! obvious: narrow a grant, spell a pattern inside the decidable fragment, or
//! degrade a `par` to a `seq`.

use boundgraph_core::{GrantAtom, GrantSet};

use crate::disjoint::{Conflict, Disjointness, disjoint};
use crate::order::{atom_leq, set_leq};
use crate::pattern::{Pattern, Tri, Undecidable};

/// Why the solver refused a flow.
///
/// Grant payloads are boxed. `Refusal` is the error half of the compiler's
/// `Result`s, so its size is paid on the success path too, and a pair of atoms
/// plus a set is well past the point where that starts to cost. The
/// constructors hide the boxing; only exhaustive matches see it.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum Refusal {
    /// A grant widened along an edge. Law I forbids it.
    #[error("`{atom}` is not permitted by the parent grant {parent:?}")]
    Widened {
        /// The atom that escaped.
        atom: Box<GrantAtom>,
        /// What the parent actually permits.
        parent: Box<GrantSet>,
    },

    /// Containment could not be decided, so the flow is refused.
    #[error("cannot prove `{atom}` is within the parent grant: {reason}")]
    UndecidableContainment {
        /// The atom that could not be compared.
        atom: Box<GrantAtom>,
        /// The parent atom it was compared against.
        against: Box<GrantAtom>,
        /// Why the comparison could not be made.
        reason: Undecidable,
    },

    /// Two branches were proved to interfere.
    #[error("`{}` and `{}` can touch the same resource: {}", .0.left, .0.right, .0.kind.describe())]
    Interference(Box<Conflict>),

    /// Two branches could not be proved not to interfere.
    #[error("cannot prove `{}` and `{}` are disjoint: {reason}", .conflict.left, .conflict.right)]
    UndecidableDisjointness {
        /// The pair that could not be decided.
        conflict: Box<Conflict>,
        /// Why the comparison could not be made.
        reason: Undecidable,
    },
}

impl Refusal {
    /// Whether this refusal is a proved violation rather than a solver gap.
    ///
    /// Both refuse the flow. The distinction is for diagnostics: a proved
    /// violation means the flow is wrong, an undecided one means the flow may
    /// be fine but is spelled in a way the solver cannot check.
    pub fn is_proved(&self) -> bool {
        matches!(self, Self::Widened { .. } | Self::Interference(_))
    }

    /// A suggested fix, phrased for the author.
    pub fn suggestion(&self) -> &'static str {
        match self {
            Self::Widened { .. } => "narrow the child grant, or widen the parent behind a gate",
            Self::UndecidableContainment { .. } => {
                "respell the resource using whole-segment `*` or a trailing `**`"
            }
            Self::Interference(_) => "narrow one of the two grants, or replace `par` with `seq`",
            Self::UndecidableDisjointness { .. } => {
                "respell the resource using whole-segment `*` or a trailing `**`, or use `seq`"
            }
        }
    }
}

/// Require that `child` is within `parent` — the Law I attenuation check.
///
/// # Errors
///
/// Returns [`Refusal::Widened`] when a child atom is proved to escape, and
/// [`Refusal::UndecidableContainment`] when it merely cannot be proved not to.
/// **Both are refusals**: an undecided comparison never passes.
pub fn require_attenuated(child: &GrantSet, parent: &GrantSet) -> Result<(), Refusal> {
    match set_leq(child, parent) {
        Tri::Yes => Ok(()),
        // Re-walk to name the specific atom rather than blame the whole set.
        _ => Err(explain_widening(child, parent)),
    }
}

/// Require that two branches cannot interfere — the `par` proof.
///
/// # Errors
///
/// Returns [`Refusal::Interference`] on a proved conflict and
/// [`Refusal::UndecidableDisjointness`] when disjointness could not be proved.
/// **Both are refusals.**
pub fn require_disjoint(a: &GrantSet, b: &GrantSet) -> Result<(), Refusal> {
    match disjoint(a, b) {
        Disjointness::Disjoint => Ok(()),
        Disjointness::Overlapping(c) => Err(Refusal::Interference(Box::new(c))),
        Disjointness::Undecided(c) => {
            let reason = reason_for(&c.left)
                .or_else(|| reason_for(&c.right))
                .unwrap_or(Undecidable::NonFinalRecursive);
            Err(Refusal::UndecidableDisjointness {
                conflict: Box::new(c),
                reason,
            })
        }
    }
}

/// Find the atom responsible and say what went wrong.
///
/// A proved widening is reported in preference to an undecided comparison, so
/// the author sees the real problem when there is one.
fn explain_widening(child: &GrantSet, parent: &GrantSet) -> Refusal {
    let mut undecided: Option<Refusal> = None;

    for atom in child.iter() {
        match Tri::any(parent.iter().map(|p| atom_leq(atom, p))) {
            Tri::Yes => continue,
            Tri::No => {
                return Refusal::Widened {
                    atom: Box::new(atom.clone()),
                    parent: Box::new(parent.clone()),
                };
            }
            Tri::Unknown if undecided.is_none() => {
                let against = parent
                    .iter()
                    .find(|p| atom_leq(atom, p).is_unknown())
                    .cloned()
                    .unwrap_or_else(|| atom.clone());
                let reason = reason_for(atom)
                    .or_else(|| reason_for(&against))
                    .unwrap_or(Undecidable::NonFinalRecursive);
                undecided = Some(Refusal::UndecidableContainment {
                    atom: Box::new(atom.clone()),
                    against: Box::new(against),
                    reason,
                });
            }
            Tri::Unknown => {}
        }
    }

    undecided.unwrap_or_else(|| Refusal::Widened {
        atom: Box::new(
            child
                .iter()
                .next()
                .cloned()
                .unwrap_or_else(|| GrantAtom::new("unknown", "unknown", "")),
        ),
        parent: Box::new(parent.clone()),
    })
}

fn reason_for(atom: &GrantAtom) -> Option<Undecidable> {
    Pattern::parse(&atom.resource).undecidable_reason()
}

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

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

    #[test]
    fn a_narrowing_child_is_accepted() {
        let parent = set(&["fs:read:/src/**"]);
        let child = set(&["fs:read:/src/lib/a.rs"]);
        assert!(require_attenuated(&child, &parent).is_ok());
    }

    #[test]
    fn a_widening_child_is_refused_and_named() {
        let parent = set(&["fs:read:/src/**"]);
        let child = set(&["fs:read:/etc/passwd"]);

        let err = require_attenuated(&child, &parent).unwrap_err();
        assert!(err.is_proved());
        assert!(
            err.to_string().contains("/etc/passwd"),
            "the message must name the offending atom: {err}"
        );
        assert!(!err.suggestion().is_empty());
    }

    #[test]
    fn an_undecidable_child_is_refused_not_admitted() {
        let parent = set(&["fs:read:/src/**"]);
        let child = set(&["fs:read:/src/*.rs"]);

        let err = require_attenuated(&child, &parent)
            .expect_err("an undecided comparison must never pass");
        assert!(
            !err.is_proved(),
            "it is a solver gap, not a proved violation"
        );
    }

    #[test]
    fn a_refusal_names_both_patterns_and_the_reason() {
        let parent = set(&["fs:read:/src/**"]);
        let child = set(&["fs:read:/src/*.rs"]);

        let err = require_attenuated(&child, &parent).unwrap_err();
        let Refusal::UndecidableContainment {
            atom,
            against,
            reason,
        } = &err
        else {
            panic!("expected an undecidable containment, got {err:?}");
        };

        assert_eq!(atom.to_string(), "fs:read:/src/*.rs");
        assert_eq!(against.to_string(), "fs:read:/src/**");
        assert!(matches!(reason, Undecidable::PartialGlob { .. }));
        assert!(
            reason.to_string().contains("*.rs"),
            "the reason must quote the offending segment: {reason}"
        );
    }

    #[test]
    fn each_undecidable_kind_explains_itself_differently() {
        let cases = [
            ("fs:read:{path}", "template"),
            ("fs:read:/src/*.rs", "globs within a segment"),
            ("fs:read:/a/**/b", "before the end"),
        ];
        for (resource, needle) in cases {
            let atom: GrantAtom = resource.parse().unwrap();
            let reason = reason_for(&atom).expect("should be undecidable");
            assert!(
                reason.to_string().contains(needle),
                "{resource}: expected {needle:?} in {reason}"
            );
        }
    }

    #[test]
    fn a_proved_widening_is_reported_before_an_undecided_sibling() {
        let parent = set(&["fs:read:/src/**"]);
        let child = set(&["fs:read:/src/*.rs", "fs:read:/etc/passwd"]);
        let err = require_attenuated(&child, &parent).unwrap_err();
        assert!(err.is_proved(), "report the real violation, not the gap");
    }

    #[test]
    fn disjoint_branches_are_accepted() {
        assert!(require_disjoint(&set(&["fs:write:/a/**"]), &set(&["fs:write:/b/**"])).is_ok());
    }

    #[test]
    fn interfering_branches_are_refused() {
        let err = require_disjoint(&set(&["fs:write:/a/x"]), &set(&["fs:read:/a/**"])).unwrap_err();
        assert!(err.is_proved());
        assert!(err.to_string().contains("/a/x"));
    }

    #[test]
    fn undecidable_disjointness_is_refused_not_admitted() {
        let err = require_disjoint(&set(&["fs:write:/a/*.rs"]), &set(&["fs:read:/a/main.rs"]))
            .expect_err("an undecided proof must never pass");
        assert!(!err.is_proved());
        assert!(matches!(err, Refusal::UndecidableDisjointness { .. }));
    }

    /// `Refusal` rides in every compiler `Result`, so its size is paid whether
    /// or not anything fails. This fails if a future variant unboxes a payload.
    #[test]
    fn the_refusal_type_stays_small() {
        let size = size_of::<Refusal>();
        assert!(
            size <= 128,
            "Refusal grew to {size} bytes; box the large fields of any new variant"
        );
    }

    #[test]
    fn the_empty_child_is_always_within_its_parent() {
        assert!(require_attenuated(&GrantSet::EMPTY, &set(&["fs:read:/src/**"])).is_ok());
        assert!(require_attenuated(&GrantSet::EMPTY, &GrantSet::EMPTY).is_ok());
    }

    #[test]
    fn nothing_is_permitted_by_an_empty_parent() {
        let err = require_attenuated(&set(&["fs:read:/src/a"]), &GrantSet::EMPTY).unwrap_err();
        assert!(err.is_proved());
    }
}