# UNDF: UNDF-2026-000000317
# UNDF: (pending)
# spring-0002: DefaultListableBeanFactory.getBeanNamesForAnnotation — O(B×M) ArrayList.contains inside loop

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

| Field | Value |
|-------|-------|
| ID | spring-0002 |
| Severity | MEDIUM |
| Ecosystem | spring-framework |
| Package | org.springframework.beans.factory.support |
| File | `spring-beans/src/main/java/org/springframework/beans/factory/support/DefaultListableBeanFactory.java` |
| Lines | 770–784 |
| Complexity | O(B×M) |
| Hot path | `getBeanNamesForAnnotation()` — called during startup and annotation-driven wiring |

## Defect

`DefaultListableBeanFactory.getBeanNamesForAnnotation()` builds a result list from
two sources: `beanDefinitionNames` and `manualSingletonNames`. For each of the M
entries in `manualSingletonNames` it calls `result.contains(beanName)` where `result`
is an `ArrayList<String>` that has already been populated with up to B entries from
`beanDefinitionNames`. This is O(B×M) — quadratic in total bean count.

```java
// DefaultListableBeanFactory.java line 770-784
public String[] getBeanNamesForAnnotation(Class<? extends Annotation> annotationType) {
    List<String> result = new ArrayList<>();
    for (String beanName : this.beanDefinitionNames) {
        BeanDefinition bd = this.beanDefinitionMap.get(beanName);
        if (bd != null && !bd.isAbstract() && findAnnotationOnBean(beanName, annotationType) != null) {
            result.add(beanName);
        }
    }
    for (String beanName : this.manualSingletonNames) {
        if (!result.contains(beanName) && findAnnotationOnBean(beanName, annotationType) != null) {
            //      ^^^^^^^^ O(B) per iteration → O(B×M) total
            result.add(beanName);
        }
    }
    return StringUtils.toStringArray(result);
}
```

`findAnnotationOnBean()` involves reflection and is itself expensive — but it is only called
after `result.contains()` succeeds (for the negative branch), so the list scan overhead is
paid on every iteration including those that ultimately do nothing.

## Fix

Build a `HashSet` shadow alongside `result` to provide O(1) dedup:

```java
public String[] getBeanNamesForAnnotation(Class<? extends Annotation> annotationType) {
    List<String> result = new ArrayList<>();
    Set<String> seen = new HashSet<>();
    for (String beanName : this.beanDefinitionNames) {
        BeanDefinition bd = this.beanDefinitionMap.get(beanName);
        if (bd != null && !bd.isAbstract() && findAnnotationOnBean(beanName, annotationType) != null) {
            result.add(beanName);
            seen.add(beanName);
        }
    }
    for (String beanName : this.manualSingletonNames) {
        if (!seen.contains(beanName) && findAnnotationOnBean(beanName, annotationType) != null) {
            result.add(beanName);
        }
    }
    return StringUtils.toStringArray(result);
}
```

## Speedup

| B (bean definitions) | M (manual singletons) | Before (ops) | After (ops) | Speedup |
|---------------------|-----------------------|-------------|-------------|---------|
| 500 | 100 | 50,000 | 600 | 83× |
| 1,000 | 500 | 500,000 | 1,500 | 333× |
| 5,000 | 1,000 | 5,000,000 | 6,000 | 833× |

Large Spring Boot applications with hundreds of beans annotated with `@Service`,
`@Component`, `@Controller` etc. will benefit most. `getBeanNamesForAnnotation()`
is called by `getBeansWithAnnotation()`, event publisher detection, and various
Spring Boot auto-configuration processors.
