[ty] Use OrderedSet/Map in more places

crates/ty_python_semantic/src/types/class.rs

@@ -8,6 +8,7 @@ use super::{
     SubclassOfType, Truthiness, Type, TypeQualifiers, class_base::ClassBase,
     function::FunctionType,
 };
+use crate::FxOrderMap;
 use crate::place::TypeOrigin;
 use crate::semantic_index::definition::{Definition, DefinitionState};
 use crate::semantic_index::scope::{NodeWithScopeKind, Scope, ScopeKind};
@@ -161,8 +162,8 @@ fn fields_cycle_initial<'db>(
     _self: ClassLiteral<'db>,
     _specialization: Option<Specialization<'db>>,
     _field_policy: CodeGeneratorKind<'db>,
-) -> FxIndexMap<Name, Field<'db>> {
-    FxIndexMap::default()
+) -> FxOrderMap<Name, Field<'db>> {
+    FxOrderMap::default()
 }
 
 /// A category of classes with code generation capabilities (with synthesized methods).
@@ -3147,7 +3148,7 @@ impl<'db> ClassLiteral<'db> {
         db: &'db dyn Db,
         specialization: Option<Specialization<'db>>,
         field_policy: CodeGeneratorKind<'db>,
-    ) -> FxIndexMap<Name, Field<'db>> {
+    ) -> FxOrderMap<Name, Field<'db>> {
         if field_policy == CodeGeneratorKind::NamedTuple {
             // NamedTuples do not allow multiple inheritance, so it is sufficient to enumerate the
             // fields of this class only.
@@ -3195,8 +3196,8 @@ impl<'db> ClassLiteral<'db> {
         db: &'db dyn Db,
         specialization: Option<Specialization<'db>>,
         field_policy: CodeGeneratorKind,
-    ) -> FxIndexMap<Name, Field<'db>> {
-        let mut attributes = FxIndexMap::default();
+    ) -> FxOrderMap<Name, Field<'db>> {
+        let mut attributes = FxOrderMap::default();
 
         let class_body_scope = self.body_scope(db);
         let table = place_table(db, class_body_scope);

crates/ty_python_semantic/src/types/cyclic.rs

@@ -24,8 +24,9 @@ use std::cmp::Eq;
 use std::hash::Hash;
 use std::marker::PhantomData;
 
-use rustc_hash::{FxHashMap, FxHashSet};
+use rustc_hash::FxHashMap;
 
+use crate::FxIndexSet;
 use crate::types::Type;
 
 /// Maximum recursion depth for cycle detection.
@@ -63,7 +64,7 @@ pub struct CycleDetector<Tag, T, R> {
     /// If the type we're visiting is present in `seen`, it indicates that we've hit a cycle (due
     /// to a recursive type); we need to immediately short circuit the whole operation and return
     /// the fallback value. That's why we pop items off the end of `seen` after we've visited them.
-    seen: RefCell<FxHashSet<T>>,
+    seen: RefCell<FxIndexSet<T>>,
 
     /// Unlike `seen`, this field is a pure performance optimisation (and an essential one). If the
     /// type we're trying to normalize is present in `cache`, it doesn't necessarily mean we've hit
@@ -85,7 +86,7 @@ pub struct CycleDetector<Tag, T, R> {
 impl<Tag, T: Hash + Eq + Clone, R: Clone> CycleDetector<Tag, T, R> {
     pub fn new(fallback: R) -> Self {
         CycleDetector {
-            seen: RefCell::new(FxHashSet::default()),
+            seen: RefCell::new(FxIndexSet::default()),
             cache: RefCell::new(FxHashMap::default()),
             depth: Cell::new(0),
             fallback,
@@ -98,23 +99,24 @@ impl<Tag, T: Hash + Eq + Clone, R: Clone> CycleDetector<Tag, T, R> {
             return val.clone();
         }
 
-        // Check depth limit to prevent stack overflow from recursive generic types
-        // with growing specializations (e.g., C[set[T]] -> C[set[set[T]]] -> ...)
-        let current_depth = self.depth.get();
-        if current_depth >= MAX_RECURSION_DEPTH {
-            return self.fallback.clone();
-        }
-
         // We hit a cycle
         if !self.seen.borrow_mut().insert(item.clone()) {
             return self.fallback.clone();
         }
 
+        // Check depth limit to prevent stack overflow from recursive generic types
+        // with growing specializations (e.g., C[set[T]] -> C[set[set[T]]] -> ...)
+        let current_depth = self.depth.get();
+        if current_depth >= MAX_RECURSION_DEPTH {
+            self.seen.borrow_mut().pop();
+            return self.fallback.clone();
+        }
         self.depth.set(current_depth + 1);
+
         let ret = func();
 
         self.depth.set(current_depth);
-        self.seen.borrow_mut().remove(&item);
+        self.seen.borrow_mut().pop();
         self.cache.borrow_mut().insert(item, ret.clone());
 
         ret
@@ -125,24 +127,24 @@ impl<Tag, T: Hash + Eq + Clone, R: Clone> CycleDetector<Tag, T, R> {
             return Some(val.clone());
         }
 
-        // Check depth limit to prevent stack overflow from recursive generic protocols
-        // with growing specializations (e.g., C[set[T]] -> C[set[set[T]]] -> ...)
-        let current_depth = self.depth.get();
-        if current_depth >= MAX_RECURSION_DEPTH {
-            return Some(self.fallback.clone());
-        }
-
         // We hit a cycle
         if !self.seen.borrow_mut().insert(item.clone()) {
             return Some(self.fallback.clone());
         }
 
+        // Check depth limit to prevent stack overflow from recursive generic protocols
+        // with growing specializations (e.g., C[set[T]] -> C[set[set[T]]] -> ...)
+        let current_depth = self.depth.get();
+        if current_depth >= MAX_RECURSION_DEPTH {
+            self.seen.borrow_mut().pop();
+            return Some(self.fallback.clone());
+        }
         self.depth.set(current_depth + 1);
 
         let ret = func()?;
 
         self.depth.set(current_depth);
-        self.seen.borrow_mut().remove(&item);
+        self.seen.borrow_mut().pop();
         self.cache.borrow_mut().insert(item, ret.clone());
 
         Some(ret)

crates/ty_python_semantic/src/types/diagnostic.rs

@@ -31,7 +31,7 @@ use crate::types::{
     protocol_class::ProtocolClass,
 };
 use crate::types::{DataclassFlags, KnownInstanceType, MemberLookupPolicy, TypeVarInstance};
-use crate::{Db, DisplaySettings, FxIndexMap, Program, declare_lint};
+use crate::{Db, DisplaySettings, FxOrderMap, Program, declare_lint};
 use itertools::Itertools;
 use ruff_db::{
     diagnostic::{Annotation, Diagnostic, Span, SubDiagnostic, SubDiagnosticSeverity},
@@ -3001,7 +3001,7 @@ pub(crate) fn report_instance_layout_conflict(
 /// The inner data is an `IndexMap` to ensure that diagnostics regarding conflicting disjoint bases
 /// are reported in a stable order.
 #[derive(Debug, Default)]
-pub(super) struct IncompatibleBases<'db>(FxIndexMap<DisjointBase<'db>, IncompatibleBaseInfo<'db>>);
+pub(super) struct IncompatibleBases<'db>(FxOrderMap<DisjointBase<'db>, IncompatibleBaseInfo<'db>>);
 
 impl<'db> IncompatibleBases<'db> {
     pub(super) fn insert(

crates/ty_python_semantic/src/types/enums.rs

@@ -2,7 +2,7 @@ use ruff_python_ast::name::Name;
 use rustc_hash::FxHashMap;
 
 use crate::{
-    Db, FxIndexMap,
+    Db, FxOrderMap,
     place::{Place, PlaceAndQualifiers, place_from_bindings, place_from_declarations},
     semantic_index::{place_table, use_def_map},
     types::{
@@ -13,7 +13,7 @@ use crate::{
 
 #[derive(Debug, PartialEq, Eq, salsa::Update)]
 pub(crate) struct EnumMetadata<'db> {
-    pub(crate) members: FxIndexMap<Name, Type<'db>>,
+    pub(crate) members: FxOrderMap<Name, Type<'db>>,
     pub(crate) aliases: FxHashMap<Name, Name>,
 }
 
@@ -22,7 +22,7 @@ impl get_size2::GetSize for EnumMetadata<'_> {}
 impl EnumMetadata<'_> {
     fn empty() -> Self {
         EnumMetadata {
-            members: FxIndexMap::default(),
+            members: FxOrderMap::default(),
             aliases: FxHashMap::default(),
         }
     }
@@ -253,7 +253,7 @@ pub(crate) fn enum_metadata<'db>(
 
             Some((name.clone(), value_ty))
         })
-        .collect::<FxIndexMap<_, _>>();
+        .collect::<FxOrderMap<_, _>>();
 
     if members.is_empty() {
         // Enum subclasses without members are not considered enums.