Title: Reshaping an Old Piece of Design

In C++, virtual functions are fundamental in supporting the capability to implement an object-oriented design. They allow a call to a member function made on a pointer/reference to a base class to result in a member function of the object's concrete class being called. In doing so, they are the language's fundamental mechanism of run time polymorphism - the function actually called depends on the type of the object pointed to, as determined at run time.

Sometimes being able to select a function to call based on the run time type of one object is not enough. Sometimes there is a need to create the effect of a function being virtual with respect to two or more objects. Some languages (e.g. CLOS) have such a mechanism, and such functions are known as multi-methods. However C++ has no such feature, and where multi-methods are required in C++ the effect must be achieved using design and programming techniques.

In this article I will first describe a problem I once faced, that motivated me to take an interest in these techniques. I will describe the solution I chose (which unfortunately was not a good one) and the alternatives I considered, examining the tradeoffs they offer. Then I will go on to look at the solution I would choose if I faced the problem now, and explain why I would prefer it.

A few years ago I was involved in the development of a package for producing two-dimensional technical drawings. The drawing program supported two basic shapes: straight lines, and semicircular arcs, and it is easy to understand how the hierarchy in the figure below was fundamental to the design.

It is obvious that these shapes would need an interface capable of supporting the operations the user is certain to expect, such as being able to move the shapes around and rotate them. However, because the program was for producing drawings of a technical nature - essentially 2D CAD - an operation to calculate the intersection with another shape was also necessary. Unfortunately having available a shape abstraction is not good enough: the intersection() methods need to implement the intersection calculation formula, and implementing the formula requires the concrete type of both shapes. In passing, it was to my delight that I found Bjarne Stroustrup cites almost this very problem as an example (in [Stroustrup]) of where multimethods would be useful.

The solution I came up with at the time was not very good and the irritating thing was that I knew I knew this - I just didn't know what else to do. I could think of other approaches, but they all seemed worse than the one I used. For example, some sources (e.g. [Meyers]) use the brute force approach of downcasting in conjunction with RTTI. In hindsight though, the RTTI approach offered a better set of tradeoffs.

This problem has been in my mind (on and off) ever since, and years later, I have come up with what I think is a satisfactory approach.

I considered two solutions at the time. One of them worked by finding out the run time types of the shapes using run time type information (RTTI); this could be described as a "brute force" approach. The alternative used an object-oriented approach, and I consider it to be a classic example of a solution being flawed while being unquestionably object-oriented.

void intersection(const line& l, const shape& s,
                  intersection_points& where) {
  if (const line* lp = dynamic_cast<const line*>(&s)) {
    lines_intersection(l, *lp, where);
  }
  else if (const arc* ap = dynamic_cast<const arc*>(&s)) {
    line_arc_intersection(l, *ap, where);
  }
  else
    //..
}

void intersection(const arc& a, const shape& s,
                  intersection_points& where)
{ /* .. */ }

class shape {
public:
  virtual ~shape();
  virtual void intersection(const shape& s,
                            intersection_points& where) const = 0;
  virtual void intersection(const arc& s,
                            intersection_points& where) const = 0;
  virtual void intersection(const line& s,
                            intersection_points& where) const = 0;
  //...
};

class arc : public shape {
private:
  virtual void intersection(const shape& s,
                            intersection_points& where) const;
  virtual void intersection(const arc& s,
                            intersection_points& where) const;
  virtual void intersection(const line& s,
                            intersection_points& where) const;
  // ...
};

class line : public shape {
private:
  virtual void intersection(const shape& s,
                            intersection_points& where) const;
  virtual void intersection(const arc& s,
                            intersection_points& where) const;
  virtual void intersection(const line& s,
                            intersection_points& where) const;
  // ...
};

shape* shape1 = new line(..);
shape* shape2 = new arc(..);

shape1->intersection(*shape2, where);
                     // Calls line::intersection()

void line::intersection(const shape& s,
                        intersection_points& where) const {
  s.intersection(*this, where);
  // Call is re-dispatched...
}

void arc::intersection(const line& s,
                       intersection_points& where) const {
  line_arc_intersection(s, *this, where);
  // ...and handled by the
  // arc::intersection()
  // overload that handles lines
}

In seeking a better solution, I'm going to start by asserting that the flawed object oriented solution would actually have been quite reasonable but for one thing: classes are intrusive on each other. My point is that this intrusiveness would not be such a problem if it could be compartmentalised and therefore its impact limited. To this end I will recruit the help of the EXTENSION OBJECT design pattern (originally documented by Erich Gamma - see [PLoPD3] for the full write-up). What follows is only a brief and slightly C++ centric summary of the pattern, but the description (below) of how it is used to implement a better solution should complete the picture.

Pattern

EXTENSION OBJECT.

Context, problem and forces

Different clients will have different requirements of an object's interface. The precise interface that will be required by each client cannot always be anticipated at design time. Also, it is often unacceptable to trade provision for them against the interface bloat that would result. In C++ this problem can be addressed to some extent by an approach using freestanding functions. However this does not solve all the (potential) problems (for example, freestanding functions cannot be virtual).

Solution

Support the additional interfaces using separate objects and give the Subject an interface for returning Extension Objects.

Configuration

The extensions hierarchy (see figure below) is headed up by the extension interface, while the facilities the extension offers to clients are made available through the interface specific_extension.

The extension interface does not support the operations required by the client, because different extensions will offer different operations. Therefore client obtains access to extensions via get_extension(), to which it passes type, where type is simply some kind of indication of the extension type being requested.

Consequences

It can be seen that this pattern offers benefits in terms of flexible extensibility, but there are some drawbacks, for example:

The solution presented as a flawed object-oriented solution was in some ways an attractive one, exhibiting the benefits of objectoriented design, keeping code performing a function together and separate from code performing other functions. It was only flawed as a consequence of making classes within the shape hierarchy intrusive on each other, and the interface clutter caused (three virtual functions were needed in each class's interface). Introducing EXTENSION OBJECT allows the same mechanisms to be deployed while keeping the intrusiveness and interface clutter out of the shape hierarchy. The design now looks as shown in the figure below.

In this design, the following mappings from the EXTENSION OBJECT configuration are used:

As an aid to understanding these mappings, the names from the configuration are used as stereotypes in the exposition in UML (see figure below).

The mechanics of recovering the types and working out the intersection points are the same as in the flawed solution - the only difference is that this time the participants are shape_intersector, arc_intersector, line_intersector and the additional shape_extension.

The class definition contains very little:

class shape_extension {
public:
  virtual ~shape_extension();
  // ...
};

It has a virtual destructor, but that needs no explanation:

namespace intersections {
class shape_intersector {
public:
  virtual ~shape_intersector();
  virtual void intersection(
                      const shape_intersector& obj,
                      intersection_points& where) const = 0;
  virtual void intersection(
                      const line_intersector& obj,
                      intersection_points& where) const = 0;
  virtual void intersection(
                      const arc_intersector& obj,
                      intersection_points& where) const = 0;
  // ...
};

boost::shared_ptr<shape_intersector>
  down_cast(
    boost::shared_ptr<shape_extension> obj);
}

The shape_intersector class is the first one in the hierarchy to have an interface of any substance. It declares intersection() member function overloads in much the same way as shape did in the flawed object oriented solution - the difference here being that these overloads take line_intersector and arc_intersector parameters, in place of line and arc parameters respectively.

Another declaration of interest is that of the down_cast() function: not a member of shape_intersector but provided within the intersections namespace. To understand its role, first we need to look at shape:

class shape {
public:
  virtual void move_x(coordinate_units x) = 0;
  virtual void move_y(coordinate_units y) = 0;
  virtual void rotate(radians rotation) = 0;
  // ...
  virtual boost::shared_ptr<shape_extension>
  create(const std::type_info& type) const=0;
};

The shape interface class provides (besides the functional interface supporting user operations) a virtual member factory function create() that returns a shape_extension instance. Here there is a deviation from the canonical EXTENSION OBJECT configuration, because concrete_subject (line or arc, omitted from the UML diagram) is designated as its owner, which is not quite the case here. The design in this example uses the C++ idiom of using a smart pointer to manage memory acquisition and release, to avoid running into problems with object lifetimes.

Returning to down_cast(): in order to use the shape_intersector interface, the shared_ptr<shape_extension> instance returned from shape::create() must be converted to type shared_ptr<shape_intersector> (remember this was listed as a consequence of the EXTENSION OBJECT design pattern). A custom mechanism in the form of down_cast() is provided to achieve this, because unfortunately the use of a smart pointer cuts across the natural approach of using dynamic_cast.

The definitions of classes line and arc are self-explanatory: they just provide implementations of shape's virtual member functions move_x(), move_y(), rotate() etc. I'm not going to list them here because I don't believe they will actually add anything to the illustration. Instead I'm going to move on to intersection(), another freestanding function declared within the intersections namespace:

namespace intersections {
intersection_points intersection(
                const shape& s1, const shape& s2) { // 1
  intersection_points where;
  boost::shared_ptr<shape_intersector> first
                = down_cast(s1.create(
                       typeid(shape_intersector))); // 2
  boost::shared_ptr<shape_intersector> second
                = down_cast(s2.create(
                       typeid(shape_intersector))); // 3
  first->intersection(*second, where);              // 4
  return where;
} }

Before looking at intersection()'s implementation, I feel it is worth digressing briefly to look at a trade-off that has been made. It was observed that as a consequence of the EXTENSION OBJECT design pattern, the machinery for obtaining extension (shape_extension) instances and down casting them to specific_extension (shape_intersector) adds complexity to clients. It was also observed that one way to address this complexity is to encapsulate it, and this is the approach taken here: i.e. it's all wrapped up in the intersection() function. This encapsulation introduces a tension with the design decision to create shape_extension instances on the heap (instead of the originating object owning them): there is no way to preserve these instances between calls to intersection(). Thus efficiency is traded for simplicity of usage (and tidiness of exposition in an article :-)).

Getting back to intersection()'s implementation...

The function takes two shape instances (by reference so they exhibit run time polymorphism), s1 and s2, as its parameters (statement 1). Statements 2 and 3 create first and second, these being the shape_intersector instances, and here two things should be observed:

Statement 4 is where the intersections (if any) are calculated. The rest of how this works is very similar to the way in which the flawed object-oriented solution worked:

shape* shape1 = new line();
shape* shape2 = new arc();

And their intersections calculated:

intersection_points where =
intersection(*shape1, *shape2);

The workings of the intersection() function were explained above, so we now need to look at how line_intersector::intersection() and arc_intersector::intersection() work. When intersection() is called with shape1 and shape2 as arguments, statement 4 in its implementation results in a call to the line_intersector::intersection() overload taking a shape_intersector parameter:

void line_intersector::intersection(
               const shape_intersector& s,
               intersection_points& where) const {
  s.intersection(*this, where);
  // Call is re-dispatched...
}

Remember shape2 has concrete type arc, so re-dispatching the call results in a call to arc_intersector::intersection() - specifically, the overload that takes a line_intersector as a parameter:

void arc_intersector::intersection(
               const line_intersector& s,
               intersection_points& where) const {
  line_arc_intersection(s, *this, where);
}

That's it. At this point the concrete types of both shape_intersectors are known, and the calculation (details of which we are not concerned with here) can be performed.

Phew!

Using the object-oriented paradigm does not automatically make a design superior. In the past object orientation has been adopted in the hope that it would be the silver bullet that would solve all software development problems. Of course, history now records that nothing was further from the truth. There were many factors involved, one being the lack of understanding of object orientation itself. Another critical factor however, was the assumption that being object oriented automatically made a design a good one. The flawed object oriented solution presented earlier is an excellent counter example.

An important lesson is that even good OOD has its costs. It comes back to the fact that when solving problems with any level of complexity, there is no such thing as a solution per-se - there are options and tradeoffs.

Finally, the BSI C++ panel are currently discussing a proposal by Julian Smith to add multi-methods to the language - therefore this feature may or may not be present in the language when the next edition of the standard appears. Full details of the proposal can be found at Julian's web site (see [Multi-Methods-Proposal]).