# UNDF: UNDF-2026-000000678
# UNDF: (pending)
# quarkus-0004: HierarchyDiscovery.discoverTypes — O(2^D) diamond type closure re-traversal

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

| Field | Value |
|-------|-------|
| ID | quarkus-0004 |
| Severity | HIGH |
| Ecosystem | quarkus |
| Package | io.quarkus.arc.impl |
| File | `independent-projects/arc/runtime/src/main/java/io/quarkus/arc/impl/HierarchyDiscovery.java` |
| Lines | 58–87 |
| Complexity | O(2^D) on diamond interface/type hierarchies |
| Hot path | ArC CDI bean type closure discovery — startup, injection point resolution |

## Defect

```java
// DEFECT: types.put() return value IGNORED, then unconditional recurse
protected void discoverTypes(Type type, boolean rawGeneric) {
    if (type instanceof Class<?>) {
        Class<?> clazz = (Class<?>) type;
        this.types.put(clazz, clazz);       // return value IGNORED
        discoverFromClass(clazz, rawGeneric); // UNCONDITIONAL → O(2^D)
    } else if (rawGeneric) {
        discoverTypes(Types.getRawType(type), rawGeneric);
    } else if (type instanceof GenericArrayType) {
        // ...
        this.types.put(arrayClass, type);   // return value IGNORED
        discoverFromClass(arrayClass, rawGeneric); // UNCONDITIONAL
    } else if (isParameterizedType(type)) {
        // ...
        this.types.put(clazz, type);        // return value IGNORED
        discoverFromClass(clazz, rawGeneric); // UNCONDITIONAL
    }
}
```

This code is a near-identical copy of Weld's `HierarchyDiscovery` (even retains
the Weld author attribution comment) and inherits the same diamond defect.
`HashMap.put()` returns the prior value when a key already exists; if the class
was already discovered, `discoverFromClass` is redundant but is still called.

For a diamond interface hierarchy at depth D, type closure discovery performs
2^D redundant traversals.

## Fix

```java
// CORRECT: guard on put() return value
protected void discoverTypes(Type type, boolean rawGeneric) {
    if (type instanceof Class<?>) {
        Class<?> clazz = (Class<?>) type;
        if (this.types.put(clazz, clazz) != null) { return; }
        discoverFromClass(clazz, rawGeneric);
    } else if (rawGeneric) {
        discoverTypes(Types.getRawType(type), rawGeneric);
    } else if (type instanceof GenericArrayType) {
        GenericArrayType arrayType = (GenericArrayType) type;
        Type genericComponentType = arrayType.getGenericComponentType();
        Class<?> rawComponentType = Types.getRawType(genericComponentType);
        if (rawComponentType != null) {
            Class<?> arrayClass = Array.newInstance(rawComponentType, 0).getClass();
            if (this.types.put(arrayClass, type) != null) { return; }
            discoverFromClass(arrayClass, rawGeneric);
        }
    } else if (isParameterizedType(type)) {
        final ParameterizedType parameterizedType = asParameterizedType(type);
        final Type rawType = parameterizedType.getRawType();
        if (rawType instanceof Class<?>) {
            Class<?> clazz = (Class<?>) rawType;
            processTypeVariables(clazz.getTypeParameters(), parameterizedType.getActualTypeArguments());
            if (this.types.put(clazz, type) != null) { return; }
            discoverFromClass(clazz, rawGeneric);
        }
    }
}
```

## 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

ArC is Quarkus's CDI container. `HierarchyDiscovery` computes the bean type
closure at startup for every discovered bean. Quarkus applications with
diamond interface hierarchies in their CDI beans will experience quadratic-to-
exponential startup time growth. Native builds are especially affected since
startup is expected to be near-instant.
