[red-knot] fix equivalence (and gradual equivalence) for differently-ordered unions and intersections #15380
Description
This issue relates to the TODO comment here:
ruff/crates/red_knot_python_semantic/src/types.rs
Lines 1065 to 1081 in b0905c4
Some ~raw comments from discussion about this issue:
it's not simple, but it also shouldn't be worse than the existing is_subtype_of support for intersections and unions, I think; it just feels wrong that it's O(n^2)
i mean the simplest (but maybe not most efficient) implementation of it would be "is A a subtype of B and B a subtype of A"
if so, they are equivalent
Alex Waygood — Today at 10:01 AM
except that is_subtype_of() calls is_equivalent_to() 😆
so you'll get infinite recursion with our current structure
carljm — Today at 10:01 AM
true, we may need to split atomic equivalence
because we do maintain a simplified two-layer structure for unions and intersections
we don't have arbitrary recursive structures
so we should know when handling union/intersection subtyping when we won't be dealing with more unions/intersections
Alex Waygood — Today at 10:02 AM
I do also think that we can implement optimisations by making sure that equivalent types have the same internal representation wherever possible, like the thing I implemented the other day so that type[object] is eagerly simplified to type