russell@unturf.com
9ef437a348
ShowCommand._display_tree() uses a list for packages_in_tree, making every `dep.name in current_tree` check O(N). For a project with 500 packages the total membership-test cost is O(N²) ≈ 250,000 ops vs O(N) = 500 with a set. Also fixes shared-state correctness bug: list is passed by reference causing sibling branches to falsely report diamond dependencies as cycles. Fix: set + per-branch set-union copy; 16-31x speedup measured. CLEAN markers added for setuptools and celery (diamond recursion). pip, django, poetry solver already CLEAN (prior or current scan).
31 lines
1.3 KiB
Markdown
31 lines
1.3 KiB
Markdown
## Diamond Recursion Scan — CLEAN (diamond recursion specific)
|
|
|
|
**Scan date:** 2026-03-29
|
|
**Pattern:** Recursive DAG traversal without visited set (CWE-407 diamond recursion, O(2^D))
|
|
|
|
### Files examined
|
|
|
|
- `celery/canvas.py` — `stamp()`, `stamp_links()`, `flatten_links()`, `freeze()`, `_display_tree()`
|
|
|
|
### Findings
|
|
|
|
**Signature.stamp() / stamp_links():** Recurses through `link` callbacks. Links form a
|
|
**tree** (callback chain), not a DAG — a given Signature object cannot appear at multiple
|
|
positions in the tree without being explicitly constructed that way by the user.
|
|
No visited guard needed for the normal use case.
|
|
|
|
**chord.freeze():** Contains an explicit `seen = set()` guard (line 2097) when walking
|
|
`node.parent` chain to detect recursive result parents. CLEAN.
|
|
|
|
**chain.stamp():** Iterates over `self.tasks` linearly. CLEAN.
|
|
|
|
**group.stamp():** Iterates over `self.tasks` linearly. CLEAN.
|
|
|
|
**flatten_links():** Returns recursive list of link callbacks. Link chains are trees
|
|
(not DAGs), so no diamond blowup. CLEAN.
|
|
|
|
Note: celery-0001 covers `ResultSet` O(N²) list membership (different pattern).
|
|
celery-0002 covers `append_to_list_option` O(N) list membership (different pattern).
|
|
Neither is diamond recursion.
|
|
|
|
### Verdict: CLEAN — no diamond recursion CWE-407 found (canvas traversals are tree-structured)
|