Psalm: Analysis is slow when analyzing arrays with lots of elements

[TysonAndre]

See https://github.com/vimeo/psalm/blob/3.0.13/src/Psalm/Internal/Analyzer/Statements/Expression/ArrayAnalyzer.php#L54-L141

It's looping over all of the array elements and building up a new array shape type by adding to an existing type. This is O(N^2) (quadratic runtime - It's 1000 times slower to copy an array with 1000 times more elements in an array shape being built up)

• https://github.com/adsr/phpspy was used to confirm that this was where the most time was being spent

What would be better would be to create a helper to combine an arbitrary number of union types, and call that after building up an array with the union type of each array value in ArrayAnalyzer->analyze.

I notice that CallMap.php was excluded, making this less noticeable. The same problem would occur on CallMap.php

        <ignoreFiles>
            <file name="src/Psalm/Internal/CallMap.php"/>

Using a mutable Type builder and calling builder->build() would probably be another way to avoid the slowness of copying large array shapes/union types - something like this but for psalm and using psalm's logic to merge array/object shapes

[muglug]

Thanks!

Running ./psalm src/Psalm/Internal/CallMap.php
Before: 130s
After: 3s