mirror of https://github.com/astral-sh/ruff
b36ff75a24
When inferring a specialization of a `Callable` type, we use the new constraint set implementation. In the example in https://github.com/astral-sh/ty/issues/1968, we end up with a constraint set that includes all of the following clauses: ``` U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M1 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M2 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M3 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M4 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M5 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M6 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 M7 ≤ U_co ≤ M1 | M2 | M3 | M4 | M5 | M6 | M7 ``` In general, we take the upper bounds of those constraints to get the specialization. However, the upper bounds of those constraints are not all guaranteed to be the same, and so first we need to intersect them all together. In this case, the upper bounds are all identical, so their intersection is trivial: ``` U_co = M1 | M2 | M3 | M4 | M5 | M6 | M7 ``` But we were still doing the work of calculating that trivial intersection 7 times. And each time we have to do 7^2 comparisons of the `M*` classes, ending up with O(n^3) overall work. This pattern is common enough that we can put in a quick heuristic to prune identical copies of the same type before performing the intersection. Fixes https://github.com/astral-sh/ty/issues/1968 |
||
|---|---|---|
| .. | ||
| legacy | ||
| pep695 | ||
| builtins.md | ||
| scoping.md | ||
| specialize_constrained.md | ||