Apache Maven — CWE-407 Analysis
=================================

.. contents:: :local:

Overview
--------

Apache Maven is the dominant build and dependency management tool for Java projects. It
constructs a project dependency graph and uses topological sorting for build-order resolution.
Three CWE-407 defect sites were found across Maven's internal graph implementation. All three
are unpatched.

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

maven-0001
~~~~~~~~~~

**File:** ``impl/maven-core/src/main/java/org/apache/maven/project/Graph.java:63-64``

**Pattern:**

.. code-block:: java

   // Project dependency graph — ArrayList.remove() in removeEdge
   private final Map<String, List<String>> edges = new HashMap<>();

   public void removeEdge(String from, String to) {
       List<String> deps = edges.get(from);
       if (deps != null) {
           deps.remove(to);   // O(n) — ArrayList.remove(Object) is linear scan
       }
   }

**Why this is O(n):** ``ArrayList.remove(Object)`` scans the list for the first occurrence of
the element. Called during edge removal in cycle-breaking traversal.

**Complexity:** ``O(n)`` per edge removal; ``O(E²/V)`` for full graph reduction

**Patch:**

.. code-block:: java

   private final Map<String, LinkedHashSet<String>> edges = new HashMap<>();

   public void removeEdge(String from, String to) {
       LinkedHashSet<String> deps = edges.get(from);
       if (deps != null) {
           deps.remove(to);   // O(1) — HashSet.remove is O(1)
       }
   }

**Data structure change:** ``Map<String, List<String>>`` → ``Map<String, LinkedHashSet<String>>``

**Status:** Unpatched

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

.. TODO: benchmark pending patch

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

Let E = edges, V = vertices. ``ArrayList.remove(Object)`` is O(E/V) per call (average degree).
With E removals total: O(E²/V). With ``HashSet.remove``: O(1) per removal, O(E) total. QED.

References
----------

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

maven-0002
~~~~~~~~~~

**File:** ``impl/maven-core/src/main/java/org/apache/maven/internal/impl/Graph.java:63-64``

**Pattern:**

Duplicate of maven-0001 in a parallel internal implementation class. Identical defect, identical
fix.

**Why this is O(n):** Same as maven-0001 — ``ArrayList.remove(Object)`` linear scan.

**Complexity:** ``O(n)`` per edge removal

**Patch:**

Identical to maven-0001: replace ``List<String>`` adjacency lists with ``LinkedHashSet<String>``.

**Data structure change:** ``Map<String, List<String>>`` → ``Map<String, LinkedHashSet<String>>``

**Status:** Unpatched

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

.. TODO: benchmark pending patch (same as maven-0001)

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

Identical to maven-0001. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/maven-0002.md``

maven-0003
~~~~~~~~~~

**File:** ``impl/maven-core/src/main/java/org/apache/maven/project/Graph.java:102``

**Pattern:**

.. code-block:: java

   // Cycle reporter — LinkedList.lastIndexOf in diagnostic output
   private String formatCycle(LinkedList<String> cycle) {
       int start = cycle.lastIndexOf(cycle.getLast());  // O(n) — lastIndexOf is linear
       return cycle.subList(start, cycle.size()).stream()
           .collect(Collectors.joining(" -> "));
   }

**Why this is O(n):** ``LinkedList.lastIndexOf()`` traverses the entire list. This is in the
cycle-reporting path (diagnostic output), so it is cold-path and bounded by the cycle length.

**Complexity:** ``O(n)`` where n = cycle length (LOW severity — diagnostic path only)

**Patch:**

.. code-block:: java

   // Use a Map to track node→index for O(1) lookup
   private String formatCycle(List<String> path) {
       Map<String, Integer> indexMap = new HashMap<>();
       for (int i = 0; i < path.size(); i++) indexMap.put(path.get(i), i);
       int start = indexMap.get(path.get(path.size() - 1));
       return path.subList(start, path.size()).stream()
           .collect(Collectors.joining(" -> "));
   }

**Data structure change:** ``LinkedList`` + ``lastIndexOf`` → ``HashMap<String,Integer>`` index

**Status:** Unpatched

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

Let n = cycle length. ``LinkedList.lastIndexOf`` is O(n). Building a ``HashMap`` is O(n);
each lookup is O(1). For the diagnostic path this is academically correct but operationally
insignificant — cycles in Maven builds are short (usually 2-3 nodes). QED.

References
----------

* Defect ticket: ``tools/tickets/defects/maven-0003.md``
