Performance: super-linear analysis time when a variable is assigned across many `===` narrowing branches

[SanderMuller]

Feature request

Assigning a variable inside many if ($x === <const>) $v = …; branches makes PHPStan's analysis time grow super-linearly in the number of branches. It's a common shape (lexers, state machines, value mappers, factories, generated dispatch tables), so a large such function makes PHPStan disproportionately slow on that one file. I'd like analysis of this shape to stay roughly linear in the number of branches.

Reproduction (single file, level 8, PHP 8.5, PHPStan 2.2.x-dev, result cache cold):

<?php
// generate: php -r '$n=400; $c="<?php\nfunction f(int \$x): string {\n \$v=0;\n"; for($i=0;$i<$n;$i++){$c.=" if (\$x === $i) \$v = \"$i\";\n";} $c.=" return (string) \$v;\n}\n"; file_put_contents("repro.php",$c);'
function f(int $x): string {
    $v = 0;
    if ($x === 0) $v = "0";
    if ($x === 1) $v = "1";
    // ... one such branch per constant ...
    return (string) $v;
}

N (branches)	analysis CPU
25	0.46 s
100	0.79 s
400	20.6 s

100 → 400 is 4x the input for ~26x the time. (I didn't use the playground because the analysis exceeds its time limit at these sizes; the one-liner above reproduces it locally.)

What it is NOT (discriminated at N=400): it's specifically the interaction of constant-value === narrowing with assigning a variable, not union-building, not narrowing in general, and not instanceof:

variant	CPU
if ($x === $i) $v = … (narrow + assign)	20.6 s	the slow case
if (rand()) $v = … (same $v union, no narrowing)	1.9 s	union-building is fine
if ($x === $i) return $i; (narrowing, no $v union)	0.6 s	narrowing alone is fine
if ($x instanceof C$i) $v = … (instanceof, not ===)	2.7 s	instanceof narrowing is fine

Root cause (instrumented TypeCombinator call counts): a call-count explosion in the conditional-expression machinery, not per-call work. On the reproducer, TypeCombinator::intersect is called 2.69M times at N=200 and 21.4M times at N=400 (~8x for 2x input), each on ~3 tiny args. Each === branch records a conditional relating $v to $x, and applying the accumulated conditionals re-intersects $v's growing type once per narrowing op, compounding to a super-linear number of small calls. (It's the conditional application, not holder storage: capping the per-target conditional holders had no effect on the time.)

Related shapes in the same family, for completeness:

• Literal-union subject !== chain. With /** @param 1|2|…|N $x */ and if ($x !== 1 && $x !== 2 && … && $x !== N), analysis is ~O(N^2.9) (≈7 s at N=200), here dominated by TypeCombinator::remove (≈11M calls at N=200 on ~2-member unions). The plain-string &&/|| version of this is already handled (the BooleanAnd/Or flattening optimisation, guarded by and-chain-truthy-blowup.php / or-chain-falsey-blowup.php); a literal-union subject appears to defeat that path.
• Large match (true) constant chain. match (true) { $x === 0 => …, $x === 1 => …, … } is ~O(N²) (≈5.7 s at N=400), while match ($value) over literal arms is fine (~0.8 s); it's the per-arm narrowing of the subject in match (true) that accumulates.

Did PHPStan help you today? Did it make you happy in any way?

Yes. This came out of profiling PHPStan against a few real codebases, and along the way it caught a number of genuine type issues. The reproducers and call-count numbers above are offered in the hope they make this one easy to dig into. Thanks for the tool.

[ondrejmirtes]

I'm currently refactoring relevant parts of the codebase to this problem. It's not finished yet (phpstan/phpstan-src#5857) but it's likely it will improve.

[SanderMuller]

Update after digging into this against #5857.

I built that branch at its current tip (125cf2209, which already migrates BinaryOp, Assign and Match off TypeResolvingExprHandler) and ran the reproducer against the branch's merge-base with 2.2.x, so the only variable is the refactor. Same machine, level 8, single process, result cache cold.

if ($x === i) $v = "i";	N=100	N=200	N=400
merge-base	0.81	3.19	21.27
#5857	0.89	3.19	21.14

The match (true) and literal-union shapes are unchanged too. The new world was active during the run (the array example from your PR description resolves to array{1, 2, 1, 3, 1, 2} in the same harness, where the merge-base gives array{1, (float|int), mixed, ...}), so an improvement would have shown up.

Instrumenting processConditionalExpressionsAfterSpecifying, the fixpoint loop and the holder scan are both linear, so neither is the cost. The whole thing is one line: MutatingScope.php:3915 runs about 2N times, each one intersect($v's growing union, the consequence union), and both operands are unions of disjoint constant scalars (for instance 0|'0'|'1'|'2'|'3'|'4' intersected with 0|'0'|'1'|'2'|'3'). intersect implements A & (B|C) by distributing A's members across B, so that is O(n*m) per call. It accounts for essentially every intersect call in the run (2.7M at N=200, 21M at N=400).

Since those operands are constant-scalar unions, the result is just their value-set intersection, which is O(n) with a value hash. A guarded fast-path in TypeCombinator::intersect for "two unions whose members are all constant scalars" takes N=400 from 20.9s to 2.3s on current 2.2.x, with TypeCombinatorTest (1167 tests) and NodeScopeResolverTest (1670 tests) green. It is independent of #5857 (the branch does not touch TypeCombinator), so it helps both current 2.2.x and the new world once it lands. I will open it as a standalone PR.

A milder super-linear residual remains after that fast-path (the conditional re-application itself, plus the union rebuild on a wide union), which the single-pass work or a width cap on the conditional union would be better placed to address than I am.

[staabm]

fixed by phpstan/phpstan-src#5935