# UNDF: UNDF-2026-000000540
# spring-0001: AnnotationTypeMapping — O(A²×M) aliases.contains in nested loops

## CWE-407 — Algorithmic Complexity: Linear Membership Test in Loop

| Field        | Value |
|--------------|-------|
| ID           | spring-0001 |
| Severity     | HIGH |
| Ecosystem    | spring-framework |
| Package      | spring-core |
| File         | `spring-core/src/main/java/org/springframework/core/annotation/AnnotationTypeMapping.java` |
| Lines        | 229, 240, 253, 562 |
| Complexity   | O(A × M × |aliases|) → effectively O(A² × M) where A=attribute count, M=annotation chain depth |
| Fix          | Convert `aliases` from `ArrayList<Method>` to `LinkedHashSet<Method>` |

## Description

`processAliases()` iterates over all annotation attributes (outer `for`) and for each attribute
calls `processAliases(i, aliases)`. Inside that method there is a `while(mapping != null)` loop
(depth M = annotation chain depth) and within that two inner `for` loops over attributes that
each call `aliases.contains(attribute)`.

`aliases` is declared `List<Method> aliases = new ArrayList<>()` — so `contains()` is O(|aliases|)
and can grow to O(A) in the worst case (all attributes are mutual aliases).

`MirrorSets.updateFrom(aliases)` at line 562 also iterates over all attributes and calls
`aliases.contains(attribute)` with the same ArrayList.

### Pattern

```java
// processAliases() - outer loop, AnnotationTypeMapping.java:199
List<Method> aliases = new ArrayList<>();
for (int i = 0; i < this.attributes.size(); i++) {   // O(A)
    aliases.clear();
    aliases.add(this.attributes.get(i));
    collectAliases(aliases);          // aliases grows up to O(A)
    if (aliases.size() > 1) {
        processAliases(i, aliases);   // called with ArrayList
    }
}

// processAliases(int, List) - AnnotationTypeMapping.java:224
while (mapping != null) {             // O(M)
    for (int i = 0; i < mapping.attributes.size(); i++) {   // O(A)
        if (aliases.contains(mapping.attributes.get(i))) {  // O(|aliases|) = O(A) worst case
            ...
        }
    }
}

// MirrorSets.updateFrom - line 562
for (int i = 0; i < attributes.size(); i++) {    // O(A)
    if (aliases.contains(attribute)) {            // O(|aliases|)
```

### Impact

Called during `@AliasFor` annotation metadata processing — runs on every Spring context refresh
and during AOT compilation. Annotations with many aliased attributes (composite annotations,
custom Spring annotations) trigger O(A²×M) processing time.

## Fix

```java
// Before
List<Method> aliases = new ArrayList<>();

// After
// Change both the local variable and the parameter types to LinkedHashSet
// (order is preserved, contains is O(1))
Set<Method> aliases = new LinkedHashSet<>();

// processAliases(int, List<Method>) → processAliases(int, Collection<Method>)
// collectAliases(List<Method>) → collectAliases(Set<Method>)
// addAll calls remain valid; get(j) indexing in collectAliases must use iterator or be refactored
```

The `collectAliases` loop uses `aliases.get(j)` via index, so the simplest fix is to change
`aliases` to `LinkedHashSet<Method>` and update `collectAliases` to use a `List<Method> snapshot`
for the indexed iteration while keeping `aliases` as a Set for O(1) membership:

```java
private void collectAliases(Set<Method> aliases) {
    AnnotationTypeMapping mapping = this;
    while (mapping != null) {
        List<Method> snapshot = new ArrayList<>(aliases);  // indexed iteration only
        for (Method m : snapshot) {
            List<Method> additional = mapping.aliasedBy.get(m);
            if (additional != null) {
                aliases.addAll(additional);  // Set.addAll deduplicates, O(1) per add
            }
        }
        mapping = mapping.source;
    }
}
```

## Speedup Estimate

For A=20 aliased attributes, M=5 chain depth: 20 × 5 × 20 = 2000 operations → 20 × 5 × 1 = 100.
**20x speedup** on moderate annotation graphs; larger in frameworks with deep alias chains.
