| use crate::arena::Arena; |
| use rustc_data_structures::aligned::{align_of, Aligned}; |
| use rustc_serialize::{Encodable, Encoder}; |
| use rustc_type_ir::{InferCtxtLike, OptWithInfcx}; |
| use std::alloc::Layout; |
| use std::cmp::Ordering; |
| use std::fmt; |
| use std::hash::{Hash, Hasher}; |
| use std::iter; |
| use std::mem; |
| use std::ops::Deref; |
| use std::ptr; |
| use std::slice; |
| |
| /// `List<T>` is a bit like `&[T]`, but with some critical differences. |
| /// - IMPORTANT: Every `List<T>` is *required* to have unique contents. The |
| /// type's correctness relies on this, *but it does not enforce it*. |
| /// Therefore, any code that creates a `List<T>` must ensure uniqueness |
| /// itself. In practice this is achieved by interning. |
| /// - The length is stored within the `List<T>`, so `&List<Ty>` is a thin |
| /// pointer. |
| /// - Because of this, you cannot get a `List<T>` that is a sub-list of another |
| /// `List<T>`. You can get a sub-slice `&[T]`, however. |
| /// - `List<T>` can be used with `CopyTaggedPtr`, which is useful within |
| /// structs whose size must be minimized. |
| /// - Because of the uniqueness assumption, we can use the address of a |
| /// `List<T>` for faster equality comparisons and hashing. |
| /// - `T` must be `Copy`. This lets `List<T>` be stored in a dropless arena and |
| /// iterators return a `T` rather than a `&T`. |
| /// - `T` must not be zero-sized. |
| #[repr(C)] |
| pub struct List<T> { |
| len: usize, |
| |
| /// Although this claims to be a zero-length array, in practice `len` |
| /// elements are actually present. |
| data: [T; 0], |
| |
| opaque: OpaqueListContents, |
| } |
| |
| extern "C" { |
| /// A dummy type used to force `List` to be unsized while not requiring |
| /// references to it be wide pointers. |
| type OpaqueListContents; |
| } |
| |
| impl<T> List<T> { |
| /// Returns a reference to the (unique, static) empty list. |
| #[inline(always)] |
| pub fn empty<'a>() -> &'a List<T> { |
| #[repr(align(64))] |
| struct MaxAlign; |
| |
| assert!(mem::align_of::<T>() <= mem::align_of::<MaxAlign>()); |
| |
| #[repr(C)] |
| struct InOrder<T, U>(T, U); |
| |
| // The empty slice is static and contains a single `0` usize (for the |
| // length) that is 64-byte aligned, thus featuring the necessary |
| // trailing padding for elements with up to 64-byte alignment. |
| static EMPTY_SLICE: InOrder<usize, MaxAlign> = InOrder(0, MaxAlign); |
| unsafe { &*(&EMPTY_SLICE as *const _ as *const List<T>) } |
| } |
| |
| pub fn len(&self) -> usize { |
| self.len |
| } |
| |
| pub fn as_slice(&self) -> &[T] { |
| self |
| } |
| } |
| |
| impl<T: Copy> List<T> { |
| /// Allocates a list from `arena` and copies the contents of `slice` into it. |
| /// |
| /// WARNING: the contents *must be unique*, such that no list with these |
| /// contents has been previously created. If not, operations such as `eq` |
| /// and `hash` might give incorrect results. |
| /// |
| /// Panics if `T` is `Drop`, or `T` is zero-sized, or the slice is empty |
| /// (because the empty list exists statically, and is available via |
| /// `empty()`). |
| #[inline] |
| pub(super) 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.is_empty()); |
| |
| let (layout, _offset) = |
| Layout::new::<usize>().extend(Layout::for_value::<[T]>(slice)).unwrap(); |
| let mem = arena.dropless.alloc_raw(layout) as *mut List<T>; |
| unsafe { |
| // Write the length |
| ptr::addr_of_mut!((*mem).len).write(slice.len()); |
| |
| // Write the elements |
| ptr::addr_of_mut!((*mem).data) |
| .cast::<T>() |
| .copy_from_nonoverlapping(slice.as_ptr(), slice.len()); |
| |
| &*mem |
| } |
| } |
| |
| // If this method didn't exist, we would use `slice.iter` due to |
| // deref coercion. |
| // |
| // This would be weird, as `self.into_iter` iterates over `T` directly. |
| #[inline(always)] |
| pub fn iter(&self) -> <&'_ List<T> as IntoIterator>::IntoIter { |
| self.into_iter() |
| } |
| } |
| |
| impl<T: fmt::Debug> fmt::Debug for List<T> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| (**self).fmt(f) |
| } |
| } |
| impl<'tcx, T: super::DebugWithInfcx<TyCtxt<'tcx>>> super::DebugWithInfcx<TyCtxt<'tcx>> for List<T> { |
| fn fmt<InfCtx: InferCtxtLike<TyCtxt<'tcx>>>( |
| this: OptWithInfcx<'_, TyCtxt<'tcx>, InfCtx, &Self>, |
| f: &mut core::fmt::Formatter<'_>, |
| ) -> core::fmt::Result { |
| fmt::Debug::fmt(&this.map(|this| this.as_slice()), f) |
| } |
| } |
| |
| impl<S: Encoder, T: Encodable<S>> Encodable<S> for List<T> { |
| #[inline] |
| fn encode(&self, s: &mut S) { |
| (**self).encode(s); |
| } |
| } |
| |
| impl<T: PartialEq> PartialEq for List<T> { |
| #[inline] |
| fn eq(&self, other: &List<T>) -> bool { |
| // Pointer equality implies list equality (due to the unique contents |
| // assumption). |
| ptr::eq(self, other) |
| } |
| } |
| |
| impl<T: Eq> Eq for List<T> {} |
| |
| impl<T> Ord for List<T> |
| where |
| T: Ord, |
| { |
| fn cmp(&self, other: &List<T>) -> Ordering { |
| // Pointer equality implies list equality (due to the unique contents |
| // assumption), but the contents must be compared otherwise. |
| if self == other { Ordering::Equal } else { <[T] as Ord>::cmp(&**self, &**other) } |
| } |
| } |
| |
| impl<T> PartialOrd for List<T> |
| where |
| T: PartialOrd, |
| { |
| fn partial_cmp(&self, other: &List<T>) -> Option<Ordering> { |
| // Pointer equality implies list equality (due to the unique contents |
| // assumption), but the contents must be compared otherwise. |
| if self == other { |
| Some(Ordering::Equal) |
| } else { |
| <[T] as PartialOrd>::partial_cmp(&**self, &**other) |
| } |
| } |
| } |
| |
| impl<T> Hash for List<T> { |
| #[inline] |
| fn hash<H: Hasher>(&self, s: &mut H) { |
| // Pointer hashing is sufficient (due to the unique contents |
| // assumption). |
| (self as *const List<T>).hash(s) |
| } |
| } |
| |
| impl<T> Deref for List<T> { |
| type Target = [T]; |
| #[inline(always)] |
| fn deref(&self) -> &[T] { |
| self.as_ref() |
| } |
| } |
| |
| impl<T> AsRef<[T]> for List<T> { |
| #[inline(always)] |
| fn as_ref(&self) -> &[T] { |
| unsafe { slice::from_raw_parts(self.data.as_ptr(), self.len) } |
| } |
| } |
| |
| impl<'a, T: Copy> IntoIterator for &'a List<T> { |
| type Item = T; |
| type IntoIter = iter::Copied<<&'a [T] as IntoIterator>::IntoIter>; |
| #[inline(always)] |
| fn into_iter(self) -> Self::IntoIter { |
| self[..].iter().copied() |
| } |
| } |
| |
| unsafe impl<T: Sync> Sync for List<T> {} |
| |
| // We need this since `List` uses extern type `OpaqueListContents`. |
| #[cfg(parallel_compiler)] |
| use rustc_data_structures::sync::DynSync; |
| |
| use super::TyCtxt; |
| #[cfg(parallel_compiler)] |
| unsafe impl<T: DynSync> DynSync for List<T> {} |
| |
| // Safety: |
| // Layouts of `Equivalent<T>` and `List<T>` are the same, modulo opaque tail, |
| // thus aligns of `Equivalent<T>` and `List<T>` must be the same. |
| unsafe impl<T> Aligned for List<T> { |
| const ALIGN: ptr::Alignment = { |
| #[repr(C)] |
| struct Equivalent<T> { |
| _len: usize, |
| _data: [T; 0], |
| } |
| |
| align_of::<Equivalent<T>>() |
| }; |
| } |