# UNDF: UNDF-2026-000000344
# actix-0001 — CWE-407: introspection `update_unique` O(R×G) Vec linear dedup

**Project:** actix-web
**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Excessive Iteration)
**File:** `actix-web/src/introspection.rs`
**Lines:** 984–989 (defect); also 935–944 (`merge_guard_reports`)
**Feature gate:** `experimental-introspection`

---

## Defective Code

```rust
// actix-web/src/introspection.rs:984-989
fn update_unique<T: Clone + PartialEq>(existing: &mut Vec<T>, new_items: &[T]) {
    for item in new_items {          // outer: O(N) over new_items
        if !existing.contains(item) {  // inner: O(E) linear scan each time
            existing.push(item.clone());
        }
    }
}
```

Called at registration time (lines 389–392, 451–454) for every route sharing a path prefix:

```rust
update_unique(&mut d.methods, &info.methods);
update_unique(&mut d.guards, &info.guards);    // guards Vec grows unbounded
merge_guard_reports(&mut d.guard_details, &info.guard_details);
update_unique(&mut d.patterns, &info.patterns); // patterns Vec grows unbounded
```

`merge_guard_reports` (lines 935–944) has the same shape — O(I×E) `iter_mut().find()` over a `Vec<GuardReport>`:

```rust
fn merge_guard_reports(existing: &mut Vec<GuardReport>, incoming: &[GuardReport]) {
    for report in incoming {
        if let Some(existing_report) = existing.iter_mut().find(|r| r.name == report.name) {
            // …
        }
    }
}
```

---

## Complexity

| Dimension | Defective | Fixed |
|-----------|-----------|-------|
| `update_unique` over G guards across R registrations | O(R × G) | O(R + G) |
| `merge_guard_reports` over I incoming × E existing reports | O(I × E) | O(I + E) |
| `update_unique` inside `merge_guard_detail_reports` (headers/methods) | O(N²) | O(N) |

In a large app with R = 500 routes sharing a scope prefix, G = 50 accumulated guard names:
- Defective: 500 × 50 = 25,000 `.contains()` comparisons per finalization
- At G = 500: 250,000 comparisons (500x op-count ratio)

---

## Trigger Conditions

1. Application uses `experimental-introspection` feature.
2. Multiple routes register under the same path prefix (scope nesting).
3. Many distinct custom guard names accumulate per path (user-defined guards via `guard::fn_guard`).
4. Large microservice with hundreds of scoped routes (e.g., REST API with 500+ routes in nested scopes).

---

## Fix Description

Pre-build a `HashSet` for O(1) membership checks before the loop:

```rust
fn update_unique<T: Clone + PartialEq + Eq + std::hash::Hash>(
    existing: &mut Vec<T>,
    new_items: &[T],
) {
    let seen: std::collections::HashSet<_> = existing.iter().collect();
    for item in new_items {
        if !seen.contains(item) {
            existing.push(item.clone());
        }
    }
}
```

For `merge_guard_reports`, build a `HashMap<&str, usize>` (name → index into `existing`) before iterating `incoming`.

For types that cannot be hashed (e.g., `GuardDetailReport`), sort and binary-search, or use a two-pass approach.

---

## Speedup Estimate

At R = 500 routes, G = 500 unique guards accumulated:
- Defective: O(500 × 500) = 250,000 contains-checks
- Fixed: O(500) HashSet inserts + O(500) lookups = ~1,000 ops
- **Ratio: ~250x**

Measured in unit test: see `defects/actix/unit/ActixUpdateUniqueAlgorithm.java`.
