Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

When using a large union type in an array key, analysis fails due to a wider type being picked for the array #8983

Closed
Ocramius opened this issue Dec 22, 2022 · 3 comments · Fixed by #9022
Closed

When using a large union type in an array key, analysis fails due to a wider type being picked for the array #8983

Ocramius opened this issue Dec 22, 2022 · 3 comments · Fixed by #9022

Comments

@Ocramius
Copy link
Contributor

Take following example @ https://psalm.dev/r/7158d77465 :

<?php

/** @psalm-type LargeUnion = self::* */
class SomeConstants
{
    const A0=0;
    const A1=1;
    const A2=2;
    const A3=3;
    const A4=4;
    const A5=5;
    const A6=6;
    const A7=7;
    const A8=8;
    const A9=9;
    const A10=10;
    const A11=11;
    const A12=12;
    const A13=13;
    const A14=14;
    const A15=15;
    const A16=16;
    const A17=17;
    const A18=18;
    const A19=19;
    const A20=20;
    const A21=21;
    const A22=22;
    const A23=23;
    const A24=24;
    const A25=25;
    const A26=26;
    const A27=27;
    const A28=28;
    const A29=29;
    const A30=30;
    const A31=31;
    const A32=32;
    const A33=33;
    const A34=34;
    const A35=35;
    const A36=36;
    const A37=37;
    const A38=38;
    const A39=39;
    const A40=40;
    const A41=41;
    const A42=42;
    const A43=43;
    const A44=44;
    const A45=45;
    const A46=46;
    const A47=47;
    const A48=48;
    const A49=49;
    const A50=50;
    const A51=51;
    const A52=52;
    const A53=53;
    const A54=54;
    const A55=55;
    const A56=56;
    const A57=57;
    const A58=58;
    const A59=59;
    const A60=60;
    const A61=61;
    const A62=62;
    const A63=63;
    const A64=64;
    const A65=65;
    const A66=66;
    const A67=67;
    const A68=68;
    const A69=69;
    const A70=70;
    const A71=71;
    const A72=72;
    const A73=73;
    const A74=74;
    const A75=75;
    const A76=76;
    const A77=77;
    const A78=78;
    const A79=79;
    const A80=80;
    const A81=81;
    const A82=82;
    const A83=83;
    const A84=84;
    const A85=85;
    const A86=86;
    const A87=87;
    const A88=88;
    const A89=89;
    const A90=90;
    const A91=91;
    const A92=92;
    const A93=93;
    const A94=94;
    const A95=95;
    const A96=96;
    const A97=97;
    const A98=98;
    const A99=99;
    const A100=100;
}

/** @return LargeUnion */
function produceValue(): int { throw new \Exception('irrelevant'); }

/** @param array<LargeUnion, mixed> $input */
function useUnion(array $input): void { throw new \Exception('irrelevant' . json_encode($input)); }

/** @psalm-trace $value */
$value = produceValue();
/** @psalm-trace $input */
$input = [$value => 'foo'];

useUnion($input);

While Psalm correctly understands $value being a LargeUnion, it gives up in the $input = [$value => 'foo']; expression, which becomes a non-empty-array<int<0, max>, 'foo'>:

Psalm output (using commit 390da64): 

INFO: [Trace](https://psalm.dev/224) - 116:1 - $value: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100

INFO: [Trace](https://psalm.dev/224) - 118:1 - $input: non-empty-array<int<0, max>, 'foo'>

ERROR: [InvalidArgument](https://psalm.dev/004) - 120:10 - Argument 1 of useUnion expects array<0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100, mixed>, but non-empty-array<int<0, max>, 'foo'> provided

The maxShapedArraySize="1000" configuration does not seem to help here either.

Reducing to less than 30 constants fixes the problem ( https://psalm.dev/r/c17fe8ddca ) , making it a look for 30 in the codebase:

<?php

/** @psalm-type LargeUnion = self::* */
class SomeConstants
{
    const A0=0;
    const A1=1;
    const A2=2;
    const A3=3;
    const A4=4;
    const A5=5;
    const A6=6;
    const A7=7;
    const A8=8;
    const A9=9;
    const A10=10;
    const A11=11;
    const A12=12;
    const A13=13;
    const A14=14;
    const A15=15;
    const A16=16;
    const A17=17;
    const A18=18;
    const A19=19;
    const A20=20;
    const A21=21;
    const A22=22;
    const A23=23;
    const A24=24;
    const A25=25;
    const A26=26;
    const A27=27;
    const A28=28;
    const A29=29;
}

/** @return LargeUnion */
function produceValue(): int { throw new \Exception('irrelevant'); }

/** @param array<LargeUnion, mixed> $input */
function useUnion(array $input): void { throw new \Exception('irrelevant' . json_encode($input)); }

/** @psalm-trace $value */
$value = produceValue();
/** @psalm-trace $input */
$input = [$value => 'foo'];

useUnion($input);
Psalm output (using commit 390da64): 

INFO: [Trace](https://psalm.dev/224) - 45:1 - $value: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29

INFO: [Trace](https://psalm.dev/224) - 47:1 - $input: non-empty-array<0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29, 'foo'>

I found some relevant code references:

  • psalm/src/Psalm/Internal/Analyzer/Statements/Expression/SimpleTypeInferer.php

    Lines 513 to 567 in 390da64

    private static function inferArrayType(
    Codebase $codebase,
    NodeDataProvider $nodes,
    PhpParser\Node\Expr\Array_ $stmt,
    Aliases $aliases,
    FileSource $file_source = null,
    ?array $existing_class_constants = null,
    ?string $fq_classlike_name = null
    ): ?Union {
    if (count($stmt->items) === 0) {
    return Type::getEmptyArray();
    }
    $array_creation_info = new ArrayCreationInfo();
    foreach ($stmt->items as $item) {
    if ($item === null) {
    continue;
    }
    if (!self::handleArrayItem(
    $codebase,
    $nodes,
    $array_creation_info,
    $item,
    $aliases,
    $file_source,
    $existing_class_constants,
    $fq_classlike_name,
    )) {
    return null;
    }
    }
    $item_key_type = null;
    if ($array_creation_info->item_key_atomic_types) {
    $item_key_type = TypeCombiner::combine(
    $array_creation_info->item_key_atomic_types,
    null,
    false,
    true,
    30,
    );
    }
    $item_value_type = null;
    if ($array_creation_info->item_value_atomic_types) {
    $item_value_type = TypeCombiner::combine(
    $array_creation_info->item_value_atomic_types,
    null,
    false,
    true,
    30,
    );
    }

  • psalm/src/Psalm/Internal/Analyzer/Statements/Expression/ArrayAnalyzer.php

    Lines 57 to 106 in 390da64

    class ArrayAnalyzer
    {
    public static function analyze(
    StatementsAnalyzer $statements_analyzer,
    PhpParser\Node\Expr\Array_ $stmt,
    Context $context
    ): bool {
    // if the array is empty, this special type allows us to match any other array type against it
    if (count($stmt->items) === 0) {
    $statements_analyzer->node_data->setType($stmt, Type::getEmptyArray());
    return true;
    }
    $codebase = $statements_analyzer->getCodebase();
    $array_creation_info = new ArrayCreationInfo();
    foreach ($stmt->items as $item) {
    if ($item === null) {
    IssueBuffer::maybeAdd(
    new ParseError(
    'Array element cannot be empty',
    new CodeLocation($statements_analyzer, $stmt),
    ),
    );
    return false;
    }
    self::analyzeArrayItem(
    $statements_analyzer,
    $context,
    $array_creation_info,
    $item,
    $codebase,
    );
    }
    if (count($array_creation_info->item_key_atomic_types) !== 0) {
    $item_key_type = TypeCombiner::combine(
    $array_creation_info->item_key_atomic_types,
    $codebase,
    false,
    true,
    30,
    );
    } else {
    $item_key_type = null;
    }
@psalm-github-bot
Copy link

I found these snippets:

https://psalm.dev/r/7158d77465 
<?php

/** @psalm-type LargeUnion = self::* */
class SomeConstants
{
    const A0=0;
    const A1=1;
    const A2=2;
    const A3=3;
    const A4=4;
    const A5=5;
    const A6=6;
    const A7=7;
    const A8=8;
    const A9=9;
    const A10=10;
    const A11=11;
    const A12=12;
    const A13=13;
    const A14=14;
    const A15=15;
    const A16=16;
    const A17=17;
    const A18=18;
    const A19=19;
    const A20=20;
    const A21=21;
    const A22=22;
    const A23=23;
    const A24=24;
    const A25=25;
    const A26=26;
    const A27=27;
    const A28=28;
    const A29=29;
    const A30=30;
    const A31=31;
    const A32=32;
    const A33=33;
    const A34=34;
    const A35=35;
    const A36=36;
    const A37=37;
    const A38=38;
    const A39=39;
    const A40=40;
    const A41=41;
    const A42=42;
    const A43=43;
    const A44=44;
    const A45=45;
    const A46=46;
    const A47=47;
    const A48=48;
    const A49=49;
    const A50=50;
    const A51=51;
    const A52=52;
    const A53=53;
    const A54=54;
    const A55=55;
    const A56=56;
    const A57=57;
    const A58=58;
    const A59=59;
    const A60=60;
    const A61=61;
    const A62=62;
    const A63=63;
    const A64=64;
    const A65=65;
    const A66=66;
    const A67=67;
    const A68=68;
    const A69=69;
    const A70=70;
    const A71=71;
    const A72=72;
    const A73=73;
    const A74=74;
    const A75=75;
    const A76=76;
    const A77=77;
    const A78=78;
    const A79=79;
    const A80=80;
    const A81=81;
    const A82=82;
    const A83=83;
    const A84=84;
    const A85=85;
    const A86=86;
    const A87=87;
    const A88=88;
    const A89=89;
    const A90=90;
    const A91=91;
    const A92=92;
    const A93=93;
    const A94=94;
    const A95=95;
    const A96=96;
    const A97=97;
    const A98=98;
    const A99=99;
    const A100=100;
}

/** @return LargeUnion */
function produceValue(): int { throw new \Exception('irrelevant'); }

/** @param array<LargeUnion, mixed> $input */
function useUnion(array $input): void { throw new \Exception('irrelevant' . json_encode($input)); }

/** @psalm-trace $value */
$value = produceValue();
/** @psalm-trace $input */
$input = [$value => 'foo'];

useUnion($input);
Psalm output (using commit 390da64):

INFO: Trace - 116:1 - $value: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100

INFO: Trace - 118:1 - $input: non-empty-array<int<0, max>, 'foo'>

ERROR: InvalidArgument - 120:10 - Argument 1 of useUnion expects array<0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100, mixed>, but non-empty-array<int<0, max>, 'foo'> provided
https://psalm.dev/r/c17fe8ddca 
<?php

/** @psalm-type LargeUnion = self::* */
class SomeConstants
{
    const A0=0;
    const A1=1;
    const A2=2;
    const A3=3;
    const A4=4;
    const A5=5;
    const A6=6;
    const A7=7;
    const A8=8;
    const A9=9;
    const A10=10;
    const A11=11;
    const A12=12;
    const A13=13;
    const A14=14;
    const A15=15;
    const A16=16;
    const A17=17;
    const A18=18;
    const A19=19;
    const A20=20;
    const A21=21;
    const A22=22;
    const A23=23;
    const A24=24;
    const A25=25;
    const A26=26;
    const A27=27;
    const A28=28;
    const A29=29;
}

/** @return LargeUnion */
function produceValue(): int { throw new \Exception('irrelevant'); }

/** @param array<LargeUnion, mixed> $input */
function useUnion(array $input): void { throw new \Exception('irrelevant' . json_encode($input)); }

/** @psalm-trace $value */
$value = produceValue();
/** @psalm-trace $input */
$input = [$value => 'foo'];

useUnion($input);
Psalm output (using commit 390da64):

INFO: Trace - 45:1 - $value: 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29

INFO: Trace - 47:1 - $input: non-empty-array<0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29, 'foo'>

@Ocramius Ocramius changed the title When using a large union type in an array key, analysis fails due to a wider type being picked for the array. When using a large union type in an array key, analysis fails due to a wider type being picked for the array Dec 22, 2022
@Ocramius
Copy link
Contributor Author

I've just seen how those code locations call TypeCombiner::combine() with an explicit $literal_limit.

Would it make sense to omit the argument there, and leave whichever healthy default in the TypeCombiner::combine() is in use? The default is 500 items, at the moment.

@orklah
Copy link
Collaborator

orklah commented Dec 23, 2022

We could try to do a PR with that. My main fear is performance, especially because we don't have tests to check performance so we wouldn't catch it. But go ahead, let's see if there's a notable change with Psalm itself

Ocramius added a commit to Ocramius/psalm that referenced this issue Dec 29, 2022
@Ocramius
Better type inference and type checking for large union types used in…
e6600fe 
… array keys/values

Fixes vimeo#8983

This patch adds a basic test showing that, when reaching a union type with 30 elements
or more, Psalm used to fail with an error, because the large union type got simplified
into a more general type as part of performance optimizations done in `TypeCombiner::combine()`.

This means that a type like `array<1|2|3|(etcetera...)|100, mixed>` was internally
simplified to `array<int, mixed>`, after reaching 30 elements or more, which in turn
led to problems and confusing errors when large union types are in play.

Such union types are relatively common in lookup-table-alike value objects.

By removing the hardcoded call-time limit of `30` types to be combined, we hereby
rely on the default `TypeCombiner::combine()` limit of `500` items, which is more
healthy.

This may come with some performance implications, but it is worth trying out, for
now.

Further parameters passed to `TypeCombiner::combine()` that were already matching
parameter default values were also omitted from the call-sites.
@Ocramius Ocramius mentioned this issue Dec 29, 2022
Merged
orklah added a commit that referenced this issue Dec 29, 2022
@orklah
Merge pull request #9022 from Ocramius/fix/#8983-allow-large-union-ty…
5bfb87c 
…pes-in-array-type-inference

Better type inference and type checking for large union types used in array keys/values
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
2 participants
@Ocramius @orklah