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 const fn new() -> Self {
21 Self {
22 vec: UnsafeCell::new(Vec::new()),
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: Clone> Clone for FrozenVec<T> {
220 fn clone(&self) -> Self {
221 Self {
222 vec: unsafe { self.vec.get().as_ref().unwrap() }.clone().into(),
223 }
224 }
225}
226
227impl<T> From<Vec<T>> for FrozenVec<T> {
228 fn from(vec: Vec<T>) -> Self {
229 Self {
230 vec: UnsafeCell::new(vec),
231 }
232 }
233}
234
235impl<T: StableDeref> Index<usize> for FrozenVec<T> {
236 type Output = T::Target;
237 fn index(&self, idx: usize) -> &T::Target {
238 self.get(index:idx).unwrap_or_else(|| {
239 panic!(
240 "index out of bounds: the len is {} but the index is {}",
241 self.len(),
242 idx
243 )
244 })
245 }
246}
247
248impl<A> FromIterator<A> for FrozenVec<A> {
249 fn from_iter<T>(iter: T) -> Self
250 where
251 T: IntoIterator<Item = A>,
252 {
253 let vec: Vec<_> = iter.into_iter().collect();
254 vec.into()
255 }
256}
257
258/// Iterator over FrozenVec, obtained via `.iter()`
259///
260/// It is safe to push to the vector during iteration
261pub struct Iter<'a, T> {
262 vec: &'a FrozenVec<T>,
263 idx: usize,
264}
265
266impl<'a, T: StableDeref> Iterator for Iter<'a, T> {
267 type Item = &'a T::Target;
268 fn next(&mut self) -> Option<&'a T::Target> {
269 if let Some(ret: &::Target) = self.vec.get(self.idx) {
270 self.idx += 1;
271 Some(ret)
272 } else {
273 None
274 }
275 }
276}
277
278impl<'a, T: StableDeref> IntoIterator for &'a FrozenVec<T> {
279 type Item = &'a T::Target;
280 type IntoIter = Iter<'a, T>;
281 fn into_iter(self) -> Iter<'a, T> {
282 Iter { vec: self, idx: 0 }
283 }
284}
285
286impl<T: StableDeref + PartialEq> PartialEq for FrozenVec<T>
287where
288 T::Target: PartialEq,
289{
290 fn eq(&self, other: &Self) -> bool {
291 unsafe { self.vec.get().as_ref() == other.vec.get().as_ref() }
292 }
293}
294
295#[test]
296fn test_iteration() {
297 let vec = vec!["a", "b", "c", "d"];
298 let frozen: FrozenVec<_> = vec.clone().into();
299
300 assert_eq!(vec, frozen.iter().collect::<Vec<_>>());
301 for (e1, e2) in vec.iter().zip(frozen.iter()) {
302 assert_eq!(*e1, e2);
303 }
304
305 assert_eq!(vec.len(), frozen.iter().count())
306}
307
308#[test]
309fn test_accessors() {
310 let vec: FrozenVec<String> = FrozenVec::new();
311
312 assert!(vec.is_empty());
313 assert_eq!(vec.len(), 0);
314 assert_eq!(vec.first(), None);
315 assert_eq!(vec.last(), None);
316 assert_eq!(vec.get(1), None);
317
318 vec.push("a".to_string());
319 vec.push("b".to_string());
320 vec.push("c".to_string());
321
322 assert!(!vec.is_empty());
323 assert_eq!(vec.len(), 3);
324 assert_eq!(vec.first(), Some("a"));
325 assert_eq!(vec.last(), Some("c"));
326 assert_eq!(vec.get(1), Some("b"));
327}
328
329#[test]
330fn test_non_stable_deref() {
331 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
332 struct Moo(i32);
333 let vec: FrozenVec<Moo> = FrozenVec::new();
334
335 assert!(vec.is_empty());
336 assert_eq!(vec.len(), 0);
337 assert_eq!(vec.get_copy(1), None);
338
339 vec.push(Moo(1));
340 vec.push(Moo(2));
341 vec.push(Moo(3));
342
343 assert!(!vec.is_empty());
344 assert_eq!(vec.len(), 3);
345 assert_eq!(vec.get_copy(1), Some(Moo(2)));
346}
347
348#[test]
349fn test_binary_search() {
350 let vec: FrozenVec<_> = vec!["ab", "cde", "fghij"].into();
351
352 assert_eq!(vec.binary_search("cde"), Ok(1));
353 assert_eq!(vec.binary_search("cdf"), Err(2));
354 assert_eq!(vec.binary_search("a"), Err(0));
355 assert_eq!(vec.binary_search("g"), Err(3));
356
357 assert_eq!(vec.binary_search_by_key(&1, |x| x.len()), Err(0));
358 assert_eq!(vec.binary_search_by_key(&3, |x| x.len()), Ok(1));
359 assert_eq!(vec.binary_search_by_key(&4, |x| x.len()), Err(2));
360
361 assert_eq!(vec.partition_point(|x| x.len() < 4), 2);
362 assert_eq!(vec.partition_point(|_| false), 0);
363 assert_eq!(vec.partition_point(|_| true), 3);
364}
365