didbot_policy_records/
bindings.rs

1//! Whom each policy is bound to: the reach a `bot.did.policyBinding` record
2//! describes, and the index a gate asks before it consults a policy.
3//!
4//! A policy says what is refused; a binding says whom it is refused to. Both
5//! are deny-only, so the policies applying to an account are the union over
6//! every binding that covers it, and a binding covers an account when
7//! [`Coverage::covers`] says so: the account is a subject, or is admitted
8//! beneath one, and is neither excluded nor beneath an excluded account.
9//! "Beneath" is the admission tree the server walks; a browser knows only
10//! the account it was told about, so it asks with a [`Boundary`] of that
11//! account alone.
12
13use std::collections::{BTreeMap, HashMap};
14
15use didbot_policy::PolicyId;
16
17use crate::records::{Includes, PolicyBinding};
18
19/// The chain of principals an account is judged within: the account first,
20/// then each principal above it. Empty for a request no account has made
21/// yet, which only a binding on the whole server reaches.
22#[derive(Debug, Clone, Default, PartialEq, Eq)]
23pub struct Boundary {
24    /// The chain, nearest first.
25    pub principals: Vec<String>,
26}
27
28impl Boundary {
29    /// A boundary over `principals`, nearest first.
30    #[must_use]
31    pub fn of(principals: Vec<String>) -> Self {
32        Self { principals }
33    }
34
35    /// A boundary holding one account and nothing above it.
36    #[must_use]
37    pub fn alone(did: &str) -> Self {
38        Self::of(vec![did.to_owned()])
39    }
40
41    /// The boundary of a request no account has made: only what covers the
42    /// whole server applies.
43    #[must_use]
44    pub fn server_wide() -> Self {
45        Self::default()
46    }
47}
48
49/// Whom one binding reaches.
50#[derive(Debug, Clone, PartialEq, Eq)]
51pub struct Coverage {
52    /// The accounts the binding starts from.
53    pub subjects: Vec<String>,
54    /// Whether the subjects themselves, their descendants, or both.
55    pub includes: Includes,
56    /// Accounts left out, along with everything beneath them.
57    pub excludes: Vec<String>,
58}
59
60impl Coverage {
61    /// The reach `binding` describes.
62    #[must_use]
63    pub fn of(binding: &PolicyBinding) -> Self {
64        Self {
65            subjects: binding.subjects.clone(),
66            includes: binding.includes,
67            excludes: binding.excludes.clone(),
68        }
69    }
70
71    /// Whether this reaches the account judged within `boundary` on the
72    /// server whose service DID is `server`. The server stands above every
73    /// chain, so naming it as a subject with `descendants` reaches every
74    /// account, and excluding it leaves everyone out.
75    #[must_use]
76    pub fn covers(&self, boundary: &Boundary, server: &str) -> bool {
77        let chain = &boundary.principals;
78        let names = |list: &[String], did: &str| list.iter().any(|named| named == did);
79        if names(&self.excludes, server) || chain.iter().any(|did| names(&self.excludes, did)) {
80            return false;
81        }
82        let account = chain.first().map(String::as_str);
83        let by_subject =
84            self.includes.subjects && account.is_some_and(|did| names(&self.subjects, did));
85        let by_descent = self.includes.descendants
86            && (chain.iter().skip(1).any(|did| names(&self.subjects, did))
87                || (account != Some(server) && names(&self.subjects, server)));
88        by_subject || by_descent
89    }
90}
91
92/// Whom each policy in a tree is bound to, by the tree's own id for it.
93///
94/// A policy with no entry is unbound — compiled in, or supplied at startup
95/// — and applies to every account. A policy with an entry applies within
96/// a [`Boundary`] one of its coverages reaches, and one with an empty entry
97/// applies to nobody.
98#[derive(Debug, Clone, Default)]
99pub struct BindingIndex {
100    server: String,
101    bound: HashMap<PolicyId, Vec<Coverage>>,
102    /// Each policy's id in the build: `{key}/{statement}/{action}` for a
103    /// record, the name for a built-in.
104    names: HashMap<PolicyId, String>,
105}
106
107impl BindingIndex {
108    /// The index over one build's records: every declaration `registered`
109    /// holds a tree position for, carrying the reach of every binding that
110    /// names the record it was declared from.
111    ///
112    /// `ids` is the declaration ids each policy record was declared under
113    /// — [`crate::set::Read::ids`]. Also returns the record keys no binding
114    /// names, in key order: compiled, and applied to nobody.
115    #[must_use]
116    pub fn of(
117        server: &str,
118        bindings: &BTreeMap<String, PolicyBinding>,
119        ids: &BTreeMap<String, Vec<String>>,
120        registered: &HashMap<String, PolicyId>,
121    ) -> (Self, Vec<String>) {
122        let mut coverages: HashMap<&str, Vec<Coverage>> = HashMap::new();
123        for binding in bindings.values() {
124            for policy in &binding.policies {
125                coverages
126                    .entry(policy.key.as_str())
127                    .or_default()
128                    .push(Coverage::of(binding));
129            }
130        }
131        let mut bound = HashMap::new();
132        let mut unbound = Vec::new();
133        for (key, ids) in ids {
134            let coverage = coverages.remove(key.as_str()).unwrap_or_default();
135            if coverage.is_empty() {
136                unbound.push(key.clone());
137            }
138            for id in ids {
139                if let Some(policy) = registered.get(id) {
140                    bound.insert(*policy, coverage.clone());
141                }
142            }
143        }
144        unbound.sort();
145        let names = registered
146            .iter()
147            .map(|(id, policy)| (*policy, id.clone()))
148            .collect();
149        (
150            Self {
151                server: server.to_owned(),
152                bound,
153                names,
154            },
155            unbound,
156        )
157    }
158
159    /// The id `policy` was registered under, for a refusal that names it.
160    #[must_use]
161    pub fn name_of(&self, policy: PolicyId) -> Option<&str> {
162        self.names.get(&policy).map(String::as_str)
163    }
164
165    /// Whether `policy` reaches the account judged within `boundary`.
166    #[must_use]
167    pub fn applies(&self, policy: PolicyId, boundary: &Boundary) -> bool {
168        match self.bound.get(&policy) {
169            None => true,
170            Some(coverages) => coverages
171                .iter()
172                .any(|coverage| coverage.covers(boundary, &self.server)),
173        }
174    }
175
176    /// How many policies carry a binding.
177    #[must_use]
178    pub fn len(&self) -> usize {
179        self.bound.len()
180    }
181
182    /// Whether no policy carries a binding.
183    #[must_use]
184    pub fn is_empty(&self) -> bool {
185        self.bound.is_empty()
186    }
187}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192
193    const SERVER: &str = "did:web:agents.example";
194    const POOL: &str = "did:web:pool.agents.example";
195    const HOST: &str = "did:web:host.agents.example";
196    const AGENT: &str = "did:web:agent.agents.example";
197
198    fn coverage(subjects: &[&str], includes: &[&str], excludes: &[&str]) -> Coverage {
199        Coverage {
200            subjects: subjects.iter().map(|s| (*s).to_owned()).collect(),
201            includes: Includes {
202                subjects: includes.contains(&"subjects"),
203                descendants: includes.contains(&"descendants"),
204            },
205            excludes: excludes.iter().map(|s| (*s).to_owned()).collect(),
206        }
207    }
208
209    /// The chain agent -> host -> pool, and the five ways a binding
210    /// reaches or misses the agent at the bottom of it.
211    #[test]
212    fn coverage_follows_the_chain_and_the_exclusions() {
213        let agent = Boundary::of(vec![AGENT.into(), HOST.into(), POOL.into()]);
214        let host = Boundary::of(vec![HOST.into(), POOL.into()]);
215        let pool = Boundary::alone(POOL);
216
217        let subjects_only = coverage(&[POOL], &["subjects"], &[]);
218        assert!(subjects_only.covers(&pool, SERVER));
219        assert!(!subjects_only.covers(&host, SERVER));
220
221        let descendants_only = coverage(&[POOL], &["descendants"], &[]);
222        assert!(!descendants_only.covers(&pool, SERVER));
223        assert!(descendants_only.covers(&host, SERVER));
224        assert!(descendants_only.covers(&agent, SERVER));
225
226        let carved = coverage(&[POOL], &["descendants"], &[HOST]);
227        assert!(!carved.covers(&host, SERVER), "the excluded account");
228        assert!(!carved.covers(&agent, SERVER), "and everything beneath it");
229
230        let whole_server = coverage(&[SERVER], &["descendants"], &[]);
231        assert!(whole_server.covers(&agent, SERVER));
232        assert!(whole_server.covers(&Boundary::alone("did:web:root.agents.example"), SERVER));
233        assert!(whole_server.covers(&Boundary::server_wide(), SERVER));
234        assert!(!coverage(&[SERVER], &["subjects"], &[]).covers(&agent, SERVER));
235
236        let elsewhere = coverage(
237            &["did:web:other.example"],
238            &["subjects", "descendants"],
239            &[],
240        );
241        assert!(!elsewhere.covers(&agent, SERVER));
242        assert!(!elsewhere.covers(&Boundary::server_wide(), SERVER));
243    }
244}
didbot_policy_records/bindings.rs

didbot_policy_records/
bindings.rs
