Bug report
Deep || chains with instanceof checks cause O(n²) analysis time due to recursive scope merging in BooleanOrHandler::processExpr.
Unlike TypeSpecifier::specifyTypesInCondition which has a specifyTypesForFlattenedBooleanOr optimization for deep chains, BooleanOrHandler::processExpr always processes recursively. At each level, the left scope is merged with the right scope ($leftResult->getScope()->mergeWith($rightResult->getScope())). The merged scope's type for the variable being narrowed grows by one ObjectType per level. The subsequent TypeCombinator::union() inside scope merging must check isSuperTypeOf against all existing union members — O(k) per merge, O(n²) total.
With BOOLEAN_EXPRESSION_MAX_PROCESS_DEPTH raised from 4 to 128:
- 100
instanceof checks: 19s
- 200
instanceof checks: 186s
Investigation
The bottleneck is in BooleanOrHandler::processExpr (phpstan-src src/Analyser/ExprHandler/BooleanOrHandler.php, line 74-81):
$leftResult = $nodeScopeResolver->processExprNode($stmt, $expr->left, $scope, ...);
$leftFalseyScope = $leftResult->getFalseyScope();
$rightResult = $nodeScopeResolver->processExprNode($stmt, $expr->right, $leftFalseyScope, ...);
$leftMergedWithRightScope = $leftResult->getScope()->mergeWith($rightResult->getScope());
This method has no depth check (unlike resolveType at line 51). For n || terms, the recursive processExprNode on the left creates n levels of scope merging. Each merge adds one ObjectType to the union, and TypeCombinator::union(UnionType_k, ObjectType) does O(k) work in the non-scalar comparison loop.
A fix would require a flattened processExpr path for deep OR chains — similar to specifyTypesForFlattenedBooleanOr but for the full expression processing pipeline (including rule invocation, throw points, etc.). This is architecturally non-trivial since each arm currently depends on the previous arm's falsey scope.
Code snippet that reproduces the problem
<?php declare(strict_types = 1);
// Requires BOOLEAN_EXPRESSION_MAX_PROCESS_DEPTH raised to 128 to expose.
// At the default limit of 4, the depth check in resolveType masks the issue.
class C1 {} class C2 {} class C3 {} class C4 {} class C5 {}
class C6 {} class C7 {} class C8 {} class C9 {} class C10 {}
class C11 {} class C12 {} class C13 {} class C14 {} class C15 {}
class C16 {} class C17 {} class C18 {} class C19 {} class C20 {}
class C21 {} class C22 {} class C23 {} class C24 {} class C25 {}
class C26 {} class C27 {} class C28 {} class C29 {} class C30 {}
class C31 {} class C32 {} class C33 {} class C34 {} class C35 {}
class C36 {} class C37 {} class C38 {} class C39 {} class C40 {}
class C41 {} class C42 {} class C43 {} class C44 {} class C45 {}
class C46 {} class C47 {} class C48 {} class C49 {} class C50 {}
function test(object $x): void {
if (
$x instanceof C1 || $x instanceof C2 || $x instanceof C3 || $x instanceof C4 || $x instanceof C5 ||
$x instanceof C6 || $x instanceof C7 || $x instanceof C8 || $x instanceof C9 || $x instanceof C10 ||
$x instanceof C11 || $x instanceof C12 || $x instanceof C13 || $x instanceof C14 || $x instanceof C15 ||
$x instanceof C16 || $x instanceof C17 || $x instanceof C18 || $x instanceof C19 || $x instanceof C20 ||
$x instanceof C21 || $x instanceof C22 || $x instanceof C23 || $x instanceof C24 || $x instanceof C25 ||
$x instanceof C26 || $x instanceof C27 || $x instanceof C28 || $x instanceof C29 || $x instanceof C30 ||
$x instanceof C31 || $x instanceof C32 || $x instanceof C33 || $x instanceof C34 || $x instanceof C35 ||
$x instanceof C36 || $x instanceof C37 || $x instanceof C38 || $x instanceof C39 || $x instanceof C40 ||
$x instanceof C41 || $x instanceof C42 || $x instanceof C43 || $x instanceof C44 || $x instanceof C45 ||
$x instanceof C46 || $x instanceof C47 || $x instanceof C48 || $x instanceof C49 || $x instanceof C50
) {
echo get_class($x);
}
}Expected output
Analysis should complete in under 2 seconds. Currently takes ~19s (with BOOLEAN_EXPRESSION_MAX_PROCESS_DEPTH = 128).
Bug report
Deep
||chains withinstanceofchecks cause O(n²) analysis time due to recursive scope merging inBooleanOrHandler::processExpr.Unlike
TypeSpecifier::specifyTypesInConditionwhich has aspecifyTypesForFlattenedBooleanOroptimization for deep chains,BooleanOrHandler::processExpralways processes recursively. At each level, the left scope is merged with the right scope ($leftResult->getScope()->mergeWith($rightResult->getScope())). The merged scope's type for the variable being narrowed grows by oneObjectTypeper level. The subsequentTypeCombinator::union()inside scope merging must checkisSuperTypeOfagainst all existing union members — O(k) per merge, O(n²) total.With
BOOLEAN_EXPRESSION_MAX_PROCESS_DEPTHraised from 4 to 128:instanceofchecks: 19sinstanceofchecks: 186sInvestigation
The bottleneck is in
BooleanOrHandler::processExpr(phpstan-srcsrc/Analyser/ExprHandler/BooleanOrHandler.php, line 74-81):This method has no depth check (unlike
resolveTypeat line 51). For n||terms, the recursiveprocessExprNodeon the left creates n levels of scope merging. Each merge adds oneObjectTypeto the union, andTypeCombinator::union(UnionType_k, ObjectType)does O(k) work in the non-scalar comparison loop.A fix would require a flattened
processExprpath for deep OR chains — similar tospecifyTypesForFlattenedBooleanOrbut for the full expression processing pipeline (including rule invocation, throw points, etc.). This is architecturally non-trivial since each arm currently depends on the previous arm's falsey scope.Code snippet that reproduces the problem
Expected output
Analysis should complete in under 2 seconds. Currently takes ~19s (with
BOOLEAN_EXPRESSION_MAX_PROCESS_DEPTH = 128).