russell@unturf.com
a629bd0bbf
New defects (all PASS): - exim-0001: same_hosts() MX-segment O(H²) → AVL set O(H log H), 10.5x at H=20 - minecraft-0001: DependencySorter.isCyclic no visited set O(E^D) → O(E), 342,000x at D=24 - minecraft-0002: PistonStructureResolver toPush ArrayList O(N²) → HashSet O(N) - minecraft-0003: RedstoneWireEvaluator Deque.contains O(N²) → HashSet O(N) - minecraft-0004: MoveThroughVillageGoal visited List O(N²) → HashSet O(N) - mpich-0001: group_lpid_to_rank O(N²) → HashMap O(N), 313x at N=1000 - ompi-0001: group_overlap process-name scan O(N×M) → HashMap O(N+M), 2048x - pcl-0001: RegionGrowing::getSegmentFromPoint O(C×S) → point_labels[] O(1), 50000x CLEAN confirmed: esbuild, express, koa, ktor, lucene, mpich-recvq, ompi-startup, prosody, roda, rust/rustc-wave2, signal-server, solana, wiredtiger, wireguard-tools, linux-kernel (pointer to linux/)
82 lines
4.5 KiB
Markdown
82 lines
4.5 KiB
Markdown
# rustc CWE-407 Wave-2 Deep Scan — CLEAN (beyond 0001–0004)
|
||
|
||
**Scan date:** 2026-03-29
|
||
**Target:** rust-lang/rust (rustc compiler)
|
||
**Prior defects:** rustc-0001 (evalstack swap-remove), rustc-0002 (evalstack),
|
||
rustc-0003 (is_target_feature_call_safe Vec scan), rustc-0004 (finalize_imports
|
||
ambiguity_errors Vec scan)
|
||
**Crates scanned this wave:**
|
||
- `compiler/rustc_resolve/src/` (imports.rs, late.rs, macros.rs, build_reduced_graph.rs,
|
||
rustdoc.rs, check_unused.rs, diagnostics.rs, ident.rs)
|
||
- `compiler/rustc_trait_selection/src/` (select/mod.rs, select/candidate_assembly.rs,
|
||
solve/fulfill.rs, dyn_compatibility.rs)
|
||
- `compiler/rustc_borrowck/src/` (diagnostics/conflict_errors.rs, polonius/constraints.rs,
|
||
diagnostics/outlives_suggestion.rs)
|
||
- `compiler/rustc_middle/src/` (dep_graph/graph.rs, ty/inhabitedness/inhabited_predicate.rs,
|
||
ty/mod.rs, ty/print/pretty.rs)
|
||
- `compiler/rustc_passes/src/dead.rs`
|
||
- `compiler/rustc_hir_typeck/src/` (fn_ctxt/arg_matrix.rs, fn_ctxt/checks.rs, pat.rs,
|
||
fallback.rs, coercion.rs)
|
||
- `compiler/rustc_ast_lowering/src/` (expr.rs, asm.rs, delegation.rs)
|
||
- `compiler/rustc_codegen_ssa/src/` (target_features.rs, mir/mod.rs, back/link.rs)
|
||
|
||
## Findings
|
||
|
||
### rustc_passes/dead.rs — ignore_variant_stack: Vec<DefId>
|
||
`ignore_variant_stack.contains(&ctor_def_id)` at lines 141, 153. This Vec is a
|
||
push/truncate scope stack that holds variants from a single match arm's pattern
|
||
(`pat.necessary_variants()`). It is bounded by the nesting depth of the match arm
|
||
being analyzed, not by the total number of enum variants in the crate. In practice
|
||
it never exceeds a handful of entries. Not a CWE-407 defect.
|
||
|
||
### rustc_middle/dep_graph/graph.rs — TaskDeps::reads: EdgesVec
|
||
`task_deps.reads.contains(&dep_node_index)` at line 494. This is an intentional
|
||
deliberate hybrid: the code uses a linear scan only for `reads.len() <= LINEAR_SCAN_MAX`
|
||
(= 16), then switches to a `read_set: FxHashSet` for larger lists. The constant
|
||
LINEAR_SCAN_MAX is chosen so the linear scan is cheaper than a hash lookup for small
|
||
sizes. Hybrid dedup is a known optimization pattern, not a defect.
|
||
|
||
### rustc_middle/ty/inhabitedness/inhabited_predicate.rs — eval_stack: SmallVec<[Ty; 1]>
|
||
`eval_stack.contains(&t)` at lines 109, 127. This is a DFS cycle-detection stack
|
||
during type inhabitedness checking. The stack depth equals the type nesting depth,
|
||
which is bounded in well-formed code. Not a hot path.
|
||
|
||
### rustc_hir_typeck/fn_ctxt/arg_matrix.rs — stack: Vec<usize>
|
||
`stack.contains(&j)` at line 270, inside a cycle-detection loop over argument
|
||
compatibility. The stack grows to the length of the compatibility cycle (at most
|
||
the number of mismatched arguments). This only runs when argument reordering is
|
||
diagnosed, which is an error-reporting path. Not a hot compilation path.
|
||
|
||
### rustc_hir_typeck/pat.rs — variant_field_idents: Vec<Ident>
|
||
`variant_field_idents.contains(&field.ident)` at line 2409, called inside
|
||
`.map()` over `fields.iter()`. This is O(F×V) where F = fields in pattern and
|
||
V = fields in variant. However, this function (`struct_fn_arg_suggestions`) is
|
||
only called to generate a diagnostic suggestion string when a struct pattern is
|
||
wrong. Pure error-reporting path.
|
||
|
||
### rustc_ast_lowering/expr.rs — legacy_args_idx: &[usize]
|
||
`legacy_args_idx.contains(&idx)` at lines 452, 473. Called inside loops over
|
||
`args.iter()`. Only runs inside `invalid_expr_error`, which is only called when a
|
||
legacy const-generic argument error is emitted. Error-reporting path only.
|
||
|
||
### rustc_codegen_ssa/target_features.rs — RUSTC_SPECIFIC_FEATURES: &[&str]
|
||
`RUSTC_SPECIFIC_FEATURES.contains(&base_feature)` at lines 172, 179. The
|
||
`RUSTC_SPECIFIC_FEATURES` slice is a small compile-time constant (currently 3 entries:
|
||
`crt-static`, `relocation-model`, `code-model`). O(1) in practice.
|
||
|
||
### All other contains() calls in scanned crates
|
||
Resolved to `FxHashSet`, `FxIndexSet`, `BTreeSet`, `HashSet`, bitset types
|
||
(`LocalDefIdSet`, `BitSet`), range checks, or flag bitmask tests (`contains()` on
|
||
`CodegenFnAttrFlags` is a bitmask AND, O(1)). All O(1).
|
||
|
||
### Previously-found hot-path patterns (rustc-0001 through rustc-0004)
|
||
These defects were found and patched in prior scans. No recurrence detected:
|
||
- `evalstack` in `rustc_const_eval` now uses swap_remove instead of index-walking
|
||
- `is_target_feature_call_safe` now uses `HashSet`
|
||
- `finalize_imports` ambiguity_errors scan now uses a counter
|
||
|
||
## Conclusion
|
||
|
||
No new CWE-407 defects found beyond rustc-0001 through rustc-0004. All remaining
|
||
`contains()` calls in the scanned hot-path crates use hash-backed structures, bitmask
|
||
checks, or are in bounded/error-only paths.
|