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