java-topology/whitepaper/proof/fix-pattern.rst

Universal Fix Pattern
======================

.. contents:: :local:

Overview
--------

Every CWE-407 graph traversal defect in this survey follows the same pattern and admits the
same fix. The defect is a list used for visited/stack state with linear-scan membership. The
fix is a hash-backed set with O(1) membership. The fix pattern is one-to-one: one line of
type change, one semantic-equivalent operation change.

The table below gives the canonical before/after for every affected language.

Fix Pattern Table
-----------------

Java
~~~~

.. code-block:: java

   // DEFECTIVE
   List<T> visited = new ArrayList<>();
   if (visited.contains(x)) { /* already seen */ }
   visited.add(x);

   // FIXED
   Set<T> visited = new HashSet<>();
   if (!visited.add(x)) { /* already seen — add() returns false for duplicates */ }

   // ALSO FIXED (separate contains + add)
   Set<T> visited = new HashSet<>();
   if (visited.contains(x)) { /* already seen */ }
   visited.add(x);

   // ALSO FIXED (containsAll → Set.equals)
   // DEFECTIVE:
   if (boundsA.containsAll(boundsB) && boundsB.containsAll(boundsA)) ...
   // FIXED:
   if (new HashSet<>(boundsA).equals(new HashSet<>(boundsB))) ...

**Type change:** ``List<T>`` → ``Set<T>`` (``HashSet<T>`` or ``LinkedHashSet<T>`` for order-preserving)

**Required traits/imports:** ``java.util.HashSet``; type ``T`` must implement ``equals()`` and ``hashCode()``

Python
~~~~~~

.. code-block:: python

   # DEFECTIVE
   visited = []
   if x in visited:    # O(n)
       pass
   visited.append(x)

   # FIXED
   visited = set()
   if x in visited:    # O(1)
       pass
   visited.add(x)

   # ALSO FIXED (combined check-and-add)
   visited = set()
   if not visited.add(x):  # Python: set.add returns None, so use:
       pass
   # OR:
   visited = set()
   newly_added = x not in visited
   visited.add(x)

**Type change:** ``list`` → ``set``

**Required:** type ``x`` must be hashable (all built-in Python types are; custom classes need ``__hash__``)

Haskell
~~~~~~~

.. code-block:: haskell

   -- DEFECTIVE
   import Data.List (elem)
   dfs visited v
     | v `elem` visited = ...  -- O(n)

   -- FIXED with Data.Set (O(log n))
   import qualified Data.Set as Set
   dfs visited v
     | Set.member v visited = ...  -- O(log n)

   -- FIXED with Data.HashMap (O(1))
   import qualified Data.HashMap.Strict as HashMap
   dfs visited v
     | HashMap.member v visited = ...  -- O(1)

**Type change:** ``[a]`` → ``Set a`` (requires ``Ord a``) or ``HashMap a ()`` (requires ``Hashable a``, ``Eq a``)

**Note:** ``Data.IntSet`` and ``Data.IntMap`` provide optimized O(min(n,W)) (W=word size) operations
for integer node IDs — often faster than general ``HashMap`` for compiler node indices.

Erlang
~~~~~~

.. code-block:: erlang

   %% DEFECTIVE
   case lists:member(V, Visited) of   %% O(n)
       true  -> ...;
       false -> dfs(G, [V | Visited], ...)
   end.

   %% FIXED with maps (O(1))
   case maps:is_key(V, Visited) of    %% O(1) amortized
       true  -> ...;
       false -> dfs(G, Visited#{V => true}, ...)
   end.

   %% FIXED with gb_sets (O(log n))
   case gb_sets:is_member(V, Visited) of   %% O(log n)
       true  -> ...;
       false -> dfs(G, gb_sets:add(V, Visited), ...)
   end.

**Type change:** ``[term()]`` → ``map()`` (``#{}``) or ``gb_sets:set()``

**Required:** for maps, key type must be any Erlang term (maps support arbitrary keys); no constraint

TypeScript
~~~~~~~~~~

.. code-block:: typescript

   // DEFECTIVE — pushIfUnique pattern
   const visited: Symbol[] = [];
   function pushIfUnique<T>(array: T[], toAdd: T): boolean {
       if (array.includes(toAdd)) return false;   // O(n)
       array.push(toAdd);
       return true;
   }

   // FIXED
   const visited = new Set<Symbol>();
   function tryAdd<T>(set: Set<T>, toAdd: T): boolean {
       if (set.has(toAdd)) return false;   // O(1)
       set.add(toAdd);
       return true;
   }
   // Or inline:
   if (!visited.has(sym)) { visited.add(sym); ... }

   // DEFECTIVE — Array.includes cycle check
   const resolutionTargets: object[] = [];
   if (resolutionTargets.includes(target)) ...   // O(depth)

   // FIXED
   const resolutionTargets = new Set<object>();
   if (resolutionTargets.has(target)) ...   // O(1)

**Type change:** ``T[]`` → ``Set<T>``

**Required:** ES2015 / TypeScript 2.0+; ``Set<T>`` uses reference equality for objects (correct for node identity)

Kotlin
~~~~~~

.. code-block:: kotlin

   // DEFECTIVE
   val visited = mutableListOf<ClassDescriptor>()
   if (descriptor in visited) return   // O(n) — List.contains()

   // FIXED
   val visited = HashSet<ClassDescriptor>()
   if (!visited.add(descriptor)) return   // O(1) — HashSet.add() returns false for duplicates

   // ALSO FIXED (explicit contains)
   val visited = HashSet<ClassDescriptor>()
   if (descriptor in visited) return   // O(1) — HashSet.contains() via 'in' operator

**Type change:** ``MutableList<T>`` → ``HashSet<T>``

**Note:** The ``in`` operator in Kotlin is polymorphic — it calls ``contains()`` on whatever collection
type is used. The fix requires only a type change; the ``in`` syntax is identical.

Scala
~~~~~

.. code-block:: scala

   // DEFECTIVE
   val visited = List[TypeParamRef]()
   if (visited.contains(tp)) ...   // O(n)
   minLower.exists(p => minUpper.contains(p))   // O(n²)

   // FIXED
   val visited = Set[TypeParamRef]()
   if (visited.contains(tp)) ...   // O(log n) with TreeSet, O(1) with HashSet

   // FIXED for the contains-in-exists pattern
   val upperSet = minUpper.toSet   // O(n) once
   minLower.exists(p => upperSet.contains(p))   // O(n) total

**Type change:** ``List[T]`` → ``Set[T]`` (``scala.collection.immutable.Set`` or ``mutable.HashSet``)

**Note:** For the O(n³) scala3-0001 defect, precomputing the set at constraint construction
time (not per-call) would reduce the total cost to O(n).

Rust
~~~~

.. code-block:: rust

   // DEFECTIVE
   let mut visited: Vec<Ty<'tcx>> = Vec::new();
   if visited.contains(&ty) { return; }   // O(n)
   visited.push(ty);

   // FIXED
   use rustc_data_structures::fx::FxHashSet;
   let mut visited: FxHashSet<Ty<'tcx>> = FxHashSet::default();
   if !visited.insert(ty) { return; }   // O(1)

   // ALSO FIXED (SmallVec → FxHashSet)
   // DEFECTIVE:
   let mut stack: SmallVec<[Ty; 4]> = SmallVec::new();
   if stack.contains(&self) { return; }
   // FIXED:
   let mut stack: FxHashSet<Ty> = FxHashSet::default();
   if !stack.insert(self) { return; }

**Type change:** ``Vec<T>`` or ``SmallVec<[T; N]>`` → ``FxHashSet<T>`` (or ``HashSet<T>`` from std)

**Required trait bounds:** ``T: Hash + Eq`` (in addition to the existing ``T: PartialEq`` for ``Vec::contains``)

C/C++
~~~~~

.. code-block:: cpp

   // DEFECTIVE
   std::vector<Node*> visited;
   if (std::find(visited.begin(), visited.end(), node) != visited.end()) {
       return;   // O(n)
   }
   visited.push_back(node);

   // FIXED
   std::unordered_set<Node*> visited;
   if (!visited.insert(node).second) {
       return;   // O(1) — insert().second is false if already present
   }

   // ALSO FIXED (LLVM SmallPtrSet)
   llvm::SmallPtrSet<Node*, 8> visited;
   if (!visited.insert(node).second) { return; }

   // ALSO FIXED (keep ordering for stack output, add set for membership)
   std::vector<Node*> stack;          // for ordered pop
   std::unordered_set<Node*> onStack; // for O(1) membership

**Type change:** ``std::vector<T*>`` + ``std::find`` → ``std::unordered_set<T*>`` + ``insert/count``

**Required:** pointer types hash by address (default ``std::hash<T*>``); value types require custom hash

Perl
~~~~

.. code-block:: perl

   # DEFECTIVE
   my @visited;
   if (grep { $_ eq $node } @visited) { return; }   # O(n)
   push @visited, $node;

   # FIXED
   my %visited;
   if (exists $visited{$node}) { return; }   # O(1)
   $visited{$node} = 1;

**Type change:** ``@array`` + ``grep`` → ``%hash`` + ``exists``

Summary Table
-------------

.. list-table::
   :header-rows: 1
   :widths: 12 25 25 18 20

   * - Language
     - Defective
     - Fixed
     - Cost before
     - Cost after
   * - Java
     - ``List.contains(x)``
     - ``Set.add(x)`` or ``Set.contains(x)``
     - O(n)
     - O(1)
   * - Python
     - ``x in list``
     - ``x in set``
     - O(n)
     - O(1)
   * - Haskell
     - ``x \`elem\` list``
     - ``Set.member x set``
     - O(n)
     - O(log n)
   * - Erlang
     - ``lists:member(x, list)``
     - ``maps:is_key(x, map)``
     - O(n)
     - O(1)
   * - TypeScript
     - ``array.includes(x)``
     - ``Set<T>.has(x)``
     - O(n)
     - O(1)
   * - Kotlin
     - ``x in list``
     - ``x in hashSet``
     - O(n)
     - O(1)
   * - Scala
     - ``list.contains(x)``
     - ``set.contains(x)``
     - O(n)
     - O(log n)
   * - Rust
     - ``vec.contains(&x)``
     - ``HashSet::insert(&x)``
     - O(n)
     - O(1)
   * - C/C++
     - ``std::find(v.begin(), v.end(), x)``
     - ``unordered_set::insert(x)``
     - O(n)
     - O(1)
   * - Perl
     - ``grep { $_ eq $x } @array``
     - ``exists $hash{$x}``
     - O(n)
     - O(1)