Rollup merge of #67791 - Zoxc:lift-interning, r=eddyb

Implement Lift using interners instead of in_arena

r? @eddyb
cc @cjgillot

8 files changed, 67 insertions, 132 deletions

diff --git a/src/libarena/lib.rs b/src/libarena/lib.rs
index beb0bac17d2..2a3d92edc49 100644
--- a/src/libarena/lib.rs
+++ b/src/libarena/lib.rs
@@ -21,7 +21,6 @@
 extern crate alloc;
 
 use rustc_data_structures::cold_path;
-use rustc_data_structures::sync::MTLock;
 use smallvec::SmallVec;
 
 use std::cell::{Cell, RefCell};
@@ -116,11 +115,6 @@ impl<T> Default for TypedArena<T> {
 }
 
 impl<T> TypedArena<T> {
-    pub fn in_arena(&self, ptr: *const T) -> bool {
-        let ptr = ptr as *const T as *mut T;
-
-        self.chunks.borrow().iter().any(|chunk| chunk.start() <= ptr && ptr < chunk.end())
-    }
     /// Allocates an object in the `TypedArena`, returning a reference to it.
     #[inline]
     pub fn alloc(&self, object: T) -> &mut T {
@@ -334,12 +328,6 @@ impl Default for DroplessArena {
 }
 
 impl DroplessArena {
-    pub fn in_arena<T: ?Sized>(&self, ptr: *const T) -> bool {
-        let ptr = ptr as *const u8 as *mut u8;
-
-        self.chunks.borrow().iter().any(|chunk| chunk.start() <= ptr && ptr < chunk.end())
-    }
-
     #[inline]
     fn align(&self, align: usize) {
         let final_address = ((self.ptr.get() as usize) + align - 1) & !(align - 1);
@@ -500,66 +488,5 @@ impl DroplessArena {
     }
 }
 
-#[derive(Default)]
-// FIXME(@Zoxc): this type is entirely unused in rustc
-pub struct SyncTypedArena<T> {
-    lock: MTLock<TypedArena<T>>,
-}
-
-impl<T> SyncTypedArena<T> {
-    #[inline(always)]
-    pub fn alloc(&self, object: T) -> &mut T {
-        // Extend the lifetime of the result since it's limited to the lock guard
-        unsafe { &mut *(self.lock.lock().alloc(object) as *mut T) }
-    }
-
-    #[inline(always)]
-    pub fn alloc_slice(&self, slice: &[T]) -> &mut [T]
-    where
-        T: Copy,
-    {
-        // Extend the lifetime of the result since it's limited to the lock guard
-        unsafe { &mut *(self.lock.lock().alloc_slice(slice) as *mut [T]) }
-    }
-
-    #[inline(always)]
-    pub fn clear(&mut self) {
-        self.lock.get_mut().clear();
-    }
-}
-
-#[derive(Default)]
-pub struct SyncDroplessArena {
-    lock: MTLock<DroplessArena>,
-}
-
-impl SyncDroplessArena {
-    #[inline(always)]
-    pub fn in_arena<T: ?Sized>(&self, ptr: *const T) -> bool {
-        self.lock.lock().in_arena(ptr)
-    }
-
-    #[inline(always)]
-    pub fn alloc_raw(&self, bytes: usize, align: usize) -> &mut [u8] {
-        // Extend the lifetime of the result since it's limited to the lock guard
-        unsafe { &mut *(self.lock.lock().alloc_raw(bytes, align) as *mut [u8]) }
-    }
-
-    #[inline(always)]
-    pub fn alloc<T>(&self, object: T) -> &mut T {
-        // Extend the lifetime of the result since it's limited to the lock guard
-        unsafe { &mut *(self.lock.lock().alloc(object) as *mut T) }
-    }
-
-    #[inline(always)]
-    pub fn alloc_slice<T>(&self, slice: &[T]) -> &mut [T]
-    where
-        T: Copy,
-    {
-        // Extend the lifetime of the result since it's limited to the lock guard
-        unsafe { &mut *(self.lock.lock().alloc_slice(slice) as *mut [T]) }
-    }
-}
-
 #[cfg(test)]
 mod tests;
diff --git a/src/librustc/arena.rs b/src/librustc/arena.rs
index cb3fdff53a3..15e92d8d842 100644
--- a/src/librustc/arena.rs
+++ b/src/librustc/arena.rs
@@ -123,6 +123,9 @@ macro_rules! arena_types {
             [few] inferred_outlives_crate: rustc::ty::CratePredicatesMap<'tcx>,
             [] upvars: rustc_data_structures::fx::FxIndexMap<rustc_hir::HirId, rustc_hir::Upvar>,
 
+            // Interned types
+            [] tys: rustc::ty::TyS<$tcx>,
+
             // HIR types
             [few] hir_forest: rustc::hir::map::Forest<$tcx>,
             [] arm: rustc_hir::Arm<$tcx>,
@@ -176,7 +179,7 @@ macro_rules! declare_arena {
     ([], [$($a:tt $name:ident: $ty:ty,)*], $tcx:lifetime) => {
         #[derive(Default)]
         pub struct Arena<$tcx> {
-            dropless: DroplessArena,
+            pub dropless: DroplessArena,
             drop: DropArena,
             $($name: arena_for_type!($a[$ty]),)*
         }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index ef776c88a8f..a51f0f7f24c 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -51,10 +51,9 @@ use rustc_session::config::CrateType;
 use rustc_session::config::{BorrowckMode, OutputFilenames};
 use rustc_session::Session;
 
-use arena::SyncDroplessArena;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::profiling::SelfProfilerRef;
-use rustc_data_structures::sharded::ShardedHashMap;
+use rustc_data_structures::sharded::{IntoPointer, ShardedHashMap};
 use rustc_data_structures::stable_hasher::{
     hash_stable_hashmap, HashStable, StableHasher, StableVec,
 };
@@ -83,21 +82,11 @@ use syntax::ast;
 use syntax::attr;
 use syntax::expand::allocator::AllocatorKind;
 
-pub struct AllArenas {
-    pub interner: SyncDroplessArena,
-}
-
-impl AllArenas {
-    pub fn new() -> Self {
-        AllArenas { interner: SyncDroplessArena::default() }
-    }
-}
-
 type InternedSet<'tcx, T> = ShardedHashMap<Interned<'tcx, T>, ()>;
 
 pub struct CtxtInterners<'tcx> {
     /// The arena that types, regions, etc. are allocated from.
-    arena: &'tcx SyncDroplessArena,
+    arena: &'tcx WorkerLocal<Arena<'tcx>>,
 
     /// Specifically use a speedy hash algorithm for these hash sets, since
     /// they're accessed quite often.
@@ -117,7 +106,7 @@ pub struct CtxtInterners<'tcx> {
 }
 
 impl<'tcx> CtxtInterners<'tcx> {
-    fn new(arena: &'tcx SyncDroplessArena) -> CtxtInterners<'tcx> {
+    fn new(arena: &'tcx WorkerLocal<Arena<'tcx>>) -> CtxtInterners<'tcx> {
         CtxtInterners {
             arena,
             type_: Default::default(),
@@ -1125,7 +1114,6 @@ impl<'tcx> TyCtxt<'tcx> {
         lint_store: Lrc<dyn Any + sync::Send + sync::Sync>,
         local_providers: ty::query::Providers<'tcx>,
         extern_providers: ty::query::Providers<'tcx>,
-        arenas: &'tcx AllArenas,
         arena: &'tcx WorkerLocal<Arena<'tcx>>,
         resolutions: ty::ResolverOutputs,
         hir: hir_map::Map<'tcx>,
@@ -1136,7 +1124,7 @@ impl<'tcx> TyCtxt<'tcx> {
         let data_layout = TargetDataLayout::parse(&s.target.target).unwrap_or_else(|err| {
             s.fatal(&err);
         });
-        let interners = CtxtInterners::new(&arenas.interner);
+        let interners = CtxtInterners::new(arena);
         let common_types = CommonTypes::new(&interners);
         let common_lifetimes = CommonLifetimes::new(&interners);
         let common_consts = CommonConsts::new(&interners, &common_types);
@@ -1567,11 +1555,11 @@ pub trait Lift<'tcx>: fmt::Debug {
 }
 
 macro_rules! nop_lift {
-    ($ty:ty => $lifted:ty) => {
+    ($set:ident; $ty:ty => $lifted:ty) => {
         impl<'a, 'tcx> Lift<'tcx> for $ty {
             type Lifted = $lifted;
             fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-                if tcx.interners.arena.in_arena(*self as *const _) {
+                if tcx.interners.$set.contains_pointer_to(&Interned(*self)) {
                     Some(unsafe { mem::transmute(*self) })
                 } else {
                     None
@@ -1582,14 +1570,14 @@ macro_rules! nop_lift {
 }
 
 macro_rules! nop_list_lift {
-    ($ty:ty => $lifted:ty) => {
+    ($set:ident; $ty:ty => $lifted:ty) => {
         impl<'a, 'tcx> Lift<'tcx> for &'a List<$ty> {
             type Lifted = &'tcx List<$lifted>;
             fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
                 if self.is_empty() {
                     return Some(List::empty());
                 }
-                if tcx.interners.arena.in_arena(*self as *const _) {
+                if tcx.interners.$set.contains_pointer_to(&Interned(*self)) {
                     Some(unsafe { mem::transmute(*self) })
                 } else {
                     None
@@ -1599,21 +1587,21 @@ macro_rules! nop_list_lift {
     };
 }
 
-nop_lift! {Ty<'a> => Ty<'tcx>}
-nop_lift! {Region<'a> => Region<'tcx>}
-nop_lift! {Goal<'a> => Goal<'tcx>}
-nop_lift! {&'a Const<'a> => &'tcx Const<'tcx>}
+nop_lift! {type_; Ty<'a> => Ty<'tcx>}
+nop_lift! {region; Region<'a> => Region<'tcx>}
+nop_lift! {goal; Goal<'a> => Goal<'tcx>}
+nop_lift! {const_; &'a Const<'a> => &'tcx Const<'tcx>}
 
-nop_list_lift! {Goal<'a> => Goal<'tcx>}
-nop_list_lift! {Clause<'a> => Clause<'tcx>}
-nop_list_lift! {Ty<'a> => Ty<'tcx>}
-nop_list_lift! {ExistentialPredicate<'a> => ExistentialPredicate<'tcx>}
-nop_list_lift! {Predicate<'a> => Predicate<'tcx>}
-nop_list_lift! {CanonicalVarInfo => CanonicalVarInfo}
-nop_list_lift! {ProjectionKind => ProjectionKind}
+nop_list_lift! {goal_list; Goal<'a> => Goal<'tcx>}
+nop_list_lift! {clauses; Clause<'a> => Clause<'tcx>}
+nop_list_lift! {type_list; Ty<'a> => Ty<'tcx>}
+nop_list_lift! {existential_predicates; ExistentialPredicate<'a> => ExistentialPredicate<'tcx>}
+nop_list_lift! {predicates; Predicate<'a> => Predicate<'tcx>}
+nop_list_lift! {canonical_var_infos; CanonicalVarInfo => CanonicalVarInfo}
+nop_list_lift! {projs; ProjectionKind => ProjectionKind}
 
 // This is the impl for `&'a InternalSubsts<'a>`.
-nop_list_lift! {GenericArg<'a> => GenericArg<'tcx>}
+nop_list_lift! {substs; GenericArg<'a> => GenericArg<'tcx>}
 
 pub mod tls {
     use super::{ptr_eq, GlobalCtxt, TyCtxt};
@@ -1937,6 +1925,11 @@ impl<'tcx, T: 'tcx + ?Sized> Clone for Interned<'tcx, T> {
 }
 impl<'tcx, T: 'tcx + ?Sized> Copy for Interned<'tcx, T> {}
 
+impl<'tcx, T: 'tcx + ?Sized> IntoPointer for Interned<'tcx, T> {
+    fn into_pointer(&self) -> *const () {
+        self.0 as *const _ as *const ()
+    }
+}
 // N.B., an `Interned<Ty>` compares and hashes as a `TyKind`.
 impl<'tcx> PartialEq for Interned<'tcx, TyS<'tcx>> {
     fn eq(&self, other: &Interned<'tcx, TyS<'tcx>>) -> bool {
@@ -2089,7 +2082,7 @@ macro_rules! slice_interners {
         $(impl<'tcx> TyCtxt<'tcx> {
             pub fn $method(self, v: &[$ty]) -> &'tcx List<$ty> {
                 self.interners.$field.intern_ref(v, || {
-                    Interned(List::from_arena(&self.interners.arena, v))
+                    Interned(List::from_arena(&*self.arena, v))
                 }).0
             }
         })+
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index e6acb6b74dc..282136fa354 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -6,6 +6,7 @@ pub use self::BorrowKind::*;
 pub use self::IntVarValue::*;
 pub use self::Variance::*;
 
+use crate::arena::Arena;
 use crate::hir::exports::ExportMap;
 use crate::hir::map as hir_map;
 
@@ -25,7 +26,6 @@ use crate::ty::layout::VariantIdx;
 use crate::ty::subst::{InternalSubsts, Subst, SubstsRef};
 use crate::ty::util::{Discr, IntTypeExt};
 use crate::ty::walk::TypeWalker;
-use arena::SyncDroplessArena;
 use rustc_data_structures::captures::Captures;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::fx::FxIndexMap;
@@ -74,7 +74,7 @@ pub use crate::ty::diagnostics::*;
 pub use self::binding::BindingMode;
 pub use self::binding::BindingMode::*;
 
-pub use self::context::{keep_local, tls, AllArenas, FreeRegionInfo, TyCtxt};
+pub use self::context::{keep_local, tls, FreeRegionInfo, TyCtxt};
 pub use self::context::{
     CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, ResolvedOpaqueTy,
     UserType, UserTypeAnnotationIndex,
@@ -604,7 +604,7 @@ unsafe impl<T: Sync> Sync for List<T> {}
 
 impl<T: Copy> List<T> {
     #[inline]
-    fn from_arena<'tcx>(arena: &'tcx SyncDroplessArena, slice: &[T]) -> &'tcx List<T> {
+    fn from_arena<'tcx>(arena: &'tcx Arena<'tcx>, slice: &[T]) -> &'tcx List<T> {
         assert!(!mem::needs_drop::<T>());
         assert!(mem::size_of::<T>() != 0);
         assert!(slice.len() != 0);
@@ -617,7 +617,9 @@ impl<T: Copy> List<T> {
 
         let size = offset + slice.len() * mem::size_of::<T>();
 
-        let mem = arena.alloc_raw(size, cmp::max(mem::align_of::<T>(), mem::align_of::<usize>()));
+        let mem = arena
+            .dropless
+            .alloc_raw(size, cmp::max(mem::align_of::<T>(), mem::align_of::<usize>()));
         unsafe {
             let result = &mut *(mem.as_mut_ptr() as *mut List<T>);
             // Write the length
diff --git a/src/librustc_data_structures/sharded.rs b/src/librustc_data_structures/sharded.rs
index 8b85d97a1d4..ee3f88ff167 100644
--- a/src/librustc_data_structures/sharded.rs
+++ b/src/librustc_data_structures/sharded.rs
@@ -137,6 +137,20 @@ impl<K: Eq + Hash + Copy> ShardedHashMap<K, ()> {
     }
 }
 
+pub trait IntoPointer {
+    /// Returns a pointer which outlives `self`.
+    fn into_pointer(&self) -> *const ();
+}
+
+impl<K: Eq + Hash + Copy + IntoPointer> ShardedHashMap<K, ()> {
+    pub fn contains_pointer_to<T: Hash + IntoPointer>(&self, value: &T) -> bool {
+        let hash = make_hash(&value);
+        let shard = self.get_shard_by_hash(hash).lock();
+        let value = value.into_pointer();
+        shard.raw_entry().from_hash(hash, |entry| entry.into_pointer() == value).is_some()
+    }
+}
+
 #[inline]
 fn make_hash<K: Hash + ?Sized>(val: &K) -> u64 {
     let mut state = FxHasher::default();
diff --git a/src/librustc_interface/passes.rs b/src/librustc_interface/passes.rs
index c4444fbaa2f..d62c7539d5f 100644
--- a/src/librustc_interface/passes.rs
+++ b/src/librustc_interface/passes.rs
@@ -15,7 +15,7 @@ use rustc::session::search_paths::PathKind;
 use rustc::session::Session;
 use rustc::traits;
 use rustc::ty::steal::Steal;
-use rustc::ty::{self, AllArenas, GlobalCtxt, ResolverOutputs, TyCtxt};
+use rustc::ty::{self, GlobalCtxt, ResolverOutputs, TyCtxt};
 use rustc::util::common::ErrorReported;
 use rustc_builtin_macros;
 use rustc_codegen_ssa::back::link::emit_metadata;
@@ -715,7 +715,6 @@ pub fn create_global_ctxt<'tcx>(
     outputs: OutputFilenames,
     crate_name: &str,
     global_ctxt: &'tcx Once<GlobalCtxt<'tcx>>,
-    all_arenas: &'tcx AllArenas,
     arena: &'tcx WorkerLocal<Arena<'tcx>>,
 ) -> QueryContext<'tcx> {
     let sess = &compiler.session();
@@ -746,7 +745,6 @@ pub fn create_global_ctxt<'tcx>(
                 lint_store,
                 local_providers,
                 extern_providers,
-                &all_arenas,
                 arena,
                 resolver_outputs,
                 hir_map,
diff --git a/src/librustc_interface/queries.rs b/src/librustc_interface/queries.rs
index bd9717d3f3d..0af9b17a299 100644
--- a/src/librustc_interface/queries.rs
+++ b/src/librustc_interface/queries.rs
@@ -7,7 +7,7 @@ use rustc::hir::map;
 use rustc::session::config::{OutputFilenames, OutputType};
 use rustc::session::Session;
 use rustc::ty::steal::Steal;
-use rustc::ty::{AllArenas, GlobalCtxt, ResolverOutputs};
+use rustc::ty::{GlobalCtxt, ResolverOutputs};
 use rustc::util::common::ErrorReported;
 use rustc_codegen_utils::codegen_backend::CodegenBackend;
 use rustc_data_structures::sync::{Lrc, Once, WorkerLocal};
@@ -66,7 +66,6 @@ pub struct Queries<'tcx> {
     compiler: &'tcx Compiler,
     gcx: Once<GlobalCtxt<'tcx>>,
 
-    all_arenas: AllArenas,
     arena: WorkerLocal<Arena<'tcx>>,
 
     dep_graph_future: Query<Option<DepGraphFuture>>,
@@ -86,7 +85,6 @@ impl<'tcx> Queries<'tcx> {
         Queries {
             compiler,
             gcx: Once::new(),
-            all_arenas: AllArenas::new(),
             arena: WorkerLocal::new(|_| Arena::default()),
             dep_graph_future: Default::default(),
             parse: Default::default(),
@@ -265,7 +263,6 @@ impl<'tcx> Queries<'tcx> {
                 outputs,
                 &crate_name,
                 &self.gcx,
-                &self.all_arenas,
                 &self.arena,
             ))
         })
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index a3be264ddc1..173bb29e964 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1320,10 +1320,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 // those that do.
                 self.one_bound_for_assoc_type(
                     || traits::supertraits(tcx, trait_ref),
-                    &trait_ref.print_only_trait_path().to_string(),
+                    || trait_ref.print_only_trait_path().to_string(),
                     binding.item_name,
                     path_span,
-                    match binding.kind {
+                    || match binding.kind {
                         ConvertedBindingKind::Equality(ty) => Some(ty.to_string()),
                         _ => None,
                     },
@@ -1880,10 +1880,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     predicates.iter().filter_map(|(p, _)| p.to_opt_poly_trait_ref()),
                 )
             },
-            &param_name.as_str(),
+            || param_name.to_string(),
             assoc_name,
             span,
-            None,
+            || None,
         )
     }
 
@@ -1892,10 +1892,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     fn one_bound_for_assoc_type<I>(
         &self,
         all_candidates: impl Fn() -> I,
-        ty_param_name: &str,
+        ty_param_name: impl Fn() -> String,
         assoc_name: ast::Ident,
         span: Span,
-        is_equality: Option<String>,
+        is_equality: impl Fn() -> Option<String>,
     ) -> Result<ty::PolyTraitRef<'tcx>, ErrorReported>
     where
         I: Iterator<Item = ty::PolyTraitRef<'tcx>>,
@@ -1908,7 +1908,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             None => {
                 self.complain_about_assoc_type_not_found(
                     all_candidates,
-                    ty_param_name,
+                    &ty_param_name(),
                     assoc_name,
                     span,
                 );
@@ -1921,6 +1921,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         if let Some(bound2) = matching_candidates.next() {
             debug!("one_bound_for_assoc_type: bound2 = {:?}", bound2);
 
+            let is_equality = is_equality();
             let bounds = iter::once(bound).chain(iter::once(bound2)).chain(matching_candidates);
             let mut err = if is_equality.is_some() {
                 // More specific Error Index entry.
@@ -1930,7 +1931,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     E0222,
                     "ambiguous associated type `{}` in bounds of `{}`",
                     assoc_name,
-                    ty_param_name
+                    ty_param_name()
                 )
             } else {
                 struct_span_err!(
@@ -1939,7 +1940,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     E0221,
                     "ambiguous associated type `{}` in bounds of `{}`",
                     assoc_name,
-                    ty_param_name
+                    ty_param_name()
                 )
             };
             err.span_label(span, format!("ambiguous associated type `{}`", assoc_name));
@@ -1977,7 +1978,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                             "use fully qualified syntax to disambiguate",
                             format!(
                                 "<{} as {}>::{}",
-                                ty_param_name,
+                                ty_param_name(),
                                 bound.print_only_trait_path(),
                                 assoc_name,
                             ),
@@ -1987,7 +1988,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 } else {
                     err.note(&format!(
                         "associated type `{}` could derive from `{}`",
-                        ty_param_name,
+                        ty_param_name(),
                         bound.print_only_trait_path(),
                     ));
                 }
@@ -1996,7 +1997,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 err.help(&format!(
                     "consider introducing a new type parameter `T` and adding `where` constraints:\
                      \n    where\n        T: {},\n{}",
-                    ty_param_name,
+                    ty_param_name(),
                     where_bounds.join(",\n"),
                 ));
             }
@@ -2110,10 +2111,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
 
                 self.one_bound_for_assoc_type(
                     || traits::supertraits(tcx, ty::Binder::bind(trait_ref)),
-                    "Self",
+                    || "Self".to_string(),
                     assoc_ident,
                     span,
-                    None,
+                    || None,
                 )?
             }
             (&ty::Param(_), Res::SelfTy(Some(param_did), None))