Rollup merge of #158642 - nnethercote:interning-clarification, r=Mark-Simulacrum Clarify some interning details Details in the commit message. r? @Mark-Simulacrum
diff --git a/compiler/rustc_data_structures/src/intern.rs b/compiler/rustc_data_structures/src/intern.rs index 042cf19..382c921 100644 --- a/compiler/rustc_data_structures/src/intern.rs +++ b/compiler/rustc_data_structures/src/intern.rs
@@ -1,4 +1,3 @@ -use std::cmp::Ordering; use std::fmt::{self, Debug}; use std::hash::{Hash, Hasher}; use std::ops::Deref; @@ -11,26 +10,40 @@ mod private { pub struct PrivateZst; } -/// A reference to a value that is interned, and is known to be unique. +/// This type is a reference with one special behaviour: the reference pointer (i.e. the address of +/// the value referred to) is used for equality and hashing, rather than the value's contents, as +/// would occur with a vanilla reference. There are two cases when this is useful. /// -/// Note that it is possible to have a `T` and a `Interned<T>` that are (or -/// refer to) equal but different values. But if you have two different -/// `Interned<T>`s, they both refer to the same value, at a single location in -/// memory. This means that equality and hashing can be done on the value's -/// address rather than the value's contents, which can improve performance. +/// - Types where uniqueness is guaranteed. This is most commonly achieved via interning -- hence +/// the name `Interned` -- though it may also be possible via other means. In this case, the use +/// of `Interned` is primarily a performance optimization, because pointer equality/hashing gives +/// the same results as value equality/hashing, but is faster. (The use of the `Interned` type +/// also provides documentation about the interned-ness.) /// -/// The `PrivateZst` field means you can pattern match with `Interned(v, _)` -/// but you can only construct a `Interned` with `new_unchecked`, and not -/// directly. +/// Note that in this case it is possible to have a `T` and a `Interned<T>` that are (or refer +/// to) equal but different values. But if you have two different `Interned<T>`s, they both refer +/// to the same value, at a single location in memory. +/// +/// - Types with identity, where distinct values should always be considered unequal, even if they +/// have equal values. These are rare in Rust, but do occur sometimes. In this case, the use of +/// `Interned` gives different behaviour, because pointer equality/hashing gives different result +/// to value equality/hashing, and is also faster. +/// +/// The `PrivateZst` field means you can pattern match with `Interned(v, _)` but you can only +/// construct a `Interned` with `new_unchecked`, and not directly. This means that all creation +/// points can be audited easily. #[rustc_pass_by_value] pub struct Interned<'a, T>(pub &'a T, pub private::PrivateZst); impl<'a, T> Interned<'a, T> { - /// Create a new `Interned` value. The value referred to *must* be interned - /// and thus be unique, and it *must* remain unique in the future. This - /// function has `_unchecked` in the name but is not `unsafe`, because if - /// the uniqueness condition is violated condition it will cause incorrect - /// behaviour but will not affect memory safety. + /// Create a new `Interned` value. The value referred to *must* satisfy one of the following + /// two conditions. + /// - It must be unique and it must remain unique in the future. + /// - It must be of a type with "identity" such that distinct values should always be + /// considered unequal. + /// + /// This function has `_unchecked` in the name but is not `unsafe`, because if neither of these + /// conditions is met it will cause incorrect behaviour but will not affect memory safety. #[inline] pub const fn new_unchecked(t: &'a T) -> Self { Interned(t, private::PrivateZst) @@ -64,41 +77,10 @@ fn eq(&self, other: &Self) -> bool { impl<'a, T> Eq for Interned<'a, T> {} -impl<'a, T: PartialOrd> PartialOrd for Interned<'a, T> { - fn partial_cmp(&self, other: &Interned<'a, T>) -> Option<Ordering> { - // Pointer equality implies equality, due to the uniqueness constraint, - // but the contents must be compared otherwise. - if ptr::eq(self.0, other.0) { - Some(Ordering::Equal) - } else { - let res = self.0.partial_cmp(other.0); - debug_assert_ne!(res, Some(Ordering::Equal)); - res - } - } -} - -impl<'a, T: Ord> Ord for Interned<'a, T> { - fn cmp(&self, other: &Interned<'a, T>) -> Ordering { - // Pointer equality implies equality, due to the uniqueness constraint, - // but the contents must be compared otherwise. - if ptr::eq(self.0, other.0) { - Ordering::Equal - } else { - let res = self.0.cmp(other.0); - debug_assert_ne!(res, Ordering::Equal); - res - } - } -} - -impl<'a, T> Hash for Interned<'a, T> -where - T: Hash, -{ +impl<'a, T> Hash for Interned<'a, T> { #[inline] fn hash<H: Hasher>(&self, s: &mut H) { - // Pointer hashing is sufficient, due to the uniqueness constraint. + // Pointer hashing is sufficient. ptr::hash(self.0, s) } }
diff --git a/compiler/rustc_data_structures/src/intern/tests.rs b/compiler/rustc_data_structures/src/intern/tests.rs index a85cd48..8b814bf 100644 --- a/compiler/rustc_data_structures/src/intern/tests.rs +++ b/compiler/rustc_data_structures/src/intern/tests.rs
@@ -1,5 +1,6 @@ use super::*; +#[allow(unused)] #[derive(Debug)] struct S(u32); @@ -11,22 +12,6 @@ fn eq(&self, _other: &Self) -> bool { impl Eq for S {} -impl PartialOrd for S { - fn partial_cmp(&self, other: &S) -> Option<Ordering> { - // The `==` case should be handled by `Interned`. - assert_ne!(self.0, other.0); - self.0.partial_cmp(&other.0) - } -} - -impl Ord for S { - fn cmp(&self, other: &S) -> Ordering { - // The `==` case should be handled by `Interned`. - assert_ne!(self.0, other.0); - self.0.cmp(&other.0) - } -} - #[test] fn test_uniq() { let s1 = S(1); @@ -45,14 +30,4 @@ fn test_uniq() { assert_eq!(v1, v1); assert_eq!(v3a, v3b); assert_ne!(v1, v4); // same content but different addresses: not equal - - assert_eq!(v1.cmp(&v2), Ordering::Less); - assert_eq!(v3a.cmp(&v2), Ordering::Greater); - assert_eq!(v1.cmp(&v1), Ordering::Equal); // only uses Interned::eq, not S::cmp - assert_eq!(v3a.cmp(&v3b), Ordering::Equal); // only uses Interned::eq, not S::cmp - - assert_eq!(v1.partial_cmp(&v2), Some(Ordering::Less)); - assert_eq!(v3a.partial_cmp(&v2), Some(Ordering::Greater)); - assert_eq!(v1.partial_cmp(&v1), Some(Ordering::Equal)); // only uses Interned::eq, not S::cmp - assert_eq!(v3a.partial_cmp(&v3b), Some(Ordering::Equal)); // only uses Interned::eq, not S::cmp }
diff --git a/compiler/rustc_resolve/src/imports.rs b/compiler/rustc_resolve/src/imports.rs index c4d668e..379ae99 100644 --- a/compiler/rustc_resolve/src/imports.rs +++ b/compiler/rustc_resolve/src/imports.rs
@@ -210,23 +210,10 @@ pub(crate) struct ImportData<'ra> { pub on_unknown_attr: Option<OnUnknownData>, } -/// All imports are unique and allocated on a same arena, -/// so we can use referential equality to compare them. +/// `Interned` is used because values of this type have "identity" and compare as unequal even if +/// they have the same contents. pub(crate) type Import<'ra> = Interned<'ra, ImportData<'ra>>; -// Allows us to use Interned without actually enforcing (via Hash/PartialEq/...) uniqueness of the -// contained data. -// FIXME: We may wish to actually have at least debug-level assertions that Interned's guarantees -// are upheld. -impl std::hash::Hash for ImportData<'_> { - fn hash<H>(&self, _: &mut H) - where - H: std::hash::Hasher, - { - unreachable!() - } -} - impl<'ra> ImportData<'ra> { pub(crate) fn is_glob(&self) -> bool { matches!(self.kind, ImportKind::Glob { .. }) @@ -291,6 +278,8 @@ pub(crate) struct NameResolution<'ra> { pub orig_ident_span: Span, } +/// `Interned` is used because values of this type have "identity" and compare as unequal even if +/// they have the same contents. pub(crate) type NameResolutionRef<'ra> = Interned<'ra, CmRefCell<NameResolution<'ra>>>; impl<'ra> NameResolution<'ra> {
diff --git a/compiler/rustc_resolve/src/lib.rs b/compiler/rustc_resolve/src/lib.rs index ca0704a..9113506 100644 --- a/compiler/rustc_resolve/src/lib.rs +++ b/compiler/rustc_resolve/src/lib.rs
@@ -683,8 +683,8 @@ struct ModuleData<'ra> { self_decl: Option<Decl<'ra>>, } -/// All modules are unique and allocated on a same arena, -/// so we can use referential equality to compare them. +/// `Interned` is used because values of this type have "identity" and compare as unequal even if +/// they have the same contents. #[derive(Clone, Copy, PartialEq, Eq, Hash)] #[rustc_pass_by_value] struct Module<'ra>(Interned<'ra, ModuleData<'ra>>); @@ -699,19 +699,6 @@ struct ModuleData<'ra> { #[rustc_pass_by_value] struct ExternModule<'ra>(Interned<'ra, ModuleData<'ra>>); -// Allows us to use Interned without actually enforcing (via Hash/PartialEq/...) uniqueness of the -// contained data. -// FIXME: We may wish to actually have at least debug-level assertions that Interned's guarantees -// are upheld. -impl std::hash::Hash for ModuleData<'_> { - fn hash<H>(&self, _: &mut H) - where - H: std::hash::Hasher, - { - unreachable!() - } -} - impl<'ra> ModuleData<'ra> { fn new( parent: Option<Module<'ra>>, @@ -916,6 +903,7 @@ fn new( assert!(kind.is_local()); let parent = parent.map(|m| m.to_module()); let data = ModuleData::new(parent, kind, expn_id, span, no_implicit_prelude, vis, arenas); + // SAFETY: `Interned` is valid because values of this type have "identity". LocalModule(Interned::new_unchecked(arenas.modules.alloc(data))) } @@ -937,6 +925,7 @@ fn new( assert!(!kind.is_local()); let parent = parent.map(|m| m.to_module()); let data = ModuleData::new(parent, kind, expn_id, span, no_implicit_prelude, vis, arenas); + // SAFETY: `Interned` is valid because values of this type have "identity". ExternModule(Interned::new_unchecked(arenas.modules.alloc(data))) } @@ -1001,23 +990,10 @@ struct DeclData<'ra> { parent_module: Option<Module<'ra>>, } -/// All name declarations are unique and allocated on a same arena, -/// so we can use referential equality to compare them. +/// `Interned` is used because values of this type have "identity" and compare as unequal even if +/// they have the same contents. type Decl<'ra> = Interned<'ra, DeclData<'ra>>; -// Allows us to use Interned without actually enforcing (via Hash/PartialEq/...) uniqueness of the -// contained data. -// FIXME: We may wish to actually have at least debug-level assertions that Interned's guarantees -// are upheld. -impl std::hash::Hash for DeclData<'_> { - fn hash<H>(&self, _: &mut H) - where - H: std::hash::Hasher, - { - unreachable!() - } -} - /// Name declaration kind. #[derive(Debug)] enum DeclKind<'ra> { @@ -1585,12 +1561,15 @@ fn new_pub_def_decl(&'ra self, res: Res, span: Span, expn_id: LocalExpnId) -> De } fn alloc_decl(&'ra self, data: DeclData<'ra>) -> Decl<'ra> { + // SAFETY: `Interned` is valid because values of this type have "identity". Interned::new_unchecked(self.dropless.alloc(data)) } fn alloc_import(&'ra self, import: ImportData<'ra>) -> Import<'ra> { + // SAFETY: `Interned` is valid because values of this type have "identity". Interned::new_unchecked(self.imports.alloc(import)) } fn alloc_name_resolution(&'ra self, orig_ident_span: Span) -> NameResolutionRef<'ra> { + // SAFETY: `Interned` is valid because values of this type have "identity". Interned::new_unchecked( self.name_resolutions.alloc(CmRefCell::new(NameResolution::new(orig_ident_span))), )