# rustc diamond-recursion scan — CLEAN

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

- `compiler/rustc_type_ir/src/elaborate.rs` — `Elaborator`, `supertrait_def_ids`
- `compiler/rustc_type_ir/src/walk.rs` — `TypeWalker`
- `compiler/rustc_trait_selection/src/traits/util.rs` — `expand_trait_aliases`
- `compiler/rustc_trait_selection/src/traits/select/mod.rs` — `evaluate_predicate_recursively`
- `compiler/rustc_hir_analysis/src/collect/predicates_of.rs` — `implied_predicates_with_filter`
- `compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs` — `collect_bounds`

## Findings

### `elaborate.rs` — CLEAN
`Elaborator` uses `visited: HashSet<ty::Binder<I, ty::PredicateKind<I>>>` (line 25).
`supertrait_def_ids` uses `set: HashSet` with `set.insert(data.def_id())` guard (line 328).
Both correctly prevent diamond re-traversal.

### `walk.rs` — CLEAN
`TypeWalker` uses `visited: SsoHashSet<I::GenericArg>` with `self.visited.insert(next)`
guard (line 59). Explicitly documented: "walker only visits each type once."

### `expand_trait_aliases` — CLEAN
Uses BFS `VecDeque` without a visited set on trait aliases, but the re-queuing
is gated by `tcx.is_trait_alias()` only. Normal (non-alias) traits are pushed
directly to `trait_preds` output without re-queuing. Diamond blowup not possible
because `tcx.explicit_super_predicates_of` is a memoized query.

### `select/mod.rs` — CLEAN
`evaluate_predicate_recursively` calls `check_candidate_cache` / `insert_candidate_cache`
— a proper memoization cache keyed on trait predicates. No diamond re-traversal.

### `predicates_of.rs` — CLEAN
All supertrait queries go through `tcx.at(span).explicit_super_predicates_of(bound.def_id())`
which is a memoized `TyCtxt` query. Results are cached per `DefId`. No diamond blowup.

### `hir_ty_lowering/bounds.rs` — CLEAN
`collect_bounds` iterates directly over HIR bounds, no recursion into supertraits.

## Conclusion

No diamond recursion CWE-407 defects in rustc. All supertrait and type traversal
uses either a proper `HashSet`/`SsoHashSet` visited set, or memoized `TyCtxt`
query results that cache per `DefId`. The O(2^D) diamond blowup pattern is not
present in the scanned rustc crates.