didbot_policy/

index.rs

//! The applicability index: the tree that turns a subject into an ordered
//! list of candidate policies.
//!
//! `plan/policy.md`: "The tree indexes; the list evaluates [...] a write
//! matching nothing has paid only for a walk it already owed." Two
//! independent trees are built per subject shape — one from each policy's
//! decision applicability, one from its observation surface — because a
//! policy can be told about an attempt without being asked to decide it.

use std::collections::HashMap;
use std::sync::Arc;

use crate::outcome::Evaluator;
use crate::outcome::Outcome;
use crate::policy::{
    Applicability, CompiledId, EvaluatorId, KindSet, PolicyDeclaration, PolicyId, Predicate, Scope,
};
use crate::subject::{Change, Subject, SubjectKind, WriteAction};

/// Split one path into the segments this index routes on: `.` separates
/// them, and an `[index]` subscript is a segment of its own rather than
/// part of the field name it follows.
///
/// Both halves of the convention exist because the write path that produces
/// a [`Change::path`] writes an array element as `tags[0]` and a nested one
/// as `labels.values[0].val` (see `didbot_pds::policy::diff`). Splitting on
/// `.` alone would make `tags[0]` a single opaque segment that the declared
/// prefix `tags` could never be an ancestor of — so a policy guarding a
/// field would silently stop guarding it the moment that field held an
/// array, while the identical policy over a scalar field worked. A prefix
/// can still name a specific element (`tags[0]`) by writing the subscript
/// out; it segments the same way on both sides.
fn segments(path: &str) -> Vec<&str> {
    let mut out = Vec::new();
    for part in path.split('.') {
        let mut start = 0;
        for (i, c) in part.char_indices() {
            if c == '[' && i > start {
                out.push(&part[start..i]);
                start = i;
            } else if c == ']' {
                out.push(&part[start..=i]);
                start = i + c.len_utf8();
            }
        }
        if start < part.len() || start == 0 {
            out.push(&part[start..]);
        }
    }
    out
}

/// A trie over changed-path segments, as [`segments`] splits them.
///
/// `here` holds policies whose declared prefix ends at this node — which
/// includes the root, for `Scope::Any` path prefixes, so those match a write
/// regardless of its diff, even one with no changed paths.
#[derive(Debug, Default)]
struct PathNode {
    here: Vec<PolicyId>,
    children: HashMap<String, PathNode>,
}

impl PathNode {
    fn insert_here(&mut self, policy: PolicyId) {
        self.here.push(policy);
    }

    fn insert_at(&mut self, prefix: &str, policy: PolicyId) {
        let mut node = self;
        for segment in segments(prefix) {
            node = node.children.entry(segment.to_string()).or_default();
        }
        node.here.push(policy);
    }

    /// Collect every policy whose declared prefix is an ancestor of, or
    /// equal to, `path` — walking exactly the segments `path` has, never
    /// more.
    fn collect(&self, path: &str, out: &mut Vec<PolicyId>) {
        let mut node = self;
        for segment in segments(path) {
            match node.children.get(segment) {
                Some(next) => {
                    node = next;
                    out.extend_from_slice(&node.here);
                }
                None => return,
            }
        }
    }
}

/// One collection's trie, plus the action and account-kind filters each
/// entry was declared with. Both are indexed in parallel with a
/// synthetic per-policy mask recorded at insertion — kept as side tables
/// rather than inline in [`PathNode`] so the trie stays generic over "a
/// policy matched here" and each filter test stays one lookup, not a scan.
#[derive(Debug, Default)]
struct CollectionTrie {
    paths: PathNode,
    actions: HashMap<PolicyId, crate::policy::ActionSet>,
    kinds: HashMap<PolicyId, KindSet>,
}

/// The write-subject index: collection, then changed path, then action.
#[derive(Debug, Default)]
struct WriteIndex {
    /// Policies declared for a specific set of collections.
    by_collection: HashMap<String, CollectionTrie>,
    /// Policies declared with `Scope::Any` collections — checked for every
    /// write regardless of its collection.
    any_collection: CollectionTrie,
}

impl WriteIndex {
    fn insert(
        &mut self,
        policy: PolicyId,
        collections: &Scope<String>,
        kinds: KindSet,
        actions: crate::policy::ActionSet,
        path_prefixes: &Scope<String>,
    ) {
        let apply = |trie: &mut CollectionTrie| {
            trie.actions.insert(policy, actions);
            trie.kinds.insert(policy, kinds);
            match path_prefixes {
                Scope::Any => trie.paths.insert_here(policy),
                Scope::Only(prefixes) => {
                    for prefix in prefixes {
                        trie.paths.insert_at(prefix, policy);
                    }
                }
            }
        };
        match collections {
            Scope::Any => apply(&mut self.any_collection),
            Scope::Only(names) => {
                for name in names {
                    apply(self.by_collection.entry(name.clone()).or_default());
                }
            }
        }
    }

    /// A write matching no policy costs exactly this: at most two hash
    /// lookups (the specific collection, the `Scope::Any` bucket) and,
    /// only when one of those exists, a walk bounded by the write's own
    /// changed paths — never by the number of policies registered.
    ///
    /// `changes` carries before/after values (see [`Change`]); this index
    /// only ever reads `change.path` out of it — routing is on where a
    /// write touched, not on what it changed to. A value predicate belongs
    /// in the evaluator that a matched policy names, with the full
    /// `Change` and [`Subject`] available to it.
    fn candidates(
        &self,
        collection: &str,
        kind: SubjectKind<'_>,
        action: WriteAction,
        changes: &[Change<'_>],
    ) -> Vec<PolicyId> {
        let mut out = Vec::new();
        for trie in [
            Some(&self.any_collection),
            self.by_collection.get(collection),
        ]
        .into_iter()
        .flatten()
        {
            let mut matched = trie.paths.here.clone();
            for change in changes {
                trie.paths.collect(change.path, &mut matched);
            }
            matched.retain(|policy| {
                trie.actions
                    .get(policy)
                    .is_some_and(|set| set.contains(action))
                    && trie.kinds.get(policy).is_some_and(|set| set.contains(kind))
            });
            out.extend(matched);
        }
        out.sort_unstable_by_key(|p| p.index());
        out.dedup();
        out
    }
}

/// The index for a subject keyed on its client alone: a grant or a token.
#[derive(Debug, Default)]
struct ClientIndex {
    by_client: HashMap<String, Vec<PolicyId>>,
    any_client: Vec<PolicyId>,
}

impl ClientIndex {
    fn insert(&mut self, policy: PolicyId, client_ids: &Scope<String>) {
        match client_ids {
            Scope::Any => self.any_client.push(policy),
            Scope::Only(ids) => {
                for id in ids {
                    self.by_client.entry(id.clone()).or_default().push(policy);
                }
            }
        }
    }

    fn candidates(&self, client_id: &str) -> Vec<PolicyId> {
        let mut out = self.any_client.clone();
        if let Some(specific) = self.by_client.get(client_id) {
            out.extend_from_slice(specific);
        }
        out.sort_unstable_by_key(|p| p.index());
        out.dedup();
        out
    }
}

/// One tree per subject shape.
#[derive(Debug, Default)]
struct Trees {
    write: WriteIndex,
    blob: Vec<PolicyId>,
    grant: ClientIndex,
    token: ClientIndex,
    create: Vec<PolicyId>,
}

impl Trees {
    fn insert(&mut self, policy: PolicyId, applicability: &Applicability) {
        match applicability {
            Applicability::Write {
                kinds,
                collections,
                actions,
                path_prefixes,
            } => self
                .write
                .insert(policy, collections, *kinds, *actions, path_prefixes),
            Applicability::Blob => self.blob.push(policy),
            Applicability::Grant { client_ids } => self.grant.insert(policy, client_ids),
            Applicability::Token { client_ids } => self.token.insert(policy, client_ids),
            Applicability::Create => self.create.push(policy),
        }
    }

    fn candidates(&self, subject: &Subject<'_>) -> Vec<PolicyId> {
        match subject {
            Subject::Write {
                attributes,
                collection,
                action,
                diff,
                ..
            } => self
                .write
                .candidates(collection, attributes.kind, *action, diff.changes),
            Subject::Blob { .. } => self.blob.clone(),
            Subject::Grant { client_id, .. } => self.grant.candidates(client_id.as_str()),
            Subject::Token { client_id, .. } => self.token.candidates(client_id.as_str()),
            Subject::Create { .. } => self.create.clone(),
        }
    }
}

/// The pair of trees every subject is routed through: decision and
/// observation.
#[derive(Debug, Default)]
struct ShapeIndex {
    decision: Trees,
    observation: Trees,
}

/// The built applicability index: every registered policy's predicate, and
/// the decision and observation trees to route a subject through.
///
/// Built once, from a fixed set of [`PolicyDeclaration`]s, via
/// [`PolicyTreeBuilder`]. `PolicyId` order is registration order, which is
/// this server's presentational evaluation order — see `PolicyId`'s doc
/// comment.
pub struct PolicyTree {
    evaluators: Vec<Arc<dyn Evaluator>>,
    predicates: Vec<Predicate>,
    index: ShapeIndex,
}

impl PolicyTree {
    /// Start building a tree.
    pub fn builder() -> PolicyTreeBuilder {
        PolicyTreeBuilder::default()
    }

    /// Every evaluator this tree holds, each named once regardless of how
    /// many policies it serves.
    ///
    /// A lifecycle event (froze, unfroze, deleted — see
    /// [`Evaluator::lifecycle`]) is about an *account*, not a subject shape
    /// or a collection, so it has no applicability to route it through the
    /// way [`decision_candidates`](Self::decision_candidates) and
    /// [`observation_candidates`](Self::observation_candidates) do for a
    /// subject. A caller telling every evaluator about a lifecycle
    /// event — see `plan/policy.md`'s "An evaluator can never unfreeze [...]
    /// the evaluator must be told, or the state that triggered the freeze
    /// survives the unfreeze and slams it shut again" — needs the complete
    /// set, not a filtered one, which is what this returns.
    pub fn evaluators(&self) -> impl Iterator<Item = &Arc<dyn Evaluator>> {
        self.evaluators.iter()
    }

    /// The evaluator responsible for `policy`, if it has one.
    ///
    /// `None` for a policy whose [`Predicate`] is
    /// [`Unusable`](Predicate::Unusable) — there is nothing to call
    /// `observe` or `lifecycle` on. A caller walking
    /// [`observation_candidates`](Self::observation_candidates) skips such
    /// a policy for those two channels; [`decide`](Self::decide) already
    /// accounts for it on the decision channel.
    ///
    /// Panics if `policy` did not come from this tree — the same programmer
    /// error as indexing a `Vec` out of bounds, and treated the same way.
    pub fn evaluator(&self, policy: PolicyId) -> Option<&dyn Evaluator> {
        match &self.predicates[policy.index() as usize] {
            Predicate::Evaluator(evaluator_id, _) => {
                Some(self.evaluators[evaluator_id.0 as usize].as_ref())
            }
            Predicate::Unusable { .. } => None,
        }
    }

    /// The compiled artifact `policy`'s evaluator was told to use, if it
    /// has one — see [`CompiledId`]'s doc comment. `None` for a policy
    /// whose predicate is [`Unusable`](Predicate::Unusable), same as
    /// [`evaluator`](Self::evaluator): there is no artifact to name.
    ///
    /// Panics if `policy` did not come from this tree — see
    /// [`evaluator`](Self::evaluator).
    pub fn compiled_id(&self, policy: PolicyId) -> Option<CompiledId> {
        match &self.predicates[policy.index() as usize] {
            Predicate::Evaluator(_, compiled) => Some(*compiled),
            Predicate::Unusable { .. } => None,
        }
    }

    /// What `policy` decides about `subject`, handling both a working
    /// evaluator and an [`Unusable`](Predicate::Unusable) predicate the
    /// same way `evaluate` handles an [`EvalError`](crate::outcome::EvalError):
    /// fail-closed, scoped to exactly this policy's applicability.
    ///
    /// Panics if `policy` did not come from this tree — see
    /// [`evaluator`](Self::evaluator).
    pub fn decide(&self, subject: &Subject<'_>, policy: PolicyId) -> Outcome {
        self.decide_detailed(subject, policy).0
    }

    /// [`decide`](Self::decide), plus whether the outcome is the evaluator's
    /// own decision (`false`) or a fail-closed refusal this tree substituted
    /// because the evaluator could not answer at all (`true`): an
    /// [`EvalError`](crate::outcome::EvalError), or a predicate that never
    /// compiled. The gate never needs the difference — both refuse alike —
    /// but a page explaining a refusal to an operator does: "the policy
    /// refused this" and "the policy could not be checked" are different
    /// claims, and only this method's caller can tell them apart.
    ///
    /// Panics if `policy` did not come from this tree — see
    /// [`evaluator`](Self::evaluator).
    pub fn decide_detailed(&self, subject: &Subject<'_>, policy: PolicyId) -> (Outcome, bool) {
        match &self.predicates[policy.index() as usize] {
            Predicate::Evaluator(evaluator_id, compiled) => {
                let evaluator = self.evaluators[evaluator_id.0 as usize].as_ref();
                match evaluator.evaluate(subject, *compiled) {
                    Ok(outcome) => (outcome, false),
                    Err(err) => (
                        Outcome::Reject {
                            // `EvalError`'s own `Display` already says what
                            // kind of failure this was ("evaluator timed
                            // out", "evaluator failed: ..."); wrapping it in
                            // another "evaluator failed:" would say it twice.
                            reason: err.to_string(),
                        },
                        true,
                    ),
                }
            }
            Predicate::Unusable { reason } => (
                Outcome::Reject {
                    reason: format!("policy predicate unusable: {reason}"),
                },
                true,
            ),
        }
    }

    /// The ordered candidate policies this subject may be decided by.
    ///
    /// For a write matching nothing, this costs only a tree walk bounded by
    /// the write's own changed paths, never by how many policies are
    /// registered — no evaluator is invoked.
    pub fn decision_candidates(&self, subject: &Subject<'_>) -> Vec<PolicyId> {
        self.index.decision.candidates(subject)
    }

    /// The ordered set of policies whose *observation* surface — not
    /// necessarily their decision surface — this subject falls under.
    ///
    /// Independent of [`decision_candidates`](Self::decision_candidates):
    /// a policy can watch attempts it has no say in deciding.
    pub fn observation_candidates(&self, subject: &Subject<'_>) -> Vec<PolicyId> {
        self.index.observation.candidates(subject)
    }
}

/// Builds a [`PolicyTree`] from a set of evaluators and the policies that
/// use them.
#[derive(Default)]
pub struct PolicyTreeBuilder {
    evaluators: Vec<Arc<dyn Evaluator>>,
    declarations: Vec<PolicyDeclaration>,
}

impl PolicyTreeBuilder {
    /// Register an evaluator, returning the id later policies reference.
    /// One evaluator may serve many policies.
    pub fn register_evaluator(&mut self, evaluator: Arc<dyn Evaluator>) -> EvaluatorId {
        let id = EvaluatorId(self.evaluators.len() as u32);
        self.evaluators.push(evaluator);
        id
    }

    /// Add a policy, returning its [`PolicyId`]. Policies are assigned ids
    /// in the order they are added here, which becomes the tree's
    /// presentational evaluation order.
    ///
    /// Panics if `declaration.predicate` names an evaluator id that was not
    /// returned by [`register_evaluator`](Self::register_evaluator) on
    /// this builder — a programmer error in the caller wiring up the tree,
    /// not a runtime condition.
    /// [`Predicate::Unusable`] needs no
    /// such check: it names no evaluator to have registered.
    pub fn add_policy(&mut self, declaration: PolicyDeclaration) -> PolicyId {
        if let Predicate::Evaluator(evaluator_id, _) = &declaration.predicate {
            assert!(
                (evaluator_id.0 as usize) < self.evaluators.len(),
                "policy declared for an evaluator id this builder never registered"
            );
        }
        let id = PolicyId(self.declarations.len() as u32);
        self.declarations.push(declaration);
        id
    }

    /// Build the tree.
    pub fn build(self) -> PolicyTree {
        let mut predicates = Vec::with_capacity(self.declarations.len());
        let mut index = ShapeIndex::default();
        for (i, decl) in self.declarations.iter().enumerate() {
            let policy = PolicyId(i as u32);
            predicates.push(decl.predicate.clone());
            index.decision.insert(policy, &decl.applicability);
            index.observation.insert(policy, &decl.observes);
        }
        PolicyTree {
            evaluators: self.evaluators,
            predicates,
            index,
        }
    }
}

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

    /// The write path writes an array element as `tags[0]` and a nested
    /// one as `labels.values[0].val`. A subscript has to be its own
    /// segment or a declared prefix naming the field can never be an
    /// ancestor of the element's path.
    #[test]
    fn a_subscript_is_its_own_segment() {
        assert_eq!(segments("displayName"), vec!["displayName"]);
        assert_eq!(segments("tags[0]"), vec!["tags", "[0]"]);
        assert_eq!(
            segments("labels.values[0].val"),
            vec!["labels", "values", "[0]", "val"]
        );
        assert_eq!(segments("grid[0][1]"), vec!["grid", "[0]", "[1]"]);
        assert_eq!(segments(""), vec![""]);
        assert_eq!(segments("a..b"), vec!["a", "", "b"]);
    }
}