Friday, December 26, 2014

Movable classes are containers

If you're writing C++11 code, you should be aware that a move constructor and move assignment operator are automatically generated if you write your classes properly. However, there are cases when making a class movable can lead to subtle bugs. This article explains the following:
  1. When we might want to store a pointer to this.
  2. Why storing a pointer to this makes it difficult to implement move operations.
  3. How move operations can be made to work using containers.
  4. Why Movable classes are containers, and why this is a problem.
Note: There exists a definition of the word "container" used by the C++ standard libraries that refers specifically to things like arrays and vectors. In this article, I use the term "container" to refer to any class whose purpose is to contain a pointer to object(s) in one way or other.
Without further ado, let us begin.

 Part 1: If only things were always this simple

Consider the following (simplified) example:
struct Node
{
    Node* Self = this;
};
In this case, it would not be correct to copy an instance of Node because the Self pointer would not be updated to point to the copied instance. There are solutions to this problem: You could disable copying of Nodes entirely (a common choice), or you could implement a custom copy constructor and copy assignment operator that correctly updates the Self pointer. The move operations can be implemented similarly, so in this case there's no real problem. However, as I'll explain in the rest of the article, things get messy when they get more complicated.

Part 2: Where things get ugly

A less obvious incarnation of this problem is when you use the popular C userdata idiom. Consider the following Win32 programming example:
struct Window
{
    HWND NativeHandle;

    Window()
    {
        NativeHandle = CreateWindow(...);

        /* more initialization code goes here */

        SetWindowLongPtr(NativeHandle, GWLP_USERDATA, (LONG_PTR) this);
    }
};
This popular pattern is used to store a pointer to our custom Window class within the Win32 native window handle. This idiom is useful because Win32 events come with the HWND ("Handle to a Window") that emitted them, which we can use to find a pointer to our own Window class. SetWindowLongPtr is the Win32 API function that allows you to specify the pointer to store with the native handle.

You might have noticed that this suffers from the same problem as the simplified example at the start of this article, but it has suddenly become much more difficult to solve the problem. We can no longer implement a hand-written copy constructor because copying a complex opaque resource like a HWND is non-trivial. If we really wanted to, we could actually still implement a move constructor and move assignment operator as long as we are careful to call SetWindowLongPtr to update the handle to point to its new owner. However, this is unwise: According to the MSDN documentation, SetWindowLongPtr is a function that can fail to execute. This is problematic because the design of C++ suggests that move operations should be noexcept. In other words, move operations should never fail.

You could argue that in your system SetWindowLongPtr would never fail in practice, but this is not a general solution to the problem. There must certainly exist similar cases out there where updating the userdata is a non-trivial operation which we can't guarantee will succeed. The only safe solution is to disable move operations entirely, which makes this class much more difficult to use because of how useful move operations are. Thus, in the next part, I will explain how to make it possible to move again.

Part 3: Containers are the solution (and the problem)

The problem in part 2 can be solved, like all other problems in computer science, by another layer of indirection. If we make our Window class a dynamically allocated member of another class, then this new container class can guarantee that the address of our Window instance does not change. It can properly disable copying, and it can safely implement move operations by (for example), swapping the contained pointers to Window instances. Here is an example of such a class:
struct WindowContainer
{
    unique_ptr<Window> ContainedWindow = make_unique<Window>();
};
(Aside: You could skip WindowContainer and just use a plain unique_ptr, but having WindowContainer makes it possible to give it convenient member functions that forward the calls to the contained Window.)

We have now solved the problem of ensuring that the address of our Window instances stay the same (by disabling both copy and move operations), while still making it possible to use move operations by using the WindowContainer instead. However, this has some disadvantages: First, additional dynamic allocations and indirect lookups are required to implement WindowContainer. Second, a pointer to a WindowContainer can't be used to represent the identity of a Window.

That second point is actually pretty annoying. It means that storing a pointer to a WindowContainer is meaningless, because WindowContainers are only used as a vehicle to transport the actual resource (the Window.) In other words, storing a pointer to a WindowContainer is pretty much meaningless because the Window it contains can be moved into a different WindowContainer with a different address. This identity problem actually affects any movable class that contains a resource, which brings me to my final point.

Part 4: Movable classes are containers

If a class is designed to be movable, then a pointer to it can no longer be used to represent the identity of what it contains. This is because its identity can freely be moved into a different object. This problem affects movable classes in general, except perhaps classes where the move operations are implemented simply as a copy (like a POD array.)

It would be a mistake to create a public API that only exposes a single Window class that behaves like WindowContainer, unless you also provide a way to refer to the identity of a Window (which becomes, in my opinion, an unnecessary complication.)

In Conclusion

Because movable classes are disconnected from their identity, it can be concluded that movable classes are containers rather than being resources themselves. Thus, if you create a class that is supposed to represent a resource, it should be neither copyable nor movable. If you want to move it, you should wrap it in a container class like a smart pointer or a standard container. This makes the relationship between container and containee explicit, and makes potential bugs more obvious to users of the API.

Appendix

 I talked a lot about disabling copy and move operations but never showed an example. Here's how you can do such a thing in C++11:
struct NoCopyNoMove
{
    // Disables the copy constructor and copy assignment operator.
    NoCopyNoMove(const NoCopyNoMove&) = delete;
    NoCopyNoMove& operator=(const NoCopyNoMove&) = delete;

    // Disables the move constructor and move assignment operator.
    NoCopyNoMove(NoCopyNoMove&&) = delete;
    NoCopyNoMove& operator=(NoCopyNoMove&&) = delete;
};

Friday, December 13, 2013

Using a Lippincott Function for Centralized Exception Handling

The lippincott function is a way to wrap the handling of many different exceptions into a single reusable function.

Consider this use case:
  • A C++ library (say, libfoo) has many distinct exception types.
  • You want to wrap the C++ library with a C API.
  • You want error codes instead of exceptions for the C API.

A simple approach is to write every C API function as follows:
typedef enum foo_Result {
    FOO_OK,
    FOO_ERROR1,
    FOO_ERROR2,
    FOO_UNKNOWN
} foo_Result;

foo_Result foo_dothing()
{
    try
    {
        // Can throw MyException1 or MyException2
        foo::DoThing();
    }
    catch (const MyException1&)
    {
        return FOO_ERROR1;
    }
    catch (const MyException2&)
    {
        return FOO_ERROR2;
    }
    catch (...)
    {
        return FOO_UNKNOWN;
    }

    return FOO_OK;
}
There are some maintenance problems with the above approach:
  • DoThing() might later throw more exception types.
  • You must repeat the exception handling code for every API function.

Jon Kalb suggests the following refactoring method, which he named after Lisa Lippincott, who taught him the technique.
foo_Result lippincott()
{
    try
    {
        throw;
    }
    catch (const MyException1&)
    {
        return FOO_ERROR1;
    }
    catch (const MyException2&)
    {
        return FOO_ERROR2;
    }
    catch (...)
    {
        return FOO_UNKNOWN;
    }
}

foo_Result foo_dothing()
{
    try
    {
        foo::DoThing();
        return FOO_OK;
    }
    catch (...)
    {
        return lippincott();
    }
}
"throw;", when inside a catch block, simply rethrows the currently caught exception. In this case, the "throw;" is not directly placed in a catch block within the lippincott() function, but it is transitively (safely) called from within the catch block of foo_dothing().

There are some important preconditions to calling lippincott():
  • You cannot call the lippincott function from outside a catch block.
    • "throw;" outside of a catch block will call std::terminate().
  •  lippincott() must be noexcept. No exceptions should escape it.
    • The exception will leak out of the C API otherwise.

If we want extra safety, we can implement safeguards for the aforementioned preconditions:

To safely handle a violation of the first precondition, we can check that std::current_exception()  is not null previous to doing the "throw;"

To prevent an exception from being thrown out of lippincott(), we can wrap the whole body of the function in a try/catch.

Here is the "extra safe"/paranoid version of lippincott():
foo_Result lippincott()
try
{
    try
    {
        if (std::exception_ptr eptr = std::current_exception())
        {
            std::rethrow_exception(eptr);
        }
        else
        {
            return FOO_UNKNOWN;
        }
    }
    catch (const MyException1&)
    {
        return FOO_ERROR1;
    }
    catch (const MyException2&)
    {
        return FOO_ERROR2;
    }
    catch (...)
    {
        return FOO_UNKNOWN;
    }
}
catch (...)
{
    return FOO_UNKNOWN;
}
The C API can now be written entirely in the style of foo_dothing(), which will centralize the error code conversion through the lippincott function.

Another interesting idea is to use the lippincott function to convert exceptions into string representations for debugging. This area is especially in need of the extra try/catch surrounding the function, since allocating dynamic strings can fail.

Full working example: http://ideone.com/m2ZfHN

The term "lippincott function" was popularized by Jon Kalb in his exception-safe coding talks.
You can find his explanation here: youtube link

Wednesday, December 4, 2013

Correcting the transitivity of const in C++

C++ allows you to make an instance of a class const. This normally prevents making changes to any member variables and also prevents the user to call any member functions which are not also marked const.

There is, however, a quirk which you must be aware of. Consider the following code:
struct A {
    int* x;
    A(): x{new int} {}
   ~A() { delete x; }
};

int main()
{
    const A a;
    *a.x = 3;
}
This code compiles and runs with no problems, even though it might appear to be writing over a read-only piece of data.
The type of a.x reveals the reason why this is allowed:
int * const
This denotes a "Constant pointer to int", which is different from a "Pointer to a constant int" or a "Constant pointer to a constant int".
In this case of "Constant pointer to int", overwriting the pointer is not allowed, but overwriting the int it points to is possible.
This may be desired behaviour in some cases, but in others it is not.

This differs from the D Programming Language, where both const and immutable are transitive by default (although in a slightly different but cool way.)

One simple way to prevent the possibly undesired behaviour is to use access modifiers and getters to prevent direct access from the user:
struct A {
    A(): x_{new int} {}
   ~A() { delete x_; }

          int& x()       { return *x_; }
    const int& x() const { return *x_; }
private:
    int* x_;
};
Now it is impossible* to access a mutable reference to *x_ through a const A.
However, it is still possible to write to *x_ from within const member functions of A. This makes it possible for const member functions to have side-effects on the class which are unexpected by the user.
[*]: again, nothing is impossible in C++.

C++11's smart pointers also have the property of not being transitively const.
Note the signatures of these std::unique_ptr member functions:
pointer std::unique_ptr::get() const;

typename std::add_lvalue_reference<T>::type
         operator*() const;  

pointer operator->() const;
These methods all return non-const pointers and references, even if the method is called on a const std::unique_ptr instance.

We could keep enforcing the transitive const relationship by writing the const and non-const getters for every publicly exposed member, but there exists a more general way to solve this problem: We can write a smart pointer with built-in transitivity for const.

std::unique_ptr is not far from the mark, so let's work on top of it:
template<
    class T,
    class Deleter = std::default_delete<T>
> class transitive_ptr : public std::unique_ptr<T,Deleter>
{
public:
    // inherit typedefs for the sake of completeness
    typedef
        typename std::unique_ptr<T,Deleter>::pointer
        pointer;
    typedef
        typename std::unique_ptr<T,Deleter>::element_type
        element_type;
    typedef
        typename std::unique_ptr<T,Deleter>::deleter_type
        deleter_type;

    // extra typedef
    typedef
        const typename std::remove_pointer<pointer>::type*
        const_pointer;

    // inherit std::unique_ptr's constructors
    using std::unique_ptr<T,Deleter>::unique_ptr;
 
    // add transitively const version of get()
    pointer get() {
        return std::unique_ptr<T,Deleter>::get();
    }
    const_pointer get() const {
        return std::unique_ptr<T,Deleter>::get();
    }

    // add transitively const version of operator*()
    typename std::add_lvalue_reference<T>::type
    operator*() {
        return *get();
    }
    typename std::add_lvalue_reference<const T>::type
    operator*() const {
        return *get();
    }
 
    // add transitively const version of operator->()
    pointer operator->() {
        return get();
    }
    const_pointer operator->() const {
        return get();
    }
};
Attempting to write to a transitively const instance of a pointer will now fail, and our class declaration is also much more concise because we were able to convey the rules for using x within its type:
struct A {
    transitive_ptr<int> x;
    A(): x{new int} {}
};

int main() {
    const A a;
    *a.x = 3;
}
Compiler output:
error: assignment of read-only location 
‘a.A::x.transitive_ptr<T, Deleter>::operator*
<int, std::default_delete<int> >()’
*a.x = 3;
     ^
This is another useful smart pointer to add to our smart pointer tool box, getting us one step closer to always correctly enforcing the rule of zero.

Full working example: http://ideone.com/0RUr3V

Friday, November 29, 2013

D's scope statement in C++


The D Programming Language brings a unique feature: The scope statement. In this C++ secret, I will explain how to implement it in C++.

Disclaimer


Some parts here get tricky, and I don't claim to be a C++ god. If something looks strange to you, then something could really be wrong. Do some research and please tell me what you think!

Introduction


For The Innocents among you who don't know about D's scope feature, please read Dlang's official documentation for a good explanation.

In summary, the scope statement allows you to specify blocks of code to be run at the end of their scope, and conditionally executed based on whether the scope was exited by an exception or not.

In D, the usage is as follows (from dlang.org):
void abc()
{
    Mutex m = new Mutex;

    lock(m); // lock the mutex
    scope(exit) unlock(m); // unlock on leaving the scope

    foo(); // do processing
}
In normal everyday C++, we use RAII to achieve the same effect:
struct lock_guard {
    std::mutex& m_;
    lock_guard(std::mutex& m) : m_(m) { m_.lock(); }
    ~lock_guard() { m_.unlock(); }
};

void abc()
{
    std::mutex m;
    lock_guard guard { m }; // Locks the mutex.
    foo();    
    // ~lock_guard() unlocks the mutex upon leaving the scope.
}
The beauty of this pattern is that ~lock_guard() is guaranteed* to be called upon unwinding the stack, no matter if foo() throws an exception or not. This is an important part of writing exception-safe code.

[*] Nothing is guaranteed in C++: Destructors are not invoked if a thrown exception will never be caught, because in this scenario no exception handler is installed. Also, if a destructor leaks out an exception while another exception is in flight, then all bets are off.

The custom lock_guard class is not necessary, it is part of the C++ standard library.

This might look all good so far, but the problem arises when, for example, we want to use a C library which does not offer convenient C++ RAII resource handles like std::lock_guard. This forces exception-conscious C++ users to write tons of little RAII resource handling classes. On the other hand, if C++ had a scope statement, these boilerplate RAII bindings would not be necessary!

The Goal


Enough talk, here is my promise to you. This C++ Secret allows the following code:
void abc()
{
    // We are manipulating a non-RAII C resource.
    pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
    pthread_mutex_lock(&m); // lock mutex
    scope (exit) {
        // unlock on leaving the scope
        pthread_mutex_unlock(&m);
    };
    foo(); // Do dangerous work which may throw an exception
}
Come hell or high water, this code will not leak the mutex. It will always be unlocked upon exiting the scope of that function, whether through normal code flow or through an exception being raised in foo().

Scope Guard


Everything begins with the scope_guard class, which will store a function object to call upon cleanup, a policy for how that cleanup should be used, and a policy for installing the scope block.
template<typename F, typename CleanupPolicy>
class scope_guard : CleanupPolicy, CleanupPolicy::installer
{
    using CleanupPolicy::cleanup;
    using CleanupPolicy::installer::install;
 
    typename std::remove_reference<F>::type f_;
 
public:
    scope_guard(F&& f) : f_(std::forward<F>(f)) {
        install();
    }
    ~scope_guard() {
        cleanup(f_);
    }
};
This class will store a routine to run at the end of the scope, and the CleanupPolicy has the right to decide how to invoke it. More on the CleanupPolicy's installer later.

Note the use of perfect forwarding to handle both lvalue and rvalue references in one fell swoop.

Installation Policies


These polices define some code to be run at the initialization of a scope_guard.
struct unchecked_install_policy {
    void install() { }
};
 
struct checked_install_policy {
    void install() {
        if (std::uncaught_exception()) {
            std::terminate(); // sorry
        }
    }
};
The installation policies solve an important problem: If an exception is currently in flight, a scope (success) or scope (failure) statement is not able to distinguish between that current exception and any other one thrown after it in the same scope. In this case, the scope (success) and scope (failure) statements behave incorrectly because they can confuse one exception for another.

The only time when an exception is "currently in flight" is during the call to destructors while unwinding the stack. Therefore, we establish and enforce an important invariant to be upheld by the programmer:

ONE CANNOT USE EITHER OF
scope (failure)
scope (success)
WITHIN A DESTRUCTOR!

This includes functions called from destructors.

scope (exit), on the other hand, is always ok. Knock yourself out!

Cleanup Policies


Next, we will define the cleanup policies. Their behaviours are:
  • exit: cleanup will happen come hell or high water.
  • failure: cleanup will happen only if the scope is exited by an exception.
  • success: cleanup will happen only if the scope is exited normally.
An appropriate installation policy is also defined for each cleanup policy.
struct exit_policy {
    typedef unchecked_install_policy installer;

    template<typename F>
    void cleanup(F& f) {
        f();
    }
};

struct failure_policy {
    typedef checked_install_policy installer;

    template<typename F>
    void cleanup(F& f) {
        // Only cleanup if we're exiting from an exception.
        if (std::uncaught_exception()) {
            f();
        }
    }
};

struct success_policy {
    typedef checked_install_policy installer;

    template<typename F>
    void cleanup(F& f) {
        // Only cleanup if we're NOT exiting from an exception.
        if (!std::uncaught_exception()) {
           f();
        }
    }
};
As you can see, exit_policy calls the cleanup unconditionally. Meanwhile, the failure_policy and success_policy use std::uncaught_exception() to check if an exception is currently "in flight" as we are unwinding the stack, which allows them to decide if the cleanup should be made or not.

Furthermore, exit_policy has no checking required during the installation, while failure_policy and success_policy enforce the invariant that no exceptions can be in flight at the time of installing the guard. WITH DEADLY FORCE!

We can test what we have so far:
void SayBye()
{
    std::cout << "Bye bye!\n";
}

int main()
{
    scope_guard<void (*)(), exit_policy>
        sayByeOnExit { SayBye };

    std::cout << "Hello!\n";
}
Output:
Hello!
Bye bye!
As expected, the call to SayBye is deferred until we exit from the scope of main().

Syntactical Sugar


Now that we have nailed down the mechanics, here comes the syntactical sugar.
template<typename CleanupPolicy>
struct scope_guard_builder { };
 
template<typename F, typename CleanupPolicy>
scope_guard<F,CleanupPolicy>
operator+(
    scope_guard_builder<CleanupPolicy> builder,
    F&& f
    )
{
    return std::forward<F>(f);
}

// typical preprocessor utility stuff.
#define PASTE_TOKENS2(a,b) a ## b
#define PASTE_TOKENS(a,b) PASTE_TOKENS2(a,b)

#define scope(condition) \
    auto PASTE_TOKENS(_scopeGuard, __LINE__) = \
        scope_guard_builder<condition##_policy>() + [&]

int main()
{
    scope (exit) {
        std::cout << "Bye bye!\n";
    };

    std::cout << "Hello!\n";
}
Output:
Hello!
Bye bye!
An instance of scope_guard is put on the stack with an automatically generated name made from "_scopeGuard" and the current line number.

Since C++ cannot infer template arguments from arguments passed to a constructor, we cannot simply assign a lambda to a scope_guard. Instead, we use a factory function, which happens to be operator+.

The first argument is an empty struct scope_guard_builder, which is only used to infer the CleanupPolicy type. The condition argument to the scope macro is used to deduce the cleanup policy to use.

The second argument is a function object, which is used to construct the returned scope_guard. The scope macro passes a lambda, which captures its enclosing scope's automatic variables by reference, as this second argument.

operator+ was chosen simply because it is an infix operator. If a regular function would have been used instead of an infix operator, the usage would look something like:
scope (exit) {
    std::cout << "bye\n";
});
Note the outstanding right parenthesis at the end, which would be required to end the regular (prefix notation) function call to which the lambda would be passed.

Instead, the lambda's capture list is part of the macro ("[&]") and the lambda's body is conveniently used as the syntax for the scope statement's block. This also allows you to enhance scope blocks by configuring their lambda's mutability, exception specification, and attribute specification.

Conclusion


To conclude, here is a relatively robust unit test.

The runtime error at the end is intentional - it shows that we enforce the rule that only scope (exit) can be used in destructors.
struct HasScopeExitInDtor {
    ~HasScopeExitInDtor() {
        scope (exit) {
            std::cout << "scope (exit) in dtor success test\n";
        };
        try {
            std::cout << "scope (exit) in dtor failure test\n";
            throw 1;
        } catch (...) { }
    }
};

struct HasScopeSuccessInDtor {
    ~HasScopeSuccessInDtor() {
        std::cout << std::flush;
        scope (success) {
            std::cout << "error: scope (success) used in dtor\n";
        };
    }
};

int main()
{
    {
        const char* captureTest = nullptr;
        scope (exit) {
            std::cout << "scope (exit) success test\n";
            std::cout << "captureTest: " << captureTest;
        };
        scope (success) {
            std::cout << "scope (success) success test\n";
        };
        scope (failure) {
            std::cout << "scope (failure) success test\n";
        };
        captureTest = "ok\n";
    }
    try {
        HasScopeSuccessInDtor s;
  
        scope (exit) {
            std::cout << "scope (exit) failure test\n";
        };
        scope (success) {
            std::cout << "scope (success) failure test\n";
        };
        scope (failure) {
            std::cout << "scope (failure) failure test\n";
        };
  
        HasScopeExitInDtor e;
  
        throw 1;
    } catch (...) { }
}
Output:
scope (success) success test
scope (exit) success test
scope (exit) in dtor failure test
scope (exit) in dtor success test
scope (failure) failure test
scope (exit) failure test
terminate called without an active exception
Beautiful.

Here is the fully functional example: http://ideone.com/2IpHBG

In general, I believe that this makes it easy to write code that is readable and exception-safe. There is only a minor runtime performance cost.

I would personally like scope to be a built-in feature of C++ so that it could be better supported by the compilers themselves.

One downside to this implementation is that the unique name generated by pasting _scopeGuard with __LINE__ disallows using more than one scope statement on the same line. One option is to use __COUNTER__ instead, but it's not standard. This is a minor use case, so I'll let it slide for now.

The major downside is the inability to call scope (success) or scope (failure) within a destructor. Some alternate implementations below address this in interesting ways.

Special Thanks


Thanks to edoceo` in ##C++ on irc.freenode.net for various suggestions and valuable criticism.

Thanks to The One And Only Andrei Alexandrescu for explaining to me the bug of calling scope (success) and scope (failure) within destructors.

Thanks to my colleague, JP Flouret, for helping me remember that, sometimes, less is more.

Further Research


Here are some alternate implementations of the ScopeGuard pattern:

Github


https://github.com/nguillemot/scope
  

Thursday, November 28, 2013

Hello, World!

Hello, welcome to the blog.

I will share some C++ secrets with you on this blog.

Stay tuned.