Octopull/C++: "Here be Dragons"

"Here be Dragons"by Alan Griffiths

"The use of animals in maps was commonplace from the earliest times. Man's deepest fears and superstitions concerning wide expanses of uncharted seas and vast tracts of 'terra incognita' were reflected in the monstrous animals that have appeared on maps ever since the Mappa Mundi." (Roderick Barron in "Decorative Maps")

For many developers C++ exception handling is like this - a Dark Continent with poor maps and rumours of ferocious beasts. I'm Alan Griffiths and I'm your guide to the landmarks and fauna of this region.

In order to discuss exception safety we need to cover a lot of territory. The next section identifies the "exception safe" mountains in the distance. Please don't skip it in the hope of getting to the good stuff - if you don't take the time to get your bearings now you'll end up in the wastelands.

Once I've established the bearings I'll show you a well-trodden path that leads straight towards the highest peak and straight through a tar pit. From experience, I've concluded that everyone has to go down this way once. So I'll go with you to make sure you come back. Not everyone comes back; some give up on the journey, others press on deeper and deeper into the tar pit until they sink from sight.

On our journey I'll tell you the history of how the experts sought for a long time before they discovered a route that bypasses that tar pit and other obstacles. Most maps don't show it yet, but I'll show you the signs to look out for. I'll also show you that the beasts are friendly and how to enlist their aid.

If you look into the distance you'll see a range of peaks, these are the heights of exception safety and are our final destination. But before we proceed on our trek let me point out two of the most important of these peaks, we'll be using them as landmarks on our travels…

The difficulty in writing exception safe code isn't in writing the code that throws an exception, or in writing the code that catches the exception to handle it. There are many sources that cover these basics. I'm going to address the greater challenge of writing the code that lies in between the two.

Imagine for a moment the call stack of a running program, function a() has called function b(), b() has called c(), and so on, until we reach x(); x() encounters a problem and throws an exception. This exception causes the stack to unwind, deleting automatic variables along the way, until the exception is caught and dealt with by a().

I'm not going to spend any time on how to write functions a() or x(). I'm sure that the author of x() has a perfectly good reason for throwing an exception (running out of memory, disc storage, or whatever) and that the author of a() knows just what to do about it (display: "Sorry, please upgrade your computer and try again!").

The difficult problem is to write all the intervening functions in a way that ensures that something sensible happens as a result of this process. If we can achieve this we have "exception safe" code. Of course, that begs the question "what is something sensible?" To answer this let us consider a typical function f() in the middle of the call stack. How should f() behave?

Well, if f() were to handle the exception it might be reasonable for it to complete its task by another method (a different algorithm, or returning a "failed" status code). However, we are assuming the exception won't be handled until we reach a(). Since f() doesn't run to completion we might reasonably expect that:

1. f() doesn't complete its task.

2. If f() has opened a file, acquired a lock on a mutex, or, more generally; if f() has "allocated a resource" then the resource should not leak. (The file must be closed, the mutex must be unlocked, etc.)

3. If f() changes a data structure, then that structure should remain useable - e.g. no dangling pointers.

In summary: If f() updates the system state, then the state must remain valid. Note that isn't quite the same as correct - for example, part of an address may have changed leaving a valid address object containing an incorrect address.

I'm going to call these conditions the basic exception safety guarantee, this is the first, and smaller of our landmark mountains. Take a good look at it so that you'll recognise it later.

The basic exception safety guarantee may seem daunting but not only will we reach this in our travels, we will be reaching an even higher peak called the strong exception safety guarantee that places a more demanding constraint on f():

4. If f() terminates by propagating an exception then it has made no change to the state of the program.

Note that it is impossible to implement f() to deliver either the basic or strong exception safety guarantees if the behaviour in the presence of exceptions of the functions it calls isn't known. This is particularly relevant when the client of f() (that is e()) supplies the functions to be called either as callbacks, as implementations of virtual member functions, or via template parameters. In such cases the only recourse is to document the constraints on them - as, for example, the standard library does for types supplied as template parameters to the containers.

If we assume a design with fully encapsulated data then each function need only be held directly responsible for aspects of the object of which it is a member. For the rest, the code in each function must rely on the functions it calls to behave as documented. (We have to rely on documentation in this case, since in C++ there is no way to express these constraints in the code.)

We'll rest here a while, and I'll tell you a little of the history of this landscape. Please take the time to make sure that you are familiar with these two exception safety guarantees. Later, when we have gained some altitude we will find that there is another peak in the mountain range: the no-throw exception safety guarantee - as the name suggests this implies that f() will never propagate an exception.

The C++ people first came to visit the land of exceptions around 1990 when Margaret Ellis and Bjarne Stroustrup published the "Annotated Reference Manual" [1]. Under the heading "experimental features" this described the basic mechanisms of exceptions in the language. In this early bestiary there is an early description of one of the friendly beasts we shall be meeting later on: it goes by the strange name of RESOURCE ACQUISITION IS INITIALISATION.

By the time the ISO C++ Standards committee circulated "Committee Draft 1" in early 1995 C++ people were truly living in exception land. They hadn't really mapped the territory or produced an accurate bestiary but they were committed to staying and it was expected that these would soon be available.

However, by late 1996 when "Committee Draft 2" was circulated the difficulties of this undertaking had become apparent. Around this time there came a number of reports from individual explorers. For example: Dave Abrahams identified the mountains we are using as landmarks in his paper "Exception Safety in STLPort" [2] although the basic exception safety guarantee was originally dubbed the "weak exception safety guarantee".

Some other studies of the region were produced by H Muller [3], Herb Sutter [4] and [5]. A little later came a sighting of another of the friendly beast that we will meet soon called ACQUISITION BEFORE RELEASE. This beast was first known by a subspecies named it COPY BEFORE RELEASE and was identified by Kevlin Henney [6] it is distinguished by the resources allocated being copies of dynamic objects.

By the time the ISO C++ Language Standard was published in 1998 the main tracks through the territory had been charted. In particular there are clauses in the standard guaranteeing the behaviour of the standard library functions in the presence of exceptions. Also, in a number of key places within the standard, special mention is made of another friendly beast - SWAP in its incarnation as the std::swap() template function. We will be examining SWAP after our detour through the tar pit.

Since the publication of the ISO standard more modern charts have been produced: the author in an early version of this article [7]. A similar route is followed by Bjarne Stroustrup [8]. Herb Sutter [9] takes a different route, but the same landmarks are clearly seen.

OK, that's enough rest, we are going to take the obvious path and head directly towards the strong exception safety guarantee.

It is time to consider an example function, and for this part of the journey I have chosen the assignment operator for the following class:

class PartOne   { /* omitted */ };
class PartTwo   { /* omitted */ };

class Whole
{
public:
    // ...Lots omitted...

    Whole& operator=(const Whole& rhs);
    
private:
    PartOne*    p1;
    PartTwo*    p2;
};

Those of you that have lived in the old country will know the classical form for the assignment operator. It looks something like the following:

Whole& Whole::operator=(const Whole& rhs)
{
    if (&rhs != this)
    {
        delete p1;
        delete p2;
        p1 = new PartOne(*rhs.p1);
        p2 = new PartTwo(*rhs.p2);
    }
    return *this;
}

If you've not seen this before, don't worry because in the new land it is not safe. Either of the new expressions could reasonably throw (since at the very least they attempt to allocate memory) and this would leave the p1 and p2 pointers dangling. In theory the "delete" expressions could also throw - but in this article we will assume that destructors never propagate exceptions. (See: "destructors that throw exceptions".)

The obvious solution to the problems caused by an exception being propagated is to catch the exception and do some clean up before throwing it again. After doing the obvious we have:

Whole& Whole::operator=(const Whole& rhs)
{
    if (&rhs != this)
    {
        PartOne* t1 = new PartOne(*rhs.p1);

        try 
        {
            PartTwo* t2 = new PartTwo(*rhs.p2);

            delete p1;
            delete p2;

            p1 = t1;
            p2 = t2;
        }
        catch (...)
        {
            delete t1;
            throw;
        }
    }
    return *this;
}

Let's examine why this works:

1. An exception in the first new expression isn't a problem - we haven't yet allocated any resources or modified anything.

2. If an exception is propagated from the second new expression, we need to release t1. So we catch it, delete t1 and throw the exception again to let it propagate.

3. We are assuming that destructors don't throw, so we pass over the two deletes without incident. Similarly the two assignments are of base types (pointers) and cannot throw an exception.

4. The state of the Whole isn't altered until we've done all the things that might throw an exception.

If you peer carefully through the undergrowth you can see the first of the friendly beasts. This one is called ACQUISITION BEFORE RELEASE. It is recognised because the code is organised so that new resources (the new PartOne and PartTwo) are successfully acquired before the old ones are released.

We've achieved the strong exception safety guarantee on our first attempt! But there is some black sticky stuff on our boots.

There are problems lying just beneath the surface of this solution. I chose an example that would enable us to pass over the tar pit without sinking too deep. Despite this, we've incurred costs: the line count has doubled and it takes a lot more effort to understand the code well enough to decide that it works.

If you want to, you may take some time out to convince yourself of the existence of the tar pit - I'll wait. Try the analogous example with three pointers to parts or replacing the pointers with two parts whose assignment operators may throw exceptions. With real life examples things get very messy very quickly.

Many people have reached this point and got discouraged. I agree with them: routinely writing code this way is not reasonable. Too much effort is expended on exception safety housekeeping chores like releasing resources. If you hear that "writing exception safe code is hard" or that "all those try...catch blocks take up too much space" you are listening to someone that has discovered the tar pit.

I'm now going to show you how exception handling allows you to use less code (not more), and I'm not going to use a single try…catch block for the rest of the article! (In a real program the exception must be caught somewhere - like function a() in the discussion above, but most functions simply need to let the exceptions pass through safely.)

There are three "golden rules":

1. Destructors may not propagate exceptions,

2. The states of two instances of a class may be swapped without an exception being thrown,

3. An object may own at most one resource,

We've already met the first rule.

The second rule isn't obvious, but is the basis on which SWAP operates and is key to exception safety. The idea of SWAP is that for two instances of a class that owns resources exchanging the states is feasible without the need to allocate additional resources. Since nothing needs to be allocated, failure needn't be an option and consequently neither must throwing an exception. (It is worth mentioning that the no-throw guarantee is not feasible for assignment, which may have to allocate resources.)

If you look at the ISO C++ Language Standard, you'll find that std::swap() provides the no-throw guarantee for fundamental types and for relevant types in the standard library. This is achieved by overloading std::swap() - e.g. there is a template corresponding to each of the STL containers. This looks like a good way to approach SWAP but introducing additional overloads of std::swap() is not permitted by the language standard. The standard does permit to explicit specialisation of an existing std::swap() template function on user defined classes and this is what I would recommend doing where applicable (there is an example below). The standards committee is currently considering a defect report that addresses the problem caused by these rules for the authors of user defined template classes. (See: Standard Algorithms and User Defined Template Classes.)

The third rule addresses the cause of all the messy exception handling code we saw in the last section. It was because creating a new second part might fail that we wrote code to handle it and doubled the number of lines in the assignment operator.

We'll now revisit the last example and make use of the above rules. In order to conform to the rule regarding ownership of multiple objects we'll delegate the responsibility of resource ownership to a couple of helper classes. I'm using the std::auto_ptr<> template to generate the helper classes here because it is standard, not because it is the ideal choice. (See: "The Trouble With std::auto_ptr<>" for reasons to avoid using auto_ptr<> in this context.)

class Whole {
public:
    // ...Lots omitted...

    Whole& operator=(const Whole& rhs);

private:
    std::auto_ptr<PartOne>    p1;
    std::auto_ptr<PartTwo>    p2;
};


Whole& Whole::operator=(const Whole& rhs)
{
    std::auto_ptr<PartOne> t1(new PartOne(*rhs.p1));
    std::auto_ptr<PartTwo> t2(new PartTwo(*rhs.p2));

    std::swap(p1, t1);
    std::swap(p2, t2);

    return *this;
}

Not only is this shorter than the original exception-unsafe example, it meets the strong exception safety guarantee.

Look at why it works:

1. There are no leaks: whether the function exits normally, or via an exception, t1 and t2 will delete the parts they currently own.

2. The swap expressions cannot throw (second rule).

3. The state of the Whole isn't altered until we've done all the things that might throw an exception.

Oh, by the way, I've not forgotten about self-assignment. Think about it - you will see the code works without a test for self-assignment. Such a test may be a bad idea: assuming that self-assignment is very rare in real code and that the branch could have a significant cost Francis Glassborow suggested a similar style of assignment operator as a speed optimisation [10]. Following on from this, Kevlin Henney explored its exception safety aspects in [11], [12] and [6].

We are on much firmer ground than before: it isn't hard to see why the code works and generalising it is simple. You should be able to see how to manage a Whole with three auto_ptrs to Parts without breaking stride.

You can also see another of the friendly beasts for the first time. Putting the allocation of a resource (here a new expression) into the initialiser of an instance of a class (eg auto_ptr<PartOne>) that will delete it on destruction is RESOURCE ACQUISITION IS INITIALISATION. And, of course, we can once again see ACQUISITION BEFORE RELEASE.

(Yes, in this case we could use assignment instead of SWAP to make the updates. However with a more complex type SWAP is necessary, as we shall see later. I use SWAP in this example for consistency.)

Before I go on to deal with having members that may throw when updated, I've a confession I need to make. It is possible, and usual, to write the assignment operator more simply than the way I've just demonstrated. The above method is more general than what follows and can be applied when only some aspects of the state are being modified. The following applies only to assignment:

Whole& Whole::operator=(const Whole& rhs)
{
    Whole(rhs).swap(*this);
    return *this;
}

Remember the second rule: Whole is a good citizen and provides for SWAP (by supplying the swap() member function). I also make use of the copy constructor - but it would be a perverse class design that supported assignment but not copy construction. I'm not sure whether the zoologists have determined the relationship between SWAP and copying here, but the traveller won't go far wrong in considering COPY AND SWAP as species in it own right.

For completeness, I'll show the methods used above:

void Whole::swap(Whole& that)
{
    std::swap(p1, that.p1);
    std::swap(p2, that.p2);
}

Whole::Whole(const Whole& rhs)
:   p1(new PartOne(*rhs.p1)),
    p2(new PartTwo(*rhs.p2))
{
}

One further point about making Whole a good citizen is that we need to specialise std::swap() to work through the swap() member function. By default std::swap() will use assignment - and not deliver the no-throw guarantee we need for SWAP. The standard allows us to specialise existing names in the std namespace on our own types, and it is good practice to do so in the header that defines the type.

namespace std
{
    template<>
    inline void swap(exe::Whole& lhs, exe::Whole& rhs)
    {
        lhs.swap(rhs);
    }
}

This avoids any unpleasant surprises for client code that attempts to swap() two Wholes.

Although we've focused on attaining the higher peak of strong exception safety guarantee, we've actually covered all the essential techniques for achieving either strong or basic exception safety. The remainder of the article shows the same techniques being employed in a more complex example and gives some indication of the reasons you might choose to approach the lesser altitudes of basic exception safety.

We can't always rely on bright sunshine, or on member variables that are as easy to manipulate as pointers. Sometimes we have to deal with rain and snow, or base classes and member variables with internal state.

To introduce a more complicated example, I'm going to elaborate the Whole class we've just developed by adding methods that update p1 and p2. Then I'll derive an ExtendedWhole class from it that also contains an instance of another class: PartThree. We'll be assuming that operations on PartThree are exception safe, but, for the purposes of discussion, I'll leave it open whether PartThree offers the basic or the strong exception safety guarantee.

Whole& Whole::setP1(const PartOne& value)
{
    p1.reset(new PartOne(value));
    return *this;
}


Whole& Whole::setP2(const PartTwo& value)
{
    p2.reset(new PartTwo(value));
    return *this;
}


class ExtendedWhole : private Whole
{
public:

    // Omitted constructors & assignment

    void swap(const ExtendedWhole& rhs);

    void setParts(
        const PartOne& p1,
        const PartTwo& p2,
        const PartThree& p3);

private:
    int       count;
    PartThree body;
};

The examples we've looked at so far are a sufficient guide to writing the constructors and assignment operators. We are going to focus on two methods: the swap() member function and a setParts() method that updates the parts.

Writing swap() looks pretty easy - we just swap the base class, and each of the members. Since each of these operations is "no-throw" the combination of them is also "no-throw".

void ExtendedWhole::swap(ExtendedWhole& rhs)
{
    Whole::swap(rhs);
    std::swap(count, rhs.count);
    std::swap(body,  rhs.body);
}

Writing setParts() looks equally easy: Whole provides methods for setting p1 and p2, and we have access to body to set that. Each of these operations is exception safe, indeed the only one that need not make the strong exception safety guarantee is the assignment to body. Think about it for a moment: is this version of setParts() exception safe? And does it matter if the assignment to body offers the basic or strong guarantee?

void ExtendedWhole::setParts(
    const PartOne& p1,
    const PartTwo& p2,
    const PartThree& p3)
{
    setP1(p1);
    setP2(p2);
    body = p3;
}

Let's go through it together, none of the operations leak resources, and setParts() doesn't allocate any so we don't have any leaks. If an exception propagates from any of the operations, then they leave the corresponding sub-object in a useable state, and presumably that leaves ExtendedWhole useable (it is possible, but in this context implausible, to construct examples where this isn't true). However, if an exception propagates from setP2() or from the assignment then the system state has been changed. And this is so regardless of which guarantee PartThree makes.

The simple way to support the strong exception safety guarantee it to ensure that nothing is updated until we've executed all the steps that might throw an exception. This means taking copies of sub-objects and making the changes on the copies, prior to swapping the state between the copies and the original sub-objects:

void ExtendedWhole::setParts(
    const PartOne& p1,
    const PartTwo& p2,
    const PartThree& p3)
{
    Whole temp(*this);
    temp.setP1(p1).setP2(p2);
    body = p3;
    Whole::swap(temp);
}

Once again does it matter if the assignment to body offers the basic or strong guarantee? Yes it does, if it offers the strong guarantee then all is well with the above, if not then the assignment needs to be replaced with COPY AND SWAP vis:

PartThree(p3).swap(body);

Once again we have attained the highest peak, but this may not be healthy. On terrestrial mountains above a certain height there is a "death zone" where the supply of oxygen is insufficient to support life. Something similar happens with exception safety: there is a cost to implementing the strong exception safety guarantee. Although the code you write isn't much more complicated than the 'basic' version, additional objects are created and these allocate resources at runtime. This causes the program to make more use of resources and to spend time allocating and releasing them.

Trying to remain forever at high altitude will drain the vitality. Fortunately, the basic exception safety guarantee is below the death zone: when one makes a composite operation whose parts offer this guarantee one automatically attains the basic guarantee (as the first version of setParts() shows this is not true of the strong guarantee). From the basic guarantee there is an easy climb from this level to the strong guarantee by means of COPY AND SWAP.

Before we descend from the peak of strong exception safety guarantee and return to our starting point look back over the route we covered. In the distance you can see the well-trampled path that led to the tar pit and just below us the few tracks leading from the tar pit up a treacherous scree slope to where we stand. Off to the left is the easier ridge path ascending from basic exception safety guarantee and beyond that the road that led us past the tar pit. Fix these landmarks in your mind and remember that the beasts we met are not as fierce as their reputations.

References

Top   The mountains   A history of this territory   Tar!   The royal road   The assignment operator   In bad weather   Looking back

Top   The mountains   A history of this territory   Tar!   The royal road   The assignment operator   In bad weather   Looking back

using std::swap;
swap(t1, t2);

Top   The mountains   A history of this territory   Tar!   The royal road   The assignment operator   In bad weather   Looking back

Top   The mountains   A history of this territory   Tar!   The royal road   The assignment operator   In bad weather   Looking back

int ExtendedWhole::setParts(
    const PartOne& p1,
    const PartTwo& p2,
    const PartThree& p3)
{
    Whole tw;
    int rcode = tw.init(*this);
    
    if (!rcode) rcode = tw.setP1(p1);

    if (!rcode) rcode = tw.setP2(p2);

    if (!rcode)
    {
        PartThree t3;
        rcode = t3.copy(p3);

        if (!rcode)
        {
            Whole::swap(tw);
            body.swap(t3);
        }
    }
    
    return rcode;
}

Top   The mountains   A history of this territory   Tar!   The royal road   The assignment operator   In bad weather   Looking back

Copyright 1999, 2000 Alan Griffiths