[red knot] support EllipsisType as a singleton

crates/red_knot_python_semantic/resources/mdtest/narrow/conditionals_is.md

@@ -0,0 +1,29 @@
+# Narrowing for `is` conditionals
+
+## `is None`
+
+```py
+x = None if flag else 1
+
+if x is None:
+    # TODO the following should be simplified to 'None'
+    reveal_type(x)  # revealed: None | Literal[1] & None
+
+reveal_type(x)  # revealed: None | Literal[1]
+```
+
+## `is` for other types
+
+```py
+class A:
+    ...
+
+x = A()
+y = x if flag else None
+
+if y is x:
+    # TODO the following should be simplified to 'A'
+    reveal_type(y)  # revealed: A | None & A
+
+reveal_type(y)  # revealed: A | None
+```

crates/red_knot_python_semantic/resources/mdtest/narrow/conditionals_is_not.md

@@ -0,0 +1,40 @@
+# Narrowing for `is not` conditionals
+
+## `is not None`
+
+The type guard removes `None` from the union type:
+
+```py
+x = None if flag else 1
+
+if x is not None:
+    reveal_type(x)  # revealed: Literal[1]
+
+reveal_type(x)  # revealed: None | Literal[1]
+```
+
+## `is not` for other singleton types
+
+```py
+x = True if flag else False
+reveal_type(x)  # revealed: bool
+
+if x is not False:
+    # TODO the following should be `Literal[True]`
+    reveal_type(x)  # revealed: bool & ~Literal[False]
+```
+
+## `is not` for non-singleton types
+
+Non-singleton types should *not* narrow the type: two instances of a
+non-singleton class may occupy different addresses in memory even if
+they compare equal.
+
+```py
+x = [1]
+y = [1]
+
+if x is not y:
+    # TODO: should include type parameter: list[int]
+    reveal_type(x)  # revealed: list
+```

crates/red_knot_python_semantic/resources/mdtest/narrow/match.md

@@ -0,0 +1,17 @@
+# Narrowing for `match` statements
+
+## Single `match` pattern
+
+```py
+x = None if flag else 1
+reveal_type(x)  # revealed: None | Literal[1]
+
+y = 0
+
+match x:
+    case None:
+        y = x
+
+# TODO intersection simplification: should be just Literal[0] | None
+reveal_type(y)  # revealed: Literal[0] | None | Literal[1] & None
+```

crates/red_knot_python_semantic/src/types.rs

@@ -463,6 +463,61 @@ impl<'db> Type<'db> {
         self == other
     }
 
+    /// Return true if there is just a single inhabitant for this type.
+    ///
+    /// Note: This function aims to have no false positives, but might return `false`
+    /// for more complicated types that are actually singletons.
+    pub(crate) fn is_singleton(self, db: &'db dyn Db) -> bool {
+        match self {
+            Type::Any
+            | Type::Never
+            | Type::Unknown
+            | Type::Todo
+            | Type::Unbound
+            | Type::IntLiteral(..)
+            | Type::StringLiteral(..)
+            | Type::BytesLiteral(..)
+            | Type::LiteralString => {
+                // Note: The literal types included in this pattern are not true singletons.
+                // There can be multiple Python objects (at different memory locations) that
+                // are both of type Literal[345], for example.
+                false
+            }
+            Type::None
+            | Type::BooleanLiteral(_)
+            | Type::Function(..)
+            | Type::Class(..)
+            | Type::Module(..) => true,
+            Type::Instance(class) => class.is_known(db, KnownClass::EllipsisType),
+            Type::Tuple(tuple) => {
+                // We deliberately deviate from the language specification [1] here and claim
+                // that the empty tuple type is a singleton type. The reasoning is that `()`
+                // is often used as a sentinel value in user code. Declaring the empty tuple to
+                // be of singleton type allows us to narrow types in `is not ()` conditionals.
+                //
+                // [1] https://docs.python.org/3/reference/expressions.html#parenthesized-forms
+                tuple.elements(db).is_empty()
+            }
+            Type::Union(..) => {
+                // A single-element union, where the sole element was a singleton, would itself
+                // be a singleton type. However, unions with length < 2 should never appear in
+                // our model due to [`UnionBuilder::build`].
+                false
+            }
+            Type::Intersection(..) => {
+                // Intersection types are hard to analyze. The following types are technically
+                // all singleton types, but it is not straightforward to compute this. Again,
+                // we simply return false.
+                //
+                //   bool & ~Literal[False]`
+                //   None & (None | int)
+                //   (A | B) & (B | C)          with A, B, C disjunct and B a singleton
+                //
+                false
+            }
+        }
+    }
+
     /// Resolve a member access of a type.
     ///
     /// For example, if `foo` is `Type::Instance(<Bar>)`,
@@ -840,6 +895,7 @@ pub enum KnownClass {
     GenericAlias,
     ModuleType,
     FunctionType,
+    EllipsisType,
     // Typeshed
     NoneType, // Part of `types` for Python >= 3.10
 }
@@ -850,17 +906,18 @@ impl<'db> KnownClass {
             Self::Bool => "bool",
             Self::Object => "object",
             Self::Bytes => "bytes",
-            Self::Tuple => "tuple",
+            Self::Type => "type",
             Self::Int => "int",
             Self::Float => "float",
             Self::Str => "str",
+            Self::List => "list",
+            Self::Tuple => "tuple",
             Self::Set => "set",
             Self::Dict => "dict",
-            Self::List => "list",
-            Self::Type => "type",
             Self::GenericAlias => "GenericAlias",
             Self::ModuleType => "ModuleType",
             Self::FunctionType => "FunctionType",
+            Self::EllipsisType => "EllipsisType",
             Self::NoneType => "NoneType",
         }
     }
@@ -882,7 +939,7 @@ impl<'db> KnownClass {
             | Self::Tuple
             | Self::Set
             | Self::Dict => builtins_symbol_ty(db, self.as_str()),
-            Self::GenericAlias | Self::ModuleType | Self::FunctionType => {
+            Self::GenericAlias | Self::ModuleType | Self::FunctionType | Self::EllipsisType => {
                 types_symbol_ty(db, self.as_str())
             }
             Self::NoneType => typeshed_symbol_ty(db, self.as_str()),
@@ -918,6 +975,7 @@ impl<'db> KnownClass {
             "NoneType" => Some(Self::NoneType),
             "ModuleType" => Some(Self::ModuleType),
             "FunctionType" => Some(Self::FunctionType),
+            "EllipsisType" => Some(Self::EllipsisType),
             _ => None,
         }
     }
@@ -939,7 +997,9 @@ impl<'db> KnownClass {
             | Self::Tuple
             | Self::Set
             | Self::Dict => module.name() == "builtins",
-            Self::GenericAlias | Self::ModuleType | Self::FunctionType => module.name() == "types",
+            Self::GenericAlias | Self::ModuleType | Self::FunctionType | Self::EllipsisType => {
+                module.name() == "types"
+            }
             Self::NoneType => matches!(module.name().as_str(), "_typeshed" | "types"),
         }
     }
@@ -1478,8 +1538,8 @@ pub struct TupleType<'db> {
 #[cfg(test)]
 mod tests {
     use super::{
-        builtins_symbol_ty, BytesLiteralType, StringLiteralType, Truthiness, TupleType, Type,
-        UnionType,
+        builtins_symbol_ty, types_symbol_ty, BytesLiteralType, StringLiteralType, Truthiness,
+        TupleType, Type, UnionType,
     };
     use crate::db::tests::TestDb;
     use crate::program::{Program, SearchPathSettings};
@@ -1514,6 +1574,7 @@ mod tests {
     enum Ty {
         Never,
         Unknown,
+        None,
         Any,
         IntLiteral(i64),
         BoolLiteral(bool),
@@ -1521,6 +1582,7 @@ mod tests {
         LiteralString,
         BytesLiteral(&'static str),
         BuiltinInstance(&'static str),
+        TypesModuleInstance(&'static str),
         Union(Vec<Ty>),
         Tuple(Vec<Ty>),
     }
@@ -1530,6 +1592,7 @@ mod tests {
             match self {
                 Ty::Never => Type::Never,
                 Ty::Unknown => Type::Unknown,
+                Ty::None => Type::None,
                 Ty::Any => Type::Any,
                 Ty::IntLiteral(n) => Type::IntLiteral(n),
                 Ty::StringLiteral(s) => {
@@ -1541,6 +1604,7 @@ mod tests {
                     Type::BytesLiteral(BytesLiteralType::new(db, s.as_bytes().into()))
                 }
                 Ty::BuiltinInstance(s) => builtins_symbol_ty(db, s).to_instance(db),
+                Ty::TypesModuleInstance(s) => types_symbol_ty(db, s).to_instance(db),
                 Ty::Union(tys) => {
                     UnionType::from_elements(db, tys.into_iter().map(|ty| ty.into_type(db)))
                 }
@@ -1618,6 +1682,29 @@ mod tests {
         assert!(from.into_type(&db).is_equivalent_to(&db, to.into_type(&db)));
     }
 
+    #[test_case(Ty::None)]
+    #[test_case(Ty::BoolLiteral(true))]
+    #[test_case(Ty::BoolLiteral(false))]
+    #[test_case(Ty::Tuple(vec![]))]
+    #[test_case(Ty::TypesModuleInstance("EllipsisType"))]
+    fn is_singleton(from: Ty) {
+        let db = setup_db();
+
+        assert!(from.into_type(&db).is_singleton(&db));
+    }
+
+    #[test_case(Ty::Never)]
+    #[test_case(Ty::IntLiteral(345))]
+    #[test_case(Ty::BuiltinInstance("str"))]
+    #[test_case(Ty::Union(vec![Ty::IntLiteral(1), Ty::IntLiteral(2)]))]
+    #[test_case(Ty::Tuple(vec![Ty::None]))]
+    #[test_case(Ty::Tuple(vec![Ty::None, Ty::BoolLiteral(true)]))]
+    fn is_not_singleton(from: Ty) {
+        let db = setup_db();
+
+        assert!(!from.into_type(&db).is_singleton(&db));
+    }
+
     #[test_case(Ty::IntLiteral(1); "is_int_literal_truthy")]
     #[test_case(Ty::IntLiteral(-1))]
     #[test_case(Ty::StringLiteral("foo"))]

crates/red_knot_python_semantic/src/types/infer.rs

@@ -5421,53 +5421,6 @@ mod tests {
         Ok(())
     }
 
-    #[test]
-    fn narrow_not_none() -> anyhow::Result<()> {
-        let mut db = setup_db();
-
-        db.write_dedented(
-            "/src/a.py",
-            "
-            x = None if flag else 1
-            y = 0
-            if x is not None:
-                y = x
-            ",
-        )?;
-
-        assert_public_ty(&db, "/src/a.py", "x", "None | Literal[1]");
-        assert_public_ty(&db, "/src/a.py", "y", "Literal[0, 1]");
-
-        Ok(())
-    }
-
-    #[test]
-    fn narrow_singleton_pattern() {
-        let mut db = setup_db();
-
-        db.write_dedented(
-            "/src/a.py",
-            "
-            x = None if flag else 1
-            y = 0
-            match x:
-                case None:
-                    y = x
-            ",
-        )
-        .unwrap();
-
-        // TODO: The correct inferred type should be `Literal[0] | None` but currently the
-        // simplification logic doesn't account for this. The final type with parenthesis:
-        // `Literal[0] | None | (Literal[1] & None)`
-        assert_public_ty(
-            &db,
-            "/src/a.py",
-            "y",
-            "Literal[0] | None | Literal[1] & None",
-        );
-    }
-
     #[test]
     fn while_loop() -> anyhow::Result<()> {
         let mut db = setup_db();

crates/red_knot_python_semantic/src/types/narrow.rs

@@ -155,13 +155,24 @@ impl<'db> NarrowingConstraintsBuilder<'db> {
             let inference = infer_expression_types(self.db, expression);
             for (op, comparator) in std::iter::zip(&**ops, &**comparators) {
                 let comp_ty = inference.expression_ty(comparator.scoped_ast_id(self.db, scope));
-                if matches!(op, ast::CmpOp::IsNot) {
-                    let ty = IntersectionBuilder::new(self.db)
-                        .add_negative(comp_ty)
-                        .build();
-                    self.constraints.insert(symbol, ty);
-                };
-                // TODO other comparison types
+                match op {
+                    ast::CmpOp::IsNot => {
+                        if comp_ty.is_singleton(self.db) {
+                            let ty = IntersectionBuilder::new(self.db)
+                                .add_negative(comp_ty)
+                                .build();
+                            self.constraints.insert(symbol, ty);
+                        } else {
+                            // Non-singletons cannot be safely narrowed using `is not`
+                        }
+                    }
+                    ast::CmpOp::Is => {
+                        self.constraints.insert(symbol, comp_ty);
+                    }
+                    _ => {
+                        // TODO other comparison types
+                    }
+                }
             }
         }
     }