GCC — CWE-407 Analysis
=======================

.. contents:: :local:

Overview
--------

GCC (GNU Compiler Collection) is one of the most widely deployed compiler suites, supporting
C, C++, Fortran, Ada, and other languages. Its coverage analysis tool ``gcov`` uses Johnson's
algorithm for cycle detection in the control-flow graph. One CWE-407 defect site was found in
the cycle-detection path. It is unpatched.

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

gcc-0001
~~~~~~~~

**File:** ``gcc/gcov.cc:980``

**Pattern:**

.. code-block:: cpp

   // Johnson's algorithm cycle detection — std::find on vector
   std::vector<arc_info *> stack;
   // ...
   bool blocked_search(arc_info *arc, ...) {
       if (std::find(stack.begin(), stack.end(), arc) != stack.end()) {
           return false;   // O(V) linear scan: std::find walks entire vector
       }
       stack.push_back(arc);
       // ... recurse
   }

**Why this is O(n):** ``std::find`` on a ``std::vector`` is O(n); called once per arc during
DFS stack-membership check in Johnson's algorithm.

**Complexity:** ``O(V²)`` where V = number of arcs in the control-flow graph

**Patch:**

.. code-block:: cpp

   std::unordered_set<arc_info *> stack_set;
   std::vector<arc_info *> stack;   // keep for ordering if needed

   bool blocked_search(arc_info *arc, ...) {
       if (stack_set.count(arc)) {
           return false;   // O(1) hash lookup
       }
       stack.push_back(arc);
       stack_set.insert(arc);
       // ... recurse
   }

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

**Status:** Unpatched

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

.. TODO: benchmark pending patch

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

Let V = number of arcs in the CFG. Johnson's algorithm visits each arc; the ``blocked_search``
function tests stack membership once per arc. With ``std::find`` on a vector of up to V
elements: O(V) per test, O(V²) total. With ``unordered_set::count``: O(1) per test, O(V) total.
QED.

References
----------

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