From b00266b79f0e2c2a5e332b30f7e6aba83b5e6e5a Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Thu, 1 Apr 2021 19:46:43 +0200 Subject: Global TypeRef/TraitRef interning --- crates/hir/src/display.rs | 2 +- crates/hir/src/lib.rs | 8 +- crates/hir_def/Cargo.toml | 1 + crates/hir_def/src/adt.rs | 9 +- crates/hir_def/src/data.rs | 29 ++++--- crates/hir_def/src/intern.rs | 157 ++++++++++++++++++++++++++++++++++ crates/hir_def/src/item_tree.rs | 92 ++------------------ crates/hir_def/src/item_tree/lower.rs | 23 +++-- crates/hir_def/src/lib.rs | 1 + crates/hir_ty/src/lower.rs | 2 +- 10 files changed, 204 insertions(+), 120 deletions(-) create mode 100644 crates/hir_def/src/intern.rs (limited to 'crates') diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs index 97a78ca25..ab04c55bc 100644 --- a/crates/hir/src/display.rs +++ b/crates/hir/src/display.rs @@ -91,7 +91,7 @@ impl HirDisplay for Function { let ret_type = if !qual.is_async { &data.ret_type } else { - match &data.ret_type { + match &*data.ret_type { TypeRef::ImplTrait(bounds) => match &bounds[0] { TypeBound::Path(path) => { path.segments().iter().last().unwrap().args_and_bindings.unwrap().bindings diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs index 97f162315..06fd6542d 100644 --- a/crates/hir/src/lib.rs +++ b/crates/hir/src/lib.rs @@ -957,7 +957,7 @@ impl SelfParam { func_data .params .first() - .map(|param| match *param { + .map(|param| match &**param { TypeRef::Reference(.., mutability) => match mutability { hir_def::type_ref::Mutability::Shared => Access::Shared, hir_def::type_ref::Mutability::Mut => Access::Exclusive, @@ -1011,7 +1011,7 @@ impl Const { } pub fn type_ref(self, db: &dyn HirDatabase) -> TypeRef { - db.const_data(self.id).type_ref.clone() + db.const_data(self.id).type_ref.as_ref().clone() } } @@ -1101,7 +1101,7 @@ impl TypeAlias { } pub fn type_ref(self, db: &dyn HirDatabase) -> Option { - db.type_alias_data(self.id).type_ref.clone() + db.type_alias_data(self.id).type_ref.as_deref().cloned() } pub fn ty(self, db: &dyn HirDatabase) -> Type { @@ -1615,7 +1615,7 @@ impl Impl { // FIXME: the return type is wrong. This should be a hir version of // `TraitRef` (ie, resolved `TypeRef`). pub fn trait_(self, db: &dyn HirDatabase) -> Option { - db.impl_data(self.id).target_trait.clone() + db.impl_data(self.id).target_trait.as_deref().cloned() } pub fn self_ty(self, db: &dyn HirDatabase) -> Type { 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, 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, - pub ret_type: TypeRef, + pub params: Vec>, + pub ret_type: Interned, 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, + pub type_ref: Option>, 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, - pub self_ty: TypeRef, + pub target_trait: Option>, + pub self_ty: Interned, pub items: Vec, 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, - pub type_ref: TypeRef, + pub type_ref: Interned, 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, - pub type_ref: TypeRef, + pub type_ref: Interned, 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 = DashMap, (), BuildHasherDefault>; + +pub struct Interned { + arc: Arc, +} + +impl Interned { + 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 Drop for Interned { + 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 PartialEq for Interned { + #[inline] + fn eq(&self, other: &Self) -> bool { + Arc::ptr_eq(&self.arc, &other.arc) + } +} + +impl Eq for Interned {} + +impl AsRef for Interned { + #[inline] + fn as_ref(&self) -> &T { + &self.arc + } +} + +impl Deref for Interned { + type Target = T; + + #[inline] + fn deref(&self) -> &Self::Target { + &self.arc + } +} + +impl Clone for Interned { + fn clone(&self) -> Self { + Self { arc: self.arc.clone() } + } +} + +impl Debug for Interned { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + (*self.arc).fmt(f) + } +} + +pub struct InternStorage { + map: OnceCell>, +} + +impl InternStorage { + pub const fn new() -> Self { + Self { map: OnceCell::new() } + } +} + +impl InternStorage { + fn get(&self) -> &InternMap { + self.map.get_or_init(DashMap::default) + } +} + +pub trait Internable: Hash + Eq + Sized + 'static { + fn storage() -> &'static InternStorage; +} + +// region:`Internable` implementations + +macro_rules! impl_internable { + ( $($t:ty),+ $(,)? ) => { $( + impl Internable for $t { + fn storage() -> &'static InternStorage { + 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>, - map: FxHashMap, Idx>>, -} - -impl TypeRefStorage { - // Note: We lie about the `Idx` to hide the interner details. - - fn intern(&mut self, ty: TypeRef) -> Idx { - 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 { - &self.arena[Idx::from_raw(id.into_raw())] - } -} - -/// `TraitRef` interner. -#[derive(Default, Debug, Eq, PartialEq)] -struct TraitRefStorage { - arena: Arena>, - map: FxHashMap, Idx>>, -} - -impl TraitRefStorage { - // Note: We lie about the `Idx` to hide the interner details. - - fn intern(&mut self, ty: TraitRef) -> Idx { - 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 { - &self.arena[Idx::from_raw(id.into_raw())] - } -} - #[derive(Default, Debug, Eq, PartialEq)] struct ItemTreeData { imports: Arena, @@ -346,8 +290,6 @@ struct ItemTreeData { vis: ItemVisibilities, generics: GenericParamsStorage, - type_refs: TypeRefStorage, - trait_refs: TraitRefStorage, inner_items: FxHashMap, SmallVec<[ModItem; 1]>>, } @@ -577,22 +519,6 @@ impl Index for ItemTree { } } -impl Index> for ItemTree { - type Output = TypeRef; - - fn index(&self, id: Idx) -> &Self::Output { - self.data().type_refs.lookup(id) - } -} - -impl Index> for ItemTree { - type Output = TraitRef; - - fn index(&self, id: Idx) -> &Self::Output { - self.data().trait_refs.lookup(id) - } -} - impl Index> for ItemTree { type Output = N; fn index(&self, id: FileItemTreeId) -> &N { @@ -637,13 +563,13 @@ pub struct Function { /// `extern "abi" fn`). pub is_in_extern_block: bool, pub params: IdRange, - pub ret_type: Idx, + pub ret_type: Interned, pub ast_id: FileAstId, } #[derive(Debug, Clone, Eq, PartialEq)] pub enum Param { - Normal(Idx), + Normal(Interned), Varargs, } @@ -699,7 +625,7 @@ pub struct Const { /// const _: () = (); pub name: Option, pub visibility: RawVisibilityId, - pub type_ref: Idx, + pub type_ref: Interned, pub ast_id: FileAstId, } @@ -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, + pub type_ref: Interned, pub ast_id: FileAstId, } @@ -729,8 +655,8 @@ pub struct Trait { #[derive(Debug, Clone, Eq, PartialEq)] pub struct Impl { pub generic_params: GenericParamsId, - pub target_trait: Option>, - pub self_ty: Idx, + pub target_trait: Option>, + pub self_ty: Interned, pub is_negative: bool, pub items: Box<[AssocItem]>, pub ast_id: FileAstId, @@ -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>, + pub type_ref: Option>, pub is_extern: bool, pub ast_id: FileAstId, } @@ -933,6 +859,6 @@ pub enum Fields { #[derive(Debug, Clone, PartialEq, Eq)] pub struct Field { pub name: Name, - pub type_ref: Idx, + pub type_ref: Interned, 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> { + fn lower_trait_ref(&mut self, trait_ref: &ast::Type) -> Option> { 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 { + fn lower_type_ref(&mut self, type_ref: &ast::Type) -> Interned { 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) -> Idx { + fn lower_type_ref_opt(&mut self, type_ref: Option) -> Interned { 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}, diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs index afbfa12d5..a08f694d9 100644 --- a/crates/hir_ty/src/lower.rs +++ b/crates/hir_ty/src/lower.rs @@ -1157,7 +1157,7 @@ fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders { Binders::new(0, TyKind::ForeignType(crate::to_foreign_def_id(t)).intern(&Interner)) } else { let type_ref = &db.type_alias_data(t).type_ref; - let inner = ctx.lower_ty(type_ref.as_ref().unwrap_or(&TypeRef::Error)); + let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error)); Binders::new(generics.len(), inner) } } -- cgit v1.2.3