[red-knot] Differently ordered unions that include `Callable` types are not always considered equivalent

[AlexWaygood]

Summary

Currently, this mdtest fails, even though it should pass:

def f3(a1: int, /, *args1: int, **kwargs2: int) -> None: ...
def f4(a2: int, /, *args2: int, **kwargs1: int) -> None: ...

static_assert(is_equivalent_to(CallableTypeOf[f3] | bool | CallableTypeOf[f4], CallableTypeOf[f4] | bool | CallableTypeOf[f3]))

Note that this is despite the fact that the simpler assertion static_assert(is_equivalent_to(CallableTypeOf[f3], CallableTypeOf[f4]) passes: the Callable types must appear in unions for the bug to occur.

I hoped that applying this diff to type_ordering.rs would fix this bug, but the assertion still fails:

diff --git a/crates/red_knot_python_semantic/src/types/type_ordering.rs b/crates/red_knot_python_semantic/src/types/type_ordering.rs
index 79f0abe1d..c0b160036 100644
--- a/crates/red_knot_python_semantic/src/types/type_ordering.rs
+++ b/crates/red_knot_python_semantic/src/types/type_ordering.rs
@@ -83,9 +83,10 @@ pub(super) fn union_or_intersection_elements_ordering<'db>(
         (Type::Callable(CallableType::WrapperDescriptorDunderGet), _) => Ordering::Less,
         (_, Type::Callable(CallableType::WrapperDescriptorDunderGet)) => Ordering::Greater,
 
-        (Type::Callable(CallableType::General(_)), Type::Callable(CallableType::General(_))) => {
-            Ordering::Equal
-        }
+        (
+            Type::Callable(CallableType::General(left)),
+            Type::Callable(CallableType::General(right)),
+        ) => left.cmp(right),
         (Type::Callable(CallableType::General(_)), _) => Ordering::Less,
         (_, Type::Callable(CallableType::General(_))) => Ordering::Greater,

Adding some reveal_type calls to the test indicates why: the two unions have different Callable types in them (even though the two Callable types are equivalent, they have different names for the parameters):

def f3(a1: int, /, *args1: int, **kwargs2: int) -> None: ...
def f4(a2: int, /, *args2: int, **kwargs1: int) -> None: ...

def f(x: CallableTypeOf[f3] | bool | CallableTypeOf[f4], y: CallableTypeOf[f4] | bool | CallableTypeOf[f3]):
    reveal_type(x)  # revealed: ((a1: int, /, *args1: int, **kwargs2: int) -> None) | bool
    reveal_type(y)  # revealed: ((a2: int, /, *args2: int, **kwargs1: int) -> None) | bool

and our implementation of is_equivalent_to for UnionTypes currently assumes that two sorted unions can only ever be equivalent if they have identical Salsa IDs:

ruff/crates/red_knot_python_semantic/src/types.rs

Lines 5081 to 5116 in ab1011c

	/// Return `true` if `self` represents the exact same set of possible runtime objects as `other`
	pub fn is_equivalent_to(self, db: &'db dyn Db, other: Self) -> bool {
	/// Inlined version of [`UnionType::is_fully_static`] to avoid having to lookup
	/// `self.elements` multiple times in the Salsa db in this single method.
	#[inline]
	fn all_fully_static(db: &dyn Db, elements: &[Type]) -> bool {
	elements.iter().all(|ty| ty.is_fully_static(db))
	}
	let self_elements = self.elements(db);
	let other_elements = other.elements(db);
	if self_elements.len() != other_elements.len() {
	return false;
	}
	if !all_fully_static(db, self_elements) {
	return false;
	}
	if !all_fully_static(db, other_elements) {
	return false;
	}
	if self == other {
	return true;
	}
	let sorted_self = self.to_sorted_union(db);
	if sorted_self == other {
	return true;
	}
	sorted_self == other.to_sorted_union(db)
	}

There are two possible fixes here:

1. Change things so that two equivalent Callable types are always guaranteed to have the same Salsa IDs (discussed as a possibility in [red-knot] Check whether two callable types are equivalent #16698 (comment))
2. Change the implementation of UnionType::is_equivalent_to so that it looks more similar to UnionType::is_gradual_equivalent_to, which takes care to iterate over all elements rather than simply checking the Salsa IDs:

   ruff/crates/red_knot_python_semantic/src/types.rs

   Lines 5144 to 5148 in ab1011c

   	sorted_self
   	.elements(db)
   	.iter()
   	.zip(sorted_other.elements(db))
   	.all(|(self_ty, other_ty)| self_ty.is_gradual_equivalent_to(db, *other_ty))

[AlexWaygood]

Cc. @dhruvmanila