Repository navigation
frozenset.__xor__ signature is wrong #16115
Description
This is also most likely the case of other comparators methods on builtins and ABCs.
In one phrase, frozenset.__xor__ on a AbstractSet will immediatly return NotImplemented, and fall-back to AbstractSet methods which have 0 guarantees of returning a frozenset instance.
Explanations
The frozenset method declares:
def __xor__(self, value: AbstractSet[_S], /) -> frozenset[_T_co | _S]:
"""Return self^value."""
...and the one for AbstractSet:
def __xor__(self, other: AbstractSet[_T], /) -> AbstractSet[_T_co | _T]: ...
But if we take a look at the actual C level implementation of frozenset.__xor__, it's easy to see why it's wrong.
PyAnySet_Check will only return true on an exact instance/subtype of set and frozenset,
not on subclasses/protocol compliant instances of collections.abc.Set.
As such, since it return NotImplemented if "value" is a subclass Foo of collections.abc.AbstractSet, it's Foo.__xor__ who's called.
The default impl of AbstractSet::__xor__ ( (Here you can see that the typing is wrong as well by being too strict, it accepts any Iterable):
def __xor__(self, other):
if not isinstance(other, Set):
if not isinstance(other, Iterable):
return NotImplemented
other = self._from_iterable(other)
return (self - other) | (other - self)So as you can see at this point we just call AbstractSet methods.
In my very own and very personal opinion I consider this design with NotImplemented a reallyy bad design in itself, but in any case this means that runtime behavior may be very different than what is expected from just looking at the typing signature.
Why it's an issue
In my current project pyochain, I'm reimplementing in Rust (by composition with python builtins, or from scratch) many python constructs, including most of collections.abc and frozenset.
to keep robustness, I ported manually many tests from cpython test suite.
I consider typeshed my primary source of truth for expected behavior (because it's much easier than looking in CPython code).
Recently, I ported a lot of tests for collections.abc, and even if my type checking was pristine, I still had many runtime errors when checking instances.
I then had to spend a few hours and many headscratchs to understand why it was like that when there's many "ball poking" between my new abstract PyoSet, my frozenset wrapper Set, and many combinations of __xor__, __rxor__ ,etc...
Reproducible example
You can use itertools.combinations_with_replacement instead of using my library if you want to quickly check it for yourself.
The class Base is directly taken from a class tested in cpython test suite.
from __future__ import annotations
from collections.abc import Iterable, Iterator
from collections.abc import Set as AbstractSet
from typing import override
from pyochain import Seq
class Base:
def __init__(self, elements: Iterable[object] = ()) -> None:
self.data: list[object] = []
for elem in elements:
if elem not in self.data:
self.data.append(elem)
@override
def __repr__(self) -> str:
return f"{self.__class__.__name__}({self.data.__class__.__name__})"
def __contains__(self, elem: object) -> bool:
return elem in self.data
def __iter__(self) -> Iterator[object]:
return iter(self.data)
def __len__(self) -> int:
return len(self.data)
class ImplAbcSet(Base, AbstractSet[object]):
pass
def main():
data = (
{1, 2, 3},
frozenset([3, 4, 5]),
ImplAbcSet([1, 2, 3]),
)
return Seq(data).iter().combinations_with_replacement(2).for_each_star(show)
def show(x: AbstractSet[object], y: AbstractSet[object]) -> AbstractSet[object]:
new = x ^ y
print(
x.__class__.__name__, "xor", y.__class__.__name__, "=>", new.__class__.__name__
)
return new
if __name__ == "__main__":
main()output:
set xor set => set
set xor frozenset => set
set xor ImplAbcSet => ImplAbcSet # not type safe!
frozenset xor frozenset => frozenset
frozenset xor ImplAbcSet => ImplAbcSet # not type safe!
ImplAbcSet xor ImplAbcSet => ImplAbcSetInlay hint (red is because of unused variable, not type error)
What I propose
To keep maximum robustness, overloads should be added. I'm not sure however if an exact tracking of every possible situations is even possible with current python typing possibilities.
EDIT:
got again bitten today by this :)
d = {1: 2}
d2 = {3: 4}
x = frozenset(d.keys()) & d2.keys()
print(x.__class__.__name__)output "set".
Activity
[-]`frozenset.__xor__` signatures is wrong[/-][+]`frozenset.__xor__` signature is wrong[/+]ekanshul commentedon Aug 16, 2026
I mapped the full behaviour on 3.14.2, since the report covers
^with three operand types and the picture across all four operators is what decides the fix shape. Each cell is the class of the result.&,|,-,^all behave identically, so one table covers them:setfrozensetsetsubclassfrozensetsubclassdict_keysdict_itemsSetimplfrozensetsetfrozensetsubclassBold cells are where the current stubs are wrong. The rule matches
PyAnySet_Checkexactly: a realset/frozensetor subclass takes the C path, anything else getsNotImplementedand the reflected method decides.Three things in there that I think matter for the fix, and that the report does not cover:
dict_keysanddict_itemsdo not behave like a generalSetimplementation. They returnset, not their own class. So they need to be their own case, not lumped into anAbstractSetfallback.A two-overload fix would regress
set. The obvious shape is aset | frozensetoverload plus anAbstractSetfallback. But look at thesetrow:set & some_dict.keys()returnssettoday and is typedsettoday, correctly. AnAbstractSetfallback would widen that toAbstractSetand make a very common pattern less precise. Getting this right without regressing needs a third case for the dict views.Subclasses do not survive. A
frozensetsubclass on the left returns plainfrozenset, not the subclass, which is worth knowing before anyone reaches forSelf.So a precise fix is three overloads per operator, times four operators, times
setandfrozenset— 24 overloads inbuiltins.pyi. That is a big change to the file type checkers hit hardest, and the tradeoff between precision and overload count is a call for maintainers rather than something to decide in a drive-by PR, so I have not sent one.Two narrower options if the full version is not wanted:
frozensetonly. Its row is wrong in three of seven columns andset's is wrong in one. Fixing justfrozensetgets most of the correctness for half the overloads and no regression risk on thesetside.frozenset.__and__and friends toAbstractSet[...]fixes the unsoundness in one line each, at the cost of precision for the commonfrozenset & frozensetcase. Probably too blunt, but it is the minimal sound change.Happy to implement whichever shape you prefer, with test cases covering the table above.
OutSquareCapital commentedon Aug 16, 2026
Yea I didn't even mention dict keys/items because they are far worse.
This is not typeshed fault tho, collections.abc code explicitly register them as ABCs even tough their behavior can differ completely at runtime. Worst offender is contains, an ABC will raise errors when a dict items/key will return false on some inputs. See my comment here on line 136:
https://github.com/OutSquareCapital/pyochain/blob/master/src/abc/views.rs
(I'm on my phone so I can't give precise line links)