[ty] Avoid false positive for not-iterable with no-positive intersection types#22089
[ty] Avoid false positive for not-iterable with no-positive intersection types#22089charliermarsh merged 13 commits intomainfrom
not-iterable with no-positive intersection types#22089Conversation
charliermarsh
changed the title
not-iterable with no-positive intersection typesnot-iterable with no-positive intersection types
Typing conformance resultsNo changes detected ✅ |
|
charliermarsh
requested review from
AlexWaygood,
carljm,
dcreager and
sharkdp
as code owners
Merging this PR will not alter performance
Comparing 
Footnotes
|
|
Ok, wasn't expecting that! |
|
This does look correct, but we obviously can't merge this if it causes the benchmarks to start timing out 🙃 I think we probably need to do similar for the |
charliermarsh
force-pushed
the
charlie/neg
branch
from
8bf771d to
905a38d
Compare
|
(Looking into it...) |
| // we treat `object` as the implicit positive element (e.g., `~str` is semantically | ||
| // `object & ~str`). | ||
| intersection | ||
| .positive_elements_or_object(db) |
There was a problem hiding this comment.
I expect this fallback to object is the source of the regression, and I'm surprised that we would need it here. If we are going to treat an intersection type with no positive elements as equivalent to object, then the only thing it can be a subtype of is object (and the only things it can be assignable to are Any/Unknown and object), and those cases should already be handled above. What was failing without this change? That is, in what form does the list[~str] iteration case reach here?
There was a problem hiding this comment.
~str can also be a subtype of a union, like ~str | int -- but I guess that's also handled by a higher-up branch.
There was a problem hiding this comment.
oh, and ~str & ~int is a subtype of both ~str and ~str & ~int, right?
There was a problem hiding this comment.
Yes, seems like we could add consideration of cases like that to get more precise results here, but that seems like a separate issue. We don't consider negative types in the intersection either before or after the current change in this PR. The only change here is to explicitly test object, which seems to me like it shouldn't be necessary (but clearly I'm missing something, if it makes the test in this PR pass.)
There was a problem hiding this comment.
I was just answering the immediate question, not trying to say that these cases were relevant. I think they're handled by the branch immediately above this one, anyway
There was a problem hiding this comment.
I am of course not an expert here but my understanding is that when we try_iterate over list[~str], we eventually check list.__iter__ which is def __iter__(self) -> Iterator[_T], and then need to infer specialization to determine that _T is ~str.
We then end up in has_relation_to_impl and in this big match on (self, target), self is an intersection (~str) and target is a type var (_T), which don't match any of the above cases... So we land in this case, and at present, intersection.positive(db).iter() is empty, so we return false.
There was a problem hiding this comment.
That makes sense. Sorry it took me a while to get back to this!
After thinking it over, I do feel like the change made here is correct and necessary. But the combination of benchmark and ecosystem results suggests that most of the time we still end up finding that object is not assignable to target (that is, in most cases this PR doesn't change our eventual behavior) -- but we now spend a fair amount of extra time reaching that conclusion.
Still, it would be great if we could bring down the perf impact more here. I feel like the most promising way to do that is probably more of what you already did? That is, find the next-most-common case (via profiling) where we spend a lot of time concluding that object is not assignable to something, and see if we can add a short-circuit test for that.
charliermarsh
force-pushed
the
charlie/neg
branch
2 times, most recently
from
a5cc211 to
6de4b1d
Compare
This handles the common case where we're checking if `object` (the implicit positive element of a pure negation like `~str`) is assignable to a generic type parameter like `_T` in `Iterator[_T]`. Co-Authored-By: Claude Opus 4.5 <[email protected]>
charliermarsh
force-pushed
the
charlie/neg
branch
from
70859e4 to
33f209b
Compare
|
Omg regression is gone. Now to remove all the fast paths and see if I can limit it to the last one. |
|
uhh we're back to a 39% regression after 01c4d3d 😆 |
This reverts commit 01c4d3d.
|
I will try to remove some of the fast paths, but the regression is gone at least. |
|
I think you can quite easily combine several of the fast paths. I don't think it's really necessary to have a separate comment for every one: diff --git a/crates/ty_python_semantic/src/types/relation.rs b/crates/ty_python_semantic/src/types/relation.rs
index efd95bdb30..32e2de1b35 100644
--- a/crates/ty_python_semantic/src/types/relation.rs
+++ b/crates/ty_python_semantic/src/types/relation.rs
@@ -662,18 +662,15 @@ impl<'db> Type<'db> {
ConstraintSet::from(true)
}
- // Fast path: `object` is not a subtype of any nominal instance type other than itself.
- // This is important for performance when checking intersections with no positive
- // elements (pure negations like `~str`), which are treated as having `object` as
- // the implicit positive element.
- (Type::NominalInstance(source), Type::NominalInstance(_)) if source.is_object() => {
- ConstraintSet::from(false)
- }
-
- // Fast path: `object` (an instance type) is not a subtype of any `type[X]` (a class type).
- (Type::NominalInstance(source), Type::SubclassOf(_)) if source.is_object() => {
- ConstraintSet::from(false)
- }
+ // Fast path for various types that we know `object` is never a subtype of
+ // (`object` can be a subtype of some protocols, but that case is handled above).
+ (
+ Type::NominalInstance(source),
+ Type::NominalInstance(_)
+ | Type::SubclassOf(_)
+ | Type::Callable(_)
+ | Type::ProtocolInstance(_),
+ ) if source.is_object() => ConstraintSet::from(false),
// Fast path: `object` is not a subtype of any non-inferable type variable, since the
// type variable could be specialized to a type smaller than `object`.
@@ -698,19 +695,6 @@ impl<'db> Type<'db> {
ConstraintSet::from(true)
}
- // Fast path: `object` is not a subtype of any callable type, since not all objects
- // are callable.
- (Type::NominalInstance(source), Type::Callable(_)) if source.is_object() => {
- ConstraintSet::from(false)
- }
-
- // Fast path: `object` is only a subtype/assignable to a protocol if the protocol
- // is equivalent to `object` (handled above). Otherwise, not all objects satisfy
- // the protocol.
- (Type::NominalInstance(source), Type::ProtocolInstance(_)) if source.is_object() => {
- ConstraintSet::from(false)
- }
-
// Fast path: `object` is only a subtype/assignable to unions that contain a type
// that can definitely accept `object`. If a union contains only types that cannot
// accept `object`, we can short-circuit to false. |
carljm
left a comment
carljm
left a comment
There was a problem hiding this comment.
Awesome! Great work eliminating the regression here.
* main: (76 commits) [ty] Improve the check for `NewType`s with generic bases (#22961) [ty] Ban legacy `TypeVar` bounds or constraints from containing type variables (#22949) Bump the typing conformance suite pin (#22960) [ty] Emit an error if a TypeVarTuple is used to subscript `Generic` or `Protocol` without being unpacked (#22952) [ty] Reduce false positives when subscripting classes generic over `TypeVarTuple`s (#22950) [ty] Detect invalid attempts to subclass `Protocol[]` and `Generic[]` simultaneously (#22948) Fix suppression indentation matching (#22903) Remove hidden `--output-format` warning (#22944) [ty] Validate signatures of dataclass `__post_init__` methods (#22730) [ty] extend special-cased `numbers` diagnostic to `invalid-argument-type` errors (#22938) [ty] Avoid false positive for `not-iterable` with no-positive intersection types (#22089) [ty] Preserve pure negation types in descriptor protocol (#22907) [ty] add special-case diagnostic for `numbers` module (#22931) [ty] Move the location of more `invalid-overload` diagnostics (#22933) [ty] Fix unary and comparison operators for TypeVars with union bounds (#22925) [ty] Rule Selection: ignore/warn/select all rules (unless subsequently overriden) (#22832) [ty] Fix TypedDict construction from existing TypedDict values (#22904) [ty] fix bug in string annotations and clean up diagnostics (#22913) [ty] Improve support for goto-type, goto-declaration, hover, and highlighting of string annotations (#22878) [ty] Rename old typing imports to new on `unresolved-reference`. (#22827) ...
3 participants
Summary
When checking if
list[~str]is iterable, we end up looking for a positive element to satisfy assignability toIterable[~str]. But when there are no positive elements, we returnfalse, rather than falling back toobject.Closes astral-sh/ty#1880.