47 lines
2.3 KiB
Markdown
47 lines
2.3 KiB
Markdown
# 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.
|