Rust — CWE-407 Language Analysis
==================================

.. contents:: :local:

Overview
--------

Rust's ``Vec<T>.contains(&x)`` is O(n) — it performs a linear scan using ``PartialEq``. The
``SmallVec`` type from the ``smallvec`` crate (used extensively in ``rustc``) has the same
behavior. The canonical fix is ``HashSet<T>`` from the standard library or ``FxHashSet<T>``
from ``rustc_data_structures::fx`` (used throughout the compiler for performance).

Rust's type system does not prevent O(n) collection operations — ``PartialEq`` alone is
sufficient for ``Vec::contains``, while ``Hash + Eq`` is required for ``HashSet``. The extra
trait bound is the only friction preventing the fix.

Canonical Defect Pattern
------------------------

.. code-block:: rust

   // Defective — O(V²)
   let mut visited: Vec<Ty<'tcx>> = Vec::new();

   fn dfs(ty: Ty<'tcx>, visited: &mut Vec<Ty<'tcx>>) {
       if visited.contains(&ty) { return; }   // O(|visited|)
       visited.push(ty);
       // ... recurse
   }

.. code-block:: rust

   // Fixed — O(V)
   use rustc_data_structures::fx::FxHashSet;
   let mut visited: FxHashSet<Ty<'tcx>> = FxHashSet::default();

   fn dfs(ty: Ty<'tcx>, visited: &mut FxHashSet<Ty<'tcx>>) {
       if !visited.insert(ty) { return; }   // O(1) — insert returns false if duplicate
       // ... recurse
   }

Confirmed Defects
-----------------

Two defects in ``rustc`` and one in Cargo. See :doc:`../compiler/rustc` for the compiler
analysis and :doc:`../tool-harness/cargo` for the Cargo analysis.

| Defect      | File                                          | Complexity | Status    |
|-------------|-----------------------------------------------|------------|-----------|
| rustc-0001  | ``inhabited_predicate.rs:109,127``            | O(d²)      | Unpatched |
| rustc-0002  | ``specialization_graph.rs:69``                | O(V²)      | Unpatched |
| cargo-0001  | ``ops/tree/mod.rs:343``                       | bounded    | Unpatched |

Ecosystem Note — Clean Implementations
---------------------------------------

The Cargo main dependency resolver uses ``HashSet`` throughout and is correct. ``cargo-0001``
is in the ``cargo tree`` display command — a separate code path from the resolver — and is
bounded by display output. Rust's own standard library documentation explicitly calls out that
``contains`` on ``Vec`` is O(n) and recommends ``HashSet`` for repeated membership testing.

References
----------

* :doc:`../compiler/rustc`
* :doc:`../tool-harness/cargo`
