# UNDF: UNDF-2026-000000045
# UNDF: (pending)
# composer-0003: InstalledRepository::getDependents — O(P²) in_array on growing needles list

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | composer-0003 |
| Severity | MEDIUM |
| Ecosystem | composer |
| Package | composer/composer |
| File | `src/Composer/Repository/InstalledRepository.php` |
| Lines | 177, 190, 201 |
| Complexity | O(P·N) → O(P²) where P = installed packages, N = needles (grows during loop) |
| Hot path | `composer why` / `composer why-not` — invoked for every dependency resolution query |

## Defect

```php
// BEFORE — O(P²): in_array($x, $needles) is O(N) inside foreach($this->getPackages()) O(P).
// $needles starts as the query needle set but GROWS during the loop (line 144):
//   $needles[] = $link->getTarget();
// So at iteration i, len($needles) can be up to i, making total cost O(P²).

// Note: $packagesFoundSet already provides O(1) cycle-detection, but $needles is a
// separate plain PHP array with no hash index.

foreach ($this->getPackages() as $package) {
    // ...
    if ($invert && in_array($package->getName(), $needles, true)) {    // O(N) scan, line 177
        // ...
    }
    foreach ($package->getConflicts() as $link) {
        if (in_array($link->getTarget(), $needles, true)) {            // O(N) scan, line 190
            // ...
        }
    }
    if ($invert && $constraint && in_array($package->getName(), $needles, true) ...) { // O(N) scan, line 201
        // ...
    }
}
```

## Fix

```php
// AFTER — O(1) lookup: build a parallel $needlesSet hash alongside $needles.
// Update $needlesSet whenever $needles grows.

$needles = array_map('strtolower', (array) $needle);
$needlesSet = array_fill_keys($needles, true);   // O(1) lookup companion

// ...
// Where needles grows (line 144), mirror the addition:
$needles[] = $link->getTarget();
$needlesSet[$link->getTarget()] = true;          // O(1) insert

// Replace all three in_array() calls:
if ($invert && isset($needlesSet[$package->getName()])) {          // O(1) — was line 177
if (isset($needlesSet[$link->getTarget()])) {                      // O(1) — was line 190
if ($invert && $constraint && isset($needlesSet[$package->getName()])) { // O(1) — was line 201
```

## Speedup

| P (packages) | Before (ops) | After (ops) | Speedup |
|--------------|-------------|-------------|---------|
| 50 | 2,500 | 50 | 50× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |
| 1,000 | 1,000,000 | 1,000 | 1,000× |

A large monorepo with 500 installed packages incurs 250,000 membership scans on
`composer why` (invert mode) instead of 500. This command is run frequently during
debugging and CI dependency audits.
