I wanted to write about this yesterday but I was dealing with the end-of-week correspondence and some phone calls I had to take. Somehow yesterday I wasn’t feeling up to it, so today I spent some time with cpp-netlib development and refactored an implementation to turn it into a generic algorithm. This post is about that experience and process, which you might be able to follow in turning some parts of your code into more generic algorithms and have more generic abstractions to implement. I’ll do a deep dive into the cpp-netlib code, so if you’d like a backgrounder, you might want to read up on the source code of the project online (here) or at least read up on the documentation (here). So what does it take to remove an implementation from a base class into a generic algorithm (function)?
In the cpp-netlib we use (heavily) a technique of doing tag-dispatch, but not just on the template functions, but in choosing a class’s parent. We try to hide the implementation details (and the policies) by introducing non-intrusive (and non-user-visible) template metafunctions that takes in a tag type and yields another type. With this facility we allow the implementation to literally choose their parents at compile time — as opposed to doing it at runtime with encapsulation and dynamic polymorphism. You can find more about this technique in the page about tag metafunctions in the cpp-netlib documentation. This is a template metaprogramming technique, not necessarily a generic programming technique.
What I would like to discuss is how we implement a generic algorithm for linearizing a request into an output iterator. You can find the current implementation of this algorithm in the 0.9-devel branch which I spent time earlier today to implement and debug here.
The high level idea of the linearize algorithm is to turn a message into a string or some other representation. The algorithm relies on the following abstractions in its implementation:
- HTTP Client Request Concept — A type that models this concept supports getting the URI of the message (technically the destination), the headers, and the body. The URI has parts which are important to the algorithm because the parts of the URI will be required (the path, query, and anchor parts). You can see the Client Request Concept definition here.
- Output Iterator — A type that models this concept allows for writing data to the underlying buffer or “sink”. You can read more about the concept here or here.
In this implementation, the linearize algorithm uses Boost.Concept_check to ensure that the parameters adhere to the abstraction requirements. This ensures that non-conforming types would cause the compilation to fail, and no bugs go through to run-time. It also means that we only specify the absolute minimum when we define the concepts we require. In this case, our minimum requirement on the parameter to the linearize algorithm is the a Client Request.
The linearize algorithm has the following signature:
template OutputIterator> OutputIterator linearize( Request const & request, typename Request::string_type const & method, unsigned version_major, unsigned version_minor, OutputIterator oi );
Above, you can see that there are 5 parameters — the request, the method, the major version, the minor version, and the output iterator. The algorithm will turn an HTTP Request object into a stream of characters, consistent with the specification of an HTTP Request Message. What we want to do is turn a request in-memory, into something that looks like:
GET / HTTP/1.1 Host: www.boost.org Accept: */* Accept-Encoding: identity;q=1.0, *;q=0 Connection: close
This is an example of an HTTP request sent out by HTTP/1.1 clients, and in this case the algorithm doesn’t require that this be in a string, in a file, in a fixed-size buffer — rather it just requires that the `oi` parameter qualifies as an Output Iterator and supports the semantics of an Output Iterator.
Using the Algorithm
If you look at the internals of the HTTP client implementation of cpp-netlib, you will see that it used to use inheritance to re-use the connection helper that does essentially the same thing that `linearize` did, except it made a lot of assumptions as to how the function was going to be used. Now the code has been changed to instead use an external, now generic algorithm that supports writing directly to iterator instead of building strings in memory. Using the algorithm in code actually looks really simple as evidenced by the example test:
linearize(request, "GET", 1u, 1u, std::ostream_iterator(std::cout));
If you notice, this just linearizes the request to the standard output stream. Linearizing to a string buffer is as simple as changing the iterator you pass in to the function. This is similar in spirit to the STL algorithms like `copy` and `transform`, except this is specific to the domain (HTTP) that stands on its own.
The Lifting Process
Lifting this from the earlier implementation of the connection helper was a multi-step process. However, here’s the high-level gist of what was done to make it happen (for context, look at the implementation of the soon to be defunct connection helper here):
- Turn the connection helper’s member function ‘create_request’ into a standalone function. I also renamed it ‘linearize’ to better convey the intention.
- Instead of taking an asio::streambuf, convert the implementation to deal with an output iterator. This changes the internals a lot, and I’ve chosen to use Boost.Range to reduce the amount of typing done with .begin() and .end() with the different strings when using the STL algorithms.
- Move as much of the assumptions outside into functions and other templates.
- Remove the original inheritance, and change all instances of the use of create_request to convert it into using the linearize function.
Sometimes it’s this simple, while sometimes, especially in larger code bases, it can be tricky. Like with all techniques, your mileage may vary.
I’ll write more about the other transformations I’ve done with cpp-netlib to make the algorithms more generic. Until tomorrow, let me know if there’s anything you need clarification on.
Thanks for reading and I hope this helps!