# UNDF: UNDF-2026-000000295
# UNDF: (pending)
# spring-0001: BeanFactoryUtils.mergeNamesWithParent — O(P×R) ArrayList.contains inside loop

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

| Field | Value |
|-------|-------|
| ID | spring-0001 |
| Severity | MEDIUM |
| Ecosystem | spring-framework |
| Package | org.springframework.beans.factory |
| File | `spring-beans/src/main/java/org/springframework/beans/factory/BeanFactoryUtils.java` |
| Lines | 525–532 |
| Complexity | O(P×R) |
| Hot path | bean type resolution with hierarchical ApplicationContext |

## Defect

`BeanFactoryUtils.mergeNamesWithParent()` is called by
`beanNamesForTypeIncludingAncestors()` and related methods to merge bean name
lists from parent and child application contexts. The `merged` variable is an
`ArrayList<String>`. For each of the P entries in `parentResult`, the code calls
`merged.contains(beanName)` — an O(R) linear scan where R is the number of
already-added names. Total cost O(P×R).

```java
// BeanFactoryUtils.java line 521-532
private static String[] mergeNamesWithParent(String[] result, String[] parentResult,
        HierarchicalBeanFactory hbf) {
    if (parentResult.length == 0) {
        return result;
    }
    List<String> merged = new ArrayList<>(result.length + parentResult.length);
    merged.addAll(Arrays.asList(result));
    for (String beanName : parentResult) {
        if (!merged.contains(beanName) && !hbf.containsLocalBean(beanName)) {
            //      ^^^^^^^^ O(R) per iteration → O(P×R) total
            merged.add(beanName);
        }
    }
    return StringUtils.toStringArray(merged);
}
```

This method is called from `getBeanNamesForType()`, `beanNamesForAnnotationIncludingAncestors()`,
and similar utility methods which can be called at runtime (e.g., during dependency injection,
AOP proxy creation, and Spring Boot auto-configuration) with deep ApplicationContext hierarchies.

## Fix

Use a `LinkedHashSet` to preserve insertion order while providing O(1) membership tests,
or build a `HashSet` for the dedup check:

```java
private static String[] mergeNamesWithParent(String[] result, String[] parentResult,
        HierarchicalBeanFactory hbf) {
    if (parentResult.length == 0) {
        return result;
    }
    Set<String> seen = new HashSet<>(Arrays.asList(result));
    List<String> merged = new ArrayList<>(result.length + parentResult.length);
    merged.addAll(Arrays.asList(result));
    for (String beanName : parentResult) {
        if (!seen.contains(beanName) && !hbf.containsLocalBean(beanName)) {
            seen.add(beanName);
            merged.add(beanName);
        }
    }
    return StringUtils.toStringArray(merged);
}
```

Alternatively, use `LinkedHashSet` directly:

```java
private static String[] mergeNamesWithParent(String[] result, String[] parentResult,
        HierarchicalBeanFactory hbf) {
    if (parentResult.length == 0) {
        return result;
    }
    Set<String> merged = new LinkedHashSet<>(Arrays.asList(result));
    for (String beanName : parentResult) {
        if (!merged.contains(beanName) && !hbf.containsLocalBean(beanName)) {
            merged.add(beanName);
        }
    }
    return StringUtils.toStringArray(merged);
}
```

## Speedup

| R (result count) | P (parentResult count) | Before (ops) | After (ops) | Speedup |
|-----------------|------------------------|-------------|-------------|---------|
| 100 | 100 | 10,000 | 100 | 100× |
| 500 | 500 | 250,000 | 500 | 500× |
| 1,000 | 1,000 | 1,000,000 | 1,000 | 1,000× |

Applications with large numbers of beans and deep ApplicationContext hierarchies
(common in Spring Boot multi-module applications and OSGi container deployments)
are most affected.
