# UNDF: UNDF-2026-000000550
# UNDF: (pending)
# weld-0002: Interceptors.addInheritedInterceptorBindings — no visited set O(2^D) diamond re-traversal

## CWE-407 — Algorithmic Complexity: Exponential Re-traversal on Diamond Interceptor Binding Hierarchy

| Field        | Value |
|--------------|-------|
| ID           | weld-0002 |
| Severity     | MEDIUM |
| Ecosystem    | weld |
| Package      | weld-impl |
| File         | `impl/src/main/java/org/jboss/weld/util/Interceptors.java` |
| Lines        | 91–100 |
| Complexity   | O(2^D) where D = diamond depth in @InterceptorBinding meta-annotation hierarchy |
| Hot path     | Called at CDI container startup during interceptor binding flattening |

## Defect

`Interceptors.addInheritedInterceptorBindings` recursively traverses the CDI
interceptor binding meta-annotation hierarchy with **no visited-set guard**.
It recurses into every meta-binding annotation without tracking which types
have already been processed.

On a diamond interceptor hierarchy (@A meta-annotated with @B and @C; both @B
and @C meta-annotated with @D), the traversal visits @D twice:

```
addInheritedInterceptorBindings(@A)
  → addInheritedInterceptorBindings(@B) → addInheritedInterceptorBindings(@D)
  → addInheritedInterceptorBindings(@C) → addInheritedInterceptorBindings(@D) ← D again
```

At depth D: 2^D redundant traversals.

```java
// impl/src/main/java/org/jboss/weld/util/Interceptors.java:91-100 (DEFECT)
private static void addInheritedInterceptorBindings(EnhancedAnnotatedType<?> clazz,
        Class<? extends Annotation> bindingType,
        MetaAnnotationStore metaAnnotationStore,
        Set<Annotation> flattenInterceptorBindings) {
    Set<Annotation> metaBindings = metaAnnotationStore.getInterceptorBindingModel(bindingType)
            .getInheritedInterceptionBindingTypes();
    addInterceptorBindings(clazz, metaBindings, flattenInterceptorBindings, metaAnnotationStore);
    for (Annotation metaBinding : metaBindings) {
        addInheritedInterceptorBindings(clazz, metaBinding.annotationType(), metaAnnotationStore,
                flattenInterceptorBindings);
        // NO visited set: @D reachable via @B and @C is re-traversed
    }
}
```

Note: `flattenInterceptorBindings` is a `Set<Annotation>`, so duplicate
insertions are rejected — but the recursive traversal still happens, repeating
the same work exponentially.

## Fix

Add a `Set<Class<? extends Annotation>> visited` parameter threaded through the
recursion. Guard at entry with `visited.add(bindingType)`.

```java
// AFTER — O(N+E): visited set prevents exponential re-traversal
// Caller:
for (Annotation annotation : rawBindings) {
    addInheritedInterceptorBindings(clazz, annotation.annotationType(),
        metaAnnotationStore, flattenInterceptorBindings, new HashSet<>());
}

private static void addInheritedInterceptorBindings(EnhancedAnnotatedType<?> clazz,
        Class<? extends Annotation> bindingType,
        MetaAnnotationStore metaAnnotationStore,
        Set<Annotation> flattenInterceptorBindings,
        Set<Class<? extends Annotation>> visited) {
    if (!visited.add(bindingType)) {   // O(1): already processed
        return;
    }
    Set<Annotation> metaBindings = metaAnnotationStore.getInterceptorBindingModel(bindingType)
            .getInheritedInterceptionBindingTypes();
    addInterceptorBindings(clazz, metaBindings, flattenInterceptorBindings, metaAnnotationStore);
    for (Annotation metaBinding : metaBindings) {
        addInheritedInterceptorBindings(clazz, metaBinding.annotationType(),
            metaAnnotationStore, flattenInterceptorBindings, 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).
