## 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

- `lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph.rb` — `add_edge`, `path` method
- `lib/rubygems/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb` — `path_to?`, `_path_to?`
- `lib/rubygems/specification.rb` — `traverse`
- `lib/rubygems/dependency_list.rb` — `dependency_order`, `tsort_each_child`
- `lib/rubygems/resolver.rb` — `resolve`
- `lib/rubygems/dependency_installer.rb` — `resolve_dependencies`
- `bundler/lib/bundler/resolver.rb` — `solve_versions`

### Findings

**molinillo Vertex#_path_to?:** Uses a `visited = new_vertex_set` (Set) accumulator that is passed on every recursive call. Properly prevents diamond re-traversal. O(V) total.

**Specification#traverse:** Uses a `visited = {}` Hash passed to all recursive calls. Additionally guards against self-referential cycles with `trail.any?`. The `visited.key?` check is O(1). CLEAN.

**dependency_list:** Uses Ruby stdlib `tsort` (Tarjan SCC) — correct O(V+E) algorithm. CLEAN.

**resolver.resolve:** Delegates to `Gem::Molinillo::Resolver` which uses Molinillo's dependency graph with proper visitation tracking. CLEAN.

**bundler resolver:** Uses `PubGrub::VersionSolver` for version conflict resolution. No hand-rolled recursive DAG traversal. CLEAN.

### Verdict: CLEAN — no diamond recursion CWE-407 found
