didbot_policy/

evaluate.rs

//! Ordered evaluation with deny-only semantics, made structural rather than
//! conventional.
//!
//! `plan/policy.md`: "Adding a policy can never widen what is permitted [...]
//! Order is presentational, not semantic." [`combine`] is the one place that
//! property lives: it folds outcomes by severity alone, so no matter what
//! order they arrive in, the *verdict* — allow, reject, or freeze — can only
//! stay the same or get more severe as more denying outcomes are folded in.
//! Only which reason is reported, when several outcomes tie for the worst
//! severity, depends on order.

use crate::index::PolicyTree;
use crate::outcome::Outcome;
use crate::policy::PolicyId;
use crate::subject::Subject;

/// The result of evaluating a subject against every candidate policy.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Verdict {
    /// No candidate policy denied the subject.
    Allow,
    /// At least one policy denied the subject, and no policy froze it.
    Reject {
        /// The reason of the first-encountered reject-or-worse outcome
        /// among those tied for most severe. Presentational: which policy
        /// is named here can depend on evaluation order; that a denial
        /// happened at all cannot.
        reason: String,
        /// Which policy authored `reason`.
        policy: PolicyId,
    },
    /// At least one policy froze the subject. Freezing is strictly more
    /// severe than rejecting — a frozen account needs an operator, a rejected
    /// write does not — so a freeze outranks any reject also present.
    Freeze {
        /// The reason of the first-encountered freeze outcome.
        reason: String,
        /// Which policy authored `reason`.
        policy: PolicyId,
    },
}

/// A total order on severity, `Allow < Reject < Freeze`, kept as a plain
/// function rather than a derived `Ord` on [`Outcome`] because `Outcome`'s
/// `reason` fields carry no ordering of their own.
fn severity(outcome: &Outcome) -> u8 {
    match outcome {
        Outcome::Allow => 0,
        Outcome::Reject { .. } => 1,
        Outcome::Freeze { .. } => 2,
    }
}

/// Fold a set of `(policy, outcome)` pairs into one [`Verdict`], taking the
/// most severe outcome regardless of the order the pairs arrive in — the
/// structural half of "order is presentational, not semantic".
///
/// Ties (more than one outcome at the worst severity) are broken by
/// input order: the first one seen is reported. That is the *only* thing
/// the order of `outcomes` can change.
pub fn combine(outcomes: impl IntoIterator<Item = (PolicyId, Outcome)>) -> Verdict {
    let mut best: Option<(u8, PolicyId, String)> = None;
    for (policy, outcome) in outcomes {
        let sev = severity(&outcome);
        if sev == 0 {
            continue;
        }
        let is_new_best = match &best {
            None => true,
            Some((best_sev, ..)) => sev > *best_sev,
        };
        if is_new_best {
            let reason = match outcome {
                Outcome::Reject { reason } | Outcome::Freeze { reason } => reason,
                Outcome::Allow => unreachable!("sev == 0 already continued"),
            };
            best = Some((sev, policy, reason));
        }
    }
    match best {
        None => Verdict::Allow,
        Some((2, policy, reason)) => Verdict::Freeze { reason, policy },
        Some((_, policy, reason)) => Verdict::Reject { reason, policy },
    }
}

/// Fold outcomes into the most severe one, taking `Allow < Reject < Freeze`
/// — the same total order [`combine`] folds by, exposed for callers that
/// hold outcomes without a [`PolicyId`] to attribute each one to.
///
/// The motivating caller is a batch of writes judged as a unit
/// (`com.atproto.repo.applyWrites`): each operation is judged on its own
/// subject and the batch's answer is the most severe of theirs, so a freeze
/// tripped by any one operation outranks a rejection tripped by another and
/// reaches the caller as a freeze. Ties are broken by input order, exactly as
/// in [`combine`]: the first outcome at the worst severity is the one whose
/// reason is reported.
///
/// Kept beside [`combine`] rather than reimplemented at each call site so
/// that severity precedence lives in exactly one place — the private
/// `severity` order both folds read — and a change to it cannot leave two
/// folds disagreeing.
pub fn worst(outcomes: impl IntoIterator<Item = Outcome>) -> Outcome {
    let mut best: Option<Outcome> = None;
    for outcome in outcomes {
        let sev = severity(&outcome);
        if sev == 0 {
            continue;
        }
        let is_new_best = match &best {
            None => true,
            Some(held) => sev > severity(held),
        };
        if is_new_best {
            best = Some(outcome);
        }
    }
    best.unwrap_or(Outcome::Allow)
}

/// Evaluate a subject against a [`PolicyTree`], in the tree's presentational
/// order.
///
/// Any [`EvalError`](crate::outcome::EvalError) from a candidate's evaluator,
/// and any candidate whose predicate is
/// [`Predicate::Unusable`](crate::policy::Predicate::Unusable) — see
/// [`PolicyTree::decide`] — is treated as a refusal: fail-closed, and
/// scoped to exactly the subject that predicate was asked about, never
/// escalated to [`Outcome::Freeze`] on its own. This is deny-only
/// monotonicity's third consequence from `plan/policy.md`: a predicate
/// that cannot answer can only make the verdict *more* restrictive, never
/// less.
///
/// The decision channel short-circuits: once a [`Outcome::Freeze`] is seen,
/// no severity can outrank it, so remaining candidates are not asked to
/// decide. (They may still be reached by
/// [`PolicyTree::observation_candidates`] — a separate walk this function
/// does not perform; see that method's doc comment for why observation is
/// independent of decision.)
pub fn evaluate(subject: &Subject<'_>, tree: &PolicyTree) -> Verdict {
    let mut outcomes = Vec::new();
    for policy in tree.decision_candidates(subject) {
        let outcome = tree.decide(subject, policy);
        let is_freeze = matches!(outcome, Outcome::Freeze { .. });
        outcomes.push((policy, outcome));
        if is_freeze {
            break;
        }
    }
    combine(outcomes)
}

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

    fn reject(text: &str) -> Outcome {
        Outcome::Reject {
            reason: text.to_string(),
        }
    }

    fn freeze(text: &str) -> Outcome {
        Outcome::Freeze {
            reason: text.to_string(),
        }
    }

    fn pid(i: u32) -> PolicyId {
        PolicyId(i)
    }

    #[test]
    fn worst_of_nothing_allows() {
        assert_eq!(worst(Vec::new()), Outcome::Allow);
        assert_eq!(worst(vec![Outcome::Allow, Outcome::Allow]), Outcome::Allow);
    }

    /// A freeze anywhere in the set outranks any rejection also present, and
    /// which position it occupies cannot change that — the property a batch
    /// of writes depends on to surface a freeze rather than a rejection.
    #[test]
    fn worst_takes_a_freeze_over_a_reject_in_any_order() {
        let base = [
            Outcome::Allow,
            reject("a"),
            freeze("b"),
            reject("c"),
            Outcome::Allow,
        ];
        for start in 0..base.len() {
            let mut rotated = base[start..].to_vec();
            rotated.extend_from_slice(&base[..start]);
            assert!(
                matches!(worst(rotated), Outcome::Freeze { .. }),
                "a Freeze anywhere in the set must win regardless of order"
            );
        }
    }

    /// Ties at the worst severity report the first one seen, which is what
    /// makes the reason a caller receives stable rather than arbitrary.
    #[test]
    fn worst_breaks_ties_toward_the_first_outcome_seen() {
        assert_eq!(
            worst(vec![Outcome::Allow, reject("first"), reject("second")]),
            reject("first")
        );
    }

    #[test]
    fn empty_outcomes_allow() {
        assert_eq!(combine(Vec::new()), Verdict::Allow);
    }

    #[test]
    fn a_single_reject_denies() {
        let v = combine(vec![(pid(0), reject("no"))]);
        assert_eq!(
            v,
            Verdict::Reject {
                reason: "no".into(),
                policy: pid(0)
            }
        );
    }

    /// Deny-only, made structural: no permutation of a fixed outcome set can
    /// change the verdict's *severity* — only which reason ties are broken
    /// toward. This is the property `plan/policy.md` calls "order is
    /// presentational, not semantic."
    #[test]
    fn shuffling_outcomes_cannot_change_the_verdict_severity() {
        use Outcome::*;
        let base = [
            (pid(0), Allow),
            (pid(1), reject("a")),
            (pid(2), Allow),
            (pid(3), freeze("b")),
            (pid(4), reject("c")),
        ];

        // Every rotation of the same multiset of outcomes.
        for start in 0..base.len() {
            let mut rotated = base[start..].to_vec();
            rotated.extend_from_slice(&base[..start]);
            let verdict = combine(rotated);
            assert!(
                matches!(verdict, Verdict::Freeze { .. }),
                "a Freeze anywhere in the set must win regardless of order"
            );
        }
    }

    /// Adding a policy — i.e. folding in one more outcome — can only hold
    /// the verdict's severity steady or increase it, never decrease it.
    /// That is monotonicity, made structural: nothing in `combine` can turn
    /// a Reject back into an Allow.
    #[test]
    fn adding_an_outcome_never_reduces_severity() {
        let mut outcomes = vec![(pid(0), Outcome::Allow)];
        assert_eq!(combine(outcomes.clone()), Verdict::Allow);

        outcomes.push((pid(1), reject("no")));
        assert!(matches!(combine(outcomes.clone()), Verdict::Reject { .. }));

        outcomes.push((pid(2), Outcome::Allow));
        assert!(
            matches!(combine(outcomes.clone()), Verdict::Reject { .. }),
            "an added Allow cannot undo an earlier Reject"
        );

        outcomes.push((pid(3), freeze("worse")));
        assert!(matches!(combine(outcomes), Verdict::Freeze { .. }));
    }

    /// Two rejects tied for worst severity: which reason is reported can
    /// depend on order (presentational), but both orders still deny
    /// (semantic content is order-independent).
    #[test]
    fn tied_severity_reports_the_first_seen_reason() {
        let first = combine(vec![(pid(0), reject("a")), (pid(1), reject("b"))]);
        let second = combine(vec![(pid(1), reject("b")), (pid(0), reject("a"))]);
        assert!(matches!(first, Verdict::Reject { ref reason, .. } if reason == "a"));
        assert!(matches!(second, Verdict::Reject { ref reason, .. } if reason == "b"));
    }
}