From 24bc854b8c95ccf8e229d3982466b71ae778d04e Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Thu, 19 Jul 2018 19:58:06 +0200 Subject: Non-naive implementation for `VecDeque.append` --- src/liballoc/tests/vec_deque.rs | 54 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs index 4d55584e2f4..0c8c1f2c65b 100644 --- a/src/liballoc/tests/vec_deque.rs +++ b/src/liballoc/tests/vec_deque.rs @@ -928,6 +928,60 @@ fn test_append() { assert_eq!(a.iter().cloned().collect::>(), []); } +#[test] +fn test_append_advanced() { + fn check( + a_push_back: usize, + a_pop_back: usize, + b_push_back: usize, + b_pop_back: usize, + a_push_front: usize, + a_pop_front: usize, + b_push_front: usize, + b_pop_front: usize + ) { + let mut taken = 0; + let mut a = VecDeque::new(); + let mut b = VecDeque::new(); + for n in (taken..).take(a_push_back) { + a.push_back(n); + } + taken += a_push_back; + for n in (taken..).take(a_push_front) { + a.push_front(n); + } + taken += a_push_front; + for n in (taken..).take(b_push_back) { + b.push_back(n); + } + taken += b_push_back; + for n in (taken..).take(b_push_front) { + b.push_front(n); + } + + a.drain(..a_pop_back); + a.drain(a_pop_front..); + b.drain(..b_pop_back); + b.drain(b_pop_front..); + let checked = a.iter().chain(b.iter()).map(|&x| x).collect::>(); + a.append(&mut b); + assert_eq!(a, checked); + assert!(b.is_empty()); + } + for a_push in 0..17 { + for a_pop in 0..a_push { + for b_push in 0..17 { + for b_pop in 0..b_push { + check(a_push, a_pop, b_push, b_pop, 0, 0, 0, 0); + check(a_push, a_pop, b_push, b_pop, a_push, 0, 0, 0); + check(a_push, a_pop, b_push, b_pop, 0, 0, b_push, 0); + check(0, 0, 0, 0, a_push, a_pop, b_push, b_pop); + } + } + } + } +} + #[test] fn test_retain() { let mut buf = VecDeque::new(); -- cgit 1.4.1-3-g733a5 From 9f1fdecb3c152b9ca0713f7c85589f9447f28961 Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Sun, 22 Jul 2018 22:15:29 +0200 Subject: Simplify vecdeque append test --- src/liballoc/tests/vec_deque.rs | 106 ++++++++++++++++++++++++---------------- 1 file changed, 64 insertions(+), 42 deletions(-) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs index 0c8c1f2c65b..6efd3d60060 100644 --- a/src/liballoc/tests/vec_deque.rs +++ b/src/liballoc/tests/vec_deque.rs @@ -929,53 +929,75 @@ fn test_append() { } #[test] -fn test_append_advanced() { - fn check( - a_push_back: usize, - a_pop_back: usize, - b_push_back: usize, - b_pop_back: usize, - a_push_front: usize, - a_pop_front: usize, - b_push_front: usize, - b_pop_front: usize - ) { - let mut taken = 0; - let mut a = VecDeque::new(); - let mut b = VecDeque::new(); - for n in (taken..).take(a_push_back) { - a.push_back(n); +fn test_append_permutations() { + fn construct_vec_deque( + push_back: usize, + pop_back: usize, + push_front: usize, + pop_front: usize, + ) -> VecDeque { + let mut out = VecDeque::new(); + for a in 0..push_back { + out.push_back(a); } - taken += a_push_back; - for n in (taken..).take(a_push_front) { - a.push_front(n); + for b in 0..push_front { + out.push_front(push_back + b); } - taken += a_push_front; - for n in (taken..).take(b_push_back) { - b.push_back(n); + for _ in 0..pop_back { + out.pop_back(); } - taken += b_push_back; - for n in (taken..).take(b_push_front) { - b.push_front(n); + for _ in 0..pop_front { + out.pop_front(); } - - a.drain(..a_pop_back); - a.drain(a_pop_front..); - b.drain(..b_pop_back); - b.drain(b_pop_front..); - let checked = a.iter().chain(b.iter()).map(|&x| x).collect::>(); - a.append(&mut b); - assert_eq!(a, checked); - assert!(b.is_empty()); + out } - for a_push in 0..17 { - for a_pop in 0..a_push { - for b_push in 0..17 { - for b_pop in 0..b_push { - check(a_push, a_pop, b_push, b_pop, 0, 0, 0, 0); - check(a_push, a_pop, b_push, b_pop, a_push, 0, 0, 0); - check(a_push, a_pop, b_push, b_pop, 0, 0, b_push, 0); - check(0, 0, 0, 0, a_push, a_pop, b_push, b_pop); + + const MAX: usize = 5; + + // Many different permutations of both the `VecDeque` getting appended to + // and the one getting appended are generated to check `append`. + // This ensures all 6 code paths of `append` are tested. + for src_push_back in 0..MAX { + for src_push_front in 0..MAX { + // doesn't pop more values than are pushed + for src_pop_back in 0..(src_push_back + src_push_front) { + for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) { + + let src = construct_vec_deque( + src_push_back, + src_pop_back, + src_push_front, + src_pop_front, + ); + + for dst_push_back in 0..MAX { + for dst_push_front in 0..MAX { + for dst_pop_back in 0..(dst_push_back + dst_push_front) { + for dst_pop_front + in 0..(dst_push_back + dst_push_front - dst_pop_back) + { + let mut dst = construct_vec_deque( + dst_push_back, + dst_pop_back, + dst_push_front, + dst_pop_front, + ); + let mut src = src.clone(); + + // Assert that appending `src` to `dst` gives the same order + // of values as iterating over both in sequence. + let correct = dst + .iter() + .chain(src.iter()) + .cloned() + .collect::>(); + dst.append(&mut src); + assert_eq!(dst, correct); + assert!(src.is_empty()); + } + } + } + } } } } -- cgit 1.4.1-3-g733a5 From b063bd4616bf2f27b814f39f0e452efd171fd539 Mon Sep 17 00:00:00 2001 From: Pazzaz Date: Wed, 15 Aug 2018 19:42:07 +0200 Subject: Test VecDeque append not dropping twice --- src/liballoc/tests/vec_deque.rs | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs index 6efd3d60060..3ea6c87a651 100644 --- a/src/liballoc/tests/vec_deque.rs +++ b/src/liballoc/tests/vec_deque.rs @@ -1004,6 +1004,31 @@ fn test_append_permutations() { } } +struct DropCounter<'a> { + count: &'a mut u32, +} + +impl<'a> Drop for DropCounter<'a> { + fn drop(&mut self) { + *self.count += 1; + } +} + +#[test] +fn test_append_double_drop() { + let (mut count_a, mut count_b) = (0, 0); + { + let mut a = VecDeque::new(); + let mut b = VecDeque::new(); + a.push_back(DropCounter { count: &mut count_a }); + b.push_back(DropCounter { count: &mut count_b }); + + a.append(&mut b); + } + assert_eq!(count_a, 1); + assert_eq!(count_b, 1); +} + #[test] fn test_retain() { let mut buf = VecDeque::new(); -- cgit 1.4.1-3-g733a5