1use std::cell::UnsafeCell;
2use std::cmp::Ordering;
3use std::iter::FromIterator;
4use std::ops::Index;
5
6use stable_deref_trait::StableDeref;
7
8/// Append-only version of `std::vec::Vec` where
9/// insertion does not require mutable access
10pub struct FrozenVec<T> {
11 vec: UnsafeCell<Vec<T>>,
12 // XXXManishearth do we need a reentrancy guard here as well?
13 // StableDeref may not guarantee that there are no side effects
14}
15
16// safety: UnsafeCell implies !Sync
17
18impl<T> FrozenVec<T> {
19 /// Constructs a new, empty vector.
20 pub fn new() -> Self {
21 Self {
22 vec: UnsafeCell::new(Default::default()),
23 }
24 }
25}
26
27impl<T> FrozenVec<T> {
28 // these should never return &T
29 // these should never delete any entries
30
31 /// Appends an element to the back of the vector.
32 pub fn push(&self, val: T) {
33 unsafe {
34 let vec: *mut Vec = self.vec.get();
35 (*vec).push(val)
36 }
37 }
38}
39
40impl<T: StableDeref> FrozenVec<T> {
41 /// Push, immediately getting a reference to the element
42 pub fn push_get(&self, val: T) -> &T::Target {
43 unsafe {
44 let vec = self.vec.get();
45 (*vec).push(val);
46 &*(&**(*vec).get_unchecked((*vec).len() - 1) as *const T::Target)
47 }
48 }
49
50 /// Returns a reference to an element.
51 pub fn get(&self, index: usize) -> Option<&T::Target> {
52 unsafe {
53 let vec = self.vec.get();
54 (*vec).get(index).map(|x| &**x)
55 }
56 }
57
58 /// Returns a reference to an element, without doing bounds checking.
59 ///
60 /// ## Safety
61 ///
62 /// `index` must be in bounds, i.e. it must be less than `self.len()`
63 pub unsafe fn get_unchecked(&self, index: usize) -> &T::Target {
64 let vec = self.vec.get();
65 &**(*vec).get_unchecked(index)
66 }
67}
68
69impl<T: Copy> FrozenVec<T> {
70 /// Returns a copy of an element.
71 pub fn get_copy(&self, index: usize) -> Option<T> {
72 unsafe {
73 let vec: *mut Vec = self.vec.get();
74 (*vec).get(index).copied()
75 }
76 }
77}
78
79impl<T> FrozenVec<T> {
80 /// Returns the number of elements in the vector.
81 pub fn len(&self) -> usize {
82 unsafe {
83 let vec: *mut Vec = self.vec.get();
84 (*vec).len()
85 }
86 }
87
88 /// Returns `true` if the vector contains no elements.
89 pub fn is_empty(&self) -> bool {
90 self.len() == 0
91 }
92}
93
94impl<T: StableDeref> FrozenVec<T> {
95 /// Returns the first element of the vector, or `None` if empty.
96 pub fn first(&self) -> Option<&T::Target> {
97 unsafe {
98 let vec: *mut Vec = self.vec.get();
99 (*vec).first().map(|x: &T| &**x)
100 }
101 }
102
103 /// Returns the last element of the vector, or `None` if empty.
104 pub fn last(&self) -> Option<&T::Target> {
105 unsafe {
106 let vec: *mut Vec = self.vec.get();
107 (*vec).last().map(|x: &T| &**x)
108 }
109 }
110 /// Returns an iterator over the vector.
111 pub fn iter(&self) -> Iter<T> {
112 self.into_iter()
113 }
114}
115
116impl<T: StableDeref> FrozenVec<T> {
117 /// Converts the frozen vector into a plain vector.
118 pub fn into_vec(self) -> Vec<T> {
119 self.vec.into_inner()
120 }
121}
122
123impl<T: StableDeref> FrozenVec<T> {
124 // binary search functions: they need to be reimplemented here to be safe (instead of calling
125 // their equivalents directly on the underlying Vec), as they run user callbacks that could
126 // reentrantly call other functions on this vector
127
128 /// Binary searches this sorted vector for a given element, analogous to [slice::binary_search].
129 pub fn binary_search(&self, x: &T::Target) -> Result<usize, usize>
130 where
131 T::Target: Ord,
132 {
133 self.binary_search_by(|p| p.cmp(x))
134 }
135
136 /// Binary searches this sorted vector with a comparator function, analogous to
137 /// [slice::binary_search_by].
138 pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
139 where
140 F: FnMut(&'a T::Target) -> Ordering,
141 {
142 let mut size = self.len();
143 let mut left = 0;
144 let mut right = size;
145 while left < right {
146 let mid = left + size / 2;
147
148 // safety: like the core algorithm, mid is always within original vector len; in
149 // pathlogical cases, user could push to the vector in the meantime, but this can only
150 // increase the length, keeping this safe
151 let cmp = f(unsafe { self.get_unchecked(mid) });
152
153 if cmp == Ordering::Less {
154 left = mid + 1;
155 } else if cmp == Ordering::Greater {
156 right = mid;
157 } else {
158 return Ok(mid);
159 }
160
161 size = right - left;
162 }
163 Err(left)
164 }
165
166 /// Binary searches this sorted vector with a key extraction function, analogous to
167 /// [slice::binary_search_by_key].
168 pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
169 where
170 F: FnMut(&'a T::Target) -> B,
171 B: Ord,
172 {
173 self.binary_search_by(|k| f(k).cmp(b))
174 }
175
176 /// Returns the index of the partition point according to the given predicate
177 /// (the index of the first element of the second partition), analogous to
178 /// [slice::partition_point].
179 pub fn partition_point<P>(&self, mut pred: P) -> usize
180 where
181 P: FnMut(&T::Target) -> bool,
182 {
183 let mut left = 0;
184 let mut right = self.len();
185
186 while left != right {
187 let mid = left + (right - left) / 2;
188 // safety: like in binary_search_by
189 let value = unsafe { self.get_unchecked(mid) };
190 if pred(value) {
191 left = mid + 1;
192 } else {
193 right = mid;
194 }
195 }
196
197 left
198 }
199
200 // TODO add more
201}
202
203impl<T> std::convert::AsMut<Vec<T>> for FrozenVec<T> {
204 /// Get mutable access to the underlying vector.
205 ///
206 /// This is safe, as it requires a `&mut self`, ensuring nothing is using
207 /// the 'frozen' contents.
208 fn as_mut(&mut self) -> &mut Vec<T> {
209 unsafe { &mut *self.vec.get() }
210 }
211}
212
213impl<T> Default for FrozenVec<T> {
214 fn default() -> Self {
215 FrozenVec::new()
216 }
217}
218
219impl<T> From<Vec<T>> for FrozenVec<T> {
220 fn from(vec: Vec<T>) -> Self {
221 Self {
222 vec: UnsafeCell::new(vec),
223 }
224 }
225}
226
227impl<T: StableDeref> Index<usize> for FrozenVec<T> {
228 type Output = T::Target;
229 fn index(&self, idx: usize) -> &T::Target {
230 self.get(index:idx).unwrap_or_else(|| {
231 panic!(
232 "index out of bounds: the len is {} but the index is {}",
233 self.len(),
234 idx
235 )
236 })
237 }
238}
239
240impl<A> FromIterator<A> for FrozenVec<A> {
241 fn from_iter<T>(iter: T) -> Self
242 where
243 T: IntoIterator<Item = A>,
244 {
245 let vec: Vec<_> = iter.into_iter().collect();
246 vec.into()
247 }
248}
249
250/// Iterator over FrozenVec, obtained via `.iter()`
251///
252/// It is safe to push to the vector during iteration
253pub struct Iter<'a, T> {
254 vec: &'a FrozenVec<T>,
255 idx: usize,
256}
257
258impl<'a, T: StableDeref> Iterator for Iter<'a, T> {
259 type Item = &'a T::Target;
260 fn next(&mut self) -> Option<&'a T::Target> {
261 if let Some(ret: &::Target) = self.vec.get(self.idx) {
262 self.idx += 1;
263 Some(ret)
264 } else {
265 None
266 }
267 }
268}
269
270impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> {
271 type Item = &'a T::Target;
272 type IntoIter = Iter<'a, T>;
273 fn into_iter(self) -> Iter<'a, T> {
274 Iter { vec: self, idx: 0 }
275 }
276}
277
278#[test]
279fn test_iteration() {
280 let vec: Vec<&str> = vec!["a", "b", "c", "d"];
281 let frozen: FrozenVec<_> = vec.clone().into();
282
283 assert_eq!(vec, frozen.iter().collect::<Vec<_>>());
284 for (e1: &&str, e2: &str) in vec.iter().zip(frozen.iter()) {
285 assert_eq!(*e1, e2);
286 }
287
288 assert_eq!(vec.len(), frozen.iter().count())
289}
290
291#[test]
292fn test_accessors() {
293 let vec: FrozenVec<String> = FrozenVec::new();
294
295 assert_eq!(vec.is_empty(), true);
296 assert_eq!(vec.len(), 0);
297 assert_eq!(vec.first(), None);
298 assert_eq!(vec.last(), None);
299 assert_eq!(vec.get(1), None);
300
301 vec.push(val:"a".to_string());
302 vec.push(val:"b".to_string());
303 vec.push(val:"c".to_string());
304
305 assert_eq!(vec.is_empty(), false);
306 assert_eq!(vec.len(), 3);
307 assert_eq!(vec.first(), Some("a"));
308 assert_eq!(vec.last(), Some("c"));
309 assert_eq!(vec.get(1), Some("b"));
310}
311
312#[test]
313fn test_non_stable_deref() {
314 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
315 struct Moo(i32);
316 let vec: FrozenVec<Moo> = FrozenVec::new();
317
318 assert_eq!(vec.is_empty(), true);
319 assert_eq!(vec.len(), 0);
320 assert_eq!(vec.get_copy(1), None);
321
322 vec.push(val:Moo(1));
323 vec.push(val:Moo(2));
324 vec.push(val:Moo(3));
325
326 assert_eq!(vec.is_empty(), false);
327 assert_eq!(vec.len(), 3);
328 assert_eq!(vec.get_copy(1), Some(Moo(2)));
329}
330
331#[test]
332fn test_binary_search() {
333 let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into();
334
335 assert_eq!(vec.binary_search("cde"), Ok(1));
336 assert_eq!(vec.binary_search("cdf"), Err(2));
337 assert_eq!(vec.binary_search("a"), Err(0));
338 assert_eq!(vec.binary_search("g"), Err(3));
339
340 assert_eq!(vec.binary_search_by_key(&1, |x| x.len()), Err(0));
341 assert_eq!(vec.binary_search_by_key(&3, |x| x.len()), Ok(1));
342 assert_eq!(vec.binary_search_by_key(&4, |x| x.len()), Err(2));
343
344 assert_eq!(vec.partition_point(|x| x.len() < 4), 2);
345 assert_eq!(vec.partition_point(|_| false), 0);
346 assert_eq!(vec.partition_point(|_| true), 3);
347}
348