Skip to content

Commit a0a1a35

Browse files
charliermarshcharliermarsh
authored
Merge 9f85c4a into e871de4 
2 parents e871de4 + 9f85c4a commit a0a1a35

12 files changed

Lines changed: 310 additions & 18 deletions

File tree

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2741,7 +2741,7 @@ class ManyCycles2:
27412741
self.x3 = [1]
27422742

27432743
def f1(self: "ManyCycles2"):
2744-
reveal_type(self.x3) # revealed: Unknown | list[int] | list[Divergent]
2744+
reveal_type(self.x3) # revealed: Unknown | list[int] | list[Divergent] | list[Unknown]
27452745

27462746
self.x1 = [self.x2] + [self.x3]
27472747
self.x2 = [self.x1] + [self.x3]

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

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1684,3 +1684,20 @@ def _(
16841684
reveal_type(nested_dict_int) # revealed: dict[str, Divergent]
16851685
reveal_type(nested_list_str) # revealed: list[Divergent]
16861686
```
1687+
1688+
### Materialization of self-referential generic implicit type aliases
1689+
1690+
```py
1691+
from typing import TypeVar, Union
1692+
from ty_extensions import Bottom, Top, is_subtype_of, static_assert
1693+
1694+
T = TypeVar("T")
1695+
K = TypeVar("K")
1696+
V = TypeVar("V")
1697+
1698+
NestedList = list["NestedList[T] | None"]
1699+
NestedDict = dict[K, Union[V, "NestedDict[K, V]"]]
1700+
1701+
static_assert(is_subtype_of(Bottom[NestedList[str]], Top[NestedList[str]]))
1702+
static_assert(is_subtype_of(Bottom[NestedDict[str, int]], Top[NestedDict[str, int]]))
1703+
```

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

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -347,6 +347,20 @@ my_isinstance(1, 1)
347347
my_isinstance(1, (int, (str, 1)))
348348
```
349349

350+
## Materialization of self-referential generic PEP 613 type aliases
351+
352+
```py
353+
from typing import TypeAlias, TypeVar, Union
354+
from ty_extensions import Bottom, Top, is_subtype_of, static_assert
355+
356+
K = TypeVar("K")
357+
V = TypeVar("V")
358+
359+
NestedDict: TypeAlias = dict[K, Union[V, "NestedDict[K, V]"]]
360+
361+
static_assert(is_subtype_of(Bottom[NestedDict[str, int]], Top[NestedDict[str, int]]))
362+
```
363+
350364
## Conditionally imported on Python < 3.10
351365

352366
```toml

‎crates/ty_python_semantic/src/types.rs‎

Lines changed: 139 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -257,7 +257,7 @@ pub(crate) struct VisitSpecialization;
257257
/// Similarly, there is `Bottom[list[Any]]`.
258258
/// This type is harder to make sense of in a set-theoretic framework, but
259259
/// it is a subtype of all materializations of `list[Any]`.
260-
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, get_size2::GetSize)]
260+
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, salsa::Update, get_size2::GetSize)]
261261
pub enum MaterializationKind {
262262
Top,
263263
Bottom,
@@ -779,13 +779,51 @@ impl<'db> Type<'db> {
779779
}
780780

781781
pub(crate) fn divergent(id: salsa::Id) -> Self {
782-
Self::Divergent(DivergentType { id })
782+
Self::Divergent(DivergentType::new(id))
783783
}
784784

785785
pub(crate) const fn is_divergent(&self) -> bool {
786786
matches!(self, Type::Divergent(_))
787787
}
788788

789+
/// Returns `true` if both `self` and `other` are `Divergent` types originating from the
790+
/// same cycle (i.e., sharing the same query ID), regardless of materialization state.
791+
fn same_divergent_marker(self, other: Type<'db>) -> bool {
792+
match (self, other) {
793+
(Type::Divergent(left), Type::Divergent(right)) => left.same_marker(right),
794+
_ => false,
795+
}
796+
}
797+
798+
/// If `self` is a materialized `Divergent` type, returns the concrete type it should
799+
/// behave as: `object` for top-materialized, `Never` for bottom-materialized.
800+
/// Returns `None` if `self` is not `Divergent` or has not been materialized.
801+
fn materialized_divergent_fallback(self) -> Option<Type<'db>> {
802+
let Type::Divergent(divergent) = self else {
803+
return None;
804+
};
805+
806+
match divergent.materialization_kind() {
807+
Some(MaterializationKind::Top) => Some(Type::object()),
808+
Some(MaterializationKind::Bottom) => Some(Type::Never),
809+
None => None,
810+
}
811+
}
812+
813+
/// Negating a divergent marker preserves the marker and flips its materialization, if any.
814+
fn negated_divergent(self) -> Option<Type<'db>> {
815+
let Type::Divergent(divergent) = self else {
816+
return None;
817+
};
818+
819+
Some(match divergent.materialization_kind() {
820+
Some(materialization_kind) => {
821+
Type::Divergent(divergent.materialized(materialization_kind.flip()))
822+
}
823+
None => Type::Divergent(divergent),
824+
})
825+
}
826+
789827
pub const fn is_unknown(&self) -> bool {
790828
matches!(
791829
self,
@@ -794,7 +832,14 @@ impl<'db> Type<'db> {
794832
}
795833

796834
pub(crate) const fn is_never(&self) -> bool {
797-
matches!(self, Type::Never)
835+
matches!(
836+
self,
837+
Type::Never
838+
| Type::Divergent(DivergentType {
839+
materialization: Some(MaterializationKind::Bottom),
840+
..
841+
})
842+
)
798843
}
799844

800845
/// Returns `true` if this type contains a `Self` type variable.
@@ -977,7 +1022,14 @@ impl<'db> Type<'db> {
9771022
}
9781023

9791024
pub(crate) const fn is_dynamic(&self) -> bool {
980-
matches!(self, Type::Dynamic(_) | Type::Divergent(_))
1025+
matches!(
1026+
self,
1027+
Type::Dynamic(_)
1028+
| Type::Divergent(DivergentType {
1029+
materialization: None,
1030+
..
1031+
})
1032+
)
9811033
}
9821034

9831035
const fn is_non_divergent_dynamic(&self) -> bool {
@@ -1552,7 +1604,11 @@ impl<'db> Type<'db> {
15521604
match self {
15531605
Type::Never => Type::object(),
15541606

1555-
Type::Dynamic(_) | Type::Divergent(_) => *self,
1607+
Type::Dynamic(_) => *self,
1608+
1609+
Type::Divergent(_) => (*self)
1610+
.negated_divergent()
1611+
.expect("matched `Type::Divergent` above"),
15561612

15571613
Type::NominalInstance(instance) if instance.is_object() => Type::Never,
15581614

@@ -1768,7 +1824,7 @@ impl<'db> Type<'db> {
17681824
div: Type<'db>,
17691825
nested: bool,
17701826
) -> Option<Self> {
1771-
if nested && self == div {
1827+
if nested && self.same_divergent_marker(div) {
17721828
return None;
17731829
}
17741830
match self {
@@ -2148,6 +2204,10 @@ impl<'db> Type<'db> {
21482204
name: &str,
21492205
policy: MemberLookupPolicy,
21502206
) -> Option<PlaceAndQualifiers<'db>> {
2207+
if let Some(fallback) = (*self).materialized_divergent_fallback() {
2208+
return fallback.find_name_in_mro_with_policy(db, name, policy);
2209+
}
2210+
21512211
match self {
21522212
Type::Union(union) => Some(union.map_with_boundness_and_qualifiers(db, |elem| {
21532213
elem.find_name_in_mro_with_policy(db, name, policy)
@@ -2486,6 +2546,10 @@ impl<'db> Type<'db> {
24862546
instance.unwrap_or_else(|| Type::none(db)).display(db),
24872547
owner.display(db)
24882548
);
2549+
if let Some(fallback) = self.materialized_divergent_fallback() {
2550+
return fallback.try_call_dunder_get(db, instance, owner);
2551+
}
2552+
24892553
match self {
24902554
Type::Callable(callable) if callable.is_staticmethod_like(db) => {
24912555
// For "staticmethod-like" callables, model the behavior of `staticmethod.__get__`.
@@ -2579,6 +2643,32 @@ impl<'db> Type<'db> {
25792643
instance: Option<Type<'db>>,
25802644
owner: Type<'db>,
25812645
) -> (PlaceAndQualifiers<'db>, AttributeKind) {
2646+
if let PlaceAndQualifiers {
2647+
place:
2648+
Place::Defined(DefinedPlace {
2649+
ty,
2650+
origin,
2651+
definedness,
2652+
widening,
2653+
}),
2654+
qualifiers,
2655+
} = attribute
2656+
&& let Some(fallback) = ty.materialized_divergent_fallback()
2657+
{
2658+
return Self::try_call_dunder_get_on_attribute(
2659+
db,
2660+
Place::Defined(DefinedPlace {
2661+
ty: fallback,
2662+
origin,
2663+
definedness,
2664+
widening,
2665+
})
2666+
.with_qualifiers(qualifiers),
2667+
instance,
2668+
owner,
2669+
);
2670+
}
2671+
25822672
match attribute {
25832673
// This branch is not strictly needed, but it short-circuits the lookup of various dunder
25842674
// methods and calls that would otherwise be made.
@@ -2894,6 +2984,10 @@ impl<'db> Type<'db> {
28942984
policy: MemberLookupPolicy,
28952985
) -> PlaceAndQualifiers<'db> {
28962986
tracing::trace!("member_lookup_with_policy: {}.{}", self.display(db), name);
2987+
if let Some(fallback) = self.materialized_divergent_fallback() {
2988+
return fallback.member_lookup_with_policy(db, name, policy);
2989+
}
2990+
28972991
if name == "__class__" {
28982992
return Place::bound(self.dunder_class(db)).into();
28992993
}
@@ -3466,6 +3560,10 @@ impl<'db> Type<'db> {
34663560
/// elements. It's usually best to only worry about "callability" relative to a particular
34673561
/// argument list, via [`try_call`][Self::try_call] and [`CallErrorKind::NotCallable`].
34683562
fn bindings(self, db: &'db dyn Db) -> Bindings<'db> {
3563+
if let Some(fallback) = self.materialized_divergent_fallback() {
3564+
return fallback.bindings(db);
3565+
}
3566+
34693567
match self {
34703568
Type::Callable(callable) => {
34713569
CallableBinding::from_overloads(self, callable.signatures(db).iter().cloned())
@@ -5536,9 +5634,14 @@ impl<'db> Type<'db> {
55365634
}
55375635
}
55385636
// `Divergent` is an internal cycle marker rather than a gradual type like `Any` or
5539-
// `Unknown`. Materializing it away would destroy the marker we rely on for recursive
5540-
// alias convergence.
5541-
Type::Divergent(_) => self,
5637+
// `Unknown`. Preserve the marker across materialization, while recording whether this
5638+
// occurrence should behave like the top (`object`) or bottom (`Never`) bound.
5639+
Type::Divergent(divergent) => match type_mapping {
5640+
TypeMapping::Materialize(materialization_kind) => {
5641+
Type::Divergent(divergent.materialized(*materialization_kind))
5642+
}
5643+
_ => self,
5644+
},
55425645

55435646
Type::Never
55445647
| Type::AlwaysTruthy
@@ -6422,11 +6525,38 @@ impl<'db> TypeMapping<'_, 'db> {
64226525
pub struct DivergentType {
64236526
/// The query ID that caused the cycle.
64246527
id: salsa::Id,
6528+
/// If this divergent marker has been materialized, preserve whether it should behave like the
6529+
/// top (`object`) or bottom (`Never`) bound while still remaining recognizable as divergent.
6530+
materialization: Option<MaterializationKind>,
64256531
}
64266532

64276533
// The Salsa heap is tracked separately.
64286534
impl get_size2::GetSize for DivergentType {}
64296535

6536+
impl DivergentType {
6537+
const fn new(id: salsa::Id) -> Self {
6538+
Self {
6539+
id,
6540+
materialization: None,
6541+
}
6542+
}
6543+
6544+
fn same_marker(self, other: Self) -> bool {
6545+
self.id == other.id
6546+
}
6547+
6548+
const fn materialized(self, kind: MaterializationKind) -> Self {
6549+
Self {
6550+
id: self.id,
6551+
materialization: Some(kind),
6552+
}
6553+
}
6554+
6555+
const fn materialization_kind(self) -> Option<MaterializationKind> {
6556+
self.materialization
6557+
}
6558+
}
6559+
64306560
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq, salsa::Update, get_size2::GetSize)]
64316561
pub enum DynamicType<'db> {
64326562
/// An explicitly annotated `typing.Any`

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

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,10 @@ impl<'db> Type<'db> {
4848
db: &'db dyn Db,
4949
policy: UpcastPolicy,
5050
) -> Option<CallableTypes<'db>> {
51+
if let Some(fallback) = self.materialized_divergent_fallback() {
52+
return fallback.try_upcast_to_callable_with_policy(db, policy);
53+
}
54+
5155
match self {
5256
Type::Callable(callable) => Some(CallableTypes::one(callable)),
5357

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

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,10 @@ use ruff_python_ast::name::Name;
88
use ty_module_resolver::{ModuleName, file_to_module};
99

1010
use super::protocol_class::ProtocolInterface;
11-
use super::{BoundTypeVarInstance, ClassType, KnownClass, SubclassOfType, Type, TypeVarVariance};
11+
use super::{
12+
BoundTypeVarInstance, ClassType, DivergentType, KnownClass, MaterializationKind,
13+
SubclassOfType, Type, TypeVarVariance,
14+
};
1215
use crate::place::PlaceAndQualifiers;
1316
use crate::semantic_index::definition::Definition;
1417
use crate::types::constraints::{
@@ -39,6 +42,10 @@ impl<'db> Type<'db> {
3942
matches!(
4043
self,
4144
Type::NominalInstance(NominalInstanceType(NominalInstanceInner::Object))
45+
| Type::Divergent(DivergentType {
46+
materialization: Some(MaterializationKind::Top),
47+
..
48+
})
4249
)
4350
}
4451

0 commit comments

Comments
 (0)