# UNDF: UNDF-2026-000000680
# UNDF: (pending)
# weld-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 | weld-0004 |
| Severity | HIGH |
| Ecosystem | weld-core |
| Package | org.jboss.weld.util.reflection |
| File | `impl/src/main/java/org/jboss/weld/util/reflection/HierarchyDiscovery.java` |
| Lines | 106–135 |
| Complexity | O(2^D) on diamond interface/type hierarchies |
| Hot path | CDI bean type closure discovery — every bean startup, every 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 (type instanceof GenericArrayType) {
        // ...
        this.types.put(arrayClass, type);  // return value IGNORED
        discoverFromClass(arrayClass, rawGeneric); // UNCONDITIONAL
    } else if (type instanceof ParameterizedType) {
        // ...
        this.types.put(clazz, type);       // return value IGNORED
        discoverFromClass(clazz, rawGeneric); // UNCONDITIONAL
    }
}

protected void discoverFromClass(Class<?> clazz, boolean rawGeneric) {
    if (clazz.getSuperclass() != null) {
        discoverTypes(..., clazz.getSuperclass(), ...);  // recurses
    }
    discoverInterfaces(clazz, rawGeneric);  // recurses into all interfaces
}
```

For a diamond hierarchy `A implements B,C; B extends D; C extends D`, `D` is
re-traversed from both `B` and `C` paths. At depth D, 2^D traversals occur.

`HashMap.put(k,v)` returns the previous value — if non-null, the class was
already discovered and `discoverFromClass` need not be called. The guard is
available but not checked.

## Fix

```java
// CORRECT: check put() return value — skip recursion if already discovered
protected void discoverTypes(Type type, boolean rawGeneric) {
    if (type instanceof Class<?>) {
        Class<?> clazz = (Class<?>) type;
        if (this.types.put(clazz, clazz) != null) { return; } // already visited
        discoverFromClass(clazz, rawGeneric);
    } else if (type instanceof GenericArrayType) {
        GenericArrayType arrayType = (GenericArrayType) type;
        Type genericComponentType = arrayType.getGenericComponentType();
        Class<?> rawComponentType = Reflections.getRawType(genericComponentType);
        if (rawComponentType != null) {
            Class<?> arrayClass = Array.newInstance(rawComponentType, 0).getClass();
            if (this.types.put(arrayClass, type) != null) { return; } // already visited
            discoverFromClass(arrayClass, rawGeneric);
        }
    } else if (type instanceof ParameterizedType) {
        ParameterizedType parameterizedType = (ParameterizedType) type;
        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; } // already visited
            discoverFromClass(clazz, rawGeneric);
        }
    }
}
```

Note: `HashMap.put()` returns the previous mapping for the key, or `null` if
there was no previous mapping. If non-null → already discovered → skip.

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

`HierarchyDiscovery` is called for every CDI bean's type closure:
- `EnhancedAnnotatedTypeImpl` — enhanced type construction
- `BackedAnnotatedType` — slim annotated types
- Injection point resolution across the entire CDI container

Applications with deep interface diamond hierarchies (e.g. service layers
implementing multiple generic interfaces sharing common supertypes) will
experience exponential CDI startup times.
