java-topology/defects/cmake/cmake-0004-addsource-ticket.md

cmake-0004 — AddSource: O(n²) std::find_if per call in Unity build loop

Severity: HIGH File: Source/cmTarget.cxx Lines: 1428–1444 CWE: CWE-407 (Algorithmic Complexity — Quadratic)

Description

cmTarget::AddSource() performs a linear std::find_if over the entire Sources.Entries vector on every call:

// Source/cmTarget.cxx:1432-1434
auto const& sources = this->impl->Sources.Entries;
if (std::find_if(sources.begin(), sources.end(),
                 TargetPropertyEntryFinder(sfl)) == sources.end()) {

AddSource is called in a for loop over unity_files in cmLocalGenerator.cxx:3353:

for (UnitySource const& file : unity_files) {
    target->AddSource(file.Path, true);   // O(n) scan each iteration

For a Unity build with S source files, constructing the unity file list costs O(S²) in total. Unity builds are precisely the scenario where S is large (hundreds to thousands of files per target).

Fix

Maintain a parallel std::unordered_set<std::string> SourcePathsSet in cmTargetInternals. On each AddSource call, attempt a set insertion first; if already present, skip the find_if and WriteDirect entirely.

Patch: patch/cmake-0004-addsource-unordered-set.patch Unit test: unit/AddSourceAlgorithm.java

Complexity

	Time
Before	O(S²)
After	O(S) amortised

Speedup estimate

At S=1000 sources: ~500× fewer comparisons on the hot path. Measured HIGH: Unity builds with thousands of sources are a documented CMake use-case (Qt, Chromium, large game engines).