boundgraph-grant 0.1.0

//! A prefix trie over resource patterns.
//!
//! Disjointness asks the same question many times: "does *anything* in this
//! set of resources touch that one?" Answering it pairwise is quadratic and
//! re-walks the same shared prefixes for every pair. Indexing one side into a
//! trie keyed on path segments lets a probe abandon a whole subtree the moment
//! a literal fails to match.
//!
//! # Glob handling is explicit, not incidental
//!
//! The two wildcards live in different places in the structure, because they
//! mean different things:
//!
//! - `*` is an **edge**, parallel to the literal edges. It matches exactly one
//!   segment, so a probe following a literal must also follow `*`.
//! - `**` is a **terminal marker** on a node. It matches zero or more
//!   segments, so reaching that node at all is a match, whatever comes next.
//!
//! Patterns outside the decidable fragment cannot be indexed at all — there is
//! no segment structure to key on. They are held aside and compared pairwise,
//! where they yield [`Tri::Unknown`] and the compiler refuses.

use std::collections::BTreeMap;

use boundgraph_core::GrantAtom;

use crate::pattern::{Pattern, Seg, Tri, overlaps};

/// What a probe found.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub(crate) struct Probe {
    /// Index of an indexed atom proved to overlap, if any.
    pub(crate) hit: Option<usize>,
    /// Whether some comparison could not be decided.
    pub(crate) undecided: bool,
}

impl Probe {
    fn merge(self, other: Self) -> Self {
        Self {
            // A proved overlap outranks an undecided one: report the real
            // conflict rather than a solver gap.
            hit: self.hit.or(other.hit),
            undecided: self.undecided || other.undecided,
        }
    }

    fn hit(index: usize) -> Self {
        Self {
            hit: Some(index),
            undecided: false,
        }
    }

    fn undecided() -> Self {
        Self {
            hit: None,
            undecided: true,
        }
    }
}

#[derive(Debug, Default)]
struct Node {
    /// Exact segment edges.
    literal: BTreeMap<String, Node>,
    /// The `*` edge: matches any single segment.
    single: Option<Box<Node>>,
    /// Atoms whose pattern ends exactly here.
    terminal: Vec<usize>,
    /// Atoms whose pattern ends in `**` here — they match this node and
    /// everything beneath it.
    recursive: Vec<usize>,
}

impl Node {
    /// Whether anything at all is indexed at or below this node.
    fn has_any(&self) -> Option<usize> {
        self.terminal
            .first()
            .or_else(|| self.recursive.first())
            .copied()
            .or_else(|| {
                self.literal
                    .values()
                    .find_map(Node::has_any)
                    .or_else(|| self.single.as_ref().and_then(|n| n.has_any()))
            })
    }
}

/// Resources indexed by domain, then by path segment.
///
/// Atoms in different domains can never touch the same thing, so the domain is
/// the outermost key and cross-domain pairs are never compared at all.
#[derive(Debug, Default)]
pub(crate) struct ResourceTrie {
    by_domain: BTreeMap<String, Node>,
    /// Atoms that cannot be indexed, held for pairwise comparison.
    opaque: Vec<usize>,
    /// Every atom inserted, in insertion order; probes report these indices.
    atoms: Vec<GrantAtom>,
}

impl ResourceTrie {
    /// Index a set of atoms.
    pub(crate) fn build<'a>(atoms: impl IntoIterator<Item = &'a GrantAtom>) -> Self {
        let mut trie = Self::default();
        for atom in atoms {
            trie.insert(atom.clone());
        }
        trie
    }

    /// The atom a probe's index refers to.
    pub(crate) fn atom(&self, index: usize) -> &GrantAtom {
        &self.atoms[index]
    }

    fn insert(&mut self, atom: GrantAtom) {
        let index = self.atoms.len();
        let pattern = Pattern::parse(&atom.resource);
        let domain = atom.domain.clone();
        self.atoms.push(atom);

        if !pattern.is_decidable() {
            self.opaque.push(index);
            return;
        }

        let mut node = self.by_domain.entry(domain).or_default();
        for seg in pattern.segments() {
            match seg {
                Seg::Literal(l) => {
                    node = node.literal.entry(l.clone()).or_default();
                }
                Seg::Single => {
                    node = node.single.get_or_insert_with(Box::default);
                }
                Seg::Recursive => {
                    // `**` is final by construction, so this ends the walk.
                    node.recursive.push(index);
                    return;
                }
                Seg::Opaque(_) => unreachable!("decidable patterns hold no opaque segments"),
            }
        }
        node.terminal.push(index);
    }

    /// Whether any indexed atom can touch the same resource as `query`.
    pub(crate) fn probe(&self, query: &GrantAtom) -> Probe {
        let pattern = Pattern::parse(&query.resource);

        // Undecidable queries cannot be walked; compare them pairwise instead.
        let mut result = if pattern.is_decidable() {
            self.by_domain
                .get(&query.domain)
                .map(|root| probe_node(root, pattern.segments()))
                .unwrap_or_default()
        } else {
            self.pairwise_against_all(query)
        };

        // Undecidable *indexed* atoms are never in the trie, so they must be
        // compared pairwise whatever the query looks like.
        for &index in &self.opaque {
            let other = &self.atoms[index];
            if other.domain != query.domain {
                continue;
            }
            result = result.merge(match overlaps(&query.resource, &other.resource) {
                Tri::Yes => Probe::hit(index),
                Tri::Unknown => Probe::undecided(),
                Tri::No => Probe::default(),
            });
        }

        result
    }

    /// Compare an unindexable query against everything, pairwise.
    fn pairwise_against_all(&self, query: &GrantAtom) -> Probe {
        self.atoms
            .iter()
            .enumerate()
            .filter(|(i, a)| a.domain == query.domain && !self.opaque.contains(i))
            .fold(Probe::default(), |acc, (index, other)| {
                acc.merge(match overlaps(&query.resource, &other.resource) {
                    Tri::Yes => Probe::hit(index),
                    Tri::Unknown => Probe::undecided(),
                    Tri::No => Probe::default(),
                })
            })
    }
}

fn probe_node(node: &Node, query: &[Seg]) -> Probe {
    // An indexed `**` here swallows whatever the query has left, including
    // nothing at all.
    if let Some(&index) = node.recursive.first() {
        return Probe::hit(index);
    }

    let Some(head) = query.first() else {
        // The query ends here; only a pattern ending at the same depth matches.
        return node
            .terminal
            .first()
            .map_or_else(Probe::default, |&i| Probe::hit(i));
    };
    let rest = &query[1..];

    match head {
        // The query's `**` covers this node and everything under it.
        Seg::Recursive => node.has_any().map_or_else(Probe::default, Probe::hit),

        Seg::Literal(l) => {
            let via_literal = node
                .literal
                .get(l)
                .map_or_else(Probe::default, |n| probe_node(n, rest));
            // An indexed `*` also matches this one segment.
            let via_single = node
                .single
                .as_ref()
                .map_or_else(Probe::default, |n| probe_node(n, rest));
            via_literal.merge(via_single)
        }

        // The query's `*` matches any single segment, so every edge is live.
        Seg::Single => node
            .literal
            .values()
            .map(|n| probe_node(n, rest))
            .chain(node.single.as_ref().map(|n| probe_node(n, rest)))
            .fold(Probe::default(), Probe::merge),

        Seg::Opaque(_) => Probe::undecided(),
    }
}

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

    fn atoms(list: &[&str]) -> Vec<GrantAtom> {
        list.iter().map(|s| s.parse().unwrap()).collect()
    }

    fn probe_for(indexed: &[&str], query: &str) -> Probe {
        let owned = atoms(indexed);
        let trie = ResourceTrie::build(owned.iter());
        trie.probe(&query.parse().unwrap())
    }

    #[test]
    fn an_exact_match_is_found() {
        let p = probe_for(&["fs:read:/src/a.rs"], "fs:read:/src/a.rs");
        assert!(p.hit.is_some());
    }

    #[test]
    fn a_sibling_path_is_not_found() {
        let p = probe_for(&["fs:read:/src/a.rs"], "fs:read:/src/b.rs");
        assert!(p.hit.is_none());
        assert!(!p.undecided);
    }

    #[test]
    fn an_indexed_recursive_glob_swallows_anything_beneath_it() {
        let p = probe_for(&["fs:read:/src/**"], "fs:read:/src/lib/deep/a.rs");
        assert!(p.hit.is_some());
        // …and the directory itself.
        assert!(
            probe_for(&["fs:read:/src/**"], "fs:read:/src")
                .hit
                .is_some()
        );
    }

    #[test]
    fn a_query_recursive_glob_finds_anything_indexed_beneath_it() {
        let p = probe_for(&["fs:read:/src/lib/a.rs"], "fs:read:/src/**");
        assert!(p.hit.is_some());
    }

    #[test]
    fn single_globs_match_on_either_side() {
        assert!(
            probe_for(&["fs:read:/src/*"], "fs:read:/src/a")
                .hit
                .is_some()
        );
        assert!(
            probe_for(&["fs:read:/src/a"], "fs:read:/src/*")
                .hit
                .is_some()
        );
        // …but only one segment deep.
        assert!(
            probe_for(&["fs:read:/src/*"], "fs:read:/src/a/b")
                .hit
                .is_none()
        );
    }

    #[test]
    fn different_domains_are_never_compared() {
        let p = probe_for(&["fs:read:/src/**"], "net:read:/src/a");
        assert!(p.hit.is_none());
        assert!(!p.undecided);
    }

    #[test]
    fn different_depths_do_not_match() {
        assert!(probe_for(&["fs:read:/a/b"], "fs:read:/a").hit.is_none());
        assert!(probe_for(&["fs:read:/a"], "fs:read:/a/b").hit.is_none());
    }

    #[test]
    fn an_undecidable_indexed_atom_makes_the_probe_undecided() {
        let p = probe_for(&["fs:read:/src/*.rs"], "fs:read:/src/main.rs");
        assert!(p.hit.is_none());
        assert!(p.undecided);
    }

    #[test]
    fn an_undecidable_query_makes_the_probe_undecided() {
        let p = probe_for(&["fs:read:/src/main.rs"], "fs:read:{path}");
        assert!(p.undecided);
    }

    #[test]
    fn a_proved_overlap_outranks_an_undecided_one() {
        // One indexed atom definitely matches, another is undecidable. The
        // definite conflict must be what gets reported.
        let p = probe_for(
            &["fs:read:/src/*.rs", "fs:read:/src/main.rs"],
            "fs:read:/src/main.rs",
        );
        assert!(p.hit.is_some(), "the definite overlap must be reported");
    }

    #[test]
    fn the_reported_index_names_the_offending_atom() {
        let indexed = atoms(&["fs:read:/etc/**", "fs:read:/src/**"]);
        let trie = ResourceTrie::build(indexed.iter());
        let p = trie.probe(&"fs:read:/src/lib/a.rs".parse().unwrap());
        let hit = p.hit.expect("should overlap");
        assert_eq!(trie.atom(hit).resource, "/src/**");
    }

    #[test]
    fn an_empty_trie_finds_nothing() {
        let p = probe_for(&[], "fs:read:/src/a");
        assert!(p.hit.is_none());
        assert!(!p.undecided);
    }

    #[test]
    fn bare_resources_index_and_match() {
        assert!(probe_for(&["time:now"], "time:now").hit.is_some());
        assert!(probe_for(&["time:now"], "rand:bytes").hit.is_none());
    }
}