In this post, we're going to test our vector.

What Exactly Are We Testing?

Trait implementations, behaviors under certain conditions. When the Vec is dropped, does the memory actually get deallocated properly? When items have been pushed into a vector, do the fields correctly reflect the state of the vector? When remove is invoked, do the remaining elements get shifted correctly? Does indexing return a reference to the correct element? Are the iterators working correctly? Does a clone invocation end up in a new vector with completely new but identical elements?

You get the idea.

Dummy Allocators

When we tested the Box, we created dummy allocators using allocators offered by the standard library. For now, we'll just copy and paste those allocators into vec.rs (We'll refactor later).

In vec.rs

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // Convenience function for getting the always successful allocator
    fn successful_allocator() -> *mut SuccessfulAllocator {
        &mut SuccessfulAllocator as *mut _
    }

        // Convenience function for getting the always fail allocator
    fn failing_allocator() -> *mut FailingAllocator {
        &mut FailingAllocator as *mut _
    }

    // Dummy allocator that we can depend on to always succeed
    struct SuccessfulAllocator;

    
    use std::alloc::Global as PlatformAllocator;
    use std::alloc::Layout;
    use std::ptr::NonNull;
    use std::alloc::Allocator as StdAllocator;
    
    // Use your computer's allocator to allocate and deallocate memory
    // Much more reliable than using our own custom allocator,
    // so we can depend on it succeeding (under normal circumstances)
    unsafe impl Allocator for SuccessfulAllocator {
        unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> {
            let mem_layout = Layout::from_size_align(size, alignment).unwrap();
            let mem = PlatformAllocator.allocate(mem_layout).unwrap();
            let ptr = mem.as_ptr() as *mut u8;
            Some(ptr)
        }
        unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {
            // Using an alignment of 1 here because I think the alignment no
            // longer matters here. We're deallocating memory because we're
            // done using it
            let mem_layout = Layout::from_size_align(size_to_dealloc, 1).unwrap();
            PlatformAllocator.deallocate(NonNull::new(ptr).unwrap(), mem_layout);
        }
    }

    // Dummy allocator we can depend on to always fail
    struct FailingAllocator;

    unsafe impl Allocator for FailingAllocator {
        unsafe fn alloc(&mut self, size: usize, alignment: usize) -> Option<*mut u8> {
            None
        }
        unsafe fn dealloc(&mut self, ptr: *mut u8, size_to_dealloc: usize) {}
    }
}

And for the testing tool to find the tests:

In main.rs

// ...Others
mod boxed;
mod vec; // NEW
mod allocator;
// ...Others

Testing

Because a lot of other things in our vector depend on the correctness of push, let's start with testing that. When a push is called, two things happen (in most cases): the pushed element is moved into the heap space and the vector's len field is increased by 1. In cases when the capacity has been reached, new heap space double the size of the previous space is allocated.

This gives us about 2 things to test:

The normal case of pushing when there is still space in the vector.
The case of pushing when capacity is filled.

You can come up with other cases yourself.

For the first case:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn test_push1() {
        let mut v: Vec<u8> = Vec::with_capacity(5, successful_allocator());
        v.push(1);
        v.push(2);
        v.push(255);
        assert_eq!(1, unsafe { *v.start_ptr.offset(0) });
        assert_eq!(2, unsafe { *v.start_ptr.offset(1) });
        assert_eq!(255, unsafe { *v.start_ptr.offset(2) });
    }

    // ...Others
}

We're using u8s so we won't have to start thinking about alignment since the alignment of a u8 is 1 (meaning any address is valid).

For the second case:

#[cfg(test)]
mod tests {
    use super::*;
    use crate::allocator::Allocator;

    // ...Others

    #[test]
    fn test_push2() {
        let mut v: Vec<u8> = Vec::with_capacity(3, successful_allocator());
        v.push(2);
        v.push(5);
        v.push(10);
        v.push(11);
        assert_eq!(v.capacity(), 6);
    }


    // ...Others
}

The pop function returns the last element in the vector, leaving its length reduced by 1. If the length of the vector is 0, it should panic.

#[test]
fn test_pop1() {
    let mut v = Vec::with_capacity(3, successful_allocator());
    v.push(212);
    v.push(33);
    assert_eq!(v.len(), 2);
    assert_eq!(v.pop(), 33);
    assert_eq!(v.len(), 1);
    assert_eq!(v.pop(), 212);
    assert_eq!(v.len(), 0);
}

Panicking:

#[should_panic]
#[test]
fn test_pop2() {
    let mut v: Vec<i32> = Vec::with_capacity(1, successful_allocator());
    v.pop();
}

Indexing:

#[test]
fn test_index() {
    let mut v = Vec::with_capacity(5, successful_allocator());
    v.push(2);
    assert_eq!(v[0], 2);
    v.push(3);
    assert_eq!(v[1], 3);
    v[0] = 100_000;
    assert_eq!(v[0], 100_000);
}

Immutable iteration:

#[test]
fn test_iter() {
    let mut v = Vec::with_capacity(2, successful_allocator());
    v.push(2);
    v.push(4);
    let mut v_iter = v.iter();
    assert_eq!(v_iter.next(), Some(&2));
    assert_eq!(v_iter.next(), Some(&4));
    assert_eq!(v_iter.next(), None);
}

Mutable iteration:

#[test]
fn test_iter_mut() {
    let mut v = Vec::with_capacity(2, successful_allocator());
    v.push(4);
    v.push(9);
    {
        let mut v_iter_mut = v.iter_mut();
        let first_item = v_iter_mut.next();
        assert_eq!(first_item, Some(&mut 4));
        let first_item = first_item.unwrap();
        *first_item = 999_999_999;
    }
    assert_eq!(v[0], 999_999_999);
}

Cloning:

#[test]
fn vec_clone() {
    let mut v = Vec::with_capacity(3, successful_allocator());
    v.push(4);
    v.push(5);
    v.push(87777);
    let other_v = v.clone();
    assert_eq!(v, other_v);
    assert_eq!(v.len(), other_v.len());
    assert_eq!(v.capacity(), other_v.capacity());
}

If you try running the tests now, you'll get errors complaining that Vec doesn't implement Debug. So, now we have to implement it. We can't just use a #[derive(Debug)] because we don't want field value to get printed out. What we want are the elements in the vector. We can do this easily with a fmt::Formatter function: debug_list.

use core::mem;
use crate::allocator::Allocator;
use core::ops::{Index, IndexMut};
use core::fmt; // NEW

impl<T: fmt::Debug + Clone> fmt::Debug for Vec<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

The debug_list function returns another struct with an entries function. This entries function takes an iterator that it uses to build the list that will get printed. The finish function finally finishes the output and returns the final result. The fmt::Formatter also has a lot of other functions useful for printing and you can check them out in the library's docs.

These tests are not extensive at all. They're barely there. You should come up with better tests that cover things these ones didn't, like alignment and the vector's behavior under allocator failures.

We're at the end of our list now:

~~Create a heap (without the heap, there can be no allocator).~~
~~Create an allocator (without the allocator, there can be no Box or Vec).~~
~~Create a Box.~~
~~Create a Vec.~~
Get on with the event handling scheme.

In the next post, we'll get on with the event handling scheme.

Take Away

For the full code, go to the repo

In The Next Post

We'll get on with the event handling scheme