Visitar URL original
[ty] Bound aliased intersection expansion during inference (#28546) · astral-sh/ruff@c47e0cd · GitHub
Skip to content

Commit c47e0cd

Browse files
carljmcarljm
authored
[ty] Bound aliased intersection expansion during inference (#28546)
Aliased union upper bounds could bypass the intersection budget during generic inference, causing exponential expansion and apparent hangs. Apply the budget inside `IntersectionBuilder`, where aliases and negated intersections are expanded, so inference falls back to `Unknown` when the surviving alternatives exceed the limit. Preserve precise results for a single wide union and for intersections whose impossible or redundant alternatives reduce them below the budget. Apply narrowing factors before distributing multiple disjunctions, including aliased unions and negated intersection aliases. Addresses the pandas/NumPy alias case discussed in astral-sh/ty#4147. ## Test plan Extend legacy and PEP 695 callable-inference mdtests with nested aliases, overlapping aliased unions in either argument order, aliased and mixed explicit/aliased unions that exceed the budget, and recursive aliases. Cover negated intersection aliases with a narrowing literal upper bound in either argument order. Add unit coverage for narrowing factors in every position, negated alias expansion, and double negation.
1 parent ff4747b commit c47e0cd

5 files changed

Lines changed: 619 additions & 94 deletions

File tree

‎crates/ty_python_semantic/resources/mdtest/generics/legacy/callables.md‎

Lines changed: 202 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -269,6 +269,208 @@ reveal_type(generic_context(outside_callable(int_identity)))
269269
outside_callable(int_identity)("string")
270270
```
271271

272+
## Union without intersection does not consider budget
273+
274+
A single union upper bound remains precise even when it has more alternatives than the solution
275+
budget. Nested `TypeAliasType` aliases preserve the same result.
276+
277+
```py
278+
from typing import Callable, TypeVar
279+
from typing_extensions import TypeAliasType
280+
281+
T = TypeVar("T")
282+
283+
class A: ...
284+
class B: ...
285+
class C: ...
286+
class D: ...
287+
class E: ...
288+
289+
def infer_from_consumer(consumer: Callable[[T], None]) -> T:
290+
raise NotImplementedError
291+
292+
def consume(value: A | B | C | D | E) -> None: ...
293+
294+
reveal_type(infer_from_consumer(consume)) # revealed: A | B | C | D | E
295+
```
296+
297+
The aliases retain nested union members until inference expands them:
298+
299+
```py
300+
FirstTwo = TypeAliasType("FirstTwo", A | B)
301+
NextTwo = TypeAliasType("NextTwo", C | D)
302+
Options = TypeAliasType("Options", FirstTwo | NextTwo | E)
303+
304+
def consume_alias(value: Options) -> None: ...
305+
306+
reveal_type(infer_from_consumer(consume_alias)) # revealed: A | B | C | D | E
307+
```
308+
309+
## Overlapping inferred union upper bounds with few surviving alternatives
310+
311+
The individual union upper bounds can exceed the solution budget when only a few alternatives
312+
survive their intersection. Disjoint alternatives do not count toward the budget.
313+
314+
```py
315+
from typing import Callable, TypeVar, final
316+
from typing_extensions import TypeAliasType
317+
318+
T = TypeVar("T")
319+
320+
def infer_from_consumers(left: Callable[[T], None], right: Callable[[T], None]) -> T:
321+
raise NotImplementedError
322+
323+
@final
324+
class A: ...
325+
326+
@final
327+
class B: ...
328+
329+
@final
330+
class C: ...
331+
332+
@final
333+
class D: ...
334+
335+
@final
336+
class E: ...
337+
338+
@final
339+
class F: ...
340+
341+
@final
342+
class G: ...
343+
344+
@final
345+
class H: ...
346+
347+
def consume_left(value: A | B | C | D | E) -> None: ...
348+
def consume_right(value: A | B | F | G | H) -> None: ...
349+
350+
reveal_type(infer_from_consumers(consume_left, consume_right)) # revealed: A | B
351+
```
352+
353+
Aliases for these unions also preserve the precise intersection in either argument order:
354+
355+
```py
356+
Left = TypeAliasType("Left", A | B | C | D | E)
357+
Right = TypeAliasType("Right", A | B | F | G | H)
358+
359+
def consume_left_alias(value: Left) -> None: ...
360+
def consume_right_alias(value: Right) -> None: ...
361+
362+
reveal_type(infer_from_consumers(consume_left_alias, consume_right_alias)) # revealed: A | B
363+
reveal_type(infer_from_consumers(consume_right_alias, consume_left_alias)) # revealed: A | B
364+
```
365+
366+
## Intersecting aliased upper bounds exceeding the solution budget
367+
368+
Each consumer constrains `T` to a different union. The classes can share subclasses, so their
369+
intersection has eight distinct alternatives. Type aliases do not exempt this expansion from the
370+
solution budget: inference falls back to `Unknown` instead of constructing the entire intersection.
371+
372+
```py
373+
from typing import Callable, TypeVar
374+
from typing_extensions import TypeAliasType
375+
376+
T = TypeVar("T")
377+
378+
class A: ...
379+
class B: ...
380+
class C: ...
381+
class D: ...
382+
class E: ...
383+
class F: ...
384+
385+
First = TypeAliasType("First", A | B)
386+
Second = TypeAliasType("Second", C | D)
387+
Third = TypeAliasType("Third", E | F)
388+
389+
def infer_from_consumers(
390+
first: Callable[[T], None],
391+
second: Callable[[T], None],
392+
third: Callable[[T], None],
393+
) -> T:
394+
raise NotImplementedError
395+
396+
def consume_first(value: First) -> None: ...
397+
def consume_second(value: Second) -> None: ...
398+
def consume_third(value: Third) -> None: ...
399+
400+
reveal_type(infer_from_consumers(consume_first, consume_second, consume_third)) # revealed: Unknown
401+
```
402+
403+
The same budget applies when an explicit union is intersected with aliased unions:
404+
405+
```py
406+
def consume_explicit(value: E | F) -> None: ...
407+
408+
reveal_type(infer_from_consumers(consume_first, consume_second, consume_explicit)) # revealed: Unknown
409+
```
410+
411+
## Narrowing negated intersection aliases
412+
413+
The negation of an aliased intersection acts as a union of negations. Intersecting three such upper
414+
bounds can exceed the solution budget, but an additional literal upper bound leaves just one
415+
solution. We infer the literal regardless of the consumer order.
416+
417+
```py
418+
from typing import Callable, Literal, TypeVar
419+
from typing_extensions import TypeAliasType
420+
from ty_extensions import Intersection, Not
421+
422+
T = TypeVar("T")
423+
424+
class A: ...
425+
class B: ...
426+
class C: ...
427+
class D: ...
428+
class E: ...
429+
class F: ...
430+
431+
AB = TypeAliasType("AB", Intersection[A, B])
432+
CD = TypeAliasType("CD", Intersection[C, D])
433+
EF = TypeAliasType("EF", Intersection[E, F])
434+
435+
def infer_from_consumers(
436+
first: Callable[[T], None],
437+
second: Callable[[T], None],
438+
third: Callable[[T], None],
439+
fourth: Callable[[T], None],
440+
) -> T:
441+
raise NotImplementedError
442+
443+
def exclude_ab(value: Not[AB]) -> None: ...
444+
def exclude_cd(value: Not[CD]) -> None: ...
445+
def exclude_ef(value: Not[EF]) -> None: ...
446+
def consume_literal(value: Literal[5]) -> None: ...
447+
448+
reveal_type(infer_from_consumers(exclude_ab, exclude_cd, exclude_ef, consume_literal)) # revealed: Literal[5]
449+
reveal_type(infer_from_consumers(consume_literal, exclude_ab, exclude_cd, exclude_ef)) # revealed: Literal[5]
450+
```
451+
452+
## Intersecting recursive inferred union upper bounds
453+
454+
A recursive alias can contribute an upper bound without expanding its nested occurrences. Here, only
455+
`int` satisfies both consumers, regardless of their order.
456+
457+
```py
458+
from typing import Callable, TypeVar
459+
from typing_extensions import TypeAliasType
460+
461+
T = TypeVar("T")
462+
Recursive = TypeAliasType("Recursive", "int | list[Recursive]")
463+
464+
def infer_from_consumers(left: Callable[[T], None], right: Callable[[T], None]) -> T:
465+
raise NotImplementedError
466+
467+
def consume_recursive(value: Recursive) -> None: ...
468+
def consume_int_or_str(value: int | str) -> None: ...
469+
470+
reveal_type(infer_from_consumers(consume_recursive, consume_int_or_str)) # revealed: int
471+
reveal_type(infer_from_consumers(consume_int_or_str, consume_recursive)) # revealed: int
472+
```
473+
272474
## Overloaded callable as generic `Callable` argument
273475

274476
An overloaded callable should be assignable to a non-overloaded callable type when the overload set

‎crates/ty_python_semantic/resources/mdtest/generics/pep695/callables.md‎

Lines changed: 128 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -430,10 +430,22 @@ def consume(value: A | B | C | D | E) -> None: ...
430430
reveal_type(infer_from_consumer(consume)) # revealed: A | B | C | D | E
431431
```
432432

433-
## Overlapping inferred union upper bounds exceeding the solution budget
433+
The same union remains precise when it is defined through nested type aliases:
434434

435-
Even if the precise intersection of two large union upper bounds is small, processing either union
436-
currently exceeds the solution budget before we can discover that intersection.
435+
```py
436+
type FirstTwo = A | B
437+
type NextTwo = C | D
438+
type Options = FirstTwo | NextTwo | E
439+
440+
def consume_alias(value: Options) -> None: ...
441+
442+
reveal_type(infer_from_consumer(consume_alias)) # revealed: A | B | C | D | E
443+
```
444+
445+
## Overlapping inferred union upper bounds with few surviving alternatives
446+
447+
The individual union upper bounds can exceed the solution budget when only a few alternatives
448+
survive their intersection. Disjoint alternatives do not count toward the budget.
437449

438450
```py
439451
from typing import Callable, final
@@ -474,6 +486,119 @@ def consume_right(value: A | B | F | G | H) -> None: ...
474486
reveal_type(infer_from_consumers(consume_left, consume_right)) # revealed: A | B
475487
```
476488

489+
Aliases for these unions also preserve the precise intersection in either argument order:
490+
491+
```py
492+
type Left = A | B | C | D | E
493+
type Right = A | B | F | G | H
494+
495+
def consume_left_alias(value: Left) -> None: ...
496+
def consume_right_alias(value: Right) -> None: ...
497+
498+
reveal_type(infer_from_consumers(consume_left_alias, consume_right_alias)) # revealed: A | B
499+
reveal_type(infer_from_consumers(consume_right_alias, consume_left_alias)) # revealed: A | B
500+
```
501+
502+
## Intersecting aliased upper bounds exceeding the solution budget
503+
504+
Each consumer constrains `T` to a different union. The classes can share subclasses, so their
505+
intersection has eight distinct alternatives. Type aliases do not exempt this expansion from the
506+
solution budget: inference falls back to `Unknown` instead of constructing the entire intersection.
507+
508+
```py
509+
from typing import Callable
510+
511+
class A: ...
512+
class B: ...
513+
class C: ...
514+
class D: ...
515+
class E: ...
516+
class F: ...
517+
518+
type First = A | B
519+
type Second = C | D
520+
type Third = E | F
521+
522+
def infer_from_consumers[T](
523+
first: Callable[[T], None],
524+
second: Callable[[T], None],
525+
third: Callable[[T], None],
526+
) -> T:
527+
raise NotImplementedError
528+
529+
def consume_first(value: First) -> None: ...
530+
def consume_second(value: Second) -> None: ...
531+
def consume_third(value: Third) -> None: ...
532+
533+
reveal_type(infer_from_consumers(consume_first, consume_second, consume_third)) # revealed: Unknown
534+
```
535+
536+
The same budget applies when an explicit union is intersected with aliased unions:
537+
538+
```py
539+
def consume_explicit(value: E | F) -> None: ...
540+
541+
reveal_type(infer_from_consumers(consume_first, consume_second, consume_explicit)) # revealed: Unknown
542+
```
543+
544+
## Narrowing negated intersection aliases
545+
546+
The negation of an aliased intersection acts as a union of negations. Intersecting three such upper
547+
bounds can exceed the solution budget, but an additional literal upper bound leaves just one
548+
solution. We infer the literal regardless of the consumer order.
549+
550+
```py
551+
from typing import Callable, Literal
552+
from ty_extensions import Intersection, Not
553+
554+
class A: ...
555+
class B: ...
556+
class C: ...
557+
class D: ...
558+
class E: ...
559+
class F: ...
560+
561+
type AB = Intersection[A, B]
562+
type CD = Intersection[C, D]
563+
type EF = Intersection[E, F]
564+
565+
def infer_from_consumers[T](
566+
first: Callable[[T], None],
567+
second: Callable[[T], None],
568+
third: Callable[[T], None],
569+
fourth: Callable[[T], None],
570+
) -> T:
571+
raise NotImplementedError
572+
573+
def exclude_ab(value: Not[AB]) -> None: ...
574+
def exclude_cd(value: Not[CD]) -> None: ...
575+
def exclude_ef(value: Not[EF]) -> None: ...
576+
def consume_literal(value: Literal[5]) -> None: ...
577+
578+
reveal_type(infer_from_consumers(exclude_ab, exclude_cd, exclude_ef, consume_literal)) # revealed: Literal[5]
579+
reveal_type(infer_from_consumers(consume_literal, exclude_ab, exclude_cd, exclude_ef)) # revealed: Literal[5]
580+
```
581+
582+
## Intersecting recursive inferred union upper bounds
583+
584+
A recursive alias can contribute an upper bound without expanding its nested occurrences. Here, only
585+
`int` satisfies both consumers, regardless of their order.
586+
587+
```py
588+
from typing import Callable
589+
590+
type Recursive = int | list[Recursive]
591+
592+
def infer_from_consumers[T](left: Callable[[T], None], right: Callable[[T], None]) -> T:
593+
raise NotImplementedError
594+
595+
def consume_recursive(value: Recursive) -> None: ...
596+
def consume_int_or_str(value: int | str) -> None: ...
597+
598+
reveal_type(infer_from_consumers(consume_recursive, consume_int_or_str)) # revealed: int
599+
reveal_type(infer_from_consumers(consume_int_or_str, consume_recursive)) # revealed: int
600+
```
601+
477602
## Contextual generic return exceeding the solution budget
478603

479604
A generic call can receive an upper bound from the type context in which its return value is used.

0 commit comments

Comments
 (0)