Fix stable iteration ordering for `Map<Name, ...>` usages

11 files changed, 55 insertions, 29 deletions

diff --git a/src/tools/rust-analyzer/crates/hir-def/src/item_scope.rs b/src/tools/rust-analyzer/crates/hir-def/src/item_scope.rs
index 092c0a1dfdf..86c3e0f041d 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/item_scope.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/item_scope.rs
@@ -1,10 +1,9 @@
 //! Describes items defined or visible (ie, imported) in a certain scope.
 //! This is shared between modules and blocks.
 
-use std::collections::hash_map::Entry;
-
 use base_db::CrateId;
 use hir_expand::{attrs::AttrId, db::ExpandDatabase, name::Name, AstId, MacroCallId};
+use indexmap::map::Entry;
 use itertools::Itertools;
 use la_arena::Idx;
 use once_cell::sync::Lazy;
@@ -17,8 +16,8 @@ use crate::{
     db::DefDatabase,
     per_ns::PerNs,
     visibility::{Visibility, VisibilityExplicitness},
-    AdtId, BuiltinType, ConstId, ExternCrateId, HasModule, ImplId, LocalModuleId, Lookup, MacroId,
-    ModuleDefId, ModuleId, TraitId, UseId,
+    AdtId, BuiltinType, ConstId, ExternCrateId, FxIndexMap, HasModule, ImplId, LocalModuleId,
+    Lookup, MacroId, ModuleDefId, ModuleId, TraitId, UseId,
 };
 
 #[derive(Debug, Default)]
@@ -67,9 +66,9 @@ pub struct ItemScope {
     /// Defs visible in this scope. This includes `declarations`, but also
     /// imports. The imports belong to this module and can be resolved by using them on
     /// the `use_imports_*` fields.
-    types: FxHashMap<Name, (ModuleDefId, Visibility, Option<ImportOrExternCrate>)>,
-    values: FxHashMap<Name, (ModuleDefId, Visibility, Option<ImportId>)>,
-    macros: FxHashMap<Name, (MacroId, Visibility, Option<ImportId>)>,
+    types: FxIndexMap<Name, (ModuleDefId, Visibility, Option<ImportOrExternCrate>)>,
+    values: FxIndexMap<Name, (ModuleDefId, Visibility, Option<ImportId>)>,
+    macros: FxIndexMap<Name, (MacroId, Visibility, Option<ImportId>)>,
     unresolved: FxHashSet<Name>,
 
     /// The defs declared in this scope. Each def has a single scope where it is
@@ -118,7 +117,7 @@ struct DeriveMacroInvocation {
     derive_call_ids: SmallVec<[Option<MacroCallId>; 1]>,
 }
 
-pub(crate) static BUILTIN_SCOPE: Lazy<FxHashMap<Name, PerNs>> = Lazy::new(|| {
+pub(crate) static BUILTIN_SCOPE: Lazy<FxIndexMap<Name, PerNs>> = Lazy::new(|| {
     BuiltinType::all_builtin_types()
         .iter()
         .map(|(name, ty)| (name.clone(), PerNs::types((*ty).into(), Visibility::Public, None)))
diff --git a/src/tools/rust-analyzer/crates/hir-def/src/nameres.rs b/src/tools/rust-analyzer/crates/hir-def/src/nameres.rs
index 8e7ef48112f..b0543727c27 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/nameres.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/nameres.rs
@@ -323,7 +323,7 @@ pub struct ModuleData {
     ///
     /// [`None`] for block modules because they are always its `DefMap`'s root.
     pub parent: Option<LocalModuleId>,
-    pub children: FxHashMap<Name, LocalModuleId>,
+    pub children: FxIndexMap<Name, LocalModuleId>,
     pub scope: ItemScope,
 }
 
@@ -593,10 +593,8 @@ impl DefMap {
         self.data.extern_prelude.iter().map(|(name, &def)| (name, def))
     }
 
-    pub(crate) fn macro_use_prelude(
-        &self,
-    ) -> impl Iterator<Item = (&Name, (MacroId, Option<ExternCrateId>))> + '_ {
-        self.macro_use_prelude.iter().map(|(name, &def)| (name, def))
+    pub(crate) fn macro_use_prelude(&self) -> &FxHashMap<Name, (MacroId, Option<ExternCrateId>)> {
+        &self.macro_use_prelude
     }
 
     pub(crate) fn resolve_path(
@@ -668,7 +666,7 @@ impl ModuleData {
             origin,
             visibility,
             parent: None,
-            children: FxHashMap::default(),
+            children: Default::default(),
             scope: ItemScope::default(),
         }
     }
diff --git a/src/tools/rust-analyzer/crates/hir-def/src/nameres/tests/macros.rs b/src/tools/rust-analyzer/crates/hir-def/src/nameres/tests/macros.rs
index d278b75e815..14d497b3a11 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/nameres/tests/macros.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/nameres/tests/macros.rs
@@ -1348,6 +1348,7 @@ fn proc_attr(a: TokenStream, b: TokenStream) -> TokenStream { a }
         .keys()
         .map(|name| name.display(&db).to_string())
         .sorted()
+        .sorted()
         .join("\n");
 
     expect![[r#"
diff --git a/src/tools/rust-analyzer/crates/hir-def/src/resolver.rs b/src/tools/rust-analyzer/crates/hir-def/src/resolver.rs
index c196f002816..f0f2210ec2c 100644
--- a/src/tools/rust-analyzer/crates/hir-def/src/resolver.rs
+++ b/src/tools/rust-analyzer/crates/hir-def/src/resolver.rs
@@ -4,6 +4,7 @@ use std::{fmt, iter, mem};
 use base_db::CrateId;
 use hir_expand::{name::Name, MacroDefId};
 use intern::{sym, Interned};
+use itertools::Itertools as _;
 use rustc_hash::FxHashSet;
 use smallvec::{smallvec, SmallVec};
 use triomphe::Arc;
@@ -497,9 +498,11 @@ impl Resolver {
                 res.add(name, ScopeDef::ModuleDef(ModuleDefId::MacroId(mac)));
             })
         });
-        def_map.macro_use_prelude().for_each(|(name, (def, _extern_crate))| {
-            res.add(name, ScopeDef::ModuleDef(def.into()));
-        });
+        def_map.macro_use_prelude().iter().sorted_by_key(|&(k, _)| k.clone()).for_each(
+            |(name, &(def, _extern_crate))| {
+                res.add(name, ScopeDef::ModuleDef(def.into()));
+            },
+        );
         def_map.extern_prelude().for_each(|(name, (def, _extern_crate))| {
             res.add(name, ScopeDef::ModuleDef(ModuleDefId::ModuleId(def.into())));
         });
diff --git a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/auto_import.rs b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/auto_import.rs
index f17635972b7..37c5d7ce7ef 100644
--- a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/auto_import.rs
+++ b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/auto_import.rs
@@ -1637,8 +1637,8 @@ mod bar {
 
     #[test]
     fn local_inline_import_has_alias() {
-        // FIXME
-        check_assist_not_applicable(
+        // FIXME wrong import
+        check_assist(
             auto_import,
             r#"
 struct S<T>(T);
@@ -1648,13 +1648,23 @@ mod foo {
     pub fn bar() -> S$0<()> {}
 }
 "#,
+            r#"
+struct S<T>(T);
+use S as IoResult;
+
+mod foo {
+    use crate::S;
+
+    pub fn bar() -> S<()> {}
+}
+"#,
         );
     }
 
     #[test]
     fn alias_local() {
-        // FIXME
-        check_assist_not_applicable(
+        // FIXME wrong import
+        check_assist(
             auto_import,
             r#"
 struct S<T>(T);
@@ -1664,6 +1674,16 @@ mod foo {
     pub fn bar() -> IoResult$0<()> {}
 }
 "#,
+            r#"
+struct S<T>(T);
+use S as IoResult;
+
+mod foo {
+    use crate::S;
+
+    pub fn bar() -> IoResult<()> {}
+}
+"#,
         );
     }
 
diff --git a/src/tools/rust-analyzer/crates/ide-completion/src/completions/format_string.rs b/src/tools/rust-analyzer/crates/ide-completion/src/completions/format_string.rs
index 5512ac21534..559a9bcba29 100644
--- a/src/tools/rust-analyzer/crates/ide-completion/src/completions/format_string.rs
+++ b/src/tools/rust-analyzer/crates/ide-completion/src/completions/format_string.rs
@@ -31,7 +31,7 @@ pub(crate) fn format_string(
     };
 
     let source_range = TextRange::new(brace_offset, cursor);
-    ctx.locals.iter().for_each(|(name, _)| {
+    ctx.locals.iter().sorted_by_key(|&(k, _)| k.clone()).for_each(|(name, _)| {
         CompletionItem::new(CompletionItemKind::Binding, source_range, name.to_smol_str())
             .add_to(acc, ctx.db);
     });
diff --git a/src/tools/rust-analyzer/crates/ide-completion/src/render/function.rs b/src/tools/rust-analyzer/crates/ide-completion/src/render/function.rs
index c15e91c4048..cdfe2317017 100644
--- a/src/tools/rust-analyzer/crates/ide-completion/src/render/function.rs
+++ b/src/tools/rust-analyzer/crates/ide-completion/src/render/function.rs
@@ -259,7 +259,7 @@ pub(super) fn add_call_parens<'b>(
 
 fn ref_of_param(ctx: &CompletionContext<'_>, arg: &str, ty: &hir::Type) -> &'static str {
     if let Some(derefed_ty) = ty.remove_ref() {
-        for (name, local) in ctx.locals.iter() {
+        for (name, local) in ctx.locals.iter().sorted_by_key(|&(k, _)| k.clone()) {
             if name.as_str() == arg {
                 return if local.ty(ctx.db) == derefed_ty {
                     if ty.is_mutable_reference() {
diff --git a/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs b/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
index 7d9c1ed98ac..eacec018c72 100644
--- a/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
+++ b/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
@@ -767,8 +767,8 @@ fn main() {
 }
 "#,
         expect![[r#"
-            fn weird_function() (use dep::test_mod::TestTrait) fn() DEPRECATED
             ct SPECIAL_CONST (use dep::test_mod::TestTrait) u8 DEPRECATED
+            fn weird_function() (use dep::test_mod::TestTrait) fn() DEPRECATED
             me random_method(…) (use dep::test_mod::TestTrait) fn(&self) DEPRECATED
         "#]],
     );
diff --git a/src/tools/rust-analyzer/crates/ide-db/src/imports/import_assets.rs b/src/tools/rust-analyzer/crates/ide-db/src/imports/import_assets.rs
index 4814394de6b..38cb4a162c2 100644
--- a/src/tools/rust-analyzer/crates/ide-db/src/imports/import_assets.rs
+++ b/src/tools/rust-analyzer/crates/ide-db/src/imports/import_assets.rs
@@ -15,7 +15,7 @@ use syntax::{
 use crate::{
     helpers::item_name,
     items_locator::{self, AssocSearchMode, DEFAULT_QUERY_SEARCH_LIMIT},
-    RootDatabase,
+    FxIndexSet, RootDatabase,
 };
 
 /// A candidate for import, derived during various IDE activities:
@@ -262,7 +262,7 @@ impl ImportAssets {
 
         let scope = match sema.scope(&self.candidate_node) {
             Some(it) => it,
-            None => return <FxHashSet<_>>::default().into_iter(),
+            None => return <FxIndexSet<_>>::default().into_iter(),
         };
 
         let krate = self.module_with_candidate.krate();
@@ -319,7 +319,7 @@ fn path_applicable_imports(
     path_candidate: &PathImportCandidate,
     mod_path: impl Fn(ItemInNs) -> Option<ModPath> + Copy,
     scope_filter: impl Fn(ItemInNs) -> bool + Copy,
-) -> FxHashSet<LocatedImport> {
+) -> FxIndexSet<LocatedImport> {
     let _p = tracing::info_span!("ImportAssets::path_applicable_imports").entered();
 
     match &path_candidate.qualifier {
@@ -500,7 +500,7 @@ fn trait_applicable_items(
     trait_assoc_item: bool,
     mod_path: impl Fn(ItemInNs) -> Option<ModPath>,
     scope_filter: impl Fn(hir::Trait) -> bool,
-) -> FxHashSet<LocatedImport> {
+) -> FxIndexSet<LocatedImport> {
     let _p = tracing::info_span!("ImportAssets::trait_applicable_items").entered();
 
     let db = sema.db;
@@ -566,7 +566,7 @@ fn trait_applicable_items(
         definitions_exist_in_trait_crate || definitions_exist_in_receiver_crate()
     });
 
-    let mut located_imports = FxHashSet::default();
+    let mut located_imports = FxIndexSet::default();
     let mut trait_import_paths = FxHashMap::default();
 
     if trait_assoc_item {
diff --git a/src/tools/rust-analyzer/crates/intern/src/symbol.rs b/src/tools/rust-analyzer/crates/intern/src/symbol.rs
index 9e275713876..a3cc5c3d6a3 100644
--- a/src/tools/rust-analyzer/crates/intern/src/symbol.rs
+++ b/src/tools/rust-analyzer/crates/intern/src/symbol.rs
@@ -37,6 +37,7 @@ const _: () =
 /// A pointer that points to a pointer to a `str`, it may be backed as a `&'static &'static str` or
 /// `Arc<Box<str>>` but its size is that of a thin pointer. The active variant is encoded as a tag
 /// in the LSB of the alignment niche.
+// Note, Ideally this would encode a `ThinArc<str>` and `ThinRef<str>`/`ThinConstPtr<str>` instead of the double indirection.
 #[derive(PartialEq, Eq, Hash, Copy, Clone, Debug)]
 struct TaggedArcPtr {
     packed: NonNull<*const str>,
diff --git a/src/tools/rust-analyzer/crates/intern/src/symbol/symbols.rs b/src/tools/rust-analyzer/crates/intern/src/symbol/symbols.rs
index 6304155ed76..064335471e9 100644
--- a/src/tools/rust-analyzer/crates/intern/src/symbol/symbols.rs
+++ b/src/tools/rust-analyzer/crates/intern/src/symbol/symbols.rs
@@ -13,6 +13,10 @@ use crate::{
 
 macro_rules! define_symbols {
     (@WITH_NAME: $($alias:ident = $value:literal),* $(,)? @PLAIN: $($name:ident),* $(,)?) => {
+        // Ideally we would be emitting `const` here, but then we no longer have stable addresses
+        // which is what we are relying on for equality! In the future if consts can refer to
+        // statics we should swap these for `const`s and have the the string literal being pointed
+        // to be statics to refer to such that their address is stable.
         $(
             pub static $name: Symbol = Symbol { repr: TaggedArcPtr::non_arc(&stringify!($name)) };
         )*