russell@unturf.com
3986d8dc50
New diamond recursion defects (O(2^D) → O(N)): - godot-0009: Font::_is_cyclic no visited set — CJK fallback diamond, 2648x at F=4,D=8 - godot-0010: Font::_update_rids_fb no visited set — duplicate RIDs + O(N^2) hot path - meson-0002: get_internal_static_libraries_recurse link_whole guard missing — 132x at D=10 - typescript-0003: hasBaseType inner check() no visited set — 1024x at D=10; hot on instanceof New O(N²) defects: - typeorm-0004: SubjectTopologicalSorter Array.indexOf dedup — 200x at N=400 - typeorm-0005: DepGraph.createDFS result.indexOf + addDependency edge dedup — 300x at N=600 CLEAN confirmed (diamond recursion sweep): bazel, cargo, cmake, composer, dgl, diesel, doctrine-orm, efcore, helm, mybatis, networkx-deeper, ninja, npm-arborist, peewee, pip, rubygems, seaorm, sqlalchemy, swift UNDF: 571→578 assigned; MOAD count: 629→635
1.4 KiB
Diamond Recursion Scan — CLEAN
Scan date: 2026-03-29 Pattern: Recursive cycle/dependency check without visited set (CWE-407 diamond recursion, O(2^D))
Files examined
src/pip/_internal/resolution/resolvelib/resolver.py—get_topological_weights,visitsrc/pip/_internal/resolution/legacy/resolver.py—get_installation_order,schedulesrc/pip/_internal/resolution/resolvelib/candidates.py—iter_dependencies
Findings
legacy resolver schedule(): ordered_reqs.add(req) is called BEFORE the recursive call into dependencies. This means any node that is already scheduled (in the set) returns immediately on the next visit. The set check is O(1). No diamond blowup. CLEAN.
resolvelib get_topological_weights / visit(): Uses a path set (not list) to guard against cycle re-entry — if node in path: return. Additionally limits each node to 5 visits via len(cur_weights) >= 5. The 5-visit limit was added as a guard (issue #10557) to prevent O(2^D) blowup on pathologically connected graphs. The underlying pattern was the diamond recursion defect; the fix is a band-aid that caps visits at 5 per node, making it O(5N) = O(N). Current code is effectively mitigated.
Note: pip-0001 covers a pre-existing CWE-407 defect in the legacy resolver's cache support index.