# UNDF: UNDF-2026-000000562
# UNDF: (pending)
# spring-0007: AnnotationsScanner.processClassHierarchy — O(2^D) diamond annotation re-traversal

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

| Field | Value |
|-------|-------|
| ID | spring-0007 |
| Severity | HIGH |
| Ecosystem | spring-framework |
| Package | org.springframework.core.annotation |
| File | `spring-core/src/main/java/org/springframework/core/annotation/AnnotationsScanner.java` |
| Lines | 173–232 |
| Complexity | O(2^D) on diamond interface/annotation hierarchies |
| Hot path | `MergedAnnotations.from(element, TYPE_HIERARCHY)` — used by every `@Autowired`, `@Component`, AOP advisor scan |

## Defect

```java
// DEFECT: no visited set; interfaces recursed unconditionally with no diamond guard
private static <C, R> @Nullable R processClassHierarchy(C context, int[] aggregateIndex,
        Class<?> source, AnnotationsProcessor<C, R> processor,
        boolean includeInterfaces, Predicate<Class<?>> searchEnclosingClass) {
    try {
        R result = processor.doWithAggregate(context, aggregateIndex[0]);
        if (result != null) { return result; }
        if (hasPlainJavaAnnotationsOnly(source)) { return null; }
        @Nullable Annotation[] annotations = getDeclaredAnnotations(source, false);
        result = processor.doWithAnnotations(context, aggregateIndex[0], source, annotations);
        if (result != null) { return result; }
        aggregateIndex[0]++;
        if (includeInterfaces) {
            for (Class<?> interfaceType : source.getInterfaces()) {
                R interfacesResult = processClassHierarchy(context, aggregateIndex,
                    interfaceType, processor, true, searchEnclosingClass); // UNCONDITIONAL → O(2^D)
                if (interfacesResult != null) { return interfacesResult; }
            }
        }
        Class<?> superclass = source.getSuperclass();
        if (superclass != Object.class && superclass != null) {
            R superclassResult = processClassHierarchy(context, aggregateIndex,
                superclass, processor, includeInterfaces, searchEnclosingClass); // recurses
            ...
        }
        ...
    }
}
```

There is no `visited` set tracking which types have been processed. When
`TYPE_HIERARCHY` search strategy is used with `includeInterfaces=true`, any
class that appears as a shared ancestor (diamond) is processed exponentially
many times.

`hasPlainJavaAnnotationsOnly` only short-circuits for `java.*` types and
`Ordered.class` — custom interface diamonds at any depth are fully re-traversed.

The `processMethodHierarchy` method (lines 261–321) has the same structure and
the same diamond defect when `includeInterfaces=true`.

## Fix

```java
// CORRECT: add a Set<Class<?>> visited parameter to guard diamond re-traversal
private static <C, R> @Nullable R processClassHierarchy(C context, int[] aggregateIndex,
        Class<?> source, AnnotationsProcessor<C, R> processor,
        boolean includeInterfaces, Predicate<Class<?>> searchEnclosingClass) {
    Set<Class<?>> visited = new HashSet<>();
    return processClassHierarchy(context, aggregateIndex, source, processor,
            includeInterfaces, searchEnclosingClass, visited);
}

private static <C, R> @Nullable R processClassHierarchy(C context, int[] aggregateIndex,
        Class<?> source, AnnotationsProcessor<C, R> processor,
        boolean includeInterfaces, Predicate<Class<?>> searchEnclosingClass,
        Set<Class<?>> visited) {
    if (!visited.add(source)) { return null; } // guard: skip already-visited types
    try {
        R result = processor.doWithAggregate(context, aggregateIndex[0]);
        if (result != null) { return result; }
        if (hasPlainJavaAnnotationsOnly(source)) { return null; }
        @Nullable Annotation[] annotations = getDeclaredAnnotations(source, false);
        result = processor.doWithAnnotations(context, aggregateIndex[0], source, annotations);
        if (result != null) { return result; }
        aggregateIndex[0]++;
        if (includeInterfaces) {
            for (Class<?> interfaceType : source.getInterfaces()) {
                R interfacesResult = processClassHierarchy(context, aggregateIndex,
                    interfaceType, processor, true, searchEnclosingClass, visited);
                if (interfacesResult != null) { return interfacesResult; }
            }
        }
        // ... superclass and enclosing class handling unchanged, passing visited
    }
    ...
}
```

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

`AnnotationsScanner.processClassHierarchy` is the innermost engine behind
Spring's entire annotation scanning infrastructure:

- `MergedAnnotations.from(element, SearchStrategy.TYPE_HIERARCHY)`
- `AnnotatedElementUtils.findMergedAnnotation()` — used by every `@RequestMapping`, `@Transactional`, `@Cacheable`, `@Async` lookup
- `AnnotationUtils.findAnnotation()` when interface hierarchy scanning is enabled
- AOP advisor scanning on application startup

Any Spring application using annotation-driven AOP, Spring MVC, Spring Data,
or Spring Security where annotated interfaces form diamond hierarchies
(e.g. a `@Transactional` service interface extended by multiple intermediate
interfaces) will experience exponential annotation scanning time.

This defect is present in both `processClassHierarchy` and
`processMethodHierarchy`.
