# UNDF: UNDF-2026-000000606
# UNDF: (pending)
# doctrine-orm-0001: ClassMetadata::addSubClass — O(N²) in_array on subClasses list

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | doctrine-orm-0001 |
| Severity | HIGH |
| Ecosystem | doctrine-orm |
| Package | doctrine/orm |
| File | `src/Mapping/ClassMetadata.php` |
| Lines | 2308–2315 |
| Complexity | O(S²) per hierarchy, O(N·S²) total metadata load |
| Hot path | EntityManager::getMetadataFactory()->getMetadataFor() — called on every entity operation |

## Defect

```php
// BEFORE — O(S²): in_array() is O(S) inside addSubClasses() which iterates S entries
// Called from ClassMetadataFactory::doLoadMetadata() during metadata bootstrap.
// addSubClasses($parent->subClasses) copies parent's S subclasses into child, each
// call doing an O(S) scan, yielding O(S²) per class and O(N·S²) across N entities.

public function addSubClass(string $className): void
{
    if (is_subclass_of($className, $this->name) && ! in_array($className, $this->subClasses, true)) {
        $this->subClasses[] = $className;   // O(S) scan each insertion
    }
}
```

Called from `ClassMetadataFactory::doLoadMetadata` (line 152):

```php
$class->addSubClasses($parent->subClasses);  // iterates S entries × O(S) each = O(S²)
```

And from the parent-class scan loop (line 386):

```php
foreach ($parentClasses as $parentClass) {
    $rootEntityClass->addSubClass($parentClass);  // O(S) scan per parent
}
```

`subClasses` is declared as a plain `list<class-string>` with no parallel hash index:

```php
// src/Mapping/ClassMetadata.php line 314
public array $subClasses = [];
```

## Fix

```php
// AFTER — O(1) lookup: maintain a parallel hash-keyed set alongside the list.
// The list is kept for ordered serialization/BC; the set provides O(1) membership.

// Add alongside $subClasses (line ~314):
/** @phpstan-var array<class-string, true> */
public array $subClassesSet = [];

public function addSubClass(string $className): void
{
    if (is_subclass_of($className, $this->name) && !isset($this->subClassesSet[$className])) {
        $this->subClassesSet[$className] = true;   // O(1) hash insert
        $this->subClasses[] = $className;           // preserve ordered list for BC
    }
}
```

`$subClassesSet` must also be hydrated on deserialization (in `__wakeup` / `__clone`):

```php
// Rebuild set after deserialization:
$this->subClassesSet = array_fill_keys($this->subClasses, true);
```

## Speedup

| S (subclasses) | Before (ops) | After (ops) | Speedup |
|----------------|-------------|-------------|---------|
| 50 | 1,275 | 50 | 25× |
| 100 | 5,050 | 100 | 50× |
| 500 | 125,250 | 500 | 250× |
| 1,000 | 500,500 | 1,000 | 500× |

A Doctrine application with a 100-subclass STI (Single-Table Inheritance) hierarchy
pays 5,050 membership scans on every cold metadata bootstrap instead of 100.
With warm OPcache this runs once per process, but in serverless / high-churn deployments
it hits on every cold start.