boundgraph_grant/

pattern.rs

//! Resource patterns, and what one pattern says about another.
//!
//! A grant's resource is a pattern over concrete resources: `/src/**` stands
//! for every path under `/src`. Deciding Law I means deciding questions about
//! those *sets* — does this pattern cover that one, could these two ever touch
//! the same thing — without enumerating them.
//!
//! # The decidable fragment
//!
//! A richer pattern language is easy to write and impossible to decide: two
//! regex-ish patterns can overlap in ways no solver settles cheaply. Goal G5
//! says conservative by default, so this module supports a fragment it can
//! decide *exactly*, and answers [`Tri::Unknown`] for everything else. The
//! compiler turns `Unknown` into a rejection (US-0206), so an undecidable
//! pattern costs you a build error, never a false guarantee.
//!
//! Inside the fragment:
//!
//! | Form | Meaning |
//! |---|---|
//! | `src` | a literal segment |
//! | `*` | exactly one segment, as a whole |
//! | `**` | zero or more segments, **final position only** |
//!
//! Outside it, and therefore `Unknown`: `**` anywhere but last, partial-segment
//! globs like `*.rs`, and `{template}` segments, which are symbolic until the
//! runtime clamps them.

use std::fmt;

/// A three-valued answer.
///
/// [`Tri::Unknown`] means "not decided", and every consumer must treat it as a
/// refusal rather than a maybe-yes. There is deliberately no conversion to
/// `bool` that guesses.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Tri {
    /// Definitely true.
    Yes,
    /// Definitely false.
    No,
    /// Could not be decided from the pattern language.
    Unknown,
}

impl Tri {
    /// Whether this is a definite yes. `Unknown` is not.
    pub fn is_yes(self) -> bool {
        self == Self::Yes
    }

    /// Whether this is a definite no. `Unknown` is not.
    pub fn is_no(self) -> bool {
        self == Self::No
    }

    /// Whether the answer is undecided.
    pub fn is_unknown(self) -> bool {
        self == Self::Unknown
    }

    /// Conjunction: `No` dominates, then `Unknown`.
    ///
    /// A definite `No` survives an undecided sibling — if one conjunct is
    /// already false the whole thing is false regardless.
    pub fn and(self, other: Self) -> Self {
        match (self, other) {
            (Self::No, _) | (_, Self::No) => Self::No,
            (Self::Unknown, _) | (_, Self::Unknown) => Self::Unknown,
            _ => Self::Yes,
        }
    }

    /// Disjunction: `Yes` dominates, then `Unknown`.
    pub fn or(self, other: Self) -> Self {
        match (self, other) {
            (Self::Yes, _) | (_, Self::Yes) => Self::Yes,
            (Self::Unknown, _) | (_, Self::Unknown) => Self::Unknown,
            _ => Self::No,
        }
    }

    /// Fold a sequence with [`Tri::and`], starting from `Yes`.
    pub fn all(items: impl IntoIterator<Item = Self>) -> Self {
        items.into_iter().fold(Self::Yes, Self::and)
    }

    /// Fold a sequence with [`Tri::or`], starting from `No`.
    pub fn any(items: impl IntoIterator<Item = Self>) -> Self {
        items.into_iter().fold(Self::No, Self::or)
    }
}

impl fmt::Display for Tri {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match self {
            Self::Yes => "yes",
            Self::No => "no",
            Self::Unknown => "undecidable",
        })
    }
}

/// One segment of a resource pattern.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Seg {
    /// An exact segment.
    Literal(String),
    /// `*` — exactly one segment.
    Single,
    /// `**` — zero or more segments. Only valid in final position.
    Recursive,
    /// Something outside the decidable fragment.
    ///
    /// Carries the original text. That is load-bearing, not diagnostic: if
    /// every opaque segment compared equal, `/src/*.rs` and `/src/*.py` would
    /// parse to identical patterns and the equality short-circuit in [`covers`]
    /// would report that each contains the other — a false guarantee, which is
    /// the one failure mode this module exists to prevent.
    Opaque(String),
}

/// A parsed resource pattern.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Pattern {
    segments: Vec<Seg>,
    decidable: bool,
}

impl Pattern {
    /// Parse a resource string into a pattern.
    ///
    /// Never fails: anything outside the decidable fragment is recorded as
    /// such and surfaces later as [`Tri::Unknown`].
    pub fn parse(resource: &str) -> Self {
        // A bare atom (`time:now`) has no resource and exactly one member: itself.
        if resource.is_empty() {
            return Self {
                segments: Vec::new(),
                decidable: true,
            };
        }

        // `/src/` and `/src` denote the same set. Normalise the trailing
        // separator away so the order is antisymmetric over denotations.
        let trimmed = resource.strip_suffix('/').unwrap_or(resource);
        let raw: Vec<&str> = trimmed.split('/').collect();
        let last = raw.len().saturating_sub(1);

        let mut decidable = true;
        let segments = raw
            .into_iter()
            .enumerate()
            .map(|(i, s)| match s {
                "*" => Seg::Single,
                // `**` in the middle makes containment undecidable cheaply:
                // it can absorb a variable number of segments on both sides.
                "**" if i == last => Seg::Recursive,
                "**" => {
                    decidable = false;
                    Seg::Opaque(s.to_string())
                }
                other if other.contains('{') || other.contains('}') => {
                    decidable = false;
                    Seg::Opaque(other.to_string())
                }
                other if other.contains('*') => {
                    // A partial-segment glob such as `*.rs`.
                    decidable = false;
                    Seg::Opaque(other.to_string())
                }
                other => Seg::Literal(other.to_string()),
            })
            .collect();

        Self {
            segments,
            decidable,
        }
    }

    /// The parsed segments, for the prefix trie to index.
    pub(crate) fn segments(&self) -> &[Seg] {
        &self.segments
    }

    /// Whether this pattern lies inside the decidable fragment.
    pub fn is_decidable(&self) -> bool {
        self.decidable
    }

    /// Why this pattern could not be decided, if it could not.
    ///
    /// A refusal has to be actionable. "These grants could not be compared" is
    /// not; "`*.rs` is a partial-segment glob, which the solver does not
    /// decide" tells the author exactly what to change.
    pub fn undecidable_reason(&self) -> Option<Undecidable> {
        self.segments.iter().find_map(|s| match s {
            Seg::Opaque(raw) if raw.contains('{') || raw.contains('}') => {
                Some(Undecidable::Template {
                    segment: raw.clone(),
                })
            }
            Seg::Opaque(raw) if raw == "**" => Some(Undecidable::NonFinalRecursive),
            Seg::Opaque(raw) => Some(Undecidable::PartialGlob {
                segment: raw.clone(),
            }),
            _ => None,
        })
    }
}

/// Why a pattern falls outside the decidable fragment.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Undecidable {
    /// A `{template}` segment, symbolic until the runtime resolves it.
    Template {
        /// The offending segment.
        segment: String,
    },
    /// A glob inside a segment, such as `*.rs`, rather than a whole segment.
    PartialGlob {
        /// The offending segment.
        segment: String,
    },
    /// `**` somewhere other than the final position.
    NonFinalRecursive,
}

impl fmt::Display for Undecidable {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Template { segment } => write!(
                f,
                "`{segment}` is a template, which stays symbolic until the runtime resolves and clamps it"
            ),
            Self::PartialGlob { segment } => write!(
                f,
                "`{segment}` globs within a segment; the solver decides whole-segment `*` and trailing `**` only"
            ),
            Self::NonFinalRecursive => f.write_str(
                "`**` appears before the end of the pattern; it is decided only in final position",
            ),
        }
    }
}

impl Pattern {
    /// A canonical rendering, so two spellings of the same pattern compare
    /// equal (`/src/` and `/src`).
    pub fn canonical(&self) -> String {
        if self.segments.is_empty() {
            return String::new();
        }
        self.segments
            .iter()
            .map(|s| match s {
                Seg::Literal(l) => l.as_str(),
                Seg::Single => "*",
                Seg::Recursive => "**",
                Seg::Opaque(raw) => raw.as_str(),
            })
            .collect::<Vec<_>>()
            .join("/")
    }
}

impl fmt::Display for Pattern {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&self.canonical())
    }
}

/// Whether every resource matched by `inner` is also matched by `outer`.
///
/// This is the containment relation the partial order is built from: `outer`
/// permits at least as much as `inner`.
pub fn covers(outer: &str, inner: &str) -> Tri {
    // Reflexivity must hold even outside the decidable fragment: a template is
    // always exactly as permissive as itself.
    if outer == inner {
        return Tri::Yes;
    }

    let o = Pattern::parse(outer);
    let i = Pattern::parse(inner);

    // Same denotation, spelled differently.
    if o == i {
        return Tri::Yes;
    }
    if !o.decidable || !i.decidable {
        return Tri::Unknown;
    }

    covers_segments(&o.segments, &i.segments)
}

fn covers_segments(outer: &[Seg], inner: &[Seg]) -> Tri {
    match (outer.first(), inner.first()) {
        // Both exhausted: the same depth, everything matched so far.
        (None, None) => Tri::Yes,
        // `**` is final and absorbs whatever remains, including nothing.
        (Some(Seg::Recursive), _) => Tri::Yes,
        // Outer ran out while inner goes deeper, or needs depth inner lacks.
        (None, Some(_)) | (Some(_), None) => Tri::No,

        (Some(Seg::Single), Some(inner_seg)) => match inner_seg {
            // A single segment cannot cover an unbounded tail.
            Seg::Recursive => Tri::No,
            Seg::Opaque(_) => Tri::Unknown,
            _ => covers_segments(&outer[1..], &inner[1..]),
        },

        (Some(Seg::Literal(a)), Some(inner_seg)) => match inner_seg {
            Seg::Literal(b) if a == b => covers_segments(&outer[1..], &inner[1..]),
            // A literal covers only itself; anything wider escapes it.
            Seg::Literal(_) | Seg::Single | Seg::Recursive => Tri::No,
            Seg::Opaque(_) => Tri::Unknown,
        },

        (Some(Seg::Opaque(_)), _) => Tri::Unknown,
    }
}

/// Whether two patterns could ever match the same concrete resource.
///
/// This is the question `par` disjointness turns on: not "is one inside the
/// other", but "can these two touch the same thing at all".
pub fn overlaps(a: &str, b: &str) -> Tri {
    if a == b {
        return Tri::Yes;
    }

    let pa = Pattern::parse(a);
    let pb = Pattern::parse(b);

    if pa == pb {
        return Tri::Yes;
    }
    if !pa.decidable || !pb.decidable {
        return Tri::Unknown;
    }

    overlaps_segments(&pa.segments, &pb.segments)
}

/// The exact intersection of two patterns, if the fragment can express it.
///
/// Returns the resource denoting precisely what both patterns admit, or `None`
/// when they admit nothing in common or the pair is undecidable.
///
/// The decidable fragment **is** closed under intersection, which is what makes
/// [`meet`](crate::meet) exact rather than approximate: a literal meets `*` as
/// that literal, `*` meets `*` as `*`, and a trailing `**` yields whatever the
/// other side has left. Picking one side and discarding the other instead
/// would break associativity — `/*` and `/a/**` share `/a`, and a rule that
/// dropped the pair would lose it.
pub fn intersect(a: &str, b: &str) -> Option<String> {
    let pa = Pattern::parse(a);
    let pb = Pattern::parse(b);

    // Identical patterns intersect to themselves, decidable or not.
    if pa == pb {
        return Some(pa.canonical());
    }
    if !pa.decidable || !pb.decidable {
        return None;
    }

    intersect_segments(pa.segments(), pb.segments()).map(|segs| {
        Pattern {
            segments: segs,
            decidable: true,
        }
        .canonical()
    })
}

fn intersect_segments(a: &[Seg], b: &[Seg]) -> Option<Vec<Seg>> {
    match (a.first(), b.first()) {
        (None, None) => Some(Vec::new()),

        // A trailing `**` matches zero or more segments, so the intersection
        // from here on is simply whatever the other side still requires.
        // These arms must precede the depth-mismatch arm below.
        (Some(Seg::Recursive), _) => Some(b.to_vec()),
        (_, Some(Seg::Recursive)) => Some(a.to_vec()),

        // One side is deeper and neither can absorb the difference.
        (None, Some(_)) | (Some(_), None) => None,

        (Some(Seg::Opaque(_)), _) | (_, Some(Seg::Opaque(_))) => None,

        (Some(head_a), Some(head_b)) => {
            let head = match (head_a, head_b) {
                (Seg::Literal(x), Seg::Literal(y)) if x == y => Seg::Literal(x.clone()),
                (Seg::Literal(_), Seg::Literal(_)) => return None,
                // `*` admits any single segment, so the literal is the narrower.
                (Seg::Literal(x), Seg::Single) | (Seg::Single, Seg::Literal(x)) => {
                    Seg::Literal(x.clone())
                }
                (Seg::Single, Seg::Single) => Seg::Single,
                _ => return None,
            };
            let mut rest = intersect_segments(&a[1..], &b[1..])?;
            rest.insert(0, head);
            Some(rest)
        }
    }
}

fn overlaps_segments(a: &[Seg], b: &[Seg]) -> Tri {
    match (a.first(), b.first()) {
        (None, None) => Tri::Yes,
        // A trailing `**` matches zero or more, so it meets whatever is left.
        (Some(Seg::Recursive), _) | (_, Some(Seg::Recursive)) => Tri::Yes,
        // One side is deeper than the other, and neither can absorb the rest.
        (None, Some(_)) | (Some(_), None) => Tri::No,

        (Some(Seg::Opaque(_)), _) | (_, Some(Seg::Opaque(_))) => Tri::Unknown,

        // `*` matches any single segment, so it meets anything at this depth.
        (Some(Seg::Single), Some(_)) | (Some(_), Some(Seg::Single)) => {
            overlaps_segments(&a[1..], &b[1..])
        }

        (Some(Seg::Literal(x)), Some(Seg::Literal(y))) => {
            if x == y {
                overlaps_segments(&a[1..], &b[1..])
            } else {
                Tri::No
            }
        }
    }
}

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

    #[test]
    fn tri_conjunction_lets_a_definite_no_win() {
        assert_eq!(Tri::No.and(Tri::Unknown), Tri::No);
        assert_eq!(Tri::Unknown.and(Tri::Yes), Tri::Unknown);
        assert_eq!(Tri::Yes.and(Tri::Yes), Tri::Yes);
    }

    #[test]
    fn tri_disjunction_lets_a_definite_yes_win() {
        assert_eq!(Tri::Yes.or(Tri::Unknown), Tri::Yes);
        assert_eq!(Tri::Unknown.or(Tri::No), Tri::Unknown);
        assert_eq!(Tri::No.or(Tri::No), Tri::No);
    }

    #[test]
    fn unknown_never_reads_as_true() {
        assert!(!Tri::Unknown.is_yes());
        assert!(!Tri::Unknown.is_no());
    }

    // ── covers ──────────────────────────────────────────────────────────────

    #[test]
    fn a_pattern_covers_itself() {
        for p in ["/src/**", "/src", "*", "{path}", "*.rs", "", "a/**/b"] {
            assert_eq!(covers(p, p), Tri::Yes, "{p} must cover itself");
        }
    }

    #[test]
    fn recursive_glob_covers_everything_beneath_it() {
        assert_eq!(covers("/src/**", "/src/lib/a.rs"), Tri::Yes);
        assert_eq!(covers("/src/**", "/src/lib"), Tri::Yes);
        // `**` matches zero segments, so it covers the directory itself.
        assert_eq!(covers("/src/**", "/src"), Tri::Yes);
        assert_eq!(covers("/src/**", "/src/*"), Tri::Yes);
    }

    #[test]
    fn a_recursive_glob_is_not_covered_by_anything_narrower() {
        assert_eq!(covers("/src", "/src/**"), Tri::No);
        assert_eq!(covers("/src/*", "/src/**"), Tri::No);
    }

    #[test]
    fn disjoint_prefixes_do_not_cover_each_other() {
        assert_eq!(covers("/src/**", "/etc/passwd"), Tri::No);
        assert_eq!(covers("/etc/passwd", "/src/**"), Tri::No);
    }

    #[test]
    fn single_glob_matches_exactly_one_segment() {
        assert_eq!(covers("/src/*", "/src/lib"), Tri::Yes);
        assert_eq!(covers("/src/*", "/src/lib/a.rs"), Tri::No);
        assert_eq!(covers("/src/*", "/src"), Tri::No);
    }

    #[test]
    fn a_trailing_separator_does_not_change_meaning() {
        assert_eq!(covers("/src/", "/src"), Tri::Yes);
        assert_eq!(covers("/src", "/src/"), Tri::Yes);
    }

    #[test]
    fn non_path_resources_compare_as_single_segments() {
        assert_eq!(
            covers("api.example.com:443", "api.example.com:443"),
            Tri::Yes
        );
        assert_eq!(
            covers("api.example.com:443", "evil.example.com:443"),
            Tri::No
        );
        assert_eq!(covers("*", "api.example.com:443"), Tri::Yes);
    }

    #[test]
    fn bare_resources_only_cover_each_other() {
        assert_eq!(covers("", ""), Tri::Yes);
        assert_eq!(covers("", "/src"), Tri::No);
        assert_eq!(covers("/src", ""), Tri::No);
    }

    /// Regression: two *different* undecidable patterns must not be mistaken
    /// for each other. If opaque segments compared equal regardless of their
    /// text, these would parse identically and the equality short-circuit
    /// would report mutual containment — granting `*.py` to something that
    /// only asked for `*.rs`.
    #[test]
    fn distinct_undecidable_patterns_are_never_treated_as_equal() {
        assert_eq!(covers("/src/*.rs", "/src/*.py"), Tri::Unknown);
        assert_eq!(covers("/src/*.py", "/src/*.rs"), Tri::Unknown);
        assert_eq!(covers("{path}", "{other}"), Tri::Unknown);
        assert_eq!(overlaps("/src/*.rs", "/src/*.py"), Tri::Unknown);

        assert_ne!(
            Pattern::parse("/src/*.rs"),
            Pattern::parse("/src/*.py"),
            "opaque segments must carry their text"
        );
    }

    #[test]
    fn undecidable_patterns_report_unknown_rather_than_guessing() {
        // Partial-segment globs.
        assert_eq!(covers("/src/*.rs", "/src/main.rs"), Tri::Unknown);
        // Templates, unresolved until runtime.
        assert_eq!(covers("/src/**", "{path}"), Tri::Unknown);
        assert_eq!(covers("{path}", "/src/a"), Tri::Unknown);
        // `**` anywhere but the end.
        assert_eq!(covers("/a/**/b", "/a/x/b"), Tri::Unknown);
    }

    // ── overlaps ────────────────────────────────────────────────────────────

    #[test]
    fn identical_and_nested_patterns_overlap() {
        assert_eq!(overlaps("/src/**", "/src/**"), Tri::Yes);
        assert_eq!(overlaps("/src/**", "/src/lib/a.rs"), Tri::Yes);
        assert_eq!(overlaps("/src/lib/a.rs", "/src/**"), Tri::Yes);
    }

    #[test]
    fn sibling_paths_do_not_overlap() {
        assert_eq!(overlaps("/src/**", "/build/**"), Tri::No);
        assert_eq!(overlaps("/src/a", "/src/b"), Tri::No);
    }

    #[test]
    fn overlap_is_symmetric() {
        let cases = [
            ("/src/**", "/src/lib"),
            ("/src/**", "/build/**"),
            ("/src/*", "/src/a"),
            ("/a/b", "/a/b/c"),
        ];
        for (x, y) in cases {
            assert_eq!(overlaps(x, y), overlaps(y, x), "{x} vs {y}");
        }
    }

    #[test]
    fn different_depths_do_not_overlap_without_a_recursive_glob() {
        assert_eq!(overlaps("/a/b", "/a/b/c"), Tri::No);
        assert_eq!(overlaps("/a/*", "/a/b/c"), Tri::No);
    }

    #[test]
    fn overlap_is_unknown_for_undecidable_patterns() {
        assert_eq!(overlaps("/src/*.rs", "/src/main.rs"), Tri::Unknown);
        assert_eq!(overlaps("{path}", "/src/a"), Tri::Unknown);
    }

    #[test]
    fn covering_implies_overlapping() {
        let pairs = [
            ("/src/**", "/src/lib/a.rs"),
            ("/src/*", "/src/lib"),
            ("/src", "/src"),
        ];
        for (outer, inner) in pairs {
            assert_eq!(covers(outer, inner), Tri::Yes);
            assert_eq!(
                overlaps(outer, inner),
                Tri::Yes,
                "if {outer} covers {inner} they must overlap"
            );
        }
    }
}