Use constraint-set assignability (rather than assignability) when bounds contain negated types

crates/ty_python_semantic/resources/mdtest/regression/1880_list_not_iterable.md

@@ -0,0 +1,16 @@
+# `list[Not[str]]` is iterable
+
+This is a regression test for <https://github.com/astral-sh/ty/issues/1880>.
+
+```toml
+[environment]
+python-version = "3.11"
+```
+
+```py
+from ty_extensions import Not
+
+def foo(value: list[Not[str]]) -> None:
+    for item in value:
+        reveal_type(item)  # revealed: ~str
+```

crates/ty_python_semantic/resources/mdtest/regression/22500_heapq_unbound_typevar.md

@@ -0,0 +1,33 @@
+# Unconstrained typevars must satisfy heapq bounds
+
+This is a regression test for <https://github.com/astral-sh/ruff/pull/22500>.
+
+```toml
+[environment]
+python-version = "3.11"
+```
+
+```py
+from heapq import heappush
+from typing import Callable, TypeVar
+
+from _typeshed import SupportsRichComparison
+from ty_extensions import TypeOf, is_assignable_to, static_assert
+
+T = TypeVar("T")
+
+# `heappush` should only be assignable to callables that require a comparable typevar.
+static_assert(
+    not is_assignable_to(
+        TypeOf[heappush],
+        Callable[[list[T], T], None],
+    )
+)
+
+static_assert(
+    is_assignable_to(
+        TypeOf[heappush],
+        Callable[[list[SupportsRichComparison], SupportsRichComparison], None],
+    )
+)
+```

crates/ty_python_semantic/resources/mdtest/regression/22501_negated_bounds_dict_ops.md

@@ -0,0 +1,23 @@
+# Dict operations after narrowing should still be valid
+
+This is a regression test for <https://github.com/astral-sh/ruff/pull/22501>.
+
+```py
+from typing import Any
+
+class OrderedDict(dict[str, Any]):
+    def popitem(self) -> tuple[str, Any]:
+        if not self:
+            raise KeyError("dictionary is empty")
+        key = next(iter(self))
+        value = dict.pop(self, key)
+        return key, value
+
+def redact(kwargs: dict[str, Any | None]) -> None:
+    kwargs = {k: v for k, v in kwargs.items() if v is not None}
+    if "durationMS" in kwargs:
+        kwargs["durationMS"] = 1
+        _ = kwargs["durationMS"]
+    if "serviceId" in kwargs:
+        kwargs["serviceId"] = "srv"
+```

crates/ty_python_semantic/src/types/generics.rs

@@ -1,5 +1,5 @@
 use std::borrow::Cow;
-use std::cell::RefCell;
+use std::cell::{Cell, RefCell};
 use std::collections::hash_map::Entry;
 use std::fmt::Display;
 
@@ -1538,6 +1538,42 @@ pub(crate) struct SpecializationBuilder<'db> {
 pub(crate) type TypeVarAssignment<'db> = (BoundTypeVarIdentity<'db>, TypeVarVariance, Type<'db>);
 
 impl<'db> SpecializationBuilder<'db> {
+    fn contains_negated_type(&self, ty: Type<'db>) -> bool {
+        struct Visitor<'db> {
+            found: Cell<bool>,
+            recursion_guard: TypeCollector<'db>,
+        }
+
+        impl<'db> TypeVisitor<'db> for Visitor<'db> {
+            fn should_visit_lazy_type_attributes(&self) -> bool {
+                false
+            }
+
+            fn visit_type(&self, db: &'db dyn Db, ty: Type<'db>) {
+                if self.found.get() {
+                    return;
+                }
+                if let Type::Intersection(intersection) = ty {
+                    let has_non_truthiness_negation = intersection.negative(db).iter().any(|neg| {
+                        !matches!(neg, Type::AlwaysFalsy | Type::AlwaysTruthy) && !neg.is_none(db)
+                    });
+                    if has_non_truthiness_negation {
+                        self.found.set(true);
+                        return;
+                    }
+                }
+                walk_type_with_recursion_guard(db, ty, self, &self.recursion_guard);
+            }
+        }
+
+        let visitor = Visitor {
+            found: Cell::new(false),
+            recursion_guard: TypeCollector::default(),
+        };
+        visitor.visit_type(self.db, ty);
+        visitor.found.get()
+    }
+
     pub(crate) fn new(db: &'db dyn Db, inferable: InferableTypeVars<'db, 'db>) -> Self {
         Self {
             db,
@@ -1878,10 +1914,14 @@ impl<'db> SpecializationBuilder<'db> {
             {
                 match bound_typevar.typevar(self.db).bound_or_constraints(self.db) {
                     Some(TypeVarBoundOrConstraints::UpperBound(bound)) => {
-                        if !ty
-                            .when_assignable_to(self.db, bound, self.inferable)
-                            .is_always_satisfied(self.db)
+                        let constraints = if self.contains_negated_type(ty)
+                            || self.contains_negated_type(bound)
                         {
+                            ty.when_constraint_set_assignable_to(self.db, bound, self.inferable)
+                        } else {
+                            ty.when_assignable_to(self.db, bound, self.inferable)
+                        };
+                        if !constraints.satisfied_by_all_typevars(self.db, self.inferable) {
                             return Err(SpecializationError::MismatchedBound {
                                 bound_typevar,
                                 argument: ty,