MyPy is nondeterministic across runs

[wjakob]

Bug Report
I'm observing nondeterminism in MyPy runs on one of my programs. Sometimes, it accepts a file, sometimes it doesn't. Once it has accepted a file it seems to cache this solution, and I need to wipe .mypy_cache to be able to reproduce the random behavior again.

To Reproduce

Download and extract the following archive (repro.tar.gz), which contains stubs from a library I am developing along with a test.py file to be checked.

This is output from an actual run on my end:

$ mypy test.py
test.py:74: error: Incompatible types in assignment (expression has type "object", variable has type "Array3f")  [assignment]
Found 1 error in 1 file (checked 1 source file)

$ mypy test.py
Success: no issues found in 1 source file

Details on setup: mypy 1.8.0 (compiled: yes), Python 3.12.2, on an Apple M1 laptop (macOS 16.6.2). The machine is and has been perfectly stable. That is to say: I don't expect cosmic rays or RAM corruption to be responsible ;).

[bzoracler]

I'm not sure if this example reveals the same underlying issue, and I don't know how to simplify it further, but this is also non-deterministic across runs with --no-incremental; see mypy Playground.

# mypy: no-incremental, disable-error-code=empty-body

from __future__ import annotations

import typing_extensions as t

from functools import total_ordering


T = t.TypeVar("T", bound="_SupportsCompare")
U = t.TypeVar("U", bound="_SupportsCompare")

@total_ordering
class _SupportsCompare(t.Protocol):
    def __lt__(self, other: t.Any, /) -> bool: ...

class Comparable(_SupportsCompare):
    @t.override
    def __lt__(self, other: t.Any, /) -> bool: ...

class A(t.Generic[T, U]):
    @t.overload
    def __init__(self: A[T, T], a: T, b: T, /) -> None: ...  # type: ignore[overload-overlap]
    @t.overload
    def __init__(self: A[T, U], a: T, b: U, /) -> t.Never: ...
    def __init__(self, a: T, b: T | U, /) -> None: ...

comparable: Comparable = Comparable()

reveal_type(A(1, 1))
reveal_type(A(comparable, comparable))
reveal_type(A(1, comparable))
reveal_type(A(comparable, 1))

Tried on both 1.8.0 and master on the playground. The output is non-deterministically one of the following:

• main.py:30: note: Revealed type is "__main__.A[builtins.int, builtins.int]"
  main.py:31: note: Revealed type is "__main__.A[__main__.Comparable, __main__.Comparable]"
  main.py:32: note: Revealed type is "__main__.A[__main__._SupportsCompare, __main__._SupportsCompare]"
  main.py:33: note: Revealed type is "__main__.A[__main__._SupportsCompare, __main__._SupportsCompare]"
  Success: no issues found in 1 source file
  

• main.py:30: note: Revealed type is "__main__.A[builtins.int, builtins.int]"
  main.py:31: note: Revealed type is "__main__.A[__main__.Comparable, __main__.Comparable]"
  main.py:32: note: Revealed type is "Never"
  Success: no issues found in 1 source file
  

[hauntsaninja]

Thanks for the repros! I haven't yet looked in wjakob's but bzoracler's non-determinism seems to be coming from mypy.solve.solve_with_dependent / mypy.solve.solve_one. The lowers, uppers produced in solve_with_dependent are sets. The order they are iterated in solve_one determines which result you get.

Slightly more minimised version:

from __future__ import annotations

import typing_extensions as t

T = t.TypeVar("T")
U = t.TypeVar("U")

class _SupportsCompare(t.Protocol):
    def __lt__(self, other: t.Any, /) -> bool:
        return True

class Comparable(_SupportsCompare):
    pass

class A(t.Generic[T, U]):
    @t.overload
    def __init__(self: A[T, T], a: T, b: T, /) -> None: ...  # type: ignore[overload-overlap]
    @t.overload
    def __init__(self: A[T, U], a: T, b: U, /) -> t.Never: ...
    def __init__(self, *a) -> None: ...

comparable: Comparable = Comparable()

reveal_type(A(1, comparable))

[hauntsaninja]

Hmm maybe issue is non-commutativity in join_types

[hauntsaninja]

I think something like this could fix:

diff --git a/mypy/join.py b/mypy/join.py
index bf88f43d8..a81714bf1 100644
--- a/mypy/join.py
+++ b/mypy/join.py
@@ -167,6 +167,15 @@ class InstanceJoiner:
             if best is None or is_better(res, best):
                 best = res
         assert best is not None
+        # Go over both sets of bases in case there's an explicit Protocol base. This is important
+        # to ensure commutativity of join (although in cases where both classes have relevant Protocol
+        # bases this maybe might still not be commutative)
+        for base in s.type.bases:
+            mapped = map_instance_to_supertype(s, base.type)
+            res = self.join_instances(t, mapped)
+            if is_better(res, best):
+                best = res
+
         for promote in t.type._promote:
             if isinstance(promote, Instance):
                 res = self.join_instances(promote, s)

[wjakob]

@hauntsaninja I applied your patch. It unfortunately does not fix the issue, the type checker fails roughly ~1/3-1/2 of the time.

[hauntsaninja]

Yeah, I haven't looked at your repro yet, possibly it could be an entirely different thing from bzoracler's