# UNDF: UNDF-2026-000000554
# weld-0003: MergedStereotypes.merge — no visited set O(2^D) on diamond meta-stereotype hierarchy

## CWE-407 — Algorithmic Complexity: Exponential Re-traversal on Diamond CDI Meta-Stereotype Hierarchy

| Field        | Value |
|--------------|-------|
| ID           | weld-0003 |
| Severity     | HIGH |
| Ecosystem    | weld |
| Package      | weld-impl |
| File         | `impl/src/main/java/org/jboss/weld/metadata/cache/MergedStereotypes.java` |
| Lines        | 75–98 |
| Complexity   | O(2^D) where D = diamond depth in CDI meta-stereotype annotation hierarchy |
| Hot path     | Called at CDI container startup via BeanAttributesFactory for every bean type |

## Defect

`MergedStereotypes.merge()` traverses the CDI meta-stereotype hierarchy recursively
with **no visited-set guard**. It iterates over stereotype annotations, and for each
one calls `merge(stereotype.getInheritedStereotypes())` unconditionally — without
first checking whether that stereotype type has already been processed in the current
traversal.

`this.stereotypes.add(stereotypeAnnotation.annotationType())` at line 95 accumulates
the output set, but the **return value is ignored** — the code never checks whether
the type was already present before recursing at line 97.

On a diamond-shaped meta-stereotype hierarchy (bean annotated with @StA; @StA
inherits from @StB and @StC; both @StB and @StC inherit from @StBase), the traversal
visits @StBase twice:

```
merge({@StA})
  → process @StA: merge(getInheritedStereotypes(@StA)) = merge({@StB, @StC})
    → process @StB: merge(getInheritedStereotypes(@StB)) = merge({@StBase})
      → process @StBase: (no children)
    → process @StC: merge(getInheritedStereotypes(@StC)) = merge({@StBase})
      → process @StBase: VISITED AGAIN — no guard
```

At depth D: the base stereotype is visited 2^D times.

```java
// impl/src/main/java/org/jboss/weld/metadata/cache/MergedStereotypes.java:75-98 (DEFECT)
protected void merge(Set<Annotation> stereotypeAnnotations) {
    final MetaAnnotationStore store = manager.getServices().get(MetaAnnotationStore.class);
    for (Annotation stereotypeAnnotation : stereotypeAnnotations) {
        StereotypeModel<?> stereotype = store.getStereotype(stereotypeAnnotation.annotationType());
        if (stereotype == null) {
            throw MetadataLogger.LOG.stereotypeNotRegistered(stereotypeAnnotation);
        }
        if (stereotype.isAlternative()) {
            alternative = true;
        }
        if (stereotype.isReserve()) {
            reserve = true;
        }
        if (stereotype.getDefaultScopeType() != null) {
            possibleScopeTypes.add(stereotype.getDefaultScopeType());
        }
        if (stereotype.isBeanNameDefaulted()) {
            beanNameDefaulted = true;
        }
        this.stereotypes.add(stereotypeAnnotation.annotationType());  // return value IGNORED
        // Merge in inherited stereotypes
        merge(stereotype.getInheritedStereotypes());  // NO visited guard
    }
}
```

Called from `BeanAttributesFactory.BeanAttributesBuilder.initStereotypes()` for every
CDI-managed bean at container startup. A new `MergedStereotypes` is constructed per
bean — results are NOT shared — so the exponential work is repeated for every bean
that carries a diamond meta-stereotype chain.

## Fix

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

```java
// AFTER — O(N+E): visited set prevents exponential re-traversal
public class MergedStereotypes<T, E> {
    // ... existing fields ...
    private final Set<Class<? extends Annotation>> visited = new HashSet<>();

    protected void merge(Set<Annotation> stereotypeAnnotations) {
        final MetaAnnotationStore store = manager.getServices().get(MetaAnnotationStore.class);
        for (Annotation stereotypeAnnotation : stereotypeAnnotations) {
            // O(1): skip if already processed — prevents O(2^D) diamond re-traversal
            if (!visited.add(stereotypeAnnotation.annotationType())) {
                continue;
            }
            StereotypeModel<?> stereotype = store.getStereotype(stereotypeAnnotation.annotationType());
            if (stereotype == null) {
                throw MetadataLogger.LOG.stereotypeNotRegistered(stereotypeAnnotation);
            }
            if (stereotype.isAlternative()) {
                alternative = true;
            }
            if (stereotype.isReserve()) {
                reserve = true;
            }
            if (stereotype.getDefaultScopeType() != null) {
                possibleScopeTypes.add(stereotype.getDefaultScopeType());
            }
            if (stereotype.isBeanNameDefaulted()) {
                beanNameDefaulted = true;
            }
            this.stereotypes.add(stereotypeAnnotation.annotationType());
            merge(stereotype.getInheritedStereotypes());
        }
    }
}
```

## Speedup

| Diamond depth (D) | Before (merge() calls) | After (merge() calls) | Speedup |
|------------------|------------------------|----------------------|---------|
| 5                | 31                     | 5                    | 6×      |
| 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).

## Relationship to Existing Weld Defects

This is a third independent defect site in weld-impl:

| ID        | File                              | Method                              |
|-----------|-----------------------------------|-------------------------------------|
| weld-0001 | `util/Beans.java`                 | `recursiveStereotypeSearch()`       |
| weld-0002 | `util/Interceptors.java`          | `addInheritedInterceptorBindings()` |
| weld-0003 | `metadata/cache/MergedStereotypes.java` | `merge()`                     |

All three are triggered at CDI container startup. Each operates on different
annotation hierarchy types (stereotypes for 0001/0003, interceptor bindings for 0002)
through different code paths.

## Impact

Weld is the CDI reference implementation, used by WildFly, GlassFish, Payara, and
as the CDI layer in Quarkus. Diamond meta-stereotype hierarchies arise in enterprise
patterns: shared `@ApplicationScoped @Transactional @Named` base stereotypes extended
by multiple domain-specific stereotypes. A D=15 diamond incurs 32,767 redundant
`merge()` calls per bean at startup.
