src/librustc_middle/ty/list.rs

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