Skip to content

Commit 3c8166b

Browse files
authored
[ty] Fix hang when negating recursive unions of instance types (#29652)
Fixes a hang when a recursive alias combines positive and negative references, such as `type A = list[A | ~A] | list[~A]`. Retain negated recursive aliases whose union members resolve to nominal instance types, so mapping does not repeatedly unfold the alias into itself. Other union members still undergo normalization to preserve literal exclusions and positive constraints. Fixes astral-sh/ty#4799. ## Test plan Checked the original reproducer and equivalent spellings using `Not[A]` and `Intersection[object, Not[A]]` with timeout-bounded debug binaries. The patched checker completes on all three; the original reproducer hangs on the baseline.
1 parent 3fd20e0 commit 3c8166b

5 files changed

Lines changed: 136 additions & 4 deletions

File tree

‎crates/ty_python_semantic/resources/mdtest/annotations/intersection_types.md‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -242,6 +242,46 @@ def _(c: C, d: D):
242242
reveal_type(d) # revealed: D
243243
```
244244

245+
## Negated recursive aliases in unions of containers
246+
247+
A recursive alias can appear positively and negatively in one container's element type and
248+
negatively in another union member.
249+
250+
Regression test for <https://github.com/astral-sh/ty/issues/4799>.
251+
252+
```toml
253+
[environment]
254+
python-version = "3.12"
255+
```
256+
257+
```py
258+
from typing import TypeAlias
259+
260+
type A = list[A | ~A] | list[~A]
261+
B: TypeAlias = "list[B | ~B] | list[~B]"
262+
263+
def _(a: A, b: B):
264+
reveal_type(a) # revealed: list[A | ~A] | list[~A]
265+
reveal_type(b) # revealed: B
266+
```
267+
268+
## Negated recursive aliases through an aliased container
269+
270+
The recursion can pass through another alias for a container in the union.
271+
272+
```toml
273+
[environment]
274+
python-version = "3.12"
275+
```
276+
277+
```py
278+
type Container = list[A | ~A]
279+
type A = Container | list[~A]
280+
281+
def _(value: A):
282+
reveal_type(value) # revealed: list[Divergent]
283+
```
284+
245285
## Intersections inside `type[...]`
246286

247287
```toml

‎crates/ty_python_semantic/resources/mdtest/narrow/type_guards.md‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1298,6 +1298,50 @@ def overwritten_target(value: object):
12981298
reveal_type(value) # revealed: TypeGuard[list[int] @ value] & ~AlwaysTruthy
12991299
```
13001300

1301+
## Negative TypeIs narrowing with recursive unions
1302+
1303+
Excluding a recursive union still exposes its literal exclusions. Removing `True` from `bool` leaves
1304+
a value whose truthiness is known.
1305+
1306+
```toml
1307+
[environment]
1308+
python-version = "3.12"
1309+
```
1310+
1311+
```py
1312+
from typing import Literal, assert_type
1313+
from typing_extensions import TypeIs
1314+
1315+
type RecursiveBool = Literal[True] | list[RecursiveBool]
1316+
1317+
def is_recursive_bool(value: object) -> TypeIs[RecursiveBool]:
1318+
raise NotImplementedError
1319+
1320+
def f(value: bool):
1321+
if not is_recursive_bool(value):
1322+
assert_type(bool(value), Literal[False])
1323+
```
1324+
1325+
Excluding an enum member also narrows the remaining members' `name` and `value` attributes.
1326+
1327+
```py
1328+
from enum import Enum
1329+
1330+
class Color(Enum):
1331+
RED = 1
1332+
BLUE = 2
1333+
1334+
type RecursiveColor = Literal[Color.RED] | list[RecursiveColor]
1335+
1336+
def is_recursive_color(value: object) -> TypeIs[RecursiveColor]:
1337+
raise NotImplementedError
1338+
1339+
def f(value: Color):
1340+
if not is_recursive_color(value):
1341+
assert_type(value.name, Literal["BLUE"])
1342+
assert_type(value.value, Literal[2])
1343+
```
1344+
13011345
## Recursive TypeIs targets
13021346

13031347
An unresolved recursive `TypeIs` target does not make the negative branch unreachable. We retain the

‎crates/ty_python_semantic/resources/mdtest/pep613_type_aliases.md‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -680,6 +680,26 @@ def f(x: B | Not[B]):
680680
reveal_type(x) # revealed: B | ~B
681681
```
682682

683+
## Negated recursive unions
684+
685+
Negating a recursive union is equivalent to intersecting the negations of its members, including
686+
when the alias contains gradual types.
687+
688+
```py
689+
from typing import Any, TypeAlias, TypeVar, assert_type
690+
from ty_extensions import Intersection, Not
691+
692+
A: TypeAlias = "int | list[tuple[Any, A]]"
693+
T = TypeVar("T")
694+
695+
def identity(x: T) -> T:
696+
return x
697+
698+
def f(x: Not[A], y: Intersection[Not[int], Not[list[tuple[Any, A]]]]):
699+
assert_type(identity(x), Intersection[Not[int], Not[list[tuple[Any, A]]]])
700+
assert_type(identity(y), Not[A])
701+
```
702+
683703
## Specializing non-generic recursive aliases
684704

685705
A recursive alias without type variables cannot be specialized. Quoting the entire definition does

‎crates/ty_python_semantic/resources/mdtest/pep695_type_aliases.md‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1868,6 +1868,25 @@ def f(x: Not[A], y: Not[list[tuple[Any, A]]]):
18681868
assert_type(identity(y), Not[A])
18691869
```
18701870

1871+
### Negated recursive unions
1872+
1873+
Negating a recursive union is equivalent to intersecting the negations of its members, including
1874+
when the alias contains gradual types.
1875+
1876+
```py
1877+
from typing import Any, assert_type
1878+
from ty_extensions import Intersection, Not
1879+
1880+
type A = int | list[tuple[Any, A]]
1881+
1882+
def identity[T](x: T) -> T:
1883+
return x
1884+
1885+
def f(x: Not[A], y: Intersection[Not[int], Not[list[tuple[Any, A]]]]):
1886+
assert_type(identity(x), Intersection[Not[int], Not[list[tuple[Any, A]]]])
1887+
assert_type(identity(y), Not[A])
1888+
```
1889+
18711890
### Recursive invariant
18721891

18731892
```py

‎crates/ty_python_semantic/src/types/set_theoretic/builder.rs‎

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1361,9 +1361,9 @@ impl<'db> IntersectionBuilder<'db> {
13611361
/// by default to preserve existing intersection normalization.
13621362
///
13631363
/// Unfolding aliases after their mapping has completed can repeatedly insert a recursive
1364-
/// type into itself, so mapped intersections retain positive aliases as well. The builder still
1365-
/// expands set operations to distribute and flatten them, and simplifies elements using their
1366-
/// alias values.
1364+
/// type into itself, so mapped intersections retain positive aliases as well. Direct unions and
1365+
/// intersections still distribute and flatten, and elements are simplified using their alias
1366+
/// values.
13671367
pub(crate) fn preserve_positive_aliases(mut self, preserve: bool) -> Self {
13681368
self.preserve_positive_aliases = preserve;
13691369
self
@@ -1605,7 +1605,16 @@ impl<'db> IntersectionBuilder<'db> {
16051605
Type::TypeAlias(_) | Type::Recursive(_) => {
16061606
self.add_negative_impl::<L>(ty, seen_aliases)?;
16071607
}
1608-
Type::Union(union) => {
1608+
// Retain recursive unions of instance types: their negations expose no positive
1609+
// constraints or literal exclusions, and unfolding during mapping can repeatedly
1610+
// insert the alias's body. Other members still need normalization, for example
1611+
// `bool & ~(Literal[True] | list[A])` simplifies to `Literal[False]`.
1612+
Type::Union(union)
1613+
if !union.elements(db).iter().all(|element| {
1614+
matches!(element.resolve_type_alias(db), Type::NominalInstance(_))
1615+
}) || (!matches!(original, Type::Recursive(_))
1616+
&& !matches!(original, Type::TypeAlias(alias) if alias.is_recursive(db))) =>
1617+
{
16091618
for elem in union.elements(db) {
16101619
self.add_negative_impl::<L>(*elem, seen_aliases)?;
16111620
}

0 commit comments

Comments
 (0)