mirror of
https://github.com/astral-sh/ruff.git
synced 2026-11-21 20:29:20 +08:00
## 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>
4.6 KiB
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]