rustc — CWE-407 Analysis
=========================

.. contents:: :local:

Overview
--------

``rustc`` is the Rust compiler. It performs exhaustiveness checking for match expressions,
trait specialization graph construction, and type inference. Two CWE-407 defect sites were
found in the middle-end compiler passes. Both are unpatched.

Defect Sites
------------

rustc-0001
~~~~~~~~~~

**File:** ``compiler/rustc_middle/src/ty/inhabited_predicate.rs:109,127``

**Pattern:**

.. code-block:: rust

   // Match exhaustiveness — SmallVec membership test during inhabited-predicate DFS
   fn visit_inhabited(
       &self,
       tcx: TyCtxt<'tcx>,
       stack: &mut SmallVec<[Ty<'tcx>; 4]>,
   ) -> InhabitedPredicate<'tcx> {
       if stack.contains(&self) {   // O(d) — SmallVec::contains is linear scan
           return InhabitedPredicate::True;
       }
       stack.push(self);
       // ... recurse
       stack.pop();
   }

**Why this is O(n):** ``SmallVec::contains`` is a linear scan regardless of the SmallVec
being stack- or heap-allocated; called once per recursive frame.

**Complexity:** ``O(d²)`` where d = recursion depth (number of types on the stack)

**Patch:**

.. code-block:: rust

   use rustc_data_structures::fx::FxHashSet;

   fn visit_inhabited(
       &self,
       tcx: TyCtxt<'tcx>,
       stack: &mut FxHashSet<Ty<'tcx>>,
   ) -> InhabitedPredicate<'tcx> {
       if !stack.insert(self) {   // O(1) — insert returns false if already present
           return InhabitedPredicate::True;
       }
       // ... recurse
       stack.remove(&self);
   }

**Data structure change:** ``SmallVec<[Ty; 4]>`` + ``contains`` → ``FxHashSet<Ty>`` + ``insert``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let d = recursion depth. ``SmallVec::contains`` scans up to d elements: O(d) per call, O(d²)
total. ``FxHashSet::insert`` returns a boolean indicating first insertion: O(1), O(d) total.
QED.

References
----------

* Defect ticket: ``tools/tickets/defects/rustc-0001.md``

rustc-0002
~~~~~~~~~~

**File:** ``compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs:69``

**Pattern:**

.. code-block:: rust

   // Specialization graph construction — Vec::position for node lookup
   fn ancestors(
       tcx: TyCtxt<'tcx>,
       trait_def_id: DefId,
       start: DefId,
   ) -> Ancestors<'tcx> {
       let mut visited: Vec<DefId> = Vec::new();
       // ...
       loop {
           if visited.iter().position(|&v| v == current).is_some() {
               // cycle detected — O(V) per check
               break;
           }
           visited.push(current);
           // ...
       }
   }

**Why this is O(n):** ``Vec::position`` is a linear scan; called on every iteration of the
specialization-graph traversal loop.

**Complexity:** ``O(V²)`` where V = number of specialization ancestors

**Patch:**

.. code-block:: rust

   use rustc_data_structures::fx::FxHashSet;

   fn ancestors(...) -> Ancestors<'tcx> {
       let mut visited: FxHashSet<DefId> = FxHashSet::default();
       loop {
           if !visited.insert(current) {   // O(1)
               break;
           }
           // ...
       }
   }

**Data structure change:** ``Vec<DefId>`` + ``position`` → ``FxHashSet<DefId>`` + ``insert``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let V = specialization ancestors. Each iteration calls ``Vec::position`` on a vec of up to V
elements: O(V). With V iterations: O(V²). ``FxHashSet::insert`` is O(1) amortized: O(V) total.
QED.

References
----------

* Defect ticket: ``tools/tickets/defects/rustc-0002.md``
