RBAC Role Inheritance (Rust)
Topics: graphs, DFS, cycle detection, authorization
Problem
In a role-based access control system, a role grants some permissions directly and inherits
every permission of the roles it extends. Given the role graph, compute the effective permission
set for a role — or report an inheritance cycle if one exists.
pub struct Role { pub inherits: Vec<String>, pub grants: Vec<String> }
pub struct CycleError { pub roles: Vec<String> }
pub fn permissions(roles: &BTreeMap<String, Role>, start: &str) -> Result<Vec<String>, CycleError>;
roles maps a role name to what it grants directly and the parent roles it inherits.- The result is
start's own grants plus everything inherited transitively, deduplicated
(a permission reached via two paths appears once) and returned in sorted order.
- A parent that isn't itself a key is an empty leaf role (grants nothing); so is an unknown
start, which yields an empty set.
- On a cycle reachable from
start (including a role that inherits itself) return
Err(CycleError) whose roles are the roles on that cycle, sorted.
viewer:{read}, editor:{>viewer, write}, admin:{>editor, delete}; start=admin
→ ["delete","read","write"]
owner:{>billing,>support, manage}, billing:{>base, pay}, support:{>base, refund}, base:{login}
→ ["login","manage","pay","refund"] (login once)
a:{>b}, b:{>a}; start=a → Err(CycleError{roles:["a","b"]})
A depth-first walk that unions grants on the way down solves this; three-color marking
(white/gray/black) turns cycle detection into spotting a back edge to a node still on the recursion
stack. A BTreeSet collects permissions deduplicated and already sorted.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.