Files
Shunsuke ShibayamaandCarl Meyer 160ffbf2cf [ty] Introduce Recursive types and fully support recursive implicit type aliases (#28425)
## Summary

Closes https://github.com/astral-sh/ty/issues/1738
(While this PR also resolves the error in the code provided in
https://github.com/astral-sh/ty/issues/1846, I consider the broader
issue under discussion to still be unresolved)

To fully support implicit type aliases, this PR introduces `Recursive`
types. These represent *structural recursive types*. In other words,
they are anonymous recursive types implicitly constructed through type
inference, rather than a nominally defined recursive type like PEP 695
recursive type aliases.

This is what was being discussed in
https://github.com/astral-sh/ruff/pull/24252#issuecomment-4172655350. We
are not introducing recursive types solely for implicit type aliases;
this is the first step toward completely replacing the current
`Divergent`-based approximate recursive type inference with a full
implementation.

Initially, I planned to completely remove the `Divergent` type alongside
the introduction of `Recursive` types, but because the scope of the
impact was far too large, I decided to replace it incrementally. Both
will coexist until the replacement is complete, but eventually,
everything should be replaced by `Recursive` types.

Following this PR, I plan to use the newly introduced `Recursive` types
to replace various forms of recursive type inference.

## Design

Currently, we approximate and treat recursive type structures generated
by recursive type inference as gradual types containing `Divergent`. For
example, a subscript on `x: Divergent` results in `x[n]: Divergent`.
Consequently, we get:

```
x: list[Divergent]
x[n]: Divergent
x[n][n]: Divergent
```

As a result, the type after subscripting loses the information that `x`
was a recursive list type. We solve this problem by introducing
recursive types.

`RecursiveType` is a binder for a body type that contains a recursive
variable. In other words, it roughly has the following structure:

```rust
struct RecursiveType<'db> {
    id: salsa::Id,
	body: Type<'db>,
	arguments: Option<Specialization<'db>>,
}

struct RecursiveVar<'db> {
    id: salsa::Id,
    arguments: Option<Specialization<'db>>,
}

enum Type<'db> {
    Recursive(RecursiveType<'db>),
    RecursiveVar(RecursiveVar<'db>),
    ...
}
```

For example, for the following implicit type alias:

```python
Tree = tuple[T, "Tree[list[T]] | None"]
# = μF. λT. tuple[T, F[list[T]] | None]
```

the constructed `RecursiveType` looks like this:

```rust
RecursiveType {
    id,
    body: tuple[T, RecursiveVar { id, arguments: [list[T]] } | None],
    arguments: [T]
}
```

Unlike `Divergent`, the recursive variable `RecursiveVar` has no type
properties on its own. Attempting to access this variable immediately
unfolds the recursive type, so questioning the typing properties of the
variable itself is meaningless. Therefore, if any type operation on
`RecursiveVar` appears, it should be a bug.

To infer the container subscript `x[1]` for `x: Tree[int]`, first unfold
`x`'s type. Unfolding replaces references to the recursive binder with
the recursive type itself. Writing `B[a := R]` for capture-avoiding
substitution of `R` for `a` in `B`:

```text
unfold(μa. B) = B[a := μa. B]
```

For `Tree[int]`, substitute the constructor for `F`, then apply `T :=
int`:

```text
unfold((μF. λT. tuple[T, F[list[T]] | None])[int])
= tuple[int, (μF. λT. tuple[T, F[list[T]] | None])[list[int]] | None]
(= tuple[int, Tree[list[int]] | None])
```

Tuple subscripting then selects the element at index 1: `x[1]:
Tree[list[int]] | None`.

## Test Plan

mdtest updated

---------

Co-authored-by: Carl Meyer <carl@astral.sh>
2026-09-18 04:01:49 +09:00

4.6 KiB

Subscripts involving type aliases

Aliases are expanded during analysis of subscripts.

[environment]
python-version = "3.12"

Non-recursive aliases

from typing_extensions import TypeAlias, Literal

ImplicitTuple = tuple[str, int, int]
PEP613Tuple: TypeAlias = tuple[str, int, int]
type PEP695Tuple = tuple[str, int, int]

ImplicitZero = Literal[0]
PEP613Zero: TypeAlias = Literal[0]
type PEP695Zero = Literal[0]

def f(
    implicit_tuple: ImplicitTuple,
    pep_613_tuple: PEP613Tuple,
    pep_695_tuple: PEP695Tuple,
    implicit_zero: ImplicitZero,
    pep_613_zero: PEP613Zero,
    pep_695_zero: PEP695Zero,
    invalid_bound: float,
):
    reveal_type(implicit_tuple[:2])  # revealed: tuple[str, int]
    reveal_type(implicit_tuple[implicit_zero])  # revealed: str
    reveal_type(implicit_tuple[pep_613_zero])  # revealed: str
    reveal_type(implicit_tuple[pep_695_zero])  # revealed: str
    implicit_tuple[invalid_bound:]  # error: [invalid-argument-type]

    reveal_type(pep_613_tuple[:2])  # revealed: tuple[str, int]
    reveal_type(pep_613_tuple[implicit_zero])  # revealed: str
    reveal_type(pep_613_tuple[pep_613_zero])  # revealed: str
    reveal_type(pep_613_tuple[pep_695_zero])  # revealed: str
    pep_613_tuple[invalid_bound:]  # error: [invalid-argument-type]

    reveal_type(pep_695_tuple[:2])  # revealed: tuple[str, int]
    reveal_type(pep_695_tuple[implicit_zero])  # revealed: str
    reveal_type(pep_695_tuple[pep_613_zero])  # revealed: str
    reveal_type(pep_695_tuple[pep_695_zero])  # revealed: str
    pep_695_tuple[invalid_bound:]  # error: [invalid-argument-type]

Recursive containers

Indexing a recursive list can produce either another list or a string. A subsequent string key is invalid for both alternatives, with one diagnostic for each. Both alias forms report the same errors.

Value = str | list["Value"]
type ExplicitValue = str | list[ExplicitValue]

def implicit(value: Value):
    # error: [invalid-argument-type] "on object of type `str`"
    # error: [invalid-argument-type] "on object of type `list[Value]`"
    value[0]["checksum"]

def explicit(value: ExplicitValue):
    # error: [invalid-argument-type] "on object of type `str`"
    # error: [invalid-argument-type] "on object of type `list[ExplicitValue]`"
    value[0]["checksum"]

Iteration over optional recursive containers

Iterating over a recursive list or string produces the same alternatives as indexing it. None additionally prevents iteration and subscripting.

Value = str | list["Value | None"]
type ExplicitValue = str | list[ExplicitValue | None]

def implicit(value: dict[str, Value | None]):
    # error: [invalid-argument-type] "on object of type `str`"
    # error: [invalid-argument-type] "on object of type `list[Value | None]`"
    # error: [not-subscriptable]
    # error: [not-iterable]
    [element["location"] for element in value["output"]]

def explicit(value: dict[str, ExplicitValue | None]):
    # error: [invalid-argument-type] "on object of type `str`"
    # error: [invalid-argument-type] "on object of type `list[ExplicitValue | None]`"
    # error: [not-subscriptable]
    # error: [not-iterable]
    [element["location"] for element in value["output"]]

Recursive path traversal

A path of string and integer keys cannot traverse arbitrary dictionaries and strings. Each incompatible combination is reported once, including after reassignment within a loop.

Value = dict[str, "Value"] | str
type ExplicitValue = dict[str, ExplicitValue] | str

def implicit(parent: Value, path: tuple[str | int, ...]):
    for segment in path:
        # error: [invalid-argument-type] "on object of type `dict[str, Value]`"
        # error: [invalid-argument-type] "on object of type `str`"
        parent = parent[segment]

def explicit(parent: ExplicitValue, path: tuple[str | int, ...]):
    for segment in path:
        # error: [invalid-argument-type] "on object of type `dict[str, ExplicitValue]`"
        # error: [invalid-argument-type] "on object of type `str`"
        parent = parent[segment]

Recursive keys

Overlapping alternatives in a key type also produce just one diagnostic for each invalid key type.

Key = str | list["Key"]
type ExplicitKey = str | list[ExplicitKey]

def implicit(value: list[int], key: Key | str):
    # error: [invalid-argument-type] "with key of type `str`"
    # error: [invalid-argument-type] "with key of type `list[Key]`"
    value[key]

def explicit(value: list[int], key: ExplicitKey | str):
    # error: [invalid-argument-type] "with key of type `str`"
    # error: [invalid-argument-type] "with key of type `list[ExplicitKey]`"
    value[key]