TypeScript — CWE-407 Language Analysis
========================================

.. contents:: :local:

Overview
--------

TypeScript's ``Array.prototype.includes()`` is O(n). The TypeScript compiler's own codebase
uses an internal helper ``pushIfUnique(array, item)`` that calls ``array.includes(item)``
before pushing — a widespread pattern in ``checker.ts`` for tracking visited state.

The idiomatic fix is ``Set<T>``; ``Set.has()`` and ``Set.add()`` are O(1) amortized. The
TypeScript standard library has supported ``Set<T>`` since ES2015 / TypeScript 2.0; there is
no language-level obstacle to using it.

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

.. code-block:: typescript

   // Defective — pushIfUnique helper used for visited tracking: O(V²)
   const visited: Symbol[] = [];

   function pushIfUnique<T>(array: T[], toAdd: T): boolean {
       if (array.includes(toAdd)) return false;   // O(|array|)
       array.push(toAdd);
       return true;
   }

   function traverse(sym: Symbol) {
       if (!pushIfUnique(visited, sym)) return;
       for (const dep of getDependencies(sym)) traverse(dep);
   }

.. code-block:: typescript

   // Fixed — Set<T>: O(V)
   const visited = new Set<Symbol>();

   function traverse(sym: Symbol) {
       if (visited.has(sym)) return;    // O(1)
       visited.add(sym);
       for (const dep of getDependencies(sym)) traverse(dep);
   }

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

Three defects in ``checker.ts`` — the core type checker. All unpatched. See
:doc:`../compiler/tsc` for full analysis.

| Defect  | File                    | Site                           | Complexity    | Status    |
|---------|-------------------------|--------------------------------|---------------|-----------|
| ts-0001 | ``checker.ts:11503``    | ``findResolutionCycleStartIndex`` | O(depth²)  | Unpatched |
| ts-0002 | ``checker.ts:5256``     | ``pushIfUnique(visitedSymbols)`` | O(V²)      | Unpatched |
| ts-0003 | ``checker.ts:5763``     | ``pushIfUnique(visitedSymbolTables)`` | O(depth²) | Unpatched |

Ecosystem Note
--------------

The ``pushIfUnique`` pattern appears throughout ``checker.ts`` beyond the three confirmed
sites. A full audit of all ``pushIfUnique`` call sites is recommended as part of the patch
effort. The function signature makes it a drop-in target for a codemod: every
``pushIfUnique(arr, x)`` where ``arr`` is a visited/stack tracker can be converted to a
``Set`` operation.

References
----------

* :doc:`../compiler/tsc`
