## Diamond Recursion Scan — CLEAN (broader scan beyond poetry-0001)

**Scan date:** 2026-03-29
**Pattern:** Recursive DAG traversal without visited set (CWE-407 diamond recursion, O(2^D))

### Files examined

- `src/poetry/puzzle/solver.py` — `depth_first_search()`, `dfs_visit()`, `_aggregate_solved_packages()`
- `src/poetry/puzzle/provider.py` — `complete_package()`, `incompatibilities_for()`
- `src/poetry/mixology/version_solver.py` — `_resolve_conflict()`
- `src/poetry/packages/locker.py` — `locked_packages()`, `_compute_lock_data()`
- `src/poetry/console/commands/show.py` — `_display_tree()` (see poetry-0001)

### Findings

**puzzle/solver.py depth_first_search / dfs_visit():** Explicit `visited: set[DFSNodeID] = set()`
guard. `if node.id in visited: return` at the top of dfs_visit. CLEAN.

**mixology/version_solver.py:** Uses the Pubgrub algorithm (backtracking SAT-style solver).
No recursive graph walk — operates on incompatibility sets with memoized partial assignments.
CLEAN.

**packages/locker.py:** Iterative dict construction from lock data. No recursive graph walk.
CLEAN.

**show.py _display_tree():** See poetry-0001. The shared-state bug prevents O(2^D) diamond
blowup (accidental guard), but introduces false-positive cycle detection. The O(N) list
membership is the primary CWE-407 finding.

### Verdict: CLEAN for diamond recursion O(2^D) — one O(N²) list-membership defect (poetry-0001)
