# UNDF: UNDF-2026-000000690
# UNDF: (pending)
# numpy-0002: join_by — names list rebuilt inside loop + .index() O(F²)

## CWE-407 — Algorithmic Complexity: O(F²) list rebuild + linear search in join_by

| Field | Value |
|-------|-------|
| ID | numpy-0002 |
| Severity | MEDIUM |
| Ecosystem | numpy |
| Package | `numpy` |
| File | `numpy/lib/recfunctions.py` |
| Lines | 1602–1628, 1636–1648 |
| Complexity | O(F²) on F total fields across the two joined arrays |
| Hot path | `join_by()` — join two structured arrays on a key field |

## Background

`join_by(key, r1, r2)` joins two NumPy structured arrays on one or more key
fields, analogous to a SQL join.  It constructs the output dtype by iterating
over fields in `r2` and checking for collisions with fields already in `ndtype`.

## Defect — site 1: names list rebuild inside loop

```python
# numpy/lib/recfunctions.py  lines 1606–1628
# Add the fields from r2
for fname, fdtype in _get_fieldspec(r2.dtype):
    # we need to rebuild this list every time         ← comment in source
    names = [name for name, dtype in ndtype]          # DEFECT: O(F) rebuild per iteration
    try:
        nameidx = names.index(fname)                  # DEFECT: O(F) linear search
    except ValueError:
        ndtype.append((fname, fdtype))
    else:
        # collision handling ...
        ndtype[nameidx:nameidx + 1] = [...]
```

For F2 fields in r2 and F1 fields already in `ndtype`, the rebuild + `.index()`
costs O(F1 + F2) per iteration, totalling O(F2 × (F1 + F2)) = O(F²).

The comment "we need to rebuild this list every time" was added because collision
handling mutates `ndtype` (splice at `nameidx`), but this does not require a full
list reconstruction — an O(1) dict/index update suffices.

## Defect — site 2: tuple `not in` scan in output assembly

```python
# numpy/lib/recfunctions.py  lines 1636–1648
names = output.dtype.names      # tuple of all output field names
for f in r1names:
    selected = s1[f]
    if f not in names or ...:   # O(|names|) tuple scan
        f += r1postfix
    ...
for f in r2names:
    selected = s2[f]
    if f not in names or ...:   # O(|names|) tuple scan
        f += r2postfix
    ...
```

`output.dtype.names` is a tuple; `f not in names` scans it linearly.  Called for
every field in both arrays: O((F1+F2)×F_total).

## Complexity table

| F (total fields) | list ops | dict ops | Speedup |
|-----------------|---------|---------|---------|
| 50 | ~2,500 | 50 | 50× |
| 200 | ~40,000 | 200 | 200× |
| 500 | ~250,000 | 500 | 500× |
| 1,000 | ~1,000,000 | 1,000 | 1,000× |

## Fix

Build a name-to-index dict alongside `ndtype` and keep it updated:

```python
# Fixed
ndtype = _get_fieldspec(r1k.dtype)

# Add r1 fields
for fname, fdtype in _get_fieldspec(r1.dtype):
    if fname not in key:
        ndtype.append((fname, fdtype))

# Build index dict once — O(F) total
name_to_idx = {name: i for i, (name, _) in enumerate(ndtype)}

# Add r2 fields using O(1) dict lookup
for fname, fdtype in _get_fieldspec(r2.dtype):
    if fname not in name_to_idx:                 # O(1)
        name_to_idx[fname] = len(ndtype)
        ndtype.append((fname, fdtype))
    else:
        nameidx = name_to_idx[fname]
        _, cdtype = ndtype[nameidx]
        if fname in key:
            ndtype[nameidx] = (fname, max(fdtype, cdtype))
            name_to_idx[fname] = nameidx          # unchanged
        else:
            ndtype[nameidx:nameidx + 1] = [
                (fname + r1postfix, cdtype),
                (fname + r2postfix, fdtype)
            ]
            # Rebuild index for names shifted by the splice — O(F) once
            name_to_idx = {n: i for i, (n, _) in enumerate(ndtype)}

# Site 2: convert output dtype names tuple to set once
names_set = set(output.dtype.names)              # O(F) once
for f in r1names:
    if f not in names_set or ...:                # O(1)
        f += r1postfix
    ...
for f in r2names:
    if f not in names_set or ...:                # O(1)
        f += r2postfix
    ...
```
