# UNDF: UNDF-2026-000000385
# elasticsearch-003: XContentHelper O(n²) mergedList.contains in list dedup merge

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: Mapping merge / template merge — called on every index mapping update and template resolution

## Location
`server/src/main/java/org/elasticsearch/common/xcontent/XContentHelper.java:507-509`

## Defect

```java
// if both are lists, simply combine them, first the second list's values, then the first's
// just make sure not to add the same value twice
List<Object> mergedList = new ArrayList<>(listToMerge);

for (Object o : baseList) {
    if (mergedList.contains(o) == false) {   // O(mergedList.size()) per iteration
        mergedList.add(o);
    }
}
first.put(toMergeEntry.getKey(), mergedList);
```

`mergedList` is an `ArrayList<Object>`. Its `contains()` is a linear O(N) scan.
The outer `for` loop runs `baseList.size()` times, giving O(baseList × mergedList) = **O(n²)**.

This code path is executed during:
- Index mapping merges (every `put mapping` or dynamic field discovery)
- Composable index template resolution (every index creation)
- XContent document merges in pipelines and cluster state updates

## Impact
- For lists of length N=100: ~10,000 operations instead of ~200
- Mapping merges on indices with many array-typed fields hit this for every field update
- Template resolution with large component template lists scales quadratically

## Fix
Replace `mergedList` with a `LinkedHashSet` to preserve insertion order while giving O(1) membership tests:

```java
LinkedHashSet<Object> merged = new LinkedHashSet<>(listToMerge);
for (Object o : baseList) {
    merged.add(o);   // no-op if already present — O(1)
}
first.put(toMergeEntry.getKey(), new ArrayList<>(merged));
```

Or equivalently, build a dedup set upfront:

```java
Set<Object> seen = new HashSet<>(listToMerge);
List<Object> mergedList = new ArrayList<>(listToMerge);
for (Object o : baseList) {
    if (seen.add(o)) {
        mergedList.add(o);
    }
}
first.put(toMergeEntry.getKey(), mergedList);
```

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| Membership test | O(n) ArrayList.contains | O(1) HashSet.contains |
| Full merge | O(n²) | O(n) |
| Speedup at n=1000 | — | ~1000× |

## Status
PATCHED (unit test confirms behaviour, see `defects/elasticsearch/unit/XContentHelperMergeContains.java`)
