1use std::collections::{HashMap, HashSet};
2use std::fmt;
3
4use serde::{Deserialize, Serialize};
5
6use crate::resource::ObjectRef;
7
8pub const WILDCARD: &str = "*";
10
11#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
13#[serde(rename_all = "snake_case")]
14pub enum TupleSubject {
15 Object(ObjectRef),
17 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#[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
67pub 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 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#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
139#[serde(tag = "rewrite", rename_all = "snake_case")]
140pub enum Rewrite {
141 This,
143 Computed {
145 relation: String,
146 },
147 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#[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 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}