Avoid quadratic rescans when ordering methods by subclassing (#22111)

Track the first unprocessed superclass blocking each method group and
retry the group when that superclass is processed. This removes the
repeated scans from the beginning of the group list. Each retry resumes
at the next MRO entry, avoiding repeated traversal and slicing of the
same MRO.

Use a min-heap of original group indices to keep the existing processing
order: the earliest available group still goes first, including when
nested classes split an enclosing class's methods into several groups.
Keep the MRO scan in a separate function so mypyc can use local
variables for the loop instead of generator environment attributes.

Fixes #22110.

mypy/semanal_main.py

diff --git a/mypy/semanal_main.py b/mypy/semanal_main.py
index 876849c..77db792 100644
--- a/mypy/semanal_main.py
+++ b/mypy/semanal_main.py
@@ -29,6 +29,7 @@
 from collections import Counter
 from collections.abc import Callable, Iterator
 from contextlib import nullcontext
+from heapq import heappop, heappush
 from itertools import groupby
 from typing import TYPE_CHECKING, Final, TypeAlias as _TypeAlias
 
@@ -217,40 +218,46 @@
 
 
 def order_by_subclassing(targets: list[FullTargetInfo]) -> Iterator[FullTargetInfo]:
-    """Make sure that superclass methods are always processed before subclass methods.
-
-    This algorithm is not very optimal, but it is simple and should work well for lists
-    that are already almost correctly ordered.
-    """
+    """Make sure that superclass methods are always processed before subclass methods."""
 
     # A nested class can split its enclosing class's methods into multiple groups.
     grouped = [(k, list(g)) for k, g in groupby(targets, key=lambda x: x[3])]
     remaining_infos = Counter(info for info, _ in grouped if info is not None)
 
-    next_group = 0
-    while grouped:
-        if next_group >= len(grouped):
-            # This should never happen, if there is an MRO cycle, it should be reported
-            # and fixed during top-level processing.
-            raise ValueError("Cannot order method targets by MRO")
-        next_info, group = grouped[next_group]
-        if next_info is None:
-            # Trivial case, not methods but functions, process them straight away.
-            yield from group
-            grouped.pop(next_group)
-            continue
-        if any(parent in remaining_infos for parent in next_info.mro[1:]):
-            # We cannot process this method group yet, try a next one.
-            next_group += 1
-            continue
+    # Retry blocked groups in their original order when their first unprocessed
+    # superclass is processed, resuming the MRO scan where it stopped.
+    candidates = list(range(len(grouped)))
+    mro_start = [1] * len(grouped)
+    waiting: dict[TypeInfo, list[int]] = {}
+    while candidates:
+        i = heappop(candidates)
+        info, group = grouped[i]
+        if info is not None:
+            pos = find_remaining_parent(info, mro_start[i], remaining_infos)
+            if pos >= 0:
+                mro_start[i] = pos + 1
+                waiting.setdefault(info.mro[pos], []).append(i)
+                continue
         yield from group
-        grouped.pop(next_group)
-        remaining_infos[next_info] -= 1
-        if not remaining_infos[next_info]:
-            del remaining_infos[next_info]
-        # Each time after processing a method group we should retry from start,
-        # since there may be some groups that are not blocked on parents anymore.
-        next_group = 0
+        if info is not None:
+            remaining_infos[info] -= 1
+            if not remaining_infos[info]:
+                del remaining_infos[info]
+                for j in waiting.pop(info, []):
+                    heappush(candidates, j)
+    if waiting:
+        # This should never happen, if there is an MRO cycle, it should be reported
+        # and fixed during top-level processing.
+        raise ValueError("Cannot order method targets by MRO")
+
+
+def find_remaining_parent(info: TypeInfo, start: int, remaining_infos: Counter[TypeInfo]) -> int:
+    """Return index of the first class in info.mro[start:] in remaining_infos, or -1."""
+    mro = info.mro
+    for pos in range(start, len(mro)):
+        if mro[pos] in remaining_infos:
+            return pos
+    return -1
 
 
 def process_functions(graph: Graph, scc: list[str], patches: Patches) -> None:

test-data/unit/check-classes.test

diff --git a/test-data/unit/check-classes.test b/test-data/unit/check-classes.test
index 3ee2b02..15a495e 100644
--- a/test-data/unit/check-classes.test
+++ b/test-data/unit/check-classes.test
@@ -7334,6 +7334,29 @@
     def d2(self) -> None:
         self.x = 0
 
+[case testOrderBySubclassingMultipleLevels]
+class E(D):
+    def e(self) -> None: ...
+
+class D(B):
+    def d(self) -> None: ...
+    class N:
+        def n(self) -> None: ...
+    def d2(self) -> None: ...
+
+def f() -> None: ...
+
+class C(A):
+    def c(self) -> None: ...
+
+class B(A):
+    def b(self) -> None: ...
+
+class A:
+    def a(self) -> None: ...
+
+[targets __main__, __main__, __main__, __main__, __main__.D.N.n, __main__.f, __main__.A.a, __main__.C.c, __main__.B.b, __main__.D.d, __main__.D.d2, __main__.E.e]
+
 [case testNewReturnType1]
 class A:
     def __new__(cls) -> B: