# UNDF: UNDF-2026-000000676
# UNDF: (pending)
# micronaut-0005: NativeElementsHelper.populateTypeHierarchy — O(2^D) diamond hierarchy re-traversal

## CWE-407 — Algorithmic Complexity: O(2^D) recursive diamond re-traversal

| Field | Value |
|-------|-------|
| ID | micronaut-0005 |
| Severity | HIGH |
| Ecosystem | micronaut-core |
| Package | io.micronaut.inject.utils |
| File | `core-processor/src/main/java/io/micronaut/inject/utils/NativeElementsHelper.java` |
| Lines | 139–150 |
| Complexity | O(2^D) on diamond interface hierarchies |
| Hot path | Annotation processing — every bean type hierarchy traversal at compile time |

## Defect

```java
// DEFECT: no visited guard; hierarchy.add() called AFTER unconditional recursion
public final void populateTypeHierarchy(C element, List<C> hierarchy) {
    for (C anInterface : getInterfaces(element)) {
        populateTypeHierarchy(anInterface, hierarchy); // UNCONDITIONAL → O(2^D)
    }
    C superClass = getSuperClass(element);
    if (superClass != null) {
        populateTypeHierarchy(superClass, hierarchy);  // UNCONDITIONAL → O(2^D)
    }
    if (!excludeClass(element)) {
        hierarchy.add(element);  // added AFTER recursion, so duplicate check must be pre-recursion
    }
}
```

For a diamond interface hierarchy `A implements B,C; B extends D; C extends D`,
calling `populateTypeHierarchy(A, list)` will call:
- `populateTypeHierarchy(B, list)` → `populateTypeHierarchy(D, list)` [adds D]
- `populateTypeHierarchy(C, list)` → `populateTypeHierarchy(D, list)` [adds D again]

`D` is traversed and added twice. At diamond depth D, 2^D traversals occur.
The `List<C> hierarchy` can also contain duplicates since there is no
deduplication before recursing.

## Fix

```java
// CORRECT: check if element already in hierarchy before recursing
public final void populateTypeHierarchy(C element, List<C> hierarchy) {
    if (hierarchy.contains(element)) { return; } // guard: O(N) but prevents O(2^D)
    // Better: pass a Set<C> visited parameter for O(1) guard
    for (C anInterface : getInterfaces(element)) {
        populateTypeHierarchy(anInterface, hierarchy);
    }
    C superClass = getSuperClass(element);
    if (superClass != null) {
        populateTypeHierarchy(superClass, hierarchy);
    }
    if (!excludeClass(element)) {
        hierarchy.add(element);
    }
}
```

Alternatively (preferred — O(1) visited check):

```java
public final void populateTypeHierarchy(C element, List<C> hierarchy) {
    Set<C> visited = new HashSet<>();
    populateTypeHierarchy(element, hierarchy, visited);
}

private void populateTypeHierarchy(C element, List<C> hierarchy, Set<C> visited) {
    if (!visited.add(element)) { return; } // guard: skip if already visited
    for (C anInterface : getInterfaces(element)) {
        populateTypeHierarchy(anInterface, hierarchy, visited);
    }
    C superClass = getSuperClass(element);
    if (superClass != null) {
        populateTypeHierarchy(superClass, hierarchy, visited);
    }
    if (!excludeClass(element)) {
        hierarchy.add(element);
    }
}
```

## Speedup

| Diamond depth (D) | Before (traversals) | After (traversals) | Speedup |
|------------------|--------------------|--------------------|---------|
| 5 | 31 | 5 | 6× |
| 10 | 1,023 | 10 | 102× |
| 15 | 32,767 | 15 | 2,184× |
| 20 | 1,048,575 | 20 | 52,428× |

## Impact

`populateTypeHierarchy` is called during annotation processing (compile time)
for every class element traversal in Micronaut's bean model construction.
Deep diamond hierarchies in service/repository classes will cause exponential
annotation-processor execution time, slowing builds significantly.
