Performance problem - nested loops #8503
Description
Feature request
PHPStan can be really slow when analysing code like this:
<?php
class HelloWorld
{
public function test(): void
{
$matrix = [];
$db = new \PDO('conn');
$qry = $db->prepare('SELECT x FROM z');
$rows = $qry->fetchAll() ?: [];
foreach($rows as $row) {
$matrix[$row['x']] = [];
foreach($rows as $row2) {
$matrix[$row['x']][$row2['x']] = [];
foreach($rows as $row3) {
$matrix[$row['x']][$row2['x']][$row3['x']] = [];
foreach($rows as $row4) {
$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']] = [];
foreach($rows as $row5) {
$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']] = [];
foreach($rows as $row6) {
$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']] = [];
foreach($rows as $row7) {
$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']][$row7['x']] = [];
foreach($rows as $row8) {
$matrix[$row['x']][$row2['x']][$row3['x']][$row4['x']][$row5['x']][$row6['x']][$row7['x']][$row8['x']] = [];
}
}
}
}
}
}
}
}
}
}PHPStan analyses different PHP loops a similar way: Go through the loop, observe if the scope changes, “generalize” the scope. If the scope is different than the last time, re-run the same process up until 3 times. Use the final scope and run the analysis with the rules etc.
The generalization is a bit hazy, basically I’m trying to write some code that compares types and tries to figure out if the loop does $i++ vs. $i = 5, to see what the type should be in the final scope.
The problem is that my algorithm (here’s the foreach loop logic: https://github.com/phpstan/phpstan-src/blob/3c3b17f238d1ec085f74aee320e9dd321d1258d8/src/Analyser/NodeScopeResolver.php#L823-L846) is very ineffective with multiple nested loops
The more the loop is nested, the more times it’s going to be analysed. If I put var_dump($stmt->getLine()); at the beginning of the foreach handler in NodeScopeResolver, the output when analysing the linked file looks like this:
int(14)
int(17)
int(20)
int(23)
int(26)
int(29)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(29)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
int(35)
int(32)
int(35)
int(35)
…
And goes on like that for more than 3,000 times.
I'd like to know how compilers of different languages handle this effectively...