# UNDF: UNDF-2026-000000361
# cel-0001: canvas.py append_to_list_option O(N²) list membership in chain/chord build loops

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** ~Nx at N=500 tasks/callbacks (verified by unit test)
**Target:** Celery (celery/celery)
**Files:**
- `celery/canvas.py:702-706` — `Signature.append_to_list_option`: list-based deduplication
- `celery/canvas.py:1029-1033` — `Chain._clone_tasks`: calls `link`/`link_error` inside loops
- `celery/canvas.py:1260-1262` — `Chain.prepare_steps`: calls `link_error` inside task loop

## Description

`append_to_list_option` deduplicates options (link callbacks, link_error callbacks)
using a plain list membership test:

```python
def append_to_list_option(self, key, value):
    items = self._with_list_option(key)   # returns self.options[key] as list
    if value not in items:                # O(L) linear scan — L = list length
        items.append(value)
    return value
```

This method is called in two hot loops during chain construction:

**Loop 1** — `_clone_tasks` (canvas.py:1031-1033):
```python
for sig in maybe_list(self.options.get('link_error')) or []:
    for task in tasks:                    # O(T) outer loop
        task.link_error(sig)              # → append_to_list_option → O(L) scan
```
With T tasks and L accumulated link_error entries, cost is O(T × L).

**Loop 2** — `prepare_steps` (canvas.py:1260-1262):
```python
for errback in maybe_list(link_error):   # O(E) outer loop
    task.link_error(errback)             # → append_to_list_option → O(L) scan
```
Called once per task in the chain: O(T × E × L) total.

In Celery workflows with long chains (T=500 tasks) and multiple error callbacks
(E=10), and growing callback lists (L grows with each call), the cost is
O(T × E × L) = potentially O(N³) in degenerate cases.

## Root Cause

`_with_list_option` returns a plain Python `list` stored in `self.options`. The
`not in` deduplication guard is O(L) per call. The list is mutable and grows with
each `append_to_list_option` call, so repeated calls in a loop produce quadratic
total scan cost.

Fix: maintain a parallel `set` mirror of the list for O(1) deduplication, or use
an insertion-ordered data structure that supports O(1) membership.

## Patch

See `patch/cel-0001-canvas-append-list-option-membership.patch`

## Complexity Before

`value not in items` (list): **O(L)**
Total in chain build loop: **O(T × E × L)** — approaches O(N³) for long chains

## Complexity After

`value not in items_set` (set): **O(1)** average
Total: **O(T × E)**

## Reproduction

```
cd defects/celery/unit && javac -d . CeleryTest.java && java -ea unit.CeleryTest
```
