Embedded Alchemy

Alchemy Send feedback »

Alchemy is a collection of independent library components that specifically relate to efficient low-level constructs used with embedded and network programming.

The latest version of Embedded Alchemy[^] can be found on GitHub.
The most recent entries as well as Alchemy topics to be posted soon:
  • Steganography[^]
  • Coming Soon: Alchemy: Data View
  • Coming Soon: Quad (Copter) of the Damned
Alchemy: Documentation[^]

Alchemy: Typelist Operations

CodeProject, C++, Alchemy, design Send feedback »

This is an entry for the continuing series of blog entries that documents the design and implementation process of a library. This library is called, Network Alchemy[^]. Alchemy performs data serialization and it is written in C++.

I discussed the Typelist with greater detail in my previous post. However, up to this point I haven't demonstrated any practical uses for the Typelist. In this entry, I will further develop operations for use with the Typelist. In order to implement the final operations in this entry, I will need to rely on, and apply the operations that are developed at the beginning in order to create a simple and elegant solution.

Useful Operations

The operations I implemented in the previous entry were fundamental operations that closely mimic the same operations you would find on a traditional runtime linked-list. More sophisticated operations could be composed from those basic commands, however, the work would be tedious, and much of the resulting syntax would be clumsy for the end user. These are two things that I am trying to avoid in order to create a maintainable library. I will approach the implementation of these operations with a different tack, focused on ease of use and maintenance.

We need operations to navigate the data format definitions defined in Alchemy. My goal is to be able to iterate through all of the data fields specified in a network packet format, and appropriately process the data at each location in the packet. This includes identifying the offset of a field in the packet, performing the proper action for a field entry, and also performing static-checks on the types used in the API. There are the operations that I believe I will need:

  • Length: The number of type entries in the list.
  • TypeAt: The defined type at a specified index.
  • SizeAt: The sizeof of type at a specified index.
  • OffsetOf: The byte offset of the type at a specified index.
  • SizeOf: The total size in bytes for all of the types specified in the list.

This list of operations should give me the functionality that I need to programmatically iterate through the well defined fields of a message packet structure. I have already demonstrated the implementation for Length[^]. That leaves four new operations to implement. As you will see, we will use some of these new operations as blocks to build other more complex operations. This is especially important in the functional programming environment that we are working within.

Style / Guidelines

I have a few remarks before I continue. It is legal to use integral types in parameterized-type declarations such as size_t, however floating-point values, string literals, and pointers are not legal syntax. struct types are typically used when creating meta-functions because they use public-scope by default, and this saves a small amount of verbosity in the code definitions.

The keyword typename and class are interchangeable in template parameter declarations. As a matter of preference I choose typename to emphasize that the required type need not be a class-type. Finally, it is legal to provide default template values using the same rules for default function parameters; all of the parameters after an entry with a default type must also have default values. However, this can only be used for class and struct templates, but not for function templates.

TypeAt

Traditionally nodes in linked-lists are accessed by iterating through the list until the desired node is found, which makes this a linear operation, O(n). Something to keep in mind when meta-programming is many times operations will reduce to constant runtime, O(1). However, the traditional linked-list iteration method required to traverse the Typelist is inconveniently verbose and will still require O(n) compile-time operations. The code below demonstrates the explicit extraction of the three types for our example Typelist.

C++

// This syntax is required to access the three types:
integral_t::type::head_t                   charVal  = 0;
integral_t::type::tail_t::head_t           shortVal = 0;
integral_t::type::tail_t::tail_t::head_t   longVal  = 0;

Because the message definitions in Alchemy may have 20-30 type entries I want to create access methods that rely on node index rather than explicit initialization. The underlying implementation will be basically the same as a linked-list iteration. However, because the compiler will reduce most of these operations to O(1) time, we will not pay the run-time cost of providing random access to a sequential construct.

If you are worried about creating an enormous increase in your compile times, stop worrying, for now at least. Compilers have become very efficient at instantiating templates, and remembering what has already been generated. If a recursive access of the 25th node has been generated, then later access to the 26th node must be generated, modern compilers will detect they have already generated up to the 25th node. Therefore, only one new instantiation is generated to reach the 26th element. Unfortunately, this cost must be paid for each compilation unit that these templates are instantiated. There is no need to pre-maturely optimize your template structures until you determine the templates have become a problem.

The first step is to define the function signature for TypeAt. This code is called a template declaration, the definition has not been provided yet.

C++

/// Return the type at the specified index
template < size_t IdxT,
           typename ContainerT,
           typename ErrorT = error::Undefined_Type >
struct Type At;

Generic Definition

We will provide a catch-all generic definition that simply declares the specified Error Type. This is the instance that will be generated for any instance of TypeAt defined with the ContainerT parameter that does not have a defined specialization:

C++

/// Return the type at the specified index
template < size_t IdxT,
           typename ContainerT,
           typename ErrorT = error::Undefined_Type >
struct TypeAt
{
  typedef ErrorT               type;
};

The Final Piece

The first step is to determine what the correct implementation would look like for a type at a specified index. This code shows what the usage would look like to access the third element in our integral_t Typelist TypeAt < 2, integral_t >::type It's important to remember that integral_t is actually a typedef for the template instantiation with our defined types. Also, initially there will be 32 available entries in the Typelist definition for an Alchemy message.

The definition of our Typelist contains every type in the index that it is defined. Rather than writing a recursive loop and terminator to count and extract the correct type, we can refer to the indexed type directly. The only catch, is that this method of implementation will require a template definition for each possible index. Therefore, the actual template definition for this operation must be defined like this:

C++

template
&lt; typename
   TypeList
   &lt; typename T0,  typename T1,  typename T2,  typename T3,
     typename T4,  typename T5,  typename T6,  typename T7,
     typename T8,  typename T9,  typename T10, typename T11,
     typename T12, typename T13, typename T14, typename T15,
     typename T16, typename T17, typename T18, typename T19,
     typename T20, typename T21, typename T22, typename T23,
     typename T24, typename T25, typename T26, typename T27,
     typename T28, typename T29, typename T30, typename T31
   >,
   typename ErrorT = error::Undefined_Type
>
struct TypeAt
  &lt; (2),
    TypeList &lt; T0,  T1,  T2,  T3,  T4,  T5,  T6,  T7,
               T8,  T9,  T10, T11, T12, T13, T14, T15,
               T16, T17, T18, T19, T20, T21, T22, T23,
               T24, T25, T26, T27, T28, T29, T30, T31
             >
  >
{
  typedef T2 type;
};

After I reached this implementation I decided that I had to find a simpler solution. To implement the final piece of the TypeAt operation, we will rely on MACRO code generation[^]. The work will still be minimal with the MACROs that I introduced earlier. This is the MACRO that will define the template instance for each index.

// TypeAt Declaration MACRO
#define tmp_ALCHEMY_TYPELIST_AT(I)                 \
template < TMP_ARRAY_32(typename T),               \
          typename ErrorT >                        \
struct TypeAt< (I),                                \
               TypeList< TMP_ARRAY_32(T) >,        \
               ErrorT                              \
             >                                     \
{                                                  \
  typedef TypeList < TMP_ARRAY_32(T) >  container; \
  typedef T##I                        type;        \
}

The declaration of the MACRO in this way will define the entire structure above: tmp_ALCHEMY_TYPELIST_AT(2);

Therefore, I declare an instance of this MACRO for as many indices are allowed in the Typelist.

C++

//  MACRO Declarations for each ENTRY
//  that is supported for the TypeList size
tmp_ALCHEMY_TYPELIST_AT(0);
tmp_ALCHEMY_TYPELIST_AT(1);
tmp_ALCHEMY_TYPELIST_AT(2);
tmp_ALCHEMY_TYPELIST_AT(3);
// ...
tmp_ALCHEMY_TYPELIST_AT(30);
tmp_ALCHEMY_TYPELIST_AT(31);
 
//  Undefining the MACRO to prevent its further use.
#undef tmp_ALCHEMY_TYPELIST_AT

Boost has libraries that are implemented in similar ways, however, they have expanded their code to actually have MACROs define each code generation MACRO at compile-time based on a constant. I have simply hand defined each instance because I have not created as sophisticated of a pre-processor library as Boost has. Also, at the moment, my library is a small special purpose library. If it becomes more generic with wide-spread use, it would probably be worth the effort to make the adjustment to a dynamic definition.

SizeOf

Although there already exists a built-in operator to report the size of a type, we will need to acquire the size of a nested structure. We are representing structure formats with a Typelist, which does not actually contain any data. Therefore we will create a sizeof operation that can report both the size of an intrinsic type, as well as a Typelist. We could take the same approach as TypeAt with MACROs to generate templates for each sized Typelist, and a generic version for intrinsic types. However, if we slightly alter the definition of our Typelist definition, we can implement this operation with a few simple templates.

Type-traits

We will now introduce the concept of type-traits[^] into our implementation of the Typelist to help us differentiate the different types of objects and containers that we create. This is as simple as creating a new type.
struct container_trait{};
Now derive the Typelist template from container_trait. The example below is from an expansion of the 3 node declaration for our Typelist:

C++

template&lt; typename T0,  typename T1,  typename T2>
struct TypeList&lt; T0,  T1,  T2>
  : container_trait
{
  typedef TypeNode&lt; T1,
          TypeNode&lt; T2,
          TypeNode&lt; T3, empty>
        > >                          type;
};

We now need a way to be able to discriminate between container_trait types and all other types. We will make use of one of the type templates found in the < type_traits > header file, is_base_of. This template creates a Boolean value set to true if the type passed in derives from the specified base class.

C++

//  Objects derived from the container_trait
//  are considered type containers.
template &lt; typename T >
struct type_container
  : std::integral_constant
      &lt; bool, std::is_base_of&lt; container_trait, T >::value >
{  };

This type discriminator can be used to discern and call the correct implementation for our implementation of sizeof.

C++

template &lt; typename T >
struct SizeOf
  : detail::SizeOf_Impl
    &lt; T,
     type_container&lt; T >::value
    >
{ };

That leaves two distinct meta-functions to implement. One that will calculate the size of container_types, and the other to report the size for all other types. I have adopted a style that Boost uses in its library implementations, which is to enclose helper constructs in a nested namespace called detail. This is a good way to notify a user of your library that the following contents are implementation details since these constructs cannot be hidden out of sight.

C++

namespace detail
{
 
// Parameterized implementation of SizeOf
template &lt; typename T, bool isContainer = false >
struct SizeOf_Impl
  : std::integral_constant&lt; size_t, sizeof(T) >
{ };
 
// SizeOf implementation for type_containers
template &lt; typename T>
struct SizeOf_Impl&lt; T, true >
  : std::integral_constant&lt; size_t,
                            ContainerSize&lt; T >::value
                          >
{ };
 
} // namespace detail

The generic implementation of this template simply uses the built-in sizeof operator to report the size of type T. The container_trait specialization calls another template meta-function to calculate the size of the Typelist container. I will have to wait and show you that after a few more of our operations are implemented.

SizeAt

The implementation for SizeAt builds upon both the TypeAt and sizeof implementations. The implementation also returns to the use of MACRO code generation to reduce the verbosity of the definitions. This implementation queries for the type at the specified index, then uses sizeof to record the size of the type. Here is the MACRO that will be used to define the template for each index:

// SizeOf Declaration MACRO
#define tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(I)                   \
template < TMP_ARRAY_32(typename T) >                          \
struct SizeAt< (I), TypeList< TMP_ARRAY_32(T) > >              \
{                                                              \
  typedef TypeList< TMP_ARRAY_32(T) >  Container;              \
  typedef typename TypeAt< (I), Container >::type TypeAtIndex; \
  enum { value = SizeOf< TypeAtIndex >::value };               \
}

Once again, there is a set of explicit MACRO declarations that have been made to define each instance of this meta-function.

C++

// MACRO Declarations for each ENTRY that is supported for the TypeList  size **
tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(0);
tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(1);
tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(2);
// ...
tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(30);
tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY(31);
 
// Undefining the declaration MACRO
// to prevent its further use.
#undef tmp_ALCHEMY_TYPELIST_SIZEOF_ENTRY

OffsetOf

Now we're picking up steam. In order to calculate the offset of an item in a Typelist, we must start from the beginning, and calculate the sum of all of the previous entries combined. This will require a recursive solution to perform the iteration, as well as the three operations that we have implemented up to this point. Here's the prototype for this meta-function:

C++

//  Forward Declaration
template &lt; size_t Index,
           typename ContainerT >
struct OffsetOf;

If you have noticed that I do not always provide a forward declaration, it is because it usually depends on if my general implementation will be the first instance encountered by the compiler, dependencies, or if I have a specialization that I would like to put in place. In this case, I am going to implement a specialization for the offset of index zero; the offset will always be zero. This specialization will also act as the terminator for the recursive calculation.

C++

/// The item at index 0 will always have an offset of 0.
template &lt; typename ContainerT >
struct OffsetOf&lt; 0, ContainerT >
{
  enum { value = 0 };
};

One of the nasty problems to tackle when writing template meta-programs, is that debugging your code becomes very difficult. The reason being, many times by the time you are actually able to see what is generated, the compiler has reduced your code to a single number. Therefore, I like to try and write a traditional function that performs a similar calculation, then convert it to a template. Pretty much the same as if I were trying to convert a class into a parameterized object. This is essentially the logic we will need to calculate the byte offset of an entry from a Typelist definition.

C++

// An array of values to stand-in
// for the Typelist.
size_t elts[] = {1,2,3,4,5,6};
 
size_t OffsetOf(size_t index)
{
  return OffsetOf(index - 1)
       + sizeof(elts[index-1]);
};

This code adds the size of the item before the requested item, to its offset to calculate the offset if the requested item. In order to get the offset of the previous item, it recursively performs this action until index 0 is reached, which will terminate the recursion. This is what the OffsetOf function looks like once it is converted to the template and code-generating MACRO.

// OffsetOf Declaration MACRO
#define tmp_ALCHEMY_TYPELIST_OFFSETOF(I)                  \
template < TMP_ARRAY_32(typename T) >                     \
struct OffsetOf< (I), TypeList< TMP_ARRAY_32(T) > >       \
{                                                         \
  typedef TypeList< TMP_ARRAY_32(T) >   container;        \
                                                          \
  enum { value = OffsetOf< (I)-1, container >::value      \
               + SizeAt  < (I)-1, container >::value };   \
}

This operation also requires the series of MACRO declarations to properly define the template for every index. However, this time we do not define an entry for index 0 since we explicitly implemented a specialization for it.

C++

//  Offset for zero is handled as a special case above
tmp_ALCHEMY_TYPELIST_OFFSETOF(1);
tmp_ALCHEMY_TYPELIST_OFFSETOF(2);
// ...
tmp_ALCHEMY_TYPELIST_OFFSETOF(31);
 
//  Undefining the declaration MACRO to prevent its further use.
#undef tmp_ALCHEMY_TYPELIST_OFFSETOF

ContainerSize

Only one operation remains. This operation is one that we had to put aside until we completed more of the operations for the Typelist. The purpose of ContainerSize is to calculate the size of an entire Typelist. This will be very important to be able to support nested data structures. Here is the implementation:

C++

template &lt; typename T >
struct ContainerSize
  : type_check&lt; type_container&lt; ContainerT >::value >
  , std::integral_constant
    &lt; size_t,
      OffsetOf&lt; Hg::length&lt; T >::value, T >::value
    >
{ };

I will give you a moment to wrap your head around this.

The first think that I do is verify that the type T that is passed into this template is in fact a type container, the Typelist. type_check is a simple template declaration that verifies the input predicate evaluates to true. There is no implementation for any other type, which will trigger a compiler error. In the actual source I have comments that indicate what would cause an error related to type_check and how to resolve it.

Next, the implementation is extremely simple. A value is defined to equal the offset at the item one passed the last item defined in the Typelist. This behaves very much like end interators in STL. It is ok to refer to the element passed the end of the list, as long as it is not dereferenced for a value. The last item will not be dereferenced by OffsetOf because it refers to the specified index minus one.

Summary

This covers just about all of the work that is required of the Typelist for Alchemy. At this point I have a type container that I can navigate its set of types in order, determine their size and offset in bytes, and I can even support nested Typelists with these operations.

What is the next step? I will need to investigate how I want to internally represent data, provide access with value semantics to the user in an efficient manner. I will also be posting on more abstract concepts that will be important to understand as we get deeper into the implementation of Alchemy, such as SFINAE and ADL lookup for templates.

Typelist Operations

CodeProject, C++, maintainability, Alchemy, design Send feedback »

I would like to devote this entry to further discuss the Typelist data type. Previously, I explored the Typelist[^] for use in my network library, Alchemy[^]. I decided that it would be a better construct for managing type info than the std::tuple. The primary reason is the is no data associated with the types placed within the. On the other hand, std::tuple manages data values internally, similar to std::pair. However, this extra storage would cause some challenging conflicts for problems that we will be solving in the near future. I would not have foreseen this, had I not already created an initial version of this library as a proof of concept. I will be sure to elaborate more on this topic when it becomes more relevant.

Linked-Lists

Linked lists are one of the fundamental data structures used through-out computer science. After the fixed-size array, the linked-list is probably the simplest data structure to implement. The Typelist is a good structure to study if you are trying to learn C++ template meta-programming. While the solutions are built in completely different ways, the structure, operations and concepts are quite similar between the two.

Any class or structure can be converted to a node in a linked list by adding a member pointer to your class, typically called next or tail, to refer to the next item in the list. Generally this is not the most effective implementation, however, it is common, simple, and fits very nicely with the concepts I am trying to convey. Here is an example C struture that we will use as a basis for comparison while we develop a complete set of operations for the Typelist meta-construct:

C++

// An integer holder
struct integer
{
  long   value;
};

This structure can become a node in a linked-list by adding a single pointer to a structure of the same type:

C++

// A Node in a list of integers
struct integer
{
  long     value;
  integer *pNext;
};

Given a pointer to the first node in the list called, head, each of the remaining nodes in the list can be accessed by traversing the pNext pointer. The last node in the list should set its pNext member to 0 to indicate the end of the list. Here is an example of a loop that prints out the value of every point node in a list:

C++

void PrintValues (integer *pHead)
{
  integer *pCur = pHead;
  while (pCur)
  {
    printf("Value: %d\n", pCur->value);
    pCur = pCur->pNext;
  }
}

This function is considered to be written with an imperative style because of pCur state variable that is updated with each pass through the loop. Recall that template meta-programming does not allow mutable state; therefore, meta-programs must rely on functional programming techniques to solve problems. Let's modify the C function above to eliminate the use of mutable state. This can be accomplished with recursion.

C++

void PrintValues (integer *pHead)
{
  if (pHead)
  {
    printf("Value: %d\n", pHead->value);
    PrintValues(pHead->pNext);
  }
}

This last function makes a single test for the validity of the input parameter, then performs the print operation. Afterwards it will call itself recursively for the next node in the list. When the last node is reached, the input test will fail, and the function will exit with no further actions. Since that is the last operation in the function, each instance of the call will pop off of the call stack until the stack frame the call originated from is reached. Incidentally, this type of recursion is called tail recursion. As we saw earlier, this form of recursion can easily be written as a loop in imperative style programs.

Typelists

Let's turn our focus to the main topic now, Typelists. Keep in mind that the goal of using a construct like a Typelist is to manage and process type information at compile-time, rather than process data at run-time. Here is the node definition I presented in a previous post to build up a Typelist with templates:

C++

template &lt; typename T, typename U >
struct Typenode
{
  typedef T        head_t;
  typedef U        tail_t;
};
 
// Here is a sample declaration of a Typelist.
// Refer to my previous blog entry on
// Typelists for the details.
typedef Typelist &lt; char, short, long >    integral_t;
 
// This syntax is required to access the type, long:
integral_t::type::tail_t::tail_t::head_t   longVal = 0;

Object Structure

The concepts and ideas in computer science are very abstract. Even when code is presented, it is merely a representation of an abstract concept in some cryptic combination of symbols. It may be helpful to create a visualization of the structure of the objects that we are dealing with. Figure 1 illustrates the nested structure that is used to construct the Typelist we have just defined:

Another way to relate this purely conceptual type defined with templates, is to define the same structure without the use of templates. Here is the definition of the Typelist above defined using C++ without templates:

C++

struct integral_t
{
  typedef struct type
  {
    typedef char   head_t;
    typedef struct tail_t
    {
      typedef short  head_t;
      typedef struct tail_t
      {
        typedef long    head_t;
        typedef empty_t tail_t;
      };
    };
  };
};

This image depicts the nested structure of this Typelist definition.

Figure 1. Non-template Typelist Structure

There is one final definition that I think will be helpful to demonstrate the similarities shared between the structures of the linked-list and the Typelist. It may be useful to think about how you would solve a problem with the nested linked-list definition when trying to compose a solution for the templated Typelist. Imagine what the structure of the linked-list would look like if the definition for the next node in the list was defined in place, inside of the current Integer holder rather than a pointer. We will replace the zero-pointer terminator with a static constant that indicates if the node is the last node. Finally, I have also changed the names of the fields from value to head and next to tail. Here is the definition required for a 3-entry list.

C++

// A 3-node integer list
struct integer
{
  long   head;
  struct integer
  {
    long   head;
    struct integer
    {
      long   head;
      static const bool k_isLast = true;
    } tail;
    static const bool k_isLast = false;
  } tail;
  static const bool k_isLast = false;
};

Here is an illustration for the structure of this statically defined linked-list.

Figure 2. Statically defined Linked-List

Take note of the consequences of the last change in structure that we made to the linked-list implementation. It is no longer a dynamic structure. It is now a static definition that is fixed in structure and content once it is compiled. Each nested node does contain a value that can be modified, unlike the Typelist. However, in all other aspects, these are two similar constructs. Hopefully these alternative definitions can help you gain a better grasp of the abstract structures we are working with as we work to create useful operations for these structures.

Basic Operations

Let's run through building a few operations for the Typelist that are similar to operations that are commonly used with a linked-list. The structure of the Typelist that we have defined really only leaves one useful goal for us to accomplish, to access the data type defined inside of a specific node. This is more complicated than it sounds because we have to adhere to the strict rules of functional programming; ie. No mutable state or programming side-effects.

Error Type

Before we continue, it might be useful to define a type that can represent an error has occurred in our meta-program. This will be useful because the Error Type will appear in the compiler error message. This could help us more easily deduce the cause of the problem based on the Error Type reported in the message. We will simply define a few new types, and we can add to this list as necessary:

C++

namespace error
{
  struct Undefined_Type;
  struct Invalid_Type_Size;
}

The type definitions do not need to be complete definitions because they are never intended to be instantiated. Remember, type declarations are the mechanism we use to define constants and values in meta-programming.

Syntactic Sugar

I wrote my previous entry on using the preprocessor for code generation[^]. I demonstrated how to use the preprocessor to simplify declarations for some of the verbose Typelist definitions that we have had to use up to this point. I make use of these MACROs to provide a syntactic sugar for the definition of some of the implementations below. For example, the regular form of a Typelist declaration looks like this:

C++

template &lt; T0 , T1 , T2 , T3 , T4 , T5 , T6 , T7 ,
           T8 , T9 , T10, T11, T12, T13, T14, T15,
           T16, T17, T18, T19, T20, T21, T22, T23,
           T24, T25, T26, T27, T28, T29, T30, T31>

The previous declaration can be shortened to the following form with the code-generation MACRO:template < TMP_ARRAY_31(typename T) > There will be an additional specialization defined for many of the function implementations below that match this format. That is because this form of the definition is the outer wrapper that contains the internally defined TypeNode. All of the implementations below are developed to work upon the TypeNode. If we did not provide this syntactic sugar, a different implementation of each operation would be required for each Typelist of a different size. For 32 nodes, that would require 32 separate implementations.

Length

I showed the implementation for the Length operation in the blog entry that I introduced the Typelist. Here is a link to that implementation for you to review Length[^]. With the Length operation we now have our first meta-function to extract information from the Typelist. Here is what a call to Length looks like:

C++

// Calls the meta-function Length
// to get the number of items in integral_t.
size_t count = Length &lt; integral_t >::value;
 
// count now equals 3

front

Because of the nested structure used to build up the Typelist, accessing the type of the first node will be imperative for us to be able to move on to more complex tasks. There are two fields in each Typenode, the head_t, the current type, and tail_t, the remainder of the list. The name the C++ standard uses to access the first element in a container is, front. Therefore, that is what we will name our meta-function.

The implementation of front is probably the simplest function that we will encounter. There are only two possibilities when we go to access the head_t type in a node; 1) it will contain a type, 2) it will contain empty. Furthermore, the first node is always guaranteed to exist. To implement front, a general template definition will be required, as well as a specialization to account for the empty type.

C++

/// General Implementation
template &lt; TMP_ARRAY_32(typename T) >
struct front &lt; Typelist &lt; TMP_ARRAY_32(T) > >
{
  // The type of the first node in the Typelist.
  typedef T0 type;
};

Here is the specialization definition to handle the empty case:

C++

template &lt; >
struct front &lt; empty >
{ };

Why is there not a definition for the type within the empty specialization? That is because the type of code that we are developing will all be resolved at compile-time. A compiler error will be generated if front < empty > ::type is accessed, because it's invalid. However, if we had defined a type definition for the empty specialization, we would need to then write code to detect this case at run-time. Detecting potential errors at compile-time eliminates unnecessary run-time checks that would add extra processing. The final result is that we are detecting programming logic errors in our code, and the use of our code, by making the logic-errors invalid syntax.

back

Just as we were able to access the first element in the list, we can extract the type from the last node. This is also relatively simple since we have already implemented a method to count the length of the Typelist.

C++

/// This allows the last type of the list to be returned.
template &lt; TMP_ARRAY_32(typename T) >
struct back &lt; TypeList &lt; TMP_ARRAY_32(T) > >
{
  typedef
    TypeList &lt; TMP_ARRAY_32(T) >  container;
  typedef
    TypeAt &lt; length &lt; container >::value-1,
             container
           >                      type;
};
 
// This is the specialization for the empty node.
template &lt; >
struct back &lt; empty >
{ };

pop_front

To navigate through the rest of the list we will need to dismantle it node-by-node. The simplest way to accomplish this is to remove the front node until we reach the desired node. A new Typelist is created from the tail of the current Typelist node as a result of the pop_front operation. Because the meta-functions are built from templates, this new Type list will be completely compatible with all of the operations that we develop for this type. Here is the forward-declaration of the meta-function:

C++

template &lt; typename ContainerT >
struct pop_front;

Up to this point, the meta-functions that we have developed only extracted a single type. The implementation for pop_front differs slightly in structure from the other templates that we have created up to this point. Remember that a new Typelist must be defined as the result. In order to do this, the instantiation of a new Typelist type must be defined within our meta-function definition. The primary implementation is actually a specialization of the template definition that we forward declared.


C++

template &lt; typename TPop, TMP_ARRAY_31(typename T) >
struct pop_front &lt; TypeList &lt; TPop, TMP_ARRAY_31(T) > >
{
  typedef TypeList &lt; TMP_ARRAY_31(T) > type;
};
 
template &lt; typename T1, typename T2 >
struct pop_front &lt; TypeNode &lt; T1, T2 > >
{
  typedef T2 type;
};

I realize that there are two template parameters in this implementation, as opposed to the single type parameter in the forward declaration. I believe this is perplexing for two reasons


1. Why is there a second parameter?


Our ultimate goal is to decompose a single node into it's two parts, and give the caller access to the interesting part of the node. In this case, the tail, the remainder of the list.


2. Why create a function if we know both types?


The short answer is: Type Deduction.
We will not call this version of the function directly. In fact, we most likely will not know the parameterized types to use in the declaration. This is an important concept to remember when programming generics. We want to focus on the constraints for the class of types to be used with our construct, rather than implementing our construct around a particular type. To design for a particular type, often leads to assumptions about the data that will be used, which in turn leads to a rigid implementation. I will be sure to revisit the topic of genericityin a future post. For now, suffice it to say that most of generic programming would not be possible if the compiler were not capable of type deduction.


All calls to the pop_front function will use the single parameter template. While the compiler is searching it's set of template instantiations for the best fit, it will deduce the two types from the Typelist that we provide. This function becomes a helper method, and is called indirectly by the compiler to create the final type. A direct instantiation would equate to the verbose syntax of the nested linked-list example from above. We use templates to put the compiler to work and generate all of this tedious code.


A specialization to handle the empty node is all that remains to complete the pop_front method.


C++

template &lt; TMP_ARRAY_31(typename T) >
struct pop_front &lt; TypeList&lt; empty, TMP_ARRAY_31(T) > >
{
  typedef empty type;
};

push_front


One final operation that I would like to demonstrate is how to implement is push_front. This will allow use to programmatically build a Typelist in our code. This operation appends a new type at the front of and existing list. Here is the forward declaration of the meta-function defined with the form the caller will use:


C++

// forward declaration
template &lt; typename ContainerT,
           typename T>
struct push_front;

The primary implementation of this template also contains one more parameter type than we expect. This gives the compiler mechanism to recursively construct the Typelist from a set of nodes. Eventually the existing Typelist sequence will be constructed, and finally the new type T that we specify will be added to the node at the front of the final list.


C++

template &lt; typename T1, typename T2, typename T >
struct push_front &lt; TypeNode &lt; T1, T2 >, T >
{
  typedef TypeNode &lt; T, TypeNode &lt; T1, T2 > > type;
};
 
// The syntactic sugar definition of this operation.
template &lt; TMP_ARRAY_32(typename T), typename T >
struct push_front &lt; TypeList &lt; TMP_ARRAY_32(T) >, T >
{
  typedef TypeList &lt; T, TMP_ARRAY_31(T) > type;
};

Finally, we must provide a specialization that contains the empty terminator.


C++

template &lt; typename T >
struct push_front &lt; empty, T >
{
  typedef TypeNode &lt; T, empty > type;
};




Summary


The Typelist will be the basis of my implementation for alchemy. In this entry I demonstrated in more detail how a Typelist is constructed, and design rationale for implementing generic programming constructs. I showed how the Typelist itself is not that much different compared to a traditional link-linked list that you most likely have worked with at some point in your career. In truth, these operations barely scratch the possibilities for what is possible for operating on the Typelist. You will find even more Typelist operations in Andrei Alexandrescu's book, Modern C++ Design. Such as rotating the elements of the list, and pruning the list to remove all of the duplicate types.


We are not done with our study of Typelists. In my next Typelist entry, we will move beyond the abstract and academic into the practical. I will explain new operations that I will need to implement Alchemy, and I will demonstrate how they can be applied to accomplish something useful.

Preprocessor Code Generation

general, CodeProject, Boost, C++, maintainability, Alchemy 2 feedbacks »

I really do not like MACROs in C and C++, at least the way they have been traditionally used starting with C. Many of these uses are antiquated because of better feature support with C++. The primary uses are inline function calls and constant declarations. With the possibility of MACRO instantiation side-effects, and all of the different ways a programmer can use a function, it is very difficult to write it correctly for all scenarios. And when a problem does occur, you cannot be certain what is being generated and compiled unless you look at the output from the preprocessor to determine if it is what you had intended.

However, there is still one use of MACROs, that I think makes them too valuable for the preprocessor to be removed altogether. This use is code generation in definitions. What I mean by that, is hiding cumbersome boiler-plate definitions that cannot easily be replicated without resorting to manual cut-and-paste editing. Cut-and-Paste is notorious for its likelihood of introducing bugs. I want to discuss some of the features that cannot be matched without the preprocessor, and set some guidelines that will help keep problems caused by preprocessor misuse to a minimum.

Beyond Function MACROs and Constants

There are two operators that are unique to the preprocessor, and allow so much more to be accomplished with MACROs than implement inline functions. The first operator converts the input parameter to a string, and the second operator allows tokens to be pasted together to create a new symbol or declaration based on the input.

String Conversion Operator: #

40-years before that #-tag became a cultural phenomenon, this operator was available in the C preprocessor. This operator is used with MACROs that take arguments. When the # prepends an argument in the MACRO definition, the argument passed to the MACRO will be converted to a string literal. This means it will be enclosed with quotation marks. Any whitespace before and after the string argument will be ignored. Therefore, strings will automatically be concatenated if two or more are adjacent to each other.

Example

#define PRINT_VALUE( p ) \
  std::cout < < # p < < " = " < < p < < std::endl;

// usage:
int index = 20;
PRINT_VALUE(index);

// output:
// index = 20;

As the example above illustrates, the string conversion operator provides us with a way to insert the name of symbols that we are programming with into output messages. This allows one argument to provide the name of the parameter as well as the value in the output message.

The C++ Way

If we were solely interested in getting the name of an argument, C++ provides a mechanism to do this, if you have type information enabled. You must include the typeinfo header file. Then you can use the typeid operator to construct an instance of the type_info class. This class has a member called type_info::name that will return the human-readable string name of the symbol

C++

#include &lt; typeinfo >
// ...
 
int index = 20;
cout &lt; &lt; typeid (index)::name() &lt; &lt; " = " &lt; &lt; index;
 
// output
// index = 20

Wait There's More

If all I wanted was to print the name of symbols, I would have sucked it up and adopted the C++ way years ago. However, anything that you place in the argument will be converted to a string. This allows this very well known MACRO sequence to be possible:

#define STR2_(x) #x
#define STR1_(x) STR2_(x)
#define TODO(str) \
  __pragma(message (__FILE__"("STR1_(__LINE__)"): TODO: " str))

// usage: TODO("Complete task.")

What does this do? This implementation is specific to Microsoft compilers; it will invoke the #pragma(message) directive, to print a message to the compiler output. Notice that it is not our message that we are converting to a string, but the line number where the message is declared.

That is accomplished with this statement: STR1_(__LINE__). You may be wondering why there are two STR_ MACRO definitions, with one nested inside of the other. That is because __LINE__ itself is a preprocessor MACRO. If we simply made this call STR2_(__LINE__), the literal output "__LINE__" would be created rather than the intended line number. The nested MACRO is a way to force the processor to resolve __LINE__ before converting the result to a string. See, MACROs can be tricky to get correct.

Finally, It will also prepend the text "TODO:" before the supplied message is finally printed. This allows the Task Manager in Visual Studio to recognize that line as a point of code that still requires attention. The final result is a message is printed to the compiler output window, that is clickable, and will take the user directly to the file and line where the TODO message was left.

file.cpp(101): TODO: Complete task

Since I first came across this MACRO for inserting messages on Microsoft compilers, I have adapted it to work for GCC compilers as well. At this point for all other compilers, the MACRO will do nothing.

// Add Compiler Specific Adjustments
#ifdef _MSC_VER
# define DO_PRAGMA(x) __pragma(x)
#elif defined(__GCC__)
# define DO_PRAGMA(x) _Pragma(x)
#else
# define DO_PRAGMA(x)
#endif

// Adjusted Message MACRO
#define MESSAGE(str) \
  DO_PRAGMA(message(__FILE__"("STR1_(__LINE__)"): NOTICE: " str))

I find the # operator is very useful for creating terse statements that improve readability and maintainability. As with any type of solution, always in moderation.

Token Pasting Operator: ##

When you want to create programmatically create repetitive symbols in code, the token-pasting operator, ## is what you need. When this operator precedes a MACRO argument, the whitespace between the previous symbol and the MACRO argument will be removed, joining the two parts together to create one token. If this is not obvious, the ## cannot be the first or last token in a MACRO definition. Here is a simple example to demonstrate:

Example

#define PRINT_OFFSET( n ) \
  std::cout << "offset" #n << " = " << offset ## n << std::endl;

// usage:
int offset2 = 20;
int offsetNext = 30;
PRINT_OFFSET(2);
PRINT_OFFSET(Next);

// output:
// offset2 = 20;
// offsetNext = 30;

This is only a demonstration for how the token-paste operator works. I will demonstrate more valuable uses in the next section.

Generating Code

My philosophy when writing code is, "The best code, is the code that is not written". Meaning, strive for simple elegant solutions. At some point, some code must exist in order to have a program. Generated code is a close second in my preferences. We can use the preprocessor with great effect towards achieving this goal. However, once again, code generation is not a panacea, because it is generally restricted to boilerplate type definitions.

Generally in practice, your software will be easier to build when there are fewer tools involved in the build process. I have written and used code generation programs, and when it is the right tool, it works fantastically. However, there is a threshold of effort that is required for a task to exceed before it becomes worth the trouble of developing and maintaining a new tool, and adding complexity to your build system. In these cases, code generation with the preprocessor is a great solution.

Before I continue, I would like to mention that Boost contains a preprocessor library[^], which is capable of some amazing things. Such as, identifying the number of arguments in a MACRO expression, iterating over the list of arguments, counting and many others. Think of it as meta-programming with the preprocessor. Many of the examples below are simplified and less general solutions to the same sort of capabilities provided by Boost Preprocessor.

Indexing with Recursion

Working with the preprocessor is yet another example of functional-programming hidden inside of C++. We are restricted from using state or mutable data (variables). Therefore, many of the solutions with the preprocessor become solutions that involve recursion, especially if a task must be repeated a number of times.

When I was exploring the Typelist construct a few days ago, I came across this cumbersome declaration:

C++

// Typelist primary template definition.
template &lt; typename T0,         typename T1 = empty,
           typename T2 = empty, typename T3 = empty,
           typename T4 = empty, typename T5 = empty,
           typename T6 = empty, typename T7 = empty,
           typename T8 = empty, typename T9 = empty >
struct Typelist
{
  typedef Typenode&lt; T0,
          Typenode&lt; T1,
          Typenode&lt; T2,
          Typenode&lt; T3,
          Typenode&lt; T4,
          Typenode&lt; T5,
          Typenode&lt; T6,
          Typenode&lt; T7,
          Typenode&lt; T8,
          Typenode&lt; T9, empty > > > > > > > > > >     type;
};

This will be tedious to maintain, and error prone as we will need to update the type definitions anywhere the Typelist is used. For brevity, I only included 10 entries in the demonstration implementation. For my solution in Alchemy, I planned on starting with a minimum support for up to 32 entries. It would be nice if we could take advantage of the preprocessor to generate some of this repetitive code for us. Especially since these are hidden definitions in a library. The user will have no need to explore these header files to determine how to interact with these constructs. That makes me feel even more confident with a solution that depends on the preprocessor.

The first challenge that we will need to overcome is how do we build something that can repetitively process something until a given end-point is reached? This sounds like a recursive solution. To create this effect, we will need a utility file with predeclared MACROs. Boost actually has MACROs create these MACROs. For what I am after, I can get by with a small set MACROs specifically built to suit my purpose.

C++

#define ALCHEMY_ARRAY_1(T)    T##0
#define ALCHEMY_ARRAY_2(T)    ALCHEMY_ARRAY_1(T),  T##1
#define ALCHEMY_ARRAY_3(T)    ALCHEMY_ARRAY_2(T) , T##2
// ...
#define ALCHEMY_ARRAY_32(T)   ALCHEMY_ARRAY_31(T), T##31
 
// Repeats a specified number of times, 32 is the current maximum.
// Note: The value N passed in must be a literal number.
#define ALCHEMY_ARRAY_N(N,T)  ALCHEMY_ARRAY_##N(T)

This will allow us to create something like this:

C++

ALCHEMY_REPEAT_N(4, typename T);
// Creates this, newlines added for clarity
typename T0,
typename T1,
typename T2,
typename T3

This will eliminate most of the repetitive template definitions that I would have had to otherwise write by hand. How does the chain of MACROs work? The result of each MACRO is a call to the MACRO of the previous index, followed by a comma, and the input T, token-pasted with the current index. Basically, we are constructing a MACRO as part of the resolution of the current MACRO. This forces the preprocessor to make another pass and resolve this instance. The process continues until the terminating case is reached.

This first version helps in two of the declarations, however, the declaration with the nested Typenodes cannot be solved with the MACRO in this form. The right-angle brackets are nested at the end of the definition. Pasting the index at the end of this expression would no longer be correct. Rather than trying to be clever, and create a MACRO that would allow me to replace text inside of a definition, I will just create a second simpler MACRO that repeats a specified token, N times.

C++

#define ALCHEMY_REPEAT_1(T)    T
#define ALCHEMY_REPEAT_2(T)    ALCHEMY_REPEAT_1(T) T
#define ALCHEMY_REPEAT_3(T)    ALCHEMY_REPEAT_2(T) T
// ...
#define ALCHEMY_REPEAT_32(T)   ALCHEMY_REPEAT_31(T) T
 
// Repeats a specified number of times, 32 is the current max
// Note: The value N passed in must be a literal number.
#define ALCHEMY_REPEAT_N(N,T)  ALCHEMY_REPEAT_##N(T)

With these two MACROs, we can now simplify the definition of a Typelist to the following:

// I have chosen to leave the template definition
// fully expanded for clarity.
// Also would have to solve the challenge of 
// T0 not having a default value.
template < typename T0, typename T1 = empty, 
  // ...
  typename T30 = empty, typename T31 = empty >
struct TypeList
{
#define DECLARE_TYPE_LIST  \
  ALCHEMY_ARRAY_32(TypeNode< T ), empty ALCHEMY_REPEAT_32( > )

  typedef DECLARE_TYPE_LIST  type;
};

If you remember I mentioned that an implementation will need to be defined for each specialization of the base template above. We have already developed all of the helper MACROs to help us define those specializations.

#define tmp_ALCHEMY_TYPELIST_DEF(S)              \
template < ALCHEMY_ARRAY_ ##S(typename T)>       \
struct TypeList < ALCHEMY_ARRAY_##S(T) >         \
{                                                \
  typedef ALCHEMY_ARRAY_##S(TypeNode < T ), empty \
    ALCHEMY_REPEAT_##S( > ). type;               \
}

// Define specializations of this array from 1 to 31 elements *****************
tmp_ALCHEMY_TYPELIST_DEF(1);
tmp_ALCHEMY_TYPELIST_DEF(2);
// ...
tmp_ALCHEMY_TYPELIST_DEF(31);

// Undefined the MACRO to prevent its further use.
#undef tmp_ALCHEMY_TYPELIST_DEF

All-in-all, the little bit of work replaces about 500 lines of definitions. We will end up using those a few more times to implement the Typelist utility functions.

Guidelines

These are a few rules that I try to follow when working on a solution. MACROs in-and-of themselves are not bad. However, there are many unknown factors that can affect how a MACRO behaves. The only way to know for sure what is happening, is to compile the file, and inspect the output from the preprocessor. If I ever need to resort to using a MACRO function, I try to hide its use away within another function, and isolate that function as much as possible so that I can be sure it is correct. The list of guidelines below is not a complete rule set, nor are these rules absolute, but they should help build more reliable and maintainable solutions when you need to resort to the power of the preprocessor.

Make them UGLY

I think the convention of ALL_CAPS_WITH_UNDERSCORES is ugly. I also think it helps easily identify MACROs in your code, and as you saw in my definitions, I don't mind creating very long names for MACROs. Hopefully their use remains hidden in implementation files.

Define constants_all_lowercase

This one only comes to mind because I have been bitten by it when trying to port code between platforms. This is another convention that has migrated from the original C days of using #define to declare MACRO constants. However, this could leave you vulnerable to some extremely difficult to find compiler errors in the best case, or code that incorrectly compiles in the worst case.

What do I mean? Think about the result if there was a MACRO defined deep within platform or library header files that clashes with the name you have declared using the CAPITAL_SNAKE_CASE naming convention. Your constant value would be overwritten with the code defined behind the MACRO. In most cases I imagine this would result in a weird compiler error stating cannot assign a literal to a literal. However, the syntax could result in something that is valid for the compiler, but not logically correct. This is one of the potential downsides of the preprocessor.

Restrict MACROs to Declarations

If you limit the context when your MACROs are used, you will have much more control over the conditions that your MACRO can be used, and ensure that it works properly. There is no longer any reason to use a MACRO as a function with inline functions in C++. However, using a MACRO to help generate a complex definition should be much less of a risk, and improves the readability and maintainability tremendously.

One of my favorite examples of this use for MACROs is in Microsoft's ATL and WTL libraries to define Windows event dispatch functions. For those of you that are not familiar with Windows programming with C/C++, each window has a registered WindowProc. This is the dispatch procedure that inspects events, and calls the correct handler based on event type. Here is an example of the WindowProc generated by the default project wizard:

C++

LRESULT CALLBACK WndProc(
  HWND hWnd,
  UINT message,
  WPARAM wParam,
  LPARAM lParam
)
{
  int wmId, wmEvent;
  PAINTSTRUCT ps;
  HDC hdc;
 
  switch (message)
  {
  case WM_COMMAND:
    wmId    = LOWORD(wParam);
    wmEvent = HIWORD(wParam);
    // Parse the menu selections:
    switch (wmId)
    {
    case IDM_ABOUT:
      DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
      break;
    case IDM_EXIT:
      DestroyWindow(hWnd);
    break;
    default:
    return DefWindowProc(hWnd, message, wParam, lParam);
   }
   break;
  case WM_PAINT:
    hdc = BeginPaint(hWnd, &amp;ps);
    // TODO: Add any drawing code here...
    EndPaint(hWnd, &amp;ps);
    break;
  case WM_DESTROY:
    PostQuitMessage(0);
    break;
  default:
    return DefWindowProc(hWnd, message, wParam, lParam);
  }
  return 0;
}

You can already see what a potential disaster is looming there. The code for each event is implemented in-line within the switch statement. I have run across WindowProc functions with up to 10000 lines of code in them. Ridiculous! Here is what a WindowProc looks like in ATL:

C++

BEGIN_MSG_MAP(CNewWindow)
    COMMAND_ID_HANDLER(IDM_ABOUT, OnAbout)
    COMMAND_ID_HANDLER(IDM_EXIT, OnExit)
    MESSAGE_HANDLER(WM_PAINT, OnPaint)
    MESSAGE_HANDLER(WM_DESTROY, OnDestroy)
  END_MSG_MAP()

This table declaration basically generates a WindowProc procedure, and maps the event handlers to a specific function call. Not only is this easier to read, it also encourages a maintainable implementation by hiding the direct access to the switch statement, and promoting the use of function handlers. I have successfully used this model many times to provide the required registration or definition of values. The result is an easy to read table that is compact and can easily serve as a point of reference for what events are registered, or definitions configured into your system.

Summary

I have demonstrated (ever notice the word demon starts out the word demonstrate) how to use some of the lesser used preprocessor features. I then went on to solve some cumbersome code declarations with these techniques, so now I have a fully declared Typelist type. Coming up, you will see how we will be able to take advantage of these utility MACROs to greatly simplify declarations that we use in the core of our library as we develop. In the end, the user of the library will be unaware that these MACROs even exist. While any type of MACRO can be risky to use based on what is included before your definition, I feel that this type of scenario gives the developer enough control over the definitions to minimize the potential for unexpected problems.

The link to download Alchemy is found below.

  • The Typelist declaration can be found in the file: /Alchemy/Meta/type_list.h.
  • The utility MACROs are located in: /Alchemy/Meta/meta_macros.h.

C++: < type_traits > header

general, CodeProject, C++, Alchemy, design Send feedback »

For this entry, I would like to introduce the type_traits header file. This file contains utility templates that greatly simplify work when writing template-based libraries. This is especially true for libraries that employ template meta-programming. The header file is available with C++ TR1 and above. This library provides tools to identify types, their qualifying properties and even peel-off properties one-by-one programmatically at compile-time. There are also transformation meta-functions that provide basic meta-programming operations such as a compile-time conditional.

The definitions in type_traits will save us a lot of time implementing Alchemy. As I introduce some of the tools that are available in the header, I will also demonstrate how these operations can be implemented. This will help you understand how to construct variations of the same type of solution when applying it in a different context. As an example of this, I will create a construct that behaves similarly to the tertiary operator, but is evaluated at compile-time.

Types and Values

Creating C++ template meta-programs are essentially functional programs. Functional programs compute with mathematical expressions. You will receive the same result each time you call a function with a specific set of parameters. As expressions are declarative, state and mutable data are generally avoided. Meta-programs are structured in a way to require the compiler to calculate the results of the expressions as part of compilation. The two constructs that we have to work with are integer constants, to hold calculation results, and types, which we can use like function calls.

Define a Value

Meta-program constants are declared and initialized statically. Therefore, these values are limited to integer-types. We cannot use string literals or floating-points because these types of static constants cannot be initialized in place with the class or struct definition. Sometimes you will see code declared with enumerations. I believe this is to prevent meta-programming objects from using space. It is possible for users to take the address of static constants, and if this occurs, the compiler must allocate space for the constant, even if the object is never instantiated. It is not possible to take the address of an enumeration declaration. Therefore no memory must be allocated when an enumeration is used.

Since I started using type_traits, I don't worry about it so much. I use the integral_constant template to define values. By convention, values are given the name value. This is important in generic programming to allow the object development to remain loosely coupled and independent of the design of other objects. The example below demonstrates how the integral_constant is typically used. Please note that all of these constructs live in the std:: namespace, which I will be omitting in these examples.

C++

// Implement the pow function to calculate
// exponent multiplication in a meta-function.
template &lt; size_t BaseT, size_t ExpT >
struct Pow
  : integral_constant&lt; size_t,
                       BaseT * Pow&lt; BaseT , ExpT-1>::value >
{ };
 
// Specialization: Terminator for exp 1.
template &lt; size_t BaseT >
struct Pow&lt; BaseT, 1 >
  : integral_constant&lt; size_t, BaseT >
{ };
 
// Specialization: Special case for exp 0.
template &lt; size_t BaseT >
struct Pow&lt; BaseT, 0 >
  : integral_constant&lt; size_t, 1 >
{ };

Call (Instantiate) our meta-function:

C++

int x = Result&lt; 3,3 >::value; // 27

integral_constant

All that is required to implement the integral_constant, is a definition of a static constant in the template struct. Structs are generally used because of their default public member access. Here is the most basic implementation:

C++

template &lt; typename T,
           T ValT>
struct integral_constant
{
  static const T value = ValT;
};

Yes it's that simple. The implementation in the C++ Standard Library goes a little bit further for convenience. Just as with the STL Containers, typedefs are created for the value_type and type of the object. There is also a value conversion operator to implicitly convert the object to the value_type. Here is the complete implementation:

C++

template &lt; typename T,
           T ValT>
struct integral_constant
{
  typedef T                           value_type;
  typedef integral_constant&lt; T, ValT> type;
 
  static const T value = ValT;
 
  operator value_type() const
  {
    return value;
  }
};

Two typedefs have been created to reduce the amount of code required to perform Boolean logic with meta-programs:

C++

typedef integral_constant&lt; bool, true >  true_type;
typedef integral_constant&lt; bool, false > false_type;

Compile-time Decisions

With meta-programming there is only one way to define a variable, and there are many ways to create decision making logic. Let's start with one that is very useful for making decisions.

is_same

This template allows you to test if two types are the same type.

C++

template &lt; typename T,
           typename U >
struct is_same
  : false_type
{ };
 
// Specialization: When types are the same
template &lt; typename T >
struct is_same&lt; T,T >
  : true_type
{ };

The compiler always looks for the best fit. That way, when multiple templates would be suitable, only the best match will be selected, if that is possible. In this case, the best match for when both types are the exact same, is our specialization that indicates true.

conditional

It's time to define a branching construct to enable us to make choices based on type. The conditional template is the moral equivalent of the if-statement for imperative C++.

C++

// The default implementation represents false
template &lt; bool Predicate,
           typename T,
           typename F >
struct conditional
{
  typedef F type;
};
 
// Specialization: Handles true
template &lt; typename T,
           typename F >
struct conditional &lt; true, T, F >
{
  typedef T type;
};

Applying These Techniques

I have just demonstrated how three of the constructs defined in the type_traits header could be implemented. The techniques used to implement these constructs are used repeatedly to create solutions for evermore complex problems. I would like to demonstrate a construct that I use quite often in my own code, which is both built upon the templates I just discussed, and implemented with the same techniques used to implement those templates.

value_if

While the conditional template will define a type based on the result a Boolean expression, I commonly want to conditionally define a value based on the result of a Boolean expression. Therefore, I implemented the value_if template. This makes use of the integral_constant template and a similar implementation as was used to create the conditional template. This gives me another tool to simplify the complex parametric expressions that I often encounter.

C++

template &lt; bool Predicate,
           typename T,
           T TrueValue,
           T FalseValue >
struct value_if
  : integral_constant&lt; T, FalseValue >
{ };
 
// Specialization: True Case
template &lt; typename T,
           T TrueValue,
           T FalseValue >
struct value_if &lt; true, T, TrueValue, FalseValue >
  : integral_constant&lt; T, TrueValue >
{ };

Summary

I just introduced you to the type_traits header in C++. If you have not yet discovered this header, you should check it out. It can be very useful, even if you are not creating template meta-programs. Here is a reference link to the header from cppreference.com[^].

With the basic constructs that I introduced in this entry, I should now be able to create more sophisticated ways to interact with the Typelist[^] that I previously discussed for Alchemy. With the simple techniques used above, we should be able to implement template expressions that will query a Typelist type by index, get the size of the type at an index, and similarly calculate the offset in bytes from the beginning of the Typelist. The offset will be one of the most important pieces of information to know for the Alchemy implementation.

Type Lists

CodeProject, C++, Alchemy, design Send feedback »

Previously I had discussed the tuple data type. The tuple is a general purpose container that can be comprised of any sequence of types. Both the types and the values can be accessed by index or traversing similar to a linked list.

The TypeList is a category of types that are very similar to the tuple, except no data is stored within the type list. Whether the final implementation is constructed in the form of a linked list, an array, or even a tree, they are all typically referred to as Typelists. I believe that the Typelist construct is credited to Andrei Alexandrescu. He first published an article in the C/C++ Users Journal, but a more thorough description can be found in his book, Modern C++ Design.

Note:
For an implementation of a TypeList with Modern C++, check out this entry:
C++: Template Meta-Programming 2.0[^]

There is No Spoon

What happens when you instantiate a Typelist?

Nothing.

Besides, that's not the point of creating a Typelist container. The overall purpose is to collect, manage, and traverse type information programmatically. Originating with generic programming methods in C++, type lists are implemented with templates. Type lists are extremely simple, and yet can be used to solve a number of problems that would require enormous amounts of hand-written code to solve. I will use the Typelist in my solution for Alchemy.

Let's start by defining a Typelist.:

C++

template < typename T, typename U >
struct Typelist
{
  typedef T        head_t;
  typedef U        tail_t;
};


There are no data or functions defined in a Typelist, only type definitions. We only need these two elements, because as we saw with the Tuple, more complex sets of types can be created by chaining Typelists together with the tail. Here is an example of more complex Typelist definition:

C++

// Typelist with an 8, 16, 32, and 64 bit integer defined.
typedef
  Typelist< char ,
  Typelist< short,
  Typelist< int, long int > > > integral_t;


When I first saw this, I thought two things:

  1. How can this be useful, there is no data
  2. The syntax is extremely verbose, I wouldn't want to use that



Remember in The Matrix when Neo goes to meet The Oracle, and he is waiting with the other "potentials"?! While he waits, he watches a young prodigy bending a spoon with his mind. He urges Neo to try, and offers some advice:



Spoon boy: Do not try and bend the spoon. That's impossible. Instead... only try to realize the truth.
Neo: What truth?
Spoon boy: There is no spoon.
Neo: There is no spoon?
Spoon boy: Then you'll see, that it is not the spoon that bends, it is only yourself.



Hmmm, maybe that's a bit too abstract, but, that's pretty much what it's like working with a Typelist. There is no data. Now take your red pill and let's move on.



Simplify the Definition


Let's make the definition simpler to work with. Working with a single Typelist definition of variable length seems much simpler to me than having to enter this repeated nesting of Typelist structures. Something like this:

C++

typedef Typelist< char, short, int, long int > integral_t;
// Or format like a C struct definition:
typedef Typelist
<
  char,
  short,
  int,
  long int
> integral_t;

This could be usable, and it is easily achieved with template specialization or variadic templates. The solution based on template specialization is much more verbose, however, it is also more portable. I have also seen comments on compiler limits placed on the number of fields supported by variadic templates, but I do not have any personal experience with hitting limits myself. This is something I will probably explore in the future. For now, I will start the implementation with a template specialization solution.



Specialization


For this type of solution, we must select a maximum number of elements that we want or expect to be used. This is one of the drawbacks of specialization compared to the variadic approach. The forward declaration of the full Typelist would look like this:

C++

template < typename T0, typename T1, ..., typename Tn >
struct Typelist;


We cannot go much further until we resolve the next missing concept.



The Terminator


Similar to a linked-list, we will need some sort of indicator to mark the end of the Typelist. This terminator will also be used in the specialized definitions of Typelist to give us a consistent way to define the large number of definitions that will be created. With meta-programming, we do not have variables, only types and constants. Since a Typelist is constructed entirely from types, we should use a type to define the terminator:

C++

struct empty {};


With a defined terminator, here is what the outer definition for a 10-node Type list:


C++

template < typename T0,         typename T1 = empty,
           typename T2 = empty, typename T3 = empty,
           typename T4 = empty, typename T5 = empty,
           typename T6 = empty, typename T7 = empty,
           typename T8 = empty, typename T9 = empty >
struct Typelist
{
  // TBD ...
};


Here is the outer definition for a specialization with two items:

C++

template < typename T0, typename T1 >
struct Typelist< T0, T1 >
{
  // TBD ...
};


Implementation


Believe it or not, we have already seen the implementation that goes inside of the template definitions shown above. The only exception is we will rename what we previously called a Typelist to a Typenode. Otherwise, the implementation becomes the typedef that we created. By convention, we will name the typedef, type. For reference, constant values are called, value, in template meta-programming. This consistency provides a very generic and compatible way for separate objects that were not designed together, to still inter-operate.



C++

template < typename T, typename U >
struct Typenode
{
  typedef T        head_t;
  typedef U        tail_t;
};
// Typelist primary template definition.
template < typename T0,         typename T1 = empty,
           typename T2 = empty, typename T3 = empty,
           typename T4 = empty, typename T5 = empty,
           typename T6 = empty, typename T7 = empty,
           typename T8 = empty, typename T9 = empty >
struct Typelist
{
  typedef Typenode< T0,
          Typenode< T1,
          Typenode< T2,
          Typenode< T3,
          Typenode< T4,
          Typenode< T5,
          Typenode< T6,
          Typenode< T7,
          Typenode< T8,
          Typenode< T9 > > > > > > > > > >     type;
};


Here is the implementation for the two node specialization:

C++

template < typename T0, typename T1 >
struct Typelist < T0, T1 >
{
  typedef Typenode< T0,
          Typenode< T1> >   type;
};


Simple? Yes. Verbose? Yes. Is it worth it? I believe it will be. Besides, since this definition will be hidden away from users, I would feel comfortable defining some code-generating MACROs to take care of the verbose and repetitive internal definitions. However, I will demonstrate that another time.



Using a Typelist


We have simplified the interface required of the user to define a Typelist, however, interacting with one at this point is still cumbersome. For example, consider the definition of the integral_t Typelist defined above. If we wanted to create a variable using the type in the 3rd slot (index 2, int), this syntax would be required:

C++

integral_t::type::tail_t::tail_t::head_t third_type = 0;

These are the stories that grown-up C programmers tell little C++ programmers growing up to prevent the use of some of the most effective aspects of the language. The next few entries will be focused on extracting data out of the Typelist in a clean and simple way. However, let's tackle one solution right now.




How Many Elements?


Length is a common piece of information that is desired from containers. This is no different for type-containers. How can we determine the number of elements in the integral_t we have been using in this entry? We will write a meta-function. Unfortunately, I have not yet demonstrated many of the techniques in meta-function development. This means we will need to develop a Length function that matches the signature for every specialization that was created for the Typelist definition itself. Otherwise, we could create a meta-function that actively traverses the Typenodes searching for a terminator. We will revisit and solve this problem with a more elegant solution.



The solution will be very simple, and very verbose, but still, very simple. Since we must define a Length implementation for each Typelist specialization that we created, we know in each specialization how many parameters types were defined. We can take advantage of that information to create our simple solution:


C++

template < typename ContainerT >
struct Length;
 
template <>
struct Length < empty >
{
  enum { value = 0 };
}
 
template < typename T0 >
struct Length < Typelist < T0 > >
{
  enum { value = 1; }
}
 
template &amp;amp< typename T0, typename T1 >
struct Length &amp;amp&lt; Typelist < T0, T1 > >
{
  enum { value = 2; }
}


Again, with some preprocessor MACROS, generating all of the variations could be greatly simplified. For now, I would like to get enough infrastructure in place to determine how effective this entire approach will be at solving the goals of Alchemy. Here is a sample that demonstrates querying the number of elements in the integral_t type.


C++

// Calls the meta-function Length
// to get the number of items in integral_t.
size_t count = Length< integral_t >::value;
 
// count now equals 4


Summary


I have now introduced the Typelist meta-programming construct. This is a simple type-only type declaration, which contains quite a bit of untapped potential for us. However, without a basic set of meta-programming constructs to build upon, our only option for implementing the Length meta-function is to resort to one function implementation for the total number of elements that can be held in the Typelist. This is not a very maintainable solution, but it won't be this way for long. I will be introducing a few simple constructs to make decisions based on type at compile-time, in order to create a more elegant and maintainable implementation of Length. From there I will continue forward and show how to query the type of parameter at a specified index, get the size of that type and many other meta-functions we can use to inspect our new data structure.

C++: Tuple

CodeProject, C++, Alchemy, design 3 feedbacks »

During my design analysis for my Network Alchemy implementation I thought that the tuple may be the answer to allow me to iterate over the types defined in a network message definition. Tuples are data structures that are a generalization of the std::pair. Rather than having a limitation of 2 items in a tuple, potentially any number of items can be constructed within a custom tuple definition. The upper-limit will most likely be associated with the limit of your compilers ability to recurse down within a nested template structure. Conceptually, a tuple is similar to a compile-time linked list. If a tuple were implemented in terms of the std::pair, it would be constructed like this:

C++

#include < utility >
using std::pair;
 
pair< int ,
      pair< float,
            pair< char, long >
          >
    > tuple;

The previous block of code defines a structure that contains 4 elements, where the head of the list is a defined type, and the tail is the remainder of the list. This particular tuple defines a type that contains: int, float, char, and a long.

What exactly is a tuple?

Before I can get into detail for how a tuple is useful, I think it would be best to show the difference between a pair and a tuple, especially if you are already familiar with the std::pair. The most common way to be introduced to the pair, is when you use std::map. The key-value pairs are actually stored in the map as an instance of an std::pair. There are only two parameters in the pair; the names of these parameters are first and second. This values represent the first and second items, respectively, which are defined in the pair. As this is a parameterized type, the parameter types of first and second is entirely dependent on each instantiation of std::pair.

Until recently, I have rarely use the pair outside of my usage of the std::map, primarily because of the accessor name, first and second. As I stated earlier, the tuple is a generalization of the pair. Accessing the different fields of a tuple differs from the pair, in that you reference an entry by its position, similar to an array. There is a parameterize function called, get that returns the value of an element of a specified index in the tuple. Similarly, there is a function called tuple_element that can be used to query the type of the element at a specified index. Here is an example that demonstrates the tuple:

C++

#include < iostream >
#include < tuple >
 
using std::tuple_element;
using std::get;
 
// The types are deduced to construct the tuple.
typedef std::tuple< int , char, size_t> tuple_t;
tuple_t data = std::make_tuple (10,'a', 100);
 
tuple_element< 0,tuple_t >::type valueA = get< 0 >(data);
tuple_element< 1,tuple_t >::type valueB = get< 1 >(data);
tuple_element< 2,tuple_t >::type valueC = get< 2 >(data);
 
// The types and values for each of the parameters:
// int    valueA = 10;
// char   valueB = 'a';
// size_t valueC = 100;

There are only a few other functions to be aware of with regards to the tuple:

  • tuple_size: Returns the number of elements in the tuple
  • tuple_cat: Concatenates two tuples to create a third tuple type
  • tie: Unpacks arguments from a tuple, and constructs a new tuple

Tie is the only function that I think needs further explanation. There is a companion type used with tie called, ignore. This is used to skip over elements in the incoming tuple to manipulate the final tuple that is constructed from the call to tie. Ultimately, this is a utility function to more conveniently construct a new type from an existing tuple type. After all, the moral equivalent to variables in template meta-programming is a new type.

How can a tuple be useful?

Let's return back to Alchemy and discuss the tuple in terms of our proposed library. Remember in the previous entry that I was searching for a mechanism that would allow me to iterate over each of the types defined in a message structure?! Well it appears that the tuple is a mechanism that can provide those capabilities for us. For example, consider if a tuple was defined with all of the elements that should appear in a message packet structure. With the handle full of functions provided by the C++ Standard Library we can:

  • Determine the number of elements in the tuple with tuple_size
  • Iterate the tuple to determine the type of an element at each index with tuple_element
  • Obtain the type of an element at a specified index with get
  • Most importantly, we can now reliably calculate the offset that a parameter should be placed in a raw buffer with this set of meta-functions

OffsetOf &lt; Idx, TupleT >

Let's analyze what I just defined to calculate the offset in bytes, for the specified position of a parameter in a tuple definition. The very first thing that I chose to do for this implementation was to create a forward declaration of this OffsetOf utility function. Simply to introduce the format of the template before we analyze the more complex aspects of this construct. This template requires a positive integer value to specify the index of the element, and a fully defined tuple. Because it's a template declaration, any type can actually be placed in the second parameter TupleT. However, the first parameter's type is already defined as size_t, so a positive integral value must be specified for the first parameter. I will demonstrate shortly that the actual types that can be specified are slightly more restrictive than I first indicated.

C++

//  Forward Declaration **********
template < size_t Index, typename TupleT>
struct OffsetOf;

The second struct defined in the first block requires us to take off our imperative programming hat, and switch over to use our functional programming hat. This hat has a very awkward fit at first; it will probably feel a little tight and lead to headaches, unless you have worn one while programming a different language such as F#, Haskel or Lisp. My advice, don't fight it, when you break this hat in, you will be a better programmer for having done so. It opens your mind to a new way of thinking about problems. You will be able to see potential solutions from multiple perspectives.

As many meta-template solutions tend to be composed of recursive implementation, the second item in the first block contains the terminating case. That is, a template specialization is created for an element whose specified index is 0. The offset for all elements at index 0, is at 0-bytes. One of the characteristics of functional programming is the inability to create mutable state within a statement. We are able to define new functions, and placeholder variables of sorts. The former is accomplished by declaring a new type, the latter by defining a constant. This is the reason an enumeration named value is assigned the value 0; to hold the calculated offset for the element at index 0. To access the value of the index, the OffsetOf type must be specified with the desired index, and the enumeration value must be referenced to get access to the value.

C++

//  Forward Declaration **********
template < size_t Index, typename TupleT>
struct OffsetOf;
 
//  *******************************
/// The item at index 0 will always have an offset at 0.
///
template < typename TupleT >
struct OffsetOf< 0, TupleT >
{
  enum { value = 0 };
};

C++

//  Get the offset of element 0 **
size_t offset = OffsetOf<0, tuple_t>::value;
 
// offset now equals: 0

By convention, constant values are given the name value and type definitions for sub-types are given a name that indicates it is a type of some sorts. For example, look at the documentation for the C++ Standard containers such as vector and map. These containers have many typedefs to declare the value_type, size_type, allocator_type; then there are other general purpose names used for reference, pointer, iterator and const versions for these types.

Specialization for a specific tuple type

C++

template < typename TupleT>
struct OffsetOf< IdxT, TupleT >
{
  typedef TupleT  container;
  typedef std::tuple_element< IdxT-1,
                              container>::type    prev;
 
  enum { value = OffsetOf<(IdxT)-1, container>::value
               + sizeof(prev)};
};

There is truly only one statement in the declaration of OffsetOf and that is the definition for the enumeration, value. The two typedefs, container, and prev are solely added for improved readability. There is, however, the possibility this extra type definitions could also prove useful later on. None-the-less, readability is my primary reasoning for adding them here. The calculation of the offset is a straight-forward recursive implementation, and the zero-defined specialization will terminate the loop. Essentially the offset of the previous element is calculated plus the size of that element to calculate the offset of this element. However, to calculate the offset of the previous element, we must know the offset and size of the element prior to that one as well. This behavior recurses until the zero terminator is reached. Then the values bubble back up, and the calculated offset is defined.

All of this behavior occurs at compile-time, with this calculations actually being performed by the compiler. No run-time code is generated from these definitions, only constant values that will be substituted in place anytime an instance of one of these templates is defined. While it is possible that heavy reliance on code written with templates can slow down the compile-times, it has been my experience that the increase in time is negligible. Also, for recursive solution such as this, many compilers have improved to the point where they store the values of previous template instantiation calculations. Therefore, the second time iterating through the loop for calculated offsets, the answer to the previous item will already be known, and a simple lookup is performed to get the value. I will continue go into deeper detail regarding the work that occurs behind the scenes another time.

Will tuples work for Alchemy>

I believe the answer to this question is "Yes." However, I do not think they will be the best fit. As I have been exploring how to use tuples, including accessing values, I think it would be difficult to achieve the natural struct-type syntax I have original set out to achieve. Primarily because of the syntax that is required to access the values from a tuple, the std::get function Therefore, I am going to put this idea to the side, and explore some other options. If the other options do not turn out to be as good as the tuple, I can always return to this idea. I want to point out that I believe the std::tuple would provide a much more robust and portable solution that the offsetof MACRO we explored in the last entry.

Next Step

We will explore what I believe to be the most promising approach in the next entry, TypeLists. I do not know the full etymology for the term, however, many of the sources that I have read credit Andrei Alexandrescu with creating the term in his book Modern C++ Design, which I believe was previously mentioned in an article he wrote that was published in Dr. Dobbs Journal. At TypeList is a similar template-type construct, that is strictly a type. No data is contained in the TypeList itself. This will give us the freedom to choose how to represent and manage all of the data, and at the same time be able to iterate over each of the field types as required.

Desired Alchemy Syntax

portability, CodeProject, C++, maintainability, Alchemy Send feedback »

When I create a new library, I like to approach the design from two different directions. The first is the traditional route, analyzing the functionality that I need and designing a suitable interface to access those features. I also may write a set of pseudo-code that demonstrates what it would look like to use the library. Generally with writing unit tests I get to cover this second option. It is all the better if I write the tests while developing the interface. Then I discover if the interface is a clunky collection of garbage or an joy to work with.

Alchemy is a unique API, in that I don't actually want there to appear to be a library at work. One goal that I set for alchemy is to facilitate the proper handling of network data without requiring much work on the users part. In this sense, I need to work backwards. I would like to take the proposed syntax, and attempt to design my library API to meet the target syntax. The expressive ability of C++ is one of the things that I really like at the language.

What Does It Currently Look Like?

Before I attempt to create a new API to break old habits, I would like to inspect what the old habits look like. If I can make my API similar to the old way, hopefully it will be adopted more easily. The technique that I am going to mimic, is one that is not guaranteed to be portable, yet it works often enough that its use is quite common. This practice is declaring a structure, using the #pragma pack(1) option, and casting raw char* to the structure type. Then the fields are accessed by their name specified in the struct. Here is an example of this technique:

C++

#pragma pack(1)
struct MsgFormat
{
  uint32_t firstValue;
  int16_t secondValue;
  char thirdValue;
};
#pragma pack()

C++

MsgFormat msg;
::memset(&amp;msg, 0, sizeof(MsgFormat));
int retVal = ::recv(s, &amp;msg, sizeof(msg), 0);
// Error checking ...
 
// Convert to the proper byte-order
ConvertMsgToHost(msg);
uint32_t valueA = msg.firstValue;
int16_t valueB = msg.secondValue;
char valueC = msg.thirdValue;

This code is simple and straight-forward linear defined logic. There is nothing is entirely wrong with this type of code. However, things change over time, and what is a few lines of code now could morph into thousands of lines of similar code. I did not show the implementation for the function ConvertMsgToHost. As the format of MsgFormat is updated, the implementation of ConvertMsgToHost must be updated as well. Most likely, there is also a corresponding function called ConvertMsgToNetwork that will need to be updated as well.

When the size of the code grows to include dozens to possibly hundreds of messages, linearly defined logic creates lots of places for little bugs to hide. Moreover, these are not bugs that are introduced to the code, they suddenly appear due to forgetting to update location B because the definition in location A changed. What you don't know CAN definitely hurt you, especially in this situation.

What Should It Look Like?

After looking at common implementations for serialized data, I have a basic idea what I want to try to create. My goals again are to create a portable and robust library to facilitate reliable and maintainable network communication implementations. I want integration of this library to be easy, and the maintenance effort to be minimal. With those factors in mind, here is a pseudo-code representation of how I would like to be able to use Network Alchemy:

Message Definition:

C++

class MsgFormat
  : AlchemyMsg
{
  uint32_t firstValue;
  int16_t secondValue;
  char thirdValue; };

Message Usage:

C++

MsgFormat msg;
input >> msg;
// Something like this should also be possible:
// recv(s, msg.buffer(), msg.size(), 0);
 
// Error checking ...
 
// Convert to the proper byte-order
msg.to_host();
uint32_t valueA = msg.firstValue;
int16_t valueB = msg.secondValue;
char valueC = msg.thirdValue;

Notice how the parameters are still accessible by their name, and its not a function call. This is highly desirable for the code that I anticipate replacing with Alchemy. Data access like this is common all throughout the code base I have in mind. However, if this cannot be achieved cleanly, then I would be okay with a function call like one of these:

C++

uint32_t valueA = msg.firstValue();
int16_t valueB = msg.get_secondValue();

However, I am not going to settle until I at least investigate what the possibilities are, and how much work it would take to implement code structured around my first choice.

Analysis

It appears to me that there are three challenges to overcome in order to create a library that can be used like my target syntax.

  1. Safely and portably access data from a raw buffer with an objects data members
  2. Provide automatic byte-order conversion (How to know what fields to convert, and when?).
  3. Make the usage syntax similar to that of accessing data members in a struct

Item number one is where much of the trouble originates and a major motivation for this library. My initial thought is focused on the position of data fields within a structure, compared to where they maybe found in the raw buffer. Ideally they will match up 1:1, however, in practice we already know that does not happen due to the difference in hardware implementations. The sizeof operator is available and it gives us a part of the information that we need if we know what type or the name of the field that we are dealing with.

What if we take the address of a member data field in the structure, and subtract the address of the structure itself away from the members address; that would give us the offset of that field from the start of the structure. This is, in fact, what the offsetof MACRO does that can be found in the header file stddef.h. Here is an example of how offsetof could be implemented:

C++

#define osffsetof(s,m) \
  (size_t)&amp;reinterpret_cast( (((s *)0)->m)) )

Unfortunately, when I consult the C++ standard, it indicates that I should make no assumption for how the fields are represented in memory. The compiler is free to organize the data for classes and structures anyway it sees fit. This freedom is given to the compiler writers to allow them to determine the most optimal layout for a data structure on the target platform. As users of structs we should use the named value interfaces and not attempt to poke down under the covers abstracted by the compiler. Also, the behavior of the offsetof MACRO is undefined for bit-fields, and that is something that I would like to possibly support in the future.

Although I am fairly confident that most of what I need to do could be solved with a method like this, I will move on to a different approach, at least for now. offsetof will not create the most portable and robust solution. I am going to skip item one, and move on to two and three. They seem like they will require the same technique to overcome the challenges presented by both of these items. Knowing that C++ is capable of some very expressive syntax for user-defined objects due to operator overloading, I believe the approach to take to create a solution for all three items will be to create a data type to abstract individual fields, a proxy member

Proxy Member

A proxy member object will need to be defined as a type that matches the corresponding type that the proxy points to. We can probably overload the conversion operator for the proxy member's type. This will create the natural syntax of accessing a data member, even though it is actually a function call, the conversion operator. If we can get the user to call any type of function, we can handle the byte-order conversion and data accesses safe and portable. We will still need a way to automatically convert the data for each field type. If we could guarantee that the user would access every single data member, every single time a message went on or came off the wire we would have a solution. However, this seems unrealistic. So again, we will return to the automatic conversion of the data's byte-order.

Here is an example of an overloaded conversion operator for a C++ object:

C++

struct ProxyMemberLong
{
  long m_data;
 
  ProxyMemberLong(long value)
    : m_data(value);
  { }  
 
  operator long()
  {
    return m_data;
  }
};
 
// Usage:
ProxyMemberLong pm(100);
 
// Implicitly use the long conversion
// operator to assign 100 to value;
Long value = pm;

Generally it is wise to stay away from overloading the conversion operator, as well as value constructors. This is because the compiler is allowed to look for constructors and conversion operations on types that could potentially create a fit for a data type passed into a function. Insidious problems can appear due to the compiler implicitly converting an object from one type to another that was not intended. This type of issue is very difficult to track down. However, this looks like a promising solution, so I would like to at least investigate this path a little further.

I would also like to mention that you can use the explicit keyword with the constructors to prevent the compiler from implicitly using the constructor as a way to convert from one type to your objects type. In this case, the constructor needs to be explicitly called in order to be used. As of C++ 11 the explicit keyword is also available for use with the conversion operator. I will not be using explicit with the conversion operator because I do want the implicit conversion to occur for most of the situations. This is an issue we will need to keep in mind and revisit when we are further along to test for any potential problems this could cause.

Automatic Processing of All Members

For languages that support reflection, this would be a simple problem to solve. Reflection is a mechanism that allows a construct to query about itself to learn things like the names of function calls and data members. Since we are going to move forward and seek a solution that uses a proxy member object, we know that we will be able to perform the required processing before fields are accessed, but we cannot guarantee they will be accesses. We need a way to be able to iterate over all of the child members of a message object.

With an iterator we will not need to know the name of the parameter. Most likely we will have a pointer or a reference to the member data that we need to process. How can we go about doing that? The tuple from the C++ Standard Library seems like a promising candidate. The std::tuple is much like the std::pair, except that the number of sub-field types is not limited to two. In fact, the std::tuple behaves a lot like a compile-time linked list. Each entry has a head and tail node, allowing you to traverse to the next node in the tuple set. There are also quite a few utility functions provided that allow you to access an entry in the tuple with an index. The tuple seems very promising.

Next Step

In the next entry for Alchemy, I will explore how the tuple might be used to solve the challenges I am working with for this library. This will give us a chance to inspect some of the valuable and useful components in the C++ Standard Library that I have not used before, and possibly apply it to solve a problem. Once we verify this is a viable direction to continue with, we can develop the code for Network Alchemy a bit further.

An Eye on Refactoring

general, CodeProject, maintainability Send feedback »

Recently I ran across the article, "Is Design Dead?", from Martin Fowler's blog. Martin addresses the common misconception that design is discouraged in Extreme Programming. He describes the overall purpose of design in software and how the design emerges as part of the development phase. As more is learned about the problem domain, better decisions can be made and the design evolves with the implementation. Refactoring code is an activity that helps facilitate success with this approach.

At a different time I was learning about the structure of the human eye and some of the potential paths in evolution that could have led to the structure of our eyes today. I learned some surprising things with regards to how our eyes are structured. The evolved structure is counter-intuitive to what I would have imagined, especially when compared to the structure of a digital camera. I took a step back and starting thinking about the evolutionary path of the eye and compared it to typical events I have experienced during a software development cycle. I wanted to share the conclusions that I reached when I thought about these two topics.

Software Design Provides Flexibility

Design is an important aspect for any engineering discipline. Good designs allow for the development of a project to be divided into independent tasks. One of the most important benefits that can be realized from software design, is the ability to remain flexible to change throughout the project. Software is so valuable for that simple reason, the flexibility and relatively ease of change. Now I say relatively because if the project is not developed and managed properly, the structure of a program can become rigid and more resistant to change.

The tendency to resist change as a project progresses is what drives the concept of the Software Change Curve. This curve says that each progressive phase of development becomes exponentially more expensive to change the software from its original design. A concept that may only cost one dollar to analyze may be orders of magnitude more expensive to introduce after the product as been released.

The Waterfall process spends a large amount of time up-front attempting to analyze and plan to the current known set of requirements. Time can also be spent to try to identify the most volatile areas of the requirements to create flexibility at the points that may change later in the project. However, this is still a difficult task, which requires the ability to predict the requirements that are likely to change. No amount of planning can foresee all potential issues that will occur.

The XP approach of evolutionary design asserts that it is possible to flatten the software change curve by making design corrections during the development process. Some of the practices in XP are intended to facilitate the corresponding changes in software to match the updates to the design; I am referring to testing, continuous integration (CI), and refactoring. Testing and CI help synchronize a teams efforts when integrating changes with each other. Software refactoring is the practice that provides the agility to efficiently alter the software by simplifying the volatile regions of code.

Structure of the Eye

So how does the eye relate to all of this? Let me first describe the structure of the eye, and I will draw the connection for the structure of the eye and its similarity to software development. In many ways the eye is structured like any type of camera that has a lens. At the front there is the lens, and the back of the eye is the retina. The retina is the light-sensitive tissue that detects light and sends signals to the brain for processing. The component in a camera that corresponds to the retina would be the CCD or CMOS image sensor.

The CCD sensor faces the lens and captures incoming photons and generates an electrical charge proportional to the amount of light that it receives. The retina functions in a very similar manner with two exceptions.

  1. Chemical and electrical nerves are triggered to send signals to the brain.
  2. The photoreceptors in the retina are at the back of the retina.


Let's focus on item two. The optical nerves that transmit signals to the brain come out of the retina facing the lens. Therefore, Any light captured must travel through the layers of nerve fibers and other cells before they are detected by the photoreceptors. This also means there must be a location in the retina where the optical nerve passes back through the retina to the back of the eye and on to the brain, and there is; this point is called the Macula. It creates a blind spot in that area of vision for our eyes, that our brain fills in the missing piece, but that's another story.

Here is an illustration from Gray's Anatomy, which shows the forward facing part of the retina at the top, and the photoreceptors at the bottom:

Layers of the Retina, from Gray's Anatomy

The Code-and-Fix Process

The "Code-and-Fix" development process is what many software development projects devolve into at some-point in their lifetime; even if it's only a temporary situation. Basically, it evaluates what functionality is needed next, code the solution, and fix an errors that are detected. Once a feature is completed, the next feature is implemented in a similar fashion. After a non-descript period of time passes, and numerous cycles of this process the code base appears to have taken on a life of its own. The current project no longer matches any initial design work that may have been done before the project started. The source code has essentially evolved to meet the current needs.

Many people mistaken the "Code-and-Fix" process, with the practice of Evolutionary Design. That's because they are very similar to one another with the exception of one thing, Evolutionary Design prescribes that you must refactor regularly to simplify the current solution. By taking this step, your design decisions can be simplified by removing complexity from your system, and reintroducing flexibility. Remember, flexibility to change is what will help flatten the software-development curve. Refactoring is key to keeping your code nimble and adaptable to solve the next set of problems.

Back to Eyes

I now want to use the evolution of the eye as analogy of a "Code-and-Fix" development cycle without refactoring. I consider myself lucky to not require corrective lenses to see clearly, especially with so much time staring at a computer screen. Through my eyes, I think that evolution arrived at a pretty good implementation for an orbital ocular organ for me to sense light, track and focus on objects, and even adapt between high-contrast and low-light conditions.

Now consider how many millions of years vision took to evolve to this level. Also, the path that has led up to my eyes today, also has billions of other very similar versions evolving with each generation. The number of less-optimal mutations of the eye, which never came to be, must be orders of magnitude larger than the number of eyes currently on this planet. That is a lot of trial-and-error.

Refactoring

I think of "Code-and-Fix" as "Trial-and-error". This is a generally an expensive process to use with engineering. "Trial-and-error" becomes more expensive as the software development cycle progresses into the next stage. If you can remain cognizant of the issues that you have run into and apply this wisdom and experience towards altering the current implementation to be most beneficial to adapt to the next set of features, you have refactoring.

There is a little more to it than that, however, not much more. Refactoring source code is just like, well, it's just like factoring a fraction into a mixed number. You have a simpler form of the same thing. Refactoring is not intended to mean rework, re-implement, or create version 2.0. You are merely supposed to simplify the structure of your program while keeping the same functionality set. This is where unit tests are very valuable to help insure you do not break things that were previously working. A good rule of thumb, if you have to change your unit tests when you refactor code, you are probably doing more than refactoring.

Regardless, you must continue to analyze and simplify the structure of your software if you want to keep the software development curve relatively flat. Otherwise, the code will become rigid, and resistant to the addition of new features free of defects. This is essentially the cause for the exponential growth of cost in the curve. Taking that little extra time to reorganize your code as you develop can payoff by allowing new features to be more easily developed. That makes more time for you do other things such as take on new challenges, or surf the Internet.

Summary

Evolution is a complex process that takes a lot of time, more time than we are given to complete a project. Evolution takes a lot of resources because it is a process that is based on Trial-and-Error. Code-and-Fix often is a Trial-and-Error process as well. There are more efficient ways to develop code. I would like to add that I do not think there is a single process that is suitable for every situation. Whether you design completely at the beginning, or let your design evolve throughout the development of your project, one of your goals is to keep your code base flexible. A code base that can easily adapt to new requirements and unforeseen circumstances, is a valuable code base indeed. The cost of development during progressive phases of development can remain relatively flat, as opposed to increasing exponentially. Because It will be easier to modify, easier to understand, and easier to maintain. Continual refactoring is a key to remaining nimble.

Byte Sex

adaptability, portability, CodeProject, C++, Alchemy Send feedback »

Byte-gender; not, "Yes! Please!"
Good! Now that I have your attention let's solve a relatively simple problem, byte sex. A less sensational name for this concept is byte endianess. This is one of those concepts that you should at least be aware of, even if you don't have to pay much attention to it in your day-to-day work. Each CPU architecture has it's own definition for memory. One of these properties is the endianess format of data registers. This is the first issue that I address for Network Alchemy.


Endianess

Endianess defines the order bytes are arranged within a word in machine hardware. There are two commonly used types, big-endian and little-endian. Other formats do exist, however, they are rare. Endianess is often mentioned with the context of network communication. Be aware that it must actually be addressed for any medium used to transfer data from one machine to another. This includes binary file formats.

  • Big Endian: Big Endian format places the most significant byte to the left of the byte sequence. Essentially, the byte sequence starts with the most significant byte, and ends with the least significant byte. This maps to the same format that we represent numbers.
  • Little Endian: The least significant byte is at the left of the byte sequence.
  • Network Byte-order: The byte-order format used to transfer data between two different machines. Big-endian byte-order format is used for network byte-order by convention.
  • Host Byte-order: The local machine's byte order format.

The description given at Wikipedia contains a more thorough treatment of this subject.

Traditional Solution

A small set of functions are usually provided with the socket libraries for a platform. These functions will perform a byte-order conversion for integers represented with multi-byte formats. The set of supported functions varies between platforms. You can generally count on this set of four to exist:

  • htons: Converts a 16-bit integer (short) from host to network byte-order.
  • ntohs: Converts a 16-bit integer (short) from network to host byte-order.
  • htonl: Converts a 32-bit integer (long) from host to network byte-order.
  • ntohl: Converts a 32-bit integer (long) from network to host byte-order.

C++

unsigned short s_before = 0xC0DE;
unsigned long  l_before  = 0x600D1DEA;
unsigned short s_after = htons(s_before);
unsigned long  l_after = htonl(l_before);
The results for values converted by htonXX functions
Endianess Type Before Before (hex) After After (hex)
Big short 0xC0DE 49374 0xC0DE 49374
Big long 0x600D1DEA 1611472362 0x600D1DEA 1611472362
Little short 0xC0DE 49374 0xDEC0 57024
Little long 0x600D1DEA 1611472362 0xEA1D0D60 246222176

Little-endian systems are the only systems that will require a modification of data. The call to htonXX() functions will not generate any code on big-endian type systems. The results in the table will be the same if the same data is input to the ntohXX(). In fact, the implementation for ntohs() could be implemented like this:

C++

inline
unsigned short ntohs(
  unsigned short netshort
)
{
  return htons(netshort);
}

Potential Problems

I have experienced these two issues, related to the byte-order conversion functions, creeping into a project. This message structure and byte-order conversion function will be used for reference to demonstrate these problems.

C++

struct DataMsg
{
  int   count;
  short index;
  unsigned char code;
  unsigned long value;
};
 
void ConvertMsgToHost(DataMsg &amp;msg)
{
  msg.count = (long) ntohl( (unsigned long)msg.count);
  msg.index = (short)ntohs((unsigned short)msg.index);
  msg.value = ntohl(msg.value);
}

Inconsistent Conversion Calls

If a strong pattern of implementation is not created and followed with the message transport process, more care will be required to keep track of the state of a message buffer. Has the buffer already been converted to network byte-order? If a buffer that has already been converted to network byte-order is converted a second time, the result will be returned to the host byte-order.

Mistake #1

C++

// Calling the convert function an even number of times
// will return the data to its original byte-order:
ConvertMsgToHost(msg);
 
// ... later called on the same message.
ConvertMsgToHost(msg);

Mistake #2

C++

// Developer is unaware that
// ConvertMsgToHost exists or is called:
ConvertMsgToHost(msg);
 
// ... later
// ERROR: The result returned is in network order.
long value = ntohl(msg.value);

Field Type Changes

Many times the field types in a message my change. It is possible for the type of field to be changed, but the byte-order conversion function to remain unchanged. This is especially true because of the tendency to use explicit casts with these functions. If this change goes undetected, data values will be truncated and incorrect values will be transported across the network.

C++

// Noted types are changed in the message format below:
struct DataMsg
{
  int   count;
  size_t index;        // Changed from short
  unsigned short code; // Changed from unsigned char
  unsigned long value;
};
 
// The mistake occurs if the conversion
// function is not properly updated:
void ConvertMsgToHost(DataMsg &amp;msg)
{
  msg.count = (long) ntohl( (unsigned long)msg.count);
 
  // The explicit cast will force this call to succeed.
  // Error: data is truncated and in wrong order
  msg.index = (short)ntohs((unsigned short)msg.index);
 
  msg.value = ntohl(msg.value);
 
  // The value msg.code will not be properly converted
}

Generic Solution

One way to improve the maintainability of your code is to use solutions that are highly consistent. When compared to the traditional approach, our solution will have a more consistent implementation by the method that we handle the context sensitive information of the solution. I am referring to: 1) the data-type to be converted, 2) the host byte-order, 3) the target byte-order of the data. If any of the field types in our DataMsg struct changes, our converter function will continue to be valid without any required changes. The EndianSwap function simply knows what to do. This does not yet resolve the issue of inconsistently converted messages. We will address that after we have a robust and consistent method to swap the byte-order of data fields.

C++

void ConvertMsgToHost(DataMsg &amp;msg)
{
  msg.count = EndianSwap(msg.count);
  msg.index = EndianSwap(msg.index);
  msg.Code  = EndianSwap(msg.code);
  msg.value = EndianSwap(msg.value);
}

We can create a function like EndianSwap that will take the appropriate action regardless of the type of field passed into it. The socket byte conversion functions are written to be compatible with C. Therefore, a different name must be given to each function, for each type supported. Function overloading in C++ will allow us to create a set of functions that can be used to generically convert the byte-order of many different types of fields. This still leaves the problem of calling the convert function an even number of times returns the data format to it's original type. We will revisit this once I create the first part of the solution.

Byte-Order Swap

Because a large variety of types may be encoded in data, we will start with a template-based approach to create a generic EndianSwap function. This will allow us to create sets of solutions and reuse them, rather than duplicating code and giving a new function prototype to each function. The base implementation will provide an empty solution that simply returns the input value. The compiler will optimize away the function call and result assignment. This effectively turns this call into a no-op:

C++

template < typename T >
inline
T EndianSwap(T input)
{
  return input;
}

A specialization of this template will be implemented for each type that requires byte-order conversion logic. Here is the implementation for unsigned 16-bit and unsigned 32-bit integers.

C++

template < >
inline
uint16_t EndianSwap(uint16_t input)
{
  return  (input << convert ::k_8bits)
        | (input >> convert ::k_8bits);
}
 
template < >
inline
uint32_t EndianSwap(uint32_t input)
{
  return  (input  <<  convert ::k_24bits)
        | ((input >> convert::k_8bits) &amp; 0x0000FF00)
        | ((input <<  convert ::k_8bits) &amp; 0x00FF0000)
        | (input >>  convert::k_24bits);
}

I chose to implement my own set of byte-order swap functions for a couple of reasons.

  1. To remain independent of system socket libraries. The functions are not portable implemented or available
  2. There is now only one byte-order conversion function rather than two with different names
  3. Added flexibility; The socket functions become no-ops on big-endian solutions, where as EndianSwap will always swap.

Another way we will improve upon the existing byte-order conversion functions is by providing a specialization for the signed types. This is necessary to eliminate the need to provide a cast with calls to these functions. The implementations for the signed versions can be implemented in terms of the unsigned definitions. However, care must be taken to avoid conditions that would create an integer overflow condition. Overflows with signed integers results in truncated data.

C++

template < >
inline
int16_t EndianSwap(int16_t input)
{
  return static_cast < int32_t >(
    EndianSwap(static_cast < uint16_t >(input))
  );
}
 
template < >
inline
int32_t EndianSwap(int32_t input)
{
  return static_cast < int32_t >(
    EndianSwap(static_cast < uint32_t >(input))
  );
}

Manage Context Information

We now have a consistent method to swap the byte-order for any data-type that we choose. However, we still need to account for the other types of context sensitive information for this solution to be useful. We have two additional pieces of context information:

  • Big Endian / Little Endian
  • Host Byte-order / Network Byte-order

Two types of context information with binary values means we will have 4 possible solutions. Here is a first attempt to create a solution that incorporates all of the pieces:

Constants deduced from compiler settings and platform header files:

C++

/// Platform Endian types
enum Endianess
{
  k_big_endian    = 0,
  k_little_endian = 1    
};
 
/// Constant indicates machine endianess.
const Endianess k_endianess = Endianess(NA_ENDIANESS);

Host-order conversion function

C++

template < typename T>
inline
T ToHostOrder(T input)
{
  if (k_little_endian == k_endianess)
  {
    return EndianSwap(input);
  }  
  else
  {
    return input;
  }
}
 
// A function called ToNetworkOrder is also
// implemented with the identical implementation.

At this point we have two separate functions, that both handle two cases. This manages our four distinct possibilities for combinations of context-sensitive information. However, this is not the final solution. In fact, this solution has all of the same issues as the socket library calls, except we can handle any type of data. We have even added a runtime cost to the implementation with an if statement.

Improve the Solution

We are going to put the compiler to work for us to improve this solution. Templates are an excellent option when you have all of the information you need at compile-time. The solution in the previous step used two runtime mechanisms to manage the context-sensitive information, a function call and a conditional. Let's create a template that will let the compiler decide if it is necessary to swap the order of bytes for a data-type rather than a runtime conditional statement.

Generic EndianSwap template to swap based upon the endian-type of the machine.

C++

// Default template implementation
// This version always performs a swap.
template < typename T, bool isSwap >
struct EndianType
{
  static
  T SwapOrder(const T&amp; value)
  {
    return EndianSwap(value);
  }
};

EndianSwap specialization that does not swap the order of bytes.

C++

// The false value is set for the isSwap field
// This is the selector to prevent the byte-order swap
template < typename T >
struct EndianType < T,false>
{
  static
  T SwapOrder(const T&amp; value)
  {
    return value;
  }
};

Template meta-programming solutions require all of the information to be known up front, and any decisions need to be calculated by the compiler. Therefore, constants and data-types become the primary mechanisms used to store information rather than variables. The compiler must have all of the answers fixed in-place to determine which pieces to use for construction of the logical statements. We now have a new struct with a static function to conditionally swap the order of bytes in a data-type. Let's connect it to the final piece of the solution.

We will shift another piece of the context-sensitive information from a variable to a type. The message endian byte-order will be encoded in this type. This object handles for conversion of data that is in host byte-order. The ToHost function call is a no-op, and the ToNetwork will provide the byte-order conversion.

C++

template < Endianess E >
struct HostByteOrderT
{
  static const
    Endianess order = E;
 
  static const
    bool       isHost = true;
 
  template < typename T>
  static
  T ToNetwork(const T&amp; input)
  {
    return EndianType < T,
                        (k_big_endian != order)
                      >::SwapOrder(input);
  }
 
  template < typename T>
  static
  T ToHost(const T&amp; input)
  {
    return input;
  }
};

Here is the corresponding implementation for the network byte-order type.

C++

template < Endianess E >
struct NetworkByteOrderT
{
  static const
    Endianess order = E;
 
  static const
    bool       isHost = false;
 
  template < typename T>
  static
  T ToHost(const T&amp; input)
  {
    return EndianType < T,
                        (k_big_endian != order)
                      >::SwapOrder(input);
  }
 
  template < typename T>
  static
  T ToNetwork(const T&amp; input)
  {
    return input;
  }
};

These two typdefs will simplify usage:

C++

typedef HostByteOrderT < k_endianess > HostByteOrder;
typedef NetByteOrderT  < k_endianess > NetByteOrder;

Usage

All of the pieces are in place to have the compiler generate context-sensitive code, based upon the machine architecture, and the desired target endian byte-order. It may not be obvious, but all of the components exist for us create a conversion function to safely convert data between byte-order types. We can even prevent a mishap from occurring by inadvertently converting a data-type from host-order twice.

The key is within the types that allow us to indicate of a value is in host or network byte-order. To create a message whose byte-order is properly managed, encode its endian byte-order with a template.

C++

template < typename T>
struct DataMsg
  : T
{
  int   count;
  short index;
  unsigned char code;
  unsigned long value;
};
 
typedef DataMsg< HostByteOrder > DataMsg_Host;
typedef DataMsg< NetByteOrder >  DataMsg_Net;

The corresponding conversion function for network-to-host conversion:

C++

// This function will only convert
// network types to host-order.
// The output is into a host-order type.
template < typename T>
void ConvertMsgToHost(
  const DataMsg_Net  &amp;in,
        DataMsg_Host &amp;out
)
{
  out.count = DataMsg < T >::ToHost(in.count);
  out.code  = DataMsg < T >::ToHost(in.code);
  out.index = DataMsg < T >::ToHost(in.index);
  out.value = DataMsg < T >::ToHost(in.value);
}

Summary

The solution created in this entry is a fairly independent piece of code. This goal of this solution is to provide a generic structure for how byte-order conversions are performed. This will ensure they are performed consistently over time, and hopefully reduce the chances of misuse. The topic of IPC is already dancing near the edges of type-safe data. Anything that we can do to keep type information around as long as possible will help improve the quality and correctness of our software.

Before we can progress much further with the Network Alchemy library, I will need to provide some foundation in template meta-programming concepts. Therefore, the next few entries related to this library will be focused on concepts, and a design for the next phase of the library.

My Unit Test Environment

CodeProject, C++, maintainability, Alchemy Send feedback »

I discussed the merits of selecting a suitable unit test framework for your development project in my previous post. I described the qualities that I found most valuable in the test framework that I use, CxxTest. The qualities are xUnit framework, portability, simplicity, and flexibility. There are other frameworks for C++ that contain many more features, however, rarely have I had to expand on what is provided in order to test something. Moreover, CxxTest is lightweight enough, that other test tools can be integrated with it, such as Google's GMock library.


Resources

I want to describe my test environment in detail since this will be the same environment that I will use to build and verify Network Alchemy.

Visual Studio Project Wizard: CxxTest

Integrated Tools

I saw benefits immediately when I first started experimenting with unit tests. I wrote a set of tests for a specialized string class I had recently written. That exercise alone helped me uncover 3 or 4 bugs that had existed in the class even though it had been in use for over two years. The thing that took a little longer to uncover was how cumbersome it became to create new unit test projects. Ideally you create a new unit test suite for each object.

I thought I that I needed to make this aspect simpler in order to have a chance of this being adopted by the other developers on my team. Therefore, I created a Visual Studio Wizard to quickly generate a new test project for me, as well as a class wizard to add a new test suite to the project. A project can contain multiple suites, however, I would only put multiple suites in the same project if they were closely related. It's best to minimize dependencies in your test suites, because of the tendency for this to help minimize the dependencies in your objects.

I also setup a Make system to be able to build my projects on Linux and other platforms. I have added these Visual Studio project wizards to my site for you to download and use if you are interested. More details are located below to describe tool requirements, installation and usage instructions. These files are located in the base directory of the zip file resources. You can use these Make files as a reference to integrate CxxTest into your own build environment.

  • \Makefile: The top-level make file
  • \Makefile.unittest: A make file specific to each unit test.

Requirements

This list describes what tools are required to use this integrated test environment that I have developed.

CxxTest

The CxxTest framework needs to be installed on your system:

Python

The Python scripting engine must be installed to generate the test runners:

Visual Studio

I have successfully used the CxxTest Project Wizard integrates with these versions of Visual Studio. I have verified the wizard works properly in Visual Studio 2013 Express. I believe it should also work in previous Express versions, possibly with minor modification:

  • Visual Studio 2005
  • Visual Studio 2008
  • Visual Studio 2010
  • Visual Studio 2012
  • Visual Studio 2013

Installation

I have customized a JavaScript file that was originally included with the WTL installation wizard. This script is in main folder of the unit test zip file. Running this script will search for installations of Visual Studio on your system by looking up a key in the registry. If it detects an installation the appropriate wizard files will be copied into the C++ wizard directories of that install. A message box will appear when the script completes. This will list all of the versions of Visual Studio that were detected and for which the wizard was installed.

Install Complete Message

Customize to Your Environment

In the past I was able to create a very flexible project configuration that allowed the tool locations to be configured with a Visual Studio Property Sheet. This is either a .vsprops or a .props file depending on which version of Visual Studio you are using. Unfortunately, the API that I used in the wizard to associate this configuration property sheet with the project is not supported in JavaScript for Visual Studio 2010 and newer. Therefore, this became a manual step in my own environment. I have still distributed the property sheet files that I created with the wizard. However, I have chosen a solution that is less flexible but provides more convenience in test creation.

There are a variables that I have placed at the top of a few files that are responsible for configuring the location to the Python and CxxTest installations. These are the variables and files to modify before you run the installation script:

  • /files/AppWiz/Scripts/1033/default.js: Project Wizard Install script. Set both of these paths to indicate where python and CxxTest have been installed so the build tool can access them during compilation.

    var pythonPath = "C:\Python34\python.exe";
    var cxxTestPath = "C:\Development\CxxTest";
  • /SetupCxxTest_VS.js (Optional): Install script for registered versions of Visual Studio. Change this to set the name of the category the test wizard appears in Visual Studio under C++ Wizards.

    var categoryDir = "CodeOfTheDamned";
  • /SetupCxxTest_VS - Express.js (Optional): Install script for Express versions of Visual Studio. Change this to set the name of the category the test wizard appears in Visual Studio under C++ Wizards.

    var categoryDir = "CodeOfTheDamned";

Usage

There are two types of wizards that I have developed to simplify the creation of unit test suites for Visual Studio and CxxTest.

Unit Test Project Wizard

The project wizard is essential for the start of any project. Since CxxTest requires a two step process to generate, then run the unit tests, I have configured this type of project to handle this steps as one. Therefore, all the developer is left to do is develop their code in the unit test harness as they would if it were any simple driver program. Except the boilerplate code for a test harness is already setup.

1. Create a new project. Use the CxxTest Wizard from the category you have configured.

New Test Suite Wizard

2. Give the test suite class a name and your basic comments.

Basic settings screen

Once the wizard has completed, you will have a shell project, similar to a default console project that Visual Studio creates. This project will be a unit test suite named by you, with file comments at the top. There are stub entries for the constructor, setup and teardown routines, and a single test case. Here is the structure of the project:

  • /TestSuite
    • (Place all utility and shared test suite files in this directory)
    • /Src
      • (All test suite header definition files will be placed in here)
      • TestSuite.h
      • /Generated
        • (Files in this directory are automatically generated)
        • TestSuiteRunner.cpp

    If all of the tools are configured properly, you should be able to successfully build the project. Output similar to this should be expected:

    1> ------ Build started: Project: TestSuite1, Configuration: Debug Win32 ------ 
    1>  A subdirectory or file ./Src/Generated/ already exists
    1>  NewTestSuiteRunner.cpp
    1>  TestSuite1.vcxproj -> c:\output\TestSuite1.exe
    1>  Running 1 test.OK!
    ========== Build: 1 succeeded, 0 failed, 0 skipped ==========

    Add Unit Test Suite

    If you would like to add a second test suite to an existing test project you can use the class wizard to generate another test suite object file. You will see the same dialog as the project wizard, which asks you for an object name, comments and author. The difference is this object will be added to your selected project. You can access the class wizard from the following menu:

    • Project | Add Wizard...

    This time the type of project is called a Test Fixture.

    Summary

    The relatively little amount of time I spent to better integrate my test environment with my development environment has been time well spent for me and my team. I have been using basically this same unit test wizard since 2009, and I have used it with all of the major releases of Visual Studio since 2005. Whatever tool you select for your development, make sure that it is easy to use. The point is to encourage the development and maintenance of unit tests for your software; not to introduce yet another tool or step in the process for the developers to fight.

Contact / Help. ©2024 by Paul Watt; Charon adapted from work by daroz. CMS / cheap web hosting.
Design & icons by N.Design Studio. Skin by Tender Feelings / Skin Faktory.