didbot_policy_records/

merge.rs

//! Assembling every source into one [`didbot_policy::PolicyTree`].
//!
//! # No precedence engine, and none is needed
//!
//! `plan/policy.md`: "All three deny; none can permit what another denies,
//! so their order is a matter of where a policy is written and not of what
//! it can do." [`build`] registers builtin, then startup, then
//! operator-sourced policies, in that fixed order -- and each source's own
//! records ordered by id within it -- but nothing about the
//! *verdict* a write receives depends on that order, only on which reason
//! [`didbot_policy::combine`] reports when more than one policy denies the
//! same write. Deny-only monotonicity is what makes this true: adding a
//! policy from any source can only hold a verdict steady or make it more
//! severe, never less, so there is no shadowing between sources and nothing
//! for a precedence engine to arbitrate. The fixed order here exists only
//! so a report is reproducible, not because it changes what is enforced.

use std::collections::HashMap;

use didbot_policy::{PolicyId, PolicyTree, Revision};

use crate::builtin::BuiltinPolicy;
use crate::compile::{
    compile_policies, compiled_successfully, register, resolve_predicate, CompileReport, Language,
    PolicyWarning, ScopedDenial,
};
use crate::last_good::LastGoodPolicies;
use crate::record::ParsedPolicy;

/// One id whose current revision would not compile, still enforced at the
/// last revision that did -- `plan/policy.md`'s "was working, new revision
/// will not compile" state, told apart from a first-publish typo (which
/// stays a plain [`ScopedDenial`], with nothing to fall back to) precisely
/// by this type existing for it. See [`crate::last_good`]'s doc comment.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LastGoodFallback {
    /// The record's id.
    pub id: String,
    /// The revision still being enforced. See
    /// [`ParsedPolicy::revision`](crate::record::ParsedPolicy::revision) for
    /// who chooses the number.
    pub enforced_revision: Revision,
    /// The revision that arrived and failed to compile. See
    /// [`ParsedPolicy::revision`](crate::record::ParsedPolicy::revision).
    pub failed_revision: Revision,
    /// Why the failed revision could not be compiled.
    pub reason: String,
}

/// Everything worth telling an operator about a tree build: which
/// operator-or-startup-sourced records could not be compiled (scoped-deny,
/// per `crate::compile`), which compiled with a warning, which fell back to
/// a last-good revision, and which records were not policies at all,
/// reported by whichever source loaded them.
#[derive(Debug, Clone, Default)]
pub struct LoadReport {
    /// Records whose predicate this build could not compile, with no
    /// last-good revision to fall back to -- still registered, scoped, via
    /// [`didbot_policy::Predicate::Unusable`]. See [`crate::compile`].
    pub scoped_denials: Vec<ScopedDenial>,
    /// Records that compiled, but with something the operator should see.
    /// Never blocks the policy -- see
    /// [`didbot_policy::CompileOutcome::CompiledWithWarnings`].
    pub warnings: Vec<PolicyWarning>,
    /// Operator-sourced records whose current revision would not compile,
    /// still enforced at their last good revision. See [`LastGoodFallback`].
    pub last_good_fallbacks: Vec<LastGoodFallback>,
    /// Records that were not policies at all -- malformed `applicability`
    /// or another structural problem. Already source-labeled by whoever
    /// called this.
    pub malformed: Vec<String>,
    /// The tree position every policy was registered at, by its id: a
    /// built-in under its [`BuiltinPolicy::name`], a startup or operator
    /// record under the id it was compiled as -- see
    /// [`crate::compile::CompileReport::registered`].
    pub registered: HashMap<String, PolicyId>,
}

/// Build the full [`PolicyTree`] from every source.
///
/// `builtins` is source 1 ([`crate::builtin::builtin_policies`]). `startup`
/// is source 2's already-parsed records
/// supplied at startup, compiled with no last-good-revision fallback: it is
/// immutable for the run, so there is never a second revision to have fallen
/// back from. `operator` is source 3's current view -- a snapshot taken once
/// at the start of this call --
/// compiled *with* last-good-revision fallback via `last_good`, which must
/// be the same [`LastGoodPolicies`] passed on every call across this
/// deployment's lifetime, or there is nothing for a bad revision to fall
/// back to. `languages` are every [`Language`] this build carries, used to
/// compile `startup` and `operator` predicates (`builtins` need none: they
/// carry already-constructed evaluators).
pub fn build(
    builtins: Vec<BuiltinPolicy>,
    startup: &HashMap<String, ParsedPolicy>,
    operator: &HashMap<String, ParsedPolicy>,
    languages: &[&dyn Language],
    last_good: &LastGoodPolicies,
) -> (PolicyTree, LoadReport) {
    let mut builder = PolicyTree::builder();
    let mut report = LoadReport::default();

    // Source 1, compiled with the same call the other two immutable
    // source uses: a built-in is the record an operator would write, so
    // there is nothing here that reads it differently.
    let builtins: HashMap<String, ParsedPolicy> = builtins
        .into_iter()
        .map(|builtin| (builtin.name, builtin.policy))
        .collect();
    let builtin_report = compile_policies(by_id(&builtins), languages, &mut builder);
    report.scoped_denials.extend(builtin_report.denials);
    report.warnings.extend(builtin_report.warnings);
    report.registered.extend(builtin_report.registered);

    let startup_report = compile_policies(by_id(startup), languages, &mut builder);
    report.scoped_denials.extend(startup_report.denials);
    report.warnings.extend(startup_report.warnings);
    report.registered.extend(startup_report.registered);

    for (id, policy) in by_id(operator) {
        let mut attempt = CompileReport::default();
        let predicate = resolve_predicate(id, policy, languages, &mut builder, &mut attempt);

        if compiled_successfully(&attempt, id) {
            // This id's current revision compiled: it is the new last-good,
            // and it is what gets registered.
            report.warnings.extend(attempt.warnings);
            last_good.record_success(id, policy);
            let registered = register(&mut builder, policy, predicate);
            report.registered.insert(id.to_string(), registered);
            continue;
        }

        // This id's current revision did not compile. Fall back to the
        // last revision that did, if there is one -- recompiled fresh here
        // (cheap, and `Evaluator::compile` is required to be idempotent),
        // never the artifact this attempt half-built via
        // `register_evaluator` above, which is simply never referenced by
        // any registered policy and costs nothing beyond an unused `Vec`
        // slot. Never re-record `last_good` for the fallback itself: it is
        // already this id's stored entry, not a new observation.
        match last_good.get(id) {
            Some((good_revision, good_policy)) => {
                let mut fallback_report = CompileReport::default();
                let fallback_predicate = resolve_predicate(
                    id,
                    &good_policy,
                    languages,
                    &mut builder,
                    &mut fallback_report,
                );
                let registered = register(&mut builder, &good_policy, fallback_predicate);
                report.registered.insert(id.to_string(), registered);
                report.last_good_fallbacks.push(LastGoodFallback {
                    id: id.to_string(),
                    enforced_revision: good_revision,
                    failed_revision: policy.revision,
                    reason: attempt
                        .denials
                        .iter()
                        .find(|denial| denial.id == id)
                        .map(|denial| denial.reason.clone())
                        .unwrap_or_default(),
                });
            }
            None => {
                // Never compiled. Nothing to fall back to -- loud, per
                // `plan/policy.md`: register the failed predicate as-is
                // (Predicate::Unusable, scoped to its own applicability)
                // and let it stand as an ordinary scoped denial.
                report.scoped_denials.extend(attempt.denials);
                let registered = register(&mut builder, policy, predicate);
                report.registered.insert(id.to_string(), registered);
            }
        }
    }
    last_good.prune(operator);

    (builder.build(), report)
}

/// One source's records in a fixed order: by id, ascending.
///
/// `plan/policy.md` puts the order of the list the tree produces in this
/// server's hands precisely so "the reason reported for a denial is
/// stable." A source is stored as a `HashMap` keyed by at-uri (or by a
/// startup-file position), and iterating one is seeded randomly per map --
/// so handing `compile_policies` a raw `HashMap::iter` would assign a
/// different `PolicyId` to each record on every build, and two identical
/// tree builds would name different policies as the reason for the same
/// refusal. Nothing about the *verdict* changes either way; the stability
/// of what an operator is told does.
fn by_id(records: &std::collections::HashMap<String, ParsedPolicy>) -> Vec<(&str, &ParsedPolicy)> {
    let mut ordered: Vec<(&str, &ParsedPolicy)> = records
        .iter()
        .map(|(id, policy)| (id.as_str(), policy))
        .collect();
    ordered.sort_unstable_by_key(|(id, _)| *id);
    ordered
}

#[cfg(test)]
mod tests {
    use super::*;
    use didbot_policy::{
        AccountKind, ActionSet, Applicability, DeploymentAttributes, Diff, EvalError, Evaluator,
        KindSet, Lifecycle, Observed, Outcome, Scope, Staleness, Subject, SubjectAttributes,
        SubjectKind, Universal, WriteAction,
    };
    use std::collections::HashMap;
    use std::sync::{Arc, Mutex};

    struct RejectAll;
    impl Evaluator for RejectAll {
        fn compile(&self, _predicate: &serde_json::Value) -> didbot_policy::CompileOutcome {
            didbot_policy::CompileOutcome::Compiled(didbot_policy::CompiledId(0))
        }
        fn evaluate(
            &self,
            _subject: &Subject<'_>,
            _compiled: didbot_policy::CompiledId,
        ) -> Result<Outcome, EvalError> {
            Ok(Outcome::Reject {
                reason: "builtin denial".into(),
            })
        }
        fn observe(&self, _event: &Observed<'_>) {}
        fn lifecycle(&self, _event: &Lifecycle<'_>) {}
        fn staleness(&self) -> Staleness {
            Staleness::Linearized
        }
    }

    fn dummy_subject() -> Subject<'static> {
        Subject::Write {
            account: "did:plc:agent",
            attributes: SubjectAttributes {
                kind: SubjectKind::Known(AccountKind::Agent),
                handle: None,
                depth: None,
            },
            universal: Universal {
                deployment: DeploymentAttributes::default(),
                now: time::macros::datetime!(2026 - 01 - 01 0:00 UTC),
            },
            client_id: None,
            collection: "app.bsky.feed.post",
            action: WriteAction::Create,
            diff: Diff::default(),
            before: None,
            after: None,
            lookups: &[],
        }
    }

    /// A build with only a builtin denial still denies, with nothing
    /// supplied at startup and no operator view loaded -- the sources are
    /// genuinely independent inputs to the same tree.
    #[test]
    fn a_builtin_alone_still_denies() {
        struct RejectAllLanguage;
        impl Language for RejectAllLanguage {
            fn name(&self) -> &str {
                "reject-all"
            }
            fn new_evaluator(&self) -> Arc<dyn Evaluator> {
                Arc::new(RejectAll)
            }
        }
        let applicability = Applicability::Write {
            kinds: KindSet::ALL,
            collections: Scope::Any,
            actions: ActionSet::ALL,
            path_prefixes: Scope::Any,
        };
        let builtins = vec![BuiltinPolicy {
            name: "builtin/reject-all/0/record.write".to_owned(),
            policy: ParsedPolicy {
                observes: applicability.clone(),
                applicability,
                staleness: Staleness::Linearized,
                language: "reject-all".to_owned(),
                predicate: serde_json::json!({}),
                revision: Revision(0),
                lookups: Vec::new(),
            },
        }];
        let (tree, report) = build(
            builtins,
            &HashMap::new(),
            &HashMap::new(),
            &[&RejectAllLanguage],
            &LastGoodPolicies::new(),
        );
        assert!(report.scoped_denials.is_empty());
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { .. }
        ));
    }

    /// `plan/policy.md`: "the order is part of this server's version of
    /// the tree, so that the reason reported for a denial is stable."
    /// Building the same set of records twice must therefore report the
    /// same reason and name the same policy -- which iterating a
    /// `HashMap` does not give, since each map carries its own random
    /// seed.
    #[test]
    fn the_reason_reported_is_stable_across_two_builds_of_the_same_records() {
        fn records(n: usize) -> HashMap<String, ParsedPolicy> {
            (0..n)
                .map(|i| {
                    let policy = ParsedPolicy {
                        applicability: Applicability::Write {
                            kinds: KindSet::ALL,
                            collections: Scope::Any,
                            actions: ActionSet::ALL,
                            path_prefixes: Scope::Any,
                        },
                        observes: Applicability::Write {
                            kinds: KindSet::ALL,
                            collections: Scope::Any,
                            actions: ActionSet::ALL,
                            path_prefixes: Scope::Any,
                        },
                        staleness: Staleness::Linearized,
                        language: "regex".to_string(),
                        predicate: serde_json::json!({}),
                        revision: didbot_policy::Revision(1),
                        lookups: Vec::new(),
                    };
                    (format!("at://op/bot.did.policy/{i:02}"), policy)
                })
                .collect()
        }

        // Every record here compiles to `Predicate::Unusable` (no
        // languages registered), so all of them deny and the reported
        // reason names whichever one the tree put first.
        let first = build(
            Vec::new(),
            &HashMap::new(),
            &records(16),
            &[],
            &LastGoodPolicies::new(),
        );
        let second = build(
            Vec::new(),
            &HashMap::new(),
            &records(16),
            &[],
            &LastGoodPolicies::new(),
        );

        let reason_of = |tree: &didbot_policy::PolicyTree| match didbot_policy::evaluate(
            &dummy_subject(),
            tree,
        ) {
            didbot_policy::Verdict::Reject { reason, policy } => (reason, policy),
            other => panic!("expected a refusal, got {other:?}"),
        };
        assert_eq!(reason_of(&first.0), reason_of(&second.0));

        // And the report an operator reads is in the same order too.
        let ids = |report: &LoadReport| -> Vec<String> {
            report.scoped_denials.iter().map(|d| d.id.clone()).collect()
        };
        assert_eq!(ids(&first.1), ids(&second.1));
    }

    #[test]
    fn an_empty_build_allows_everything() {
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &HashMap::new(),
            &[],
            &LastGoodPolicies::new(),
        );
        assert!(report.scoped_denials.is_empty());
        assert_eq!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Allow
        );
    }

    /// A predicate `{"valid": bool, "reason": "..."}`: compiles (denying
    /// with `reason`) when `valid` is `true`, rejects otherwise -- just
    /// enough to drive last-good-revision tests without needing
    /// `didbot-policy-regex`.
    struct SwitchableEvaluator {
        reason: Mutex<Option<String>>,
    }
    impl SwitchableEvaluator {
        fn new() -> Self {
            Self {
                reason: Mutex::new(None),
            }
        }
    }
    impl Evaluator for SwitchableEvaluator {
        fn compile(&self, predicate: &serde_json::Value) -> didbot_policy::CompileOutcome {
            let valid = predicate
                .get("valid")
                .and_then(|v| v.as_bool())
                .unwrap_or(false);
            let reason = predicate
                .get("reason")
                .and_then(|v| v.as_str())
                .unwrap_or("denied")
                .to_string();
            if valid {
                *self.reason.lock().unwrap() = Some(reason);
                didbot_policy::CompileOutcome::Compiled(didbot_policy::CompiledId(0))
            } else {
                didbot_policy::CompileOutcome::Rejected(reason)
            }
        }
        fn evaluate(
            &self,
            _subject: &Subject<'_>,
            _compiled: didbot_policy::CompiledId,
        ) -> Result<Outcome, EvalError> {
            let reason = self.reason.lock().unwrap().clone().unwrap_or_default();
            Ok(Outcome::Reject { reason })
        }
        fn observe(&self, _event: &Observed<'_>) {}
        fn lifecycle(&self, _event: &Lifecycle<'_>) {}
        fn staleness(&self) -> Staleness {
            Staleness::Linearized
        }
    }
    struct SwitchableLanguage;
    impl Language for SwitchableLanguage {
        fn name(&self) -> &str {
            "switchable"
        }
        fn new_evaluator(&self) -> Arc<dyn Evaluator> {
            Arc::new(SwitchableEvaluator::new())
        }
    }

    fn switchable_policy(valid: bool, reason: &str, revision: u64) -> ParsedPolicy {
        ParsedPolicy {
            applicability: Applicability::Write {
                kinds: KindSet::ALL,
                collections: Scope::Any,
                actions: ActionSet::ALL,
                path_prefixes: Scope::Any,
            },
            observes: Applicability::Write {
                kinds: KindSet::ALL,
                collections: Scope::Any,
                actions: ActionSet::ALL,
                path_prefixes: Scope::Any,
            },
            staleness: Staleness::Linearized,
            language: "switchable".to_string(),
            predicate: serde_json::json!({
                "valid": valid,
                "reason": reason,
            }),
            revision: didbot_policy::Revision(revision),
            lookups: Vec::new(),
        }
    }

    /// The core of `plan/policy.md`'s last-good-revision behaviour: a
    /// policy that compiled at revision 1 and fails to compile at revision
    /// 2 keeps enforcing revision 1, and the failure is reported as a
    /// fallback rather than a plain scoped denial.
    #[test]
    fn a_bad_revision_falls_back_to_the_last_good_one() {
        let last_good = LastGoodPolicies::new();
        let languages: Vec<&dyn Language> = vec![&SwitchableLanguage];

        let mut operator = HashMap::new();
        operator.insert(
            "at://operator/bot.did.policy/1".to_string(),
            switchable_policy(true, "revision one enforced", 1),
        );
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(report.scoped_denials.is_empty());
        assert!(report.last_good_fallbacks.is_empty());
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { ref reason, .. } if reason == "revision one enforced"
        ));

        // Revision 2 arrives, broken.
        operator.insert(
            "at://operator/bot.did.policy/1".to_string(),
            switchable_policy(false, "revision two is broken", 2),
        );
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(
            report.scoped_denials.is_empty(),
            "a bad revision with a last-good fallback is not a plain scoped denial"
        );
        assert_eq!(report.last_good_fallbacks.len(), 1);
        assert_eq!(
            report.last_good_fallbacks[0].enforced_revision,
            didbot_policy::Revision(1)
        );
        assert_eq!(
            report.last_good_fallbacks[0].failed_revision,
            didbot_policy::Revision(2)
        );
        // Revision 1's own predicate is still what is enforced -- the edit
        // visibly did not land, rather than the write being denied by
        // revision 2's (broken) applicability or reason.
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { ref reason, .. } if reason == "revision one enforced"
        ));
    }

    /// A policy that has *never* compiled has nothing to fall back to: it
    /// is an ordinary, loud [`ScopedDenial`], not a
    /// [`LastGoodFallback`] -- the two states an operator must be able to
    /// tell apart.
    #[test]
    fn a_policy_that_never_compiled_is_a_plain_scoped_denial() {
        let last_good = LastGoodPolicies::new();
        let languages: Vec<&dyn Language> = vec![&SwitchableLanguage];

        let mut operator = HashMap::new();
        operator.insert(
            "at://operator/bot.did.policy/1".to_string(),
            switchable_policy(false, "never worked", 1),
        );
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert_eq!(report.scoped_denials.len(), 1);
        assert!(report.last_good_fallbacks.is_empty());
        // Still fail-closed within its own applicability -- a broken
        // never-compiled policy is loud to the operator, but the write
        // path itself is unaffected by which of the two report shapes
        // produced the denial.
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { .. }
        ));
    }

    /// A policy that compiles again after a bad revision replaces the
    /// last-good entry with the new success -- fixing the typo clears the
    /// fallback, it does not become permanent.
    #[test]
    fn a_later_good_revision_replaces_the_fallback() {
        let last_good = LastGoodPolicies::new();
        let languages: Vec<&dyn Language> = vec![&SwitchableLanguage];
        let id = "at://operator/bot.did.policy/1".to_string();

        let mut operator = HashMap::new();
        operator.insert(id.clone(), switchable_policy(true, "v1", 1));
        build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );

        operator.insert(id.clone(), switchable_policy(false, "v2 broken", 2));
        build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );

        operator.insert(id.clone(), switchable_policy(true, "v3", 3));
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(report.last_good_fallbacks.is_empty());
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { ref reason, .. } if reason == "v3"
        ));
    }

    /// Last-good-revision must not become a way to resurrect a policy the
    /// operator deleted. A source's view drops a record absent
    /// from a successful listing, so a deleted id simply stops appearing in
    /// `operator` -- but an at-uri is the operator's to reuse, and a *new*
    /// record published at a deleted one's rkey whose first revision does
    /// not compile would otherwise find the deleted policy's entry still
    /// sitting in `LastGoodPolicies` and enforce it. `build`'s prune is
    /// what closes that: a first publish that fails to compile is the loud,
    /// never-compiled state, whatever used to live at that id.
    #[test]
    fn a_deleted_id_leaves_nothing_for_a_later_record_to_fall_back_onto() {
        let last_good = LastGoodPolicies::new();
        let languages: Vec<&dyn Language> = vec![&SwitchableLanguage];
        let id = "at://operator/bot.did.policy/reused-rkey".to_string();

        // A policy that works, so it becomes this id's last-good.
        let mut operator = HashMap::new();
        operator.insert(id.clone(), switchable_policy(true, "the deleted policy", 1));
        let (tree, _) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(matches!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Reject { ref reason, .. } if reason == "the deleted policy"
        ));

        // The operator deletes it: the view no longer names the id at all.
        operator.remove(&id);
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(report.last_good_fallbacks.is_empty());
        assert_eq!(
            didbot_policy::evaluate(&dummy_subject(), &tree),
            didbot_policy::Verdict::Allow,
            "a deleted policy must not still be enforced"
        );

        // A new, unrelated record is published at the same at-uri, and its
        // very first revision does not compile.
        operator.insert(id.clone(), switchable_policy(false, "a fresh typo", 1));
        let (tree, report) = build(
            Vec::new(),
            &HashMap::new(),
            &operator,
            &languages,
            &last_good,
        );
        assert!(
            report.last_good_fallbacks.is_empty(),
            "the deleted policy is not a revision this record can fall back to"
        );
        assert_eq!(report.scoped_denials.len(), 1);
        match didbot_policy::evaluate(&dummy_subject(), &tree) {
            didbot_policy::Verdict::Reject { reason, .. } => assert_ne!(
                reason, "the deleted policy",
                "a deleted policy's predicate was resurrected at a reused at-uri"
            ),
            other => panic!("a never-compiled predicate must still deny, got {other:?}"),
        }
    }
}