This presents a case study using modern C++ to solve a particular problem that came up in a project that I'm working on: making property queries to a CalDAV service. The nature of the problem is such that while the mechanics of making queries can be expressed in generic terms, the challenge in implementation is to be able to handle any particular specific query without becoming either ineffective (meaning difficult for the programmer to use: repetitive or error-prone) or inefficient. The objective I set myself was to see if it was possible to apply compile-time techniques to support application-specific queries in a way that is both efficient and effective.
While in my experience case studies aren't naturally of interest to a wide audience because of their specific nature, the problem I outline here is different enough from the typical ‘generic type’ applications of compile-time technique that I thought it could at least spark an appreciation of what is possible; even if the case itself is arcane. Probably similar techniques can be applied to other remote query technologies; such as a SQL ORM. To keep the discussion at a reasonable length, I'll gloss over or completely avoid much irrelevant detail.
The program I'm developing is a utility that makes requests to a CalDAV service. Roughly, CalDAV is a protocol (or rather, a sprawling collection of RFC specifications) for calendaring-related services, based on WebDAV, which is itself is based on HTTP and XML. The WebDAV model extends and refines HTTP into a collection of resources which may have arbitrary XML-valued properties associated with them. Some of these properties are defined by WebDAV, while others are specific to CalDAV. The point is that the universe of properties is open-ended and certainly not consistently structured.
WebDAV properties are accessed using the PROPFIND HTTP verb defined for this purpose and an XML-formatted HTTP body. The ‘outer structure’ of the request body consists of some XML defined by WebDAV indicating that a property query is being made, and the ‘inner structure’ of XML that can defined by WebDAV, CalDAV, or any other specification defining the specific properties being requested. For example:
<?xml version="1.0" encoding="utf-8" ?> <D:propfind xmlns:D="DAV:"> <D:prop><D:current-user-principal/></D:prop> </D:propfind>
Conversely, the HTTP response body consists of XML defined by WebDAV at the outer level and by the respective specifications at the inner level containing the requested properties:
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <multistatus xmlns="DAV:"> <response xmlns="DAV:"> <href>/123456789/principal/</href> <propstat> <prop><current-user-principal xmlns="DAV:"> <href xmlns="DAV:">/123456789/principal/</href> </current-user-principal></prop> <status>HTTP/1.1 200 OK</status> </propstat> </response> </multistatus>
Early on I opted for an event-driven (as opposed to tree-driven) XML parser to process the response bodies. There were several reasons for this, but for the sake of the discussion here consider just that the amount of data returned can be relatively large (in the order of megabytes). To abstract the actual response handling from the implementation of the parser I defined a data structure that declares the XML tree structure of the expected response and the handlers for the response values. This way, each particular kind of query for some given set of properties can declare its specific ‘handler’ data structure while keeping the parser generic.
Nothing too unusual here. Note what needs to be done within the design to support each ‘kind’ of query:
Good software design dictates that we design the implementation of items 1 and 2 close together, as the form of the request and the structure of the response are tightly coupled; but to keep item 3 separated (as there are arbitrary ways of processing a response to a given query). Similarly in the interest of proper design we may add:
Item 4 applies common-sense abstraction, item 5 future-proofs the design, and item 6 expresses the ‘Don't Repeat Yourself’ principle.
All the above design guidelines can be addressed within the style of classical C++ and run-time mechanisms: given a query for some specific set of properties 1) the request XML and 2) the parser data structures can be statically constructed; 3) the response handler can be exposed as a class with virtual member functions which also contributes to the abstraction required by 4). Item 5) is slightly trickier to implement and requires that all the preceding items are implemented separately and ‘connected’ at run time:
Inserting the ‘inner’ into the ‘outer’ XML can be done in any well-known number of ways; for illustration I show this method that I sometimes use that employs a stack-based/no-heap allocation:
// construct PROPFIND XML body static const char bodyTemplate[] = R"(<?xml version="1.0" encoding="utf-8" ?><D:propfind xmlns:D="DAV:">%s</D:propfind>)"; const unsigned bodyN = sizeof bodyTemplate + (-2 + strlen(property)); char *const body = static_cast<char*>(alloca(bodyN)); const unsigned bodyL = snprintf(body, bodyN, bodyTemplate, property); assert(bodyL == bodyN - 1);
The XML parser uses data structures representing parse state and state transitions; for illustration:
const StateParser::State::Transition
WebDAV::PropertiesResponse::gTransitionsFromProperty[] = {
{ L"creationdate", &gStateCreationDate },
{ L"displayname", &gStateDisplayName },
[…]
{}
};
const StateParser::State
WebDAV::PropertiesResponse::gStateCreationDate {
&gStateProperty, {},
nullptr, nullptr,
static_cast<void (StateParser::Response::*)(const XMLParser<StateParser>::String)>(
&PropertiesResponse::CreationDate
)
},
WebDAV::PropertiesResponse::gStateDisplayName {
&gStateProperty, {},
nullptr, nullptr,
static_cast<void (StateParser::Response::*)(const XMLParser<StateParser>::String)>(
&PropertiesResponse::DisplayName
)
},
[…]
The advantage of these is that they are static and available without further construction when the program is loaded.
The response handlers are represented by a simple abstract base class that is overridden by the caller.
/* Response
Handle specific events in document
This allows the entire document response to be flattened into a single callback object
*/
struct Response {
// needs to contain at least one virtual method; or pointer-to-member-functions don't look for a vtbl
virtual void StartElement(String namespaceURI, const String name, Attributes attributes) {}
virtual void EndElement(String namespaceURI, const String name) {}
virtual void Characters(String) {}
};
However, depending on the complexity of the query and the properties being requested, the response subclasses are nontrivial to write and error-prone.
Using the above approach to support general queries for some set of properties not known at design time seems like it ought to be possible using some kind of ‘constructive’ approach and classes for each possible property type. This would require a bit more work at design time, but more significantly by the implementor as well: the desired property classes would have to be instantiated and strung together by the application.
If we wanted to simplify things for the implementor, we could try to abandon the ‘clean’ class-constructive design and simply put everything in a single class. This is essentially the ‘specific query’ scenario we described previously; but supporting arbitrary general queries within a single easy-to-use class isn't easy to do well. It suggests either that we anticipate every possible property that a user might want to query for and implement a run-time switch to enable the desired properties (which goes against the open-endedness design constraint); or expose details of the WebDAV protocol so that the caller can construct the exact required query himself.
I can imagine a way of doing it using only run-time mechanisms; but at this point it becomes worth asking whether it isn't possible to accomplish what we want using compile-time techniques—and this is what I describe next.
Note that I've overlooked mentioning the performance implications of run-time polymorphism. While this is often given as an argument in favor of a compile-time approach, in this case I find it mostly unpersuasive: any performance penalty incurred by virtual function or other run-time dispatching would be dwarfed by the overhead of the CalDAV request itself; so I don't really consider it to be a serious consideration. The only run-time performance impact that is actually important are the demands placed on the CalDAV server— which clearly eliminates from serious consideration any kind of solution that is based on querying ‘all’ or ‘most’ properties and then only handling the ones of interest.
Off the bat, it is important to be clear on exactly what and what we are not attempting to do at compile time. Specifically, I'm not looking to change the state-driven XML parser itself: the only possible point of ‘unrolling' the parser for a given request would be a speed improvement, which I've already explained is not a real concern and would come at the cost of potentially significant code bloat. I do want the items specifically mentioned above to be constructed at compile time while still keeping the design goals in mind. Let's address them individually:
The ‘outer’ XML structure that is common to all property queries and the ‘inner’ structure specific to the individual query can be constructed into static constexpr member variables:
template <class A, class... Is>
struct WebDAV::PropertiesState {
static constexpr std::string_view
gStartTag = "<D:prop>",
gEndTag = "</D:prop>";
// length of XML query string
static constexpr std::size_t gXMLL = gStartTag.size() + Transitions<Is...>::gXML.size() + gEndTag.size();
// XML query string
static constexpr std::array<char, gXMLL + 1> gXML = []() {
/* If the array is too short for the string, compilation will fail due to a call to "_CrtDbgReport" */
std::array<char, gXMLL + 1> result {};
// concatenate string into 'result' (note 'mutable' to maintain the iterator between invocations)
auto append = [resultAt = result.begin()](const std::string_view &s) mutable {
resultAt = std::copy(s.begin(), s.end(), resultAt);
};
append(gStartTag);
/* Note that you must construct using an explicit size; otherwise we'll try to read past the end
of the array at compile time, looking for the NUL terminator. */
append(std::string_view { Transitions<Is...>::gXML.data(), Transitions<Is...>::gXML.size() });
append(gEndTag);
return result;
}();
[…]
}
WebDAV::PropertiesState<class A, class... Is> is the class template representing a specific request for ‘common’ properties A and specific properties Is.... I prefer to compute the length of the compound query string so that I can declare the type of the constructed string explicitly, as opposed to relying on auto, which I find enhances comprehensibility of the code.
The string is constructed piecewise with the help of a stateful lambda: there is no compile-time equivalent to sprintf(). The state keeps track of the current end of the constructed string so that it can be applied consecutively. The common ‘outer’ structure is represented by gBeginTag and gEndTag, and the XML representing the specific requests by a member variable of another class template Transitions<Is...>.
There is something notable here regarding the roundabout way of using std::array and std::string_view to construct the compound string; why not just use std::string, since that is constexpr as of C++20? The problem is that compile-time dynamic allocation may not be “transient” into run time: whatever string that is constructed during compile time that uses dynamic allocation must be deallocated by the end of compile time. In fact, using constexpr std::string does compile without error (at least under current MSVC) and therefore seems like it would work; but the constructed strings are empty at run time. This is a very subtle issue that isn't clear just by looking at the individual STL class documentation. std::array doesn’t suffer from this problem exactly because it isn't dynamic allocation.
The compound request XML of the list of specific requests is constructed in a similar way, but now using the usual recursive variadic template unrolling. There is no parameter pack method of concatenating string.
template <class I, class... Is>
struct WebDAV::Transitions<I, Is...> {
static constexpr std::size_t gXMLL = I::xml.size() + Transitions<Is...>::gXML.size();
static constexpr std::array<char, gXMLL> gXMLa = []() {
/* If the array is too short for the string, compilation will fail due to a call to "_CrtDbgReport" */
std::array<char, gXMLL> result;
// concatenate string into 'result' (note 'mutable' to maintain the iterator between invocations)
auto append = [resultAt = result.begin()](const std::string_view &s) mutable {
resultAt = std::copy(s.begin(), s.end(), resultAt);
};
// concatenate string into 'result'
append(I::xml);
append(Transitions<Is...>::gXML);
return result;
}();
[…]
}
Note that if the std::array allocated to construct the compound string into is too short, compilation fails with a C runtime assertion; this sort of makes sense if you accept that the compiler is running some kind of ‘constexpr program’ at compile time but is another reminder of the immaturity of the tooling.
The recursive pack expansion is terminated in the usual way, but note another subtlety:
template <>
struct WebDAV::Transitions<> : public […] {
// can't use a zero-size std::array because it "may or may not return NULL"
static constexpr std::string_view gXML {};
[…]
};
Note that in this case we construct a std::string_view to represent the empty query string instead of a (zero-length) std::array. It turns out that constexpr zero-length std::arrays won't work in this case because .data() “may or may not return a null pointer” in this case, and a NULL pointer can't be used to construct the string_view. The trick of using a string_view happens to work here because both it and array provide the same .data() and .size() member functions. In essence there is an intricate dance between using array and string_view depending on which type can perform what function in different constexpr scenarios.
The details of the XML parser data structures aren't that important; mostly they can be constructed directly as static constexpr members. The data structure representing the list of transitions out of the XML prop element containing the specifically requested properties deserves some attention:
template <class I, class... Is>
struct WebDAV::Transitions<I, Is...> {
[…]
// construct list of transitions out of XML parse state
static constexpr std::array<StateParser::State::Transition, 1 + sizeof...(Is) + 1> gTransitions = []() {
std::array<StateParser::State::Transition, 1 + sizeof...(Is) + 1> result;
// add transition to 'fInner' state
result.at(0) = StateParser::State::Transition {
I::tag,
&I::gState,
sizeof(Transitions<Is...>)
};
// copy transitions to previous states
std::copy(
std::begin(Transitions<Is...>::gTransitions),
std::end(Transitions<Is...>::gTransitions),
++result.begin()
);
return result;
}();
};
Once again, I prefer to declare the type of the constructed array explicitly (though I could have been persuaded to use an alias) rather than just using auto. I know this doesn't appear to reflect common practice, but I have a strong personal bias in favor of readability.
For the common properties available in the response of any WebDAV property query, I used a slightly different approach: in this case no particular XML needs to be generated to obtain the properties and the only question is whether the caller wants to handle any particular common property. I defined a number of handler classes akin to the following:
template <typename Callable>
struct WebDAV::HREF {
Callable c;
void RespondHREF(const wchar_t href[]) { c(href); }
};
This declares the caller's intent to handle (in this case) the href common response property. These are aggregated into a single common response handler:
/* Response
Becomes a derived class of all its template arguments
*/
template <class... Is>
struct WebDAV::Response : public Is... {
};
which when instantiated (for example, as Response<HREF>) inherits all the Respond… member functions from the respective responder base classes.
Then, when generating the XML parser data structures we can detect whether any particular Respond… member function is present and populate the respective pointer-to-member function slot with a pointer to the caller's response handler:
template <class A, class... Is>
struct WebDAV::PropertiesState : public StateParser::Response {
/* This function can only compile if the adapter actually provides the respective
operations; however they will only actually be instantiated if the corresponding State
pointer-to-member refers to them when the 'constexpr-if' evaluation says they exist. */
void RespondHREF(const XMLParser<StateParser>::String href) { fAdapter.RespondHREF(href); }
static constexpr StateParser::State gStateHREF = {
nullptr,
nullptr,
nullptr,
[]() {
// does adapter define a handler for 'href'?
if constexpr (requires(A &a) { a.RespondHREF(L""); })
return static_cast<void (StateParser::Response::*)(const XMLParser<StateParser>::String)>(
&PropertiesState::RespondHREF
);
else
return nullptr;
}()
};
Note first that this uses a constexpr-if with a requires-expression to return a pointer to the caller's responder function only if it exists; note second that the if/else is again wrapped in an Immediately-Invoked Function Expression (IIFE) to work around the lack of a constexpr ternary expression.
Wrapping all this up; this means that a WebDAV query for a specific property with a particular handler can now look as simple as this:
WebDAV::Properties(
client,
pathToWebDAVResource,
WebDAV::Depth::zero,
WebDAV::Response(
WebDAV::HREF(
[&href](const wchar_t characters[]) { href = characters; }
)
),
WebDAV::CurrentUserPrincipal()
);
This relies on the C++17 technique of Class Template Argument Deduction (CTAD) to deduce the specific type of the instantiated Properties function template so that the underlying template reality is entirely abstracted. To further illustrate, an example of a more complex query:
// list all direct items in a WebDAV collection
std::wstring itemPath, itemETag, itemLastModified;
WebDAV::Properties(
client,
pathToWebDAVResource,
WebDAV::Depth::one,
// handle standard WebDAV 'response'
WebDAV::Response(
// begin of each multi-status response
WebDAV::Begin(
[&]() {
itemPath.erase();
itemETag.erase();
itemLastModified.erase();
}
),
// ‘href’ property
WebDAV::HREF(
[&](const wchar_t characters[]) { itemPath = characters; }
),
// end of each multi-status response
WebDAV::End(
[&]() {
std::wcout << itemPath << ", " << itemETag << ", " << itemLastModified << std::endl;
}
)
),
// query for and respond to 'etag'
WebDAV::ETag(
[&](const wchar_t characters[]) { itemETag = characters; }
),
// query for and respond to 'getlastmodified'
WebDAV::LastModified(
[&](const wchar_t characters[]) { itemLastModified = characters; }
)
);
There is still one essentially unsolved problem with all this, related to the calculation of the location of response subobjects in a containing response. Normally I would pointers-to-member or offsetof(), but these are unavailable in the constexpr environment because they both rely on reinterpret_cast. In the end I worked around the problem using a fairly intolerable hack that in my mind makes all of this almost not worth doing.
Since code size is always a concern to me whenever templates are involved, I measured the executable sizes (current MSVC of Visual Studio 2022)
| Polymorphism | Debug (/Od) | Release (/Os /O1) |
|---|---|---|
| run-time | 742912 | 293888 |
| compile-time | 776192 | 312832 |
As expected the code size increased somewhat, but in this context by an irrelevant amount that is certainly worth paying for the increase in flexibility, readability, and maintainability. I'm confident that with a closer look I would still be able to reduce these numbers.
It's readily apparent that an operation that was implemented in classical ‘run-time’ C++ looks dramatically different in modern ‘compile-time’ C++; I don't think it's much of an overstatement to say that compile-time C++ is in significant respects a fundamentally different language. With the advent of C++20 certainly more complex scenarios can be handled than ever before. Some things to be aware of:
All pages under this domain © Copyright 1999-2023 by: Ben Hekster