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