]>
Commit | Line | Data |
---|---|---|
e1599b0c | 1 | use std::collections::TryReserveError::*; |
60c5eb7d XL |
2 | use std::collections::{vec_deque::Drain, VecDeque}; |
3 | use std::fmt::Debug; | |
0531ce1d | 4 | use std::mem::size_of; |
74b04a01 | 5 | use std::panic::{catch_unwind, AssertUnwindSafe}; |
c34b1796 | 6 | |
9fa01778 XL |
7 | use crate::hash; |
8 | ||
9 | use Taggy::*; | |
10 | use Taggypar::*; | |
c34b1796 AL |
11 | |
12 | #[test] | |
13 | fn test_simple() { | |
14 | let mut d = VecDeque::new(); | |
15 | assert_eq!(d.len(), 0); | |
16 | d.push_front(17); | |
17 | d.push_front(42); | |
18 | d.push_back(137); | |
19 | assert_eq!(d.len(), 3); | |
20 | d.push_back(137); | |
21 | assert_eq!(d.len(), 4); | |
22 | assert_eq!(*d.front().unwrap(), 42); | |
23 | assert_eq!(*d.back().unwrap(), 137); | |
24 | let mut i = d.pop_front(); | |
25 | assert_eq!(i, Some(42)); | |
26 | i = d.pop_back(); | |
27 | assert_eq!(i, Some(137)); | |
28 | i = d.pop_back(); | |
29 | assert_eq!(i, Some(137)); | |
30 | i = d.pop_back(); | |
31 | assert_eq!(i, Some(17)); | |
32 | assert_eq!(d.len(), 0); | |
33 | d.push_back(3); | |
34 | assert_eq!(d.len(), 1); | |
35 | d.push_front(2); | |
36 | assert_eq!(d.len(), 2); | |
37 | d.push_back(4); | |
38 | assert_eq!(d.len(), 3); | |
39 | d.push_front(1); | |
40 | assert_eq!(d.len(), 4); | |
c34b1796 AL |
41 | assert_eq!(d[0], 1); |
42 | assert_eq!(d[1], 2); | |
43 | assert_eq!(d[2], 3); | |
44 | assert_eq!(d[3], 4); | |
45 | } | |
46 | ||
3157f602 | 47 | fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) { |
c34b1796 AL |
48 | let mut deq = VecDeque::new(); |
49 | assert_eq!(deq.len(), 0); | |
50 | deq.push_front(a.clone()); | |
51 | deq.push_front(b.clone()); | |
52 | deq.push_back(c.clone()); | |
53 | assert_eq!(deq.len(), 3); | |
54 | deq.push_back(d.clone()); | |
55 | assert_eq!(deq.len(), 4); | |
56 | assert_eq!((*deq.front().unwrap()).clone(), b.clone()); | |
57 | assert_eq!((*deq.back().unwrap()).clone(), d.clone()); | |
58 | assert_eq!(deq.pop_front().unwrap(), b.clone()); | |
59 | assert_eq!(deq.pop_back().unwrap(), d.clone()); | |
60 | assert_eq!(deq.pop_back().unwrap(), c.clone()); | |
61 | assert_eq!(deq.pop_back().unwrap(), a.clone()); | |
62 | assert_eq!(deq.len(), 0); | |
63 | deq.push_back(c.clone()); | |
64 | assert_eq!(deq.len(), 1); | |
65 | deq.push_front(b.clone()); | |
66 | assert_eq!(deq.len(), 2); | |
67 | deq.push_back(d.clone()); | |
68 | assert_eq!(deq.len(), 3); | |
69 | deq.push_front(a.clone()); | |
70 | assert_eq!(deq.len(), 4); | |
71 | assert_eq!(deq[0].clone(), a.clone()); | |
72 | assert_eq!(deq[1].clone(), b.clone()); | |
73 | assert_eq!(deq[2].clone(), c.clone()); | |
74 | assert_eq!(deq[3].clone(), d.clone()); | |
75 | } | |
76 | ||
77 | #[test] | |
78 | fn test_push_front_grow() { | |
79 | let mut deq = VecDeque::new(); | |
80 | for i in 0..66 { | |
81 | deq.push_front(i); | |
82 | } | |
83 | assert_eq!(deq.len(), 66); | |
84 | ||
85 | for i in 0..66 { | |
86 | assert_eq!(deq[i], 65 - i); | |
87 | } | |
88 | ||
89 | let mut deq = VecDeque::new(); | |
90 | for i in 0..66 { | |
91 | deq.push_back(i); | |
92 | } | |
93 | ||
94 | for i in 0..66 { | |
95 | assert_eq!(deq[i], i); | |
96 | } | |
97 | } | |
98 | ||
99 | #[test] | |
100 | fn test_index() { | |
101 | let mut deq = VecDeque::new(); | |
102 | for i in 1..4 { | |
103 | deq.push_front(i); | |
104 | } | |
105 | assert_eq!(deq[1], 2); | |
106 | } | |
107 | ||
108 | #[test] | |
109 | #[should_panic] | |
110 | fn test_index_out_of_bounds() { | |
111 | let mut deq = VecDeque::new(); | |
112 | for i in 1..4 { | |
113 | deq.push_front(i); | |
114 | } | |
115 | deq[3]; | |
116 | } | |
117 | ||
c34b1796 AL |
118 | #[derive(Clone, PartialEq, Debug)] |
119 | enum Taggy { | |
120 | One(i32), | |
121 | Two(i32, i32), | |
122 | Three(i32, i32, i32), | |
123 | } | |
124 | ||
125 | #[derive(Clone, PartialEq, Debug)] | |
126 | enum Taggypar<T> { | |
127 | Onepar(T), | |
128 | Twopar(T, T), | |
129 | Threepar(T, T, T), | |
130 | } | |
131 | ||
132 | #[derive(Clone, PartialEq, Debug)] | |
133 | struct RecCy { | |
134 | x: i32, | |
135 | y: i32, | |
3157f602 | 136 | t: Taggy, |
c34b1796 AL |
137 | } |
138 | ||
139 | #[test] | |
140 | fn test_param_int() { | |
141 | test_parameterized::<i32>(5, 72, 64, 175); | |
142 | } | |
143 | ||
144 | #[test] | |
145 | fn test_param_taggy() { | |
146 | test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42)); | |
147 | } | |
148 | ||
149 | #[test] | |
150 | fn test_param_taggypar() { | |
60c5eb7d XL |
151 | test_parameterized::<Taggypar<i32>>( |
152 | Onepar::<i32>(1), | |
153 | Twopar::<i32>(1, 2), | |
154 | Threepar::<i32>(1, 2, 3), | |
155 | Twopar::<i32>(17, 42), | |
156 | ); | |
c34b1796 AL |
157 | } |
158 | ||
159 | #[test] | |
160 | fn test_param_reccy() { | |
60c5eb7d XL |
161 | let reccy1 = RecCy { x: 1, y: 2, t: One(1) }; |
162 | let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) }; | |
163 | let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) }; | |
164 | let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) }; | |
c34b1796 AL |
165 | test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4); |
166 | } | |
167 | ||
168 | #[test] | |
169 | fn test_with_capacity() { | |
170 | let mut d = VecDeque::with_capacity(0); | |
171 | d.push_back(1); | |
172 | assert_eq!(d.len(), 1); | |
173 | let mut d = VecDeque::with_capacity(50); | |
174 | d.push_back(1); | |
175 | assert_eq!(d.len(), 1); | |
176 | } | |
177 | ||
178 | #[test] | |
179 | fn test_with_capacity_non_power_two() { | |
180 | let mut d3 = VecDeque::with_capacity(3); | |
181 | d3.push_back(1); | |
182 | ||
183 | // X = None, | = lo | |
184 | // [|1, X, X] | |
185 | assert_eq!(d3.pop_front(), Some(1)); | |
186 | // [X, |X, X] | |
187 | assert_eq!(d3.front(), None); | |
188 | ||
189 | // [X, |3, X] | |
190 | d3.push_back(3); | |
191 | // [X, |3, 6] | |
192 | d3.push_back(6); | |
193 | // [X, X, |6] | |
194 | assert_eq!(d3.pop_front(), Some(3)); | |
195 | ||
196 | // Pushing the lo past half way point to trigger | |
197 | // the 'B' scenario for growth | |
198 | // [9, X, |6] | |
199 | d3.push_back(9); | |
200 | // [9, 12, |6] | |
201 | d3.push_back(12); | |
202 | ||
203 | d3.push_back(15); | |
204 | // There used to be a bug here about how the | |
205 | // VecDeque made growth assumptions about the | |
206 | // underlying Vec which didn't hold and lead | |
207 | // to corruption. | |
208 | // (Vec grows to next power of two) | |
3157f602 XL |
209 | // good- [9, 12, 15, X, X, X, X, |6] |
210 | // bug- [15, 12, X, X, X, |6, X, X] | |
c34b1796 AL |
211 | assert_eq!(d3.pop_front(), Some(6)); |
212 | ||
213 | // Which leads us to the following state which | |
214 | // would be a failure case. | |
3157f602 | 215 | // bug- [15, 12, X, X, X, X, |X, X] |
c34b1796 AL |
216 | assert_eq!(d3.front(), Some(&9)); |
217 | } | |
218 | ||
219 | #[test] | |
220 | fn test_reserve_exact() { | |
221 | let mut d = VecDeque::new(); | |
222 | d.push_back(0); | |
223 | d.reserve_exact(50); | |
224 | assert!(d.capacity() >= 51); | |
225 | } | |
226 | ||
227 | #[test] | |
228 | fn test_reserve() { | |
229 | let mut d = VecDeque::new(); | |
230 | d.push_back(0); | |
231 | d.reserve(50); | |
232 | assert!(d.capacity() >= 51); | |
233 | } | |
234 | ||
235 | #[test] | |
236 | fn test_swap() { | |
237 | let mut d: VecDeque<_> = (0..5).collect(); | |
238 | d.pop_front(); | |
239 | d.swap(0, 3); | |
240 | assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]); | |
241 | } | |
242 | ||
243 | #[test] | |
244 | fn test_iter() { | |
245 | let mut d = VecDeque::new(); | |
246 | assert_eq!(d.iter().next(), None); | |
247 | assert_eq!(d.iter().size_hint(), (0, Some(0))); | |
248 | ||
249 | for i in 0..5 { | |
250 | d.push_back(i); | |
251 | } | |
252 | { | |
3157f602 | 253 | let b: &[_] = &[&0, &1, &2, &3, &4]; |
c34b1796 AL |
254 | assert_eq!(d.iter().collect::<Vec<_>>(), b); |
255 | } | |
256 | ||
257 | for i in 6..9 { | |
258 | d.push_front(i); | |
259 | } | |
260 | { | |
3157f602 | 261 | let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4]; |
c34b1796 AL |
262 | assert_eq!(d.iter().collect::<Vec<_>>(), b); |
263 | } | |
264 | ||
265 | let mut it = d.iter(); | |
266 | let mut len = d.len(); | |
267 | loop { | |
268 | match it.next() { | |
269 | None => break, | |
3157f602 XL |
270 | _ => { |
271 | len -= 1; | |
272 | assert_eq!(it.size_hint(), (len, Some(len))) | |
273 | } | |
c34b1796 AL |
274 | } |
275 | } | |
276 | } | |
277 | ||
278 | #[test] | |
279 | fn test_rev_iter() { | |
280 | let mut d = VecDeque::new(); | |
281 | assert_eq!(d.iter().rev().next(), None); | |
282 | ||
283 | for i in 0..5 { | |
284 | d.push_back(i); | |
285 | } | |
286 | { | |
3157f602 | 287 | let b: &[_] = &[&4, &3, &2, &1, &0]; |
c34b1796 AL |
288 | assert_eq!(d.iter().rev().collect::<Vec<_>>(), b); |
289 | } | |
290 | ||
291 | for i in 6..9 { | |
292 | d.push_front(i); | |
293 | } | |
3157f602 | 294 | let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8]; |
c34b1796 AL |
295 | assert_eq!(d.iter().rev().collect::<Vec<_>>(), b); |
296 | } | |
297 | ||
298 | #[test] | |
299 | fn test_mut_rev_iter_wrap() { | |
300 | let mut d = VecDeque::with_capacity(3); | |
301 | assert!(d.iter_mut().rev().next().is_none()); | |
302 | ||
303 | d.push_back(1); | |
304 | d.push_back(2); | |
305 | d.push_back(3); | |
306 | assert_eq!(d.pop_front(), Some(1)); | |
307 | d.push_back(4); | |
308 | ||
60c5eb7d | 309 | assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(), vec![4, 3, 2]); |
c34b1796 AL |
310 | } |
311 | ||
312 | #[test] | |
313 | fn test_mut_iter() { | |
314 | let mut d = VecDeque::new(); | |
315 | assert!(d.iter_mut().next().is_none()); | |
316 | ||
317 | for i in 0..3 { | |
318 | d.push_front(i); | |
319 | } | |
320 | ||
321 | for (i, elt) in d.iter_mut().enumerate() { | |
322 | assert_eq!(*elt, 2 - i); | |
323 | *elt = i; | |
324 | } | |
325 | ||
326 | { | |
327 | let mut it = d.iter_mut(); | |
328 | assert_eq!(*it.next().unwrap(), 0); | |
329 | assert_eq!(*it.next().unwrap(), 1); | |
330 | assert_eq!(*it.next().unwrap(), 2); | |
331 | assert!(it.next().is_none()); | |
332 | } | |
333 | } | |
334 | ||
335 | #[test] | |
336 | fn test_mut_rev_iter() { | |
337 | let mut d = VecDeque::new(); | |
338 | assert!(d.iter_mut().rev().next().is_none()); | |
339 | ||
340 | for i in 0..3 { | |
341 | d.push_front(i); | |
342 | } | |
343 | ||
344 | for (i, elt) in d.iter_mut().rev().enumerate() { | |
345 | assert_eq!(*elt, i); | |
346 | *elt = i; | |
347 | } | |
348 | ||
349 | { | |
350 | let mut it = d.iter_mut().rev(); | |
351 | assert_eq!(*it.next().unwrap(), 0); | |
352 | assert_eq!(*it.next().unwrap(), 1); | |
353 | assert_eq!(*it.next().unwrap(), 2); | |
354 | assert!(it.next().is_none()); | |
355 | } | |
356 | } | |
357 | ||
358 | #[test] | |
359 | fn test_into_iter() { | |
c34b1796 AL |
360 | // Empty iter |
361 | { | |
362 | let d: VecDeque<i32> = VecDeque::new(); | |
363 | let mut iter = d.into_iter(); | |
364 | ||
365 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
366 | assert_eq!(iter.next(), None); | |
367 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
368 | } | |
369 | ||
370 | // simple iter | |
371 | { | |
372 | let mut d = VecDeque::new(); | |
373 | for i in 0..5 { | |
374 | d.push_back(i); | |
375 | } | |
376 | ||
3157f602 | 377 | let b = vec![0, 1, 2, 3, 4]; |
c34b1796 AL |
378 | assert_eq!(d.into_iter().collect::<Vec<_>>(), b); |
379 | } | |
380 | ||
381 | // wrapped iter | |
382 | { | |
383 | let mut d = VecDeque::new(); | |
384 | for i in 0..5 { | |
385 | d.push_back(i); | |
386 | } | |
387 | for i in 6..9 { | |
388 | d.push_front(i); | |
389 | } | |
390 | ||
3157f602 | 391 | let b = vec![8, 7, 6, 0, 1, 2, 3, 4]; |
c34b1796 AL |
392 | assert_eq!(d.into_iter().collect::<Vec<_>>(), b); |
393 | } | |
394 | ||
395 | // partially used | |
396 | { | |
397 | let mut d = VecDeque::new(); | |
398 | for i in 0..5 { | |
399 | d.push_back(i); | |
400 | } | |
401 | for i in 6..9 { | |
402 | d.push_front(i); | |
403 | } | |
404 | ||
405 | let mut it = d.into_iter(); | |
406 | assert_eq!(it.size_hint(), (8, Some(8))); | |
407 | assert_eq!(it.next(), Some(8)); | |
408 | assert_eq!(it.size_hint(), (7, Some(7))); | |
409 | assert_eq!(it.next_back(), Some(4)); | |
410 | assert_eq!(it.size_hint(), (6, Some(6))); | |
411 | assert_eq!(it.next(), Some(7)); | |
412 | assert_eq!(it.size_hint(), (5, Some(5))); | |
413 | } | |
414 | } | |
415 | ||
416 | #[test] | |
417 | fn test_drain() { | |
c34b1796 AL |
418 | // Empty iter |
419 | { | |
420 | let mut d: VecDeque<i32> = VecDeque::new(); | |
421 | ||
422 | { | |
b039eaaf | 423 | let mut iter = d.drain(..); |
c34b1796 AL |
424 | |
425 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
426 | assert_eq!(iter.next(), None); | |
427 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
428 | } | |
429 | ||
430 | assert!(d.is_empty()); | |
431 | } | |
432 | ||
433 | // simple iter | |
434 | { | |
435 | let mut d = VecDeque::new(); | |
436 | for i in 0..5 { | |
437 | d.push_back(i); | |
438 | } | |
439 | ||
b039eaaf | 440 | assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]); |
c34b1796 AL |
441 | assert!(d.is_empty()); |
442 | } | |
443 | ||
444 | // wrapped iter | |
445 | { | |
446 | let mut d = VecDeque::new(); | |
447 | for i in 0..5 { | |
448 | d.push_back(i); | |
449 | } | |
450 | for i in 6..9 { | |
451 | d.push_front(i); | |
452 | } | |
453 | ||
3157f602 | 454 | assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]); |
c34b1796 AL |
455 | assert!(d.is_empty()); |
456 | } | |
457 | ||
458 | // partially used | |
459 | { | |
460 | let mut d: VecDeque<_> = VecDeque::new(); | |
461 | for i in 0..5 { | |
462 | d.push_back(i); | |
463 | } | |
464 | for i in 6..9 { | |
465 | d.push_front(i); | |
466 | } | |
467 | ||
468 | { | |
b039eaaf | 469 | let mut it = d.drain(..); |
c34b1796 AL |
470 | assert_eq!(it.size_hint(), (8, Some(8))); |
471 | assert_eq!(it.next(), Some(8)); | |
472 | assert_eq!(it.size_hint(), (7, Some(7))); | |
473 | assert_eq!(it.next_back(), Some(4)); | |
474 | assert_eq!(it.size_hint(), (6, Some(6))); | |
475 | assert_eq!(it.next(), Some(7)); | |
476 | assert_eq!(it.size_hint(), (5, Some(5))); | |
477 | } | |
478 | assert!(d.is_empty()); | |
479 | } | |
480 | } | |
481 | ||
482 | #[test] | |
483 | fn test_from_iter() { | |
3157f602 | 484 | let v = vec![1, 2, 3, 4, 5, 6, 7]; |
c34b1796 AL |
485 | let deq: VecDeque<_> = v.iter().cloned().collect(); |
486 | let u: Vec<_> = deq.iter().cloned().collect(); | |
487 | assert_eq!(u, v); | |
488 | ||
041b39d2 | 489 | let seq = (0..).step_by(2).take(256); |
c34b1796 AL |
490 | let deq: VecDeque<_> = seq.collect(); |
491 | for (i, &x) in deq.iter().enumerate() { | |
3157f602 | 492 | assert_eq!(2 * i, x); |
c34b1796 AL |
493 | } |
494 | assert_eq!(deq.len(), 256); | |
495 | } | |
496 | ||
497 | #[test] | |
498 | fn test_clone() { | |
499 | let mut d = VecDeque::new(); | |
500 | d.push_front(17); | |
501 | d.push_front(42); | |
502 | d.push_back(137); | |
503 | d.push_back(137); | |
504 | assert_eq!(d.len(), 4); | |
505 | let mut e = d.clone(); | |
506 | assert_eq!(e.len(), 4); | |
507 | while !d.is_empty() { | |
508 | assert_eq!(d.pop_back(), e.pop_back()); | |
509 | } | |
510 | assert_eq!(d.len(), 0); | |
511 | assert_eq!(e.len(), 0); | |
512 | } | |
513 | ||
514 | #[test] | |
515 | fn test_eq() { | |
516 | let mut d = VecDeque::new(); | |
517 | assert!(d == VecDeque::with_capacity(0)); | |
518 | d.push_front(137); | |
519 | d.push_front(17); | |
520 | d.push_front(42); | |
521 | d.push_back(137); | |
522 | let mut e = VecDeque::with_capacity(0); | |
523 | e.push_back(42); | |
524 | e.push_back(17); | |
525 | e.push_back(137); | |
526 | e.push_back(137); | |
527 | assert!(&e == &d); | |
528 | e.pop_back(); | |
529 | e.push_back(0); | |
530 | assert!(e != d); | |
531 | e.clear(); | |
532 | assert!(e == VecDeque::new()); | |
533 | } | |
534 | ||
8bb4bdeb XL |
535 | #[test] |
536 | fn test_partial_eq_array() { | |
537 | let d = VecDeque::<char>::new(); | |
538 | assert!(d == []); | |
539 | ||
540 | let mut d = VecDeque::new(); | |
541 | d.push_front('a'); | |
542 | assert!(d == ['a']); | |
543 | ||
544 | let mut d = VecDeque::new(); | |
545 | d.push_back('a'); | |
546 | assert!(d == ['a']); | |
547 | ||
548 | let mut d = VecDeque::new(); | |
549 | d.push_back('a'); | |
550 | d.push_back('b'); | |
551 | assert!(d == ['a', 'b']); | |
552 | } | |
553 | ||
c34b1796 AL |
554 | #[test] |
555 | fn test_hash() { | |
3157f602 XL |
556 | let mut x = VecDeque::new(); |
557 | let mut y = VecDeque::new(); | |
c34b1796 | 558 | |
3157f602 XL |
559 | x.push_back(1); |
560 | x.push_back(2); | |
561 | x.push_back(3); | |
c34b1796 | 562 | |
3157f602 XL |
563 | y.push_back(0); |
564 | y.push_back(1); | |
565 | y.pop_front(); | |
566 | y.push_back(2); | |
567 | y.push_back(3); | |
c34b1796 | 568 | |
9fa01778 | 569 | assert!(hash(&x) == hash(&y)); |
c34b1796 AL |
570 | } |
571 | ||
7453a54e SL |
572 | #[test] |
573 | fn test_hash_after_rotation() { | |
574 | // test that two deques hash equal even if elements are laid out differently | |
575 | let len = 28; | |
576 | let mut ring: VecDeque<i32> = (0..len as i32).collect(); | |
577 | let orig = ring.clone(); | |
578 | for _ in 0..ring.capacity() { | |
579 | // shift values 1 step to the right by pop, sub one, push | |
580 | ring.pop_front(); | |
581 | for elt in &mut ring { | |
582 | *elt -= 1; | |
583 | } | |
584 | ring.push_back(len - 1); | |
9fa01778 | 585 | assert_eq!(hash(&orig), hash(&ring)); |
7453a54e SL |
586 | assert_eq!(orig, ring); |
587 | assert_eq!(ring, orig); | |
588 | } | |
589 | } | |
590 | ||
591 | #[test] | |
592 | fn test_eq_after_rotation() { | |
593 | // test that two deques are equal even if elements are laid out differently | |
594 | let len = 28; | |
595 | let mut ring: VecDeque<i32> = (0..len as i32).collect(); | |
596 | let mut shifted = ring.clone(); | |
597 | for _ in 0..10 { | |
598 | // shift values 1 step to the right by pop, sub one, push | |
599 | ring.pop_front(); | |
600 | for elt in &mut ring { | |
601 | *elt -= 1; | |
602 | } | |
603 | ring.push_back(len - 1); | |
604 | } | |
605 | ||
606 | // try every shift | |
607 | for _ in 0..shifted.capacity() { | |
608 | shifted.pop_front(); | |
609 | for elt in &mut shifted { | |
610 | *elt -= 1; | |
611 | } | |
612 | shifted.push_back(len - 1); | |
613 | assert_eq!(shifted, ring); | |
614 | assert_eq!(ring, shifted); | |
615 | } | |
616 | } | |
617 | ||
c34b1796 AL |
618 | #[test] |
619 | fn test_ord() { | |
620 | let x = VecDeque::new(); | |
621 | let mut y = VecDeque::new(); | |
622 | y.push_back(1); | |
623 | y.push_back(2); | |
624 | y.push_back(3); | |
625 | assert!(x < y); | |
626 | assert!(y > x); | |
627 | assert!(x <= x); | |
628 | assert!(x >= x); | |
629 | } | |
630 | ||
631 | #[test] | |
632 | fn test_show() { | |
633 | let ringbuf: VecDeque<_> = (0..10).collect(); | |
634 | assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); | |
635 | ||
60c5eb7d XL |
636 | let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); |
637 | assert_eq!(format!("{:?}", ringbuf), "[\"just\", \"one\", \"test\", \"more\"]"); | |
c34b1796 AL |
638 | } |
639 | ||
640 | #[test] | |
641 | fn test_drop() { | |
c30ab7b3 | 642 | static mut DROPS: i32 = 0; |
c34b1796 AL |
643 | struct Elem; |
644 | impl Drop for Elem { | |
645 | fn drop(&mut self) { | |
3157f602 | 646 | unsafe { |
c30ab7b3 | 647 | DROPS += 1; |
3157f602 | 648 | } |
c34b1796 AL |
649 | } |
650 | } | |
651 | ||
652 | let mut ring = VecDeque::new(); | |
653 | ring.push_back(Elem); | |
654 | ring.push_front(Elem); | |
655 | ring.push_back(Elem); | |
656 | ring.push_front(Elem); | |
657 | drop(ring); | |
658 | ||
c30ab7b3 | 659 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
660 | } |
661 | ||
662 | #[test] | |
663 | fn test_drop_with_pop() { | |
c30ab7b3 | 664 | static mut DROPS: i32 = 0; |
c34b1796 AL |
665 | struct Elem; |
666 | impl Drop for Elem { | |
667 | fn drop(&mut self) { | |
3157f602 | 668 | unsafe { |
c30ab7b3 | 669 | DROPS += 1; |
3157f602 | 670 | } |
c34b1796 AL |
671 | } |
672 | } | |
673 | ||
674 | let mut ring = VecDeque::new(); | |
675 | ring.push_back(Elem); | |
676 | ring.push_front(Elem); | |
677 | ring.push_back(Elem); | |
678 | ring.push_front(Elem); | |
679 | ||
680 | drop(ring.pop_back()); | |
681 | drop(ring.pop_front()); | |
c30ab7b3 | 682 | assert_eq!(unsafe { DROPS }, 2); |
c34b1796 AL |
683 | |
684 | drop(ring); | |
c30ab7b3 | 685 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
686 | } |
687 | ||
688 | #[test] | |
689 | fn test_drop_clear() { | |
c30ab7b3 | 690 | static mut DROPS: i32 = 0; |
c34b1796 AL |
691 | struct Elem; |
692 | impl Drop for Elem { | |
693 | fn drop(&mut self) { | |
3157f602 | 694 | unsafe { |
c30ab7b3 | 695 | DROPS += 1; |
3157f602 | 696 | } |
c34b1796 AL |
697 | } |
698 | } | |
699 | ||
700 | let mut ring = VecDeque::new(); | |
701 | ring.push_back(Elem); | |
702 | ring.push_front(Elem); | |
703 | ring.push_back(Elem); | |
704 | ring.push_front(Elem); | |
705 | ring.clear(); | |
c30ab7b3 | 706 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
707 | |
708 | drop(ring); | |
c30ab7b3 | 709 | assert_eq!(unsafe { DROPS }, 4); |
c34b1796 AL |
710 | } |
711 | ||
60c5eb7d XL |
712 | #[test] |
713 | fn test_drop_panic() { | |
714 | static mut DROPS: i32 = 0; | |
715 | ||
716 | struct D(bool); | |
717 | ||
718 | impl Drop for D { | |
719 | fn drop(&mut self) { | |
720 | unsafe { | |
721 | DROPS += 1; | |
722 | } | |
723 | ||
724 | if self.0 { | |
725 | panic!("panic in `drop`"); | |
726 | } | |
727 | } | |
728 | } | |
729 | ||
730 | let mut q = VecDeque::new(); | |
731 | q.push_back(D(false)); | |
732 | q.push_back(D(false)); | |
733 | q.push_back(D(false)); | |
734 | q.push_back(D(false)); | |
735 | q.push_back(D(false)); | |
736 | q.push_front(D(false)); | |
737 | q.push_front(D(false)); | |
738 | q.push_front(D(true)); | |
739 | ||
740 | catch_unwind(move || drop(q)).ok(); | |
741 | ||
742 | assert_eq!(unsafe { DROPS }, 8); | |
743 | } | |
744 | ||
c34b1796 AL |
745 | #[test] |
746 | fn test_reserve_grow() { | |
747 | // test growth path A | |
748 | // [T o o H] -> [T o o H . . . . ] | |
749 | let mut ring = VecDeque::with_capacity(4); | |
750 | for i in 0..3 { | |
751 | ring.push_back(i); | |
752 | } | |
753 | ring.reserve(7); | |
754 | for i in 0..3 { | |
755 | assert_eq!(ring.pop_front(), Some(i)); | |
756 | } | |
757 | ||
758 | // test growth path B | |
759 | // [H T o o] -> [. T o o H . . . ] | |
760 | let mut ring = VecDeque::with_capacity(4); | |
761 | for i in 0..1 { | |
762 | ring.push_back(i); | |
763 | assert_eq!(ring.pop_front(), Some(i)); | |
764 | } | |
765 | for i in 0..3 { | |
766 | ring.push_back(i); | |
767 | } | |
768 | ring.reserve(7); | |
769 | for i in 0..3 { | |
770 | assert_eq!(ring.pop_front(), Some(i)); | |
771 | } | |
772 | ||
773 | // test growth path C | |
774 | // [o o H T] -> [o o H . . . . T ] | |
775 | let mut ring = VecDeque::with_capacity(4); | |
776 | for i in 0..3 { | |
777 | ring.push_back(i); | |
778 | assert_eq!(ring.pop_front(), Some(i)); | |
779 | } | |
780 | for i in 0..3 { | |
781 | ring.push_back(i); | |
782 | } | |
783 | ring.reserve(7); | |
784 | for i in 0..3 { | |
785 | assert_eq!(ring.pop_front(), Some(i)); | |
786 | } | |
787 | } | |
788 | ||
789 | #[test] | |
790 | fn test_get() { | |
791 | let mut ring = VecDeque::new(); | |
792 | ring.push_back(0); | |
793 | assert_eq!(ring.get(0), Some(&0)); | |
794 | assert_eq!(ring.get(1), None); | |
795 | ||
796 | ring.push_back(1); | |
797 | assert_eq!(ring.get(0), Some(&0)); | |
798 | assert_eq!(ring.get(1), Some(&1)); | |
799 | assert_eq!(ring.get(2), None); | |
800 | ||
801 | ring.push_back(2); | |
802 | assert_eq!(ring.get(0), Some(&0)); | |
803 | assert_eq!(ring.get(1), Some(&1)); | |
804 | assert_eq!(ring.get(2), Some(&2)); | |
805 | assert_eq!(ring.get(3), None); | |
806 | ||
807 | assert_eq!(ring.pop_front(), Some(0)); | |
808 | assert_eq!(ring.get(0), Some(&1)); | |
809 | assert_eq!(ring.get(1), Some(&2)); | |
810 | assert_eq!(ring.get(2), None); | |
811 | ||
812 | assert_eq!(ring.pop_front(), Some(1)); | |
813 | assert_eq!(ring.get(0), Some(&2)); | |
814 | assert_eq!(ring.get(1), None); | |
815 | ||
816 | assert_eq!(ring.pop_front(), Some(2)); | |
817 | assert_eq!(ring.get(0), None); | |
818 | assert_eq!(ring.get(1), None); | |
819 | } | |
820 | ||
821 | #[test] | |
822 | fn test_get_mut() { | |
823 | let mut ring = VecDeque::new(); | |
824 | for i in 0..3 { | |
825 | ring.push_back(i); | |
826 | } | |
827 | ||
828 | match ring.get_mut(1) { | |
829 | Some(x) => *x = -1, | |
3157f602 | 830 | None => (), |
c34b1796 AL |
831 | }; |
832 | ||
833 | assert_eq!(ring.get_mut(0), Some(&mut 0)); | |
834 | assert_eq!(ring.get_mut(1), Some(&mut -1)); | |
835 | assert_eq!(ring.get_mut(2), Some(&mut 2)); | |
836 | assert_eq!(ring.get_mut(3), None); | |
837 | ||
838 | assert_eq!(ring.pop_front(), Some(0)); | |
839 | assert_eq!(ring.get_mut(0), Some(&mut -1)); | |
840 | assert_eq!(ring.get_mut(1), Some(&mut 2)); | |
841 | assert_eq!(ring.get_mut(2), None); | |
842 | } | |
843 | ||
844 | #[test] | |
845 | fn test_front() { | |
846 | let mut ring = VecDeque::new(); | |
847 | ring.push_back(10); | |
848 | ring.push_back(20); | |
849 | assert_eq!(ring.front(), Some(&10)); | |
850 | ring.pop_front(); | |
851 | assert_eq!(ring.front(), Some(&20)); | |
852 | ring.pop_front(); | |
853 | assert_eq!(ring.front(), None); | |
854 | } | |
855 | ||
856 | #[test] | |
857 | fn test_as_slices() { | |
858 | let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); | |
859 | let cap = ring.capacity() as i32; | |
3157f602 XL |
860 | let first = cap / 2; |
861 | let last = cap - first; | |
c34b1796 AL |
862 | for i in 0..first { |
863 | ring.push_back(i); | |
864 | ||
865 | let (left, right) = ring.as_slices(); | |
0731742a | 866 | let expected: Vec<_> = (0..=i).collect(); |
c34b1796 AL |
867 | assert_eq!(left, &expected[..]); |
868 | assert_eq!(right, []); | |
869 | } | |
870 | ||
871 | for j in -last..0 { | |
872 | ring.push_front(j); | |
873 | let (left, right) = ring.as_slices(); | |
0731742a | 874 | let expected_left: Vec<_> = (-last..=j).rev().collect(); |
c34b1796 AL |
875 | let expected_right: Vec<_> = (0..first).collect(); |
876 | assert_eq!(left, &expected_left[..]); | |
877 | assert_eq!(right, &expected_right[..]); | |
878 | } | |
879 | ||
880 | assert_eq!(ring.len() as i32, cap); | |
881 | assert_eq!(ring.capacity() as i32, cap); | |
882 | } | |
883 | ||
884 | #[test] | |
885 | fn test_as_mut_slices() { | |
886 | let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); | |
887 | let cap = ring.capacity() as i32; | |
3157f602 XL |
888 | let first = cap / 2; |
889 | let last = cap - first; | |
c34b1796 AL |
890 | for i in 0..first { |
891 | ring.push_back(i); | |
892 | ||
893 | let (left, right) = ring.as_mut_slices(); | |
0731742a | 894 | let expected: Vec<_> = (0..=i).collect(); |
c34b1796 AL |
895 | assert_eq!(left, &expected[..]); |
896 | assert_eq!(right, []); | |
897 | } | |
898 | ||
899 | for j in -last..0 { | |
900 | ring.push_front(j); | |
901 | let (left, right) = ring.as_mut_slices(); | |
0731742a | 902 | let expected_left: Vec<_> = (-last..=j).rev().collect(); |
c34b1796 AL |
903 | let expected_right: Vec<_> = (0..first).collect(); |
904 | assert_eq!(left, &expected_left[..]); | |
905 | assert_eq!(right, &expected_right[..]); | |
906 | } | |
907 | ||
908 | assert_eq!(ring.len() as i32, cap); | |
909 | assert_eq!(ring.capacity() as i32, cap); | |
910 | } | |
911 | ||
912 | #[test] | |
913 | fn test_append() { | |
914 | let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); | |
915 | let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); | |
916 | ||
917 | // normal append | |
918 | a.append(&mut b); | |
919 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
920 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []); | |
921 | ||
922 | // append nothing to something | |
923 | a.append(&mut b); | |
924 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
925 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []); | |
926 | ||
927 | // append something to nothing | |
928 | b.append(&mut a); | |
929 | assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]); | |
930 | assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []); | |
931 | } | |
d9579d0f | 932 | |
b7449926 XL |
933 | #[test] |
934 | fn test_append_permutations() { | |
935 | fn construct_vec_deque( | |
936 | push_back: usize, | |
937 | pop_back: usize, | |
938 | push_front: usize, | |
939 | pop_front: usize, | |
940 | ) -> VecDeque<usize> { | |
941 | let mut out = VecDeque::new(); | |
942 | for a in 0..push_back { | |
943 | out.push_back(a); | |
944 | } | |
945 | for b in 0..push_front { | |
946 | out.push_front(push_back + b); | |
947 | } | |
948 | for _ in 0..pop_back { | |
949 | out.pop_back(); | |
950 | } | |
951 | for _ in 0..pop_front { | |
952 | out.pop_front(); | |
953 | } | |
954 | out | |
955 | } | |
956 | ||
f9f354fc XL |
957 | // Miri is too slow |
958 | let max = if cfg!(miri) { 3 } else { 5 }; | |
b7449926 XL |
959 | |
960 | // Many different permutations of both the `VecDeque` getting appended to | |
961 | // and the one getting appended are generated to check `append`. | |
962 | // This ensures all 6 code paths of `append` are tested. | |
f9f354fc XL |
963 | for src_push_back in 0..max { |
964 | for src_push_front in 0..max { | |
b7449926 XL |
965 | // doesn't pop more values than are pushed |
966 | for src_pop_back in 0..(src_push_back + src_push_front) { | |
967 | for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) { | |
b7449926 XL |
968 | let src = construct_vec_deque( |
969 | src_push_back, | |
970 | src_pop_back, | |
971 | src_push_front, | |
972 | src_pop_front, | |
973 | ); | |
974 | ||
f9f354fc XL |
975 | for dst_push_back in 0..max { |
976 | for dst_push_front in 0..max { | |
b7449926 | 977 | for dst_pop_back in 0..(dst_push_back + dst_push_front) { |
60c5eb7d XL |
978 | for dst_pop_front in |
979 | 0..(dst_push_back + dst_push_front - dst_pop_back) | |
b7449926 XL |
980 | { |
981 | let mut dst = construct_vec_deque( | |
982 | dst_push_back, | |
983 | dst_pop_back, | |
984 | dst_push_front, | |
985 | dst_pop_front, | |
986 | ); | |
987 | let mut src = src.clone(); | |
988 | ||
989 | // Assert that appending `src` to `dst` gives the same order | |
990 | // of values as iterating over both in sequence. | |
991 | let correct = dst | |
992 | .iter() | |
993 | .chain(src.iter()) | |
994 | .cloned() | |
995 | .collect::<Vec<usize>>(); | |
996 | dst.append(&mut src); | |
997 | assert_eq!(dst, correct); | |
998 | assert!(src.is_empty()); | |
999 | } | |
1000 | } | |
1001 | } | |
1002 | } | |
1003 | } | |
1004 | } | |
1005 | } | |
1006 | } | |
1007 | } | |
1008 | ||
1009 | struct DropCounter<'a> { | |
1010 | count: &'a mut u32, | |
1011 | } | |
1012 | ||
9fa01778 | 1013 | impl Drop for DropCounter<'_> { |
b7449926 XL |
1014 | fn drop(&mut self) { |
1015 | *self.count += 1; | |
1016 | } | |
1017 | } | |
1018 | ||
1019 | #[test] | |
1020 | fn test_append_double_drop() { | |
1021 | let (mut count_a, mut count_b) = (0, 0); | |
1022 | { | |
1023 | let mut a = VecDeque::new(); | |
1024 | let mut b = VecDeque::new(); | |
1025 | a.push_back(DropCounter { count: &mut count_a }); | |
1026 | b.push_back(DropCounter { count: &mut count_b }); | |
1027 | ||
1028 | a.append(&mut b); | |
1029 | } | |
1030 | assert_eq!(count_a, 1); | |
1031 | assert_eq!(count_b, 1); | |
1032 | } | |
1033 | ||
d9579d0f AL |
1034 | #[test] |
1035 | fn test_retain() { | |
1036 | let mut buf = VecDeque::new(); | |
1037 | buf.extend(1..5); | |
1038 | buf.retain(|&x| x % 2 == 0); | |
1039 | let v: Vec<_> = buf.into_iter().collect(); | |
1040 | assert_eq!(&v[..], &[2, 4]); | |
1041 | } | |
62682a34 SL |
1042 | |
1043 | #[test] | |
1044 | fn test_extend_ref() { | |
1045 | let mut v = VecDeque::new(); | |
1046 | v.push_back(1); | |
1047 | v.extend(&[2, 3, 4]); | |
1048 | ||
1049 | assert_eq!(v.len(), 4); | |
1050 | assert_eq!(v[0], 1); | |
1051 | assert_eq!(v[1], 2); | |
1052 | assert_eq!(v[2], 3); | |
1053 | assert_eq!(v[3], 4); | |
1054 | ||
1055 | let mut w = VecDeque::new(); | |
1056 | w.push_back(5); | |
1057 | w.push_back(6); | |
1058 | v.extend(&w); | |
1059 | ||
1060 | assert_eq!(v.len(), 6); | |
1061 | assert_eq!(v[0], 1); | |
1062 | assert_eq!(v[1], 2); | |
1063 | assert_eq!(v[2], 3); | |
1064 | assert_eq!(v[3], 4); | |
1065 | assert_eq!(v[4], 5); | |
1066 | assert_eq!(v[5], 6); | |
1067 | } | |
a7813a04 XL |
1068 | |
1069 | #[test] | |
1070 | fn test_contains() { | |
1071 | let mut v = VecDeque::new(); | |
1072 | v.extend(&[2, 3, 4]); | |
1073 | ||
1074 | assert!(v.contains(&3)); | |
1075 | assert!(!v.contains(&1)); | |
1076 | ||
1077 | v.clear(); | |
1078 | ||
1079 | assert!(!v.contains(&3)); | |
1080 | } | |
9e0c209e SL |
1081 | |
1082 | #[allow(dead_code)] | |
1083 | fn assert_covariance() { | |
c30ab7b3 SL |
1084 | fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { |
1085 | d | |
1086 | } | |
9e0c209e | 1087 | } |
476ff2be SL |
1088 | |
1089 | #[test] | |
1090 | fn test_is_empty() { | |
1091 | let mut v = VecDeque::<i32>::new(); | |
1092 | assert!(v.is_empty()); | |
1093 | assert!(v.iter().is_empty()); | |
1094 | assert!(v.iter_mut().is_empty()); | |
1095 | v.extend(&[2, 3, 4]); | |
1096 | assert!(!v.is_empty()); | |
1097 | assert!(!v.iter().is_empty()); | |
1098 | assert!(!v.iter_mut().is_empty()); | |
1099 | while let Some(_) = v.pop_front() { | |
1100 | assert_eq!(v.is_empty(), v.len() == 0); | |
1101 | assert_eq!(v.iter().is_empty(), v.iter().len() == 0); | |
1102 | assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0); | |
1103 | } | |
1104 | assert!(v.is_empty()); | |
1105 | assert!(v.iter().is_empty()); | |
1106 | assert!(v.iter_mut().is_empty()); | |
1107 | assert!(v.into_iter().is_empty()); | |
1108 | } | |
8bb4bdeb | 1109 | |
0531ce1d XL |
1110 | #[test] |
1111 | fn test_reserve_exact_2() { | |
1112 | // This is all the same as test_reserve | |
1113 | ||
1114 | let mut v = VecDeque::new(); | |
1115 | ||
1116 | v.reserve_exact(2); | |
1117 | assert!(v.capacity() >= 2); | |
1118 | ||
1119 | for i in 0..16 { | |
1120 | v.push_back(i); | |
1121 | } | |
1122 | ||
1123 | assert!(v.capacity() >= 16); | |
1124 | v.reserve_exact(16); | |
1125 | assert!(v.capacity() >= 32); | |
1126 | ||
1127 | v.push_back(16); | |
1128 | ||
1129 | v.reserve_exact(16); | |
1130 | assert!(v.capacity() >= 48) | |
1131 | } | |
1132 | ||
1133 | #[test] | |
60c5eb7d | 1134 | #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM |
ba9703b0 | 1135 | #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc |
0531ce1d | 1136 | fn test_try_reserve() { |
0531ce1d XL |
1137 | // These are the interesting cases: |
1138 | // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM) | |
1139 | // * > isize::MAX should always fail | |
1140 | // * On 16/32-bit should CapacityOverflow | |
1141 | // * On 64-bit should OOM | |
1142 | // * overflow may trigger when adding `len` to `cap` (in number of elements) | |
1143 | // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes) | |
1144 | ||
1145 | const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1; | |
1146 | const MAX_USIZE: usize = usize::MAX; | |
1147 | ||
1148 | // On 16/32-bit, we check that allocations don't exceed isize::MAX, | |
1149 | // on 64-bit, we assume the OS will give an OOM for such a ridiculous size. | |
1150 | // Any platform that succeeds for these requests is technically broken with | |
1151 | // ptr::offset because LLVM is the worst. | |
1152 | let guards_against_isize = size_of::<usize>() < 8; | |
1153 | ||
1154 | { | |
1155 | // Note: basic stuff is checked by test_reserve | |
1156 | let mut empty_bytes: VecDeque<u8> = VecDeque::new(); | |
1157 | ||
1158 | // Check isize::MAX doesn't count as an overflow | |
1159 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) { | |
1160 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1161 | } | |
1162 | // Play it again, frank! (just to be sure) | |
1163 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) { | |
1164 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1165 | } | |
1166 | ||
1167 | if guards_against_isize { | |
1168 | // Check isize::MAX + 1 does count as overflow | |
1169 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) { | |
60c5eb7d XL |
1170 | } else { |
1171 | panic!("isize::MAX + 1 should trigger an overflow!") | |
1172 | } | |
0531ce1d XL |
1173 | |
1174 | // Check usize::MAX does count as overflow | |
1175 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { | |
60c5eb7d XL |
1176 | } else { |
1177 | panic!("usize::MAX should trigger an overflow!") | |
1178 | } | |
0531ce1d XL |
1179 | } else { |
1180 | // Check isize::MAX is an OOM | |
1181 | // VecDeque starts with capacity 7, always adds 1 to the capacity | |
1182 | // and also rounds the number to next power of 2 so this is the | |
1183 | // furthest we can go without triggering CapacityOverflow | |
e1599b0c | 1184 | if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_CAP) { |
60c5eb7d XL |
1185 | } else { |
1186 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1187 | } | |
0531ce1d XL |
1188 | } |
1189 | } | |
1190 | ||
0531ce1d XL |
1191 | { |
1192 | // Same basic idea, but with non-zero len | |
1193 | let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); | |
1194 | ||
1195 | if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) { | |
1196 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1197 | } | |
1198 | if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) { | |
1199 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1200 | } | |
1201 | if guards_against_isize { | |
1202 | if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) { | |
60c5eb7d XL |
1203 | } else { |
1204 | panic!("isize::MAX + 1 should trigger an overflow!"); | |
1205 | } | |
0531ce1d | 1206 | } else { |
e1599b0c | 1207 | if let Err(AllocError { .. }) = ten_bytes.try_reserve(MAX_CAP - 9) { |
60c5eb7d XL |
1208 | } else { |
1209 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1210 | } | |
0531ce1d XL |
1211 | } |
1212 | // Should always overflow in the add-to-len | |
1213 | if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) { | |
60c5eb7d XL |
1214 | } else { |
1215 | panic!("usize::MAX should trigger an overflow!") | |
1216 | } | |
0531ce1d XL |
1217 | } |
1218 | ||
0531ce1d XL |
1219 | { |
1220 | // Same basic idea, but with interesting type size | |
1221 | let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); | |
1222 | ||
60c5eb7d | 1223 | if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) { |
0531ce1d XL |
1224 | panic!("isize::MAX shouldn't trigger an overflow!"); |
1225 | } | |
60c5eb7d | 1226 | if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10) { |
0531ce1d XL |
1227 | panic!("isize::MAX shouldn't trigger an overflow!"); |
1228 | } | |
1229 | if guards_against_isize { | |
60c5eb7d XL |
1230 | if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) { |
1231 | } else { | |
1232 | panic!("isize::MAX + 1 should trigger an overflow!"); | |
1233 | } | |
0531ce1d | 1234 | } else { |
60c5eb7d XL |
1235 | if let Err(AllocError { .. }) = ten_u32s.try_reserve(MAX_CAP / 4 - 9) { |
1236 | } else { | |
1237 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1238 | } | |
0531ce1d XL |
1239 | } |
1240 | // Should fail in the mul-by-size | |
1241 | if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) { | |
1242 | } else { | |
1243 | panic!("usize::MAX should trigger an overflow!"); | |
1244 | } | |
1245 | } | |
0531ce1d XL |
1246 | } |
1247 | ||
1248 | #[test] | |
60c5eb7d | 1249 | #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM |
ba9703b0 | 1250 | #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc |
0531ce1d | 1251 | fn test_try_reserve_exact() { |
0531ce1d XL |
1252 | // This is exactly the same as test_try_reserve with the method changed. |
1253 | // See that test for comments. | |
1254 | ||
1255 | const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1; | |
1256 | const MAX_USIZE: usize = usize::MAX; | |
1257 | ||
1258 | let guards_against_isize = size_of::<usize>() < 8; | |
1259 | ||
1260 | { | |
1261 | let mut empty_bytes: VecDeque<u8> = VecDeque::new(); | |
1262 | ||
1263 | if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) { | |
1264 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1265 | } | |
1266 | if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) { | |
1267 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1268 | } | |
1269 | ||
1270 | if guards_against_isize { | |
1271 | if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) { | |
60c5eb7d XL |
1272 | } else { |
1273 | panic!("isize::MAX + 1 should trigger an overflow!") | |
1274 | } | |
0531ce1d XL |
1275 | |
1276 | if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) { | |
60c5eb7d XL |
1277 | } else { |
1278 | panic!("usize::MAX should trigger an overflow!") | |
1279 | } | |
0531ce1d XL |
1280 | } else { |
1281 | // Check isize::MAX is an OOM | |
1282 | // VecDeque starts with capacity 7, always adds 1 to the capacity | |
1283 | // and also rounds the number to next power of 2 so this is the | |
1284 | // furthest we can go without triggering CapacityOverflow | |
e1599b0c | 1285 | if let Err(AllocError { .. }) = empty_bytes.try_reserve_exact(MAX_CAP) { |
60c5eb7d XL |
1286 | } else { |
1287 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1288 | } | |
0531ce1d XL |
1289 | } |
1290 | } | |
1291 | ||
0531ce1d XL |
1292 | { |
1293 | let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); | |
1294 | ||
1295 | if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) { | |
1296 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1297 | } | |
1298 | if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) { | |
1299 | panic!("isize::MAX shouldn't trigger an overflow!"); | |
1300 | } | |
1301 | if guards_against_isize { | |
1302 | if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) { | |
60c5eb7d XL |
1303 | } else { |
1304 | panic!("isize::MAX + 1 should trigger an overflow!"); | |
1305 | } | |
0531ce1d | 1306 | } else { |
e1599b0c | 1307 | if let Err(AllocError { .. }) = ten_bytes.try_reserve_exact(MAX_CAP - 9) { |
60c5eb7d XL |
1308 | } else { |
1309 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1310 | } | |
0531ce1d XL |
1311 | } |
1312 | if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) { | |
60c5eb7d XL |
1313 | } else { |
1314 | panic!("usize::MAX should trigger an overflow!") | |
1315 | } | |
0531ce1d XL |
1316 | } |
1317 | ||
0531ce1d XL |
1318 | { |
1319 | let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect(); | |
1320 | ||
60c5eb7d | 1321 | if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) { |
0531ce1d XL |
1322 | panic!("isize::MAX shouldn't trigger an overflow!"); |
1323 | } | |
60c5eb7d | 1324 | if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10) { |
0531ce1d XL |
1325 | panic!("isize::MAX shouldn't trigger an overflow!"); |
1326 | } | |
1327 | if guards_against_isize { | |
60c5eb7d XL |
1328 | if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) { |
1329 | } else { | |
1330 | panic!("isize::MAX + 1 should trigger an overflow!"); | |
1331 | } | |
0531ce1d | 1332 | } else { |
60c5eb7d XL |
1333 | if let Err(AllocError { .. }) = ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9) { |
1334 | } else { | |
1335 | panic!("isize::MAX + 1 should trigger an OOM!") | |
1336 | } | |
0531ce1d XL |
1337 | } |
1338 | if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) { | |
60c5eb7d XL |
1339 | } else { |
1340 | panic!("usize::MAX should trigger an overflow!") | |
1341 | } | |
0531ce1d | 1342 | } |
0531ce1d | 1343 | } |
0731742a XL |
1344 | |
1345 | #[test] | |
1346 | fn test_rotate_nop() { | |
1347 | let mut v: VecDeque<_> = (0..10).collect(); | |
1348 | assert_unchanged(&v); | |
1349 | ||
1350 | v.rotate_left(0); | |
1351 | assert_unchanged(&v); | |
1352 | ||
1353 | v.rotate_left(10); | |
1354 | assert_unchanged(&v); | |
1355 | ||
1356 | v.rotate_right(0); | |
1357 | assert_unchanged(&v); | |
1358 | ||
1359 | v.rotate_right(10); | |
1360 | assert_unchanged(&v); | |
1361 | ||
1362 | v.rotate_left(3); | |
1363 | v.rotate_right(3); | |
1364 | assert_unchanged(&v); | |
1365 | ||
1366 | v.rotate_right(3); | |
1367 | v.rotate_left(3); | |
1368 | assert_unchanged(&v); | |
1369 | ||
1370 | v.rotate_left(6); | |
1371 | v.rotate_right(6); | |
1372 | assert_unchanged(&v); | |
1373 | ||
1374 | v.rotate_right(6); | |
1375 | v.rotate_left(6); | |
1376 | assert_unchanged(&v); | |
1377 | ||
1378 | v.rotate_left(3); | |
1379 | v.rotate_left(7); | |
1380 | assert_unchanged(&v); | |
1381 | ||
1382 | v.rotate_right(4); | |
1383 | v.rotate_right(6); | |
1384 | assert_unchanged(&v); | |
1385 | ||
1386 | v.rotate_left(1); | |
1387 | v.rotate_left(2); | |
1388 | v.rotate_left(3); | |
1389 | v.rotate_left(4); | |
1390 | assert_unchanged(&v); | |
1391 | ||
1392 | v.rotate_right(1); | |
1393 | v.rotate_right(2); | |
1394 | v.rotate_right(3); | |
1395 | v.rotate_right(4); | |
1396 | assert_unchanged(&v); | |
1397 | ||
1398 | fn assert_unchanged(v: &VecDeque<i32>) { | |
1399 | assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); | |
1400 | } | |
1401 | } | |
1402 | ||
1403 | #[test] | |
1404 | fn test_rotate_left_parts() { | |
1405 | let mut v: VecDeque<_> = (1..=7).collect(); | |
1406 | v.rotate_left(2); | |
1407 | assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..])); | |
1408 | v.rotate_left(2); | |
1409 | assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..])); | |
1410 | v.rotate_left(2); | |
1411 | assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..])); | |
1412 | v.rotate_left(2); | |
1413 | assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..])); | |
1414 | v.rotate_left(2); | |
1415 | assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..])); | |
1416 | v.rotate_left(2); | |
1417 | assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..])); | |
1418 | v.rotate_left(2); | |
1419 | assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..])); | |
1420 | } | |
1421 | ||
1422 | #[test] | |
1423 | fn test_rotate_right_parts() { | |
1424 | let mut v: VecDeque<_> = (1..=7).collect(); | |
1425 | v.rotate_right(2); | |
1426 | assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..])); | |
1427 | v.rotate_right(2); | |
1428 | assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..])); | |
1429 | v.rotate_right(2); | |
1430 | assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..])); | |
1431 | v.rotate_right(2); | |
1432 | assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..])); | |
1433 | v.rotate_right(2); | |
1434 | assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..])); | |
1435 | v.rotate_right(2); | |
1436 | assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..])); | |
1437 | v.rotate_right(2); | |
1438 | assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..])); | |
1439 | } | |
1440 | ||
1441 | #[test] | |
1442 | fn test_rotate_left_random() { | |
1443 | let shifts = [ | |
60c5eb7d XL |
1444 | 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3, |
1445 | 12, 9, 11, 1, 7, 9, 7, 2, | |
0731742a XL |
1446 | ]; |
1447 | let n = 12; | |
1448 | let mut v: VecDeque<_> = (0..n).collect(); | |
1449 | let mut total_shift = 0; | |
1450 | for shift in shifts.iter().cloned() { | |
1451 | v.rotate_left(shift); | |
1452 | total_shift += shift; | |
1453 | for i in 0..n { | |
1454 | assert_eq!(v[i], (i + total_shift) % n); | |
1455 | } | |
1456 | } | |
1457 | } | |
1458 | ||
1459 | #[test] | |
1460 | fn test_rotate_right_random() { | |
1461 | let shifts = [ | |
60c5eb7d XL |
1462 | 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3, |
1463 | 12, 9, 11, 1, 7, 9, 7, 2, | |
0731742a XL |
1464 | ]; |
1465 | let n = 12; | |
1466 | let mut v: VecDeque<_> = (0..n).collect(); | |
1467 | let mut total_shift = 0; | |
1468 | for shift in shifts.iter().cloned() { | |
1469 | v.rotate_right(shift); | |
1470 | total_shift += shift; | |
1471 | for i in 0..n { | |
1472 | assert_eq!(v[(i + total_shift) % n], i); | |
1473 | } | |
1474 | } | |
1475 | } | |
9fa01778 XL |
1476 | |
1477 | #[test] | |
1478 | fn test_try_fold_empty() { | |
1479 | assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None)); | |
1480 | } | |
1481 | ||
1482 | #[test] | |
1483 | fn test_try_fold_none() { | |
1484 | let v: VecDeque<u32> = (0..12).collect(); | |
60c5eb7d | 1485 | assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None })); |
9fa01778 XL |
1486 | } |
1487 | ||
1488 | #[test] | |
1489 | fn test_try_fold_ok() { | |
1490 | let v: VecDeque<u32> = (0..12).collect(); | |
1491 | assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b))); | |
1492 | } | |
1493 | ||
1494 | #[test] | |
1495 | fn test_try_fold_unit() { | |
1496 | let v: VecDeque<()> = std::iter::repeat(()).take(42).collect(); | |
1497 | assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(()))); | |
1498 | } | |
1499 | ||
9fa01778 XL |
1500 | #[test] |
1501 | fn test_try_fold_unit_none() { | |
1502 | let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect(); | |
1503 | let mut iter = v.into_iter(); | |
1504 | assert!(iter.try_fold((), |_, _| None).is_none()); | |
1505 | assert_eq!(iter.len(), 9); | |
1506 | } | |
1507 | ||
1508 | #[test] | |
1509 | fn test_try_fold_rotated() { | |
1510 | let mut v: VecDeque<_> = (0..12).collect(); | |
1511 | for n in 0..10 { | |
1512 | if n & 1 == 0 { | |
1513 | v.rotate_left(n); | |
1514 | } else { | |
1515 | v.rotate_right(n); | |
1516 | } | |
1517 | assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b))); | |
1518 | } | |
1519 | } | |
1520 | ||
1521 | #[test] | |
1522 | fn test_try_fold_moves_iter() { | |
1523 | let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); | |
1524 | let mut iter = v.into_iter(); | |
1525 | assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None); | |
1526 | assert_eq!(iter.next(), Some(&60)); | |
1527 | } | |
1528 | ||
1529 | #[test] | |
1530 | fn test_try_fold_exhaust_wrap() { | |
1531 | let mut v = VecDeque::with_capacity(7); | |
1532 | v.push_back(1); | |
1533 | v.push_back(1); | |
1534 | v.push_back(1); | |
1535 | v.pop_front(); | |
1536 | v.pop_front(); | |
1537 | let mut iter = v.iter(); | |
1538 | let _ = iter.try_fold(0, |_, _| Some(1)); | |
1539 | assert!(iter.is_empty()); | |
1540 | } | |
1541 | ||
1542 | #[test] | |
1543 | fn test_try_fold_wraparound() { | |
1544 | let mut v = VecDeque::with_capacity(8); | |
1545 | v.push_back(7); | |
1546 | v.push_back(8); | |
1547 | v.push_back(9); | |
1548 | v.push_front(2); | |
1549 | v.push_front(1); | |
1550 | let mut iter = v.iter(); | |
1551 | let _ = iter.find(|&&x| x == 2); | |
1552 | assert_eq!(Some(&7), iter.next()); | |
1553 | } | |
1554 | ||
1555 | #[test] | |
1556 | fn test_try_rfold_rotated() { | |
1557 | let mut v: VecDeque<_> = (0..12).collect(); | |
1558 | for n in 0..10 { | |
1559 | if n & 1 == 0 { | |
1560 | v.rotate_left(n); | |
1561 | } else { | |
1562 | v.rotate_right(n); | |
1563 | } | |
1564 | assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b))); | |
1565 | } | |
1566 | } | |
1567 | ||
1568 | #[test] | |
1569 | fn test_try_rfold_moves_iter() { | |
60c5eb7d | 1570 | let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect(); |
9fa01778 XL |
1571 | let mut iter = v.into_iter(); |
1572 | assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None); | |
1573 | assert_eq!(iter.next_back(), Some(&70)); | |
1574 | } | |
74b04a01 XL |
1575 | |
1576 | #[test] | |
1577 | fn truncate_leak() { | |
1578 | static mut DROPS: i32 = 0; | |
1579 | ||
1580 | struct D(bool); | |
1581 | ||
1582 | impl Drop for D { | |
1583 | fn drop(&mut self) { | |
1584 | unsafe { | |
1585 | DROPS += 1; | |
1586 | } | |
1587 | ||
1588 | if self.0 { | |
1589 | panic!("panic in `drop`"); | |
1590 | } | |
1591 | } | |
1592 | } | |
1593 | ||
1594 | let mut q = VecDeque::new(); | |
1595 | q.push_back(D(false)); | |
1596 | q.push_back(D(false)); | |
1597 | q.push_back(D(false)); | |
1598 | q.push_back(D(false)); | |
1599 | q.push_back(D(false)); | |
1600 | q.push_front(D(true)); | |
1601 | q.push_front(D(false)); | |
1602 | q.push_front(D(false)); | |
1603 | ||
1604 | catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok(); | |
1605 | ||
1606 | assert_eq!(unsafe { DROPS }, 7); | |
1607 | } | |
1608 | ||
1609 | #[test] | |
1610 | fn test_drain_leak() { | |
1611 | static mut DROPS: i32 = 0; | |
1612 | ||
1613 | #[derive(Debug, PartialEq)] | |
1614 | struct D(u32, bool); | |
1615 | ||
1616 | impl Drop for D { | |
1617 | fn drop(&mut self) { | |
1618 | unsafe { | |
1619 | DROPS += 1; | |
1620 | } | |
1621 | ||
1622 | if self.1 { | |
1623 | panic!("panic in `drop`"); | |
1624 | } | |
1625 | } | |
1626 | } | |
1627 | ||
1628 | let mut v = VecDeque::new(); | |
1629 | v.push_back(D(4, false)); | |
1630 | v.push_back(D(5, false)); | |
1631 | v.push_back(D(6, false)); | |
1632 | v.push_front(D(3, false)); | |
1633 | v.push_front(D(2, true)); | |
1634 | v.push_front(D(1, false)); | |
1635 | v.push_front(D(0, false)); | |
1636 | ||
1637 | catch_unwind(AssertUnwindSafe(|| { | |
1638 | v.drain(1..=4); | |
1639 | })) | |
1640 | .ok(); | |
1641 | ||
1642 | assert_eq!(unsafe { DROPS }, 4); | |
1643 | assert_eq!(v.len(), 3); | |
1644 | drop(v); | |
1645 | assert_eq!(unsafe { DROPS }, 7); | |
1646 | } |