Title: From Mechanism to Method: The Safe Stacking of Cats

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:

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.

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:

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

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

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

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

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.

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.

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).

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.

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.