# UNDF: UNDF-2026-000000580
# UNDF: (pending)
# dagger-0001: LegacyBindingGraphFactory.resolve — cycleStack Deque.contains() O(N) cycle detection

## CWE-407 — Algorithmic Complexity: O(N) Deque membership scan in recursive dependency resolution

| Field        | Value |
|--------------|-------|
| ID           | dagger-0001 |
| Severity     | MEDIUM |
| Ecosystem    | dagger |
| Package      | dagger-compiler |
| File         | `dagger-compiler/main/java/dagger/internal/codegen/binding/LegacyBindingGraphFactory.java` |
| Lines        | 312, 512, 723 |
| Complexity   | O(N) per call; O(N×D) total over depth-D resolution chain |
| Hot path     | Called during Dagger component binding resolution (annotation processing) |

## Defect

`LegacyBindingGraphFactory.Resolver.resolve(Key)` uses a `Deque<Key> cycleStack` for cycle detection.
`Deque.contains()` is O(N) — it performs a linear scan over all elements in the deque:

```java
// LegacyBindingGraphFactory.java:312
final Deque<Key> cycleStack = new ArrayDeque<>();

// LegacyBindingGraphFactory.java:720-740 (DEFECT)
void resolve(Key key) {
    if (cycleStack.contains(key)) {  // O(N) linear scan of Deque
        return;
    }
    if (resolvedContributionBindings.containsKey(key)) {  // O(1) — HashMap
        return;
    }
    cycleStack.push(key);
    try {
        LegacyResolvedBindings bindings = lookUpBindings(key);
        resolvedContributionBindings.put(key, bindings);
        resolveDependencies(bindings);   // recurses
    } finally {
        cycleStack.pop();
    }
}
```

Also at line 512 in `createDelegateBinding`:
```java
if (cycleStack.contains(delegateKey)) {   // O(N) linear scan of Deque
    return bindingFactory.unresolvedDelegateBinding(delegateDeclaration);
}
```

For a dependency graph of N bindings with max chain depth D, `cycleStack.contains()` is called N times
at an average depth of D/2, giving O(N×D) total comparisons instead of O(N).

For a large Dagger component with 200 bindings in a chain of depth 20:
- Before: 200 × 10 = 2,000 contains-comparisons
- After: 200 × 1 = 200 contains-comparisons (O(1) HashSet lookup)

## Fix

Add a parallel `Set<Key> cycleSet` that mirrors the Deque's membership for O(1) contains:

```java
// AFTER — O(1) cycle detection
final Deque<Key> cycleStack = new ArrayDeque<>();
final Set<Key> cycleSet = new HashSet<>();     // ADD: mirrors cycleStack membership

void resolve(Key key) {
    if (cycleSet.contains(key)) {              // O(1) HashSet lookup
        return;
    }
    if (resolvedContributionBindings.containsKey(key)) {
        return;
    }
    cycleStack.push(key);
    cycleSet.add(key);                         // ADD: keep mirror in sync
    try {
        LegacyResolvedBindings bindings = lookUpBindings(key);
        resolvedContributionBindings.put(key, bindings);
        resolveDependencies(bindings);
    } finally {
        cycleStack.pop();
        cycleSet.remove(key);                  // ADD: remove on pop
    }
}
```

Same fix for `createDelegateBinding` line 512: replace `cycleStack.contains(delegateKey)` with
`cycleSet.contains(delegateKey)`.

## Speedup

| Bindings (N) × Depth (D) | Before (comparisons) | After (comparisons) | Speedup |
|--------------------------|----------------------|---------------------|---------|
| 50 × 10                  | 250                  | 50                  | 5×      |
| 100 × 20                 | 1,000                | 100                 | 10×     |
| 200 × 50                 | 5,000                | 200                 | 25×     |

Growth before: O(N×D). Growth after: O(N).
