Python — CWE-407 Language Analysis
====================================

.. contents:: :local:

Overview
--------

Python's list ``in`` operator (``x in list``) is O(n) — it delegates to ``list.__contains__``,
which performs a linear scan. This is the canonical CWE-407 pattern in Python. The fix is to
use a Python ``set`` (backed by a hash table): ``x in set`` is O(1) average.

The Python standard library itself includes both correct and defective implementations: the
``graphlib.TopologicalSorter`` (added in Python 3.9) is correctly implemented with set-backed
visited state, while the older ``sccutils.py`` in the PEG parser generator carried the defect
until it was patched.

Canonical Defect Pattern
------------------------

.. code-block:: python

   # Defective — O(V²)
   path = []
   def dfs(node):
       if node in path:      # O(|path|) linear scan
           return            # cycle detected
       path.append(node)
       for neighbor in graph[node]:
           dfs(neighbor)
       path.pop()

.. code-block:: python

   # Fixed — O(V)
   on_path = set()
   def dfs(node):
       if node in on_path:   # O(1) hash lookup
           return
       on_path.add(node)
       for neighbor in graph[node]:
           dfs(neighbor)
       on_path.discard(node)

Confirmed Defects
-----------------

cpython-0001
~~~~~~~~~~~~

CPython PEG parser generator ``sccutils.py``. See :doc:`../compiler/cpython-peg` for full
analysis. **Status: Patched.**

distlib-0001
~~~~~~~~~~~~

**File:** ``distlib/util.py:1180,1204``

**Pattern:**

.. code-block:: python

   # Tarjan SCC in pip's dependency resolver — 'successor in stack' where stack is a list
   def strong_connections(graph):
       stack = []
       lowlinks = {}
       index = {}
       sccs = []

       def strongconnect(v):
           index[v] = lowlinks[v] = len(index)
           stack.append(v)
           for w in graph.get(v, []):
               if w not in index:
                   strongconnect(w)
                   lowlinks[v] = min(lowlinks[v], lowlinks[w])
               elif w in stack:   # O(V) — list membership
                   lowlinks[v] = min(lowlinks[v], index[w])
           if lowlinks[v] == index[v]:
               scc = []
               while True:
                   w = stack.pop()
                   scc.append(w)
                   if w == v:
                       break
               sccs.append(scc)

       for v in graph:
           if v not in index:
               strongconnect(v)
       return sccs

**Why this is O(n):** ``w in stack`` where ``stack`` is a list; same pattern as cpython-0001.
This code runs during ``pip install`` dependency resolution for every package with a dependency
graph large enough to form cycles (circular dependencies, sdist build deps).

**Complexity:** ``O(V²)`` where V = number of packages in the dependency graph

**Patch:**

.. code-block:: python

   def strong_connections(graph):
       stack = []
       on_stack = set()   # O(1) membership
       lowlinks = {}
       index = {}
       sccs = []

       def strongconnect(v):
           index[v] = lowlinks[v] = len(index)
           stack.append(v)
           on_stack.add(v)
           for w in graph.get(v, []):
               if w not in index:
                   strongconnect(w)
                   lowlinks[v] = min(lowlinks[v], lowlinks[w])
               elif w in on_stack:   # O(1)
                   lowlinks[v] = min(lowlinks[v], index[w])
           if lowlinks[v] == index[v]:
               scc = []
               while True:
                   w = stack.pop()
                   on_stack.discard(w)
                   scc.append(w)
                   if w == v:
                       break
               sccs.append(scc)

       for v in graph:
           if v not in index:
               strongconnect(v)
       return sccs

**Data structure change:** ``list`` stack + ``in`` → ``set`` on_stack + ``in``

**Status:** Unpatched

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

.. TODO: benchmark pending patch

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

Identical to cpython-0001. Let V = package nodes. ``w in stack`` costs O(V) per call.
O(V²) total with list; O(V) total with set. QED.

References
----------

* :doc:`../compiler/cpython-peg`
* :doc:`../tool-harness/pip-distlib`

Clean Python Implementations (Reference)
-----------------------------------------

- ``graphlib.TopologicalSorter`` (Python 3.9+): set-backed, correct O(V+E)
- ``ast`` cycle checking: set-backed throughout