Revision control
Copy as Markdown
Other Tools
use super::*;
use std::cell::Cell;
use std::mem;
use std::panic::{self, AssertUnwindSafe};
use std::ptr;
struct DropTracker<'a>(&'a Cell<u32>);
impl<'a> Drop for DropTracker<'a> {
fn drop(&mut self) {
self.0.set(self.0.get() + 1);
}
}
struct Node<'a, 'b: 'a>(Option<&'a Node<'a, 'b>>, u32, DropTracker<'b>);
#[test]
fn arena_as_intended() {
let drop_counter = Cell::new(0);
{
let arena = Arena::with_capacity(2);
let mut node: &Node = arena.alloc(Node(None, 1, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 0);
node = arena.alloc(Node(Some(node), 2, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 0);
node = arena.alloc(Node(Some(node), 3, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 1);
node = arena.alloc(Node(Some(node), 4, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 1);
assert_eq!(node.1, 4);
assert_eq!(node.0.unwrap().1, 3);
assert_eq!(node.0.unwrap().0.unwrap().1, 2);
assert_eq!(node.0.unwrap().0.unwrap().0.unwrap().1, 1);
assert!(node.0.unwrap().0.unwrap().0.unwrap().0.is_none());
assert_eq!(arena.len(), 4);
mem::drop(node);
assert_eq!(drop_counter.get(), 0);
let mut node: &Node = arena.alloc(Node(None, 5, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 1);
node = arena.alloc(Node(Some(node), 6, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 1);
node = arena.alloc(Node(Some(node), 7, DropTracker(&drop_counter)));
assert_eq!(arena.chunks.borrow().rest.len(), 2);
assert_eq!(drop_counter.get(), 0);
assert_eq!(node.1, 7);
assert_eq!(node.0.unwrap().1, 6);
assert_eq!(node.0.unwrap().0.unwrap().1, 5);
assert!(node.0.unwrap().0.unwrap().0.is_none());
assert_eq!(drop_counter.get(), 0);
}
assert_eq!(drop_counter.get(), 7);
}
#[test]
fn ensure_into_vec_maintains_order_of_allocation() {
let arena = Arena::with_capacity(1); // force multiple inner vecs
for &s in &["t", "e", "s", "t"] {
arena.alloc(String::from(s));
}
let vec = arena.into_vec();
assert_eq!(vec, vec!["t", "e", "s", "t"]);
}
#[test]
fn test_zero_cap() {
let arena = Arena::with_capacity(0);
let a = arena.alloc(1);
let b = arena.alloc(2);
assert_eq!(*a, 1);
assert_eq!(*b, 2);
assert_eq!(arena.len(), 2);
}
#[test]
fn test_alloc_extend() {
let arena = Arena::with_capacity(2);
for i in 0..15 {
let slice = arena.alloc_extend(0..i);
for (j, &elem) in slice.iter().enumerate() {
assert_eq!(j, elem);
}
}
}
#[test]
fn test_alloc_uninitialized() {
const LIMIT: usize = 15;
let drop_counter = Cell::new(0);
unsafe {
let arena: Arena<Node> = Arena::with_capacity(4);
for i in 0..LIMIT {
let slice = arena.alloc_uninitialized(i);
for (j, elem) in slice.iter_mut().enumerate() {
ptr::write(elem.as_mut_ptr(), Node(None, j as u32, DropTracker(&drop_counter)));
}
assert_eq!(drop_counter.get(), 0);
}
}
assert_eq!(drop_counter.get(), (0..LIMIT).fold(0, |a, e| a + e) as u32);
}
#[test]
fn test_alloc_extend_with_drop_counter() {
let drop_counter = Cell::new(0);
{
let arena = Arena::with_capacity(2);
let iter = (0..100).map(|j| Node(None, j as u32, DropTracker(&drop_counter)));
let older_ref = Some(&arena.alloc_extend(iter)[0]);
assert_eq!(drop_counter.get(), 0);
let iter = (0..100).map(|j| Node(older_ref, j as u32, DropTracker(&drop_counter)));
arena.alloc_extend(iter);
assert_eq!(drop_counter.get(), 0);
}
assert_eq!(drop_counter.get(), 200);
}
/// Test with bools.
///
/// Bools, unlike integers, have invalid bit patterns. Therefore, ever having an uninitialized bool
/// is insta-UB. Make sure miri doesn't find any such thing.
#[test]
fn test_alloc_uninitialized_bools() {
const LEN: usize = 20;
unsafe {
let arena: Arena<bool> = Arena::with_capacity(2);
let slice = arena.alloc_uninitialized(LEN);
for elem in slice.iter_mut() {
ptr::write(elem.as_mut_ptr(), true);
}
// Now it is fully initialized, we can safely transmute the slice.
let slice: &mut [bool] = mem::transmute(slice);
assert_eq!(&[true; LEN], slice);
}
}
/// Check nothing bad happens by panicking during initialization of borrowed slice.
#[test]
fn alloc_uninitialized_with_panic() {
struct Dropper(bool);
impl Drop for Dropper {
fn drop(&mut self) {
// Just make sure we touch the value, to make sure miri would bite if it was
// unitialized
if self.0 {
panic!();
}
}
}
let mut reached_first_init = false;
panic::catch_unwind(AssertUnwindSafe(|| unsafe {
let arena: Arena<Dropper> = Arena::new();
arena.reserve_extend(2);
let uninitialized = arena.uninitialized_array();
assert!((*uninitialized).len() >= 2);
ptr::write((*uninitialized)[0].as_mut_ptr(), Dropper(false));
reached_first_init = true;
panic!("To drop the arena");
// If it didn't panic, we would continue by initializing the second one and confirming by
// .alloc_uninitialized();
})).unwrap_err();
assert!(reached_first_init);
}
#[test]
fn test_uninitialized_array() {
let arena = Arena::with_capacity(2);
let uninit = arena.uninitialized_array();
arena.alloc_extend(0..2);
unsafe {
for (&a, b) in (&*uninit).iter().zip(0..2) {
assert_eq!(a.assume_init(), b);
}
assert!((&*arena.uninitialized_array()).as_ptr() != (&*uninit).as_ptr());
arena.alloc(0);
let uninit = arena.uninitialized_array();
assert_eq!((&*uninit).len(), 3);
}
}
#[test]
fn dont_trust_the_iterator_size() {
use std::iter::repeat;
struct WrongSizeIter<I>(I);
impl<I> Iterator for WrongSizeIter<I>
where
I: Iterator,
{
type Item = I::Item;
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(0, Some(0))
}
}
impl<I> ExactSizeIterator for WrongSizeIter<I> where I: Iterator {}
let arena = Arena::with_capacity(2);
arena.alloc(0);
let slice = arena.alloc_extend(WrongSizeIter(repeat(1).take(1_000)));
// Allocation of 1000 elements should have created a new chunk
assert_eq!(arena.chunks.borrow().rest.len(), 1);
assert_eq!(slice.len(), 1000);
}
#[test]
fn arena_is_send() {
fn assert_is_send<T: Send>(_: T) {}
// If `T` is `Send`, ...
assert_is_send(42_u32);
// Then `Arena<T>` is also `Send`.
let arena: Arena<u32> = Arena::new();
assert_is_send(arena);
}
#[test]
fn iter_mut_low_capacity() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 1_000;
const CAP: usize = 16;
let arena = Arena::with_capacity(CAP);
for i in 1..MAX {
arena.alloc(NonCopy(i));
}
assert!(
arena.chunks.borrow().rest.len() > 1,
"expected multiple chunks"
);
let mut iter = arena.iter();
for i in 1..MAX {
assert_eq!(Some(&NonCopy(i)), iter.next());
}
assert_eq!(None, iter.next());
}
#[test]
fn iter_mut_high_capacity() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 1_000;
const CAP: usize = 8192;
let arena = Arena::with_capacity(CAP);
for i in 1..MAX {
arena.alloc(NonCopy(i));
}
assert!(
arena.chunks.borrow().rest.is_empty(),
"expected single chunk"
);
let mut iter = arena.iter();
for i in 1..MAX {
assert_eq!(Some(&NonCopy(i)), iter.next());
}
assert_eq!(None, iter.next());
}
fn assert_size_hint<T>(arena_len: usize, iter: Iter<'_, T>) {
let (min, max) = iter.size_hint();
assert!(max.is_some());
let max = max.unwrap();
// Check that the actual arena length lies between the estimated min and max
assert!(min <= arena_len);
assert!(max >= arena_len);
// Check that the min and max estimates are within a factor of 3
assert!(min >= arena_len / 3);
assert!(max <= arena_len * 3);
}
#[test]
fn size_hint() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 32;
const CAP: usize = 0;
for cap in CAP..(CAP + 16/* check some non-power-of-two capacities */) {
let arena = Arena::with_capacity(cap);
for i in 1..MAX {
arena.alloc(NonCopy(i));
let iter = arena.iter();
assert_size_hint(i, iter);
}
}
}
#[test]
#[cfg_attr(miri, ignore)]
fn size_hint_low_initial_capacities() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 25_000;
const CAP: usize = 0;
for cap in CAP..(CAP + 128/* check some non-power-of-two capacities */) {
let arena = Arena::with_capacity(cap);
for i in 1..MAX {
arena.alloc(NonCopy(i));
let iter = arena.iter();
assert_size_hint(i, iter);
}
}
}
#[test]
#[cfg_attr(miri, ignore)]
fn size_hint_high_initial_capacities() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 25_000;
const CAP: usize = 8164;
for cap in CAP..(CAP + 128/* check some non-power-of-two capacities */) {
let arena = Arena::with_capacity(cap);
for i in 1..MAX {
arena.alloc(NonCopy(i));
let iter = arena.iter();
assert_size_hint(i, iter);
}
}
}
#[test]
#[cfg_attr(miri, ignore)]
fn size_hint_many_items() {
#[derive(Debug, PartialEq, Eq)]
struct NonCopy(usize);
const MAX: usize = 5_000_000;
const CAP: usize = 16;
let arena = Arena::with_capacity(CAP);
for i in 1..MAX {
arena.alloc(NonCopy(i));
let iter = arena.iter();
assert_size_hint(i, iter);
}
}