# UNDF: UNDF-2026-000000533
# solr-002: ActiveReplicaWatcher O(n²) replicaIds/solrCoreNames.contains in state-change loop

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: ZooKeeper state-change callback — fires on every cluster state update

## Location
`solr/core/src/java/org/apache/solr/cloud/ActiveReplicaWatcher.java:161,169`

## Defect

```java
private final List<String> replicaIds = new ArrayList<>();
private final List<String> solrCoreNames = new ArrayList<>();

// Called on every ZK state change:
for (Slice slice : collectionState.getSlices()) {             // O(shards)
    for (Replica replica : slice.getReplicas()) {             // O(replicas/shard)
        if (replicaIds.contains(replica.getName())) {         // O(replicaIds) = O(n)
            ...
        } else if (solrCoreNames.contains(                    // O(solrCoreNames) = O(n)
                replica.getStr(ZkStateReader.CORE_NAME_PROP))) {
            ...
        }
    }
}
```

Both `replicaIds` and `solrCoreNames` are `ArrayList`. The watcher fires on every
ZooKeeper cluster-state change event (node joins, replica state transitions, shard
splits, etc.). For a collection with S shards × R replicas and N watched IDs:

Total comparisons per event: **O(S × R × N)** for each list independently.

## Fix

Convert to `HashSet` at construction time (the lists are populated once and then only
shrink via `remove()`):

```java
private final Set<String> replicaIds = new HashSet<>();
private final Set<String> solrCoreNames = new HashSet<>();
```

`HashSet.remove()` is also O(1), so the existing removal calls in the loop body
(`replicaIds.remove(replica.getName())`) remain correct and become faster.

The public getters at lines 93/98 return the field directly as `List`; the return type
would need to change to `Collection` or the getter can wrap with `new ArrayList<>(replicaIds)`.

## Complexity
| Metric | Before | After |
|--------|--------|-------|
| contains() | O(N) | O(1) |
| Per ZK event | O(S×R×N) | O(S×R) |
| remove() | O(N) | O(1) |

## Affected Versions
Present in all Solr versions with `ActiveReplicaWatcher` (Solr 7+).
