# UNDF: UNDF-2026-000000469
# UNDF: (pending)
# quarkus-0003: BeanDeployment.recursiveBuild — transitive binding traversal no visited set O(2^D)

## CWE-407 — Algorithmic Complexity: Exponential Recursion on Diamond Annotation Hierarchy

| Field        | Value |
|--------------|-------|
| ID           | quarkus-0003 |
| Severity     | MEDIUM |
| Ecosystem    | quarkus |
| Package      | arc/processor |
| File         | `independent-projects/arc/processor/src/main/java/io/quarkus/arc/processor/BeanDeployment.java` |
| Lines        | 955–964 |
| Complexity   | O(2^D) where D = diamond depth in annotation hierarchy |
| Hot path     | Called at application startup for every binding annotation |

## Description

`BeanDeployment.recursiveBuild(DotName name, Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap)`
traverses the transitive annotation binding graph recursively with no visited-set guard.

On a diamond-shaped annotation hierarchy (annotation A meta-annotated with @B and @C;
both @B and @C meta-annotated with @D), the call tree is:

```
recursiveBuild(A) → recursiveBuild(B) → recursiveBuild(D)
                 → recursiveBuild(C) → recursiveBuild(D)   ← D visited twice
```

At depth D, @D is visited 2^D times. At D=24: 16,777,216 redundant visits.

```java
// BEFORE — O(2^D): no visited set — exponential on diamond annotation hierarchies
private static Set<AnnotationInstance> recursiveBuild(DotName name,
        Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap) {
    Set<AnnotationInstance> result = transitiveBindingsMap.get(name);
    for (AnnotationInstance instance : transitiveBindingsMap.get(name)) {
        if (transitiveBindingsMap.containsKey(instance.name())) {
            result.addAll(recursiveBuild(instance.name(), transitiveBindingsMap));
        }
    }
    return result;
}
```

Note: `result` is the same reference as `transitiveBindingsMap.get(name)` — the function
modifies the map's values in-place during iteration, which also carries a
`ConcurrentModificationException` risk if the Set implementation doesn't tolerate modification.

## Fix

Add a `Set<DotName> visited` parameter to guard against revisiting the same annotation node.

```java
// AFTER — O(N+E): visited set prevents exponential re-traversal
for (DotName name : result.keySet()) {
    result.put(name, recursiveBuild(name, result, new HashSet<>()));
}

private static Set<AnnotationInstance> recursiveBuild(DotName name,
        Map<DotName, Set<AnnotationInstance>> transitiveBindingsMap,
        Set<DotName> visited) {
    if (!visited.add(name)) {
        return Collections.emptySet();
    }
    Set<AnnotationInstance> result = new HashSet<>(transitiveBindingsMap.get(name));
    for (AnnotationInstance instance : transitiveBindingsMap.get(name)) {
        if (transitiveBindingsMap.containsKey(instance.name())) {
            result.addAll(recursiveBuild(instance.name(), transitiveBindingsMap, visited));
        }
    }
    return result;
}
```

## Speedup

| Annotation depth (D) | Before (calls) | After (calls) | Speedup |
|---------------------|---------------|---------------|---------|
| 10                  | 1,023         | 10            | 102×    |
| 15                  | 32,767        | 15            | 2,184×  |
| 20                  | 1,048,575     | 20            | 52,428× |

Growth before: O(2^D). Growth after: O(D).
