salsa update: coarse tracked structs

Turupawn · Turupawn · Mar 15, 2025 · Feb 28, 2024 · Feb 28, 2024 · Feb 28, 2024
commit 8eb41e0e03e9c02ec0e846047a2dc29240b6f775
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
@@ -22,7 +22,7 @@ dir-test = "0.4"
 rustc-hash = "2.1.0"
 num-bigint = "0.4"
 paste = "1.0.15"
-salsa = { git = "https://github.com/salsa-rs/salsa", rev = "d32b3c1995b632d894250a667adb79c846b3da02" }
+salsa = { git = "https://github.com/salsa-rs/salsa", rev = "ca9fba4e83b38ad7c2002b394edd792fa75f924a" }
 smallvec = { version = "2.0.0-alpha.10" }
 wasm-bindgen-test = "0.3"
 glob = "0.3.2"

diff --git a/crates/common/Cargo.toml b/crates/common/Cargo.toml
@@ -10,10 +10,11 @@ description = "Provides HIR definition and lowering for Fe lang."
 
 [dependencies]
 camino.workspace = true
-indexmap = "2.7"
 paste.workspace = true
 salsa.workspace = true
 semver.workspace = true
 smol_str = "0.3.2"
 
 parser.workspace = true
+ordermap = "0.5.5"
+rustc-hash.workspace = true
diff --git a/crates/common/src/indexmap.rs b/crates/common/src/indexmap.rs
@@ -1,20 +1,24 @@
 use std::{
-    hash::{BuildHasher, Hash, RandomState},
+    hash::Hash,
     ops::{Deref, DerefMut},
 };
 
+use rustc_hash::FxBuildHasher;
 use salsa::Update;
 
-#[derive(Debug, Clone)]
-pub struct IndexMap<K, V, S = RandomState>(indexmap::IndexMap<K, V, S>);
+type OrderMap<K, V> = ordermap::OrderMap<K, V, FxBuildHasher>;
+type OrderSet<V> = ordermap::OrderSet<V, FxBuildHasher>;
+
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+pub struct IndexMap<K, V>(OrderMap<K, V>);
 
 impl<K, V> IndexMap<K, V> {
     pub fn new() -> Self {
-        Self(indexmap::IndexMap::new())
+        Self(OrderMap::default())
     }
 
     pub fn with_capacity(n: usize) -> Self {
-        Self(indexmap::IndexMap::with_capacity(n))
+        Self(OrderMap::with_capacity_and_hasher(n, FxBuildHasher {}))
     }
 }
 
@@ -24,83 +28,56 @@ impl<K, V> Default for IndexMap<K, V> {
     }
 }
 
-impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
-    type Item = <indexmap::IndexMap<K, V, S> as IntoIterator>::Item;
-    type IntoIter = <indexmap::IndexMap<K, V, S> as IntoIterator>::IntoIter;
+impl<K, V> IntoIterator for IndexMap<K, V> {
+    type Item = <OrderMap<K, V> as IntoIterator>::Item;
+    type IntoIter = <OrderMap<K, V> as IntoIterator>::IntoIter;
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
     }
 }
 
-impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
-    type Item = <&'a indexmap::IndexMap<K, V, S> as IntoIterator>::Item;
-    type IntoIter = <&'a indexmap::IndexMap<K, V, S> as IntoIterator>::IntoIter;
+impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
+    type Item = <&'a OrderMap<K, V> as IntoIterator>::Item;
+    type IntoIter = <&'a OrderMap<K, V> as IntoIterator>::IntoIter;
     fn into_iter(self) -> Self::IntoIter {
         (&self.0).into_iter()
     }
 }
 
-impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
-    type Item = <&'a mut indexmap::IndexMap<K, V, S> as IntoIterator>::Item;
-    type IntoIter = <&'a mut indexmap::IndexMap<K, V, S> as IntoIterator>::IntoIter;
+impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
+    type Item = <&'a mut OrderMap<K, V> as IntoIterator>::Item;
+    type IntoIter = <&'a mut OrderMap<K, V> as IntoIterator>::IntoIter;
     fn into_iter(self) -> Self::IntoIter {
         (&mut self.0).into_iter()
     }
 }
 
-impl<K, V, S> PartialEq for IndexMap<K, V, S>
-where
-    K: Eq + Hash,
-    V: PartialEq,
-    S: BuildHasher,
-{
-    fn eq(&self, other: &Self) -> bool {
-        self.0.eq(&other.0)
-    }
-}
-
-impl<K, V, S> Eq for IndexMap<K, V, S>
-where
-    K: Eq + Hash,
-    V: Eq,
-    S: BuildHasher,
-{
-}
-
-impl<K, V, S> FromIterator<(K, V)> for IndexMap<K, V, S>
+impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
 where
     K: Hash + Eq,
-    S: BuildHasher + Default,
 {
     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
-        Self(indexmap::IndexMap::from_iter(iter))
+        Self(OrderMap::from_iter(iter))
     }
 }
 
-impl<K, V, S> Deref for IndexMap<K, V, S>
-where
-    S: BuildHasher,
-{
-    type Target = indexmap::IndexMap<K, V, S>;
+impl<K, V> Deref for IndexMap<K, V> {
+    type Target = OrderMap<K, V>;
     fn deref(&self) -> &Self::Target {
         &self.0
     }
 }
 
-impl<K, V, S> DerefMut for IndexMap<K, V, S>
-where
-    S: BuildHasher,
-{
+impl<K, V> DerefMut for IndexMap<K, V> {
     fn deref_mut(&mut self) -> &mut Self::Target {
         &mut self.0
     }
 }
 
-unsafe impl<K, V, S> Update for IndexMap<K, V, S>
+unsafe impl<K, V> Update for IndexMap<K, V>
 where
     K: Update + Eq + Hash,
     V: Update,
-    S: BuildHasher,
 {
     unsafe fn maybe_update(old_pointer: *mut Self, new_map: Self) -> bool {
         let old_map = unsafe { &mut *old_pointer };
@@ -131,15 +108,15 @@ where
 }
 
 #[derive(Debug, Clone)]
-pub struct IndexSet<V, S = RandomState>(indexmap::IndexSet<V, S>);
+pub struct IndexSet<V>(OrderSet<V>);
 
 impl<V> IndexSet<V> {
     pub fn new() -> Self {
-        Self(indexmap::IndexSet::new())
+        Self(OrderSet::default())
     }
 
     pub fn with_capacity(n: usize) -> Self {
-        Self(indexmap::IndexSet::with_capacity(n))
+        Self(OrderSet::with_capacity_and_hasher(n, FxBuildHasher {}))
     }
 }
 
@@ -149,72 +126,58 @@ impl<V> Default for IndexSet<V> {
     }
 }
 
-impl<V, S> IntoIterator for IndexSet<V, S> {
-    type Item = <indexmap::IndexSet<V, S> as IntoIterator>::Item;
-    type IntoIter = <indexmap::IndexSet<V, S> as IntoIterator>::IntoIter;
+impl<V> IntoIterator for IndexSet<V> {
+    type Item = <OrderSet<V> as IntoIterator>::Item;
+    type IntoIter = <OrderSet<V> as IntoIterator>::IntoIter;
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
     }
 }
 
-impl<'a, V, S> IntoIterator for &'a IndexSet<V, S> {
-    type Item = <&'a indexmap::IndexSet<V, S> as IntoIterator>::Item;
-    type IntoIter = <&'a indexmap::IndexSet<V, S> as IntoIterator>::IntoIter;
+impl<'a, V> IntoIterator for &'a IndexSet<V> {
+    type Item = <&'a OrderSet<V> as IntoIterator>::Item;
+    type IntoIter = <&'a OrderSet<V> as IntoIterator>::IntoIter;
     fn into_iter(self) -> Self::IntoIter {
         (&self.0).into_iter()
     }
 }
 
-impl<V, S> PartialEq for IndexSet<V, S>
+impl<V> PartialEq for IndexSet<V>
 where
     V: Hash + Eq,
-    S: BuildHasher,
 {
     fn eq(&self, other: &Self) -> bool {
         self.0.eq(&other.0)
     }
 }
 
-impl<V, S> Eq for IndexSet<V, S>
-where
-    V: Eq + Hash,
-    S: BuildHasher,
-{
-}
+impl<V> Eq for IndexSet<V> where V: Eq + Hash {}
 
-impl<V, S> FromIterator<V> for IndexSet<V, S>
+impl<V> FromIterator<V> for IndexSet<V>
 where
     V: Hash + Eq,
-    S: BuildHasher + Default,
 {
     fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
-        Self(indexmap::IndexSet::from_iter(iter))
+        Self(OrderSet::from_iter(iter))
     }
 }
 
-impl<V, S> Deref for IndexSet<V, S>
-where
-    S: BuildHasher,
-{
-    type Target = indexmap::IndexSet<V, S>;
+impl<V> Deref for IndexSet<V> {
+    type Target = OrderSet<V>;
     fn deref(&self) -> &Self::Target {
         &self.0
     }
 }
 
-impl<V, S> DerefMut for IndexSet<V, S>
-where
-    S: BuildHasher,
-{
+impl<V> DerefMut for IndexSet<V> {
     fn deref_mut(&mut self) -> &mut Self::Target {
         &mut self.0
     }
 }
 
-unsafe impl<V, S> Update for IndexSet<V, S>
+unsafe impl<V> Update for IndexSet<V>
 where
     V: Update + Eq + Hash,
-    S: BuildHasher,
 {
     unsafe fn maybe_update(old_pointer: *mut Self, new_set: Self) -> bool {
         let old_set = unsafe { &mut *old_pointer };

diff --git a/crates/hir-analysis/src/ty/def_analysis.rs b/crates/hir-analysis/src/ty/def_analysis.rs
@@ -1261,7 +1261,7 @@ impl<'db> ImplTraitMethodAnalyzer<'db> {
                 &mut self.diags,
             );
 
-            required_methods.shift_remove(name);
+            required_methods.remove(name);
         }
 
         if !required_methods.is_empty() {

diff --git a/crates/hir/src/hir_def/body.rs b/crates/hir/src/hir_def/body.rs
@@ -5,6 +5,7 @@
 
 use std::hash::Hash;
 
+use common::indexmap::IndexMap;
 use cranelift_entity::{EntityRef, PrimaryMap, SecondaryMap};
 use parser::ast::{self, prelude::*};
 use rustc_hash::FxHashMap;
@@ -22,7 +23,7 @@ use crate::{
 
 #[salsa::tracked]
 pub struct Body<'db> {
-    #[id]
+ //    #[id]
     id: TrackedItemId<'db>,
 
     /// The expression that evaluates to the value of the body.
@@ -77,13 +78,13 @@ impl<'db> Body<'db> {
     }
 }
 
-#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 pub enum BodyKind {
     FuncBody,
     Anonymous,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Hash, Clone)]
 pub struct NodeStore<K, V>(PrimaryMap<K, V>)
 where
     K: EntityRef;
@@ -170,21 +171,22 @@ where
 pub trait SourceAst: AstNode + Clone + Hash + PartialEq + Eq {}
 impl<T> SourceAst for T where T: AstNode + Clone + Hash + PartialEq + Eq {}
 
-#[derive(Clone, Debug, Default, PartialEq, Eq)]
+#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
 pub struct BodySourceMap {
     pub stmt_map: SourceNodeMap<ast::Stmt, StmtId>,
     pub expr_map: SourceNodeMap<ast::Expr, ExprId>,
     pub pat_map: SourceNodeMap<ast::Pat, PatId>,
 }
 
-#[derive(Clone, Debug)]
+#[allow(clippy::derived_hash_with_manual_eq)]
+#[derive(Clone, Debug, Hash)]
 pub struct SourceNodeMap<Ast, Node>
 where
     Ast: SourceAst,
     Node: EntityRef,
 {
     pub node_to_source: SecondaryMap<Node, HirOrigin<Ast>>,
-    pub source_to_node: FxHashMap<HirOrigin<Ast>, Node>,
+    pub source_to_node: IndexMap<HirOrigin<Ast>, Node>,
 }
 
 impl<Ast, Node> SourceNodeMap<Ast, Node>
@@ -226,7 +228,7 @@ where
 {
     fn default() -> Self {
         Self {
-            source_to_node: FxHashMap::default(),
+            source_to_node: IndexMap::default(),
             node_to_source: SecondaryMap::new(),
         }
     }