Testing with Axioms in C++ 2011
By: Anya Helene Bagge, Valentin David, Magne Haveraaen
Abstract Unit testing is an important part of modern software development,
where individual code units are tested in isolation. Such tests are
typically case-based, checking a likely error scenario or an error that has
previously been identified and fixed. Coming up with good test cases
is challenging, particularly when testing generic code, and focusing on
individual tests can distract from creating tests that cover the full functionality.
Concepts provide a generic way of describing code interfaces for generic
code. Together with axioms, program behaviour can be specified algebraically
in a formal or semi-formal way.
In this paper we show how concepts and axioms can be expressed in
standard C++ 2011, and explore how to generate generic unit tests, by
treating the axioms as code to be evaluated with test data. We also show
a generic way to generate test data for axiom-based testing in C++ 2011.
Keywords Algebraic Specification; Axiom-Based Testing; Axioms; C++;
C++0x; C++11; Concepts; Generative Programming; Mouldable Programming;
Test Generation; Unit Testing
Modern software engineering practises encourage the use of unit testing to increase
software reliability. Test-driven development (TDD) [Bec02] dictates that software
should be extended by writing tests for a new feature first, before implementing
the feature. The tests provide a specification of the behaviour of the new feature,
and provide an easy way to check the implementation throughout development and
Less extreme methods call for tests for all program units, and for regression tests
to be written to ward off the reappearance of known bugs. Such methods may be
practised rigorously, or in an ad hoc manner. Common to all is that they rely on the
programmer to invent good test cases that cover both likely and unlikely errors. The
programmer must also be careful that the tests exercise the full expected feature set,
or the implementation will seem OK when all it does is implement the bare minimum
to pass the tests.
1.1 Testing with Concepts and Axioms
We suggest writing tests based on axioms that formally specify expected behaviour,
rather than relying on ad hoc test cases. We integrate axioms with concepts that
describe code interfaces – basically, the types and operations that a program module
supports. Axiom-based testing provides reusable tests for implementations of concepts.
Also, by stating the requirements of generic code in terms of concepts, we
know what behaviour we must test for in arguments given to generic code.
Testing an implementation consists of stating (and checking) that it conforms to
the interface of the given concept, then generating suitable test data, and finally evaluating
the axioms for the generated test data values using the implementation. If
any of the axioms evaluate to false, the implementation does not satisfy the concept
specification – which may mean that the implementation is buggy, or that the specification
is wrong; if the results are to be reliable, the axiom must correctly express
the desired feature.
1.2 Concepts in C++ 2011
Concepts were proposed for inclusion in the C++111 standard as a modularisation
feature for generic programming. Concepts were designed to solve the problem of
incomprehensible error messages from deep inside C++ template code, providing a
sort of bounded polymorphism to the otherwise duck typed (at compile time) template
system, similar to how type classes work in Haskell [HHPW96]. The proposal also
allowed for axioms in concepts, opening the way to axiom-based optimisation [TJ07,
BH09] and testing [BDH09]. However, concepts were dropped [Str09] from the draft
standard [B+11b] before finalisation.
Since the proposed C++ standard no longer provides for concepts and axioms,
our approach has changed since our original implementation of axiom-based testing
for C++ [BDH09]. We now provide a library, Catsfoot, which adds alternative
concept support to C++11 as well as support for generating axiom tests, all using
template meta-programming. While we previously had to rely on an external tool to
support test generation, with limited C++ support, this is no longer necessary.
Our contributions in this article include:
a technique and library for testing with concepts and axioms in C++11,
a library for using concepts in C++11, and
a generic test data generation library to be used with axiom-based testing.
Our Catsfoot concept library supports most of the features of the previous
C++0x draft [GSSW08] (with the exception of archetypes), though in this paper we
will focus mainly on using it for axiom-based testing, leaving the rest for a future
paper. Further information on the concept library, as well as the full source code released
under the GNU LGPL license, is available at http://catsfoot.sourceforge.
We have tested all code examples in this paper with GCC 4.5.2 and 4.6.0 (with
the exception of one example, which does not run on current compiler releases). The
file containing the examples can be obtained from the website.
... to read more articles, visit http://sqa.fyicenter.com/art/