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
2.7 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
Source/cmGeneratorExpressionDAGChecker.cxx/.h— generator expression DAG traversalSource/cmComputeTargetDepends.cxx— inter-target dependency graph computationSource/cmComputeComponentGraph.cxx— Tarjan SCC implementationSource/cmComputeLinkDepends.cxx— link dependency ordering (VisitComponent,VisitEntry)Source/cmOrderDirectories.cxx— directory ordering DFS (VisitDirectory)Source/cmGlobalGhsMultiGenerator.cxx— GHS target topological sort (VisitTarget)Source/cmCMakePresetsGraph.cxx— preset inheritance cycle detection (VisitPreset)Source/cmFindPackageCommand.cxx—FindPackageDependencies, transitive CPS package deps
Findings
cmGeneratorExpressionDAGChecker: Uses a parent-chain walk via linked Parent pointers to detect cycles. Each cmGeneratorExpressionDAGChecker instance carries a pointer to its parent, and CheckGraph() walks the chain linearly. This is O(depth) for cycle detection, not recursive — CLEAN. The Seen map on Top prevents duplicate transitive property evaluation.
cmComputeTargetDepends: Uses Tarjan's SCC algorithm (cmComputeComponentGraph) for dependency analysis — proper O(V+E) algorithm, no naive recursive reachability. CollectSideEffectsForTarget uses std::set<size_t> visited passed by reference. CLEAN.
cmComputeLinkDepends: VisitComponent uses ComponentVisited[] array (indexed by component ID) as visited guard; checks before recursing. VisitEntry tracks component state. CLEAN.
cmOrderDirectories: VisitDirectory uses DirectoryVisited[] array indexed by node ID; checks and marks before recursing into neighbors. CLEAN.
cmGlobalGhsMultiGenerator::VisitTarget: Uses temp (in-progress) and perm (completed) std::set pairs for proper topological sort. CLEAN.
cmCMakePresetsGraph VisitPreset: Uses std::map<std::string, CycleStatus> with three states (Unvisited/InProgress/Verified) — standard DFS coloring. CLEAN.
cmFindPackageCommand::FindPackageDependencies: Processes CPS-format transitive dependencies by creating new cmFindPackageCommand instances for each dep. Uses global Makefile state (Foo_FOUND, Foo_DIR cache entries) to detect already-processed packages. The _DIR cache variable acts as a memoization key that causes HandlePackageMode to use the cached directory instead of re-searching. Re-reading the config file can occur but is idempotent in practice. Diamond traversal is bounded by CMake's internal include-guard mechanism in config files. CLEAN.