Skip to content

Improve inference SCC limiting code to avoid repeated inferring the same cycle #38517

@Keno

Description

@Keno

Part of the problem in talking about this issue is that we don't have great terminology,
so I'm gonna use some terminology that I think is reasonable, but we should probably
come up with some proper names for all these concepts and put them in the devdocs.

Consider a call cycle like

   +------------+
   v            +
E+>A+>B+>C+>B'+>D->E'
   ^
F+-+

Where B, B' are the same method with different signatures, (as are E and E').
Now, when inference see a method cycle like B->B' it has some heuristics to
decide whether to allow this or whether to "limit" the signature B' (e.g. by widening
some arguments to Any to force it to have strictly less information than B, thus
preventing infinitely growing types). However, when it does this it must also
"poison" all inference frames between B and B' (in this case C) to avoid
caching it. This is done such that if some other caller enters C, (without having
gone through B), it will not be subject to the same limiting.
Now, in the example above, we later discover that C is actually part of the
SCC (strongly-connected component) A,B,C,B',D. In this case, we should
be able to undo the limiting, because any entry point into the SCC will always
eventually see the B->B' method cycle forcing limiting. However, we need
to be a bit careful, because we could also be in the situation E->SCC->E'
in which case the entire SCC does actually need to be poisoned to avoid
pessimizing inference for F->SCC->E'.

Currently we only track a boolean for the limited flag, which is insufficient to
distinguish the above two cases. We should extend this information to track
which limiting decisions the current results depend on, then figuring out if
they are part of the current SCC or not.

As an additional refinement, we could also clear any limiting decisions that
don't actually affect the return value of the current function.

cc @NHDaly @Sacha0 @vtjnash

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions