russell@unturf.com
7491349edc
bullet3-0001: btGhostObject::addOverlappingObjectInternal O(N²) linear dedup per broadphase step — even carries "too slow" self-admission comment (HIGH) bullet3-0002: btSoftRigidCollisionAlgorithm::processCollision O(C×D) per frame on m_collisionDisabledObjects plain array (MEDIUM) allegro5: CLEAN (vector_contains only on non-hot setup paths) box2d: CLEAN (v3 rewrite uses b2HashSet throughout) dry: CLEAN (HashSet/HashMap on all hot dedup paths)
81 lines
2.8 KiB
Markdown
81 lines
2.8 KiB
Markdown
# 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).
|