compiler/rustc_middle/src/ty/list.rs

   1 use crate::arena::Arena;
   2
   3 use rustc_serialize::{Encodable, Encoder};
   4
   5 use std::alloc::Layout;
   6 use std::cmp::Ordering;
   7 use std::fmt;
   8 use std::hash::{Hash, Hasher};
   9 use std::iter;
  10 use std::mem;
  11 use std::ops::Deref;
  12 use std::ptr;
  13 use std::slice;
  14
  15 extern "C" {
  16     /// A dummy type used to force `List` to be unsized while not requiring references to it be wide
  17     /// pointers.
  18     type OpaqueListContents;
  19 }
  20
  21 /// A wrapper for slices with the additional invariant
  22 /// that the slice is interned and no other slice with
  23 /// the same contents can exist in the same context.
  24 /// This means we can use pointer for both
  25 /// equality comparisons and hashing.
  26 ///
  27 /// Unlike slices, the types contained in `List` are expected to be `Copy`
  28 /// and iterating over a `List` returns `T` instead of a reference.
  29 ///
  30 /// Note: `Slice` was already taken by the `Ty`.
  31 #[repr(C)]
  32 pub struct List<T> {
  33     len: usize,
  34     data: [T; 0],
  35     opaque: OpaqueListContents,
  36 }
  37
  38 unsafe impl<'a, T: 'a> rustc_data_structures::tagged_ptr::Pointer for &'a List<T> {
  39     const BITS: usize = std::mem::align_of::<usize>().trailing_zeros() as usize;
  40     fn into_usize(self) -> usize {
  41         self as *const List<T> as usize
  42     }
  43     unsafe fn from_usize(ptr: usize) -> Self {
  44         &*(ptr as *const List<T>)
  45     }
  46     unsafe fn with_ref<R, F: FnOnce(&Self) -> R>(ptr: usize, f: F) -> R {
  47         // Self: Copy so this is fine
  48         let ptr = Self::from_usize(ptr);
  49         f(&ptr)
  50     }
  51 }
  52
  53 unsafe impl<T: Sync> Sync for List<T> {}
  54
  55 impl<T: Copy> List<T> {
  56     #[inline]
  57     pub(super) fn from_arena<'tcx>(arena: &'tcx Arena<'tcx>, slice: &[T]) -> &'tcx List<T> {
  58         assert!(!mem::needs_drop::<T>());
  59         assert!(mem::size_of::<T>() != 0);
  60         assert!(!slice.is_empty());
  61
  62         let (layout, _offset) =
  63             Layout::new::<usize>().extend(Layout::for_value::<[T]>(slice)).unwrap();
  64         let mem = arena.dropless.alloc_raw(layout);
  65         unsafe {
  66             let result = &mut *(mem as *mut List<T>);
  67             // Write the length
  68             result.len = slice.len();
  69
  70             // Write the elements
  71             let arena_slice = slice::from_raw_parts_mut(result.data.as_mut_ptr(), result.len);
  72             arena_slice.copy_from_slice(slice);
  73
  74             result
  75         }
  76     }
  77
  78     // If this method didn't exist, we would use `slice.iter` due to
  79     // deref coercion.
  80     //
  81     // This would be weird, as `self.into_iter` iterates over `T` directly.
  82     #[inline(always)]
  83     pub fn iter(&self) -> <&'_ List<T> as IntoIterator>::IntoIter {
  84         self.into_iter()
  85     }
  86 }
  87
  88 impl<T: fmt::Debug> fmt::Debug for List<T> {
  89     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  90         (**self).fmt(f)
  91     }
  92 }
  93
  94 impl<S: Encoder, T: Encodable<S>> Encodable<S> for List<T> {
  95     #[inline]
  96     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
  97         (**self).encode(s)
  98     }
  99 }
 100
 101 impl<S: Encoder, T: Encodable<S>> Encodable<S> for &List<T> {
 102     #[inline]
 103     fn encode(&self, s: &mut S) -> Result<(), S::Error> {
 104         (**self).encode(s)
 105     }
 106 }
 107
 108 impl<T> Ord for List<T>
 109 where
 110     T: Ord,
 111 {
 112     fn cmp(&self, other: &List<T>) -> Ordering {
 113         if self == other { Ordering::Equal } else { <[T] as Ord>::cmp(&**self, &**other) }
 114     }
 115 }
 116
 117 impl<T> PartialOrd for List<T>
 118 where
 119     T: PartialOrd,
 120 {
 121     fn partial_cmp(&self, other: &List<T>) -> Option<Ordering> {
 122         if self == other {
 123             Some(Ordering::Equal)
 124         } else {
 125             <[T] as PartialOrd>::partial_cmp(&**self, &**other)
 126         }
 127     }
 128 }
 129
 130 impl<T: PartialEq> PartialEq for List<T> {
 131     #[inline]
 132     fn eq(&self, other: &List<T>) -> bool {
 133         ptr::eq(self, other)
 134     }
 135 }
 136 impl<T: Eq> Eq for List<T> {}
 137
 138 impl<T> Hash for List<T> {
 139     #[inline]
 140     fn hash<H: Hasher>(&self, s: &mut H) {
 141         (self as *const List<T>).hash(s)
 142     }
 143 }
 144
 145 impl<T> Deref for List<T> {
 146     type Target = [T];
 147     #[inline(always)]
 148     fn deref(&self) -> &[T] {
 149         self.as_ref()
 150     }
 151 }
 152
 153 impl<T> AsRef<[T]> for List<T> {
 154     #[inline(always)]
 155     fn as_ref(&self) -> &[T] {
 156         unsafe { slice::from_raw_parts(self.data.as_ptr(), self.len) }
 157     }
 158 }
 159
 160 impl<'a, T: Copy> IntoIterator for &'a List<T> {
 161     type Item = T;
 162     type IntoIter = iter::Copied<<&'a [T] as IntoIterator>::IntoIter>;
 163     #[inline(always)]
 164     fn into_iter(self) -> Self::IntoIter {
 165         self[..].iter().copied()
 166     }
 167 }
 168
 169 impl<T> List<T> {
 170     #[inline(always)]
 171     pub fn empty<'a>() -> &'a List<T> {
 172         #[repr(align(64), C)]
 173         struct EmptySlice([u8; 64]);
 174         static EMPTY_SLICE: EmptySlice = EmptySlice([0; 64]);
 175         assert!(mem::align_of::<T>() <= 64);
 176         unsafe { &*(&EMPTY_SLICE as *const _ as *const List<T>) }
 177     }
 178 }