Review¶

  • How to construct a test case

Do your homework¶

  • Identify preconditions (what is expected)
    • Including implicit preconditions in the basic interface
  • Example from documentation for vector::back

Calling back on an empty container is undefined.

  • If the API is a template, what are the requirements for the type arguments?
    • Including the axioms of any operations on the type
  • Example from documentation for vector

The requirements that are imposed on the elements depend on the actual operations performed on the container. Generally, it is required that element type meets the requirements of Erasable, but many member functions impose stricter requirements. This container (but not its members) can be instantiated with an incomplete element type if the allocator satisfies the allocator completeness requirements.

  • From the general library requirements

X(a) [copy construction], Requires: T is CopyInsertable into X

  • Identify postconditions (what is guaranteed)
  • From documentation for vector

a.back(); Operational semantics:

{ auto tmp = a.end(); --tmp; return *tmp; }
  • From definition of CopyInsertable

The value of v is unchanged and is equivalent to *p

  • Note that postconditions can extend to affiliated objects

After container move construction, references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this.

  • Identify invariants (what always holds)
  • Some may be implicit and follow from definition
    • !(capacity() < size())
    • distance(begin(), end()) == size()
  • Have a basic mental model of the implementation

Design your tests¶

  • Determine a representative set of values (and types)
    • Values must satisfy preconditions
    • Different operations may require different values
    • Include values that trigger an inflection in preconditions, postconditions, and implementation
  • Tagging values is useful to identify known properties
    • Equality
    • Orderings
    • Concepts (Copyable vs. Movable)

  • Execute with all meaningful combinations of representative values

    • include aliased values where allowed
    • and duplicate values

  • Check postconditions, axioms, and invariants after API execution

  • Use counters to test complexity and external failure points

  • Use a model type with static_assert to test type requirements

Anatomy of a test case for a template¶

  • Create a model type which counts operations to measure complexity
struct {
    size_t _equality;
    size_t _ctor;
    size_t _move_ctor;
    size_t _copy_ctor;
    size_t _copy_assignment;
    size_t _move_assignment;
    size_t _dtor;
} _counters;
  • The model type is parameterized for the required operations
enum operations {
    moveable = 1 << 0,
    copyable = 1 << 1,
    equality_comparable = 1 << 2
};
  • The model tests for valid operation use
template <operations Ops>
struct model {
    int _value = 0; // 0 flags partially formed

    explicit model(int x) : _value(x) { ++_counters._ctor; }
    model(model&& x) noexcept : _value(x._value) {
        static_assert(Ops & moveable);
        x._value = 0;
        ++_counters._move_ctor;
    }
    model& operator=(model&& x) {
        static_assert(Ops & moveable);
        REQUIRE(x._value || !(x._value || _value));
        _value = x._value;
        x._value = 0;
        ++_counters._move_assignment;
        return *this;
    }
    //...
    static constexpr auto equality = [](const auto& a, const auto& b) {
        return a._value == b._value;
    };
};
  • Write a test for the class invariants
template <class C>
void test_invariants(const C& a) {
    REQUIRE(a.empty() == (a.begin() == a.end()));
    REQUIRE(distance(a.begin(), a.end()) == a.size());
    REQUIRE(!(a.capacity() < a.size()));
}
  • Write a test for each operation
    • Test invariants after a mutable operation
    • Test postconditions
    • Test complexity
template <class C, class I, class T>
void test_move_insert(
    const C& initial, const T& initial_value, C& container, I position, T value) {
    auto counters = _counters;
    bool has_capacity = container.size() < container.capacity();
    auto ip = begin(initial) + distance(begin(container), position);

    auto p = container.insert(position, move(value));
    // Test invariants
    test_invariants(container);
    // Test postconditions
    REQUIRE(equal(begin(initial), ip, begin(container), p, T::equality));
    REQUIRE(equal(ip, end(initial), next(p), end(container), T::equality));
    REQUIRE(T::equality(*p, initial_value));
    if (has_capacity) {
        REQUIRE(p == position);
    }
    // Test complexity
    auto move_count =
        (has_capacity ? distance(ip, end(initial)) : initial.size()) + 1;
    REQUIRE((_counters._move_ctor - counters._move_ctor) <= move_count);
}
  • Write a driver to construct cases which exercise inflection points
  • A helper function to generate vectors from an array with a given capacity
template <class C, class T>
auto build_vector(const T& a, size_t capacity) {
    C r;
    r.reserve(capacity);
    for (auto& e : a)
        r.emplace_back(e);
    return r;
}
  • A driver to generate test cases and execute the test
void test_move_insert_driver() {
    using value_t = model<moveable>;
    constexpr int a[] = {1, 2, 3};

    auto v1 = build_vector<vector<value_t>>(a, size(a));
    size_t positions[] = {0, size(a) / 2, size(a)}; // begin, middle, end
    // insert each position without sufficient capacity
    for (const auto& e : positions) {
        auto v2 = build_vector<vector<value_t>>(a, size(a));
        test_move_insert(v1, value_t{4}, v2, begin(v2) + e, value_t{4});
    }
    // insert each position with sufficient capacity
    for (const auto& e : positions) {
        auto v2 = build_vector<vector<value_t>>(a, size(a) + 1);
        test_move_insert(v1, value_t{4}, v2, begin(v2) + e, value_t{4});
    }
    // insert into an empty vector
    {
        vector<value_t> v2;
        test_move_insert(vector<value_t>(), value_t{4}, v2, begin(v2), value_t{4});
    }
}
  • Execute the tests
test_move_insert_driver();

Creating general test cases¶

  • For many operations and types you can write generic test case

    • copy, move, equality, comparisons
    • iterators, containers
    • numerics

  • Refine how you manage tables of representative values so you can reuse the structure with different tables for different tests

  • For a given type, you can write a single test for invariants and use it after each operation

Designing a testable interface¶

  • Write complete and regular types
  • When the semantics are the same, use the same name
  • Keep class interfaces thin
    • Seek a minimal efficient basis
  • Minimize dependencies
    • Try to write each piece of code as a stand alone library
    • Use template arguments, callbacks, and delegates to factor out dependencies

Upcoming¶

  • September 19th, Jared Wyles will guest lecture on clang-format and clang-tidy tools
  • October 3rd, Lecture on Generic Programming
  • October 17th, No class (I'll be at Pacific++ in Sydney)
  • October 31st, Start Better Code section (finally!)