1use std::collections::{BTreeSet, HashMap, HashSet};
36use std::fmt;
37use std::sync::{Arc, RwLock};
38
39pub const MAX_DEPTH: usize = 25;
41pub const MAX_READS: usize = 1000;
43pub const MAX_NAME: usize = 256;
45
46#[derive(Debug, Clone, PartialEq, Eq)]
48pub enum AuthzError {
49 Parse(String),
51 Schema(String),
54 Limit(String),
56 Store(String),
58}
59
60impl fmt::Display for AuthzError {
61 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
62 match self {
63 AuthzError::Parse(e) => write!(f, "parse error: {e}"),
64 AuthzError::Schema(e) => write!(f, "schema: {e}"),
65 AuthzError::Limit(e) => write!(f, "limit: {e}"),
66 AuthzError::Store(e) => write!(f, "store: {e}"),
67 }
68 }
69}
70
71impl std::error::Error for AuthzError {}
72
73fn name(text: &str, what: &str) -> Result<String, AuthzError> {
74 let ok = !text.is_empty()
75 && text.len() <= MAX_NAME
76 && text.bytes().all(|b| b.is_ascii_alphanumeric() || matches!(b, b'_' | b'-' | b'.'));
77 if ok {
78 Ok(text.to_string())
79 } else {
80 Err(AuthzError::Parse(format!("{what} {text:?}: letters, digits, '_', '-' and '.' only, 1–{MAX_NAME} characters")))
81 }
82}
83
84fn id(text: &str) -> Result<String, AuthzError> {
88 let ok = !text.is_empty() && text.len() <= MAX_NAME && !text.bytes().any(|b| b == b'#' || b == b' ' || b.is_ascii_control());
89 if ok {
90 Ok(text.to_string())
91 } else {
92 Err(AuthzError::Parse(format!("id {text:?}: 1–{MAX_NAME} characters, no '#', spaces or control characters")))
93 }
94}
95
96#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
98pub struct ObjectRef {
99 pub kind: String,
100 pub id: String,
101}
102
103impl ObjectRef {
104 pub fn parse(text: &str) -> Result<ObjectRef, AuthzError> {
105 let (kind, rest) = text.split_once(':').ok_or_else(|| AuthzError::Parse(format!("object {text:?}: expected type:id")))?;
106 Ok(ObjectRef { kind: name(kind, "type")?, id: id(rest)? })
107 }
108}
109
110impl fmt::Display for ObjectRef {
111 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112 write!(f, "{}:{}", self.kind, self.id)
113 }
114}
115
116#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
118pub struct Subject {
119 pub object: ObjectRef,
120 pub relation: Option<String>,
121}
122
123impl Subject {
124 pub fn parse(text: &str) -> Result<Subject, AuthzError> {
125 match text.split_once('#') {
126 Some((object, relation)) => Ok(Subject { object: ObjectRef::parse(object)?, relation: Some(name(relation, "relation")?) }),
127 None => Ok(Subject { object: ObjectRef::parse(text)?, relation: None }),
128 }
129 }
130}
131
132impl fmt::Display for Subject {
133 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134 match &self.relation {
135 Some(relation) => write!(f, "{}#{relation}", self.object),
136 None => write!(f, "{}", self.object),
137 }
138 }
139}
140
141#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
143pub struct Tuple {
144 pub object: ObjectRef,
145 pub relation: String,
146 pub subject: Subject,
147}
148
149impl Tuple {
150 pub fn parse(text: &str) -> Result<Tuple, AuthzError> {
151 let text = text.trim();
152 let malformed = || AuthzError::Parse(format!("tuple {text:?}: expected object#relation@subject"));
153 let (object, rest) = text.split_once('#').ok_or_else(malformed)?;
154 let (relation, subject) = rest.split_once('@').ok_or_else(malformed)?;
155 Ok(Tuple { object: ObjectRef::parse(object)?, relation: name(relation, "relation")?, subject: Subject::parse(subject)? })
156 }
157}
158
159impl fmt::Display for Tuple {
160 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
161 write!(f, "{}#{}@{}", self.object, self.relation, self.subject)
162 }
163}
164
165#[derive(Clone, Debug, PartialEq, Eq)]
167pub enum Term {
168 Direct(String),
170 DirectSet(String, String),
172 Computed(String),
174 TupleToUserset { tupleset: String, computed: String },
176}
177
178pub fn parse_expression(text: &str) -> Result<Vec<Term>, AuthzError> {
182 if text.len() > 4096 {
183 return Err(AuthzError::Parse("relation definition over 4096 characters".to_string()));
184 }
185 let mut terms = Vec::new();
186 for part in text.split('|') {
187 let part = part.trim();
188 let term = if let Some((tupleset, computed)) = part.split_once("->") {
189 Term::TupleToUserset { tupleset: name(tupleset.trim(), "relation")?, computed: name(computed.trim(), "relation")? }
190 } else if let Some((kind, relation)) = part.split_once('#') {
191 Term::DirectSet(name(kind.trim(), "type")?, name(relation.trim(), "relation")?)
192 } else {
193 Term::Direct(name(part, "type or relation")?)
194 };
195 terms.push(term);
196 }
197 if terms.is_empty() {
198 return Err(AuthzError::Parse("empty relation definition".to_string()));
199 }
200 Ok(terms)
201}
202
203#[derive(Clone, Debug, Default)]
205pub struct Schema {
206 types: HashMap<String, HashMap<String, Vec<Term>>>,
207 written: Vec<(String, String, String)>,
209}
210
211impl Schema {
212 pub fn new() -> Schema {
213 Schema::default()
214 }
215
216 pub fn relation(mut self, kind: &str, relation: &str, definition: &str) -> Result<Schema, AuthzError> {
220 let (kind, relation) = (name(kind, "type")?, name(relation, "relation")?);
221 let terms = parse_expression(definition)?;
222 self.types.entry(kind.clone()).or_default().insert(relation.clone(), terms);
223 self.written.push((kind, relation, definition.to_string()));
224 Ok(self)
225 }
226
227 pub fn object_type(mut self, kind: &str) -> Result<Schema, AuthzError> {
229 self.types.entry(name(kind, "type")?).or_default();
230 Ok(self)
231 }
232
233 pub fn types(&self) -> Vec<&str> {
235 let mut types: Vec<&str> = self.types.keys().map(String::as_str).collect();
236 types.sort_unstable();
237 types
238 }
239
240 pub fn relations(&self, kind: &str) -> Vec<&str> {
242 let mut relations: Vec<&str> = self.types.get(kind).map(|r| r.keys().map(String::as_str).collect()).unwrap_or_default();
243 relations.sort_unstable();
244 relations
245 }
246
247 pub fn has_relation(&self, kind: &str, relation: &str) -> bool {
248 self.types.get(kind).is_some_and(|r| r.contains_key(relation))
249 }
250
251 pub fn validate(&self) -> Result<Schema, AuthzError> {
256 let mut known: HashSet<String> = self.types.keys().cloned().collect();
257 let mut resolved = self.clone();
258 for (kind, relations) in &self.types {
259 for (relation, terms) in relations {
260 let mut out = Vec::with_capacity(terms.len());
261 for term in terms {
262 out.push(match term {
263 Term::Direct(word) if relations.contains_key(word) && !self.types.contains_key(word) => Term::Computed(word.clone()),
264 Term::Direct(word) => {
265 known.insert(word.clone());
266 Term::Direct(word.clone())
267 }
268 Term::DirectSet(set_kind, set_relation) => {
269 if !self.has_relation(set_kind, set_relation) {
270 return Err(AuthzError::Schema(format!("{kind}#{relation}: {set_kind}#{set_relation} isn't defined")));
271 }
272 term.clone()
273 }
274 Term::TupleToUserset { tupleset, .. } => {
275 let Some(set_terms) = relations.get(tupleset) else {
276 return Err(AuthzError::Schema(format!("{kind}#{relation}: {tupleset} isn't a relation of {kind}")));
277 };
278 if !set_terms.iter().all(|t| matches!(t, Term::Direct(_))) {
279 return Err(AuthzError::Schema(format!("{kind}#{relation}: {tupleset} must name objects directly (only types, no sets or relations)")));
280 }
281 term.clone()
282 }
283 Term::Computed(other) => {
284 if !relations.contains_key(other) {
285 return Err(AuthzError::Schema(format!("{kind}#{relation}: {other} isn't a relation of {kind}")));
286 }
287 term.clone()
288 }
289 });
290 }
291 resolved.types.get_mut(kind).expect("kind").insert(relation.clone(), out);
292 }
293 }
294 for (kind, relations) in &resolved.types {
296 for (relation, terms) in relations {
297 for term in terms {
298 if let Term::TupleToUserset { tupleset, computed } = term {
299 for target in relations[tupleset].iter().filter_map(|t| if let Term::Direct(k) = t { Some(k) } else { None }) {
300 if !resolved.has_relation(target, computed) {
301 return Err(AuthzError::Schema(format!("{kind}#{relation}: {tupleset}->{computed} needs {computed} on {target}")));
302 }
303 }
304 }
305 }
306 }
307 }
308 for kind in known {
309 resolved.types.entry(kind).or_default();
310 }
311 Ok(resolved)
312 }
313
314 fn terms(&self, kind: &str, relation: &str) -> Option<&[Term]> {
315 self.types.get(kind)?.get(relation).map(Vec::as_slice)
316 }
317
318 pub fn allows(&self, tuple: &Tuple) -> Result<(), AuthzError> {
321 let terms = self
322 .terms(&tuple.object.kind, &tuple.relation)
323 .ok_or_else(|| AuthzError::Schema(format!("{}#{} isn't defined", tuple.object.kind, tuple.relation)))?;
324 let fits = terms.iter().any(|term| match (term, &tuple.subject.relation) {
325 (Term::Direct(kind), None) => *kind == tuple.subject.object.kind,
326 (Term::DirectSet(kind, relation), Some(r)) => *kind == tuple.subject.object.kind && relation == r,
327 _ => false,
328 });
329 if fits {
330 Ok(())
331 } else {
332 Err(AuthzError::Schema(format!("{}#{} doesn't take {} as a subject", tuple.object.kind, tuple.relation, tuple.subject)))
333 }
334 }
335}
336
337#[derive(Clone, Debug, Default)]
339pub struct TupleFilter {
340 pub object: Option<ObjectRef>,
341 pub object_kind: Option<String>,
342 pub relation: Option<String>,
343 pub subject: Option<Subject>,
344}
345
346impl TupleFilter {
347 pub fn matches(&self, tuple: &Tuple) -> bool {
348 self.object.as_ref().is_none_or(|o| *o == tuple.object)
349 && self.object_kind.as_ref().is_none_or(|k| *k == tuple.object.kind)
350 && self.relation.as_ref().is_none_or(|r| *r == tuple.relation)
351 && self.subject.as_ref().is_none_or(|s| *s == tuple.subject)
352 }
353}
354
355pub trait TupleStore: Send + Sync {
357 fn write(&self, tuple: &Tuple) -> Result<bool, AuthzError>;
359 fn delete(&self, tuple: &Tuple) -> Result<bool, AuthzError>;
361 fn read(&self, object: &ObjectRef, relation: &str) -> Result<Vec<Subject>, AuthzError>;
363 fn list(&self, filter: &TupleFilter, limit: usize) -> Result<Vec<Tuple>, AuthzError>;
365}
366
367#[derive(Default)]
370pub struct MemoryStore {
371 tuples: RwLock<HashMap<(ObjectRef, String), BTreeSet<Subject>>>,
372}
373
374impl MemoryStore {
375 pub fn new() -> MemoryStore {
376 MemoryStore::default()
377 }
378}
379
380impl TupleStore for MemoryStore {
381 fn write(&self, tuple: &Tuple) -> Result<bool, AuthzError> {
382 let mut tuples = self.tuples.write().unwrap_or_else(|e| e.into_inner());
383 Ok(tuples.entry((tuple.object.clone(), tuple.relation.clone())).or_default().insert(tuple.subject.clone()))
384 }
385
386 fn delete(&self, tuple: &Tuple) -> Result<bool, AuthzError> {
387 let mut tuples = self.tuples.write().unwrap_or_else(|e| e.into_inner());
388 let key = (tuple.object.clone(), tuple.relation.clone());
389 let removed = tuples.get_mut(&key).is_some_and(|subjects| subjects.remove(&tuple.subject));
390 if tuples.get(&key).is_some_and(BTreeSet::is_empty) {
391 tuples.remove(&key);
392 }
393 Ok(removed)
394 }
395
396 fn read(&self, object: &ObjectRef, relation: &str) -> Result<Vec<Subject>, AuthzError> {
397 let tuples = self.tuples.read().unwrap_or_else(|e| e.into_inner());
398 Ok(tuples.get(&(object.clone(), relation.to_string())).map(|s| s.iter().cloned().collect()).unwrap_or_default())
399 }
400
401 fn list(&self, filter: &TupleFilter, limit: usize) -> Result<Vec<Tuple>, AuthzError> {
402 let tuples = self.tuples.read().unwrap_or_else(|e| e.into_inner());
403 let mut out: Vec<Tuple> = tuples
404 .iter()
405 .flat_map(|((object, relation), subjects)| {
406 subjects.iter().map(move |subject| Tuple { object: object.clone(), relation: relation.clone(), subject: subject.clone() })
407 })
408 .filter(|t| filter.matches(t))
409 .collect();
410 out.sort();
411 out.truncate(limit);
412 Ok(out)
413 }
414}
415
416#[derive(Clone)]
419pub struct Authorizer {
420 schema: Arc<Schema>,
421 store: Arc<dyn TupleStore>,
422}
423
424impl fmt::Debug for Authorizer {
425 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
426 f.debug_struct("Authorizer").field("types", &self.schema.types()).finish_non_exhaustive()
427 }
428}
429
430impl Authorizer {
431 pub fn new(schema: Schema, store: impl TupleStore + 'static) -> Result<Authorizer, AuthzError> {
433 Authorizer::with_store(schema, Arc::new(store))
434 }
435
436 pub fn with_store(schema: Schema, store: Arc<dyn TupleStore>) -> Result<Authorizer, AuthzError> {
437 Ok(Authorizer { schema: Arc::new(schema.validate()?), store })
438 }
439
440 pub fn schema(&self) -> &Schema {
441 &self.schema
442 }
443
444 pub fn store(&self) -> &Arc<dyn TupleStore> {
445 &self.store
446 }
447
448 pub fn write(&self, tuple: &Tuple) -> Result<bool, AuthzError> {
450 self.schema.allows(tuple)?;
451 self.store.write(tuple)
452 }
453
454 pub fn write_str(&self, tuple: &str) -> Result<bool, AuthzError> {
456 self.write(&Tuple::parse(tuple)?)
457 }
458
459 pub fn delete(&self, tuple: &Tuple) -> Result<bool, AuthzError> {
460 self.store.delete(tuple)
461 }
462
463 pub fn check(&self, subject: &str, relation: &str, object: &str) -> Result<bool, AuthzError> {
466 Ok(self.explain(subject, relation, object)?.is_some())
467 }
468
469 pub fn explain(&self, subject: &str, relation: &str, object: &str) -> Result<Option<Vec<String>>, AuthzError> {
472 self.explain_subject(&Subject::parse(subject)?, relation, &ObjectRef::parse(object)?)
473 }
474
475 pub fn check_subject(&self, subject: &Subject, relation: &str, object: &ObjectRef) -> Result<bool, AuthzError> {
478 Ok(self.explain_subject(subject, relation, object)?.is_some())
479 }
480
481 pub fn explain_subject(&self, subject: &Subject, relation: &str, object: &ObjectRef) -> Result<Option<Vec<String>>, AuthzError> {
483 if !self.schema.has_relation(&object.kind, relation) {
484 return Err(AuthzError::Schema(format!("{}#{relation} isn't defined", object.kind)));
485 }
486 Walk::new(self).run(subject, object.clone(), relation.to_string())
487 }
488}
489
490struct Walk<'a> {
493 authz: &'a Authorizer,
494 reads: usize,
495 nodes: Vec<(ObjectRef, String, Option<usize>, usize)>,
497}
498
499impl<'a> Walk<'a> {
500 fn new(authz: &'a Authorizer) -> Walk<'a> {
501 Walk { authz, reads: 0, nodes: Vec::new() }
502 }
503
504 fn read(&mut self, object: &ObjectRef, relation: &str) -> Result<Vec<Subject>, AuthzError> {
505 self.reads += 1;
506 if self.reads > MAX_READS {
507 return Err(AuthzError::Limit(format!("more than {MAX_READS} tuple reads")));
508 }
509 self.authz.store.read(object, relation)
510 }
511
512 fn path(&self, mut at: usize, last: String) -> Vec<String> {
513 let mut steps = vec![last];
514 loop {
515 let (object, relation, parent, _) = &self.nodes[at];
516 steps.push(format!("{object}#{relation}"));
517 match parent {
518 Some(p) => at = *p,
519 None => break,
520 }
521 }
522 steps.reverse();
523 steps
524 }
525
526 fn run(mut self, subject: &Subject, object: ObjectRef, relation: String) -> Result<Option<Vec<String>>, AuthzError> {
527 let mut visited: HashSet<(ObjectRef, String)> = HashSet::new();
528 self.nodes.push((object, relation, None, 0));
529 let mut stack = vec![0usize];
530 while let Some(at) = stack.pop() {
531 let (object, relation, _, depth) = self.nodes[at].clone();
532 if !visited.insert((object.clone(), relation.clone())) {
533 continue;
534 }
535 if subject.relation.as_deref() == Some(relation.as_str()) && subject.object == object {
537 return Ok(Some(self.path(at, format!("{subject}"))));
538 }
539 if depth >= MAX_DEPTH {
540 return Err(AuthzError::Limit(format!("deeper than {MAX_DEPTH} relations")));
541 }
542 let Some(terms) = self.authz.schema.terms(&object.kind, &relation) else { continue };
543 let terms = terms.to_vec();
544 let mut direct_read = false;
545 for term in &terms {
546 match term {
547 Term::Direct(_) | Term::DirectSet(..) => {
548 if direct_read {
549 continue;
550 }
551 direct_read = true;
552 for found in self.read(&object, &relation)? {
553 if found == *subject {
554 return Ok(Some(self.path(at, format!("{object}#{relation}@{found}"))));
555 }
556 if let Some(set_relation) = &found.relation {
557 self.nodes.push((found.object.clone(), set_relation.clone(), Some(at), depth + 1));
558 stack.push(self.nodes.len() - 1);
559 }
560 }
561 }
562 Term::Computed(other) => {
563 self.nodes.push((object.clone(), other.clone(), Some(at), depth + 1));
564 stack.push(self.nodes.len() - 1);
565 }
566 Term::TupleToUserset { tupleset, computed } => {
567 for found in self.read(&object, tupleset)? {
568 if found.relation.is_none() {
569 self.nodes.push((found.object.clone(), computed.clone(), Some(at), depth + 1));
570 stack.push(self.nodes.len() - 1);
571 }
572 }
573 }
574 }
575 }
576 }
577 Ok(None)
578 }
579}
580
581#[cfg(test)]
582mod tests;