java-topology/defects/ninja/ninja-0001-depfile-ticket.md

ninja-0001 — DepfileParser: O(n²) std::find on ins_/outs_ vectors in parse loop

Severity: HIGH File: src/depfile_parser.cc (generated from src/depfile_parser.in.cc) Lines: 338, 349 (depfile_parser.cc) / 178, 189 (depfile_parser.in.cc) CWE: CWE-407 (Algorithmic Complexity — Quadratic)

Description

DepfileParser::Parse() scans each token in a while (in < end) loop. For each token it performs a linear membership test against ins_ and outs_ (both std::vector<StringPiece>):

// src/depfile_parser.cc:338-350
std::vector<StringPiece>::iterator pos =
    std::find(ins_.begin(), ins_.end(), piece);   // O(n)
if (pos == ins_.end()) {
    if (is_dependency) {
        ins_.push_back(piece);
    } else {
        if (std::find(outs_.begin(), outs_.end(), piece) == outs_.end())  // O(n)
            outs_.push_back(piece);
    }
}

Ninja processes one depfile per compilation unit; generated dependency files (e.g., from compilers with -MMD) can contain hundreds of header paths, many repeated (e.g., stddef.h appearing in every TU). Each parse is O(T²) where T is the token count. For a build with many TUs, total depfile parse cost is O(B × T²).

Fix

Shadow ins_ and outs_ with std::unordered_set<StringPiece> members (ins_set_, outs_set_). Use set insertion/lookup for the membership checks; keep the vectors for ordered output.

Patch: patch/ninja-0001-depfile-unordered-set.patch Unit test: unit/DepfileAlgorithm.java

Complexity

	Time per depfile
Before	O(T²)
After	O(T) amortised

Speedup estimate

At T=500 tokens (a header-heavy TU): ~250× fewer comparisons. Severity HIGH: depfile parsing occurs for every compilation unit on every incremental build.