java-topology/defects/cargo/cargo-0002-edges-add-edge-hashset.md

cargo-0002: CWE-407 — O(E²) Vec.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:

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:

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.