Templates raise two classes of challenges when it comes to debugging them. One set of challenges is definitely a problem for writers of templates: How can we ensure that the templates we write will function for any template arguments that satisfy the conditions we document? The other class of problems is almost exactly the opposite: How can a user of a template find out which of the template parameter requirements it violated when the template does not behave as documented?
Before we discuss these issues in depth, it is useful to contemplate the kinds of constraints that may be imposed on template parameters. In this chapter, we deal mostly with the constraints that lead to compilation errors when violated, and we call these constraints syntactic constraints. Syntactic constraints can include the need for a certain kind of constructor to exist, for a particular function call to be unambiguous, and so forth. The other kind of constraint we call semantic constraints. These constraints are much harder to verify mechanically. In the general case, it may not even be practical to do so. For example, we may require that there be a < operator defined on a template type parameter (which is a syntactic constraint), but usually we’ll also require that the operator actually defines some sort of ordering on its domain (which is a semantic constraint).
The term concept is often used to denote a set of constraints that is repeatedly required in a template library. For example, the C++ standard library relies on such concepts as random access iterator and default constructible. With this terminology in place, we can say that debugging template code includes a significant amount of determining how concepts are violated in the template implementation and in their use. This chapter delves into both design and debugging techniques that can make templates easier to work with, both for template authors and for template users.
When template errors occur, the problems are often found after a long chain of instantiations, leading to lengthy error messages like those discussed in Section 9.4 on page 1431 To illustrate this, consider the following somewhat contrived code:
template<typename T>
void clear (T& p)
{
*p = 0; // assumes T is a pointer-like type
}
template<typename T>
void core (T& p)
{
clear(p);
}
template<typename T>
void middle (typename T::Index p)
{
core(p);
}
template<typename T>
void shell (T const& env)
{
typename T::Index i;
middle<T>(i);
}
This example illustrates the typical layering of software development: High-level function templates like shell() rely on components like middle(), which themselves make use of basic facilities like core(). When we instantiate shell(), all the layers below it also need to be instantiated. In this example, a problem is revealed in the deepest layer: core() is instantiated with type int (from the use of Client::Index in middle()) and attempts to dereference a value of that type, which is an error.
The error is only detectable at instantiation time. For example:
class Client
{
public:
using Index = int;
};
int main()
{
Client mainClient;
shell(mainClient);
}
A good generic diagnostic includes a trace of all the layers that led to the problems, but we observe that so much information can appear unwieldy.
An excellent discussion of the core ideas surrounding this problem can be found in [StroustrupDnE], in which Bjarne Stroustrup identifies two classes of approaches to determine earlier whether template arguments satisfy a set of constraints: through a language extension or through earlier parameter use. We cover the former option in Section 17.8 on page 361 and Appendix E. The latter alternative consists of forcing any errors in shallow instantiations. This is achieved by inserting unused code with no other purpose than to trigger an error if that code is instantiated with template arguments that do not meet the requirements of deeper levels of templates.
In our previous example, we could add code in shell() that attempts to dereference a value of type T::Index. For example:
template<typename T>
void ignore(T const&)
{
}
template<typename T>
void shell (T const& env)
{
class ShallowChecks
{
void deref(typename T::Index ptr) {
ignore(*ptr);
}
};
typename T::Index i;
middle(i);
}
If T is a type such that T::Index cannot be dereferenced, an error is now diagnosed on the local class ShallowChecks. Note that because the local class is not actually used, the added code does not impact the running time of the shell() function. Unfortunately, many compilers will warn that ShallowChecks is not used (and neither are its members). Tricks such as the use of the ignore() template can be used to inhibit such warnings, but they add to the complexity of the code.
Clearly, the development of the dummy code in our example can become as complex as the code that implements the actual functionality of the template. To control this complexity, it is natural to attempt to collect various snippets of dummy code in some sort of library. For example, such a library could contain macros that expand to code that triggers the appropriate error when a template parameter substitution violates the concept underlying that particular parameter. The most popular such library is the Concept Check Library, which is part of the Boost distribution (see [BCCL]).
Unfortunately, the technique isn’t particularly portable (the way errors are diagnosed differs considerably from one compiler to another) and sometimes masks issues that cannot be captured at a higher level.
Once we have concepts in C++ (see Appendix E), we have other ways to support the definition of requirements and expected behavior.
The assert() macro is often used in C++ code to check that some particular condition holds at a certain point within the program’s execution. If the assertion fails, the program is (noisily) halted so the programmer can fix the problem.
The C++ static_assert keyword, introduced with C++11, serves the same purpose but is evaluated at compile time: If the condition (which must be a constant expression) evaluates to false, the compiler will issue an error message. That error message will include a string (that is part of the static_assert itself) indicating to the programmer what has gone wrong. For example, the following static assertion ensures that we are compiling on a platform with 64-bit pointers:
static_assert(sizeof(void*) * CHAR_BIT == 64, "Not a 64-bit platform");
Static assertions can be used to provide useful error messages when a template argument does not satisfy the constraints of a template. For example, using the techniques described in Section 19.4 on page 416, we can create a type trait to determine whether a given type is dereferenceable:
debugging/hasderef.hpp
#include <utility> // for declval()
#include <type_traits> // for true_type and false_type
template<typename T>
class HasDereference {
private:
template<typename U> struct Identity;
template<typename U> static std::true_type
test(Identity<decltype(*std::declval<U>())>*);
template<typename U> static std::false_type
test(…);
public:
static constexpr bool value = decltype(test<T>(nullptr))::value;
};
Now, we can introduce a static assertion into shell() that provides a better diagnostic if the shell() template from the previous section is instantiated with a type that is not dereferencable:
template<typename T>
void shell (T const& env)
{
static_assert(HasDereference<T>::value, "T is not dereferenceable");
typename T::Index i;
middle(i);
}
With this change, the compiler produces a significantly more concise diagnostic indicating that the type T is not dereferenceable.
Static assertions can drastically improve the user experience when working with template libraries, by making error messages both shorter and more direct.
Note that you can also apply them to class templates and use all type traits discussed in Appendix D:
template<typename T>
class C {
static_assert(HasDereference<T>::value, "T is not dereferenceable");
static_assert(std::is_default_constructible<T>::value,
"T is not default constructible");
…
};
When writing a template, it is challenging to ensure that the template definition will compile for any template arguments that meet the specified constraints for that template. Consider a simple find() algorithm that looks for a value within an array, along with its documented constraints:
// T must be EqualityComparable, meaning:
// two objects of type T can be compared with == and the result converted to bool
template<typename T>
int find(T const* array, int n, T const& value);
We could imagine the following straightforward implementation of this function template:
template<typename T>
int find(T const* array, int n, T const& value) {
int i = 0;
while(i != n && array[i] != value)
++i;
return i;
}
There are two problems with this template definition, both of which will manifest as compilation errors when given certain template arguments that technically meet the requirements of the template yet behave slightly differently than the template author expected. We will use the notion of archetypes to test our implementation’s use of its template parameters against the requirements specified by the find() template.
Archetypes are user-defined classes that can be used as template arguments to test a template definition’s adherence to the constraints it imposes on its corresponding template parameter. An archetype is specifically crafted to satisfy the requirements of the template in the most minimal way possible, without providing any extraneous operations. If instantiation of a template definition with the archetype as its template argument succeeds, then we know that the template definition does not try to use any operations not explicitly required by the template.
For example, here is an archetype intended to meet the requirements of the EqualityComparable concept described in the documentation of our find() algorithm:
class EqualityComparableArchetype
{
};
class ConvertibleToBoolArchetype
{
public:
operator bool() const;
};
ConvertibleToBoolArchetype
operator==(EqualityComparableArchetype const&,
EqualityComparableArchetype const&);
The EqualityComparableArchetype has no member functions or data, and the only operation it provides is an overloaded operator== to satisfy the equality requirement for find(). That operator== is itself rather minimal, returning another archetype, ConvertibleToBoolArchetype, whose only defined operation is a user-defined conversion to bool.
The EqualityComparableArchetype clearly meets the stated requirements of the find() template, so we can check whether the implementation of find() held up its end of the contract by attempting to instantiate find() with EqualityComparableArchetype:
template int find(EqualityComparableArchetype const*, int,
EqualityComparableArchetype const&);
The instantiation of find<EqualityComparableArchetype> will fail, indicating that we have found our first problem: the EqualityComparable description requires only ==, but the implementation of find() relies on comparing T objects with !=. Our implementation would have worked with most user-defined types, which implement == and != as a pair, but it was actually incorrect. Archetypes are intended to find such problems early in the development of template libraries.
Altering the implementation of find() to use equality rather than inequality solves this first problem, and the find() template will successfully compile with the archetype:2
template<typename T>
int find(T const* array, int n, T const& value) {
int i = 0;
while(i != n && !(array[i] == value))
++i;
return i;
}
Uncovering the second problem in find() using archetypes requires a bit more ingenuity. Note that the new definition of find() now applies the ! operator directly to the result of ==. In the case of our archetype, this relies on the user-defined conversion to bool and the built-in logical negation operator!. A more careful implementation of ConvertibleToBoolArchetype poisons operator! so that it cannot be used improperly:
class ConvertibleToBoolArchetype
{
public:
operator bool() const;
bool operator!() = delete;// logical negation was not explicitly required
};
We could extend this archetype further, using deleted functions3 to also poison the operators && and || to help find problems in other template definitions. Typically, a template implementer will want to develop an archetype for every concept identified in the template library and then use these archetypes to test each template definition against its stated requirements.
So far, we have discussed bugs that arise when compiling or linking programs that contain templates. However, the most challenging task of ensuring that a program behaves correctly at run time often follows a successful build. Templates can sometimes make this task a little more difficult because the behavior of generic code represented by a template depends uniquely on the client of that template (certainly much more so than ordinary classes and functions). A tracer is a software device that can alleviate that aspect of debugging by detecting problems in template definitions early in the development cycle.
A tracer is a user-defined class that can be used as an argument for a template to be tested. Often, a tracer is also an archetype, written just to meet the requirements of the template. More important, however, a tracer should generate a trace of the operations that are invoked on it. This allows, for example, to verify experimentally the efficiency of algorithms as well as the sequence of operations.
Here is an example of a tracer that might be used to test a sorting algorithm:4
debugging/tracer.hpp
#include <iostream>
class SortTracer {
private:
int value; // integer value to be sorted
int generation; // generation of this tracer
inline static long n_created = 0; // number of constructor calls
inline static long n_destroyed = 0; // number of destructor calls
inline static long n_assigned = 0; // number of assignments
inline static long n_compared = 0; // number of comparisons
inline static long n_max_live = 0; // maximum of existing objects
// recompute maximum of existing objects
static void update_max_live() {
if (n_created-n_destroyed > n_max_live) {
n_max_live = n_created-n_destroyed;
}
}
public:
static long creations() {
return n_created;
}
static long destructions() {
return n_destroyed;
}
static long assignments() {
return n_assigned;
}
static long comparisons() {
return n_compared;
}
static long max_live() {
return n_max_live;
}
public:
// constructor
SortTracer (int v = 0) : value(v), generation(1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", created generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// copy constructor
SortTracer (SortTracer const& b)
: value(b.value), generation(b.generation+1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", copied as generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// destructor
~SortTracer() {
++n_destroyed;
update_max_live();
std::cerr << "SortTracer generation " << generation
<< " destroyed (total: "
<< n_created - n_destroyed << ")\n";
}
// assignment
SortTracer& operator= (SortTracer const& b) {
++n_assigned;
std::cerr << "SortTracer assignment #" << n_assigned
<< " (generation " << generation
<< " = " << b.generation
<< ")\n";
value = b.value;
return *this;
}
// comparison
friend bool operator < (SortTracer const& a,
SortTracer const& b) {
++n_compared;
std::cerr << "SortTracer comparison #" << n_compared
<< " (generation " << a.generation
<< " < " << b.generation
<< ")\n";
return a.value < b.value;
}
int val() const {
return value;
}
};
In addition to the value to sort, value, the tracer provides several members to trace an actual sort: For each object, generation traces by how many copy operations it is removed from the original. That is, an original has generation == 1, a direct copy of an original has generation == 2, a copy of a copy has generation == 3, and so on. The other static members trace the number of creations (constructor calls), destructions, assignment comparisons, and the maximum number of objects that ever existed.
This particular tracer allows us to track the pattern of entity creation and destruction as well as assignments and comparisons performed by a given template. The following test program illustrates this for the std::sort() algorithm of the C++ standard library:
debugging/tracertest.cpp
#include <iostream>
#include <algorithm>
#include "tracer.hpp"
int main()
{
// prepare sample input:
SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };
// print initial values:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ’ ’;
}
std::cerr << ’\n’;
// remember initial conditions:
long created_at_start = SortTracer::creations();
long max_live_at_start = SortTracer::max_live();
long assigned_at_start = SortTracer::assignments();
long compared_at_start = SortTracer::comparisons();
// execute algorithm:
std::cerr << "---[ Start std::sort() ]--------------------\n";
std::sort<>(&input[0], &input[9]+1);
std::cerr << "---[ End std::sort() ]----------------------\n";
// verify result:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ’ ’;
}
std::cerr << "\n\n";
// final report:
std::cerr << "std::sort() of 10 SortTracer’s"
<< " was performed by:\n "
<< SortTracer::creations() - created_at_start
<< " temporary tracers\n "
<< "up to "
<< SortTracer::max_live()
<< " tracers at the same time ("
<< max_live_at_start << " before)\n "
<< SortTracer::assignments() - assigned_at_start
<< " assignments\n "
<< SortTracer::comparisons() - compared_at_start
<< " comparisons\n\n";
}
Running this program creates a considerable amount of output, but much can be concluded from the final report. For one implementation of the std::sort() function, we find the following:
std::sort() of 10 SortTracer’s was performed by:
9 temporary tracers
up to 11 tracers at the same time (10 before)
33 assignments
27 comparisons
For example, we see that although nine temporary tracers were created in our program while sorting, at most two additional tracers existed at any one time.
Our tracer thus fulfills two roles: It proves that the standard sort() algorithm requires no more functionality than our tracer (e.g., operators == and > were not needed), and it gives us a sense of the cost of the algorithm. It does not, however, reveal much about the correctness of the sorting template.
Tracers are relatively simple and effective, but they allow us to trace the execution of templates only for specific input data and for a specific behavior of its related functionality. We may wonder, for example, what conditions must be met by the comparison operator for the sorting algorithm to be meaningful (or correct), but in our example, we have only tested a comparison operator that behaves exactly like less-than for integers.
An extension of tracers is known in some circles as oracles (or run-time analysis oracles). They are tracers that are connected to an inference engine—a program that can remember assertions and reasons about them to infer certain conclusions.
Oracles allow us, in some cases, to verify template algorithms dynamically without fully specifying the substituting template arguments (the oracles are the arguments) or the input data (the inference engine may request some sort of input assumption when it gets stuck). However, the complexity of the algorithms that can be analyzed in this way is still modest (because of the limitations of the inference engines), and the amount of work is considerable. For these reasons, we do not delve into the development of oracles, but the interested reader should examine the publication mentioned in the afternotes (and the references contained therein).
A fairly systematic attempt to improve C++ compiler diagnostics by adding dummy code in high-level templates can be found in Jeremy Siek’s Concept Check Library (see [BCCL]). It is part of the Boost library (see [Boost]).
Robert Klarer and John Maddock proposed the static_assert feature to help programmers check conditions at compile time. It was among the earliest features added to what would later become C++11. Prior to that, it was commonly expressed as a library or macro using techniques similar to those described in Section 28.1 on page 652. The Boost.StaticAssert library is one such implementation.
The MELAS system provided oracles for certain parts of the C++ standard library, allowing verification of some of its algorithms. This system is discussed in [MusserWangDynaVeri].5
1 And if you’ve made it this far in the book, no doubt you’ve encountered error messages that make that initial example look tame!
2 The program will compile but it will not link, because we never defined the overloaded operator==. That’s typical for archetypes, which are generally meant only as compile-time checking aids.
3 Deleted functions are functions that participate in overload resolution as normal functions. If they are selected by overload resolution, however, the compiler produces an error.
4 Before C++17, we had to initialize the static members outside the class declaration in one translation unit.
5 One author, David Musser, was also a key figure in the development of the C++ standard library. Among other things, he designed and implemented the first associative containers.