# UNDF: UNDF-2026-000000480
# numpy-0001: f2py _get_depend_dict — O(n²) linear dedup in dependency resolution

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** >30x at V=500 variables
**Target:** NumPy (numpy/numpy)
**File:** `numpy/f2py/crackfortran.py:2352-2371`

## Description

`_get_depend_dict` builds a transitive dependency list for each Fortran variable.
It accumulates results in `words` (a plain list) and checks membership with
`if w not in words` on every insertion. Because `words` also grows during the
inner loop (via `words.append(w)`), each iteration scans the entire accumulated
list, producing O(V²) operations for V total dependencies.

`_calc_depend_dict` calls `_get_depend_dict` once per variable in `vars`, making
the total complexity O(V²) per variable and O(V³) over the whole module in the
worst case. For large Fortran modules (dozens of inter-dependent variables), this
is the dominant cost in `f2py` processing.

## Root Cause

```python
# numpy/f2py/crackfortran.py:2362-2366
for word in words[:]:                       # outer pass over current words
    for w in deps.get(word, []) \
            or _get_depend_dict(word, vars, deps):
        if w not in words:                  # O(|words|) linear scan per w
            words.append(w)                 # words grows — next iteration scans more
```

`words` is a list. Each `w not in words` scans from index 0. As `words` grows
to length W, the W-th insertion costs O(W). Total cost: O(1+2+…+W) = O(W²).

Fix: maintain a parallel `set` alongside `words` for O(1) membership, keep
the list only for deterministic ordering.

## Patch

```python
def _get_depend_dict(name, vars, deps):
    if name in vars:
        words = list(vars[name].get('depend', []))
        words_set = set(words)                   # O(1) membership

        if '=' in vars[name] and not isstring(vars[name]):
            for word in word_pattern.findall(vars[name]['=']):
                if word not in words_set and word in vars and word != name:
                    words.append(word)
                    words_set.add(word)
        for word in words[:]:
            for w in deps.get(word, []) \
                    or _get_depend_dict(word, vars, deps):
                if w not in words_set:
                    words.append(w)
                    words_set.add(w)
    else:
        outmess(f'_get_depend_dict: no dependence info for {repr(name)}\n')
        words = []
    deps[name] = words
    return words
```

## Complexity Before

`_get_depend_dict`: **O(W²)** per variable (W = transitive dependency count)
`_calc_depend_dict`: **O(V × W²)** total

## Complexity After

`_get_depend_dict`: **O(W)** per variable
`_calc_depend_dict`: **O(V × W)** total

## Reproduction

```
cd defects/numpy/unit && javac -d . *.java && java -ea unit.NumpyTest
```
