# UNDF: UNDF-2026-000000005
# ans-0001: role get_vars() seen-list O(D²) deduplication over transitive dependencies

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** ~30x at D=80 half-duplicate dependencies (verified by unit test)
**Target:** Ansible (ansible/ansible)
**Files:**
- `lib/ansible/playbook/role/__init__.py:539-546` — `seen = []` list deduplication

## Description

`get_vars()` deduplicates transitive role dependencies using a plain list:

```python
seen = []
for dep in self.get_all_dependencies():        # O(D) outer loop
    if dep not in seen:                        # O(D) linear scan — O(D²) total
        all_vars = combine_vars(all_vars, dep.get_vars(include_params=False, only_exports=True))
        seen.append(dep)
```

`get_vars()` is called during task compilation — once per role, per play.
With D transitive dependencies, total membership comparisons = D*(D-1)/2 = O(D²).

For a playbook with 100 transitive role dependencies, this is ~4,950 comparisons
per role var computation instead of 100.

The source code TODO comment at this location already flagged the underlying
issue: "re-examine dep loading to see if we are somehow improperly adding
the same dep too many times."

## Root Cause

`Role` defines `__eq__` for value-based comparison but not `__hash__`, so
a plain `set()` of `Role` objects would raise `TypeError` at runtime.
The `seen` list was used as a workaround, at the cost of O(D) per check.

Fix: use `id(dep)` as the identity key — `seen_ids = set()` of integers,
giving O(1) average membership test. Identity deduplication is correct here
because `get_all_dependencies()` returns actual Role object references, and
duplicate entries are the same object appearing multiple times.

## Patch

See `patch/ans-0001-role-get-vars-seen-id-set.patch`

## Complexity Before

`dep not in seen` per iteration: **O(D)**
Total across D dependencies: **O(D²)**

## Complexity After

`id(dep) not in seen_ids`: **O(1)** average
Total: **O(D)**

## Reproduction

```
cd defects/ansible/unit && javac -d . AnsibleRoleTest.java && java -ea unit.AnsibleRoleTest
```

test1: D=60 unique deps, defect=1770, fixed=60 (29.5x ratio)
test2: D=80 half-unique deps, ratio=29.8x
