]>
Commit | Line | Data |
---|---|---|
f9f354fc XL |
1 | use crate::arena::Arena; |
2 | ||
3 | use rustc_serialize::{Encodable, Encoder}; | |
4 | ||
f035d41b XL |
5 | use std::alloc::Layout; |
6 | use std::cmp::Ordering; | |
f9f354fc XL |
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 | /// | |
fc512014 | 27 | /// Unlike slices, the types contained in `List` are expected to be `Copy` |
f9f354fc XL |
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 | ||
3dfed10e XL |
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; | |
17df50a5 | 40 | #[inline] |
3dfed10e XL |
41 | fn into_usize(self) -> usize { |
42 | self as *const List<T> as usize | |
43 | } | |
17df50a5 | 44 | #[inline] |
3dfed10e XL |
45 | unsafe fn from_usize(ptr: usize) -> Self { |
46 | &*(ptr as *const List<T>) | |
47 | } | |
48 | unsafe fn with_ref<R, F: FnOnce(&Self) -> R>(ptr: usize, f: F) -> R { | |
49 | // Self: Copy so this is fine | |
50 | let ptr = Self::from_usize(ptr); | |
51 | f(&ptr) | |
52 | } | |
53 | } | |
54 | ||
f9f354fc XL |
55 | unsafe impl<T: Sync> Sync for List<T> {} |
56 | ||
57 | impl<T: Copy> List<T> { | |
58 | #[inline] | |
59 | pub(super) fn from_arena<'tcx>(arena: &'tcx Arena<'tcx>, slice: &[T]) -> &'tcx List<T> { | |
60 | assert!(!mem::needs_drop::<T>()); | |
61 | assert!(mem::size_of::<T>() != 0); | |
62 | assert!(!slice.is_empty()); | |
63 | ||
f035d41b XL |
64 | let (layout, _offset) = |
65 | Layout::new::<usize>().extend(Layout::for_value::<[T]>(slice)).unwrap(); | |
136023e0 | 66 | let mem = arena.dropless.alloc_raw(layout) as *mut List<T>; |
f9f354fc | 67 | unsafe { |
f9f354fc | 68 | // Write the length |
136023e0 | 69 | ptr::addr_of_mut!((*mem).len).write(slice.len()); |
f9f354fc XL |
70 | |
71 | // Write the elements | |
136023e0 XL |
72 | ptr::addr_of_mut!((*mem).data) |
73 | .cast::<T>() | |
74 | .copy_from_nonoverlapping(slice.as_ptr(), slice.len()); | |
f9f354fc | 75 | |
136023e0 | 76 | &mut *mem |
f9f354fc XL |
77 | } |
78 | } | |
79 | ||
80 | // If this method didn't exist, we would use `slice.iter` due to | |
81 | // deref coercion. | |
82 | // | |
83 | // This would be weird, as `self.into_iter` iterates over `T` directly. | |
84 | #[inline(always)] | |
85 | pub fn iter(&self) -> <&'_ List<T> as IntoIterator>::IntoIter { | |
86 | self.into_iter() | |
87 | } | |
88 | } | |
89 | ||
90 | impl<T: fmt::Debug> fmt::Debug for List<T> { | |
91 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
92 | (**self).fmt(f) | |
93 | } | |
94 | } | |
95 | ||
3dfed10e XL |
96 | impl<S: Encoder, T: Encodable<S>> Encodable<S> for List<T> { |
97 | #[inline] | |
98 | fn encode(&self, s: &mut S) -> Result<(), S::Error> { | |
99 | (**self).encode(s) | |
100 | } | |
101 | } | |
102 | ||
103 | impl<S: Encoder, T: Encodable<S>> Encodable<S> for &List<T> { | |
f9f354fc | 104 | #[inline] |
3dfed10e | 105 | fn encode(&self, s: &mut S) -> Result<(), S::Error> { |
f9f354fc XL |
106 | (**self).encode(s) |
107 | } | |
108 | } | |
109 | ||
110 | impl<T> Ord for List<T> | |
111 | where | |
112 | T: Ord, | |
113 | { | |
114 | fn cmp(&self, other: &List<T>) -> Ordering { | |
115 | if self == other { Ordering::Equal } else { <[T] as Ord>::cmp(&**self, &**other) } | |
116 | } | |
117 | } | |
118 | ||
119 | impl<T> PartialOrd for List<T> | |
120 | where | |
121 | T: PartialOrd, | |
122 | { | |
123 | fn partial_cmp(&self, other: &List<T>) -> Option<Ordering> { | |
124 | if self == other { | |
125 | Some(Ordering::Equal) | |
126 | } else { | |
127 | <[T] as PartialOrd>::partial_cmp(&**self, &**other) | |
128 | } | |
129 | } | |
130 | } | |
131 | ||
132 | impl<T: PartialEq> PartialEq for List<T> { | |
133 | #[inline] | |
134 | fn eq(&self, other: &List<T>) -> bool { | |
135 | ptr::eq(self, other) | |
136 | } | |
137 | } | |
138 | impl<T: Eq> Eq for List<T> {} | |
139 | ||
140 | impl<T> Hash for List<T> { | |
141 | #[inline] | |
142 | fn hash<H: Hasher>(&self, s: &mut H) { | |
143 | (self as *const List<T>).hash(s) | |
144 | } | |
145 | } | |
146 | ||
147 | impl<T> Deref for List<T> { | |
148 | type Target = [T]; | |
149 | #[inline(always)] | |
150 | fn deref(&self) -> &[T] { | |
151 | self.as_ref() | |
152 | } | |
153 | } | |
154 | ||
155 | impl<T> AsRef<[T]> for List<T> { | |
156 | #[inline(always)] | |
157 | fn as_ref(&self) -> &[T] { | |
158 | unsafe { slice::from_raw_parts(self.data.as_ptr(), self.len) } | |
159 | } | |
160 | } | |
161 | ||
162 | impl<'a, T: Copy> IntoIterator for &'a List<T> { | |
163 | type Item = T; | |
164 | type IntoIter = iter::Copied<<&'a [T] as IntoIterator>::IntoIter>; | |
165 | #[inline(always)] | |
166 | fn into_iter(self) -> Self::IntoIter { | |
167 | self[..].iter().copied() | |
168 | } | |
169 | } | |
170 | ||
171 | impl<T> List<T> { | |
172 | #[inline(always)] | |
173 | pub fn empty<'a>() -> &'a List<T> { | |
174 | #[repr(align(64), C)] | |
175 | struct EmptySlice([u8; 64]); | |
176 | static EMPTY_SLICE: EmptySlice = EmptySlice([0; 64]); | |
177 | assert!(mem::align_of::<T>() <= 64); | |
178 | unsafe { &*(&EMPTY_SLICE as *const _ as *const List<T>) } | |
179 | } | |
180 | } |