phpstan: Exponential complexity when appending an array to itself

Bug report

The complexity of inferring the type of an array grows exponentially in the following case:

<?php
$row = [1];

if (rand()) {
	$row[] = $row;
}
// repeat the condition as many times as you want...

With 9 copies of the condition it takes 2.5s for me, with 10 it’s 7.3s and with 11 it’s 23.1s. I’m using version 1.5.2.

The issue is a bit similar to https://github.com/phpstan/phpstan/issues/4883 but it achieves exponential behavior in a different way.

About this issue

Original URL
State: open
Created 2 years ago
Comments: 17 (15 by maintainers)

Most upvoted comments

Also started looking into this, wish me luck xD Not gonna spend much time today, but the profiler is telling me already that TypeCombinator::union is doing a couple of calls here… And it is being called multiple times (not on this graph) via VariableTypeHolder::and. This is with 8 of those if blocks.

herndlm on Mar 30, 2022

alternatively: when appending constant-array types to another array keep track of the overall number of elements involved and reduce the type precision after a limit was reached

staabm on Mar 31, 2022

I think the array should somehow detect itself when being appended and realize “hey, this is me!” when calling setOffsetValueType.

ondrejmirtes on Mar 31, 2022

the analysis of a similar issue I worked on previously has been solved like

looking at the profiler graphs
realizing that TypeCombinator::union() is producing types with several 10.000s or even 100.000s of types
adding a debug_print_backtrace into TypeCombinator::union(), sorrounded by a if (count(types) > 10000) -> we see which part of the codebase is building up the huge unions
think about ways we can limit the analysis, so phpstan will no produce that huge union-types

staabm on Mar 30, 2022