# UNDF: UNDF-2026-000000530
# UNDF: (pending)
# weld-0001: Beans.recursiveStereotypeSearch — no visited set O(2^D) on diamond stereotype hierarchy

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

| Field        | Value |
|--------------|-------|
| ID           | weld-0001 |
| Severity     | HIGH |
| Ecosystem    | weld |
| Package      | weld-impl |
| File         | `impl/src/main/java/org/jboss/weld/util/Beans.java` |
| Lines        | 783–804 |
| Complexity   | O(2^D) where D = diamond depth in stereotype annotation hierarchy |
| Hot path     | Called at CDI container startup for every bean type |

## Defect

`Beans.recursiveStereotypeSearch` traverses the CDI stereotype annotation hierarchy
recursively with **no visited-set guard**. It iterates all annotations of a stereotype,
and for each annotation that is itself a `@Stereotype`, recurses without tracking
which stereotypes have already been processed.

On a diamond-shaped stereotype hierarchy (meta-stereotype @A annotated with @B and @C;
both @B and @C are themselves stereotypes annotated with @D), the traversal is:

```
recursiveStereotypeSearch(@A)
  → recursiveStereotypeSearch(@B) → recursiveStereotypeSearch(@D)
  → recursiveStereotypeSearch(@C) → recursiveStereotypeSearch(@D)  ← D visited twice
```

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

```java
// impl/src/main/java/org/jboss/weld/util/Beans.java:783-804 (DEFECT)
private static void recursiveStereotypeSearch(Class<? extends Annotation> stereotype,
        AnnotationSearchResult annotationSearchResult) {
    Priority priorityAnnotation = stereotype.getAnnotation(Priority.class);
    if (priorityAnnotation != null) {
        annotationSearchResult.addPriority(priorityAnnotation.value());
    }
    // ...
    // perform a recursive search for more stereotypes
    for (Annotation annotation : stereotype.getAnnotations()) {
        Class<? extends Annotation> annotationClass = annotation.annotationType();
        if (annotationClass.getAnnotation(Stereotype.class) != null) {
            recursiveStereotypeSearch(annotationClass, annotationSearchResult);
            // NO visited set: @D reachable via @B and @C is re-traversed 2^D times
        }
    }
}
```

Called from `annotationSearch` (line 770-781) for every bean annotation at startup.

## Fix

Add a `Set<Class<? extends Annotation>> visited` guard to prevent re-traversal:

```java
// AFTER — O(N+E): visited set prevents exponential re-traversal
public static AnnotationSearchResult annotationSearch(Annotated type) {
    AnnotationSearchResult annotationSearchResult = new AnnotationSearchResult();
    Set<Class<? extends Annotation>> visited = new HashSet<>();
    for (Annotation annotation : type.getAnnotations()) {
        Class<? extends Annotation> annotationClass = annotation.annotationType();
        if (annotationClass.getAnnotation(Stereotype.class) != null) {
            recursiveStereotypeSearch(annotationClass, annotationSearchResult, visited);
        }
    }
    return annotationSearchResult;
}

private static void recursiveStereotypeSearch(Class<? extends Annotation> stereotype,
        AnnotationSearchResult annotationSearchResult,
        Set<Class<? extends Annotation>> visited) {
    if (!visited.add(stereotype)) {   // O(1): already processed, skip
        return;
    }
    Priority priorityAnnotation = stereotype.getAnnotation(Priority.class);
    if (priorityAnnotation != null) {
        annotationSearchResult.addPriority(priorityAnnotation.value());
    }
    Reserve reserve = stereotype.getAnnotation(Reserve.class);
    if (reserve != null) {
        annotationSearchResult.setReserve(reserve.annotationType());
    }
    Alternative alternative = stereotype.getAnnotation(Alternative.class);
    if (alternative != null) {
        annotationSearchResult.setAlternative(alternative.annotationType());
    }
    for (Annotation annotation : stereotype.getAnnotations()) {
        Class<? extends Annotation> annotationClass = annotation.annotationType();
        if (annotationClass.getAnnotation(Stereotype.class) != null) {
            recursiveStereotypeSearch(annotationClass, annotationSearchResult, visited);
        }
    }
}
```

## Speedup

| Diamond 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).

## Impact

Weld is the CDI reference implementation, used by WildFly, GlassFish, Payara, and
indirectly by Quarkus (CDI layer). Diamond CDI stereotype hierarchies arise naturally
in enterprise patterns: a shared `@ApplicationScoped @Transactional @Named` meta-stereotype
and multiple extending stereotypes converging on it.
