# 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>`):

```cpp
// 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.
