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.5 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
lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph.rb—add_edge,pathmethodlib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb—path_to?,_path_to?lib/rubygems/specification.rb—traverselib/rubygems/dependency_list.rb—dependency_order,tsort_each_childlib/rubygems/resolver.rb—resolvelib/rubygems/dependency_installer.rb—resolve_dependenciesbundler/lib/bundler/resolver.rb—solve_versions
Findings
molinillo Vertex#_path_to?: Uses a visited = new_vertex_set (Set) accumulator that is passed on every recursive call. Properly prevents diamond re-traversal. O(V) total.
Specification#traverse: Uses a visited = {} Hash passed to all recursive calls. Additionally guards against self-referential cycles with trail.any?. The visited.key? check is O(1). CLEAN.
dependency_list: Uses Ruby stdlib tsort (Tarjan SCC) — correct O(V+E) algorithm. CLEAN.
resolver.resolve: Delegates to Gem::Molinillo::Resolver which uses Molinillo's dependency graph with proper visitation tracking. CLEAN.
bundler resolver: Uses PubGrub::VersionSolver for version conflict resolution. No hand-rolled recursive DAG traversal. CLEAN.