[ty] Limit argument expansion size for overload call evaluation#20041
[ty] Limit argument expansion size for overload call evaluation#20041dhruvmanila merged 5 commits intomainfrom
Conversation
Diagnostic diff on typing conformance testsNo changes detected when running ty on typing conformance tests ✅ |
|
dhruvmanila
force-pushed
the
dhruv/limit-argument-expansion-size
branch
from
61c5245 to
6df342d
Compare
...oads.md_-_Overloads_-_Argument_type_expans…_-_Optimization___Limit_…_(cd61048adbc17331).snap
Outdated
Show resolved
Hide resolved
dhruvmanila
requested review from
AlexWaygood,
carljm,
dcreager and
sharkdp
as code owners
...oads.md_-_Overloads_-_Argument_type_expans…_-_Optimization___Limit_…_(cd61048adbc17331).snap
Outdated
Show resolved
Hide resolved
I think it is good to move on from this issue now, if the limit takes care of the runaway problem on the fuzzer code sample, and we don't have reports of this in real code. But for future, I'm curious -- why is the above hard to implement? It sounds like a custom-implemented iterator that stores some state, which doesn't seem particularly unusual? |
I'll try to explain it using this example: One way to resolve this could be that we only maintain the expanded types and generate the combinations for each iteration manually i.e., in the above example, for the first argument, we'd generate 2 combinations by expanding Does this make sense? But, now that I think this out loud, maybe the second solution isn't too bad. |
…al-sh#20041) ## Summary This PR limits the argument type expansion size for an overload call evaluation to 512. The limit chosen is arbitrary but I've taken the 256 limit from Pyright into account and bumped it x2 to start with. Initially, I actually started out by trying to refactor the entire argument type expansion to be lazy. Currently, expanding a single argument at any position eagerly creates the combination (argument lists) and returns that (`Vec<CallArguments>`) but I thought we could make it lazier by converting the return type of `expand` from `Iterator<Item = Vec<CallArguments>>` to `Iterator<Item = Iterator<Item = CallArguments>>` but that's proving to be difficult to implement mainly because we **need** to maintain the previous expansion to generate the next expansion which is the main reason to use `std::iter::successors` in the first place. Another approach would be to eagerly expand all the argument types and then use the `combinations` from `itertools` to generate the combinations but we would need to find the "boundary" between arguments lists produced from expanding argument at position 1 and position 2 because that's important for the algorithm. Closes: astral-sh/ty#868 ## Test Plan Add test case to demonstrate the limit along with the diagnostic snapshot stating that the limit has been reached.
3 participants
Summary
This PR limits the argument type expansion size for an overload call evaluation to 512.
The limit chosen is arbitrary but I've taken the 256 limit from Pyright into account and bumped it x2 to start with.
Initially, I actually started out by trying to refactor the entire argument type expansion to be lazy. Currently, expanding a single argument at any position eagerly creates the combination (argument lists) and returns that (
Vec<CallArguments>) but I thought we could make it lazier by converting the return type ofexpandfromIterator<Item = Vec<CallArguments>>toIterator<Item = Iterator<Item = CallArguments>>but that's proving to be difficult to implement mainly because we need to maintain the previous expansion to generate the next expansion which is the main reason to usestd::iter::successorsin the first place.Another approach would be to eagerly expand all the argument types and then use the
combinationsfromitertoolsto generate the combinations but we would need to find the "boundary" between arguments lists produced from expanding argument at position 1 and position 2 because that's important for the algorithm.Closes: astral-sh/ty#868
Test Plan
Add test case to demonstrate the limit along with the diagnostic snapshot stating that the limit has been reached.