russell@unturf.com 7491349edc game-engines: allegro5/bullet3/box2d/dry CWE-407 scan

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)

2026-03-29 19:50:49 -04:00

2.8 KiB

Raw Permalink Blame History

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.

# 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.

# 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).

2.8 KiB Raw Permalink Blame History Unescape Escape