|« Alchemy: Vectors||C++: Type Decay »|
A continuation of a series of blog entries that documents the design and implementation process of a library. The library is called, Network Alchemy[^]. Alchemy performs low-level data serialization with compile-time reflection. It is written in C++ using template meta-programming.
Once Alchemy was functional and supported a fundamental set of types, I had other development teams in my department approach me about using Alchemy on their product. Unfortunately, there was one type I had not given any consideration to up to this point, arrays. This group needed the ability to have variable sized messages, where the array payload started at the last byte of the fixed-format message. At that point, I had no clean solution to help deal with that problem.
Expanding the type support
This request brought two new issues to my attention that I had never considered before. Both of these features needed to be added to Alchemy for it to be a generally useful library.
- Support for arrays or sequences of the same type
- Support for variable-sized structures. Every message type in Alchemy is currently fixed in size.
I chose to handle these issues as two separate types. Primarily because I believed that allowing fixed-size fields to remain as a fixed-size definition would have a better chance of being optimized by the compiler. I wanted to use a completely separate data type for message definitions that required a dynamically-sized buffer.
I like the C++ Standard Library very much. I also use it as a model when I am designing interfaces or new constructs. Therefore, I decided to mimic the
vector types from the standard library. I will cover the challenges that I encountered adding support for the
array in this entry. The next post will focus on the
vector and how I chose to solve the new problem of dynamically sized message objects.
Defining an Alchemy Array
Even before I could figure out how the code would need to be modified, and what specializations I needed to accommodate an array type, I needed a way to declare an array in both the
TypeList and the Hg message definition. The simple and natural candidate was to jump to the basic array syntax:
This is when I discovered the concept of Type Decay[^], and that I lost the extra array information for my declaration. This problem was simple enough to solve, however, because of the obscure work-around involved, I didn't think that this would a good enough solution. This solution would be fraught with potential for mistakes.
This is when I decided that while I would allow traditional array declaration syntax, the syntax I would promote would be based on the
Again, this caused one new wrinkle. The std::array definition is not legal in the HG_DATUM MACRO that is used to declare a field entry within the Hg message format, due to the extra comma. The pre-processor is not smart enough to parse through angle-brackets, therefore, it sees three parameters for a MACRO that it only expects to see two parameters.
[sigh] Once again, this has a simple solution; simply wrap the template argument of the MACRO within parenthesis.
And once again [sigh], I thought this would lead to simple errors that would not have an intuitive solution. We are working with the pre-processor after all. This is one area where I do believe it is best to avoid the pre-processor whenever possible. However, it would just be too painful to not take advantage of it's code generating abilities.
The best solution then was to add a new HG_DATUM MACRO type to support arrays.
With a simple MACRO to create the correct declaration of the template form for a std::array, I can re-use the error-prone form internally, hidden behind the preferred array MACRO.
Blazing new trails
The difficult first step was now behind me. The next step was to create a
DataProxy specialization that would allow the array to behave like an array, yet still interact properly with the underlying
Datum that manages a single parameter.
There are many more ways an array can be classified as far as types are concerned for tag-dispatching. Therefore, I then created a set of type-trait definitions to identify and dispatch arrays. I was also dealing with the addition of vectors at the same time, so I will include the definitions that help distinguish arrays.
These were only the type-definitions that I would use to distinguish the types to be processed. I still needed some discerning meta-functions to identify the traits of a
We're not done yet. We still need a value test to identify natively-defined array types. For this one, I create a few utility meta-functions that simplified the overall syntax, and made the expression easier to read. I believe I have mentioned them before, if not, this is Déjà vu. The utility templates are
One final set of tests were required. I needed to be able to distinguish the sequence-types from the fundamental-types and the type-containers.
Are you looking back at the tag-dispatch identifiers thinking what I thought when I reached this point?
"Shit just got real!"
If this code were a NASA astronaut candidate, it would have just passed the first phase of High-G training[^]. Most likely with 'eyeballs out', and to top it all off, we avoided G-LOC without wearing G-suits.
Back to Earth
A new piece of information that was required was the extent of the array (number of elements). At this point in time, I have started to become quite proficient at determining how best to extract this information. Given a single type T, how can I extract a number out of the original definition?
This is why we went through the effort to avoid Type Decay. Because somewhere inside of that definition for type T, hides all of the information that we need.
We have declared a default template without an implementation called
array_size. If that were the end, any attempt to instantiate
array_size would result in a compiler error that indicated no matches.
Therefore, we create a specialization that will match the default template for our array type. Furthermore, we define our specialization in such a way that will extract the extent (element count) from the type, and become a parameterized entry in the template definition. The specialization of the template occurs at this point in the declaration:
std::array<T, N> becomes a single type, it qualifies as a valid specialization for the default declaration without an implementation. The
std::array of specialized definition explicitly indicates that we only want matches for the array. Therefore, we were able to extract both the original type and the extent of the array. In this case the extent is defined as a
std::integral_constant and the type T is discarded.
This technique will appear many more times through-out the solution where we will use the type and discard the extent, or even use both values.
DataProxy<array_trait, IdxT, FormatT>
It's time to demonstrate some of the ways that the array's
DataProxy differs from the other types that have already been integrated into Alchemy. First, the standard
typedefs have been added to the array's proxy to match the other types:
The extent is referenced many times throughout the implementation, therefore, I wanted a clean way to access this value without requiring a call to the previously defined
One more new type definition is required. Up until now, the type that we needed to process in the structured message, was the same type that was defined in the message. A slight exception is the nested-type, however, we were able to handle that with a recursive call.
These new sequence containers, both the array and vector, are containers themselves that contain a set of their own types. These are the types that we actually want to consider when we programmatically process the data with our generic algorithms. Here is the array proxies definition of the
The only a few remaining pieces that are new to the array's
Some new ways to query for structure sizes. One method will query the extent of the array, the other queries the number of bytes required to store this construct in a buffer.
The set operations get optimized implementations that depend on standard library algorithms. There is also an override implementation to accept natively defined arrays as well as the
Finally, here is a small sample set of how the proxy pass-through functions are implemented to forward calls to the internal array instantiation.
Now let's start the real work
Believe it or not, all of the previous code was just the infrastructure required to support a new type.
And, believe it or not, because of the orthogonal structure, generic interfaces, type generators and large amount of Mountain Dew that has been used to build this framework, there are only a few small specializations left to implement in order to have a fully-supported array data type in Alchemy.
It may be helpful to review this previous topic on how I have structured the Serialization[^] operations for Alchemy. However, it isn't necessary to understand how processing the individual data within the array functions.
Here is the declaration of the array byte-order conversion meta-function.
Here is the actual implementation for converting the byte-order elements in the array:
I would like to draw your attention to the real work in the previous function. The majority of the code in the previous snippet is used for declarations and type definitions. The snippet below only contains the code that is performing work.
"That's all I have to say about that."
Generic programming is powerful. There is no reason C++ must be written as verbosely as C is often written. Alchemy is production-quality code. The error handling is in place; in most cases it occurs at compile-time. If it won't compile, the program is not logically correct and would fail at run-time as well.
I did not demonstrate the
unpack operations for the array. They are slightly more complicated because of the nature of this container. When I started to explore real-world scenarios, I realized that I may run into arrays-of-arrays and arrays-of-nested-types-that-contain-arrays.
The solution isn't much more complicated than the byte-order converter. However, it does require a few more specialized templates to account for this potential Cat-in-the-Hat absurd, yet likely, scenario. The next entry will describe how I expanded Alchemy to support dynamically sized messages for vectors. Then a follow-up article will demonstrate how the array and vector types are serialized in Alchemy, and are capable of handling a deep nesting of types.