Exponential blowup in Protocol-vs-Protocol structural subtyping

[grievejia]

Describe the Bug

This issue was revealed after fixing #2560, when checking scikit-learn.
Minimal repro:

"""Pyrefly exponential blowup reproduction.
Three Protocols form a cycle: Array1 → Array2 → Array3 → Array1.
Each method's return type references the NEXT Protocol in the chain.
Cross-Protocol subtyping checks (e.g. Array2 <: Array1) trigger
exponential recursive structural subtyping:
  For each method, pyrefly checks:
    - Parameter contravariance: Array1|complex <: Array2|complex
      → requires Array1 <: Array2 (recursive Protocol conformance!)
    - Return type covariance: Array3 <: Array2 (recursive!)
  Each recursive check triggers N more recursive checks.
Measured results (opt build):
  N=10 baseline (no cross-Protocol calls): 48ms
  N=10 with cross-Protocol calls:          97s   (2,029x blowup!)
  N=12 with cross-Protocol calls:          280s
  24.4 million get_idx calls for a single binding key at N=10.
"""
from typing import Protocol
class Array1(Protocol):
    def op_0(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_1(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_2(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_3(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_4(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_5(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_6(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_7(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_8(self, other: "Array1 | complex", /) -> "Array2": ...
    def op_9(self, other: "Array1 | complex", /) -> "Array2": ...
class Array2(Protocol):
    def op_0(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_1(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_2(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_3(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_4(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_5(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_6(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_7(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_8(self, other: "Array2 | complex", /) -> "Array3": ...
    def op_9(self, other: "Array2 | complex", /) -> "Array3": ...
class Array3(Protocol):
    def op_0(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_1(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_2(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_3(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_4(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_5(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_6(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_7(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_8(self, other: "Array3 | complex", /) -> "Array1": ...
    def op_9(self, other: "Array3 | complex", /) -> "Array1": ...
class Impl:
    """Concrete class that satisfies all three Protocols."""
    def op_0(self, other: object, /) -> "Impl": ...
    def op_1(self, other: object, /) -> "Impl": ...
    def op_2(self, other: object, /) -> "Impl": ...
    def op_3(self, other: object, /) -> "Impl": ...
    def op_4(self, other: object, /) -> "Impl": ...
    def op_5(self, other: object, /) -> "Impl": ...
    def op_6(self, other: object, /) -> "Impl": ...
    def op_7(self, other: object, /) -> "Impl": ...
    def op_8(self, other: object, /) -> "Impl": ...
    def op_9(self, other: object, /) -> "Impl": ...
def f1(x: Array1 | complex) -> Array1: ...
def f2(x: Array2 | complex) -> Array2: ...
def f3(x: Array3 | complex) -> Array3: ...
def test() -> None:
    val = Impl()
    # Impl-vs-Protocol checks (relatively fast):
    a1 = f1(val)
    a2 = f2(val)
    a3 = f3(val)
    # Cross-Protocol checks (triggers exponential blowup):
    c1 = f1(a2)  # Array2 checked against Array1
    c2 = f2(a3)  # Array3 checked against Array2
    c3 = f3(a1)  # Array1 checked against Array3

Sandbox Link

No response

(Only applicable for extension issues) IDE Information

No response