1use crate::errors::{AuthError, Result};
20use serde::{Deserialize, Serialize};
21use std::collections::{HashMap, HashSet, VecDeque};
22use std::sync::Arc;
23use tokio::sync::RwLock;
24
25#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
29pub struct RelationTuple {
30 pub object: String,
32 pub relation: String,
34 pub subject: String,
37}
38
39impl RelationTuple {
40 pub fn new(
42 object: impl Into<String>,
43 relation: impl Into<String>,
44 subject: impl Into<String>,
45 ) -> Self {
46 Self {
47 object: object.into(),
48 relation: relation.into(),
49 subject: subject.into(),
50 }
51 }
52
53 pub fn parse_subject(&self) -> Option<(&str, &str, Option<&str>)> {
58 let (ns_id, userset) = if let Some(hash_pos) = self.subject.find('#') {
59 (
60 &self.subject[..hash_pos],
61 Some(&self.subject[hash_pos + 1..]),
62 )
63 } else {
64 (self.subject.as_str(), None)
65 };
66 let colon_pos = ns_id.find(':')?;
67 Some((&ns_id[..colon_pos], &ns_id[colon_pos + 1..], userset))
68 }
69
70 pub fn parse_object(&self) -> Option<(&str, &str)> {
74 let pos = self.object.find(':')?;
75 Some((&self.object[..pos], &self.object[pos + 1..]))
76 }
77}
78
79#[derive(Debug, Clone, Serialize, Deserialize)]
83pub struct NamespaceConfig {
84 pub name: String,
86 pub relations: HashMap<String, RelationDef>,
88}
89
90#[derive(Debug, Clone, Serialize, Deserialize)]
92pub struct RelationDef {
93 #[serde(default = "default_true")]
95 pub direct: bool,
96 #[serde(default)]
99 pub union: Vec<String>,
100 #[serde(default)]
104 pub tuple_to_userset: Vec<TupleToUserset>,
105}
106
107fn default_true() -> bool {
108 true
109}
110
111#[derive(Debug, Clone, Serialize, Deserialize)]
113pub struct TupleToUserset {
114 pub tupleset_relation: String,
116 pub computed_userset_relation: String,
118}
119
120pub struct ZanzibarStore {
124 namespaces: Arc<RwLock<HashMap<String, NamespaceConfig>>>,
126 tuples: Arc<RwLock<HashMap<String, Vec<RelationTuple>>>>,
128 max_depth: usize,
130}
131
132impl ZanzibarStore {
133 pub fn new(max_depth: usize) -> Self {
135 Self {
136 namespaces: Arc::new(RwLock::new(HashMap::new())),
137 tuples: Arc::new(RwLock::new(HashMap::new())),
138 max_depth,
139 }
140 }
141
142 pub async fn add_namespace(&self, config: NamespaceConfig) {
144 self.namespaces
145 .write()
146 .await
147 .insert(config.name.clone(), config);
148 }
149
150 pub async fn write_tuple(&self, tuple: RelationTuple) -> Result<()> {
152 if let Some((ns, _)) = tuple.parse_object() {
154 let namespaces = self.namespaces.read().await;
155 if let Some(ns_config) = namespaces.get(ns)
156 && !ns_config.relations.contains_key(&tuple.relation)
157 {
158 return Err(AuthError::validation(format!(
159 "Relation '{}' not defined in namespace '{}'",
160 tuple.relation, ns
161 )));
162 }
163 }
164
165 self.tuples
166 .write()
167 .await
168 .entry(tuple.object.clone())
169 .or_default()
170 .push(tuple);
171 Ok(())
172 }
173
174 pub async fn delete_tuple(&self, tuple: &RelationTuple) -> bool {
176 let mut tuples = self.tuples.write().await;
177 if let Some(list) = tuples.get_mut(&tuple.object) {
178 let before = list.len();
179 list.retain(|t| t != tuple);
180 list.len() < before
181 } else {
182 false
183 }
184 }
185
186 pub async fn read_tuples(&self, object: &str, relation: Option<&str>) -> Vec<RelationTuple> {
188 let tuples = self.tuples.read().await;
189 match tuples.get(object) {
190 Some(list) => {
191 if let Some(rel) = relation {
192 list.iter().filter(|t| t.relation == rel).cloned().collect()
193 } else {
194 list.clone()
195 }
196 }
197 None => Vec::new(),
198 }
199 }
200
201 pub async fn check(&self, object: &str, relation: &str, subject: &str) -> Result<bool> {
206 let mut visited = HashSet::new();
207 self.check_internal(object, relation, subject, 0, &mut visited)
208 .await
209 }
210
211 #[allow(
212 clippy::only_used_in_recursion,
213 reason = "self is used only by the recursive call; it stays a method of the checker"
214 )]
215 fn check_internal<'a>(
216 &'a self,
217 object: &'a str,
218 relation: &'a str,
219 subject: &'a str,
220 depth: usize,
221 visited: &'a mut HashSet<String>,
222 ) -> std::pin::Pin<Box<dyn std::future::Future<Output = Result<bool>> + Send + 'a>> {
223 Box::pin(async move {
224 if depth > self.max_depth {
225 return Err(AuthError::internal(
226 "Zanzibar check exceeded maximum traversal depth",
227 ));
228 }
229
230 let visit_key = format!("{object}#{relation}@{subject}");
231 if !visited.insert(visit_key) {
232 return Ok(false); }
234
235 let direct_tuples = self.read_tuples(object, Some(relation)).await;
237 for t in &direct_tuples {
238 if t.subject == subject {
239 return Ok(true);
240 }
241
242 if let Some((_, sub_id, Some(sub_rel))) = t.parse_subject() {
244 let (sub_ns, _) = t.subject.split_once('#').unwrap_or((&t.subject, ""));
245 if self
247 .check_internal(sub_ns, sub_rel, subject, depth + 1, visited)
248 .await?
249 {
250 let _ = sub_id; return Ok(true);
252 }
253 }
254 }
255
256 if let Some((ns, _)) = object.split_once(':') {
258 let namespaces = self.namespaces.read().await;
259 if let Some(ns_config) = namespaces.get(ns)
260 && let Some(rel_def) = ns_config.relations.get(relation)
261 {
262 for union_rel in &rel_def.union {
264 if self
265 .check_internal(object, union_rel, subject, depth + 1, visited)
266 .await?
267 {
268 return Ok(true);
269 }
270 }
271
272 for ttu in &rel_def.tuple_to_userset {
274 let parent_tuples =
275 self.read_tuples(object, Some(&ttu.tupleset_relation)).await;
276 for pt in &parent_tuples {
277 if self
278 .check_internal(
279 &pt.subject,
280 &ttu.computed_userset_relation,
281 subject,
282 depth + 1,
283 visited,
284 )
285 .await?
286 {
287 return Ok(true);
288 }
289 }
290 }
291 }
292 }
293
294 Ok(false)
295 })
296 }
297
298 pub async fn expand(&self, object: &str, relation: &str) -> Result<Vec<String>> {
300 let mut result = Vec::new();
301 let mut visited = HashSet::new();
302 self.expand_internal(object, relation, 0, &mut result, &mut visited)
303 .await?;
304 Ok(result)
305 }
306
307 fn expand_internal<'a>(
308 &'a self,
309 object: &'a str,
310 relation: &'a str,
311 depth: usize,
312 result: &'a mut Vec<String>,
313 visited: &'a mut HashSet<String>,
314 ) -> std::pin::Pin<Box<dyn std::future::Future<Output = Result<()>> + Send + 'a>> {
315 Box::pin(async move {
316 if depth > self.max_depth {
317 return Ok(());
318 }
319
320 let visit_key = format!("{object}#{relation}");
321 if !visited.insert(visit_key) {
322 return Ok(());
323 }
324
325 let tuples = self.read_tuples(object, Some(relation)).await;
327 for t in &tuples {
328 if let Some((ref_obj, ref_rel)) = t.subject.split_once('#') {
329 self.expand_internal(ref_obj, ref_rel, depth + 1, result, visited)
331 .await?;
332 } else if !result.contains(&t.subject) {
333 result.push(t.subject.clone());
334 }
335 }
336
337 if let Some((ns, _)) = object.split_once(':') {
339 let namespaces = self.namespaces.read().await;
340 if let Some(ns_config) = namespaces.get(ns)
341 && let Some(rel_def) = ns_config.relations.get(relation)
342 {
343 for union_rel in &rel_def.union {
344 self.expand_internal(object, union_rel, depth + 1, result, visited)
345 .await?;
346 }
347 for ttu in &rel_def.tuple_to_userset {
348 let parent_tuples =
349 self.read_tuples(object, Some(&ttu.tupleset_relation)).await;
350 for pt in &parent_tuples {
351 self.expand_internal(
352 &pt.subject,
353 &ttu.computed_userset_relation,
354 depth + 1,
355 result,
356 visited,
357 )
358 .await?;
359 }
360 }
361 }
362 }
363
364 Ok(())
365 })
366 }
367
368 pub async fn list_objects(
371 &self,
372 object_type: &str,
373 relation: &str,
374 subject: &str,
375 ) -> Result<Vec<String>> {
376 let prefix = format!("{object_type}:");
377 let tuples = self.tuples.read().await;
378
379 let mut found = Vec::new();
380 let mut queue: VecDeque<String> = VecDeque::new();
381 let mut seen = HashSet::new();
382
383 for key in tuples.keys() {
385 if key.starts_with(&prefix) {
386 queue.push_back(key.clone());
387 }
388 }
389
390 while let Some(obj) = queue.pop_front() {
391 if !seen.insert(obj.clone()) {
392 continue;
393 }
394 drop(tuples);
396 if self.check(&obj, relation, subject).await? {
397 found.push(obj);
398 }
399 break; }
402
403 let candidates: Vec<String> = {
405 let tuples = self.tuples.read().await;
406 tuples
407 .keys()
408 .filter(|k| k.starts_with(&prefix))
409 .cloned()
410 .collect()
411 };
412
413 let mut result = Vec::new();
414 for obj in candidates {
415 if self.check(&obj, relation, subject).await? {
416 result.push(obj);
417 }
418 }
419 Ok(result)
420 }
421
422 pub async fn tuple_count(&self) -> usize {
424 self.tuples.read().await.values().map(|v| v.len()).sum()
425 }
426}
427
428impl Default for ZanzibarStore {
429 fn default() -> Self {
430 Self::new(15)
431 }
432}
433
434#[cfg(test)]
435mod tests {
436 use super::*;
437
438 #[test]
441 fn test_tuple_parse_object() {
442 let t = RelationTuple::new("document:readme", "viewer", "user:alice");
443 let (ns, id) = t.parse_object().unwrap();
444 assert_eq!(ns, "document");
445 assert_eq!(id, "readme");
446 }
447
448 #[test]
449 fn test_tuple_parse_subject_direct() {
450 let t = RelationTuple::new("document:readme", "viewer", "user:alice");
451 let (ns, id, userset) = t.parse_subject().unwrap();
452 assert_eq!(ns, "user");
453 assert_eq!(id, "alice");
454 assert_eq!(userset, None);
455 }
456
457 #[test]
458 fn test_tuple_parse_subject_userset() {
459 let t = RelationTuple::new("document:readme", "viewer", "group:eng#member");
460 let (ns, id, userset) = t.parse_subject().unwrap();
461 assert_eq!(ns, "group");
462 assert_eq!(id, "eng");
463 assert_eq!(userset, Some("member"));
464 }
465
466 #[test]
467 fn test_tuple_serialization() {
468 let t = RelationTuple::new("doc:1", "viewer", "user:alice");
469 let json = serde_json::to_string(&t).unwrap();
470 let parsed: RelationTuple = serde_json::from_str(&json).unwrap();
471 assert_eq!(parsed, t);
472 }
473
474 #[tokio::test]
477 async fn test_direct_relation_check() {
478 let store = ZanzibarStore::default();
479 store
480 .write_tuple(RelationTuple::new(
481 "document:readme",
482 "viewer",
483 "user:alice",
484 ))
485 .await
486 .unwrap();
487
488 assert!(
489 store
490 .check("document:readme", "viewer", "user:alice")
491 .await
492 .unwrap()
493 );
494 assert!(
495 !store
496 .check("document:readme", "viewer", "user:bob")
497 .await
498 .unwrap()
499 );
500 assert!(
501 !store
502 .check("document:readme", "editor", "user:alice")
503 .await
504 .unwrap()
505 );
506 }
507
508 #[tokio::test]
511 async fn test_union_relation() {
512 let store = ZanzibarStore::default();
513
514 store
516 .add_namespace(NamespaceConfig {
517 name: "document".to_string(),
518 relations: HashMap::from([
519 (
520 "editor".to_string(),
521 RelationDef {
522 direct: true,
523 union: vec![],
524 tuple_to_userset: vec![],
525 },
526 ),
527 (
528 "viewer".to_string(),
529 RelationDef {
530 direct: true,
531 union: vec!["editor".to_string()],
532 tuple_to_userset: vec![],
533 },
534 ),
535 ]),
536 })
537 .await;
538
539 store
540 .write_tuple(RelationTuple::new(
541 "document:readme",
542 "editor",
543 "user:alice",
544 ))
545 .await
546 .unwrap();
547
548 assert!(
550 store
551 .check("document:readme", "viewer", "user:alice")
552 .await
553 .unwrap()
554 );
555 assert!(
557 store
558 .check("document:readme", "editor", "user:alice")
559 .await
560 .unwrap()
561 );
562 assert!(
564 !store
565 .check("document:readme", "viewer", "user:bob")
566 .await
567 .unwrap()
568 );
569 }
570
571 #[tokio::test]
574 async fn test_tuple_to_userset() {
575 let store = ZanzibarStore::default();
576
577 store
579 .add_namespace(NamespaceConfig {
580 name: "document".to_string(),
581 relations: HashMap::from([
582 (
583 "parent".to_string(),
584 RelationDef {
585 direct: true,
586 union: vec![],
587 tuple_to_userset: vec![],
588 },
589 ),
590 (
591 "viewer".to_string(),
592 RelationDef {
593 direct: true,
594 union: vec![],
595 tuple_to_userset: vec![TupleToUserset {
596 tupleset_relation: "parent".to_string(),
597 computed_userset_relation: "viewer".to_string(),
598 }],
599 },
600 ),
601 ]),
602 })
603 .await;
604
605 store
606 .add_namespace(NamespaceConfig {
607 name: "folder".to_string(),
608 relations: HashMap::from([(
609 "viewer".to_string(),
610 RelationDef {
611 direct: true,
612 union: vec![],
613 tuple_to_userset: vec![],
614 },
615 )]),
616 })
617 .await;
618
619 store
621 .write_tuple(RelationTuple::new("folder:docs", "viewer", "user:alice"))
622 .await
623 .unwrap();
624
625 store
627 .write_tuple(RelationTuple::new(
628 "document:readme",
629 "parent",
630 "folder:docs",
631 ))
632 .await
633 .unwrap();
634
635 assert!(
637 store
638 .check("document:readme", "viewer", "user:alice")
639 .await
640 .unwrap()
641 );
642 assert!(
644 !store
645 .check("document:readme", "viewer", "user:bob")
646 .await
647 .unwrap()
648 );
649 }
650
651 #[tokio::test]
654 async fn test_group_membership_userset() {
655 let store = ZanzibarStore::default();
656
657 store
658 .add_namespace(NamespaceConfig {
659 name: "group".to_string(),
660 relations: HashMap::from([(
661 "member".to_string(),
662 RelationDef {
663 direct: true,
664 union: vec![],
665 tuple_to_userset: vec![],
666 },
667 )]),
668 })
669 .await;
670
671 store
672 .add_namespace(NamespaceConfig {
673 name: "document".to_string(),
674 relations: HashMap::from([(
675 "viewer".to_string(),
676 RelationDef {
677 direct: true,
678 union: vec![],
679 tuple_to_userset: vec![],
680 },
681 )]),
682 })
683 .await;
684
685 store
687 .write_tuple(RelationTuple::new("group:eng", "member", "user:alice"))
688 .await
689 .unwrap();
690
691 store
693 .write_tuple(RelationTuple::new(
694 "document:readme",
695 "viewer",
696 "group:eng#member",
697 ))
698 .await
699 .unwrap();
700
701 assert!(
703 store
704 .check("document:readme", "viewer", "user:alice")
705 .await
706 .unwrap()
707 );
708 assert!(
710 !store
711 .check("document:readme", "viewer", "user:bob")
712 .await
713 .unwrap()
714 );
715 }
716
717 #[tokio::test]
720 async fn test_expand() {
721 let store = ZanzibarStore::default();
722
723 store
724 .write_tuple(RelationTuple::new(
725 "document:readme",
726 "viewer",
727 "user:alice",
728 ))
729 .await
730 .unwrap();
731 store
732 .write_tuple(RelationTuple::new("document:readme", "viewer", "user:bob"))
733 .await
734 .unwrap();
735 store
736 .write_tuple(RelationTuple::new(
737 "document:readme",
738 "editor",
739 "user:carol",
740 ))
741 .await
742 .unwrap();
743
744 let viewers = store.expand("document:readme", "viewer").await.unwrap();
745 assert_eq!(viewers.len(), 2);
746 assert!(viewers.contains(&"user:alice".to_string()));
747 assert!(viewers.contains(&"user:bob".to_string()));
748 }
749
750 #[tokio::test]
753 async fn test_delete_tuple() {
754 let store = ZanzibarStore::default();
755 let tuple = RelationTuple::new("document:readme", "viewer", "user:alice");
756
757 store.write_tuple(tuple.clone()).await.unwrap();
758 assert!(
759 store
760 .check("document:readme", "viewer", "user:alice")
761 .await
762 .unwrap()
763 );
764
765 assert!(store.delete_tuple(&tuple).await);
766 assert!(
767 !store
768 .check("document:readme", "viewer", "user:alice")
769 .await
770 .unwrap()
771 );
772 }
773
774 #[tokio::test]
775 async fn test_delete_nonexistent_tuple() {
776 let store = ZanzibarStore::default();
777 let tuple = RelationTuple::new("document:readme", "viewer", "user:alice");
778 assert!(!store.delete_tuple(&tuple).await);
779 }
780
781 #[tokio::test]
784 async fn test_tuple_count() {
785 let store = ZanzibarStore::default();
786 assert_eq!(store.tuple_count().await, 0);
787
788 store
789 .write_tuple(RelationTuple::new("doc:1", "viewer", "user:a"))
790 .await
791 .unwrap();
792 store
793 .write_tuple(RelationTuple::new("doc:2", "viewer", "user:b"))
794 .await
795 .unwrap();
796 assert_eq!(store.tuple_count().await, 2);
797 }
798
799 #[tokio::test]
802 async fn test_invalid_relation_rejected() {
803 let store = ZanzibarStore::default();
804 store
805 .add_namespace(NamespaceConfig {
806 name: "document".to_string(),
807 relations: HashMap::from([(
808 "viewer".to_string(),
809 RelationDef {
810 direct: true,
811 union: vec![],
812 tuple_to_userset: vec![],
813 },
814 )]),
815 })
816 .await;
817
818 let result = store
819 .write_tuple(RelationTuple::new("document:readme", "admin", "user:alice"))
820 .await;
821 assert!(result.is_err());
822 }
823
824 #[tokio::test]
827 async fn test_cycle_protection() {
828 let store = ZanzibarStore::new(5);
829
830 store
832 .write_tuple(RelationTuple::new("group:a", "member", "group:b#member"))
833 .await
834 .unwrap();
835 store
836 .write_tuple(RelationTuple::new("group:b", "member", "group:a#member"))
837 .await
838 .unwrap();
839
840 let result = store.check("group:a", "member", "user:alice").await;
842 if let Ok(v) = result {
844 assert!(!v);
845 }
846 }
847
848 #[tokio::test]
851 async fn test_read_tuples_with_filter() {
852 let store = ZanzibarStore::default();
853 store
854 .write_tuple(RelationTuple::new("doc:1", "viewer", "user:a"))
855 .await
856 .unwrap();
857 store
858 .write_tuple(RelationTuple::new("doc:1", "editor", "user:b"))
859 .await
860 .unwrap();
861
862 let viewers = store.read_tuples("doc:1", Some("viewer")).await;
863 assert_eq!(viewers.len(), 1);
864 assert_eq!(viewers[0].subject, "user:a");
865
866 let all = store.read_tuples("doc:1", None).await;
867 assert_eq!(all.len(), 2);
868 }
869
870 #[tokio::test]
871 async fn test_read_tuples_empty() {
872 let store = ZanzibarStore::default();
873 let result = store.read_tuples("doc:nonexistent", None).await;
874 assert!(result.is_empty());
875 }
876}