boundgraph-core 0.1.0

//! Permission atoms and sets, as data.
//!
//! This module owns the *shape* and the *syntax* of a permission. The algebra
//! — containment (`⊑`), meet and join, normalisation, disjointness — lives in
//! `boundgraph-grant` (feature 02). Keeping the type here lets
//! [`WorkOrder`](crate::WorkOrder) and the ledger reference permissions without
//! depending on the solver.
//!
//! Two consequences of Law I are already visible in these types:
//!
//! - A [`GrantSet`] is a `BTreeSet`, so it has no insertion order and no
//!   duplicates. Two sets with the same atoms are the same value and share a
//!   digest.
//! - [`GrantSet::EMPTY`] is the default. A step that declares nothing gets
//!   nothing; there is no representation of "unrestricted".

use std::collections::BTreeSet;
use std::fmt;
use std::str::FromStr;

use serde::{Deserialize, Serialize};

/// The resource families the specification documents.
///
/// Parsing does **not** reject an unknown domain — the vocabulary is meant to
/// grow, and a hard-coded list in the parser would make every new sandbox
/// capability a breaking change. Unknown domains are instead treated
/// conservatively by the solver, and [`GrantAtom::has_known_domain`] lets a
/// diagnostic point out a likely typo.
pub const KNOWN_DOMAINS: &[&str] = &["fs", "net", "proc", "env", "secret", "time", "rand"];

/// One permission, as `domain:action:resource`.
///
/// For example `fs:read:/src/**`, `net:egress:api.example.com:443`, or
/// `secret:use:stripe_key`. The resource may be omitted for permissions that
/// take no argument, giving the two-part form `time:now` or `rand:bytes`.
///
/// A resource may be a *template* such as `{path}`, resolved at runtime and
/// clamped to the statically computed envelope, so a dynamic value can only
/// ever narrow the grant, never widen it.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct GrantAtom {
    /// The resource family: `fs`, `net`, `proc`, `env`, `secret`, `time`, `rand`.
    pub domain: String,
    /// What may be done: `read`, `write`, `egress`, `exec`, `use`.
    pub action: String,
    /// What it applies to. May contain globs or `{template}` segments, and may
    /// be empty for permissions that take no argument.
    pub resource: String,
}

impl GrantAtom {
    /// Build an atom from its three parts.
    pub fn new(
        domain: impl Into<String>,
        action: impl Into<String>,
        resource: impl Into<String>,
    ) -> Self {
        Self {
            domain: domain.into(),
            action: action.into(),
            resource: resource.into(),
        }
    }

    /// Whether the resource contains a `{template}` segment to be resolved at
    /// runtime.
    ///
    /// Templates stay symbolic through grant inference; the compiler reasons
    /// about the envelope they are clamped to rather than the value.
    pub fn is_template(&self) -> bool {
        self.resource.contains('{') && self.resource.contains('}')
    }

    /// Whether this permission takes no resource argument, as `time:now` does.
    pub fn is_bare(&self) -> bool {
        self.resource.is_empty()
    }

    /// Whether the domain is one the specification documents.
    ///
    /// A `false` here is not an error — see [`KNOWN_DOMAINS`].
    pub fn has_known_domain(&self) -> bool {
        KNOWN_DOMAINS.contains(&self.domain.as_str())
    }
}

/// An atom did not match `domain:action[:resource]`.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum GrantAtomParseError {
    /// The input was empty or only whitespace.
    #[error("a grant atom cannot be empty")]
    Empty,

    /// Only one segment was supplied.
    #[error("expected `domain:action[:resource]`, found {input:?} with no action")]
    MissingAction {
        /// What was supplied.
        input: String,
    },

    /// The domain or action segment was empty.
    #[error("the {segment} segment of a grant atom cannot be empty")]
    EmptySegment {
        /// Which segment: `domain` or `action`.
        segment: &'static str,
    },

    /// The domain or action contained whitespace.
    #[error("the {segment} segment must not contain whitespace, found {ch:?}")]
    Whitespace {
        /// Which segment: `domain` or `action`.
        segment: &'static str,
        /// The offending character.
        ch: char,
    },
}

impl FromStr for GrantAtom {
    type Err = GrantAtomParseError;

    /// Parse `domain:action[:resource]`.
    ///
    /// Splits on the **first two** colons only, so a resource may itself
    /// contain colons — `net:egress:api.example.com:443` is one atom whose
    /// resource is `api.example.com:443`, not a malformed four-part atom.
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if s.trim().is_empty() {
            return Err(GrantAtomParseError::Empty);
        }

        let mut parts = s.splitn(3, ':');
        let domain = parts.next().unwrap_or_default();
        let Some(action) = parts.next() else {
            return Err(GrantAtomParseError::MissingAction {
                input: s.to_string(),
            });
        };
        // Absent third segment is the bare form; an empty one is equivalent.
        let resource = parts.next().unwrap_or("");

        check_segment(domain, "domain")?;
        check_segment(action, "action")?;

        Ok(Self::new(domain, action, resource))
    }
}

/// The domain and action are identifiers, not free text: they must be present
/// and must not contain whitespace. The resource is deliberately unconstrained
/// — real paths contain spaces.
fn check_segment(value: &str, segment: &'static str) -> Result<(), GrantAtomParseError> {
    if value.is_empty() {
        return Err(GrantAtomParseError::EmptySegment { segment });
    }
    if let Some(ch) = value.chars().find(|c| c.is_whitespace()) {
        return Err(GrantAtomParseError::Whitespace { segment, ch });
    }
    Ok(())
}

impl fmt::Display for GrantAtom {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.is_bare() {
            write!(f, "{}:{}", self.domain, self.action)
        } else {
            write!(f, "{}:{}:{}", self.domain, self.action, self.resource)
        }
    }
}

impl fmt::Debug for GrantAtom {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{self}")
    }
}

/// A set of permissions.
///
/// Unordered and duplicate-free by construction, so equal permissions always
/// produce an equal digest regardless of how the set was built.
#[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[serde(transparent)]
pub struct GrantSet(BTreeSet<GrantAtom>);

impl GrantSet {
    /// No permissions at all. The default, and the floor of the lattice.
    pub const EMPTY: Self = Self(BTreeSet::new());

    /// Build a set from atoms, discarding duplicates.
    pub fn new(atoms: impl IntoIterator<Item = GrantAtom>) -> Self {
        Self(atoms.into_iter().collect())
    }

    /// Parse a set from atom strings.
    ///
    /// # Errors
    ///
    /// Returns the first [`GrantAtomParseError`] encountered.
    pub fn parse<'a>(
        atoms: impl IntoIterator<Item = &'a str>,
    ) -> Result<Self, GrantAtomParseError> {
        atoms
            .into_iter()
            .map(GrantAtom::from_str)
            .collect::<Result<BTreeSet<_>, _>>()
            .map(Self)
    }

    /// Whether this grants nothing.
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// How many distinct atoms this holds.
    pub fn len(&self) -> usize {
        self.0.len()
    }

    /// Iterate the atoms in a deterministic order.
    pub fn iter(&self) -> impl Iterator<Item = &GrantAtom> {
        self.0.iter()
    }

    /// Whether this set contains exactly this atom.
    ///
    /// This is literal membership, **not** the containment relation `⊑` — an
    /// atom may be permitted by a broader atom in the set without appearing in
    /// it. That question belongs to the grant lattice.
    pub fn contains_atom(&self, atom: &GrantAtom) -> bool {
        self.0.contains(atom)
    }

    /// Whether any atom carries an unresolved template.
    pub fn has_templates(&self) -> bool {
        self.0.iter().any(GrantAtom::is_template)
    }
}

impl FromIterator<GrantAtom> for GrantSet {
    fn from_iter<I: IntoIterator<Item = GrantAtom>>(iter: I) -> Self {
        Self::new(iter)
    }
}

impl<'a> IntoIterator for &'a GrantSet {
    type Item = &'a GrantAtom;
    type IntoIter = std::collections::btree_set::Iter<'a, GrantAtom>;

    fn into_iter(self) -> Self::IntoIter {
        self.0.iter()
    }
}

impl fmt::Debug for GrantSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.0.iter()).finish()
    }
}

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

    fn atoms() -> Vec<GrantAtom> {
        vec![
            GrantAtom::new("fs", "read", "/src/**"),
            GrantAtom::new("net", "egress", "api.example.com:443"),
        ]
    }

    #[test]
    fn default_grants_nothing() {
        assert!(GrantSet::default().is_empty());
        assert!(GrantSet::EMPTY.is_empty());
    }

    #[test]
    fn insertion_order_does_not_change_identity() {
        let forward = GrantSet::new(atoms());
        let reverse = GrantSet::new(atoms().into_iter().rev());
        assert_eq!(forward, reverse);
        assert_eq!(forward.digest().unwrap(), reverse.digest().unwrap());
    }

    #[test]
    fn duplicates_collapse() {
        let mut with_dupes = atoms();
        with_dupes.extend(atoms());
        assert_eq!(GrantSet::new(with_dupes).len(), 2);
    }

    #[test]
    fn templates_are_detected() {
        assert!(GrantAtom::new("fs", "read", "{path}").is_template());
        assert!(!GrantAtom::new("fs", "read", "/src/**").is_template());
        assert!(GrantSet::new([GrantAtom::new("fs", "read", "{path}")]).has_templates());
        assert!(!GrantSet::new(atoms()).has_templates());
    }

    // ── US-0201: syntax ─────────────────────────────────────────────────────

    #[test]
    fn parses_the_documented_three_part_form() {
        let a: GrantAtom = "fs:read:/src/**".parse().unwrap();
        assert_eq!(a, GrantAtom::new("fs", "read", "/src/**"));
    }

    #[test]
    fn a_resource_may_itself_contain_colons() {
        // The classic trap: this is three segments, not four.
        let a: GrantAtom = "net:egress:api.example.com:443".parse().unwrap();
        assert_eq!(a.domain, "net");
        assert_eq!(a.action, "egress");
        assert_eq!(a.resource, "api.example.com:443");
    }

    #[test]
    fn parses_the_bare_two_part_form() {
        for s in ["time:now", "rand:bytes"] {
            let a: GrantAtom = s.parse().unwrap();
            assert!(a.is_bare(), "{s} should have no resource");
            assert_eq!(
                a.to_string(),
                s,
                "bare atoms round-trip without a trailing colon"
            );
        }
        // A trailing colon is the same thing written differently.
        assert_eq!(
            "time:now:".parse::<GrantAtom>().unwrap(),
            "time:now".parse::<GrantAtom>().unwrap()
        );
    }

    #[test]
    fn every_documented_domain_parses() {
        let documented = [
            "fs:read:/src/**",
            "fs:write:/build/**",
            "net:egress:api.example.com:443",
            "proc:exec:git",
            "env:read:HOME",
            "secret:use:stripe_key",
            "time:now",
            "rand:bytes",
        ];
        for s in documented {
            let a: GrantAtom = s.parse().unwrap_or_else(|e| panic!("{s} failed: {e}"));
            assert!(a.has_known_domain(), "{s} should use a documented domain");
        }
    }

    #[test]
    fn display_round_trips_through_parse() {
        for s in [
            "fs:read:/src/**",
            "net:egress:api.example.com:443",
            "fs:read:{path}",
            "time:now",
            "fs:read:/a path/with spaces/**",
        ] {
            let a: GrantAtom = s.parse().unwrap();
            assert_eq!(a.to_string().parse::<GrantAtom>().unwrap(), a);
        }
    }

    #[test]
    fn glob_and_template_resources_are_preserved_verbatim() {
        assert_eq!(
            "fs:read:/src/**".parse::<GrantAtom>().unwrap().resource,
            "/src/**"
        );
        assert_eq!(
            "fs:read:/src/*".parse::<GrantAtom>().unwrap().resource,
            "/src/*"
        );

        let t: GrantAtom = "fs:read:{path}".parse().unwrap();
        assert_eq!(t.resource, "{path}");
        assert!(t.is_template(), "a parsed template is marked symbolic");
    }

    #[test]
    fn an_unknown_domain_parses_but_is_flagged() {
        let a: GrantAtom = "gpu:use:cuda0".parse().unwrap();
        assert!(!a.has_known_domain());
    }

    #[test]
    fn malformed_atoms_name_the_offending_segment() {
        assert_eq!("".parse::<GrantAtom>(), Err(GrantAtomParseError::Empty));
        assert_eq!("   ".parse::<GrantAtom>(), Err(GrantAtomParseError::Empty));

        assert!(matches!(
            "fsread".parse::<GrantAtom>(),
            Err(GrantAtomParseError::MissingAction { .. })
        ));
        assert_eq!(
            ":read:/src".parse::<GrantAtom>(),
            Err(GrantAtomParseError::EmptySegment { segment: "domain" })
        );
        assert_eq!(
            "fs::/src".parse::<GrantAtom>(),
            Err(GrantAtomParseError::EmptySegment { segment: "action" })
        );
        assert_eq!(
            "f s:read:/src".parse::<GrantAtom>(),
            Err(GrantAtomParseError::Whitespace {
                segment: "domain",
                ch: ' '
            })
        );
    }

    #[test]
    fn a_set_parses_from_strings() {
        let g = GrantSet::parse(["fs:read:/src/**", "net:egress:api.example.com:443"]).unwrap();
        assert_eq!(g.len(), 2);
        assert!(GrantSet::parse(["fs:read:/src/**", "bad"]).is_err());
    }
}