russell@unturf.com d4ed2dff91 ORM wave: 24 defects patched across 10 ORMs (157 sites, 62 ecosystems)

Hibernate (5 HIGH): addColumn/addReferencedColumn/addIndex ArrayList→LinkedHashSet (19x)
  FK second-pass LinkedHashSet, orderHierarchy LinkedHashSet
MyBatis (1 MEDIUM): sortConstructorMappings indexOf→HashMap (12x)
EF Core (2 HIGH + 1 MEDIUM): FindGenerationProperty HashSet (250x),
  AddPrincipals HashSet (250x), FK discovery HashSet (6x)
Diesel (3 MEDIUM): SQLite/MySQL row position()→BTreeMap (51x)
SQLAlchemy (2 HIGH): _values_bindparam Set (500x), evaluated_keys Set (500x)
Peewee (1 MEDIUM): _SortedFieldList.index() bisect (42x)
Sequelize (2 HIGH): bulkInsert Set (50x), expandIncludeAll Set (250x)
TypeORM (3 HIGH): OrmUtils.uniq Map (500x), diffColumns Set (125x),
  updatedColumns Set (100x)
Doctrine ORM (1 HIGH + 2 MEDIUM): hydrator discriminator (26x),
  addSubClass (250x), SqlWalker partial (130x)
GORM (1 MEDIUM): sortCallbacks getRIndex→map (194x)
SQLite: SqliteTest unit proof 4/4 PASS (101x)

Unit tests: all PASS — Hibernate/MyBatis/EfCore/Diesel/SQLAlchemy/Peewee/
  Sequelize/TypeORM/Doctrine/GORM
Whitepaper: 157 sites, 62 ecosystems; PDF 752K

2026-03-27 13:34:26 -04:00

2.8 KiB

Raw Permalink Blame History

doctrine-orm-0002 — ClassMetadata::addSubClass: O(n²) subclass dedup during metadata loading

Status: OPEN Severity: MEDIUM Component: doctrine/orm — src/Doctrine/ORM/Mapping/ClassMetadata.php Affects: Application startup / metadata cache warming; entity class hierarchies with many subclasses

Root Cause

ClassMetadata.php:2313 — addSubClass():

// DEFECTIVE — O(subclasses) linear scan per addSubClass call
public function addSubClass(string $className): void
{
    if (is_subclass_of($className, $this->name) && ! in_array($className, $this->subClasses, true)) {
        $this->subClasses[] = $className;
    }
}

$this->subClasses is a plain PHP array (public array $subClasses = [], line 314). in_array scans the entire array for every call.

addSubClass() is called inside loops in ClassMetadataFactory:

ClassMetadataFactory.php:152: $class->addSubClasses($parent->subClasses) — bulk add loop
ClassMetadataFactory.php:386: inside foreach ($parentClasses as $parentClass) loop inside findAbstractEntityClassesNotListedInDiscriminatorMap()

The second call site is the worst case: for each discriminator map entry, getParentClasses() returns all ancestor classes, and addSubClass is called for each. With S subclasses and D depth, total comparisons: O(S × D × S) = O(S²×D).

Complexity Analysis

Metric	Defective	Fixed
Single addSubClass	O(current subclass count)	O(1)
Full hierarchy load (S subclasses)	O(S²)	O(S)
Growth pattern	Quadratic	Linear

Fix

Replace $this->subClasses with a parallel indexed structure, or use a Set-equivalent (array keyed by class name):

// Keep public array $subClasses for backward compat, add private set for O(1) lookup
private array $subClassSet = [];

public function addSubClass(string $className): void
{
    if (is_subclass_of($className, $this->name) && ! isset($this->subClassSet[$className])) {
        $this->subClassSet[$className] = true;
        $this->subClasses[] = $className;
    }
}

Alternatively, key $subClasses by class name directly (breaking change to indexed access).

Call Sites

File	Line	Context
`src/Mapping/ClassMetadata.php`	2313	`addSubClass()`
`src/Mapping/ClassMetadataFactory.php`	152	bulk inherit from parent
`src/Mapping/ClassMetadataFactory.php`	386	discriminator map abstract class discovery

Speedup Estimate

Metadata loading for a hierarchy with 50 subclasses: ~50× reduction in membership check work. Impact is startup/warm-up only (metadata is cached after first load). Applications without metadata caching (e.g., dev mode with auto_generate_proxy_classes) see this on every request.

2.8 KiB Raw Permalink Blame History Unescape Escape