liballoc: Unconfigure tests during normal build

Remove additional libcore-like restrictions from liballoc, turns out the testing works ok if the tests are a part of liballoc itself.

1 files changed, 379 insertions, 0 deletions

diff --git a/src/liballoc/collections/vec_deque/tests.rs b/src/liballoc/collections/vec_deque/tests.rs
new file mode 100644
index 00000000000..d2535239979
--- /dev/null
+++ b/src/liballoc/collections/vec_deque/tests.rs
@@ -0,0 +1,379 @@
+use super::*;
+
+use ::test;
+
+#[bench]
+#[cfg(not(miri))] // Miri does not support benchmarks
+fn bench_push_back_100(b: &mut test::Bencher) {
+    let mut deq = VecDeque::with_capacity(101);
+    b.iter(|| {
+        for i in 0..100 {
+            deq.push_back(i);
+        }
+        deq.head = 0;
+        deq.tail = 0;
+    })
+}
+
+#[bench]
+#[cfg(not(miri))] // Miri does not support benchmarks
+fn bench_push_front_100(b: &mut test::Bencher) {
+    let mut deq = VecDeque::with_capacity(101);
+    b.iter(|| {
+        for i in 0..100 {
+            deq.push_front(i);
+        }
+        deq.head = 0;
+        deq.tail = 0;
+    })
+}
+
+#[bench]
+#[cfg(not(miri))] // Miri does not support benchmarks
+fn bench_pop_back_100(b: &mut test::Bencher) {
+    let mut deq = VecDeque::<i32>::with_capacity(101);
+
+    b.iter(|| {
+        deq.head = 100;
+        deq.tail = 0;
+        while !deq.is_empty() {
+            test::black_box(deq.pop_back());
+        }
+    })
+}
+
+#[bench]
+#[cfg(not(miri))] // Miri does not support benchmarks
+fn bench_pop_front_100(b: &mut test::Bencher) {
+    let mut deq = VecDeque::<i32>::with_capacity(101);
+
+    b.iter(|| {
+        deq.head = 100;
+        deq.tail = 0;
+        while !deq.is_empty() {
+            test::black_box(deq.pop_front());
+        }
+    })
+}
+
+#[test]
+fn test_swap_front_back_remove() {
+    fn test(back: bool) {
+        // This test checks that every single combination of tail position and length is tested.
+        // Capacity 15 should be large enough to cover every case.
+        let mut tester = VecDeque::with_capacity(15);
+        let usable_cap = tester.capacity();
+        let final_len = usable_cap / 2;
+
+        for len in 0..final_len {
+            let expected: VecDeque<_> = if back {
+                (0..len).collect()
+            } else {
+                (0..len).rev().collect()
+            };
+            for tail_pos in 0..usable_cap {
+                tester.tail = tail_pos;
+                tester.head = tail_pos;
+                if back {
+                    for i in 0..len * 2 {
+                        tester.push_front(i);
+                    }
+                    for i in 0..len {
+                        assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
+                    }
+                } else {
+                    for i in 0..len * 2 {
+                        tester.push_back(i);
+                    }
+                    for i in 0..len {
+                        let idx = tester.len() - 1 - i;
+                        assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
+                    }
+                }
+                assert!(tester.tail < tester.cap());
+                assert!(tester.head < tester.cap());
+                assert_eq!(tester, expected);
+            }
+        }
+    }
+    test(true);
+    test(false);
+}
+
+#[test]
+fn test_insert() {
+    // This test checks that every single combination of tail position, length, and
+    // insertion position is tested. Capacity 15 should be large enough to cover every case.
+
+    let mut tester = VecDeque::with_capacity(15);
+    // can't guarantee we got 15, so have to get what we got.
+    // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
+    // this test isn't covering what it wants to
+    let cap = tester.capacity();
+
+
+    // len is the length *after* insertion
+    for len in 1..cap {
+        // 0, 1, 2, .., len - 1
+        let expected = (0..).take(len).collect::<VecDeque<_>>();
+        for tail_pos in 0..cap {
+            for to_insert in 0..len {
+                tester.tail = tail_pos;
+                tester.head = tail_pos;
+                for i in 0..len {
+                    if i != to_insert {
+                        tester.push_back(i);
+                    }
+                }
+                tester.insert(to_insert, to_insert);
+                assert!(tester.tail < tester.cap());
+                assert!(tester.head < tester.cap());
+                assert_eq!(tester, expected);
+            }
+        }
+    }
+}
+
+#[test]
+fn test_remove() {
+    // This test checks that every single combination of tail position, length, and
+    // removal position is tested. Capacity 15 should be large enough to cover every case.
+
+    let mut tester = VecDeque::with_capacity(15);
+    // can't guarantee we got 15, so have to get what we got.
+    // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
+    // this test isn't covering what it wants to
+    let cap = tester.capacity();
+
+    // len is the length *after* removal
+    for len in 0..cap - 1 {
+        // 0, 1, 2, .., len - 1
+        let expected = (0..).take(len).collect::<VecDeque<_>>();
+        for tail_pos in 0..cap {
+            for to_remove in 0..=len {
+                tester.tail = tail_pos;
+                tester.head = tail_pos;
+                for i in 0..len {
+                    if i == to_remove {
+                        tester.push_back(1234);
+                    }
+                    tester.push_back(i);
+                }
+                if to_remove == len {
+                    tester.push_back(1234);
+                }
+                tester.remove(to_remove);
+                assert!(tester.tail < tester.cap());
+                assert!(tester.head < tester.cap());
+                assert_eq!(tester, expected);
+            }
+        }
+    }
+}
+
+#[test]
+fn test_drain() {
+    let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
+
+    let cap = tester.capacity();
+    for len in 0..=cap {
+        for tail in 0..=cap {
+            for drain_start in 0..=len {
+                for drain_end in drain_start..=len {
+                    tester.tail = tail;
+                    tester.head = tail;
+                    for i in 0..len {
+                        tester.push_back(i);
+                    }
+
+                    // Check that we drain the correct values
+                    let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
+                    let drained_expected: VecDeque<_> = (drain_start..drain_end).collect();
+                    assert_eq!(drained, drained_expected);
+
+                    // We shouldn't have changed the capacity or made the
+                    // head or tail out of bounds
+                    assert_eq!(tester.capacity(), cap);
+                    assert!(tester.tail < tester.cap());
+                    assert!(tester.head < tester.cap());
+
+                    // We should see the correct values in the VecDeque
+                    let expected: VecDeque<_> = (0..drain_start)
+                        .chain(drain_end..len)
+                        .collect();
+                    assert_eq!(expected, tester);
+                }
+            }
+        }
+    }
+}
+
+#[test]
+fn test_shrink_to_fit() {
+    // This test checks that every single combination of head and tail position,
+    // is tested. Capacity 15 should be large enough to cover every case.
+
+    let mut tester = VecDeque::with_capacity(15);
+    // can't guarantee we got 15, so have to get what we got.
+    // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
+    // this test isn't covering what it wants to
+    let cap = tester.capacity();
+    tester.reserve(63);
+    let max_cap = tester.capacity();
+
+    for len in 0..=cap {
+        // 0, 1, 2, .., len - 1
+        let expected = (0..).take(len).collect::<VecDeque<_>>();
+        for tail_pos in 0..=max_cap {
+            tester.tail = tail_pos;
+            tester.head = tail_pos;
+            tester.reserve(63);
+            for i in 0..len {
+                tester.push_back(i);
+            }
+            tester.shrink_to_fit();
+            assert!(tester.capacity() <= cap);
+            assert!(tester.tail < tester.cap());
+            assert!(tester.head < tester.cap());
+            assert_eq!(tester, expected);
+        }
+    }
+}
+
+#[test]
+fn test_split_off() {
+    // This test checks that every single combination of tail position, length, and
+    // split position is tested. Capacity 15 should be large enough to cover every case.
+
+    let mut tester = VecDeque::with_capacity(15);
+    // can't guarantee we got 15, so have to get what we got.
+    // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
+    // this test isn't covering what it wants to
+    let cap = tester.capacity();
+
+    // len is the length *before* splitting
+    for len in 0..cap {
+        // index to split at
+        for at in 0..=len {
+            // 0, 1, 2, .., at - 1 (may be empty)
+            let expected_self = (0..).take(at).collect::<VecDeque<_>>();
+            // at, at + 1, .., len - 1 (may be empty)
+            let expected_other = (at..).take(len - at).collect::<VecDeque<_>>();
+
+            for tail_pos in 0..cap {
+                tester.tail = tail_pos;
+                tester.head = tail_pos;
+                for i in 0..len {
+                    tester.push_back(i);
+                }
+                let result = tester.split_off(at);
+                assert!(tester.tail < tester.cap());
+                assert!(tester.head < tester.cap());
+                assert!(result.tail < result.cap());
+                assert!(result.head < result.cap());
+                assert_eq!(tester, expected_self);
+                assert_eq!(result, expected_other);
+            }
+        }
+    }
+}
+
+#[test]
+fn test_from_vec() {
+    use crate::vec::Vec;
+    for cap in 0..35 {
+        for len in 0..=cap {
+            let mut vec = Vec::with_capacity(cap);
+            vec.extend(0..len);
+
+            let vd = VecDeque::from(vec.clone());
+            assert!(vd.cap().is_power_of_two());
+            assert_eq!(vd.len(), vec.len());
+            assert!(vd.into_iter().eq(vec));
+        }
+    }
+}
+
+#[test]
+fn test_vec_from_vecdeque() {
+    use crate::vec::Vec;
+
+    fn create_vec_and_test_convert(capacity: usize, offset: usize, len: usize) {
+        let mut vd = VecDeque::with_capacity(capacity);
+        for _ in 0..offset {
+            vd.push_back(0);
+            vd.pop_front();
+        }
+        vd.extend(0..len);
+
+        let vec: Vec<_> = Vec::from(vd.clone());
+        assert_eq!(vec.len(), vd.len());
+        assert!(vec.into_iter().eq(vd));
+    }
+
+    #[cfg(not(miri))] // Miri is too slow
+    let max_pwr = 7;
+    #[cfg(miri)]
+    let max_pwr = 5;
+
+    for cap_pwr in 0..max_pwr {
+        // Make capacity as a (2^x)-1, so that the ring size is 2^x
+        let cap = (2i32.pow(cap_pwr) - 1) as usize;
+
+        // In these cases there is enough free space to solve it with copies
+        for len in 0..((cap + 1) / 2) {
+            // Test contiguous cases
+            for offset in 0..(cap - len) {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+
+            // Test cases where block at end of buffer is bigger than block at start
+            for offset in (cap - len)..(cap - (len / 2)) {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+
+            // Test cases where block at start of buffer is bigger than block at end
+            for offset in (cap - (len / 2))..cap {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+        }
+
+        // Now there's not (necessarily) space to straighten the ring with simple copies,
+        // the ring will use swapping when:
+        // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
+        //  right block size  >   free space    &&      left block size       >    free space
+        for len in ((cap + 1) / 2)..cap {
+            // Test contiguous cases
+            for offset in 0..(cap - len) {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+
+            // Test cases where block at end of buffer is bigger than block at start
+            for offset in (cap - len)..(cap - (len / 2)) {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+
+            // Test cases where block at start of buffer is bigger than block at end
+            for offset in (cap - (len / 2))..cap {
+                create_vec_and_test_convert(cap, offset, len)
+            }
+        }
+    }
+}
+
+#[test]
+fn issue_53529() {
+    use crate::boxed::Box;
+
+    let mut dst = VecDeque::new();
+    dst.push_front(Box::new(1));
+    dst.push_front(Box::new(2));
+    assert_eq!(*dst.pop_back().unwrap(), 1);
+
+    let mut src = VecDeque::new();
+    src.push_front(Box::new(2));
+    dst.append(&mut src);
+    for a in dst {
+        assert_eq!(*a, 2);
+    }
+}