# cargo-0002: CWE-407 — O(E²) Vec<Edge>.contains() dedup in Edges::add_edge

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity)
**Target:** rust-lang/cargo
**File:** `src/cargo/ops/tree/graph.rs`
**Lines:** 122–126
**Status:** PATCHED (unit test PASS)

## Description

`Edges::add_edge()` deduplicates outgoing edges from a dependency graph node by
calling `Vec::contains` before each push:

```rust
fn add_edge(&mut self, edge: Edge) {
    let indexes = self.0.entry(edge.kind()).or_default();
    if !indexes.contains(&edge) {   // O(n) scan of Vec<Edge>
        indexes.push(edge)
    }
}
```

`self.0` is `HashMap<EdgeKind, Vec<Edge>>`.  For each `EdgeKind` bucket, edges
are stored in a `Vec` and membership is tested with a linear scan.

## Call Volume

`add_edge` is called from:
- `build_graph()` — once per dep edge per package when processing the workspace
  dependency graph (line 545, 548)
- `add_feature()` (lines 597, 604) — called for *every feature* of every
  dependency, twice per feature (from→feature-node + feature-node→dep)
- Graph deduplication in `dedupe_graph()` (lines 279, 302)

With `--graph-features` (`cargo tree -e features`), a package with F features
and D dependencies each averaging G features generates on the order of
`D × G × 2` `add_edge` calls just for that package.  For a workspace with
`tokio` (50+ features) or `serde` (multiple feature flags) as a shared
dependency, the total feature edge count per node grows large.

Within each `EdgeKind::Feature` bucket, the `Vec<Edge>` for a heavily-featured
node can accumulate dozens of entries.  Each subsequent `add_edge` call scans
the entire existing Vec — O(k) for the k-th insertion — making the total
insertion cost O(E²/K) where E is total edges and K is the number of edge kind
buckets (2–3 in practice).

## Root Cause

`Vec<Edge>` was chosen because edge sets are "usually small" but in
`--graph-features` mode they can grow to 50–100 entries per node, triggering
the quadratic behavior.

## Fix

Replace `Vec<Edge>` with an order-preserving `IndexSet<Edge>` (from the
`indexmap` crate, already a transitive dependency of cargo) so that both
membership test and push are O(1) amortized:

```rust
use indexmap::IndexSet;

struct Edges(HashMap<EdgeKind, IndexSet<Edge>>);

impl Edges {
    fn add_edge(&mut self, edge: Edge) {
        self.0.entry(edge.kind()).or_default().insert(edge);
        // IndexSet::insert is O(1) amortized and ignores duplicates.
    }
    fn all(&self) -> impl Iterator<Item = &Edge> + '_ {
        self.0.values().flatten()
    }
    fn of_kind(&self, kind: &EdgeKind) -> &[Edge] {
        self.0.get(kind).map(IndexSet::as_slice).unwrap_or_default()
    }
}
```

`Edge` already derives `Hash + Eq` (required by `IndexSet`).

## Complexity

| Version | Per add_edge (E total) | Total |
|---------|------------------------|-------|
| Before  | O(k) (k = current bucket size) | O(E²/K) |
| After   | O(1) amortized | O(E) |

At E = 200 feature edges per shared dep node, K = 1 (Feature bucket):
200 × 200 / 2 = **20 000 comparisons** vs **200 inserts** — 100× reduction.
