# UNDF: UNDF-2026-000000296
# UNDF: (pending)
# spring-0003: AnnotationTypeMapping.processAliases — O(A²×D×L) ArrayList.contains in nested annotation attribute loop

## CWE-407 — Algorithmic Complexity: Unnecessary Quadratic Complexity (List membership inside nested loop)

| Field | Value |
|-------|-------|
| ID | spring-0003 |
| Severity | MEDIUM |
| Ecosystem | spring-framework |
| Package | org.springframework.core.annotation |
| File | `spring-core/src/main/java/org/springframework/core/annotation/AnnotationTypeMapping.java` |
| Lines | 197–258, 556–573 |
| Complexity | O(A²×D×L) |
| Hot path | annotation type mapping initialization (startup + first use per annotation type) |

## Defect

`AnnotationTypeMapping.processAliases()` resolves `@AliasFor` relationships across
meta-annotation hierarchies. It is called once per annotation type during mapping
construction (cached afterwards). The `aliases` local variable is an `ArrayList<Method>`.

For each annotation attribute (A attributes), `processAliases(i, aliases)` is called.
Inside that method, for each level in the meta-annotation chain (D levels), it iterates
over all attributes (A) and calls `aliases.contains(mapping.attributes.get(i))` — an O(L)
scan where L is the current aliases list size. The same pattern appears in
`getFirstRootAttributeIndex()` and `MirrorSets.updateFrom()`.

```java
// processAliases(int attributeIndex, List<Method> aliases) — lines 223-248
AnnotationTypeMapping mapping = this;
while (mapping != null) {                         // D iterations (meta-annotation depth)
    if (rootAttributeIndex != -1 && mapping != this.root) {
        for (int i = 0; i < mapping.attributes.size(); i++) {  // A iterations
            if (aliases.contains(mapping.attributes.get(i))) { // O(L) scan
                mapping.aliasMappings[i] = rootAttributeIndex;
            }
        }
    }
    mapping.mirrorSets.updateFrom(aliases);       // updateFrom also calls aliases.contains()
    ...
    mapping = mapping.source;
}

// MirrorSets.updateFrom(Collection<Method> aliases) — lines 556-573
for (int i = 0; i < attributes.size(); i++) {     // A iterations
    Method attribute = attributes.get(i);
    if (aliases.contains(attribute)) {             // O(L) scan
        ...
    }
}
```

Total cost per annotation type: O(A × D × A × L) = O(A²×D×L).

For complex composed annotations (e.g., `@SpringBootTest`, `@Transactional`, framework
stereotypes with `@AliasFor` chains), A can be 10–30, D can be 5–10, L can be 5–10,
yielding up to ~90,000 operations per annotation type initialization.

## Fix

Replace `List<Method>` with `LinkedHashSet<Method>` for `aliases` to make `.contains()`
O(1) while preserving insertion order (order matters for alias resolution):

```java
private void processAliases() {
    Set<Method> aliases = new LinkedHashSet<>();  // was: List<Method> aliases = new ArrayList<>();
    for (int i = 0; i < this.attributes.size(); i++) {
        aliases.clear();
        aliases.add(this.attributes.get(i));
        collectAliases(aliases);
        if (aliases.size() > 1) {
            processAliases(i, aliases);
        }
    }
}
```

The `processAliases(int, List<Method>)` signature must also accept `Collection<Method>`
or `Set<Method>` (or keep `List<Method>` and pass `new ArrayList<>(aliases)`).
Similarly update `getFirstRootAttributeIndex()` and `MirrorSets.updateFrom()` parameter
types to accept `Collection<Method>`.

## Speedup

| A (attributes) | D (depth) | L (alias list) | Before (ops) | After (ops) | Speedup |
|---------------|-----------|---------------|-------------|-------------|---------|
| 10 | 5 | 5 | 2,500 | 500 | 5× |
| 20 | 8 | 10 | 32,000 | 4,000 | 8× |
| 30 | 10 | 15 | 135,000 | 9,000 | 15× |

Annotation types are cached after first construction, so this is a startup / first-use
cost rather than per-request. Applications with many composed annotations (Spring Boot,
Spring Security, Spring Data) construct many such mappings during startup.
