russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
67 lines
2.5 KiB
ReStructuredText
67 lines
2.5 KiB
ReStructuredText
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`
|