# UNDF: UNDF-2026-000000268
# rustc-0003: CWE-407 — O(C×B) nested Vec<TargetFeature> scan in is_target_feature_call_safe

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity)
**Target:** rust-lang/rust (rustc)
**File:** `compiler/rustc_middle/src/ty/context.rs`
**Line:** 1323–1325
**Status:** PATCHED (unit test PASS)

## Description

`TyCtxt::is_target_feature_call_safe()` checks whether a function call is safe
by verifying that every target feature required by the callee is also enabled in
the caller.  It does this with a nested linear scan:

```rust
callee_features
    .iter()
    .all(|feature| body_features.iter().any(|f| f.name == feature.name))
```

Both `callee_features` and `body_features` are `&[TargetFeature]` slices.  For
each of the C callee features, the body_features slice of length B is scanned
linearly — O(C × B) total.

This function is called from:
- `rustc_mir_build/src/check_unsafety.rs:490` — once per `ExprKind::Call` in
  every MIR body, for every function call whose callee has target features.
- `rustc_middle/src/ty/context.rs:1338` via `adjust_target_feature_sig()` —
  called from `rustc_hir_typeck/src/coercion.rs:1200` and
  `rustc_borrowck/src/type_check/mod.rs:1016`.

Additionally, `check_unsafety.rs:492-505` builds a `missing` `Vec` using the
same O(C × B) nested scan and then calls `sess.target_features.iter().filter(|f|
missing.contains(f))` — a further O(T × M) scan where T is the total platform
feature count.

## Root Cause

x86_64 with AVX-512 support has 60+ named target features.  A function
annotated with many `#[target_feature]` attributes can accumulate C ≈ 20–50
features.  The caller's feature set B is similarly bounded.  At C = B = 50 that
is 2 500 name comparisons per call site per compilation, multiplied by the
number of call expressions in a crate.

The fix is to build a `HashSet<Symbol>` from `body_features` once, then do O(1)
lookups for each callee feature — O(C + B) total instead of O(C × B).

## Patch

```rust
// compiler/rustc_middle/src/ty/context.rs

pub fn is_target_feature_call_safe(
    self,
    callee_features: &[TargetFeature],
    body_features: &[TargetFeature],
) -> bool {
    self.sess.target.options.is_like_wasm || {
        // CWE-407 fix: build a HashSet once for O(1) membership tests.
        let body_set: FxHashSet<Symbol> =
            body_features.iter().map(|f| f.name).collect();
        callee_features.iter().all(|f| body_set.contains(&f.name))
    }
}
```

## Complexity

| Version | Per call | Notes |
|---------|----------|-------|
| Before  | O(C × B) | nested slice scan |
| After   | O(C + B) | one HashSet build + C lookups |

At C = B = 50 the hot ratio is 50×50 / (50+50) = **25×** fewer comparisons.
