Maybe related to https://bugs.python.org/issue8420

Somewhat obscure, but using only standard Python, and no frame- or gc-hacks, it looks like we can get a use-after-free:

from random import random

BADNESS = 0.0

class Bad:
    def __eq__(self, other):
        if random() < BADNESS:
            set1.clear()
        if random() < BADNESS:
            set2.clear()
        return True
    def __hash__(self):
        return 42

SIZE = 100
TRIALS = 10_000

ops = [
    "|", "|=",
    "==", "!=",
    "<", "<=",
    ">", ">=",
    # "&",  # crash!
    # "&=", # crash!
    "^",
    # "^=", # crash
    # "-", # crash
    "-=",
]

for op in ops:
    stmt = f"set1 {op} set2"
    print(stmt, "...")
    for _ in range(TRIALS):
        BADNESS = 0.00
        set1 = {Bad() for _ in range(SIZE)}
        set2 = {Bad() for _ in range(SIZE)}
        BADNESS = 0.02
        exec(stmt)
    print("ok.")

replacing `return True` with `return random() < 0.5` makes *all* of the operations crash, except for `|` and `|=`.

set1.isdisjoint(set2) also crashes

The likely culprit is the set_next() loop.  Perhaps it is never safe to use set_next() because any lookup can callback to __eq__ which can mutate the set.

Since set_isdisjoint() method isn't a mutating method, that is the easiest place to start investigating.  Try disabling the exact set fast path to see if the issue persists.

Presumably _PyDict_Next is also suspect.  Even the advertised "safe" calls to PyDict_SetItem() for existing keys would be a trigger.  Calling clear() in either __eq__ or __hash__ would suffice.

If the next loops are the culprint, the new challenge is figuring out how to fix it without wrecking code clarity and performance (and having to deprecate PyDict_Next() which is part of the stable ABI).

Marking as low priority given that ehe next loop code has been deployed without incident for two decades (a little less for sets and a little more for dicts).

It looks like usages of the PyDict_Next API assume the resulting references are borrowed and so INCREF them.

Usages of set_next do not, but should.

It should hopefully be a straightforward fix of adding INCREF/DECREFs.

Raised the priority back to normal.

I agree with Dennis's observation that PyDict_Next is safe, provided it's used as intended: it returns borrowed references, but to things that absolutely are legitimate at the time. In the presence of mutations, *what* it returns isn't defined at all, but I don't see a way for it to blow up (unless its caller screws up by believing it owns the references). It doesn't assume anything about the structure of the dict across calls.

New changeset 4a66615ba736f84eadf9456bfd5d32a94cccf117 by Dennis Sweeney in branch 'main':
bpo-46615: Don't crash when set operations mutate the sets (GH-31120)
https://github.com/python/cpython/commit/4a66615ba736f84eadf9456bfd5d32a94cccf117

New changeset 1f5fe9962f768c8bfd4ed06a22532d31d3424dc9 by Miss Islington (bot) in branch '3.10':
bpo-46615: Don't crash when set operations mutate the sets (GH-31120)
https://github.com/python/cpython/commit/1f5fe9962f768c8bfd4ed06a22532d31d3424dc9

New changeset c31b8a97a8a7e8255231c9e12ed581c6240c0d6c by Dennis Sweeney in branch '3.9':
bpo-46615: Don't crash when set operations mutate the sets (GH-31120) (GH-31312)
https://github.com/python/cpython/commit/c31b8a97a8a7e8255231c9e12ed581c6240c0d6c

Thanks Dennis for your report and PRs.

Do you mind to analyze also uses of _PySet_NextEntry(), PyDict_Next() and _PyDict_Next()? Many of them look safe, but _pickle.c seems vulnerable.

It does look like there are some pickle situations that crash. Attached is a randomized crasher. I haven't done too much careful reasoning about it, but adding INCREFs everywhere seems to fix most of the issues.