summaryrefslogtreecommitdiffstats
path: root/third_party/rust/typed-arena-nomut/src/test.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/typed-arena-nomut/src/test.rs')
-rw-r--r--third_party/rust/typed-arena-nomut/src/test.rs373
1 files changed, 373 insertions, 0 deletions
diff --git a/third_party/rust/typed-arena-nomut/src/test.rs b/third_party/rust/typed-arena-nomut/src/test.rs
new file mode 100644
index 0000000000..6f666128a0
--- /dev/null
+++ b/third_party/rust/typed-arena-nomut/src/test.rs
@@ -0,0 +1,373 @@
+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);
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-05 17:14:02 +0000