Skip to main content

themis/
rebac.rs

1use std::collections::{HashMap, HashSet};
2use std::fmt;
3
4use serde::{Deserialize, Serialize};
5
6use crate::resource::ObjectRef;
7
8/// Wildcard id: the tuple `document:42#viewer@user:*` holds for every subject of kind `user`.
9pub const WILDCARD: &str = "*";
10
11/// Who is on the right-hand side of a tuple.
12#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
13#[serde(rename_all = "snake_case")]
14pub enum TupleSubject {
15    /// A direct object (`user:alice`, `user:*`).
16    Object(ObjectRef),
17    /// Everyone who has `relation` on `object` (`group:9#member`).
18    Userset(ObjectRef, String),
19}
20
21impl fmt::Display for TupleSubject {
22    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23        match self {
24            TupleSubject::Object(object) => write!(f, "{object}"),
25            TupleSubject::Userset(object, relation) => write!(f, "{object}#{relation}"),
26        }
27    }
28}
29
30/// Relation fact: `object#relation@subject`.
31#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
32pub struct Tuple {
33    pub object: ObjectRef,
34    pub relation: String,
35    pub subject: TupleSubject,
36}
37
38impl fmt::Display for Tuple {
39    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
40        write!(f, "{}#{}@{}", self.object, self.relation, self.subject)
41    }
42}
43
44impl Tuple {
45    pub fn new(object: ObjectRef, relation: impl Into<String>, subject: ObjectRef) -> Self {
46        Self {
47            object,
48            relation: relation.into(),
49            subject: TupleSubject::Object(subject),
50        }
51    }
52
53    pub fn userset(
54        object: ObjectRef,
55        relation: impl Into<String>,
56        set: ObjectRef,
57        set_relation: impl Into<String>,
58    ) -> Self {
59        Self {
60            object,
61            relation: relation.into(),
62            subject: TupleSubject::Userset(set, set_relation.into()),
63        }
64    }
65}
66
67/// Storage of the tuples. A database implementation queries by `(object, relation)`.
68pub trait TupleStore {
69    fn visit(&self, object: &ObjectRef, relation: &str, visitor: &mut dyn FnMut(&TupleSubject));
70}
71
72impl<T: TupleStore + ?Sized> TupleStore for &T {
73    fn visit(&self, object: &ObjectRef, relation: &str, visitor: &mut dyn FnMut(&TupleSubject)) {
74        (**self).visit(object, relation, visitor);
75    }
76}
77
78#[derive(Debug, Clone, Default)]
79pub struct InMemoryTuples {
80    map: HashMap<(ObjectRef, String), Vec<TupleSubject>>,
81}
82
83impl InMemoryTuples {
84    pub fn new() -> Self {
85        Self::default()
86    }
87
88    /// Returns `false` if the tuple already existed.
89    pub fn insert(&mut self, tuple: Tuple) -> bool {
90        let entry = self.map.entry((tuple.object, tuple.relation)).or_default();
91        if entry.contains(&tuple.subject) {
92            return false;
93        }
94        entry.push(tuple.subject);
95        true
96    }
97
98    pub fn remove(&mut self, tuple: &Tuple) -> bool {
99        let key = (tuple.object.clone(), tuple.relation.clone());
100        let Some(entry) = self.map.get_mut(&key) else {
101            return false;
102        };
103        let before = entry.len();
104        entry.retain(|s| s != &tuple.subject);
105        before != entry.len()
106    }
107
108    pub fn len(&self) -> usize {
109        self.map.values().map(Vec::len).sum()
110    }
111
112    pub fn is_empty(&self) -> bool {
113        self.len() == 0
114    }
115}
116
117impl FromIterator<Tuple> for InMemoryTuples {
118    fn from_iter<I: IntoIterator<Item = Tuple>>(iter: I) -> Self {
119        let mut store = Self::new();
120        for tuple in iter {
121            store.insert(tuple);
122        }
123        store
124    }
125}
126
127impl TupleStore for InMemoryTuples {
128    fn visit(&self, object: &ObjectRef, relation: &str, visitor: &mut dyn FnMut(&TupleSubject)) {
129        if let Some(subjects) = self.map.get(&(object.clone(), relation.to_string())) {
130            for subject in subjects {
131                visitor(subject);
132            }
133        }
134    }
135}
136
137/// How a relation is derived from others (Zanzibar's userset rewrite).
138#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
139#[serde(tag = "rewrite", rename_all = "snake_case")]
140pub enum Rewrite {
141    /// Only the tuples written for the relation itself.
142    This,
143    /// Another relation on the same object (`editor` implies `viewer`).
144    Computed {
145        relation: String,
146    },
147    /// Follows `tupleset` to the parent object and checks `computed` there (`parent->member`).
148    TupleToUserset {
149        tupleset: String,
150        computed: String,
151    },
152    Union {
153        of: Vec<Rewrite>,
154    },
155    Intersection {
156        of: Vec<Rewrite>,
157    },
158    Exclusion {
159        base: Box<Rewrite>,
160        subtract: Box<Rewrite>,
161    },
162}
163
164impl Rewrite {
165    pub fn computed(relation: impl Into<String>) -> Self {
166        Self::Computed {
167            relation: relation.into(),
168        }
169    }
170
171    pub fn from_parent(tupleset: impl Into<String>, computed: impl Into<String>) -> Self {
172        Self::TupleToUserset {
173            tupleset: tupleset.into(),
174            computed: computed.into(),
175        }
176    }
177
178    pub fn union(of: impl IntoIterator<Item = Rewrite>) -> Self {
179        Self::Union {
180            of: of.into_iter().collect(),
181        }
182    }
183
184    pub fn intersection(of: impl IntoIterator<Item = Rewrite>) -> Self {
185        Self::Intersection {
186            of: of.into_iter().collect(),
187        }
188    }
189
190    pub fn exclusion(base: Rewrite, subtract: Rewrite) -> Self {
191        Self::Exclusion {
192            base: Box::new(base),
193            subtract: Box::new(subtract),
194        }
195    }
196}
197
198static THIS: Rewrite = Rewrite::This;
199
200#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
201pub enum RebacError {
202    #[error("profundidade máxima de relação ({0}) excedida")]
203    DepthExceeded(usize),
204}
205
206/// Derivation rules by `(object kind, relation)`. A relation with no rule is [`Rewrite::This`].
207#[derive(Debug, Clone, Default)]
208pub struct RelationSchema {
209    rules: HashMap<(String, String), Rewrite>,
210}
211
212impl RelationSchema {
213    pub fn new() -> Self {
214        Self::default()
215    }
216
217    pub fn relation(mut self, kind: impl Into<String>, relation: impl Into<String>, rewrite: Rewrite) -> Self {
218        self.rules.insert((kind.into(), relation.into()), rewrite);
219        self
220    }
221
222    pub fn rewrite(&self, kind: &str, relation: &str) -> &Rewrite {
223        self.rules
224            .get(&(kind.to_string(), relation.to_string()))
225            .unwrap_or(&THIS)
226    }
227
228    /// Does `subject` have `relation` on `object`?
229    pub fn check(
230        &self,
231        store: &dyn TupleStore,
232        object: &ObjectRef,
233        relation: &str,
234        subject: &ObjectRef,
235        max_depth: usize,
236    ) -> Result<bool, RebacError> {
237        Checker {
238            schema: self,
239            store,
240            subject,
241            max_depth,
242            visiting: HashSet::new(),
243        }
244        .relation(object, relation, 0)
245    }
246}
247
248struct Checker<'a> {
249    schema: &'a RelationSchema,
250    store: &'a dyn TupleStore,
251    subject: &'a ObjectRef,
252    max_depth: usize,
253    visiting: HashSet<(ObjectRef, String)>,
254}
255
256impl<'a> Checker<'a> {
257    fn relation(&mut self, object: &ObjectRef, relation: &str, depth: usize) -> Result<bool, RebacError> {
258        if depth > self.max_depth {
259            return Err(RebacError::DepthExceeded(self.max_depth));
260        }
261        let key = (object.clone(), relation.to_string());
262        if !self.visiting.insert(key.clone()) {
263            return Ok(false);
264        }
265        let schema = self.schema;
266        let result = self.eval(schema.rewrite(&object.kind, relation), object, relation, depth);
267        self.visiting.remove(&key);
268        result
269    }
270
271    fn eval(
272        &mut self,
273        rewrite: &'a Rewrite,
274        object: &ObjectRef,
275        relation: &str,
276        depth: usize,
277    ) -> Result<bool, RebacError> {
278        match rewrite {
279            Rewrite::This => self.direct(object, relation, depth),
280            Rewrite::Computed { relation: other } => self.relation(object, other, depth + 1),
281            Rewrite::TupleToUserset { tupleset, computed } => {
282                for parent in self.subjects(object, tupleset) {
283                    let parent = match parent {
284                        TupleSubject::Object(o) | TupleSubject::Userset(o, _) => o,
285                    };
286                    if self.relation(&parent, computed, depth + 1)? {
287                        return Ok(true);
288                    }
289                }
290                Ok(false)
291            }
292            Rewrite::Union { of } => {
293                for rw in of {
294                    if self.eval(rw, object, relation, depth)? {
295                        return Ok(true);
296                    }
297                }
298                Ok(false)
299            }
300            Rewrite::Intersection { of } => {
301                if of.is_empty() {
302                    return Ok(false);
303                }
304                for rw in of {
305                    if !self.eval(rw, object, relation, depth)? {
306                        return Ok(false);
307                    }
308                }
309                Ok(true)
310            }
311            Rewrite::Exclusion { base, subtract } => {
312                Ok(self.eval(base, object, relation, depth)? && !self.eval(subtract, object, relation, depth)?)
313            }
314        }
315    }
316
317    fn direct(&mut self, object: &ObjectRef, relation: &str, depth: usize) -> Result<bool, RebacError> {
318        for subject in self.subjects(object, relation) {
319            match subject {
320                TupleSubject::Object(o) => {
321                    let wildcard = o.id == WILDCARD && o.kind == self.subject.kind && self.subject.id != WILDCARD;
322                    if o == *self.subject || wildcard {
323                        return Ok(true);
324                    }
325                }
326                TupleSubject::Userset(set, set_relation) => {
327                    if self.relation(&set, &set_relation, depth + 1)? {
328                        return Ok(true);
329                    }
330                }
331            }
332        }
333        Ok(false)
334    }
335
336    fn subjects(&self, object: &ObjectRef, relation: &str) -> Vec<TupleSubject> {
337        let mut out = Vec::new();
338        self.store.visit(object, relation, &mut |s| out.push(s.clone()));
339        out
340    }
341}
342
343#[cfg(test)]
344mod tests {
345    use super::*;
346
347    fn o(kind: &str, id: &str) -> ObjectRef {
348        ObjectRef::new(kind, id)
349    }
350
351    fn schema() -> RelationSchema {
352        RelationSchema::new()
353            .relation(
354                "document",
355                "editor",
356                Rewrite::union([Rewrite::This, Rewrite::computed("owner")]),
357            )
358            .relation(
359                "document",
360                "viewer",
361                Rewrite::union([
362                    Rewrite::This,
363                    Rewrite::computed("editor"),
364                    Rewrite::from_parent("parent", "member"),
365                ]),
366            )
367            .relation(
368                "document",
369                "commenter",
370                Rewrite::exclusion(Rewrite::computed("viewer"), Rewrite::computed("banned")),
371            )
372    }
373
374    fn store() -> InMemoryTuples {
375        [
376            Tuple::new(o("document", "d1"), "owner", o("user", "alice")),
377            Tuple::new(o("document", "d1"), "parent", o("folder", "f1")),
378            Tuple::new(o("folder", "f1"), "member", o("user", "bob")),
379            Tuple::userset(o("folder", "f1"), "member", o("group", "g1"), "member"),
380            Tuple::new(o("group", "g1"), "member", o("user", "carol")),
381            Tuple::new(o("document", "d1"), "banned", o("user", "bob")),
382            Tuple::new(o("document", "pub"), "viewer", o("user", WILDCARD)),
383        ]
384        .into_iter()
385        .collect()
386    }
387
388    fn check(object: ObjectRef, relation: &str, subject: ObjectRef) -> bool {
389        schema().check(&store(), &object, relation, &subject, 16).unwrap()
390    }
391
392    #[test]
393    fn computed_and_parent_relations() {
394        assert!(check(o("document", "d1"), "viewer", o("user", "alice")));
395        assert!(check(o("document", "d1"), "viewer", o("user", "bob")));
396        assert!(check(o("document", "d1"), "viewer", o("user", "carol")));
397        assert!(!check(o("document", "d1"), "editor", o("user", "bob")));
398        assert!(!check(o("document", "d1"), "viewer", o("user", "dave")));
399    }
400
401    #[test]
402    fn exclusion_removes_banned() {
403        assert!(check(o("document", "d1"), "commenter", o("user", "carol")));
404        assert!(!check(o("document", "d1"), "commenter", o("user", "bob")));
405    }
406
407    #[test]
408    fn wildcard_matches_any_subject_of_kind() {
409        assert!(check(o("document", "pub"), "viewer", o("user", "zed")));
410        assert!(!check(o("document", "pub"), "viewer", o("service", "zed")));
411    }
412
413    #[test]
414    fn tuple_display() {
415        let t = Tuple::userset(o("folder", "f1"), "member", o("group", "g1"), "member");
416        assert_eq!(t.to_string(), "folder:f1#member@group:g1#member");
417    }
418
419    #[test]
420    fn cycle_terminates_and_depth_is_bounded() {
421        let schema = RelationSchema::new().relation("a", "r", Rewrite::from_parent("next", "r"));
422        let store: InMemoryTuples = (0..50)
423            .map(|i| Tuple::new(o("a", &i.to_string()), "next", o("a", &(i + 1).to_string())))
424            .chain([Tuple::new(o("a", "x"), "next", o("a", "x"))])
425            .collect();
426        assert!(!schema.check(&store, &o("a", "x"), "r", &o("user", "u"), 16).unwrap());
427        assert_eq!(
428            schema.check(&store, &o("a", "0"), "r", &o("user", "u"), 16),
429            Err(RebacError::DepthExceeded(16))
430        );
431    }
432}