Introduction¶
- The take home QE test:
- Write a unit test, using Catch2 (a single-header C++ test framework) for
std::vector<>.
- Write a unit test, using Catch2 (a single-header C++ test framework) for
- IMO this is a bad problem
- As we will see, this is a significant project in scale
- The Catch2 docs use
vector<>in their examples, badly vector<>is very well specified, most APIs are not- Writing good tests requires some knowledge of the implementation
vector<>has been very well vetted, so it is extremely unlikely the candidate will find a bug
- I've been surprised by the results
- Disclaimers
- The usual approach to writing tests is:
- Make sure every operation is called once
- Check an attribute of the post-condition
- Add additional tests until 100% code coverage is obtained
- This approach will usually only catch trivial mistakes
- It is unlikely to catch edge cases or design errors
- During this course section we will be developing an approach to test
std::vector<>- To simplify the problem we will be only be testing with the default allocator
- We will also ignore the
std::vector<bool>specialization
- To improve the probability the code is correct
- But what is correct?
- Correct is logically consistent, without contradiction
- For software to be correct it has to mean something
- What does
0100mean?
- What does
- For objects to have meaning they must correspond to an entity, either concrete or abstract
void f() {
int i; // the value of i has no meaning
}
- Two objects are equal iff their values correspond to the same entity
- From this definition of equality we can derive the following properties
(∀a)a=a.(∀a,b)a=b⟹b=a.(∀a,b,c)a=b∧b=c⟹a=c.
History¶
- Double-entry bookkeeping was pioneered in the 11th century by Jewish banking community
- and likely developed independently in Korea in the same time period
- In the late 13th century it spread to Italy
- In the 14th century double-entry bookkeeping was adopted by the Medici bank
- And is credited with establishing the Medici bank as reliable and trustworthy, leading to the rise of one of the most powerful family dynasties in history
- Was codified by Luca Pacioli (the Father of Accounting) in 1494
- Double-entry bookkeeping is a tool for error detection and fraud prevention
- It relies on the accounting equation:
- And is an example of equational reasoning
- By ensuring that all transactions are made against two separate accounts
- The probability of error is significantly reduced
- Not eliminated
- And the account gains transparency making it easier to audit and detect fraud
- The probability of error is significantly reduced
Principals of Testing¶
- Testing is applying the principals of double-entry bookkeeping to engineering
- State each operation in two independent but equivalent forms
- Where possible, state an operation in terms of the axioms that define it
- Test for equivalency and flag any contradictions
- A contradiction does not imply the code being tested is wrong
- The test case is at least as likely to be incorrect
- A failed test only implies something is inconsistent
First Test¶
- Our tests will largely be based on what equality means
- So we start our test with making sure equality is correct
vectoris a container, the standard includes a table of the container requirements:
template <class T>
void test_equality_1(const T& a, const T& b, const T& c) {
REQUIRE(a == a); // Reflexivity
REQUIRE(!(a == b) || (b == a)); // Symmetry
REQUIRE(!(a == b && b == c) || (a == c)); // Transitivity
}
{
vector<int> a, b, c;
test_equality_1(a, b, c);
}
- There are at least two problems with this test
- It ignores the universal quantifier, ∀
- It is trivially satisfiable
operator==()could always return true
- It isn't practical, or even possible, to test universal quantifiers
- Instead we need to choose representative values
- size (zero, not-zero, different)
- capacity (equal size, greater size, different)
- values (equal, initial equal, different)
template <class T>
auto make_vector(initializer_list<T> init, std::size_t additional_capacity) {
vector<T> r;
r.reserve(size(init) + additional_capacity);
r.insert(end(r), init);
return r;
}
- Create an array of pairs tags and representative values
- Values with the same tag, and only values with the same tag, must be equal
struct {
int tag;
std::vector<int> value;
} vec_rep[]{
{0, make_vector<int>({}, 0)}, {0, make_vector<int>({}, 1)},
{0, make_vector<int>({}, 2)},
{1, make_vector({0}, 0)}, {1, make_vector({0}, 1)},
{1, make_vector({0}, 2)},
{2, make_vector({0, 1}, 0)}, {2, make_vector({0, 1}, 0)},
{2, make_vector({0, 1}, 0)},
{3, make_vector({0, 2}, 0)}, {3, make_vector({0, 2}, 0)},
{3, make_vector({0, 2}, 0)},
{4, make_vector({1, 2}, 0)}, {4, make_vector({1, 2}, 0)},
{4, make_vector({1, 2}, 0)},
};
template <class T>
void test_equality_2(const T& a) {
// Reflexivity
for (const auto& e : a)
REQUIRE(e.value == e.value);
// Symmetry
for_each_k_combination<2>(a, [](const auto& a, const auto& b) {
REQUIRE((a.tag == b.tag) == (a.value == b.value));
REQUIRE((a.tag == b.tag) == (b.value == a.value));
});
// Transitivity
for_each_k_combination<3>(a, [](const auto& a, const auto& b, const auto& c) {
REQUIRE(!(a.value == b.value && b.value == c.value) ||
(a.value == c.value));
});
}
{
test_equality_2(vec_rep);
}
- Side notes
- Is the test for transitivity redundant?
- All pair value combinations are equal to the equivalency of tags
- Tag comparisons are transitive
- Therefore value comparisons are transitive
for_each_k_combination<>is an interesting algorithm (implementation in my notes)
- Is the test for transitivity redundant?
{
int a[] = {0, 1, 2, 3, 4};
for_each_k_combination<3>(a, [](int a, int b, int c){
cout << a << "," << b << "," << c << endl;
});
}
- Knowing
operator==()is correct we can test operatoroperator!=()easily
template <class T>
void test_inequality_1(const T& a) {
for_each_k_combination<2>(a, [](const auto& a, const auto& b){
REQUIRE(!(a.value == b.value) == (a.value != b.value));
REQUIRE(!(a.value == b.value) == (b.value != a.value));
});
}
{
test_inequality_1(vec_rep);
}
Copy & Assignment¶
- Copy & Assignment are defined in term of equality
Let m() be an an action that modifies its argument such that given a=b, m(a)⟹a≠b.
a→b⟹a=b.Let a=c. a→b, m(a)⟹a≠b∧b=c.
- Notice anything missing?
- Nothing I can find in the C++ standard precludes aliased copies, i.e.
vector<int> a;
vector<int> b = a;
a.push_back(42);
assert(b.back() == 42);
- Except for breaking-all-the-code there is no disjoint requirement
- Eric Niebler, Stephan T. Lavavej, and Howard Hinnant agree
template <class T>
void test_copy_and_assignment_1(const T& v) {
for (const auto& a : v) {
{
decltype(a.value) b = a.value; // copy construct
REQUIRE(a.value == b);
}
{
decltype(a.value) b; // default construct
b = a.value; // assignment
REQUIRE(a.value == b);
}
}
}
{
test_copy_and_assignment_1(vec_rep);
}
- Only checking the first axiom
- The assignment check is always assigning to a default constructed object
- This might mask a leak
- Self assignment is not checked
- A common failure case
- No complexity test
- No failure tests
- Also, what is the behavior if there is sufficient capacity for the left value of assignment?
- I do not believe this behavior is currently specified
std::vector<int> vec_rep_2[]{
make_vector<int>({}, 0),
make_vector<int>({}, 1),
make_vector<int>({}, 2),
make_vector({0}, 0),
make_vector({0}, 1),
make_vector({0}, 2),
make_vector({0, 1}, 0),
make_vector({0, 2}, 0),
make_vector({1, 2}, 0)
};
template <class T>
void modify(vector<T>& a) {
a.push_back(T{});
}
template <class T>
void test_copy_and_assignment_2(const T& v) {
for (const auto& a : v) {
decltype(a) b = a; // copy construct
REQUIRE(a == b); // copies are equal
b = b; // self assignment
REQUIRE(a == b); // self assignment is a no-op
modify(b);
REQUIRE(a != b); // copies are disjoint
}
for (const auto& a : v) {
for (const auto& c : v) {
decltype(a) b = a; // make a copy
b = c; // copy assignment
REQUIRE(b == c); // copies ar equal
modify(b);
REQUIRE(b != c); // copies are disjoint
}
}
}
- We are still missing complexity and failure cases...
Homework¶
- Read the C++ specification for
vector: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4713.pdf- When you come across terms like
ContainerandEqualityComparablelook those up as well
- When you come across terms like
- Create a class with an
operato==()which fails in various ways and test it- Implementation of
for_each_k_combination<>is available here https://github.com/sean-parent/notebook/blob/master/common.hpp
- Implementation of
- Can you create an
vector<T>whereTis notEqualityComparable?- Consider how to test such an instance
Introduction The take home QE test: Write a unit test, using Catch2 (a single-header C++ test framework) for std::vector<> . IMO this is a bad problem As we will see, this is a significant project in scale The Catch2 docs use vector<> in their examples, badly vector<> is very well specified, most APIs are not Writing good tests requires some knowledge of the implementation vector<> has been very well vetted, so it is extremely unlikely the candidate will find a bug I've been surprised by the results