# UNDF: UNDF-2026-000000054
# UNDF: (pending)
# sea-orm-0001: enumerate_role / list_role_hierarchy_edges — O(2^D) diamond BFS

## CWE-407 — Algorithmic Complexity: Quadratic/Exponential Traversal of Role Hierarchy

| Field | Value |
|-------|-------|
| ID | sea-orm-0001 |
| Severity | HIGH |
| Ecosystem | Rust |
| Package | sea-orm (rbac feature) |
| File | `src/rbac/engine/role_hierarchy_impl.rs` |
| Lines | 9–65 |
| Complexity | O(2^D) where D is diamond depth |
| Hot path | `user_can()` → `get_user_role_ids()` → `enumerate_role()` — called on every authorization check |

## Defect

Both `enumerate_role` and `list_role_hierarchy_edges` implement a BFS over the role
hierarchy using a `seen` HashSet to prevent re-visiting nodes. However, the guard
has a critical omission: child roles are checked against `seen` before enqueueing,
but **never inserted into `seen` at enqueue time**. Only the root node is inserted
at startup.

```rust
// BROKEN: seen is only populated with the root role
queue.push_back(role);
seen.insert(role);  // only root

while let Some(role) = queue.pop_front() {
    roles.push(role);
    if let Some(children) = role_hierarchy.get(&role) {
        for child in children {
            if !seen.contains(child) {     // checks seen...
                queue.push_back(*child);   // ...but never inserts child into seen!
            }
        }
    }
}
```

Because `seen.insert(child)` is absent, when two parents both point to the same
child role (a diamond), that child passes the `!seen.contains(child)` test from
both parents and is enqueued twice. Every role below the merge point is then
processed once per path that reaches it — O(2^D) total work for D diamond levels.

**Diamond trace** for A → [B, C], B → [D], C → [D]:

| Step | Queue | seen | roles |
|------|-------|------|-------|
| init | [A] | {A} | [] |
| pop A | push B (ok), push C (ok) → [B, C] | {A} | [A] |
| pop B | push D (D ∉ seen, enqueue, no insert) → [C, D] | {A} | [A,B] |
| pop C | push D again (D ∉ seen!) → [D, D] | {A} | [A,B,C] |
| pop D | → [D] | {A} | [A,B,C,D] |
| pop D | → [] | {A} | [A,B,C,D,**D**] |

D is visited twice. With depth D=10 (realistic RBAC hierarchy), a single
`user_can()` call triggers 2^10 = 1,024 role visits instead of R.

The same bug is present in both `enumerate_role` (returns `Vec<RoleId>`) and
`list_role_hierarchy_edges` (returns edges). Both files are identical between
`sea-orm` and `sea-orm-sync`:

- `src/rbac/engine/role_hierarchy_impl.rs`
- `sea-orm-sync/src/rbac/engine/role_hierarchy_impl.rs`

## Fix

Insert each child into `seen` **at enqueue time**, not at dequeue time:

```rust
pub fn enumerate_role(role: RoleId, role_hierarchy: &RoleHierarchyMap) -> Vec<RoleId> {
    let mut roles = Vec::new();
    let mut queue = VecDeque::new();
    let mut seen = HashSet::new();

    queue.push_back(role);
    seen.insert(role);

    while let Some(role) = queue.pop_front() {
        roles.push(role);
        if let Some(children) = role_hierarchy.get(&role) {
            for child in children {
                if seen.insert(*child) {     // insert returns true if newly added
                    queue.push_back(*child); // only enqueue if not already seen
                }
            }
        }
    }

    roles
}
```

Same fix applies identically to `list_role_hierarchy_edges` (the `seen.insert(*child)`
guard around `queue.push_back`; the `edges.push(...)` call outside the guard is
intentional and should remain unconditional to capture all hierarchy edges).

```rust
pub fn list_role_hierarchy_edges(
    role: RoleId,
    role_hierarchy: &RoleHierarchyMap,
) -> Vec<RoleHierarchy> {
    let mut edges = Vec::new();
    let mut roles = Vec::new();
    let mut queue = VecDeque::new();
    let mut seen = HashSet::new();

    queue.push_back(role);
    seen.insert(role);

    while let Some(role) = queue.pop_front() {
        roles.push(role);
        if let Some(children) = role_hierarchy.get(&role) {
            for child in children {
                if seen.insert(*child) {      // fix: insert at enqueue
                    queue.push_back(*child);
                }
                edges.push(RoleHierarchy {    // edge record stays unconditional
                    super_role_id: role,
                    role_id: *child,
                });
            }
        }
    }

    edges
}
```

## Speedup

| Diamond depth D | Roles visited (before) | Roles visited (after) | Speedup |
|-----------------|------------------------|----------------------|---------|
| 5 | 32 (2^5) | 6 | 5× |
| 10 | 1,024 (2^10) | 11 | 93× |
| 15 | 32,768 (2^15) | 16 | 2,048× |
| 20 | 1,048,576 (2^20) | 21 | ~50,000× |

For a flat chain (no diamonds) the fix is neutral — same O(R) traversal.
For real-world RBAC hierarchies with role sharing (e.g. `viewer` role inherited
by many specialized roles), the speedup is O(2^sharing_depth) vs O(R).

The fix also eliminates duplicate entries in the returned `Vec<RoleId>`, which
could cause double-counting of role grants in `get_roles_and_ranks()`.
