# UNDF: UNDF-2026-000000518
# quarkus-0002: ComponentsProviderGenerator.isDependency — O(B×D) dependants.contains in loop

## CWE-407 — Algorithmic Complexity: Linear Membership Test in Loop

| Field        | Value |
|--------------|-------|
| ID           | quarkus-0002 |
| Severity     | MEDIUM |
| Ecosystem    | quarkus |
| Package      | arc/processor |
| File         | `independent-projects/arc/processor/src/main/java/io/quarkus/arc/processor/ComponentsProviderGenerator.java` |
| Lines        | 771 |
| Complexity   | O(B × D) where B = bean count, D = dependants per bean; called O(B) times = O(B² × D) total |
| Fix          | Build a reverse-lookup `Set<BeanInfo>` of all current dependants |

## Description

`isDependency(BeanInfo bean, Map<BeanInfo, List<BeanInfo>> dependencyMap)` iterates over all
values in the dependency map (lists of dependants) and calls `dependants.contains(bean)` — O(D)
on each `ArrayList<BeanInfo>`.

```java
private boolean isDependency(BeanInfo bean, Map<BeanInfo, List<BeanInfo>> dependencyMap) {
    for (List<BeanInfo> dependants : dependencyMap.values()) {  // O(B)
        if (dependants.contains(bean)) {                        // O(D) ArrayList scan
            return true;
        }
    }
    return false;
}
```

`isDependency` is called from lambdas passed to `addBeans()` which are invoked in a `while`
loop that iterates until the dependency map is empty — so `isDependency` is called O(B) times
total = O(B² × D) overall work.

### Impact

Quarkus build-time CDI processing runs `preprocessBeans()` on every build. As the number of
CDI beans grows (large applications with hundreds of beans), this becomes O(B²×D) — a quadratic
build-time cost in application size.

## Fix

Build an inverted index (a flat `Set<BeanInfo>`) once, before the loop:

```java
// Precompute: set of all beans that appear as a dependant in ANY entry
private static Set<BeanInfo> buildDependantSet(Map<BeanInfo, List<BeanInfo>> dependencyMap) {
    Set<BeanInfo> allDependants = new HashSet<>();
    for (List<BeanInfo> dependants : dependencyMap.values()) {
        allDependants.addAll(dependants);
    }
    return allDependants;
}
```

Then replace `isDependency(b, dependencyMap)` with `allDependants.contains(b)` — O(1).

The set must be recomputed after `addBeans()` removes entries from the map (or maintained
incrementally). The simplest correct fix: rebuild the set once per while-loop iteration,
which reduces total cost from O(B²×D) to O(B×D + B) — linear in total dependency edges.

## Speedup Estimate

At B=300 beans, D=10 average dependants: 300 × 300 × 10 = 900,000 → 300 × 10 = 3,000.
**300x speedup** on large Quarkus applications.
