# UNDF: UNDF-2026-000000689
# UNDF: (pending)
# numpy-0001: stack_arrays — seen=[] list dedup O(A×F²) field-name tracking

## CWE-407 — Algorithmic Complexity: O(A×F²) list-contains in structured-array stacking

| Field | Value |
|-------|-------|
| ID | numpy-0001 |
| Severity | MEDIUM |
| Ecosystem | numpy |
| Package | `numpy` |
| File | `numpy/lib/recfunctions.py` |
| Lines | 1396–1405 |
| Complexity | O(A×F²) on A arrays with F fields each |
| Hot path | `stack_arrays()` — stacking structured/record arrays |

## Background

`stack_arrays(arrays)` superposes structured arrays field by field, building a
merged output array.  It tracks which field names have already been seen in order
to handle anonymous arrays (arrays without named fields) by generating synthetic
names like `f0`, `f1`, …

## Defect

```python
# numpy/lib/recfunctions.py  lines 1394–1405
output = ma.masked_all((np.sum(nrecords),), newdescr)
offset = np.cumsum(np.r_[0, nrecords])
seen = []                                   # DEFECT: list, not set
for (a, n, i, j) in zip(seqarrays, fldnames, offset[:-1], offset[1:]):
    names = a.dtype.names
    if names is None:
        output[f'f{len(seen)}'][i:j] = a
    else:
        for name in n:
            output[name][i:j] = a[name]
            if name not in seen:            # O(F) list scan each time
                seen.append(name)
```

The outer loop runs A times (once per input array).  The inner loop runs F times
per array.  `if name not in seen` is an O(|seen|) linear scan, so the total work
for field-name dedup is O(A×F²).  The same `seen` list grows across all arrays,
making later checks progressively more expensive.

Note that `stack_arrays` also calls a sibling loop at lines 1377–1383 (the
`newdescr` / `names` list build) with the same O(F²) pattern — see numpy-0002 for
the `join_by` variant.

### When does this matter?

Scientific pipelines that stack many structured arrays (e.g. HDF5 record batches,
FITS tables, structured CSV readers) can pass hundreds of arrays each with dozens
of fields, reaching millions of unnecessary comparisons.

## Complexity table

| Arrays (A) | Fields (F) | list ops | set ops | Speedup |
|-----------|-----------|---------|---------|---------|
| 10 | 50 | ~12,500 | 500 | 25× |
| 50 | 100 | ~250,000 | 5,000 | 50× |
| 100 | 200 | ~2,000,000 | 20,000 | 100× |
| 500 | 500 | ~62,500,000 | 250,000 | 250× |

## Fix

Replace `seen = []` with `seen = set()` and use `in`/`.add()`:

```python
# Fixed
seen = set()                                # FIX: O(1) membership
for (a, n, i, j) in zip(seqarrays, fldnames, offset[:-1], offset[1:]):
    names = a.dtype.names
    if names is None:
        output[f'f{len(seen)}'][i:j] = a
    else:
        for name in n:
            output[name][i:j] = a[name]
            if name not in seen:            # O(1) set probe
                seen.add(name)
```

`set.add()` and `name not in seen` are both O(1) amortised.  The only change is
the data structure; the ordering semantics of `len(seen)` for synthetic name
generation (`f0`, `f1`, …) are preserved because set cardinality is tracked
identically.