ACCU Home page ACCU Conference Page ACCU 2017 Conference Registration Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinFrom Mechanism to Method: The Safe Stacking of Cats

Overload Journal #62 - Aug 2004 + Design of applications and programs   Author: Kevlin Henney

In spite of some obvious differences - and the similarity that neither can be considered a normal practice - curling and throwing have something in common: curling is a bizarre sport played on ice; throwing in C++ is often played on thin ice. It is the thin ice that has most often caused consternation, and the balanced art of not falling through that has attracted much attention.

By coincidence, curling is also something in which cats both indulge and excel, putting the pro into procrastination. But more on cats later.

Taking Exception

Exceptions are disruptive but modular. The common appeal to consider them as related to the goto is more than a little misleading ("considering goto" considered harmful, if you like). That they are both discontinuous is one of the few features they share. It is an observation that although true is not necessarily useful: break, continue, and return also share this description of behavior. A quick dissection exposes the differences:

  • Transferred information:

    a goto can associate only with a label whereas a throw communicates with respect to both type and any information contained in the type instance. In this sense, the throw acts more like a return, communicating an exceptional rather than a normal result.

  • Locality:

    a goto has meaning only within a function, labels being the only C++ entity with function scope. By contrast, exception handling is primarily about transferring control out of a function. It shares this with return, but potentially has the whole of the call stack rather than just the immediate caller within its reach. It also shares with break and continue a relationship with an enclosing control flow primitive, so exception handling can also be used simply at the block level.

  • Destination coupling:

    the target of a goto is fixed, hardwired at compile time. There is no way to express "the following has happened, so whoever can sort it out, please sort it out." Exceptions are independent of lexical scope and do not nominate their handlers explicitly. Instead, nomination is dynamic and by requirement - "the first one that can handle one of these gets to sort it out." Exceptions can be handled or ignored at different call levels without intervention from any of the levels in between. In many ways, the try/catch mechanism resembles an advanced selection control structure - an if/else with extreme attitude.

  • Block structure:

    Taligent's Guide to Designing Programs pulls no punches in stating that "a goto completely invalidates the high-level structure of the code" [Taligent]. Far from being merely a provocative statement, this is a concise summary of fact. C++ is essentially block structured: exceptions respect and work within this structure, whereas gotos largely ignore and disrespect it.

The differences are thrown (sic) into sharp relief when you attempt to refactor code. Say that you wish to factor a block out as a function (the Extract Method refactoring [Fowler]); it is trivial to factor out the data flow: looking at the data that's used and affected in the block tells you what arguments and results you need to pass and how. With control flow, unless you flow off the bottom of a block or throw, you cannot factor the code simply. Traditional discontinuous control flow is nonmodular and requires additional restructuring to communicate to the caller that a break, return, continue, or goto (especially) must be effected. This is not the case with throw: both the overall structure and the fine-grained detail remain unchanged.

State Corruption

This all sounds straightforward - or straight backward if you take the call stack's perspective - because we know about modularity, both structured programming and object-oriented programming are built on that foundation. However, there is still that one small matter of "disruption." When an exception is thrown, the only thing you want disrupted is the control flow, not the integrity of the program.

Any block of code may be characterized with respect to the program's stability in the event of an exception. We can guarantee different levels of safety, of which three are commonly recognized [Sutter2000], plus the (literally) degenerate case:

  • No guarantee of exception safety:

    ensures disruption, corruption, and chaos. Code written without exceptions in mind often falls into this category, leaking memory or leaving dangling pointers in the event of a thrown exception - converting the exceptional into the unacceptable. In short, all bets are off.

  • Basic guarantee of exception safety:

    ensures that the thrower will not leak or corrupt resources. Objects involved in the execution will be in a stable and usable, albeit not necessarily predictable, state.

  • Strong guarantee of exception safety:

    ensures that a program's state remains unchanged in the presence of exceptions. In other words, commit-rollback semantics.

  • No-throw guarantee of exception safety:

    ensures that exceptions are never thrown, hence the question of how program state is affected in the presence of an exception need never be answered because it is purely hypothetical.

The stroke of midnight separates the first, degenerate category of exception unsafety from the last, Zen-like guarantee of benign order through the simple absence of disruption. Code written to achieve these guarantees may have the same structure, but will differ in the not-so-small detail of whether or not exceptions occur anywhere in their flow.

These guarantees apply to any unit of code from a statement to a function, but are most commonly applied to member functions called on objects. A point that is not often made relates exception safety to encapsulation: not so much that exception safety can be improved by better encapsulation, but that exception safety is one measure of encapsulation. Prominent OO propaganda holds that encapsulation is concerned with making object data private. Whilst this view is not strictly false, it misses some important truths.

Encapsulation is neither a language feature nor a practice; rather it is a non-functional property of code, and something that you can have more or less of. Encapsulation describes the degree to which something is self-contained, the degree to which its insides affect its outsides, the degree to which internal representation affects external usage. Encapsulation is about usability, about not imposing on the user. Language features and idiomatic design practices can be used to improve encapsulation, but of themselves they are not encapsulation. Thinking back to exceptions, you can see that without even thinking about internal representation, an object that offers the strong guarantee on a member function is more encapsulated than one that offers no guarantee.

Incorruptible Style

It is one thing to have a guarantee, but quite another to fulfill it. What is the style and mechanism of the code that allows a thrown exception to propagate out of a block in a safe manner? Including the degenerate case, there are essentially four approaches to achieving exception safety:

  • Exception-unaware code:

    code that is not written with exceptions in mind is as easy to read as it is dangerous - going wrong with confidence.

  • Exception-aware code:

    code may be scaffolded explicitly with try, catch, and throw to ensure that the appropriate stabilizing action is taken in the event of a thrown exception. Alas, it is not always obvious that exception-aware code is safe: such code is rarely clear and concise.

  • Exception-neutral code:

    code that works in the presence of exceptions, but does not require any explicit exception-handling apparatus to do so (i.e., no explicit try/catch code). Not only is exception-neutral code briefer and clearer than exception-aware code, but it is also typically shorter than exception unaware code. So, exception safety and seamless exception propagation aside, such minimalism offers another strong motivation for reworking code in this style.

  • Exception-free code:

    code that generates no exceptions offers the most transparent fulfillment of exception safety.

When Cats Turn Bad

There is a tradition - from Schrödinger to Stroustrup - of employing cats for demonstration purposes, and I see no reason to stand in the way of tradition. There appears to be sufficient prior art in the stacking of cats [Stroustrup] that I will also adopt that practice. Of course, we are only dealing with abstractions - if you are concerned for the poor cat, keep in mind that unless we set it in concrete no act of cruelty actually occurs.

Assuming that we have an appropriate cat class definition, the following fragment demonstrates exception-unaware code:

{
  cat *marshall = new cat;
  .... // play with marshall
  delete marshall;
}

If an exception occurs during play, there will be a memory leak: you will forget about your scoped cat. The following fragment demonstrates exception-aware code:

{
  cat *marshall = new cat;
  try {
    .... // play with marshall
  }
  catch(...) {
    delete marshall;
    throw;
  }
  delete marshall;
}

Safe? Yes. Unreadable? Certainly. What it lacks in elegance it more than makes up for in verbosity. The code may be safe, but it is not obviously so [Hoare]. The following fragment demonstrates exception-neutral code:

{
  std::auto_ptr<cat> marshall(new cat);
  .... // play with marshall
}

For all its faults (and they are many), this is one job that std::auto_ptr does do well. If we know that default cat constructors do not throw exceptions, and we recognize that marshall is always bounded by scope, the following fragment demonstrates exception-free code:

{
  cat marshall;
  .... // play with marshall
}

Clearly, for demo purposes, we are taking some liberties with the common understanding of cats and their care, treating them as disposable commodities. Taking further license with feline appreciation and object design, let us also assume that they are value-based rather than entity-based objects. This means that they support copying through construction and assignment, are generally not heap based, and are typically not deeply involved in class hierarchies.

Modern cloning technology is imperfect, so cat copy constructors are not always guaranteed to work. On failure they throw an exception, but they are well behaved enough to avoid resource leakage and to not corrupt the program's state.

Throwing Gauntlets

In 1994 Tom Cargill laid down a challenge - or extended an invitation to solution, depending on your point of view - concerning exception safety [Cargill]. The challenge was based on a fairly typical stack class template. There were a number of elements to the challenge; the one I want to focus on here is how to write the pop member function.

Here is some code that demonstrates the challenge:

template<typename value_type>
class stack {
public:
  void push(const value_type &new_top) {
    data.push_back(new_top);
  }
  value_type pop() {
    value_type old_top = data.back();
    data.pop_back();
    return old_top;
  }
  std::size_t size() const {
    return data.size();
  }
  ....
private:
  std::vector<value_type> data;
};

I have used std::vector for brevity (performing manual memory management does nothing to make the problem clearer) and I am skipping issues related to assignment - I would recommend looking at Herb Sutter's thorough coverage of the challenge to see how this is addressed [Sutter2000].

We can now recruit our favorite cat to demonstrate the issue. First of all, pushing cats is not problematic:

stack<cat> stacked;
stacked.push(marshall);
std::cout << "number of stacked cats == "
          << stacked.size() << std::endl;

The issue arises when we pop cats:

try {
  cat fender = stacked.pop();
  .... // play with fender
}
catch(...) {
  std::cout << "number of stacked cats"
            << " == " << stacked.size()
            << std::endl;
}

If the copy made in pop's return statement fails, we have lost the top cat: the cat has been removed from data and size is one less than before. pop, therefore, cannot satisfy the strong guarantee of exception safety, because that requires everything to be left as it was before the exception was thrown. The stack is still usable and its resulting state is predictable, which means that we can promise marginally more than the basic guarantee ... but we've still got a missing cat.

Before setting about any solution, it is important to remember that designs - and therefore design problems - do not exist in a vacuum. Design is intimately bound up with purpose and context, and without understanding these we risk either solving the wrong problem or, as we so often do, solving the solution. Design is about balancing goals - as well as cats.

Unasking the Question

Looking at the class interface, we might ask why two actions are combined into one: Why does pop both return a queried value and modify the target object? We know that such a return causes an exception-safety problem, and we also know that it is potentially wasteful. What if you do not plan to use the return value? Even if you ignore it, the work that goes into copying and returning the value still happens. You are potentially paying both a cost and a penalty for something you didn't use.

The Command-Query Separation pattern [Henney1] - sometimes referred to as a principle rather than a pattern [Meyer] - resolves our concerns by making a separation with respect to qualification:

template<typename value_type>
class stack {
public:
  ....
  void pop() {
    data.pop_back();
  }
  value_type &top() {
    return data.back();
  }
  const value_type &top() const {
    return data.back();
  }
  ....
private:
  std::vector<value_type> data;
};

The separation of modifier from query operations ensures that we cannot make a change and lose the result. This separated interface also supports a slightly different usage model:

cat fender = stacked.top();
stacked.pop();
.... // play with fender

No copying exception can arise within the stack, so there is no need to deal with it. This separation of concerns (and member functions) can be seen in the design of the STL sequences and sequence adaptors.

Rephrasing the Question

It would seem that the problem is solved, except for one thing: we never fully established the context of execution. It is entirely possible that the basic guarantee of the original code was satisfactory for our purposes, so there was no problem - from our perspective - to be solved. Either we accept the loss of a cat or, more commonly, the element type of the stack has exception-free copying, which would be the case for built-in types as well as a number of user-defined types. So under some circumstances, the stack offers us the strong guarantee. If these are your circumstances, the original code does not strictly speaking need to be fixed. If they are not, there is indeed a problem to be fixed, and Command-Query Separation offers one solution.

But there are others. Command-Query Separation is attractive because it clarifies the role of interface functions. It could be said to offer better encapsulation and cohesion. However, such a statement is not universally true, and understanding why will demonstrate why we must consider Command-Query Separation a pattern (a design solution with consequences and a context) and not a principle (an idea that expresses a universal truth).

Consider a clarification in design context: the stack is to be shared between multiple threads. Ideally we would like to encapsulate synchronization detail within the stack, ensuring that primitives such as mutexes are used safely and correctly. Focusing just on the push member, an exception-unaware implementation would be as follows:

template<typename value_type>
class stack {
public:
  ....
  void push(const value_type &new_top) {
    guard.lock();
    data.push_back(new_top);
    guard.unlock();
  }
  ....
private:
  mutable mutex monitor;
  std::vector<value_type> data;
};

The exception-neutral approach is both shorter and safer:

template<typename value_type>
class stack {
public:
  ....
  void push(const value_type &new_top) {
    locker<mutex> guard(monitor);
    data.push_back(new_top);
  }
  ....
private:
  mutable mutex monitor;
  std::vector<value_type> data;
};

Where locker is a helper class template responsible for abstracting control flow [Henney2]:

template<typename locked_type>
class locker {
public:
  explicit locker(locked_type &lockee)
    : lockee(lockee) {
    lockee.lock();
  }
  ~locker() {
    lockee.unlock();
  }
private:
  locker(const locker &); // no copying
  locked_type &lockee;
};

Making each public member function of stack self-locking would appear to preserve encapsulation. However, this works only for usage scenarios that are based on single function calls. For the Command-Query Separation solution, this would introduce a couple of subtle bugs:

cat fender = stacked.top();
stacked.pop();
.... // play with fender

First of all, top returns a reference. Consider the following simple action in another concurrent thread:

stacked.pop();

Assuming that all of the member functions we are talking about are self-locking, what is the problem? Imagine that the second thread executes pop just after the first thread completes the call to top: the reference result from top is now dangling, referring to a non-existent element. Undefined behavior. Oops. Poor fender gets a very bad start in life.

Returning references to value objects from thread-shared objects is a bad idea, so let's fix stack:

template<typename value_type>
class stack {
public:
  ....
  value_type top() const {
    locker<mutex> guard(monitor);
    return data.back();
  }
  ....
private:
  mutable mutex monitor;
  std::vector<value_type> data;
};

This solves the problem of undefined behavior, but leads us straight into the jaws of the second problem, which is that of "surprising" behavior. Idiomatically, we treat the following as a single unit:

cat fender = stacked.top();
stacked.pop();
.... // play with fender

However, this usage is not cohesive in its execution. It can be interrupted by another thread:

cat peavey;
stacked.push(peavey);

so that the push in the second thread occurs between the initialization of fender and the pop in the first thread. This means that the wrong element is popped from the stack. Oops, again.

We could expose the lock and unlock features in stack and let the user sort it all out:

template<typename value_type>
class stack {
public:
  void lock() {
    monitor.lock();
  }
  void unlock() {
    monitor.unlock();
  }
  ....
private:
  mutex monitor;
  std::vector<value_type> data;
};

Giving rise to the following somewhat clunky usage:

cat fender; {
  locker< stack<cat> > guard(stacked);
  fender = stacked.top();
  stacked.pop();
}
.... // play with fender

Let's compare this with the original usage:

cat fender = stacked.pop();
.... // play with fender

There's now more to write and more to remember - and therefore more to forget. In addition to being more tedious and error prone, it is easy to make the code pessimistic by forgetting to enclose the locker in the narrowest scope possible, leaving waiting threads locked out of stacked for far longer than necessary.

Remember that the original design's only safety shortcoming was that it offered only the basic - rather than the strong - guarantee of exception safety. It would take a leap of orthodoxy to say, hand on heart, that Command-Query Separation has produced a more cohesive and encapsulated solution - the opposite is true in this context.

The Combined Method pattern [Henney1] is one that sometimes finds itself in tension with Command-Query Separation, combining separate actions into a single, transactional whole for the benefit of simplicity and correctness in, principally, multithreaded environments. The original pop was an example of this tactical pattern, but suffered from weakened exception safety. An alternative realization that achieves strong exception safety in an exceptionneutral style is to overload the pure pop function with a Combined Method that takes a result argument:

template<typename value_type>
class stack {
public:
  ....
  void pop() {
    locker<mutex> guard(monitor);
    data.pop_back();
  }
  void pop(value_type &old_top) {
    locker<mutex> guard(monitor);
    old_top = data.back();
    data.pop_back();
  }
  ....
private:
  mutable mutex monitor;
  std::vector<value_type> data;
};

This design tightens the screws a little on the element type requirements, additionally requiring assignability as well as copy constructibility. In practice this often means that we also demand default constructibility of the target because the overloaded pop cannot be used in an assignment:

cat fender;
stacked.pop(fender);
.... // play with fender

Another consequence of the assignment-based approach is that the result variable must be an exact type match for the element type (i.e., it cannot rely on implicit conversions that would have worked if pop's result had been returned by value).

A Transactional Approach

Staying with Combined Method, but for brevity leaving aside the code for thread synchronization, it turns out that it is possible to write an exception-neutral version of pop that preserves the original value-returning interface and satisfies the strong guarantee of exception safety in slightly different circumstances to the original:

template<typename value_type>
class stack {
public:
  ....
  value_type pop() {
    popper karl(data);
    return data.back();
  }
  ....
private:
  class popper {
  public:
    popper(std::vector<value_type> &data)
      : data(data) {}
    ~popper() {
      if(!std::uncaught_exception())
        data.pop_back();
    }
  private:
    popper(const popper &);
    std::vector<value_type> &data;
  };
  std::vector<value_type> data;
};

Here a small helper object, karl, is created to commit a pop action if the copying of the return value is successful. The popper object is passed the representation of the surrounding stack, and on destruction, it will cause a pop_back to be executed. If the copy is unsuccessful, the popper destructor will not commit the intended change, skipping the pop_back.

This approach has the benefit of preserving the signature interface and typically reducing the number of temporaries involved in copying. However, there is an important precondition that must be publicized and satisfied for popper to work as expected: pop should not be called from the destructor of another object. Why? What if the destructor is being called because the stack is being unwound by an exception? The call to std::uncaught_exception in popper's destructor will return true even if the copy is successful.

How you respond to this scenario is a matter of context-driven requirement. Either you state that the behavior of a stack is undefined in these circumstances or you define behavior for it. One definition of behavior is shown above - in the presence of existing exceptions, don't pop - but could be considered unsatisfactory because of its pessimism. An alternative, more optimistic approach is to say that our pop offers a strong guarantee of exception safety if there is no unhandled exception present when it is executed, but only the basic guarantee otherwise:

template<typename value_type>
class stack {
  ....
  class popper {
  public:
    popper(std::vector<value_type> &data)
      : data(data),
        unwinding(
            std::uncaught_exception()) {}
    ~popper() {
      if(unwinding
         || !std::uncaught_exception())
        data.pop_back();
    }
  private:
    popper(const popper &);
    std::vector<value_type> &data;
    const bool unwinding;
  };
  ....
};

std::uncaught_exception is a function that is generally not as useful as it first appears. It often leads to false confidence in code [Sutter2002], but with an understanding of its limitations, there are a few situations in which we can press it into useful service.

A Lazy Approach

It is possible to take the transactional idea a step further using a technique that I first saw Angelika Langer present at C++ World in 1999:

template<typename value_type>
class stack {
public:
  ....
  value_type pop() {
    try {
      --length;
      return data[length];
    }
    catch(...) {
      ++length;
      throw;
    }
  }
  ....
private:
  std::size_t length;
  std::vector<value_type> data;
};

Here the size of the stack is tracked in a separate variable that is incremented and decremented accordingly. It uses an exception-aware style to implement commit-rollback semantics, bumping the length count back up again if the copy from the last element fails with an exception.

The obvious benefit of this approach is that it will work independently of whether or not the stack is already unwinding because of an exception. However, the disadvantage with this approach is not so much with the extra piece of state that has been introduced but that popped elements are never actually popped. They continue to exist in the data member long after they have been popped: at least up until another modification operation requires rationalization of data with length, such as a push. A couple of minor refinements address this issue by introducing a deferred but amortized commit operation:

template<typename value_type>
class stack {
public:
  stack()
    : uncommitted(false) {}
  void push(const value_type &new_top) {
    commit();
    data.push_back(new_top);
  }
  value_type pop() {
    commit();
    try {
      uncommitted = true;
      return data.back();
    }
    catch(...) {
      uncommitted = false;
      throw;
    }
  }
  std::size_t size() const {
    commit();
    return data.size();
  }
  ....
private:
  void commit() const {
    if(uncommitted) {
      data.pop_back();
      uncommitted = false;
    }
  }
  mutable bool uncommitted;
  mutable std::vector<value_type> data;
};

Internally the committed state will be at most one element different from the uncommitted state, but externally any attempt to determine the state by calling an operation will ensure that the books are kept balanced. This constraint requires that all public functions call the commit function as their first act, which requires that the object's state to be qualified as mutable to permit updates in query functions. Thus, this design affects all member functions and imposes a little more on the class developer. The class user is, however, unaffected.

Conclusion

It is time to declare a moratorium on these exceptional experiments on abstracted cats. They have served to demonstrate that no design can be perfect, and that encapsulation is related to usability; it is not just a matter of data hiding. Although we may strive for absolute recommendations, there are times when only relative ones can be made with confidence (and caveats). Design is about compromise and about context, and therefore it is about understanding consequences. Weigh up the benefits and liabilities for a particular usage and then make your decision - what is workable in one context may be unworkable in another, and so what is "good" in one situation may be "bad" in another.

On the compromise of design in other fields I will leave you with this quote from David Pye [Petroski]:

It follows that all designs for use are arbitrary. The designer or his client has to choose in what degree and where there shall be failure. Thus the shape of all design things is the product of arbitrary choice. If you vary the terms of your compromise - say, more speed, more heat, less safety, more discomfort, lower first cost-then you vary the shape of the thing designed. It is quite impossible for any design to be "the logical outcome of the requirements" simply because, the requirements being in conflict, their logical outcome is an impossibility.

References

[Taligent] Taligent's Guide to Designing Programs: Well-Mannered Object-Oriented Design in C++, (Addison-Wesley, 1994), http://pcroot.cern.ch/TaligentDocs/TaligentOnline/DocumentRoot/1.0/Docs/books/WM/WM_1.html

[Fowler] Martin Fowler. Refactoring: Improving the Design of Existing Code (Addison-Wesley, 1999), www.refactoring.com

[Sutter2000] Herb Sutter. Exceptional C++ (Addison-Wesley, 2000).

[Stroustrup] Bjarne Stroustrup. "Sixteen Ways to Stack a Cat," C++ Report, October 1990, www.research.att.com/~bs

[Hoare] To quote C. A. R. Hoare: "There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies."

[Cargill] Tom Cargill. "Exception Handling: A False Sense of Security," C++ Report, November-December 1994.

[Henney1] Kevlin Henney. "A Tale of Two Patterns," Java Report, December 2000, www.curbralan.com

[Meyer] Bertrand Meyer. Object-Oriented Software Construction, 2nd Edition (Prentice Hall, 1997).

[Henney2] Kevlin Henney. "C++ Patterns: Executing Around Sequences," EuroPLoP 2000, July 2000, www.curbralan.com

[Sutter2002] Herb Sutter. More Exceptional C++ (Addison-Wesley, 2002).

[Petroski] Henry Petroski. To Engineer is Human: The Role of Failure in Successful Design (Vintage, 1992).

Overload Journal #62 - Aug 2004 + Design of applications and programs