7 files changed, 198 insertions, 114 deletions

diff --git a/crates/hir_def/Cargo.toml b/crates/hir_def/Cargo.toml
index 475d337f3..43324d8d9 100644
--- a/crates/hir_def/Cargo.toml
+++ b/crates/hir_def/Cargo.toml
@@ -11,6 +11,7 @@ doctest = false
 
 [dependencies]
 cov-mark = { version = "1.1", features = ["thread-local"] }
+dashmap = { version = "4.0.2", features = ["raw-api"] }
 log = "0.4.8"
 once_cell = "1.3.1"
 rustc-hash = "1.1.0"
diff --git a/crates/hir_def/src/adt.rs b/crates/hir_def/src/adt.rs
index 58e35353b..402fb1d8d 100644
--- a/crates/hir_def/src/adt.rs
+++ b/crates/hir_def/src/adt.rs
@@ -15,6 +15,7 @@ use tt::{Delimiter, DelimiterKind, Leaf, Subtree, TokenTree};
 use crate::{
     body::{CfgExpander, LowerCtx},
     db::DefDatabase,
+    intern::Interned,
     item_tree::{AttrOwner, Field, Fields, ItemTree, ModItem, RawVisibilityId},
     src::HasChildSource,
     src::HasSource,
@@ -58,7 +59,7 @@ pub enum VariantData {
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct FieldData {
     pub name: Name,
-    pub type_ref: TypeRef,
+    pub type_ref: Interned<TypeRef>,
     pub visibility: RawVisibility,
 }
 
@@ -292,7 +293,7 @@ fn lower_struct(
                     || Either::Left(fd.clone()),
                     || FieldData {
                         name: Name::new_tuple_field(i),
-                        type_ref: TypeRef::from_ast_opt(&ctx, fd.ty()),
+                        type_ref: Interned::new(TypeRef::from_ast_opt(&ctx, fd.ty())),
                         visibility: RawVisibility::from_ast(db, ast.with_value(fd.visibility())),
                     },
                 );
@@ -309,7 +310,7 @@ fn lower_struct(
                     || Either::Right(fd.clone()),
                     || FieldData {
                         name: fd.name().map(|n| n.as_name()).unwrap_or_else(Name::missing),
-                        type_ref: TypeRef::from_ast_opt(&ctx, fd.ty()),
+                        type_ref: Interned::new(TypeRef::from_ast_opt(&ctx, fd.ty())),
                         visibility: RawVisibility::from_ast(db, ast.with_value(fd.visibility())),
                     },
                 );
@@ -358,7 +359,7 @@ fn lower_field(
 ) -> FieldData {
     FieldData {
         name: field.name.clone(),
-        type_ref: item_tree[field.type_ref].clone(),
+        type_ref: field.type_ref.clone(),
         visibility: item_tree[override_visibility.unwrap_or(field.visibility)].clone(),
     }
 }
diff --git a/crates/hir_def/src/data.rs b/crates/hir_def/src/data.rs
index 214bcc648..31f994681 100644
--- a/crates/hir_def/src/data.rs
+++ b/crates/hir_def/src/data.rs
@@ -9,6 +9,7 @@ use crate::{
     attr::Attrs,
     body::Expander,
     db::DefDatabase,
+    intern::Interned,
     item_tree::{AssocItem, FunctionQualifier, ItemTreeId, ModItem, Param},
     type_ref::{TraitRef, TypeBound, TypeRef},
     visibility::RawVisibility,
@@ -19,8 +20,8 @@ use crate::{
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct FunctionData {
     pub name: Name,
-    pub params: Vec<TypeRef>,
-    pub ret_type: TypeRef,
+    pub params: Vec<Interned<TypeRef>>,
+    pub ret_type: Interned<TypeRef>,
     pub attrs: Attrs,
     /// True if the first param is `self`. This is relevant to decide whether this
     /// can be called as a method.
@@ -57,11 +58,11 @@ impl FunctionData {
             params: enabled_params
                 .clone()
                 .filter_map(|id| match &item_tree[id] {
-                    Param::Normal(ty) => Some(item_tree[*ty].clone()),
+                    Param::Normal(ty) => Some(ty.clone()),
                     Param::Varargs => None,
                 })
                 .collect(),
-            ret_type: item_tree[func.ret_type].clone(),
+            ret_type: func.ret_type.clone(),
             attrs: item_tree.attrs(db, krate, ModItem::from(loc.id.value).into()),
             has_self_param: func.has_self_param,
             has_body: func.has_body,
@@ -76,7 +77,7 @@ impl FunctionData {
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct TypeAliasData {
     pub name: Name,
-    pub type_ref: Option<TypeRef>,
+    pub type_ref: Option<Interned<TypeRef>>,
     pub visibility: RawVisibility,
     pub is_extern: bool,
     /// Bounds restricting the type alias itself (eg. `type Ty: Bound;` in a trait or impl).
@@ -94,7 +95,7 @@ impl TypeAliasData {
 
         Arc::new(TypeAliasData {
             name: typ.name.clone(),
-            type_ref: typ.type_ref.map(|id| item_tree[id].clone()),
+            type_ref: typ.type_ref.clone(),
             visibility: item_tree[typ.visibility].clone(),
             is_extern: typ.is_extern,
             bounds: typ.bounds.to_vec(),
@@ -156,8 +157,8 @@ impl TraitData {
 
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct ImplData {
-    pub target_trait: Option<TraitRef>,
-    pub self_ty: TypeRef,
+    pub target_trait: Option<Interned<TraitRef>>,
+    pub self_ty: Interned<TypeRef>,
     pub items: Vec<AssocItemId>,
     pub is_negative: bool,
 }
@@ -169,8 +170,8 @@ impl ImplData {
 
         let item_tree = impl_loc.id.item_tree(db);
         let impl_def = &item_tree[impl_loc.id.value];
-        let target_trait = impl_def.target_trait.map(|id| item_tree[id].clone());
-        let self_ty = item_tree[impl_def.self_ty].clone();
+        let target_trait = impl_def.target_trait.clone();
+        let self_ty = impl_def.self_ty.clone();
         let is_negative = impl_def.is_negative;
         let module_id = impl_loc.container;
         let container = AssocContainerId::ImplId(id);
@@ -195,7 +196,7 @@ impl ImplData {
 pub struct ConstData {
     /// const _: () = ();
     pub name: Option<Name>,
-    pub type_ref: TypeRef,
+    pub type_ref: Interned<TypeRef>,
     pub visibility: RawVisibility,
 }
 
@@ -207,7 +208,7 @@ impl ConstData {
 
         Arc::new(ConstData {
             name: konst.name.clone(),
-            type_ref: item_tree[konst.type_ref].clone(),
+            type_ref: konst.type_ref.clone(),
             visibility: item_tree[konst.visibility].clone(),
         })
     }
@@ -216,7 +217,7 @@ impl ConstData {
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct StaticData {
     pub name: Option<Name>,
-    pub type_ref: TypeRef,
+    pub type_ref: Interned<TypeRef>,
     pub visibility: RawVisibility,
     pub mutable: bool,
     pub is_extern: bool,
@@ -230,7 +231,7 @@ impl StaticData {
 
         Arc::new(StaticData {
             name: Some(statik.name.clone()),
-            type_ref: item_tree[statik.type_ref].clone(),
+            type_ref: statik.type_ref.clone(),
             visibility: item_tree[statik.visibility].clone(),
             mutable: statik.mutable,
             is_extern: statik.is_extern,
diff --git a/crates/hir_def/src/intern.rs b/crates/hir_def/src/intern.rs
new file mode 100644
index 000000000..28ec72cff
--- /dev/null
+++ b/crates/hir_def/src/intern.rs
@@ -0,0 +1,157 @@
+//! Global `Arc`-based object interning infrastructure.
+//!
+//! Eventually this should probably be replaced with salsa-based interning.
+
+use std::{
+    fmt::{self, Debug},
+    hash::{BuildHasherDefault, Hash},
+    ops::Deref,
+    sync::Arc,
+};
+
+use dashmap::{DashMap, SharedValue};
+use once_cell::sync::OnceCell;
+use rustc_hash::FxHasher;
+
+type InternMap<T> = DashMap<Arc<T>, (), BuildHasherDefault<FxHasher>>;
+
+pub struct Interned<T: Internable> {
+    arc: Arc<T>,
+}
+
+impl<T: Internable> Interned<T> {
+    pub fn new(obj: T) -> Self {
+        let storage = T::storage().get();
+        let shard_idx = storage.determine_map(&obj);
+        let shard = &storage.shards()[shard_idx];
+        let shard = shard.upgradeable_read();
+
+        // Atomically,
+        // - check if `obj` is already in the map
+        //   - if so, clone its `Arc` and return it
+        //   - if not, box it up, insert it, and return a clone
+        // This needs to be atomic (locking the shard) to avoid races with other thread, which could
+        // insert the same object between us looking it up and inserting it.
+
+        // FIXME: avoid double lookup by using raw entry API (once stable, or when hashbrown can be
+        // plugged into dashmap)
+        if let Some((arc, _)) = shard.get_key_value(&obj) {
+            return Self { arc: arc.clone() };
+        }
+
+        let arc = Arc::new(obj);
+        let arc2 = arc.clone();
+
+        {
+            let mut shard = shard.upgrade();
+            shard.insert(arc2, SharedValue::new(()));
+        }
+
+        Self { arc }
+    }
+}
+
+impl<T: Internable> Drop for Interned<T> {
+    fn drop(&mut self) {
+        // When the last `Ref` is dropped, remove the object from the global map.
+        if Arc::strong_count(&self.arc) == 2 {
+            // Only `self` and the global map point to the object.
+
+            let storage = T::storage().get();
+            let shard_idx = storage.determine_map(&self.arc);
+            let shard = &storage.shards()[shard_idx];
+            let mut shard = shard.write();
+
+            // FIXME: avoid double lookup
+            let (arc, _) =
+                shard.get_key_value(&self.arc).expect("interned value removed prematurely");
+
+            if Arc::strong_count(arc) != 2 {
+                // Another thread has interned another copy
+                return;
+            }
+
+            shard.remove(&self.arc);
+
+            // Shrink the backing storage if the shard is less than 50% occupied.
+            if shard.len() * 2 < shard.capacity() {
+                shard.shrink_to_fit();
+            }
+        }
+    }
+}
+
+/// Compares interned `Ref`s using pointer equality.
+impl<T: Internable> PartialEq for Interned<T> {
+    #[inline]
+    fn eq(&self, other: &Self) -> bool {
+        Arc::ptr_eq(&self.arc, &other.arc)
+    }
+}
+
+impl<T: Internable> Eq for Interned<T> {}
+
+impl<T: Internable> AsRef<T> for Interned<T> {
+    #[inline]
+    fn as_ref(&self) -> &T {
+        &self.arc
+    }
+}
+
+impl<T: Internable> Deref for Interned<T> {
+    type Target = T;
+
+    #[inline]
+    fn deref(&self) -> &Self::Target {
+        &self.arc
+    }
+}
+
+impl<T: Internable> Clone for Interned<T> {
+    fn clone(&self) -> Self {
+        Self { arc: self.arc.clone() }
+    }
+}
+
+impl<T: Debug + Internable> Debug for Interned<T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        (*self.arc).fmt(f)
+    }
+}
+
+pub struct InternStorage<T> {
+    map: OnceCell<InternMap<T>>,
+}
+
+impl<T> InternStorage<T> {
+    pub const fn new() -> Self {
+        Self { map: OnceCell::new() }
+    }
+}
+
+impl<T: Internable> InternStorage<T> {
+    fn get(&self) -> &InternMap<T> {
+        self.map.get_or_init(DashMap::default)
+    }
+}
+
+pub trait Internable: Hash + Eq + Sized + 'static {
+    fn storage() -> &'static InternStorage<Self>;
+}
+
+// region:`Internable` implementations
+
+macro_rules! impl_internable {
+    ( $($t:ty),+ $(,)? ) => { $(
+        impl Internable for $t {
+            fn storage() -> &'static InternStorage<Self> {
+                static STORAGE: InternStorage<$t> = InternStorage::new();
+                &STORAGE
+            }
+        }
+    )+ };
+}
+
+impl_internable!(crate::type_ref::TypeRef, crate::type_ref::TraitRef);
+
+// endregion
diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 5449bbf5d..9f6bb3a7c 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -30,6 +30,7 @@ use crate::{
     attr::{Attrs, RawAttrs},
     db::DefDatabase,
     generics::GenericParams,
+    intern::Interned,
     path::{path, AssociatedTypeBinding, GenericArgs, ImportAlias, ModPath, Path, PathKind},
     type_ref::{Mutability, TraitRef, TypeBound, TypeRef},
     visibility::RawVisibility,
@@ -146,8 +147,6 @@ impl ItemTree {
                 macro_defs,
                 vis,
                 generics,
-                type_refs,
-                trait_refs,
                 inner_items,
             } = &mut **data;
 
@@ -172,9 +171,6 @@ impl ItemTree {
 
             vis.arena.shrink_to_fit();
             generics.arena.shrink_to_fit();
-            type_refs.arena.shrink_to_fit();
-            type_refs.map.shrink_to_fit();
-            trait_refs.map.shrink_to_fit();
 
             inner_items.shrink_to_fit();
         }
@@ -271,58 +267,6 @@ static EMPTY_GENERICS: GenericParams = GenericParams {
     where_predicates: Vec::new(),
 };
 
-/// `TypeRef` interner.
-#[derive(Default, Debug, Eq, PartialEq)]
-struct TypeRefStorage {
-    arena: Arena<Arc<TypeRef>>,
-    map: FxHashMap<Arc<TypeRef>, Idx<Arc<TypeRef>>>,
-}
-
-impl TypeRefStorage {
-    // Note: We lie about the `Idx<TypeRef>` to hide the interner details.
-
-    fn intern(&mut self, ty: TypeRef) -> Idx<TypeRef> {
-        if let Some(id) = self.map.get(&ty) {
-            return Idx::from_raw(id.into_raw());
-        }
-
-        let ty = Arc::new(ty);
-        let idx = self.arena.alloc(ty.clone());
-        self.map.insert(ty, idx);
-        Idx::from_raw(idx.into_raw())
-    }
-
-    fn lookup(&self, id: Idx<TypeRef>) -> &TypeRef {
-        &self.arena[Idx::from_raw(id.into_raw())]
-    }
-}
-
-/// `TraitRef` interner.
-#[derive(Default, Debug, Eq, PartialEq)]
-struct TraitRefStorage {
-    arena: Arena<Arc<TraitRef>>,
-    map: FxHashMap<Arc<TraitRef>, Idx<Arc<TraitRef>>>,
-}
-
-impl TraitRefStorage {
-    // Note: We lie about the `Idx<TraitRef>` to hide the interner details.
-
-    fn intern(&mut self, ty: TraitRef) -> Idx<TraitRef> {
-        if let Some(id) = self.map.get(&ty) {
-            return Idx::from_raw(id.into_raw());
-        }
-
-        let ty = Arc::new(ty);
-        let idx = self.arena.alloc(ty.clone());
-        self.map.insert(ty, idx);
-        Idx::from_raw(idx.into_raw())
-    }
-
-    fn lookup(&self, id: Idx<TraitRef>) -> &TraitRef {
-        &self.arena[Idx::from_raw(id.into_raw())]
-    }
-}
-
 #[derive(Default, Debug, Eq, PartialEq)]
 struct ItemTreeData {
     imports: Arena<Import>,
@@ -346,8 +290,6 @@ struct ItemTreeData {
 
     vis: ItemVisibilities,
     generics: GenericParamsStorage,
-    type_refs: TypeRefStorage,
-    trait_refs: TraitRefStorage,
 
     inner_items: FxHashMap<FileAstId<ast::BlockExpr>, SmallVec<[ModItem; 1]>>,
 }
@@ -577,22 +519,6 @@ impl Index<GenericParamsId> for ItemTree {
     }
 }
 
-impl Index<Idx<TypeRef>> for ItemTree {
-    type Output = TypeRef;
-
-    fn index(&self, id: Idx<TypeRef>) -> &Self::Output {
-        self.data().type_refs.lookup(id)
-    }
-}
-
-impl Index<Idx<TraitRef>> for ItemTree {
-    type Output = TraitRef;
-
-    fn index(&self, id: Idx<TraitRef>) -> &Self::Output {
-        self.data().trait_refs.lookup(id)
-    }
-}
-
 impl<N: ItemTreeNode> Index<FileItemTreeId<N>> for ItemTree {
     type Output = N;
     fn index(&self, id: FileItemTreeId<N>) -> &N {
@@ -637,13 +563,13 @@ pub struct Function {
     /// `extern "abi" fn`).
     pub is_in_extern_block: bool,
     pub params: IdRange<Param>,
-    pub ret_type: Idx<TypeRef>,
+    pub ret_type: Interned<TypeRef>,
     pub ast_id: FileAstId<ast::Fn>,
 }
 
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum Param {
-    Normal(Idx<TypeRef>),
+    Normal(Interned<TypeRef>),
     Varargs,
 }
 
@@ -699,7 +625,7 @@ pub struct Const {
     /// const _: () = ();
     pub name: Option<Name>,
     pub visibility: RawVisibilityId,
-    pub type_ref: Idx<TypeRef>,
+    pub type_ref: Interned<TypeRef>,
     pub ast_id: FileAstId<ast::Const>,
 }
 
@@ -710,7 +636,7 @@ pub struct Static {
     pub mutable: bool,
     /// Whether the static is in an `extern` block.
     pub is_extern: bool,
-    pub type_ref: Idx<TypeRef>,
+    pub type_ref: Interned<TypeRef>,
     pub ast_id: FileAstId<ast::Static>,
 }
 
@@ -729,8 +655,8 @@ pub struct Trait {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Impl {
     pub generic_params: GenericParamsId,
-    pub target_trait: Option<Idx<TraitRef>>,
-    pub self_ty: Idx<TypeRef>,
+    pub target_trait: Option<Interned<TraitRef>>,
+    pub self_ty: Interned<TypeRef>,
     pub is_negative: bool,
     pub items: Box<[AssocItem]>,
     pub ast_id: FileAstId<ast::Impl>,
@@ -743,7 +669,7 @@ pub struct TypeAlias {
     /// Bounds on the type alias itself. Only valid in trait declarations, eg. `type Assoc: Copy;`.
     pub bounds: Box<[TypeBound]>,
     pub generic_params: GenericParamsId,
-    pub type_ref: Option<Idx<TypeRef>>,
+    pub type_ref: Option<Interned<TypeRef>>,
     pub is_extern: bool,
     pub ast_id: FileAstId<ast::TypeAlias>,
 }
@@ -933,6 +859,6 @@ pub enum Fields {
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Field {
     pub name: Name,
-    pub type_ref: Idx<TypeRef>,
+    pub type_ref: Interned<TypeRef>,
     pub visibility: RawVisibilityId,
 }
diff --git a/crates/hir_def/src/item_tree/lower.rs b/crates/hir_def/src/item_tree/lower.rs
index 124dcc866..23d3dea7b 100644
--- a/crates/hir_def/src/item_tree/lower.rs
+++ b/crates/hir_def/src/item_tree/lower.rs
@@ -362,7 +362,7 @@ impl Ctx {
                         }
                     }
                 };
-                let ty = self.data().type_refs.intern(self_type);
+                let ty = Interned::new(self_type);
                 let idx = self.data().params.alloc(Param::Normal(ty));
                 self.add_attrs(idx.into(), RawAttrs::new(&self_param, &self.hygiene));
                 has_self_param = true;
@@ -372,7 +372,7 @@ impl Ctx {
                     Some(_) => self.data().params.alloc(Param::Varargs),
                     None => {
                         let type_ref = TypeRef::from_ast_opt(&self.body_ctx, param.ty());
-                        let ty = self.data().type_refs.intern(type_ref);
+                        let ty = Interned::new(type_ref);
                         self.data().params.alloc(Param::Normal(ty))
                     }
                 };
@@ -395,8 +395,6 @@ impl Ctx {
             ret_type
         };
 
-        let ret_type = self.data().type_refs.intern(ret_type);
-
         let has_body = func.body().is_some();
 
         let ast_id = self.source_ast_id_map.ast_id(func);
@@ -428,7 +426,7 @@ impl Ctx {
             qualifier,
             is_in_extern_block: false,
             params,
-            ret_type,
+            ret_type: Interned::new(ret_type),
             ast_id,
         };
         res.generic_params = self.lower_generic_params(GenericsOwner::Function(&res), func);
@@ -694,8 +692,7 @@ impl Ctx {
                 generics.fill(&self.body_ctx, sm, node);
                 // lower `impl Trait` in arguments
                 for id in func.params.clone() {
-                    if let Param::Normal(ty) = self.data().params[id] {
-                        let ty = self.data().type_refs.lookup(ty);
+                    if let Param::Normal(ty) = &self.data().params[id] {
                         generics.fill_implicit_impl_trait_args(ty);
                     }
                 }
@@ -749,20 +746,20 @@ impl Ctx {
         self.data().vis.alloc(vis)
     }
 
-    fn lower_trait_ref(&mut self, trait_ref: &ast::Type) -> Option<Idx<TraitRef>> {
+    fn lower_trait_ref(&mut self, trait_ref: &ast::Type) -> Option<Interned<TraitRef>> {
         let trait_ref = TraitRef::from_ast(&self.body_ctx, trait_ref.clone())?;
-        Some(self.data().trait_refs.intern(trait_ref))
+        Some(Interned::new(trait_ref))
     }
 
-    fn lower_type_ref(&mut self, type_ref: &ast::Type) -> Idx<TypeRef> {
+    fn lower_type_ref(&mut self, type_ref: &ast::Type) -> Interned<TypeRef> {
         let tyref = TypeRef::from_ast(&self.body_ctx, type_ref.clone());
-        self.data().type_refs.intern(tyref)
+        Interned::new(tyref)
     }
 
-    fn lower_type_ref_opt(&mut self, type_ref: Option<ast::Type>) -> Idx<TypeRef> {
+    fn lower_type_ref_opt(&mut self, type_ref: Option<ast::Type>) -> Interned<TypeRef> {
         match type_ref.map(|ty| self.lower_type_ref(&ty)) {
             Some(it) => it,
-            None => self.data().type_refs.intern(TypeRef::Error),
+            None => Interned::new(TypeRef::Error),
         }
     }
 
diff --git a/crates/hir_def/src/lib.rs b/crates/hir_def/src/lib.rs
index c9e07de86..f408e510a 100644
--- a/crates/hir_def/src/lib.rs
+++ b/crates/hir_def/src/lib.rs
@@ -49,6 +49,7 @@ pub mod import_map;
 
 #[cfg(test)]
 mod test_db;
+mod intern;
 
 use std::{
     hash::{Hash, Hasher},