debugging c++ templates

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 section 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. Concepts can form hierarchies in the sense that one concept can be a refinement of another. The more refined concept includes all the constraints of the other concept but adds a few more. For example, the concept random access iterator refines the concept bidirectional iterator in the C++ standard library. 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.

Decoding the Error Novel

Ordinary compilation errors are normally quite succinct and to the point. For example, when a compiler says "class X has no member 'fun'," it usually isn't too hard to figure out what is wrong in our code (for example, we might have mistyped run as fun). Not so with templates. Consider the following relatively simple code excerpt using the C++ standard library. It contains a fairly small mistake: list<string> is used, but we are searching using a greater<int> function object, which should have been a greater<string> object:

std::list<std::string> coll; 

std::list<std::string> coll; … // Find the first element greater than "A" std::list<std::string>::iterator pos; pos = std::find_if(coll.begin(),coll.end(), // range std::bind2nd(std::greater<int>(),"A")); // criterion

This sort of mistake commonly happens when cutting and pasting some code and forgetting to adapt parts of it.

A version of the popular GNU C++ compiler reports the following error:

/local/include/stl/_algo.h: In function 'struct _STL::_List_iterator<_STL::basic 
_string<char,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Nonconst_tra 
its<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > > > 
_STL::find_if<_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<cha 
r>,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL:: 
char_traits<char>,_STL::allocator<char> > > >, _STL::binder2nd<_STL::greater<int 
> > >(_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char>,_STL: 
:allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_tra 
its<char>,_STL::allocator<char> > > >, _STL::_List_iterator<_STL::basic_string<c 
har,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL: 
:basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > > >, _STL::bi 
nder2nd<_STL::greater<int> >, _STL::input_iterator_tag)': 
/local/include/stl/_algo.h:115:   instantiated from '_STL::find_if<_STL::_List_i 
terator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> >, 
_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::all 
ocator<char> > > >, _STL::binder2nd<_STL::greater<int> > >(_STL::_List_iterator< 
_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_N 
onconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<c 
har> > > >, _STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char> 
,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::ch 
ar_traits<char>,_STL::allocator<char> > > >, _STL::binder2nd<_STL::greater<int> 
>)' 
testprog.cpp:18:   instantiated from here 
/local/include/stl/_algo.h:78: no match for call to '(_STL::binder2nd<_STL::grea 
ter<int> >) (_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<cha 
r> > &)' 
/local/include/stl/_function.h:261: candidates are: bool _STL::binder2nd<_STL::g 
reater<int> >::operator ()(const int &) const 

A message like this starts looking more like a novel than a diagnostic. It can also be overwhelming to the point of discouraging novice template users. However, with some practice, messages like this become manageable, and the errors are relatively easily located.

The first part of this error message says that an error occurred in a function template instance (with a horribly long name) deep inside the /local/include/stl/_algo.h header. Next, the compiler reports why it instantiated that particular instance. In this case it all started on line 18 of testprog.cpp (which is the file containing our example code), which caused the instantiation of a find_if template on line 115 of the _algo.h header. The compiler reports all this in case we simply were not expecting all these templates to be instantiated. It allows us to determine the chain of events that caused the instantiations.

However, in our example we're willing to believe that all kinds of templates needed to be instantiated, and we just wonder why it didn't work. This information comes in the last part of the message: The part that says "no match for call" implies that a function call could not be resolved because the types of the arguments and the parameter types didn't match. Furthermore, just after this, the line containing "candidates are" explains that there was a single candidate type expecting an integer type (parameter type const int&). Looking back at line 18 of the program, we see std::bind2nd(std::greater<int>(),"A"), which does indeed contain an integer type (<int>) that is not compatible with the string type objects for which we're looking in our example. Replacing <int> with <std::string> makes the problem go away.

There is no doubt that the error message could be better structured. The actual problem could be omitted before the history of the instantiation, and instead of using fully expanded template instantiation names like MyTemplate<YourTemplate<int> >, decomposing the instance as in MyTemplate<T> with T=YourTemplate<int> can reduce the overwhelming length of names. However, it is also true that all the information in this diagnostic could be useful in some situations. It is therefore not surprising that other compilers provide similar information (although some use the structuring techniques mentioned).

Shallow Instantiation

Diagnostics such as those discussed earlier arise when errors are found after a long chain of instantiations. To illustrate this, consider the following somewhat contrived code:

template <typename T> void clear (T const& p) { *p=0; // assumes T is a pointer-like type } template <typename T> void core (T const& 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); } class Client { public: typedef int Index; }; Client main_client; int main() { shell(main_client); }

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. 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. 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> inline void ignore(T const&) { } template <typename T> void shell (T const& env) { class ShallowChecks { void deref(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 about the fact 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.

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.

Long Symbols

There is an another problem of templates: Instantiated template code can result in very long symbols. For example, in the implementation used earlier std::string is expanded to

_STL::basic_string<char,_STL::char_traits<char>, _STL::allocator<char> >

Some programs that use the C++ standard library produce symbols that contain more than 10,000 characters. These very long symbols can also cause errors or warnings in compilers, linkers, and debuggers. Modern compilers use compression techniques to reduce this problem, but in error messages this is not apparent.

Tracers

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, it is written just to meet the requirements of the template and no more than those requirements. 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:

// basics/tracer.hpp #include <iostream> class SortTracer { private: int value; // integer value to be sorted int generation; // generation of this tracer static long n_created; // number of constructor calls static long n_destroyed; // number of destructor calls static long n_assigned; // number of assignments static long n_compared; // number of comparisons static long n_max_live; // 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 (intv=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: generation traces for each object how many copies it is from the original. The other static members trace the number of creations (constructor calls), destructions, assignment comparisons, and the maximum number of objects that ever existed.

The static members are defined in a separate dot-C file:

// basics/tracer.cpp #include "tracer.hpp" long SortTracer::n_created = 0; long SortTracer::n_destroyed = 0; long SortTracer::n_max_live = 0; long SortTracer::n_assigned = 0; long SortTracer::n_compared = 0;

This particular tracer allows us to track the pattern or 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:

// basics/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 << std::endl; // 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: 15 temporary tracers up to 12 tracers at the same time (10 before) 33 assignments 27 comparisons

For example, we see that although 15 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 (for example, 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.

Oracles

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 a so-called inference engine—a program that can remember assertions and reasons about them to infer certain conclusions. One such system that was applied to certain parts of a standard library implementation is called MELAS and is discussed in [MusserWangDynaVeri].

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.

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 earlier (and the references contained therein).

Archetypes

We mentioned earlier that tracers often provide an interface that is the minimal requirement of the template they trace. When such a minimal tracer does not generate run-time output, it is sometimes called an archetype. An archetype allows us to verify that a template implementation does not require more syntactic constraints than intended. Typically, a template implementer will want to develop an archetype for every concept identified in the template library.

-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

• Complete Tutorial of C++ Template's
• Standard Template Library Tutorial
• Inter Process Communication Tutorial
• Advance Programming in C & C++

-----------------------------------------------------------------

The Art of Learning with Innovation,
eLearning Courses for C and C++ Programming Language - The Most appreciated course !!!

Copyright © ccplusplus.com