use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::fmt;
use serde::{Deserialize, Serialize};
use crate::audit::RoleName;
use crate::capabilities::{is_valid_path_segment, MethodPath};
use crate::credential::Scope;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ScopeError {
Empty,
InvalidFormat(String),
}
impl fmt::Display for ScopeError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
ScopeError::Empty => write!(f, "scope must not be empty"),
ScopeError::InvalidFormat(s) => write!(
f,
"invalid scope {s:?}: expected bare `*`, dot-separated lowercase \
identifiers ([a-z][a-z0-9_]*), or such a path with a trailing `.*` \
segment wildcard"
),
}
}
}
impl std::error::Error for ScopeError {}
fn is_valid_scope(s: &str) -> bool {
if s == "*" {
return true;
}
let body = s.strip_suffix(".*").unwrap_or(s);
if body.is_empty() {
return false;
}
body.split('.').all(is_valid_path_segment)
}
impl Scope {
pub fn try_new(s: impl Into<String>) -> Result<Self, ScopeError> {
let s = s.into();
if s.is_empty() {
return Err(ScopeError::Empty);
}
if !is_valid_scope(&s) {
return Err(ScopeError::InvalidFormat(s));
}
Ok(Self::new(s))
}
pub fn is_wildcard(&self) -> bool {
self.as_str() == "*" || self.as_str().ends_with(".*")
}
pub fn matches(&self, required: &Scope) -> bool {
let held = self.as_str();
if held == "*" {
return true;
}
if self == required {
return true;
}
if let Some(prefix) = held.strip_suffix(".*") {
let req = required.as_str();
return req.len() > prefix.len()
&& req.starts_with(prefix)
&& req.as_bytes()[prefix.len()] == b'.';
}
false
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RoleNameError {
Empty,
InvalidFormat(String),
}
impl fmt::Display for RoleNameError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
RoleNameError::Empty => write!(f, "role name must not be empty"),
RoleNameError::InvalidFormat(s) => {
write!(f, "invalid role name {s:?}: expected [a-z][a-z0-9_]*")
}
}
}
}
impl std::error::Error for RoleNameError {}
impl RoleName {
pub fn try_new(s: impl Into<String>) -> Result<Self, RoleNameError> {
let s = s.into();
if s.is_empty() {
return Err(RoleNameError::Empty);
}
if !is_valid_path_segment(&s) {
return Err(RoleNameError::InvalidFormat(s));
}
Ok(Self::new(s))
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Role {
name: RoleName,
scopes: Vec<Scope>,
inherits: Vec<RoleName>,
description: String,
}
impl Role {
pub fn new(
name: RoleName,
scopes: Vec<Scope>,
inherits: Vec<RoleName>,
description: impl Into<String>,
) -> Self {
Self {
name,
scopes,
inherits,
description: description.into(),
}
}
pub fn name(&self) -> &RoleName {
&self.name
}
pub fn scopes(&self) -> &[Scope] {
&self.scopes
}
pub fn inherits(&self) -> &[RoleName] {
&self.inherits
}
pub fn description(&self) -> &str {
&self.description
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ScopeRegistryError {
InvalidRoleName(RoleNameError),
InvalidScope(ScopeError),
DuplicateRole(RoleName),
UnknownInheritedRole {
role: RoleName,
inherits: RoleName,
},
InheritanceCycle {
path: Vec<RoleName>,
},
InheritsBeforeRole,
}
impl fmt::Display for ScopeRegistryError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
ScopeRegistryError::InvalidRoleName(e) => write!(f, "{e}"),
ScopeRegistryError::InvalidScope(e) => write!(f, "{e}"),
ScopeRegistryError::DuplicateRole(r) => {
write!(f, "role {r} declared more than once")
}
ScopeRegistryError::UnknownInheritedRole { role, inherits } => write!(
f,
"role {role} inherits undeclared role {inherits}"
),
ScopeRegistryError::InheritanceCycle { path } => {
let rendered: Vec<&str> = path.iter().map(|r| r.as_str()).collect();
write!(f, "role inheritance cycle: {}", rendered.join(" -> "))
}
ScopeRegistryError::InheritsBeforeRole => write!(
f,
"inherits()/description() called before any role() — nothing to modify"
),
}
}
}
impl std::error::Error for ScopeRegistryError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
ScopeRegistryError::InvalidRoleName(e) => Some(e),
ScopeRegistryError::InvalidScope(e) => Some(e),
_ => None,
}
}
}
impl From<RoleNameError> for ScopeRegistryError {
fn from(e: RoleNameError) -> Self {
ScopeRegistryError::InvalidRoleName(e)
}
}
impl From<ScopeError> for ScopeRegistryError {
fn from(e: ScopeError) -> Self {
ScopeRegistryError::InvalidScope(e)
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ScopeRegistry {
roles: BTreeMap<RoleName, Role>,
public_methods: BTreeSet<MethodPath>,
method_overlays: BTreeMap<MethodPath, Vec<Scope>>,
}
impl ScopeRegistry {
pub fn builder() -> ScopeRegistryBuilder {
ScopeRegistryBuilder::default()
}
pub fn role(&self, name: &RoleName) -> Option<&Role> {
self.roles.get(name)
}
pub fn is_public(&self, method: &MethodPath) -> bool {
self.public_methods.contains(method)
}
pub fn required_scopes_for(&self, method: &MethodPath) -> Vec<Scope> {
if let Some(explicit) = self.method_overlays.get(method) {
return explicit.clone();
}
vec![Scope::new(method.as_str())]
}
pub fn expand_role(&self, role: &RoleName) -> BTreeSet<Scope> {
let mut out = BTreeSet::new();
let mut visited: HashSet<&RoleName> = HashSet::new();
let mut frontier: Vec<&RoleName> = vec![role];
while let Some(name) = frontier.pop() {
if !visited.insert(name) {
continue;
}
if let Some(def) = self.roles.get(name) {
out.extend(def.scopes.iter().cloned());
frontier.extend(def.inherits.iter());
}
}
out
}
pub fn effective_scopes(&self, roles: &[RoleName]) -> BTreeSet<Scope> {
roles.iter().flat_map(|r| self.expand_role(r)).collect()
}
}
#[derive(Debug, Clone)]
struct RoleDraft {
name: String,
scopes: Vec<String>,
inherits: Vec<String>,
description: String,
}
#[derive(Debug, Clone, Default)]
pub struct ScopeRegistryBuilder {
roles: Vec<RoleDraft>,
public_methods: BTreeSet<MethodPath>,
method_overlays: BTreeMap<MethodPath, Vec<Scope>>,
modifier_before_role: bool,
}
impl ScopeRegistryBuilder {
pub fn role(mut self, name: impl Into<String>, scopes: &[&str]) -> Self {
self.roles.push(RoleDraft {
name: name.into(),
scopes: scopes.iter().map(|s| (*s).to_string()).collect(),
inherits: Vec::new(),
description: String::new(),
});
self
}
pub fn inherits(mut self, parents: &[&str]) -> Self {
match self.roles.last_mut() {
Some(draft) => draft
.inherits
.extend(parents.iter().map(|s| (*s).to_string())),
None => self.modifier_before_role = true,
}
self
}
pub fn description(mut self, description: impl Into<String>) -> Self {
match self.roles.last_mut() {
Some(draft) => draft.description = description.into(),
None => self.modifier_before_role = true,
}
self
}
pub fn public_method(mut self, method: MethodPath) -> Self {
self.public_methods.insert(method);
self
}
pub fn method_scopes(mut self, method: MethodPath, scopes: &[Scope]) -> Self {
self.method_overlays.insert(method, scopes.to_vec());
self
}
pub fn build(self) -> Result<ScopeRegistry, ScopeRegistryError> {
if self.modifier_before_role {
return Err(ScopeRegistryError::InheritsBeforeRole);
}
let mut roles: BTreeMap<RoleName, Role> = BTreeMap::new();
for draft in self.roles {
let name = RoleName::try_new(draft.name)?;
let scopes = draft
.scopes
.into_iter()
.map(Scope::try_new)
.collect::<Result<Vec<_>, _>>()?;
let inherits = draft
.inherits
.into_iter()
.map(RoleName::try_new)
.collect::<Result<Vec<_>, _>>()?;
if roles.contains_key(&name) {
return Err(ScopeRegistryError::DuplicateRole(name));
}
roles.insert(
name.clone(),
Role::new(name, scopes, inherits, draft.description),
);
}
for role in roles.values() {
for parent in role.inherits() {
if !roles.contains_key(parent) {
return Err(ScopeRegistryError::UnknownInheritedRole {
role: role.name().clone(),
inherits: parent.clone(),
});
}
}
}
if let Some(path) = detect_inheritance_cycle(&roles) {
return Err(ScopeRegistryError::InheritanceCycle { path });
}
Ok(ScopeRegistry {
roles,
public_methods: self.public_methods,
method_overlays: self.method_overlays,
})
}
}
fn detect_inheritance_cycle(roles: &BTreeMap<RoleName, Role>) -> Option<Vec<RoleName>> {
#[derive(Clone, Copy, PartialEq)]
enum Color {
Gray,
Black,
}
let mut color: HashMap<&RoleName, Color> = HashMap::new();
for start in roles.keys() {
if color.contains_key(start) {
continue;
}
let mut stack: Vec<(&RoleName, usize)> = vec![(start, 0)];
color.insert(start, Color::Gray);
while let Some(&(node, edge_idx)) = stack.last() {
let inherits = roles
.get(node)
.expect("referential integrity checked before cycle detection")
.inherits();
if edge_idx < inherits.len() {
stack.last_mut().expect("stack non-empty inside loop").1 += 1;
let child = &inherits[edge_idx];
match color.get(child) {
Some(Color::Gray) => {
let pos = stack
.iter()
.position(|(n, _)| *n == child)
.expect("gray node is on the current path");
let mut path: Vec<RoleName> =
stack[pos..].iter().map(|(n, _)| (*n).clone()).collect();
path.push(child.clone());
return Some(path);
}
Some(Color::Black) => {}
None => {
color.insert(child, Color::Gray);
stack.push((child, 0));
}
}
} else {
color.insert(node, Color::Black);
stack.pop();
}
}
}
None
}
#[cfg(test)]
mod tests {
use super::*;
fn scope(s: &str) -> Scope {
Scope::try_new(s).unwrap()
}
fn role_name(s: &str) -> RoleName {
RoleName::try_new(s).unwrap()
}
fn method(s: &str) -> MethodPath {
MethodPath::try_new(s).unwrap()
}
#[test]
fn scope_grammar_accepts_canonical_forms() {
for ok in [
"*",
"forms",
"forms.list",
"forms.list.detail",
"forms.*",
"forms.list.*",
"cone.send_message",
"a1.b_2",
"a_x.y9.*",
"x",
] {
assert!(
Scope::try_new(ok).is_ok(),
"grammar must accept {ok:?}"
);
}
}
#[test]
fn scope_grammar_rejects_violations() {
assert_eq!(Scope::try_new(""), Err(ScopeError::Empty));
for bad in [
".",
".*",
"*.*",
"**",
"*a",
"a*",
"a.b*",
"a.*x",
"a.*.b",
"*.thing",
"a.",
".a",
"a..b",
"a.b.",
"A.b",
"a.B",
"Forms.List",
"9a.b",
"_a.b",
"a-b.c",
"a b",
"a.b ",
" a.b",
"café.list",
] {
assert_eq!(
Scope::try_new(bad),
Err(ScopeError::InvalidFormat(bad.to_string())),
"grammar must reject {bad:?}"
);
}
}
#[test]
fn scope_is_wildcard() {
assert!(scope("*").is_wildcard());
assert!(scope("cone.*").is_wildcard());
assert!(scope("cone.threads.*").is_wildcard());
assert!(!scope("cone.send_message").is_wildcard());
assert!(!scope("forms").is_wildcard());
}
#[test]
fn scope_matches_canonical_six() {
assert!(scope("*").matches(&scope("cone.send_message")));
assert!(scope("cone.*").matches(&scope("cone.send_message")));
assert!(scope("cone.*").matches(&scope("cone.threads.list")));
assert!(!scope("cone.*").matches(&scope("forms.list")));
assert!(scope("cone.send_message").matches(&scope("cone.send_message")));
assert!(!scope("cone.send_message").matches(&scope("cone.read_thread")));
}
#[test]
fn role_name_grammar_accepts() {
for ok in ["admin", "a", "tenant_owner", "r2d2", "x_9"] {
assert!(
RoleName::try_new(ok).is_ok(),
"grammar must accept {ok:?}"
);
}
}
#[test]
fn role_name_grammar_rejects() {
assert_eq!(RoleName::try_new(""), Err(RoleNameError::Empty));
for bad in ["Admin", "9x", "_x", "a.b", "a-b", "a b", "*", "ADMIN", "café"] {
assert_eq!(
RoleName::try_new(bad),
Err(RoleNameError::InvalidFormat(bad.to_string())),
"grammar must reject {bad:?}"
);
}
}
#[test]
fn role_construction_carries_fields() {
let r = Role::new(
role_name("editor"),
vec![scope("forms.write")],
vec![role_name("viewer")],
"can edit forms",
);
assert_eq!(r.name(), &role_name("editor"));
assert_eq!(r.scopes(), &[scope("forms.write")]);
assert_eq!(r.inherits(), &[role_name("viewer")]);
assert_eq!(r.description(), "can edit forms");
}
fn example_registry() -> ScopeRegistry {
ScopeRegistry::builder()
.role("viewer", &["forms.list"])
.description("read-only access")
.role("editor", &["forms.write"])
.inherits(&["viewer"])
.role("tenant_owner", &[])
.inherits(&["editor"])
.role("admin", &["*"])
.public_method(method("auth.login"))
.method_scopes(method("forms.export"), &[scope("forms.list")])
.build()
.expect("the §4 example taxonomy must build")
}
#[test]
fn builder_example_taxonomy_expands_as_pinned() {
let reg = example_registry();
assert_eq!(
reg.expand_role(&role_name("viewer")),
BTreeSet::from([scope("forms.list")])
);
assert_eq!(
reg.expand_role(&role_name("editor")),
BTreeSet::from([scope("forms.write"), scope("forms.list")])
);
assert_eq!(
reg.expand_role(&role_name("tenant_owner")),
BTreeSet::from([scope("forms.write"), scope("forms.list")])
);
assert_eq!(
reg.expand_role(&role_name("admin")),
BTreeSet::from([scope("*")])
);
}
#[test]
fn builder_role_lookup_carries_description() {
let reg = example_registry();
let viewer = reg.role(&role_name("viewer")).expect("viewer declared");
assert_eq!(viewer.description(), "read-only access");
}
#[test]
fn is_public_true_only_for_declared_methods() {
let reg = example_registry();
assert!(reg.is_public(&method("auth.login")));
assert!(!reg.is_public(&method("forms.export")));
assert!(!reg.is_public(&method("cone.send_message")));
}
#[test]
fn required_scopes_explicit_overlay_wins() {
let reg = example_registry();
assert_eq!(
reg.required_scopes_for(&method("forms.export")),
vec![scope("forms.list")]
);
}
#[test]
fn required_scopes_implicit_is_the_method_path() {
let reg = example_registry();
assert_eq!(
reg.required_scopes_for(&method("cone.send_message")),
vec![Scope::new("cone.send_message")]
);
}
#[test]
fn build_rejects_two_role_cycle_with_path() {
let err = ScopeRegistry::builder()
.role("a", &["x.one"])
.inherits(&["b"])
.role("b", &["y.one"])
.inherits(&["a"])
.build()
.expect_err("cycle must be rejected at build()");
match err {
ScopeRegistryError::InheritanceCycle { path } => {
assert_eq!(path.first(), path.last());
assert!(path.contains(&role_name("a")));
assert!(path.contains(&role_name("b")));
assert_eq!(path.len(), 3, "a->b->a (closed) has length 3");
}
other => panic!("expected InheritanceCycle, got {other:?}"),
}
}
#[test]
fn build_rejects_self_cycle() {
let err = ScopeRegistry::builder()
.role("a", &["x.one"])
.inherits(&["a"])
.build()
.expect_err("self-cycle must be rejected at build()");
assert!(matches!(
err,
ScopeRegistryError::InheritanceCycle { ref path } if path == &vec![role_name("a"), role_name("a")]
));
}
#[test]
fn build_rejects_deep_cycle_without_overflow() {
let n = 10_000;
let names: Vec<String> = (0..n).map(|i| format!("r{i}")).collect();
let mut b = ScopeRegistry::builder();
for i in 0..n {
let parent = names[(i + 1) % n].clone();
b = b.role(names[i].as_str(), &[]).inherits(&[parent.as_str()]);
}
let err = b.build().expect_err("the loop must be rejected");
assert!(matches!(err, ScopeRegistryError::InheritanceCycle { .. }));
}
#[test]
fn build_accepts_diamond_inheritance() {
let reg = ScopeRegistry::builder()
.role("d", &["base.read"])
.role("b", &["b.write"])
.inherits(&["d"])
.role("c", &["c.write"])
.inherits(&["d"])
.role("a", &[])
.inherits(&["b", "c"])
.build()
.expect("diamond is acyclic");
assert_eq!(
reg.expand_role(&role_name("a")),
BTreeSet::from([scope("base.read"), scope("b.write"), scope("c.write")])
);
}
#[test]
fn build_rejects_unknown_inherited_role() {
let err = ScopeRegistry::builder()
.role("a", &["x.one"])
.inherits(&["ghost"])
.build()
.expect_err("dangling inherits must be rejected");
assert_eq!(
err,
ScopeRegistryError::UnknownInheritedRole {
role: role_name("a"),
inherits: role_name("ghost"),
}
);
}
#[test]
fn build_rejects_duplicate_role() {
let err = ScopeRegistry::builder()
.role("a", &["x.one"])
.role("a", &["y.one"])
.build()
.expect_err("redeclaration must be rejected");
assert_eq!(err, ScopeRegistryError::DuplicateRole(role_name("a")));
}
#[test]
fn build_rejects_invalid_role_name() {
let err = ScopeRegistry::builder()
.role("Admin", &["x.one"])
.build()
.expect_err("bad role name must be rejected");
assert!(matches!(err, ScopeRegistryError::InvalidRoleName(_)));
}
#[test]
fn build_rejects_invalid_scope() {
let err = ScopeRegistry::builder()
.role("a", &["Bad.Scope"])
.build()
.expect_err("bad scope must be rejected");
assert!(matches!(err, ScopeRegistryError::InvalidScope(_)));
}
#[test]
fn build_rejects_inherits_before_role() {
let err = ScopeRegistry::builder()
.inherits(&["a"])
.role("a", &["x.one"])
.build()
.expect_err("inherits() before role() must be rejected");
assert_eq!(err, ScopeRegistryError::InheritsBeforeRole);
}
#[test]
fn default_registry_is_empty() {
let reg = ScopeRegistry::default();
assert!(!reg.is_public(&method("auth.login")));
assert!(reg.effective_scopes(&[role_name("admin")]).is_empty());
assert_eq!(
reg.required_scopes_for(&method("cone.send_message")),
vec![Scope::new("cone.send_message")]
);
assert_eq!(reg, ScopeRegistry::builder().build().unwrap());
}
#[test]
fn expand_role_terminates_on_injected_cycle() {
let mut roles = BTreeMap::new();
roles.insert(
role_name("a"),
Role::new(role_name("a"), vec![scope("x.one")], vec![role_name("b")], ""),
);
roles.insert(
role_name("b"),
Role::new(role_name("b"), vec![scope("y.one")], vec![role_name("a")], ""),
);
let reg = ScopeRegistry {
roles,
public_methods: BTreeSet::new(),
method_overlays: BTreeMap::new(),
};
assert_eq!(
reg.expand_role(&role_name("a")),
BTreeSet::from([scope("x.one"), scope("y.one")])
);
}
}