Understanding how a type checker processes frozenset([42])

[superbobry]

Hi everyone,

I am trying to build a mental model for how a type checker resolves the type of frozenset([42]) and I'm stuck at type argument inference. Could someone help me understand what is going on here?

frozenset is a generic class with a single covariant type parameter. It has an overloaded __new__ classmethod which uses a Self type:

class frozenset(AbstractSet[_T_co], Generic[_T_co]):
    @overload
    def __new__(cls: type[Self]) -> Self: ...
    @overload
    def __new__(cls: type[Self], __iterable: Iterable[_T_co]) -> Self: ...

A type checker will select the second overload based on the number of arguments passed to the call. Note that the overload is not generic, because __new__ is (implicitly) a classmethod, so _T_co in the type of __iterable is bound by the class and not __new__. The type of cls is less clear. According to PEP-673,

The behavior is to preserve the type argument of the object on which the method was called [...].

However, since __new__ is called implicitly, that type is also implicit. Is it frozenset[Any] or frozenset[_T_co]? If the latter, how does this work exactly?

• Is the class instantiated to its type parameters?
• Is Self bound to that instantiation? i.e. should Self in the return type also be treated as if it was frozenset[_T_co]?

[AlexWaygood]

The Self symbol that typeshed uses in the stub here isn't actually the PEP 673 Self type. Mypy will support typing(_extensions).Self in its next release, but doesn't yet support it in any released version, so we can't yet use it in typeshed. As a workaround in the meantime, typeshed defines a Self = TypeVar("Self") symbol in the stdlib/_typeshed/__init__.pyi file, and it's that symbol that you see being used in the stub here. It's just a TypeVar; PEP 673 is irrelevant here.

__new__ is (implicitly) a classmethod

Strictly speaking, it's actually an implicit staticmethod rather than an implicit classmethod :) The cls parameter is simply always passed in as the first argument, so it behaves as if it were a classmethod. But this detail is not particularly relevant here!

---

Addressing your question, I can't comment on how type checkers solve the problem, exactly. But if the type checker should understand the type of the created frozenset as being frozenset[_T_co], and then immediately solve _T_co as being int, therefore leading to the inferred type as being frozenset[int]. This is indeed what mypy does:

reveal_type(frozenset([42]))  # Revealed type is "builtins.frozenset[builtins.int]"

The constructor is typed such that a type checker should be able to easily infer the type of calls to subclasses, even if the __new__ method is not overridden on the subclass:

from typing import TypeVar

_T_co = TypeVar("_T_co")
class Foo(frozenset[_T_co]): ...
reveal_type(Foo([42]))  # Revealed type is "__main__.Foo[builtins.int]"

[superbobry]

I still find the substitution Self:Foo[S] magical, because AFAICT type checkers will have to special-case it, since the S there is S@Foo.

[superbobry]

Thanks @JelleZijlstra! Alex already corrected that. If __new__ is a static method, then _T_co is actually bound by the method and not the class and __new__ is generic. Is that how you think about it?

[erictraut]

Constructors necessarily involve significant special casing in Python type checkers. Here are some of the considerations and complexities in pyright's implementation. I presume that mypy and the other Python type checkers are similar.

1. As Alex said, __new__ is treated as a static method, not a bound class method.
2. A caller can explicitly specialize the class before calling the constructor (as in frozenset[float]([42])).
3. In addition to (or instead of) a __new__ method, there can be an __init__ method, which may also contain parameters whose types contain class-scoped type variables.
4. An __init__ method can have an annotated self parameter, which can affect the specialized type of the constructed object if the __init__ is overloaded.
5. If there is additional context (aka an "expected type"), bidirectional type inference must be applied.

x = set([42])
reveal_type(x) # set[int]
y: Iterable[float]
y = set([42])
reveal_type(y)  # set[float]

6. Metaclasses can provide a custom __call__, which causes the class's __new__ to be skipped.
7. It's possible for __new__ to return a type other than the class being constructed.

[superbobry]

Thanks Eric, that's very useful!

Does pyright actually support 6. and 7.?

[erictraut]

Does pyright actually support 6. and 7.?

Yes. For 6, it supports it the best that it can. There's no perfect solution in this case. If a metaclass implements a custom __call__, a type checker has no real way of knowing whether that metaclass calls through to the original __new__ and __init__ or completely ignores them. I've seen examples of both in the wild. Pyright conservatively assumes that the metaclass doesn't call through, so __new__ and __init__ are not checked in this case.

[superbobry]

There is still one more bit I don't quite understand.

If __new__ is a static method and static methods are not bound to the class (and thus cannot reference type parameters). What is _T_co in the signature of __new__? Is it a type parameter of __new__ in the same way Self is? If yes, what is the connection between _T_co@__new__ and _T_co@frozenset?

[superbobry]

Would the same be true for any other @staticmethod? E.g. is T here

class A(Generic[T]):
    @staticmethod
    def f(x: T) -> T: ...

also bound by the class?

[erictraut]

No, constructors are special. For regular static methods, it's assumed that you already have a (specialized) class type. As I mentioned above, type checkers contain a bunch of special casing for constructors.

[superbobry]

Sorry, just to make sure I got it right: a static method can only be invoked on an instantiated/specialized class type, so T in the above example is bound by the class?

Sadly, PEP-484 does not cover static methods at all, so this is undefined behavior.

[erictraut]

If you're unsure how it works, you can always try the sample in mypy or pyright.

[superbobry]

Okay, for the record

from typing import TypeVar, Generic
T = TypeVar('T')
class A(Generic[T]):
    @staticmethod
    def f(x: T):
         reveal_type(x)

outputs

pyright 1.1.257
/tmp/foo.py
  /tmp/foo.py:6:17 - information: Type of "x" is "T@A"

Thanks, Eric!