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
33 lines
2.7 KiB
Markdown
33 lines
2.7 KiB
Markdown
## 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 traversal
|
|
- `Source/cmComputeTargetDepends.cxx` — inter-target dependency graph computation
|
|
- `Source/cmComputeComponentGraph.cxx` — Tarjan SCC implementation
|
|
- `Source/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.
|
|
|
|
### Verdict: CLEAN — no diamond recursion CWE-407 found
|