# UNDF: UNDF-2026-000000025
# celery-0001 — O(N²) ResultSet Membership Test in update()/add()

**Severity:** MEDIUM
**Complexity:** O(N²) → O(N)
**CWE:** CWE-407 (Algorithmic Complexity)

## Affected File

| File | Lines | Notes |
|------|-------|-------|
| `celery/result.py` | 597–598, 629–631 | ResultSet.add() and ResultSet.update() |

## Defective Code

### `celery/result.py` line 597–598 — `ResultSet.add()`

```python
def add(self, result):
    if result not in self.results:   # O(N) list scan
        self.results.append(result)
```

### `celery/result.py` line 629–631 — `ResultSet.update()`

```python
def update(self, results):
    """Extend from iterable of results."""
    self.results.extend(r for r in results if r not in self.results)
    #                                          ^^^^^^^^^^^^^^^^^^^
    #                                          O(N) scan per element → O(M*N)
```

`self.results` is a plain `list` (see line 586: `self.results = results`).
Each `r not in self.results` scan is O(N). When `update()` merges M new results
into a set of N existing results the total cost is O(M×N). For chord groups with
thousands of tasks this becomes the bottleneck.

## Root Cause

`ResultSet.results` stores `AsyncResult` objects in a `list`. Deduplication uses
linear scan (`not in list`) instead of a `set`/`dict` lookup.

## Fix

Maintain a parallel `set` for O(1) membership:

```python
def __init__(self, results, app=None, ready_barrier=None, **kwargs):
    self._app = app
    self.results = results
    self._result_ids = {r.id for r in results}   # shadow set for O(1) lookup
    ...

def add(self, result):
    if result.id not in self._result_ids:
        self._result_ids.add(result.id)
        self.results.append(result)
        if self._on_full:
            self._on_full.add(result)

def update(self, results):
    for r in results:
        if r.id not in self._result_ids:
            self._result_ids.add(r.id)
            self.results.append(r)
```

Alternatively, change `results` to an `OrderedDict` keyed by `result.id`.

## Impact

- Affects `group()` / `chord()` workflows with large task counts
- `update()` is O(M×N) → becomes the dominant cost for chord result collection
- At N=M=1000: 1,000,000 comparisons vs 1,000 dict lookups (1000x overhead)
- Backend chord unlock (`celery.chord_unlock`) iterates `header_result.results`
  which triggers the O(N²) path when merging partial completions
