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
26 lines
1.3 KiB
Markdown
26 lines
1.3 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
|
||
|
||
- `pkg/chart/v2/util/dependencies.go` — `processDependencyEnabled`, `processDependencyImportValues`
|
||
- `internal/chart/v3/util/dependencies.go` — same (v3 equivalent)
|
||
- `pkg/chart/v2/lint/rules/dependencies.go` — `validateDependenciesUnique`
|
||
- `pkg/engine/engine.go` — `recAllTpls`, `allTemplates`
|
||
- `pkg/action/install.go` — `CheckDependencies`
|
||
|
||
### Findings
|
||
|
||
**processDependencyEnabled:** Recurses into sub-charts. However, Helm charts embed their dependencies as nested tarballs — the dependency tree is structurally a tree (each chart is a separate embedded copy), not a DAG with shared references. Diamond graphs are impossible in this structure. CLEAN.
|
||
|
||
**recAllTpls:** Recurses through `accessor.Dependencies()` — same tree structure argument applies. No shared nodes, no diamond. CLEAN.
|
||
|
||
**CheckDependencies:** O(R×D) nested loop — no recursion. CLEAN.
|
||
|
||
**validateDependenciesUnique:** Iterates flat arrays, no recursion. CLEAN.
|
||
|
||
Note: `helm-0001` through `helm-0003` cover pre-existing CWE-407 defects in release filtering and repo update operations.
|
||
|
||
### Verdict: CLEAN — no diamond recursion CWE-407 found (Helm chart structure is a tree, not a DAG)
|