Skip to content

Commit 680cce4

Browse files
authored
[ty] Optimize inherited recursive protocol comparisons (#27922)
Generic classes inheriting recursive protocols can repeatedly expand the same protocol interface when contextual constructor inference or diagnostic collection binds explicitly constrained method receivers. Programs with several inherited recursive members then become pathologically slow. Check finite requirements first for nominally inherited protocols, and stop expanding recursive requirements once their constraints establish the inherited relationship. Preserve full structural checking when it remains necessary for erased type parameters, overridden requirements, concrete-source inference, or diagnostic explanations. Also restrict eager receiver-compatibility checks to overload selection, where they actually prune candidates, so single-method binding does not recursively re-enter the protocol. Part of astral-sh/ty#4269. ## Ecosystem impact Werkzeug gains two overload errors and two unused-ignore warnings because improved contextual inference preserves the actual `sorted` callback argument instead of widening it to `object`. This exposes its existing `int | None` sort key; the old lambda-line ignore no longer covers the call-level error. ## Test plan - Protocol mdtests cover contextual constructor inference, invalid constructor arguments, empty-iterable `Never` inference, concrete/symbolic/unknown constrained receivers, erased type parameters recovered structurally, and overridden recursive requirements. - A diagnostic snapshot preserves nested protocol-member explanations during context collection. - A constraint-support test verifies exact type-variable identities without treating declaration-default metadata as semantic support. - Separate benchmarks cover recursive-protocol constructor inference and diagnostic collection.
1 parent 974d3cb commit 680cce4

7 files changed

Lines changed: 357 additions & 8 deletions

File tree

‎crates/ruff_benchmark/benches/ty.rs‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -863,6 +863,60 @@ fn benchmark_many_protocol_members_mismatch(criterion: &mut Criterion) {
863863
});
864864
}
865865

866+
/// Regression benchmarks for ty#4269: recursive protocol inference and assignment diagnostics.
867+
///
868+
/// Explicit receiver annotations can repeatedly expand inherited recursive protocol members
869+
/// during constructor inference or diagnostic collection.
870+
fn benchmark_inherited_recursive_protocol(criterion: &mut Criterion) {
871+
const NUM_METHODS: usize = 8;
872+
873+
setup_rayon();
874+
875+
let mut code = "\
876+
from __future__ import annotations
877+
878+
from collections.abc import Callable, Iterable
879+
from typing import Protocol
880+
881+
class Chain[T](Protocol):
882+
def value(self) -> T: ...
883+
"
884+
.to_string();
885+
886+
for i in 0..NUM_METHODS {
887+
writeln!(
888+
&mut code,
889+
" def method_{i}[A, B](self: Chain[tuple[A, B]], callback: Callable[[A, B], T]) -> Chain[T]: ..."
890+
)
891+
.ok();
892+
}
893+
894+
code.push_str("\nclass Concrete[T](Chain[T]):\n");
895+
code.push_str(" def __init__(self, values: Iterable[T]) -> None: ...\n");
896+
897+
for (name, scenario, expected_diagnostics) in [
898+
(
899+
"ty_micro[inherited_recursive_protocol_constructor]",
900+
"\nvalue: Chain[int] = Concrete(())\n",
901+
0,
902+
),
903+
(
904+
"ty_micro[inherited_recursive_protocol_diagnostic]",
905+
"\ndef diagnose[T](value: Concrete[T]) -> None:\n invalid: Chain[int] = value\n",
906+
1,
907+
),
908+
] {
909+
let code = format!("{code}{scenario}");
910+
criterion.bench_function(name, |b| {
911+
b.iter_batched_ref(
912+
|| setup_micro_case(&code),
913+
|case| assert_eq!(case.db.check().len(), expected_diagnostics),
914+
BatchSize::SmallInput,
915+
);
916+
});
917+
}
918+
}
919+
866920
/// Regression benchmark for large calls to a gradual variadic tail.
867921
///
868922
/// Without the gradual-call shortcut, every positional argument type is folded into the same
@@ -1621,6 +1675,7 @@ criterion_group!(
16211675
benchmark_mixed_str_enum_comparison,
16221676
benchmark_many_enum_members_2,
16231677
benchmark_many_protocol_members_mismatch,
1678+
benchmark_inherited_recursive_protocol,
16241679
benchmark_vararg_parameter_type_accumulation,
16251680
benchmark_very_large_tuple,
16261681
benchmark_large_union_narrowing,

‎crates/ty_python_semantic/resources/mdtest/diagnostics/error_context.md‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1272,6 +1272,51 @@ info: └── protocol member `check` is incompatible
12721272
info: └── parameter `y` has an incompatible type: `str` is not assignable to `bytes`
12731273
```
12741274

1275+
## Recursive protocol diagnostic context
1276+
1277+
A value-constrained type parameter makes the recursive `child` override valid for each permitted
1278+
specialization. The explicit receiver on `Outer.expose` preserves unresolved type variables while
1279+
diagnostic context is collected, including the incompatible recursive member and its return type.
1280+
1281+
```py
1282+
from __future__ import annotations
1283+
1284+
from typing import Protocol
1285+
1286+
class Chain[T](Protocol):
1287+
def child(self) -> Chain[T]: ...
1288+
def value(self) -> T: ...
1289+
1290+
class Outer[T](Protocol):
1291+
def expose(self: Outer[T]) -> Chain[T]: ...
1292+
1293+
class Concrete[T: (str, object)](Chain[T], Outer[T]):
1294+
def child(self) -> Concrete[str]:
1295+
raise NotImplementedError
1296+
1297+
def expose(self: Outer[T]) -> Concrete[T]:
1298+
raise NotImplementedError
1299+
1300+
def diagnose[T: (str, object)](value: Concrete[T]) -> None:
1301+
invalid: Outer[int] = value # snapshot: invalid-assignment
1302+
```
1303+
1304+
```snapshot
1305+
error[invalid-assignment]: Object of type `Concrete[T@diagnose]` is not assignable to `Outer[int]`
1306+
--> src/mdtest_snippet.py:20:27
1307+
|
1308+
20 | invalid: Outer[int] = value # snapshot: invalid-assignment
1309+
| ---------- ^^^^^ Incompatible value of type `Concrete[T@diagnose]`
1310+
| |
1311+
| Declared type
1312+
info: type `Concrete[T@diagnose]` is not assignable to protocol `Chain[int]`
1313+
info: └── protocol member `child` is incompatible
1314+
info: └── incompatible return types: `Concrete[str]` is not assignable to `Chain[int]`
1315+
info: └── type `Concrete[str]` is not assignable to protocol `Chain[int]`
1316+
info: └── protocol member `value` is incompatible
1317+
info: └── incompatible return types: `str` is not assignable to `int`
1318+
```
1319+
12751320
## Protocol method parameter names
12761321

12771322
Assignability errors against protocols are often caused because a method in the protocol class

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

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6684,6 +6684,137 @@ def check(value: Recursive[int]) -> None:
66846684
rejected: Recursive[str] = value # error: [invalid-assignment]
66856685
```
66866686

6687+
### Generic constructors inheriting recursive protocols
6688+
6689+
A generic constructor can infer its specialization from an expected recursive protocol even when the
6690+
protocol includes a method with an explicitly constrained receiver. Invalid constructor arguments
6691+
are rejected. Without an expected type, the empty tuple is an `Iterable[Never]`, so the constructor
6692+
infers `T = Never` regardless of the protocol's variance.
6693+
6694+
```toml
6695+
[environment]
6696+
python-version = "3.12"
6697+
```
6698+
6699+
```py
6700+
from __future__ import annotations
6701+
6702+
from collections.abc import Iterable
6703+
from typing import Protocol
6704+
6705+
class Chain[T](Protocol):
6706+
def value(self) -> T: ...
6707+
def combine[S](self: Chain[S], pair: tuple[S, T]) -> Chain[T]: ...
6708+
6709+
class Concrete[T](Chain[T]):
6710+
def __init__(self, values: Iterable[T]) -> None: ...
6711+
6712+
contextual: Chain[int] = Concrete(())
6713+
reveal_type(contextual) # revealed: Concrete[int]
6714+
wrong: Chain[int] = Concrete(("wrong",)) # error: [invalid-assignment]
6715+
reveal_type(Concrete(())) # revealed: Concrete[Never]
6716+
6717+
def make() -> Chain[int]:
6718+
return Concrete(())
6719+
```
6720+
6721+
### Specialized sources with constrained protocol receivers
6722+
6723+
A concrete class can inherit recursive methods with explicitly constrained receivers. Concrete,
6724+
symbolic, and unknown specializations bind those receivers and preserve the corresponding return
6725+
types.
6726+
6727+
```toml
6728+
[environment]
6729+
python-version = "3.12"
6730+
```
6731+
6732+
```py
6733+
from __future__ import annotations
6734+
6735+
from typing import Protocol
6736+
6737+
class Chain[T](Protocol):
6738+
def value(self) -> T: ...
6739+
def accumulate[S](self: Chain[S]) -> Chain[S]: ...
6740+
6741+
class Concrete[T](Chain[T]): ...
6742+
6743+
def check[T](concrete: Concrete[int], symbolic: Concrete[T]) -> None:
6744+
reveal_type(concrete.accumulate()) # revealed: Chain[int]
6745+
reveal_type(symbolic.accumulate()) # revealed: Chain[T@check]
6746+
reveal_type(Concrete().accumulate()) # revealed: Chain[Unknown]
6747+
```
6748+
6749+
### Structural inference from recursive protocol requirements
6750+
6751+
An inherited protocol specialization can erase a class type parameter. A recursive member can still
6752+
recover that parameter structurally, so satisfying the nominal relation is not enough to stop
6753+
collecting protocol constraints.
6754+
6755+
```toml
6756+
[environment]
6757+
python-version = "3.12"
6758+
```
6759+
6760+
```py
6761+
from __future__ import annotations
6762+
6763+
from collections.abc import Callable
6764+
from typing import Any, Protocol
6765+
6766+
class Recursive[A, B](Protocol):
6767+
first: A
6768+
def value(self, child: Recursive[Any, Any]) -> B: ...
6769+
6770+
class Erased[T, U](Recursive[T, Any]):
6771+
def value(self, child: Recursive[Any, Any]) -> U:
6772+
raise NotImplementedError
6773+
6774+
def __init__(self, callback: Callable[[U], object]) -> None: ...
6775+
6776+
pair: Recursive[int, str] = Erased(lambda value: reveal_type(value)) # revealed: str
6777+
```
6778+
6779+
### Overridden recursive protocol requirements
6780+
6781+
Recursive requirements remain significant when a concrete class overrides them. Their constraints
6782+
reject incompatible assignments and preserve generic inference.
6783+
6784+
```toml
6785+
[environment]
6786+
python-version = "3.12"
6787+
```
6788+
6789+
```py
6790+
from __future__ import annotations
6791+
6792+
from typing import Protocol
6793+
6794+
class Node[T](Protocol):
6795+
@property
6796+
def value(self) -> T: ...
6797+
@property
6798+
def child(self) -> Node[T]: ...
6799+
6800+
class Mismatched[T](Node[object]):
6801+
def __init__(self, value: T) -> None: ...
6802+
@property
6803+
def value(self) -> T:
6804+
raise NotImplementedError
6805+
6806+
@property
6807+
def child(self) -> Node[str]:
6808+
raise NotImplementedError
6809+
6810+
bad_assignment: Node[int] = Mismatched(1) # error: [invalid-assignment]
6811+
6812+
def extract[U](node: Node[U]) -> U:
6813+
raise NotImplementedError
6814+
6815+
reveal_type(extract(Mismatched(1))) # revealed: object
6816+
```
6817+
66876818
### Recursive legacy generic protocol
66886819

66896820
```py

‎crates/ty_python_semantic/src/types/constraints.rs‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -518,6 +518,14 @@ impl<'db, 'c> ConstraintSet<'db, 'c> {
518518
self.node == ALWAYS_TRUE
519519
}
520520

521+
/// Returns whether this constraint set mentions the given type-variable identity.
522+
pub(super) fn mentions_typevar(self, typevar: BoundTypeVarIdentity<'db>) -> bool {
523+
let storage = self.builder.storage.borrow();
524+
storage
525+
.node_support(self.node)
526+
.is_some_and(|support| support.iter().any(|id| storage.typevar_data(id) == typevar))
527+
}
528+
521529
/// Returns the constraints under which `lhs` is a subtype of `rhs`, assuming that the
522530
/// constraints in this constraint set hold. Panics if neither of the types being compared are
523531
/// a typevar. (That case is handled by `Type::has_relation_to`.)
@@ -7206,6 +7214,13 @@ mod tests {
72067214

72077215
assert_eq!(mentioned, vec![t.identity(db), u.identity(db)]);
72087216
assert!(support.is_complete());
7217+
7218+
let builder = ConstraintSetBuilder::new();
7219+
let constraint =
7220+
ConstraintSet::constrain_typevar_upper_bound(db, &env, &builder, t, actual_bound);
7221+
assert!(constraint.mentions_typevar(t.identity(db)));
7222+
assert!(constraint.mentions_typevar(u.identity(db)));
7223+
assert!(!constraint.mentions_typevar(metadata.identity(db)));
72097224
}
72107225

72117226
#[test]

0 commit comments

Comments
 (0)