# UNDF: UNDF-2026-000000508
# pulsar-0004 — PersistentTopic: shadowTopics List.contains() O(S×R) in checkShadowReplication()

## Metadata
- **Project**: Apache Pulsar
- **Component**: `pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentTopic.java`
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Complexity**: O(S × R) → O(R + S) where S = configured shadow topics, R = active shadow replicators

## Location

```
pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentTopic.java
Lines 2127–2155
```

## Defective code

```java
private CompletableFuture<Void> checkShadowReplication() {
    if (CollectionUtils.isEmpty(shadowTopics)) {
        return CompletableFuture.completedFuture(null);
    }
    List<String> configuredShadowTopics = shadowTopics;  // volatile List<String> (line 223)
    // ...
    // Check for replicators to be stopped
    shadowReplicators.forEach((shadowTopic, replicator) -> {
        ((PersistentReplicator) replicator).updateMessageTTL(newMessageTTLInSeconds);
        if (!configuredShadowTopics.contains(shadowTopic)) {  // O(S) List.contains per replicator
            futures.add(removeShadowReplicator(shadowTopic));
        }
    });
    return FutureUtil.waitForAll(futures);
}
```

`shadowTopics` is declared as `private volatile List<String>` (line 223). The `configuredShadowTopics.contains(shadowTopic)` call inside the `shadowReplicators.forEach()` iterates the list linearly for each active replicator.

## Fix

```java
// BEFORE:
List<String> configuredShadowTopics = shadowTopics;

// AFTER:
Set<String> configuredShadowTopics = new HashSet<>(shadowTopics);
```

One-line fix. The `configuredShadowTopics` local is used only for `contains` checks — a `HashSet` is semantically correct and provides O(1) lookup.

## Complexity analysis

| Scenario | Before | After |
|----------|--------|-------|
| S shadow topics, R shadow replicators | O(R × S) | O(R + S) |
| S=50, R=50 | 2,500 ops per topic check | ~100 ops |
| Large shadow-replication deployment | Multiplied across all topics × check frequency | Negligible |

## Notes

`checkShadowReplication()` is called from `checkReplication()`, which is invoked periodically per topic. In deployments with many shadow topics per topic (used for cross-cluster shadow replication of high-throughput topics), the cost compounds at each check interval. The fix is identical in spirit to pulsar-0003 (same method, same root cause, different field).
