Playful Programming

Saturday, December 13, 2014

Introducing the Trompeloeil C++ Mocking framework

Trompeloeil is a new mocking framework for C++, aimed at ease of use without sacrificing expressive power.

In arts, trompeloeil is intended to mock your mind, making you believe you see something that isn't what it appears to be. In unit tests, we use use mocks to fool the unit under test, so that we can break dependencies and test small pieces in isolation.

Trompeloeil requires a reasonably C++14 compliant compiler (gcc-4.9 and clang-3.5 are known to work.) It is a single header file only, so there is no need to worry about compiler-flag compatibility issues between the test code and the framework. Trompeloeil is released under the BOOST SOFTWARE LICENSE 1.0.

Simple Example

Let's dive in to mocking with Trompeloeil by writing tests for the order class of a warehouse, following the example in Martin Fowler's post Mocks Aren't Stubs.

The order class looks like below:

class Order
{
public:
  Order(const std::string& name, size_t amount);
  void fill(Warehouse& w);
  bool is_filled() const;
};

Warehouse in an interface looking like this:

class Warehouse
{
public:
  virtual bool hasInventory(const std::string& name, size_t amount) const = 0;
  virtual void remove(const std::string& name, size_t amount) = 0;
};

From the interface, a mock class can be created. The mechanism is nearly identical to that of GoogleMock.

class WarehouseMock : public Warehouse
{
public:
  MAKE_CONST_MOCK2(hasInventory, bool(const std::string&, size_t));
  MAKE_MOCK2(remove, void(const std::string&, size_t));
};

MAKE_MOCKn creates a mock implementation of a non-const member function with n parameters, and MAKE_CONST_MOCKn creates a mock implementation of a const member function. The first parameter of each macro is the name of the member function, and the second parameter is the function signature. Trompeloeil supports up to 15 parameters in a function signature.

From this we can write a first simple test for the Order class.

TEST(filling_removes_inventory_if_in_stock)
{
  Order order("Talisker", 50);

  WarehouseMock warehouse;
  {
    REQUIRE_CALL(warehouse, hasInventory("Talisker", 50))
      .RETURN(true);

    REQUIRE_CALL(warehouse, remove("Talisker", 50));

    order.fill(warehouse);
  }

  ASSERT_TRUE(order.is_filled());
}

REQUIRE_CALL on lines 7 and 10 are what they sound like. For each, a matching call is required exactly once. The requirement must be met by the end of the surrounding scope, or a violation is reported.

If several REQUIRE_CALL could match the same call, they are tried in reversed order, until a match is found. This allows you to declare an open default early in your test, and add restricted specializations later when needed.

A weakness in the above, however, is that no sequencing is implied. The two REQUIRE_CALLs are considered logically parallel, i.e. the order of the calls is of no significance to the outcome of the test. To ensure that the test passes only if hasInventory is called before remove, a sequence object is introduced:

TEST(filling_removes_inventory_if_in_stock)
{
  Order order("Talisker", 50);

  WarehouseMock warehouse;
  {
    trompeloeil::sequence seq;
    REQUIRE_CALL(warehouse, hasInventory("Talisker", 50))
      .IN_SEQUENCE(seq)
      .RETURN(true);

    REQUIRE_CALL(warehouse, remove("Talisker", 50))
      .IN_SEQUENCE(seq);

    order.fill(warehouse);
  }

  ASSERT_TRUE(order.is_filled());
}

Now the test will fail if remove is called before hasInventory.

Let's add another test for trying to order more than is available in inventory:

TEST(filling_does_not_remove_if_not_in_stock)
{
  Order order("Talisker", 51);

  WarehouseMock warehouse;
  {
    REQUIRE_CALL(warehouse, hasInventory("Talisker", 51))
      .RETURN(false);

    order.fill(warehouse);
  }

  ASSERT_FALSE(order.is_filled());
}

Expectations and Fixtures

This is straight forward, but there is a problem with repetition between the two tests. Let's refactor the code by breaking out the common code.

using trompeloeil::_;

const auto talisker = "Talisker";

struct TaliskerStore
{
  size_t                stock;
  trompeloeil::sequence seq;
  WarehouseMock         mock;
  std::unique_ptr<trompeloeil::expectation> inventory
    = NAMED_REQUIRE_CALL(mock, hasInventory(talisker, _))
      .IN_SEQUENCE(seq)
      .RETURN(_2 <= stock);
};

TEST(filling_removes_inventory_if_in_stock)
{
  Order order(talisker, 50);
  {
    TaliskerStore warehouse{50};

    REQUIRE_CALL(warehouse.mock, remove(talisker, 50))
      .IN_SEQUENCE(warehouse.seq);

    order.fill(warehouse.mock);
  }
  ASSERT_TRUE(order.is_filled());
}

TEST(filling_does_not_remove_if_not_in_stock)
{
  Order order(talisker, 51);
  {
    TaliskerStore warehouse{50};

    order.fill(warehouse.mock);
  }
  ASSERT_FALSE(order.is_filled());
}

trompeloeil::_ on line 1 is a wildcard used in REQUIRE_CALL when any value is acceptable.

Since REQUIRE_CALL must be met by the end of the surrounding scope, it works poorly in fixtures. NAMED_REQUIRE_CALL creates an expectation object to be held by a std::unique_ptr<trompeloeil::expectation>. This is seen on lines 10-13. The call must be met by the time the object is destroyed.

On line 13, the _2 refers to the second parameter of the function call (the one matched with the wildcard,) so the return value will be true if the amount asked for is available in stock, and false otherwise.

Mocking with side effects

An alternative rewrite is to move more of the test logic into the fixture, making it behave like a reasonable test store, implemented in terms of the mock.

using trompeloeil::_;

const auto talisker = "Talisker";

struct TaliskerStore
{
  using named_expectation = std::unique_ptr<trompeloeil::expectation>;

  size_t                stock;
  trompeloeil::sequence seq;
  WarehouseMock         mock;
  named_expectation talisker_inventory
    = NAMED_REQUIRE_CALL(mock, hasInventory(talisker, _))
      .IN_SEQUENCE(seq)
      .TIMES(AT_LEAST(1))
      .LR_RETURN(_2 <= stock);
  named_expectation remove
    = NAMED_ALLOW_CALL(mock, remove(talisker, _))
      .IN_SEQUENCE(seq)
      .LR_WITH(_2 <= stock)
      .LR_SIDE_EFFECT(stock -= _2);
};

TEST(filling_removes_inventory_if_in_stock)
{
  Order order(talisker, 50);
  {
    TaliskerStore warehouse{50};

    order.fill(warehouse.mock);

    ASSERT_TRUE(warehouse.stock == 0U);
  }
  ASSERT_TRUE(order.is_filled());
}

TEST(filling_does_not_remove_if_not_in_stock)
{
  Order order(talisker, 51);
  {
    TaliskerStore warehouse{50};

    order.fill(warehouse.mock);

    ASSERT_TRUE(warehouse.stock == 50U);
  }
  ASSERT_FALSE(order.is_filled());
}

.TIMES(AT_LEAST(1)) on line 15 alters the default of requiring exactly 1 matching call. You can use .TIMES(2) to require exactly 2 matching calls, .TIMES(2,5) to require 2 through 5 matching calls. Naturally, there is also an AT_MOST(n) that can be used.

The .LR_RETURN(_2 <= stock) on line 16 looks a bit odd. .WITH(), .SIDE_EFFECT(), .RETURN() and .THROW() all refers to copies of local names, whereas the LR_-prefixed versions accesses them by reference. So, a .RETURN(_2 <= stock) would always compare _2 with the value stock had when the expectation object was created, whereas .LR_RETURN(_2 <= stock) compares _2 with the value the member variable stock has at the time of the matching call.

NAMED_ALLOW_CALL() on line 18 is a shorthand for NAMED_REQUIRE_CALL(...).TIMES(0,infinity), i.e. an absence of calls is OK and infinitely many calls are equally OK. There is also a FORBID_CALL() with obvious meaning.

.LR_WITH(_2 <= stock) on line 20, makes the call match only if _2 <= the value of the member variable stock at the time of the call. .WITH() and .LR_WITH() tests are always tried first when a matching signature is found. You can add as many .WITH() and .LR_WITH() as you like for an expectation. They are tried in the order they are added.

.LR_SIDE_EFFECT(stock -= _2) subtracts _2 from the member variable stock. You can add as many .SIDE_EFFECT() and .LR_SIDE_EFFECT() as you like to an expectation. They are executed in the order they are added, provided that the signature and the .WITH() and .LR_WITH() conditions matched.

Sequencing may seem a bit odd when the number of calls required to match is not an exact number. In Trompeloeil a sequence restriction is satisfied when the minimum number of calls is reached. In the example above, this means that it is an error if remove is called before hasInventory, but it is OK to never call remove, since the minimum number of calls is 0, which is trivially satisfied. It is likewise OK to call hasInventory many many times before remove, and then call hasInventory again followed by further calls to remove.

Wrap up

Please give Trompeloeil a try and give feedback (or better yet, join the job and submit improvements.) My experience is that its use of direct expressions/statements in the expectations together with the strict control of deadline for a match through the normal C++ lifetime rules makes it very easy to work with.

Thursday, August 28, 2014

Asserting compilation errors in C++

Sometimes when crafting an interface, we want to ensure that some illegal constructs leads to compilation errors. After all, a good interface is easy to use correctly, and difficult to get wrong, and what can be more difficult to get wrong than something that doesn't compile?

We also know that untested often is buggy, or at least we cannot be sure that it is correct, and tests tests that aren't automated tend to be forgotten. This, of course, means that even if you've carefully crafted an interface where some construction is illegal, and made some manual tests for it, some bug fix later might ruin it and no test will catch that the illegal construct now compiles.

However, namespaces and using directives opens an opportunity. Below is the beginnings of a trap that catches illegal calls to a function named f.

int f(std::string); // function to trap abuse of

struct illegal;
namespace bait {
illegal f(...);
}

using namespace bait;
f(3); // calls bait::f
f(""); // calls ::f

With the aid of the C++11 decltype specifier, we can catch the resulting type of an expression at compile time, in this case getting the return type of a function call, without actually making the call.

decltype(f(3)) obj1; // illegal
decltype(f("")) obj2; // int

Note that bait::f is never implemented. All that is needed is the signature so that the compiler can find match the arguments and get the return type.

With these two, the trap can be triggered at compile time using C++11 static_assert and std::is_same<T,U>

#include <type_traits>
static_assert(std::is_same<decltype(f(3)),illegal>::value,
"compiles when it shouldn't");

The above compiles, since f(3) matches bait::f, and no code is generated. Changing to a match of ::f, however

static_assert(std::is_same<decltype(f("")),illegal>::value,
"compiles when it shouldn't");

gives a compilation error. On clang++ 3.4.2 the message is:

fc.cpp:18:1: error: static_assert failed "compiles when it shouldn't"
static_assert(std::is_same<decltype(f("")), illegal>::value,
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 error generated.

and g++ 4.8.2 gives the message:

fc.cpp:18:1: error: static assertion failed: compiles when it shouldn't
static_assert(std::is_same<decltype(f("")), illegal>::value,
^

The results seem reversed. A call that would cause compilation error compiles, and a call that would compile gives a compilation error.

Now what if f is in a namespace? Things becomes marginally more cluttered, but the technique remains the same. Putting the bait in an inline namespace solves the problem.

namespace ns {
int f(std::string);
}

struct illegal;

namespace ns {
inline namespace bait {
illegal f(...);
}
}

An inline namespace is a namespace, but a everything declared in it is visible in its surrounding namespace, similar to the using namespace directive used earlier.

ns::f(3); // calls ns::bait::f
ns::f(""); // calls ns::f

The test thus becomes:

static_assert(std::is_same<decltype(ns::f(3)),illegal>::value,
"compiles when it shouldn't");

A macro can help with code readability:

#define ASSERT_COMPILATION_ERROR(...) \
static_assert(std::is_same<decltype(__VA_ARGS__), \
illegal::type>::value, \
#__VA_ARGS__ " compiles when it shouldn't")

Writing the test code as:

ASSERT_COMPILATION_ERROR(ns::f(""));

gives the (g++ 4.8.2) compilation error:

fc.cpp:20:3: error: static assertion failed: ns::f("")compiles when it shouldn't
static_assert(std::is_same<decltype(__VA_ARGS__), illegal>::value, \
^
fc.cpp:23:1: note: in expansion of macro ‘ASSERT_COMPILATION_ERROR’
ASSERT_COMPILATION_ERROR(ns::f(""));
^

I think this is pretty neat. It is now simple to test that illegal calls actually don't compile. You can add these tests to the unit test program that asserts the intended functionality.

Sunday, March 31, 2013

strings as types

As odd as it may seem, I have more than once felt the need to express a string literal as a unique type which can be used as a any class.

As an example, I would like to inherit from a string literal:

class C : public "literal"
{
...
};

C++11 sort of provides the means with the introduction of variadic templates. Here's an introduction with a simple t_string (for type string,) with easy access to the size and a c-string representation:

template <char ...t>
struct t_string
{
static const size = sizeof...(t);
static const char c_str[size + 1];
};
template <char ...t>
const char t_string<t...>::c_str[t_string<t...>::size+1]={t...,0};

This can be used in a sample program like follows:

int main()
{
typedef t_string<'p', 'i', 'g'> P;
std::cout << "P::c_str[" << P::size+1 << "]=" << P::c_str << '\n';
}

When run, the output is

> ./test1
P::c_str[4]=pig

While the above works, it is, at best, very cumbersome and not really a practical solution.

constexpr and the preprocessor to the rescue!

I had pretty much given up on this and resolved to make do without strings as types, but then this blog post by Abel Sinkovics and Dave Abrahams pointed me in the right direction.

In C++11, a constexpr function is a function that not only can be evaluated at compile time, but which return value can be used in constant expressions, for example as template parameters. For this problem, a useful function indexes a char array:

template <size_t N>
constexpr char at(size_t n, const char (&array)[N])
{
static_assert(n < N, "index is out of bounds for the array");
return array[n];
}

The array parameter can refer to any string literal. With this, the above example program can be written as:

int main()
{
typedef t_string<at(0, "pig"), at(1, "pig"), at(2, pig)> P;
std::cout << "P::c_str[" << P::size+1 << "]=" << P::c_str << '\n';
}

This may not seem like an obvious improvement, but with a little help from our old friend, the preprocessor, things can improve a lot.

#define A_LIST_1(M, ...) M(0, __VA_ARGS__)
#define A_LIST_2(M, ...) A_LIST_1(M, __VA_ARGS__), M(1, __VA_ARGS__)
#define A_LIST_3(M, ...) A_LIST_2(M, __VA_ARGS__), M(2, __VA_ARGS__)

#define INDEX(x, array) at(x, array)

int main()
{
typedef t_string<A_LIST_3(INDEX, "pig")> P;
std::cout << "P::c_str[" << P::size + 1 << "]=" << P::c_str << '\n';
}

This expands to the same as the above program, which in turn expands to the same as the first sample program, making P an alias for t_string<'p', 'i', 'g'>.

The problem with the above is having to use A_LIST_3() when the string literal is 3 characters long. This is error prone.

Generalizing on length

One thing that can be done to get around this is to use a sufficiently long list (for some measure of sufficient), and change the constexpr function at() to return 0 for out of bounds indexes.

template <size_t N>
constexpr char at(size_t n, const char (&array)[N])
{
return n < N ? array[n] : 0;
}

Extending the A_LIST_X series to a reasonable value of "sufficient", we can now safely ignore the string length problem:

int main()
{
typedef t_string<A_LIST_500(INDEX, "pig")> P;
std::cout << "P::c_str[" << P::size + 1 << "]=" << P::c_str << '\n';
}

Well, there's this problem with size... Running this program shows:

> ./test4
P::c_str[501]=pig

Getting rid of those zeroes

Instead of adding characters to the type as a comma separated list, we can extend the t_string template with an append function-like type template, that ignores '\0'.

template <typename T>
struct append_t;

template <char ...t>
struct t_string
{
template <char c>
struct append
{
typedef typename append_t<c, t_string>::type type;
};
static const size = sizeof...(t);
static const char c_str[size + 1];
};

template <char ...t>
const char t_string<t...>::c_str[t_string<t...>::size+1]={t...,0};

template <char c, char ...t>
struct append_t<c, t_string<t...>>
{
typedef t_string<t..., c> type;
};

template <char ...t>
struct append_t<'\0', t_string<t...>>
{
typedef t_string<t...> type;
};

This changes the syntax a bit, but a small modification of the first example program shows the way:

int main()
{
typedef t_string<>
::append<'p'>::type
::append<'i'>::type
::append<'g'>::type
::append<'0'>::type
::append<'0'>::type P;
std::cout << "P::c_str[" << P::size+1 << "]=" << P::c_str << '\n';
}

The output from this program is:

> ./test5
P::c_str[4]=pig

Obviously the trailing zeroes were ignored.

The remaining thing now is to change the sequencing macros. The comma separating A_LIST_X macros should be replaced by something that just concatenates the expansions.

#define REPEAT_1(M, ...) M(0, __VA_ARGS__)
#define REPEAT_2(M, ...) REPEAT_1(M, __VA_ARGS__) M(1, __VA_ARGS__)
#define REPEAT_3(M, ...) REPEAT_2(M, __VA_ARGS__) M(2, __VA_ARGS__)
...
#define REPEAT_500(M, ...) REPEAT_499(M, __VA_ARGS__) M(499, __VA_ARGS__)
#define APPEND_INDEX(x, array) ::append<at(x, array)>::type

int main()
{
typedef t_string<> REPEAT_500(APPEND_INDEX, "pig") P;
std::cout << "P::c_str[" << P::size + 1 << "]=" << P::c_str << '\n';
}

The output from running this program is:

> ./test6
P::c_str[4]=pig

Alright, just wrap it up in a fancy macro:

#define T_STRING(x) t_string<> REPEAT_500(APPEND_INDEX, x)

class C : public T_STRING("piglet")
{
public:
friend std::ostream& operator<<(std::ostream& os, const C&)
{
return os << C::c_str;
}
};

int main()
{
C c;
std::cout << c << "\n";
}

Conclusion

Once the idea hit home, it turns out that using strings as types isn't very difficult at all. What about the cost, though?

There's performance and there's performance. Runtime performance of this construction is as good as it can ever get. Not a single instruction is generated for the t_string templates. The only result of them is a read-only char array generated at compile time, and those arrays are only generated for the t_string template instantiations where the c_str member is used.

Compile time carries a cost, however. A very long preprocessor repetition (like the 500 used above) takes some time on its own, and the template machinery will have some work to do. I don't have concrete measurements and in my experiments the time has not been an issue, but it does take more time to compile than a simple

static const char animal[] = "pig";

I, for one, can live with the small compile time cost, and believe it or not, I actually have a use for this - a problem that would be very difficult, or at least very time consuming, to solve in other ways.

Wednesday, September 28, 2011

Compile time messages in C++

At times it's desirable to give a message at compile time. Sounds cheezy, eh? Well read on and find out.

As an example of the cheezy kind, the compile-time quick sort shown here earlier contained an unnecessary run time element with a main()function, for_each() and a print template. It is possible to display all information at compile time by causing a compiler error, like this:

template <typename T>
struct print;

Use it by, for example, by referring to a member type.

Let's revisit the list and concat templates.

template <typename T, T... elems>
struct list;

template <typename ...T>
struct concat;

template <typename T, T... lh, T... rh, typename ...U>
struct concat<list<T, lh...>, list<T, rh...>, U...>
{
typedef typename concat<U..., list<T, lh..., rh...> >::type type;
};

template <typename T, T... elems>
struct concat<list<T, elems...> >
{
typedef list<T, elems...> type;
};

Now a simple test of how it works

typedef print<concat<list<int, 1, 2>, list<int, 3, 4> >::type>::type message;

The output from the compiler is:

c.cpp:72:9: error: 'type' in class 'print<list<int, 1, 2, 3, 4> >' does not name a type

Not perfect, but but it does show the resulting type list<int, 1, 2, 3, 4>.

Well, there is a caveat. The standard mandates very little indeed regarding error messages. The typical phrase used is "... a diagnostic is required". Nothing at all is said about the information in that diagnostic, and a compiler simply saying "?" can be fully standards compliant. Fortunately compiler writers likes happy users, and so usually try to help them with informative messages, so this usually works fine, just no guarantees.

Note that the technique is perfectly usable in C++ as defined by the 1998 standard. The only reason I used the C++ 2011 feature, variadic templates here, is to save space.

As shown so far, this is just silly, but this can actually come in handy. How about some unit tests for the concat template?

First a helper template:

template <typename T, typename U>
struct assert_same_type;

template <typename T>
struct assert_same_type<T, T>
{
typedef T type;
};

The idea is that if the two parameter types are the same, the member type can be used in, for example a typedef, otherwise the compiler will emit an error message.

Now let's put concat through its pace:

typedef assert_same_type<concat<list<int> >::type,
list<int> >::type
concat_empty_list;

typedef assert_same_type<concat<list<int, 1, 2> >::type,
list<int, 1, 2> >::type
concat_one_list;

typedef assert_same_type<concat<list<int, 1, 2>,
list<int, 3, 4> >::type,
list<int, 1, 2, 3, 4> >::type
concat_two_lists;

typedef assert_same_type<concat<list<int, 1>,
list<int, 2>,
list<int, 3> >::type,
list<int, 1, 2, 3> >::type
concat_three_lists;

The result of compilation is:

c.cpp:79:9: error: 'type' in class 'assert_same_type<list<int, 3, 1, 2>, list<int, 1, 2, 3> >' does not name a type

Whoaa! A bug! It seems that when three elements are concatenated, the order is changed. Hmm. Ah, look at concat above. The error is rather obvious. Glad that one was caught before any library user came complaining.

Fixing the concat template to:

template <typename T, T... lh, T... rh, typename ...U>
struct concat<list<T, lh...>, list<T, rh...>, U...>
{
typedef typename concat<list<T, lh..., rh...>, U... >::type
type;
};

Should take care of it. Another attempt at compiling gives silence. It works.

So, as can be seen, the technique can be rather useful. The error message given was, in this case, rather informative and quickly pointed us in the right direction to fix the bug.

What about giving library users a little help, though? concat can only be used with list type parameters. Anything else is an error. What does the compiler emit when concat is used with mismatching types? Let's put it to the test:

typedef concat<list<int>, std::vector<std::string> >::type listvec;

The error message is:

c.cpp:69:9: error: 'type' in class 'concat<list<int>, std::vector<std::basic_string<char> > >' does not name a type

Not very helpful. The user will have to look at the sources for concat to understand what it means.

If you're lucky enough to write your programs with a compiler that supports static_assert(), officially introduced in ISO C++ 2011, but supported by many compilers for some time (gcc introduced it in version 4.3 released in March 2008,) it's simple. static_assert() requires a compile-time known boolean value and a string. The string is the error message if the boolean is false.

So, with a simple helper, concat can provide a lot better information to the user.

template <typename ...Tail>
struct all_elements_are_lists
{
static const bool value = false;
};

template <typename T, T... elems, typename ... Tail>
struct all_elements_are_lists<list<T, elems...>,
Tail...>
{
static const bool value = all_elements_are_lists<Tail...>::value;
};

template <typename T, T... elems>
struct all_elements_are_lists<list<T, elems...> >
{
static const bool value = true;
};

template <typename ...T>
struct concat
{
static_assert(all_elements_are_lists<T...>::value,
"All parameters to concat must be lists.");
};

Let's try the faulty concat invocation again. Now the error message is:

c.cpp: In instantiation of 'concat<list<int>, std::vector<std::basic_string<char> > >':
c.cpp:79:53: instantiated from here
c.cpp:38:3: error: static assertion failed: "All parameters to concat must be lists."
c.cpp:79:9: error: 'type' in class 'concat<list<int>, std::vector<std::basic_string<char> > >' does not name a type

It would be a lie to say that it's perfect, but the information is a lot clearer and the user does not have to read the sources for concat, so it's an improvement.

So what to do if your compiler does not support static_assert()? All is not lost. Use the technique described in the beginning of the post to create a type, or a template, with a descriptive name that causes an error. The descriptive name will hopefully be shown in the error message. You may have to play around a bit to find a solution, but it's doable, although the message will never be as clear as with static_assert().

Compile time messages turned out to be pretty useful, I think.

Sunday, September 25, 2011

Exploring time keeping in ISO C++ 2011

A lot has been written about new features coming in the 2011 revision of ISO C++. One that has received surprisingly little attention is the <chrono> header. The types and functions therein makes it so much simpler to write time keeping software. Its neat simple interface is, however, also problematic.

Here's a small example program that shows both neatness and problems:

#include <chrono>#include <thread> // std::this_thread::sleep_until()#include <iostream>#include <ostream>

template <typename T, long N, long D>std::ostream &operator<<(std::ostream &os, std::chrono::duration<T, std::ratio<N, D> >&d){ os << d.count() << '*' << N << '/' << D << " seconds"; return os;}

int main(){ const std::chrono::seconds desired_duration(1); auto before = std::chrono::system_clock::now(); auto deadline = before + desired_duration; std::this_thread::sleep_until(deadline); auto after = std::chrono::system_clock::now(); auto delay = after - deadline; std::cout << delay << std::endl;}

A sample run says:

65*1/1000000 seconds

The header <chrono> contains the templates time_point<> and duration<> in addition to a smorgasboard of clocks, all in the namespace std::chrono. In the example above, the variables before, deadline and after are all instantiations of the time_point<> template, and the variables desired_duration and delay are instantiations of the duration<> template.

You can subtract time_points to get a duration. You can add or subtract a duration and a time_point and get another time_point. You can multiply or divide durations with a scalar, and you can even divide durations and get their relative length as a scalar quotient.

One of the template parameters of time_point<> is the clock it came from, so you can't by mistake subtract two time_points from different clocks.

As shown in the example above, the durations are templatized on the type used to represent values, and a ratio describing its base in seconds. The example above shows microseconds.

There are predefined convenience duration typedefs in namescape std::chrono: nanoseconds, microseconds, milliseconds, seconds, minutes and hours.

Every clock has a typedef period, which is the ratio of the resolution of the clock. A small example program, using the above templated operator<< for durations displays the resolution of the system clock:

int main()
{
using namespace std::chrono;
duration<int, system_clock::period> resolution(1);
std::cout << resolution << '\n';
}

The output is:

1*1/1000000 seconds

This computer's system clock uses microseconds to represent time.

Herein lies one of the problems with <chrono>. The resolution of clocks must be known at compile time. This means that the makers of a standard library must strike a balance between giving the impression of a finer granularity clock than is actually available, and making the types too coarse. The computer used to run this example program has a clock with nanosecond granularity, but the library does not acknowledge its existence. I am of course free to implement my own clock type for it, and it's not much work, but it feels unnecessary.

Converting between durations with different resolutions is simple and safe. As long as the conversion can be done without losing precision, it can be done implicitly. When the conversion causes loss of precision, std::chrono::duration_cast<> is available.

The standard names three clocks. system_clock, steady_clock and high_precision_clock. The clock steady_clock, was at times during the standardization process called monotonic_clock, and a number of C++ compilers ship with libraries using that name. The steady clock is a clock that is not ever allowed to see time point adjustments, only rate adjustments. It is thus very handy for server software that does carries out jobs at certain intervals, or for profiling.

Unfortunately the standard allows the three to be typedef:ed to each other. In my library they are all typedefs for the same clock. The implication of this is that my compiler right now allows the calculation std::chrono::high_precision_clock::now() - std::chrono::system_clock::now(), since the time points returned both refer to the same type. The exact same code may not compile on another conforming compiler, if its library uses distinct types for those two clocks. I think that is unnecessary.

Yet a problem is that the clock static member function now() must be declared noexcept to be standards conforming, i.e. calling it must not cause any exception to be thrown. There is thus no possible way to check at run time if a clock is available or not. If the library supports it, it must be there and it must work. I think this is bad.

For those of you who had hoped to see a date class, to do calendar work with, sorry - it isn't there.

Friday, September 23, 2011

Compile time quick sort using C++ variadic templates

[ Edit June 4 2015: This article is very dated. Read this revisiting article for a far better solution ]

C++ is a strange language. In many ways it's a crap language, but it's a very fun crap language to use. It's also a very powerful one, especially the templates. Now that ISO C++ 2011 has brought variadic templates, it becomes easier to use and requires less typing.

I decided to explore variadic templattes, and I thought one way of exploring it was to express a compile-time quick-sort. Note that I didn't set out to explore if it can be done - that I was certain of. I set out to explore if I can do it, and I very specifically decided not to check what others had done as I had no illusions of being the first.

The first problem to solve was that of expressing a list of numbers.

template <typename T, T... elems>
struct list;

That's all that is required. The second template parameter is a list of zero or more elements of type T. That's what "..." denotes.

It's use is simple:

typedef list<int, 3, 8, 69, 2> integers;
typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;

That the template is only declared, not defined, is not a mistake. It's not a problem that the types are incomplete and can't be instantiated. Instantiated objects are a run time thing, and this is about compile time computation.

It is, however, a good idea to be able to show what a list of numbers looks like, so a function to print the list is handy. More handy is a mechanism to call a function for every value in the list, in order.

Specializing function templates is still a no-go, but the classic forwarding to a helper class works.

template <typename T>
struct foreach_t;

This just introduces the helper class template. All work is done in the specializations.

template <typename T, T head, T... tail>
struct foreach_t<list<T, head, tail...> >
{
template <typename F>
static void apply(F f)
{
f(head);
foreach_t<list<T, tail...> >::apply(f);
}
};

template <typename T>
struct foreach_t<list<T> >
{
template <typename F>
static void apply(F)
{
}
};

The first specialization calls the function provided in the apply member function to the first element of the list, and then recurses to do the same with the tail of the list. The second specialization ends the recursion by handling an empty list.

Ah the memories. This time of the year, in 1989, I was in university and took my first academic programming course - "Functional Programming with Standard ML." I thought I had a good idea about programming, but boy was I wrong. Who would've known that I'd find that course useful for C++ 22 years later? The programming technique is the same. The syntax is far worse in C++, though.

As a convenience, a function template is added

template <typename T, typename F>
void foreach(F f = F())
{
foreach_t<T>::apply(f);
}

The thing with the default parameter is just so that the function can either be called with an object, or using a type that is instantiated. It's just convenient. A small test program shows why.

#include <iostream>
#include <ostream>
#include <cstdio>

struct print
{
template <typename T>
void operator()(T t)
{
std::cout << t << ' ';
}
};

int main()
{
typedef list<int, 3, 8, 69, 2> integers;
typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;
foreach<integers, print>();
std::cout << '\n';
foreach<word>(std::putchar);
}

The output when run is

3 8 69 2
chars

Not very exciting, I admit, but it shows that the list works and that traversing it works. In all test programs to follow, the print struct is presumed available.

In order to implement a quick sort on the lists, two things must be possible to do with them, partitioning and concatenating them.

First the concatenation, since it's the easier operation.

template <typename ...T>
struct concat;

As before, the generic concat template just introduces the name for the specializations.

template <typename T, T... p1, T... p2, typename ...Tail>
struct concat<list<T, p1...>, list<T, p2...>, Tail... >
{
typedef list<T, p1..., p2...> first_two;
typedef typename concat<first_two, Tail...>::type type;
};

template <typename T, T... elems>
struct concat<list<T, elems...> >
{
typedef list<T, elems...> type;
};

Local typedef:s galore in template meta programming, otherwise the lines becomes way too long to see properly.

The recursion is the same pattern, but here it is all about creating new types.

Another simple program shows the use

int main()
{
typedef list<int, 2, 4, 8> first;
typedef list<int, 3, 5, 7> second;
foreach<concat<first, second>::type, print>();
std::cout << '\n';
}

The output is

2 4 8 3 5 7

It seems to work. Good.

Partitioning a list is possible to do with one template, but the code becomes messy to read. This is about learning a technique, not about managing messy code, so I decided to go for filtering instead. Less efficient, but much easier to read and understand.

The filter template solution takes a predicate and a list. The predicate picks the elements to keep. Doing this first requires a simple helper, the if_else template. I was pretty certain that this one made it to the standard library, but perhaps I was wrong. At least I can't find it.

template <bool b, typename T, typename F>
struct if_else
{
typedef T type;
};

template <typename T, typename F>
struct if_else<false, T, F>
{
typedef F type;
};

It's not very complicated. The template accepts a boolean value and two types. The typedef is the first type when the boolean value is true, and the second type otherwise.

With this, the filter template is reasonably straight forward as it follows a by now familiar pattern.

template <template <typename U, U> class Pred,
typename Data>
struct filter;

template <template <typename U, U> class Pred,
typename T, T head, T... tail>
struct filter<Pred, list<T, head, tail...> >
{
typedef list<T, tail...> tlist;
typedef typename filter<Pred, tlist>::type ftail;
typedef list<T, head> h;
typedef typename if_else<Pred<T, head>::value,
typename concat<h, ftail>::type,
ftail>::type type;
};

template <template <typename U, U> class Pred, typename T>
struct filter<Pred, list<T> >
{
typedef list<T> type;
};

The predicate is a template that provides a boolean value given a type and an input value. The filter template recurses over the elements of the list, and uses if_else to select either only the tail, or the selected value concatenated with the tail.

A simple program demonstrates.

template <typename T, T t>
struct is_odd
{
static const bool value = t & T(1);
};

int main()
{
typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
foreach<filter<is_odd, data>::type, print>();
std::cout << '\n';
}

The output is

9 1 23 11 23 3

It seems like the filtering works.

Quick sort is now only about picking a pivot element, and filtering the elements from the list that are smaller and those that aren't into separate lists, quick sort the lists and concatenate the results.

To be generic, though, the sort order should be defined by a comparison template. A reasonable comparison template is

template <typename T, T l, T r>
struct lt
{
static const bool value = l < r;
};

Using a selected pivot value, this comparison template must be transformed into a predicate that the filter template can use. Inspired by the std::bind functions from the standard library, here is a bind template that provides the needed transformation.

template <template <typename U, U, U> class C,
typename T, T t>
struct bind
{
template <typename V, V v>
struct pred
{
static const bool value = C<T, v, t>::value;
};
};

The template parameter C is the comparison template, and the member template pred is the resulting predicate.

It can be used like this

int main()
{
typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
typedef filter<bind<lt, int, 10>::pred, data>::type lt10;
foreach<lt10, print>();
std::cout << '\n';
}

The output is

8 9 2 1 0 3

Presumably it works.

Now, for the quick sort, both the set selected by the predicate, and its complement, must be available. A simple way to get the complement is to negate the predicate. Enter another helper template.

template <template <typename U, U> class Pred>
struct neg
{
template <typename T, T v>
struct pred
{
static const bool value = !Pred<T, v>::value;
};
};

The template parameter Pred is the predicate to negate, and the member template pred, is the negated predicate to use.

A simple variation of the previous example program is

int main()
{
typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
typedef filter<neg<bind<lt, int, 10>::pred>::pred,
data>::type ge10;
foreach<ge10, print>();
std::cout << '\n';
}

Unsurprisingly the output is

23 11 23 512

Now, finally, all the bits and pieces are there. It's just a matter of assembling them to a quick sort template

template <template <typename T, T, T> class Comp,
typename Data>
struct q_sort;

template <template <typename U, U, U> class Comp,
typename T, T head, T... tail>
struct q_sort<Comp, list<T, head, tail...> >
{
template <typename V, V v>
struct pred : bind<Comp, V, v>::template pred<T, head> {};
template <typename V, V v>
struct npred : neg<pred>::template pred<V, v> {};
typedef typename filter<npred, list<T, tail...> >::type fl;
typedef typename filter< pred, list<T, tail...> >::type tl;
typedef typename q_sort<Comp, fl>::type sfl;
typedef typename q_sort<Comp, tl>::type stl;
typedef list<T, head> hl;
typedef typename concat<sfl, hl, stl>::type type;
};

template <template <typename U, U, U> class Pred,
typename T>
struct q_sort<Pred, list<T> >
{
typedef list<T> type;
};

The middle template that does all the work is a bit overwhelming, but it's not as bad as it looks.

The head element is chosen as the pivot element.

First a predicate is made out of the Comp comparison template parameter, using the bind helper template introduced earlier and the pivot element.

Next a negated predicate npred is made with the help of the neg helper template.

Using these two predicates, two new lists are made, fl for false, i.e. when the negated predicate picked the elements, and tl for true, i.e. when the predicate picked the elements.

Then the two lists are sorted recursively, by creating two new types sfl and stl (for sorted versions of fl and tl.)

The only thing that remains is to concatenate the lists and the pivot element into a resulting type.

The use is simple:

int main()
{
typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
foreach<q_sort<lt, data>::type, print>();
std::cout << '\n';
}

The result (drumroll)

0 1 2 3 8 9 11 23 23 512

Quick sort in compile time using C++ variadic templates. Now how useless is that?

Hope you enjoyed the show!