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
25 lines
1.2 KiB
Markdown
25 lines
1.2 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
|
|
|
|
- `src/main/java/com/google/devtools/build/lib/analysis/` — dependency graph construction
|
|
- `src/main/java/com/google/devtools/build/lib/packages/` — rule/target definitions
|
|
- `src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java` — Skyframe cycle detection
|
|
- `src/main/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/ModExecutor.java` — module dependency traversal
|
|
|
|
### Findings
|
|
|
|
All cycle/reachability checks in Bazel use proper visited-set patterns:
|
|
|
|
1. **Skyframe** — uses incremental evaluation with memoized SkyValues; graph traversal is work-queue-based, not recursive.
|
|
|
|
2. **ModExecutor.notCycle** — uses `parentStack` (HashSet), push/pop per DFS recursion level. This correctly tracks ancestors, preventing cycles and diamond re-visits via the ancestor set.
|
|
|
|
3. **SimpleCycleDetector** — iterative algorithm with explicit sets.
|
|
|
|
4. **ConfiguredRuleClassProvider.dependencyGraph** — uses `Digraph.getTopologicalOrder()` which is a proper topo-sort (no recursive cycle check).
|
|
|
|
### Verdict: CLEAN — no diamond recursion CWE-407 found
|