CMake — CWE-407 Analysis
=========================

.. contents:: :local:

Overview
--------

CMake is the most widely used C/C++ build system generator, processing ``CMakeLists.txt`` files
into native build system files (Makefiles, Ninja, Visual Studio projects). It performs link
dependency analysis to determine transitive link libraries. One CWE-407 defect site was found
in the link dependency computation. It is unpatched.

Defect Sites
------------

cmake-0001
~~~~~~~~~~

**File:** ``Source/cmComputeLinkDepends.cxx:1167,521,1363``

**Pattern:**

.. code-block:: cpp

   // Link dependency group membership — std::find on group vectors
   std::vector<int> groupMembers;
   // ...
   bool IsInGroup(int componentIndex) {
       return std::find(groupMembers.begin(),
                        groupMembers.end(),
                        componentIndex) != groupMembers.end();
       // O(|groupMembers|) per call
   }

   // Called during link order traversal for each target
   void ProcessGroup(...) {
       for (auto& dep : dependencies) {
           if (IsInGroup(dep.componentIndex)) {  // O(V) per edge
               // merge groups
           }
       }
   }

**Why this is O(n):** ``std::find`` on a ``std::vector`` is O(n); called once per dependency
edge during link group traversal.

**Complexity:** ``O(n)`` per group membership test; ``O(V²)`` for full link order computation
in worst case (dense dependency graph)

**Patch:**

.. code-block:: cpp

   std::unordered_set<int> groupMemberSet;
   std::vector<int> groupMembers;  // keep for ordering

   bool IsInGroup(int componentIndex) {
       return groupMemberSet.count(componentIndex) > 0;  // O(1)
   }

   void AddToGroup(int componentIndex) {
       if (groupMemberSet.insert(componentIndex).second) {
           groupMembers.push_back(componentIndex);
       }
   }

**Data structure change:** ``std::vector<int>`` + ``std::find`` → ``std::unordered_set<int>`` + ``count()``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let V = number of link-order components. ``std::find`` on a vector of up to V elements: O(V)
per call. With O(V) calls during traversal: O(V²). ``unordered_set::count`` is O(1) amortized:
O(V) total. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/cmake-0001.md``
