Java — CWE-407 Language Analysis
=================================

.. contents:: :local:

Overview
--------

Java's ``java.util.ArrayList`` and related ``List`` implementations expose a ``contains(Object o)``
method that performs a linear scan of the backing array. This is O(n) and is the canonical source
of CWE-407 defects in the Java ecosystem. The pattern is endemic because ``ArrayList`` is the
default collection in Java idiom and developers frequently use ``contains`` without considering
its cost in loops.

The fix in all cases is to replace the ``List`` with a ``HashSet`` (or ``LinkedHashSet`` when
insertion order must be preserved). ``HashSet.contains()`` and ``HashSet.add()`` are O(1)
amortized.

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

.. code-block:: java

   // Defective — O(V²) for V membership tests
   List<Node> visited = new ArrayList<>();
   for (Node n : graph.nodes()) {
       if (!visited.contains(n)) {   // O(|visited|) each time
           visited.add(n);
           // ... process n
       }
   }

.. code-block:: java

   // Fixed — O(V) for V membership tests
   Set<Node> visited = new HashSet<>();
   for (Node n : graph.nodes()) {
       if (visited.add(n)) {   // O(1) — add returns false if already present
           // ... process n
       }
   }

Confirmed Defects in this Language's Compiler/Runtime
------------------------------------------------------

All five javac defects are Java code: see :doc:`../compiler/javac` for full analysis.

| Defect     | File                                  | Complexity | Status   |
|------------|---------------------------------------|------------|----------|
| javac-0001 | ``GraphUtils.java:186``               | O(V²)      | Patched  |
| javac-0002a| ``Infer.java:1850``                   | O(N²)      | Patched  |
| javac-0002b| ``Infer.java:1747``                   | O(K·V)     | Patched  |
| javac-0003 | ``ModuleHashesBuilder``               | O(V²)      | Unpatched|
| javac-0004 | ``Dependencies.java:197``             | O(M²)      | Patched  |
| javac-0005 | ``InferenceContext.java:506``         | O(B²)      | Patched  |

The ``javac-0003`` defect is in the ``java.base`` module (``ModuleHashesBuilder``), not in the
compiler package itself. It also affects JVM module resolution at runtime for large module
graphs.

Java Ecosystem Note
-------------------

Maven also carries two instances of this pattern in its project graph implementation: see
:doc:`../tool-harness/maven`.

The canonical fix summary for Java:

- Replace ``ArrayList<T>.contains(x)`` with ``HashSet<T>.contains(x)``
- Replace ``if (!list.contains(x)) { list.add(x); }`` with ``set.add(x)`` (idempotent)
- Replace ``list.containsAll(other)`` with ``new HashSet<>(list).equals(new HashSet<>(other))``
- Replace ``Deque.contains(x)`` with a companion ``HashSet`` for O(1) membership tests

Clean Java Implementations (Reference)
---------------------------------------

- **Gradle** ``ExecutionPlan``: uses ``HashSet`` and ``HashMultimap`` throughout — correct O(V+E)
- **Cargo main resolver** (Java-adjacent): HashSet throughout

References
----------

* :doc:`../compiler/javac`
* :doc:`../tool-harness/maven`