=| and &= allowed for immutable set ABC

[sanderr]

Bug Report

mypy seems to allow |= and &= for collections.abc.Set, which is an immutable set type. Its documentation declares that it doesn't offer the __ior__ and __iand__ methods. Indeed, mypy rejects the use of these methods directly, but it does allow |= and &=.

A consequence of this is that because collections.abc.Set is covariant in its element type, breaking out of its immutability allows breaking the Liskov substitution principle.

I've checked both the collections.abc and the typeshed implementation of the relevant types and as far as I can make out they seem to be defined in line with the documentation, so I assume this is a mypy issue, but I could be wrong about that.

To Reproduce

https://mypy-play.net/?mypy=latest&python=3.11&gist=ca538f567c30d410778f87454f9d3494

import collections.abc
from typing import TYPE_CHECKING

myset: collections.abc.Set[int] = {1}
if TYPE_CHECKING:
    reveal_type(myset)
alias: collections.abc.Set[int] = myset
myset |= {2}
# proof that the set object has been modified despite being declared immutable
assert alias == {1, 2}

# Consequence: break Liskov

class Parent: pass
class Child(Parent): pass

def f(s: collections.abc.Set[Parent]) -> None:
    # s should be immutable and yet we can extend it
    s |= {Parent()}

children: collections.abc.Set[Child] = {Child()}
# mypy allows this because the immutable `Set` is covariant in its element type.
# This is safe because, it being immutable, the method can not add elements to it.
# Except that with this bug it can, adding an `Parent` to a `Set[Child]`
f(children)
if TYPE_CHECKING:
    reveal_type(children)
# This should never happen
assert any(isinstance(child, Parent) for child in children)

Expected Behavior

I expected mypy to reject |= and &= for collections.abc.Set and only allow it for collections.abc.MutableSet.

Actual Behavior

Mypy finds no issues with the snippet:

main.py:6: note: Revealed type is "typing.AbstractSet[builtins.int]"
main.py:27: note: Revealed type is "typing.AbstractSet[__main__.Child]"
Success: no issues found in 1 source file

Your Environment

• Mypy version used: 0.931 locally, 1.0.0 on mypy-play.net
• Mypy command-line flags: none
• Mypy configuration options from mypy.ini (and other config files): none
• Python version used: 3.9 locally, 3.11 on mypy-play.net

[sanderr]

Loosely related to #11097 in the sense that |= and __ior__ behavior differ, but the focus of this ticket is different.

[TeamSpen210]

Hmm, mypy is sorta correct in its understanding here. It's assuming __ior__() isn't defined but __or__() is, meaning that a |= b is identical to a = a | b, reassigning to a copy of the set. If you replaced the set with a frozenset in your code, it would be both typesafe and act as "expected" by mypy. So this is really that sets themselves break Liskov...

[sanderr]

But it isn't identical: a |= b modifies the set object, while a = a | b is a reassignment to a new set. So in the presence of aliases (e.g. function parameters) there is a small but important difference:

a = {1}
b = a
a |= {2}

x = {1}
y = x
x = x | {2}

assert a == x
assert b != y
# b is modified
assert b == {1, 2}
# y is not
assert y == {1}

[sanderr]

It's assuming __ior__() isn't defined but __or__() is

I now realize this was the core of your message and I didn't respond to that. I agree with you that if only one is defined, the behavior would be identical. But with inheritance you can never be sure: collections.abc.Set is an abstract type that defines an interface. Some of its children may always extend it.

[sanderr]

But I have to admit that this complicates things. I need to give it some more thought and I'll report back.

[sanderr]

The problem is with the duality of |=. The docs say "These methods should attempt to do the operation in-place (modifying self) and return the result (which could be, but does not have to be, self). If a specific method is not defined, the augmented assignment falls back to the normal methods.". This means that from a typing perspective there really is no way to declare a type that offers one of the normal methods but not any self-modifying method. Therefore, there is no way to declare an immutable type with any of these operators.

I'm starting to realize that this is not an issue with mypy per se. Mypy could address the issue by e.g. only allowing the in-place operators when the in-place methods are explicitly defined. But I also see how that's an imperfect solution, and you may be hesitant to take that approach.

On the other hand, I also don't think it can be feasibly fixed by collections.abc.Set or typing.AbstractSet, because the data model just doesn't provide a way to differentiate the two (as far as I can see). This may be addressed in future versions of Python if there's sufficient motivation to do so, but in the meantime the only reasonable approach I see is to address it in the type checkers.

Therefore, while I'm hesitant to call it a bug in mypy, I'm inclined to say it's a shortcoming of Python's data model that limits the granularity with which static type checks can be applied. I think it would be fair to say that when such limitations pop up (and they can't be fixed in the language), it is the type checkers responsibility to account for them by erring on the side of correctness. The current behavior is overly lax, the trivial alternative would be overly restrictive. There may be a middle ground to be found, but if not, I think a type checker should at least aim to be correct and pick the overly restrictive approach.

Concretely, I would like to see the following: if an operator may have two different behaviors, only allow it when both behaviors are defined. The alternative is to keep it as is (as it's not technically a bug), but this would mean breaking collections.abc.Set and similar constructs. If you don't agree with my proposal to make this check more strict, perhaps the strict behavior could be added as an option?

[sterliakov]

For me, the mypy behaviour is expected here. __ior__, when called directly, is correctly rejected. |= is not - and should not be, IMO. I don't expect x += 1, where x is some int, to be rejected by mypy, despite x immutability (id(x) changes after such operation). Sets are no different, and it completely agrees with operator definition in the language, so that it falls back to some_set = some_set | other_set, if __ior__ is not defined explicitly. "Immutable set ABC" means only that there are no in-place modification implemented, and so you don't have update method or in-place |=. It is valid to create a new set, somehow related to the original one - for example, with new elements added.

[JukkaL]

One option would be to add an optional check (enabled by enabling a specific error code) that generates an error if |= is used with an abstract set.

[sanderr]

@sterliakov I agree with most of your message, but I think you're missing a relevant detail. builtins.set, which is supposed to be compatible with collections.abc.Set, does implement __ior__ in an in-place manner, so |= for builtins.set, does modify the object. This allows you to create a Set[Child] that actually contains instances of Parent (as in my initial example snippet), which should be a type violation.
Therefore, I'm strongly of the opinion that |= and the likes should be disallowed for collections.abc.Set. Whether this is mypy's responsibility is debatable (though I think it is). But I think that it is irrefutable that the current behavior leads to a type violation that is not reported.

[sanderr]

@JukkaL I would personally be in favor of a stricter approach, though I must admit I haven't fully figured out what/how yet. But if non consensus can be reached there I think what you suggest is a good middle ground.

[sanderr]

Perhaps there would be merit to extending that to all operators and all types that are an instance of abc.ABCMeta. I think it might make sense to expect all such types to declare the full extent of their interface explicitly (and I think they currently do). If they leave out e.g. __ior__ it is because it should not be called on its instances. Since it can never be statically known whether |= will call __or__ or __ior__, it should by extension not be allowed.
The looser behavior would then remain for non ABCMeta types, where the current behavior might make more sense.

This is just a rough idea at the moment. I still have to consider all implications.

[sanderr]

I've been thinking about this and its broader implications off and on for the past few weeks and I think that without making changes to Python's data model itself, the only correct approach would be to disallow the in-place operators unless the __i<operator>__ method is explicitly declared on the annotated type. Only in this case is the behavior of the in-place operator fully defined. In all other cases the binary nature of the operator (which is part of Python, not the type's interface) introduces uncontrolled polymorphism: behavior of the operator is overridden by introducing methods outside of the type's defined interface. I can't think of any other situation where this is the case, and I think it should be disallowed as a rule.

Put differently, if the type checker has to determine whether a certain method call is allowed on a type, it checks whether the type defines the method. Translating that to operators this would mean that an operator is allowed if the type defines the operator's behavior according to the Python specification. For an in-place operator this requires at least the in-place method to be defined because it is the primary entry point for the operator.

One aspect I'm still unclear on is that of primitives. They do not define the in-place operator but they are somewhat of a special case and of course the in-place operators should be allowed on them.

I understand this may be a breaking change and that if it would be introduced it might have to start as an opt-in strictness option, but since the current behavior allows you to actually produce type violations (for any generic type with a co-/contravariant parameter that supports an operator), I think it should eventually even become the default.

I would be interested to hear your thoughts on this. Do you see alternative options?