# UNDF: UNDF-2026-000000039
# UNDF: (pending)
# cpython-0001: unittest.mock.Mock.reset_mock — O(N²) visited list in diamond mock tree traversal

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | cpython-0001 |
| Severity | MEDIUM |
| Ecosystem | cpython |
| Package | unittest.mock |
| File | `Lib/unittest/mock.py` |
| Lines | 638–667 |
| Complexity | O(N²) list membership, O(N) with set |
| Hot path | `mock.reset_mock()` on large/deeply-nested MagicMock trees |

## Defect

`reset_mock` uses a `list` for cycle detection when traversing the mock object
tree. On each recursive call, `id(self) in visited` performs an O(N) linear
scan of all previously visited mock IDs. For a mock tree with N nodes (children
plus return_value chains), the total membership-check cost is O(1+2+…+N) =
O(N²).

MagicMock auto-creates child mocks on attribute access, so test suites that
build large spec-based or deeply-patched mocks can trigger this path. A mock
with 1,000 children (e.g. a module-level patch with many methods) causes ~500k
comparisons instead of ~1k.

```python
# BEFORE — O(N²): list membership O(N) per recursive call
def reset_mock(self, visited=None, *, return_value=False, side_effect=False):
    if visited is None:
        visited = []          # list, not set
    if id(self) in visited:   # O(N) linear scan
        return
    visited.append(id(self))  # O(1) append but scan above is O(N)

    for child in self._mock_children.values():
        if isinstance(child, _SpecState) or child is _deleted:
            continue
        child.reset_mock(visited, ...)   # recurse, visited grows

    ret = self._mock_return_value
    if _is_instance_mock(ret) and ret is not self:
        ret.reset_mock(visited)
```

## Fix

Replace the `list` with a `set`. Integer `id` values hash in O(1) and set
membership is O(1) average.

```python
# AFTER — O(N): set membership O(1) per call
def reset_mock(self, visited=None, *, return_value=False, side_effect=False):
    if visited is None:
        visited = set()        # set, not list
    if id(self) in visited:    # O(1) hash lookup
        return
    visited.add(id(self))      # O(1) insert
    # ... rest unchanged
```

## Speedup

| Mock nodes (N) | Before (ops) | After (ops) | Speedup |
|----------------|--------------|-------------|---------|
| 100 | 5,050 | 100 | 50× |
| 500 | 125,250 | 500 | 250× |
| 1,000 | 500,500 | 1,000 | 500× |
| 2,000 | 2,001,000 | 2,000 | 1,000× |

## Notes

- The same pattern appears in `_mock_check_sig` / other recursive helpers; only
  `reset_mock` is flagged here as the primary confirmed path.
- `id` values are unique integers per live object — set storage is safe.
- No semantic change: cycle detection behaviour is identical.
- Fix applies to CPython main as of depth-1 clone (HEAD ~May 2025).