Cargo — CWE-407 Analysis
=========================

.. contents:: :local:

Overview
--------

Cargo is the Rust package manager and build tool. Its main dependency resolver uses ``HashSet``
throughout and is correctly implemented — O(V+E) for dependency resolution. One CWE-407 defect
site was found in the ``cargo tree`` display command. It is unpatched but classified as MEDIUM
severity because ``cargo tree`` is a display-only path and input is bounded by the size of the
installed workspace.

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

cargo-0001
~~~~~~~~~~

**File:** ``src/cargo/ops/tree/mod.rs:343``

**Pattern:**

.. code-block:: rust

   // cargo tree display — Vec::contains for cycle detection in tree traversal
   fn add_node(
       &mut self,
       package_id: PackageId,
       symbols: &Symbols,
       visited: &mut Vec<PackageId>,
   ) {
       if visited.contains(&package_id) {  // O(|visited|) — Vec::contains linear scan
           // already displayed, show as [*]
           return;
       }
       visited.push(package_id);
       // ... recurse through dependencies
   }

**Why this is O(n):** ``Vec::contains`` is a linear scan; called once per node in the tree
display traversal.

**Complexity:** ``O(V²)`` where V = packages in the workspace — bounded in practice (display only)

**Patch:**

.. code-block:: rust

   use std::collections::HashSet;

   fn add_node(
       &mut self,
       package_id: PackageId,
       symbols: &Symbols,
       visited: &mut HashSet<PackageId>,
   ) {
       if !visited.insert(package_id) {   // O(1) — insert returns false if duplicate
           return;
       }
       // ... recurse through dependencies
   }

**Data structure change:** ``Vec<PackageId>`` + ``contains`` → ``HashSet<PackageId>`` + ``insert``

**Status:** Unpatched

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

.. TODO: benchmark pending patch

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

Let V = packages in the workspace. ``Vec::contains`` on a vec of up to V elements: O(V) per
call. With V calls: O(V²). ``HashSet::insert`` is O(1) amortized: O(V) total. While the
input is bounded by workspace size in practice, the principle violation is identical to all
other defects in this survey. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/cargo-0001.md``
* Note: Cargo's main resolver (``src/cargo/core/resolver/``) is correctly implemented with
  ``HashSet`` — this defect is isolated to the tree-display code path only.
