Composer — CWE-407 Analysis
============================

.. contents:: :local:

Overview
--------

Composer is the de facto PHP package manager, used by virtually all PHP projects.
Its dependency resolver uses a CDCL/SAT-based solver (``DependencyResolver/``) with
a pool of package objects. It also provides display and diagnostic commands
(``composer why``, ``composer show --tree``, ``composer depends``) that traverse the
installed dependency graph.

**Status: 2 confirmed defects — MEDIUM severity, both unpatched**

The installation solver is CLEAN. The defects are in the graph traversal code used
for display and diagnostic commands.

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

.. list-table::
   :header-rows: 1
   :widths: 15 40 20 10 15

   * - ID
     - File:Line
     - Pattern
     - Complexity
     - Severity
   * - composer-0001
     - ``Repository/RepositoryUtils.php:46``
     - ``in_array($candidate, $bucket)`` in ``filterRequiredPackages`` foreach
     - O(N²) + O(N³) recursive
     - MEDIUM
   * - composer-0002
     - ``Repository/InstalledRepository.php:128,154,167,180``
     - ``in_array($pkg, $packagesInTree)`` × 4 in ``getDependents``
     - O(N² × L × K)
     - MEDIUM

Defect Detail — composer-0001
-------------------------------

``RepositoryUtils::filterRequiredPackages()`` finds all transitively required packages
using a PHP array ``$bucket`` for the result/visited set::

   foreach ($packages as $candidate) {         // O(N) packages
       foreach ($candidate->getNames() as $name) {
           if (isset($requires[$name])) {
               if (!in_array($candidate, $bucket, true)) {   // O(|bucket|) = O(N) worst case
                   $bucket[] = $candidate;
                   $bucket = self::filterRequiredPackages($packages, $candidate, ...);

``in_array()`` on a PHP array is a sequential scan — O(n). ``$bucket`` grows to O(N)
as packages are found. Top-level cost is O(N²); with recursive calls for transitive
dependencies, O(N³) worst case.

For a Symfony project with 200 installed packages, this is 40,000 comparisons per
``composer why`` call.

**Fix:** Replace ``$bucket`` array with an associative hash keyed on ``spl_object_id($candidate)``;
use ``isset()`` for O(1) membership. Return ``array_values($bucket)`` at the boundary.

Defect Detail — composer-0002
-------------------------------

``InstalledRepository::getDependents()`` traverses the dependency graph for
``composer show --tree`` and ``composer depends --tree``::

   foreach ($this->getPackages() as $package) {            // O(N)
       ...
       foreach ($links as $link) {                          // O(L links/package)
           foreach ($needles as $needle) {                  // O(K needles)
               if (in_array($source, $packagesInTree)) {    // O(|tree|) = O(N) growing

``$packagesInTree`` is a PHP array that grows as packages are added with
``$packagesInTree[] = $link->getSource()``. Four call sites (lines 128, 154, 167, 180)
all scan this same growing array.

**Fix:** Thread a ``$packagesInTreeSet`` associative array alongside ``$packagesInTree``;
replace ``in_array($x, $packagesInTree)`` with ``isset($packagesInTreeSet[$x])``.

Solver Core — CLEAN
--------------------

The CDCL/SAT dependency solver (``DependencyResolver/Solver.php``,
``DependencyResolver/RuleSet.php``, ``DependencyResolver/Pool.php``) is clean:

- Package lookup by name: ``$this->packages`` via associative hash — O(1)
- Rule propagation: integer-indexed arrays, O(1) access by package ID
- ``Pool::isUnacceptableFixedOrLockedPackage()``: O(n) scan on
  ``$this->unacceptableFixedOrLockedPackages``, but this list is bounded to
  single digits in practice (explicit lock overrides only). Not flagged.

The defects are entirely in the display/diagnostic layer, not the solver.

Scan Details
------------

* Scanner: ``tools/scans/composer.sh``
* Scan result: ``tools/scan-results/composer.txt`` — 29 candidates; 2 confirmed
* Scanned: ``DependencyResolver/``, ``Package/``, ``Repository/``, ``Util/``
