RBAC Role Inheritance (Go)
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.
type Role struct { Inherits []string; Grants []string }
func Permissions(roles map[string]Role, start string) ([]string, error)
type CycleError struct { Roles []string }
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.
- If inheritance reachable from
start contains a cycle (including a role that inherits itself),
return a *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 → *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.
Run
go test -v ./challenges/rbac-role-inheritance/go/
Sign in to submit your solution.