I’ve noticed over the years that for the majority of computer scientists design is something we either love or hate. And however unfortunate it may be, I think either way design is usually a bit of an after thought, or at the least it’s a moving target. High level design can usually be done in advance, but for large projects the design almost always needs to be tweaked on the fly as new issues crop up.
I, personally, am in the camp that loves design. I have seen some beautifully elegant code written by crazy geniuses <cough>John Carmack</cough> that was… less than well designed, but most of the programs I admire (of which I also have access to the source code) generally have equally admirable design philosophies.
But, this isn’t a perfect world. It’s a bit sad that we still haven’t figured out a way to hook computers directly to our brains, so we’re left with using terribly inefficient and somewhat cumbersome programming languages to wrangle these computation machines into doing something close to what we wish them to. Of course they have the irritating habit of doing exactly what we tell them, rather than what we mean.
I bring this point up because although programmer skill is definitely one issue, languages themselves suffer from design issues, and I’d say a good majority of the time that’s spent struggling with design is actually spent struggling with a language’s design. It’s the same battle artists have fought for years: I’ve got a beautiful image in my head, now how do I get this paint brush to paint that image on this canvas?
For this series of of articles I’m going to pick on C++. Love it or hate it’s so prevalent that even if you’re one who spends most of your time with more modern languages like Ruby, Python, and Haskell, you’re still likely forced to bust out some C++ now and again. And for those of us who spend 40 hours a week (or more) with C++ and love it, I’m sure we’ve all got a fairly lengthy laundry list of problems that don’t necessary come out as clean as we’d like when we put them into the crazy kitchen sink that is C++. So basically, I’m going to pick on C++ because it’s easy — that and the fact that I’m a C++ compiler developer by day, so I may have a somewhat unique perspective on the language.
For this first Effective C++ installment I’m going to start off slow. I’ve got plans to dive into some more advanced things like template metaprogramming and some of the upcoming C++0x features down the road, but I thought first I’d tackle a problem that’s plagued me more than once, and in more languages than just C++ over the years. It’s also an issue that I’ve seen some fairly… wacky (I’m being nice)… solutions to by students and even in some open source code in the past: it’s the joyous design problem known as the cyclomatic dependency.
But before I begin let me just say: there’s no judging here. Say what you want, but I know as well as the next, given certain circumstances sometimes a goto, or a Duff’s device can actually be an elegant solution, so I’m not going to sit here and say “rethink your design”, I’m going to trust that you have, and move on. Fact is, you’ve run into an issue where you need to have class A depend on class B, and class B on A. Let’s look at an example:
Here is NetworkServer.hpp:
#include "NetworkConnection.hpp" class NetworkServer { list<NetworkConnection> mConnections; };
And here’s NetworkConnection.hpp:
#include "NetworkServer.hpp" class NetworkConnection { public: NetworkConnection(const NetworkServer& server) : mServer(server); private: NetworkServer& mServer; };
You can immediately spot the issue. Now, of course, this simplistic problem could be reworked in any number of ways to avoid the cyclical dependency, but real world problems are often much more complex and thus harder to refactor, yet often come down to some variation of the above.
Fortunately C++ actually has a fairly decent solution to this problem: the forward declaration. It’s simple, and it works well, but before looking at it, let me say that I’ve seen enough work arounds to know there’s plenty of C++ programmers out there who don’t know what a forward declaration is, or if they do, why it’s useful, or what the C++ compiler actually does with it.
One of the solutions I’ve seen to this is to use generic programming, or in C++ speak: templates. We could define NetworkConnection like so:
template <typename T> class NetworkConnection { public: NetworkConnection(const T& server) : mServer(server); private: T& mServer; };
This works, but what if someone instantiates NetworkConnection with a type that doesn’t provide the same methods as NetworkServer — broken design! Not only that but if you’re using NetworkConnection as a base class it might not make sense to have it templated because you might need to cast from it to a super class, and you might not know what it was instantiated with at casting time. This is actually a design flaw with C++, and is being addressed with the upcoming C++0x language feature known as concepts (which I intend to look at in detail in a future installment).
There’s also a non-template way to deal with this issue, however, and it’s something I’ve seen used a lot, especially by students (who are, through no fault of their own, ingrained in the java-single-inheritance-heavy-on-the-interface style of design). You simply make class A inherit from an abstract base class that provides pure virtual function interfaces to the methods needed by the other class caught in the cyclical loop. Then pass the abstract class around rather than its implementation and voila, dependency avoided:
NetworkServerInterface.hpp:
struct NetworkServerInterface { virtual void someFuncA() = 0; virtual bool someFuncB() = 0; ... };
NetworkServer.hpp:
#include "NetworkServerInterface.hpp" #include "NetworkConnection.hpp" class NetworkServer : public NetworkServerInterface { public: void someFuncA(); bool SomeFuncB(); private: list<NetworkConnection> mConnections; };
NetworkConnection.hpp:
#include "NetworkServerInterface.hpp" class NetworkConnection { public: NetworkConnection(const NetworkServerInterface& server) : mServer(server) { mServer.someFuncA(); } private: NetworkServerInterface& mServer; };
This works, and can be a good technique to enforece certain design principles (it’s easy to only allow specific objects to use the NetworkServer in exactly the way you want by only providing a subset of functions in the abstract class definition), but it’s not without its shortcomings. Firstly, significant development effort is wasted by requiring the interface class and main class be kept in sync. Then there’s the overhead of virtual function calls that should be considered. For a time critical section of code this scenario should be avoided like the plague.
Another possible solution is the dreaded void *. It’s a holdover from the days of C programming, and much like the goto, is generally frowned upon in modern OO design. The problem with using a void pointer is if you need to use the member variable as its actual type then you have to cast it back and you’re left with the same cyclical dependency because then you need to include the casted type’s header file again.
Fortunately with C++, since the headers no longer include one another, and the translation unit is often broken into separate header and source files, you’re free to include any headers you wish in the parts of the translation unit that contain the implementation definitions (the cpp files). So, you could store the variable as a void pointer and cast from it whenever you need to access its actual type’s methods, ie:
NetworkConnection.hpp
class NetworkConnection { public: NetworkConnection(void* server); private: void* mpServer; };
NetworkConnection.cpp:
#include "NetworkConnection.hpp" #include "NetworkServer.hpp" NetworkConnection::NetworkConnection(void* server) { mpServer = server; static_cast<NetworkServer*>(server)->someFuncA(); }
Yep, this works, but it’s nasty ugly, and kills proper design because you can’t really return the void pointer from public facing functions in any safe way. Normally I wouldn’t even bring this up, but it is an option, and it’s also a precursor to the forward declaration.
Essentially with forward declarations you’re telling the compiler that you want to use a class without knowing anything about it. In compiler terminology basically you’re doing namelookup, and that’s about it. You can’t use any objects of that type until you give the compiler the details it needs. This is fine though, because you can make sure to only use the variable after its class definition is available (ie in out of line member functions, or in the implementation part of the translation unit). Here’s an example:
NetworkServer.hpp:
#include "NetworkConnection.hpp" class NetworkServer { public: int someFuncA() { return 0; } private: list<NetworkConnection> mConnections; };
NetworkConnection.hpp:
class NetworkServer; // Foward declaration class NetworkConnection { public: NetworkConnection(const NetworkServer& server); private: NetworkServer& mServer; };
NetworkConnection.cpp:
#include "NetworkConnection.hpp" #include "NetworkServer.hpp" NetworkConnection::NetworkConnection(const NetworkServer& server) : mServer(server) { mServer.someFuncA(); }
Not only does this solve the cyclical dependency issue, but it speeds up compilation times as well. I’d even go as far as to say it’s good practice to use forward declarations wherever possible, which is in most header files if you’re writing a traditional application or a library that’s not meant to be completely header based.
So there you have it, a look at how to deal with cyclical dependencies in C++.
I’m thinking that the next topic will be a multi-part series on the upcoming variadic templates feature of C++0x since you can already play with them via gcc >= 4.3. Plus my goal is to eventually focus on more metaprogramming type stuff, and variadics are going to make that a lot more fun.
