Implementation Challenge: Traits for Concepts with optional functionality

15 Dec 2015 by Jonathan

Traits classes are very powerful. They allow to associate information and functionality with arbitrary classes in a non-intrusive way. This makes it possible to use any type in a certain template as long as all access is done through the traits and there is an appropriate specialization.

The default specialization often just forwards to a member function. But for some functionality the types don’t necessarily need to provide it, it’s optional. Then the traits define a default implementation that is used as a fallback. In this post, I will show you how to implement such traits classes.

This post was originally intended as a kind of conclusion of the “Controlling overload resolution” series, combining everything I’ve shown you there into one. But I have made it a separate post. If you don’t know any of the techniques I’m going to use here, I highly recommended checking it out.

{% assign series-menu-name = “Controlling overload resolution: " %} {% assign series-menu-series = “controlling-overload-resolution” %} {% include post_series_menu.html %}

Motivation

A C++11 Allocator does only need to provide the following functions:

#include <cstddef>
template <class Tp>
struct SimpleAllocator {
  typedef Tp value_type;
  SimpleAllocator(/*ctor args*/);
  template <class T> SimpleAllocator(const SimpleAllocator<T>& other);
  Tp* allocate(std::size_t n);
  void deallocate(Tp* p, std::size_t n);
};
template <class T, class U>
bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&);
template <class T, class U>
bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&);

(Copy&Pasted from cppreference)

Yes, I do a lot of stuff with Allocators. Don’t judge me.

But optionally Allocators can do a lot more, for example, they can control the pointer type or the construction of objects. If you look at the table at cppreference, many members are marked “optional”. How is this achieved?

The answer is the traits class std::allocator_traits.

See, perfect example.

Not only does it provide the ability to specialize it for arbitrary user-defined types with a different interface, it also provides defaulted fallbacks. For example, if a class does not provide the member typedef pointer, it will provide a default of T*. How this is done is the topic of this blog post.

The Challenge

But std::allocator_traits is boring and implementing it is way to easy!

It is also covered by a talk from Alisdair Meredith on CppCon 2014. Part 1 and Part 2 are online, I highly recommend checking them out.

Also, all implementations __are _M_ugly.

Instead, let’s look at memory::allocator_traits from foonathan/memory.

I told you I use allocators for everything.

In the library, there is a new allocator concept, a RawAllocator. The traits class also needs to accept Allocator classes, so they work as RawAllocators as well, in addtion to the “normal” traits stuff. So it needs to perform a little bit more work than the std:: version. So much work in fact, that we just look at the following members:

max_node_size(): calls member max_node_size() or fallbacks to maximum integer value
max_array_size(): calls member max_array_size() or fallbacks to traits::max_node_size()
allocate_node(): calls member allocate_node() or fallbacks to a member function allocate(), else error
is_stateful: forwards to member typedef is_stateful or fallbacks to using std::is_empty

If you are interested in the full set of members and exact semantics, read the docs here. Feel free to implement it yourself based on these information.

The Setup

The default specialization of allocator_traits must provide different implementations depending on the exact properties of the type it is instantiated with. As we’ve learned in the post about tag dispatching, the different implementations should be extracted into different function with a parent function just inserting a tag and forwarding.

This can look as follows:

namespace traits_detail
{
  ...
}

template <class RawAllocator>
class allocator_traits
{
 public:  
  static std::size_t max_node_size(const allocator_type &state)
  {
      return traits_detail::max_node_size(/* tag object */, state);
  }

  static std::size_t max_array_size(const allocator_type &state)
  {
      return traits_detail::max_array_size(/* tag object */, state);
  }
  
  static void* allocate_node(allocator_type& state,
                                std::size_t size, std::size_t alignment)
  {
      return traits_detail::allocate_node(/* tag object */,
                                          state, size, alignment);
  }
  
  using is_stateful = ...;
};

The implementation functions are in a detail namespace traits_detail as they are a pure implementation detail. Now we need a proper tag type to select it.

One way of doing it would be to write mini-traits that check whether or not a type has the required member function. But this is tidious, so I’ve decided against it.

Instead, one can notice a hierachy in the implementations, first it tries to call the member function, then it fallbacks to something. And as I’ve shown you, this can also be modelled by a hierachy of tags:

struct error {}; // for types without the member function
struct std_concept : error {}; // for types that provide the standard Allocator functions (allocate() instead of allocate_node())
struct min_concept : std_concept {}; // for types that provide only the minimal RawAllocator concept functions
struct full_concept : min_concept {}; // for types that provide the full set of functions

The parent function inside the traits will pass an object of type traits_detail::full_concept to the implementation, overload resolution will select the first fitting implementation in the hierchy.

Implementing `max_node_size()`

max_node_size() is the simplest of the functions. If it has a member function max_node_size(), call it, else return the maximum value of type std::size_t.

This translates like so:

template <class Allocator>
std::size_t max_node_size(full_concept, const Allocator &alloc)
{
  return alloc.max_node_size(); 
}

template <class Allocator>
std::size_t max_node_size(min_concept, const Allocator &) noexcept
{
  return std::size_t(-1);
}

I have used unsigned underflow to get to the maximum value. This is well-defined by the C++ standard.

But the above code will always select the first overload, since it does not require the derived-to-base conversion! For types without the proper member function, this will then fail to compile. We thus need a way to disable the first overload for types without the member function.

And if you’ve read my the part four of my “Controlling overload resolution” series, this will ring a bell: We can use SFINAE, namely, expression SFINAE, to disable the first overload like so:

template <class Allocator>
auto max_node_size(full_concept, const Allocator &alloc)
-> decltype(alloc.max_node_size())
{
  return alloc.max_node_size(); 
}

template <class Allocator>
std::size_t max_node_size(min_concept, const Allocator &) noexcept
{
  return std::size_t(-1);
}

I have used the C++11 trailing return type syntax to be able to access the parameter name inside the decltype() there. Also, the code duplication could be avoided by using a macro, but for simplicity, I’ve avoided it here.

By putting the decltype() at the end, the existence of the member function will become part of the signature and thus template argument deduction will fail for types without it. Then it selects the other candidate and only then, since it is a worse match due to the derived-to-base conversion.

Perfect.

Implementing `max_array_size()`

max_array_size() is very similar to max_node_size(). The fallback only requires to return max_node_size(), but we need to make sure to use the version with fallback itself, to not rely on the existence of a member function.

This translates as follows:

template <class Allocator>
auto max_array_size(full_concept, const Allocator &alloc)
-> decltype(alloc.max_array_size())
{
  return alloc.max_array_size();
}

template <class Allocator>
std::size_t max_array_size(min_concept, const Allocator &alloc)
{
  return max_node_size(full_concept{}, alloc);
}

Note that it calls the implementation function directly, making sure to pass the top-level tag type again. But you’ve probably figured that out already.

By now I am probably boring you, so fasten your seatbelt and enter allocate_node()!

Implementing `allocate_node()`

allocate_node() first tries to call allocate_node(), then fallbacks to allocate():

template <class Allocator>
auto allocate_node(full_concept, Allocator &alloc,
                    std::size_t size, std::size_t alignment)
-> delctype(alloc.allocate_node(size, alignment))
{
  return alloc.allocate_node(size, alignment); 
}

template <class Allocator>
auto allocate_node(std_concept, Allocator &alloc,
                    std::size_t size, std::size_t)
-> decltype(static_cast<void*>(alloc.allocate(size)))
{
  return static_cast<void*>(alloc.allocate(size));
}

The fallback calls allocate() of a standard Allocator. The real implementation ensures that it is rebound to char to allocate the exact number of bytes.

But, you ask, what if the type does not provide the allocate() member function either?

Then overload resolution fails. Which makes sense, because the type is required to provide either function, otherwise it must not be used. But overload resolution errors are not the prettiest and terse kind of error messages.

In this case, it will show a failed overload resolution inside a detail namespace with a ton of instantiation cases that go through the entire memory library, nested through tons of types.

Instead of flooding the user of my libraries in tons of error messages when they have written alloctae_node() instead of allocate_node(), wouldn’t it be nice if there was a short and to the point error message giving the exact information?

As I’ve shown in part 2 of the series, this is indeed possible: First, we need a fallback overload that triggers a static_assert() upon instantiation. This is achieved by providing a false value that is dependent on the template parameter. The most elegant way is a templated struct with a member constant.

Putting it together gives:

template <typename T>
struct invalid_allocator_concept
{
  static const bool error = false;
};

// new overload
template <class Allocator>
void* allocate_node(error, Allocator &,
                    std::size_t, std::size_t)
{
  static_assert(invalid_allocator_concept<Allocator>::error,
                "type does not provide: void* allocate_node(std::size_t, std::size_t)");
  return nullptr; // to silence warning
}

How this works exactly is covered in the post.

Now the user still gets an error message, most likely nested deep inside the library, but it provides a useful and informative error message right at the beginning, allowing the user to facepalm and correct his typo.

Implementing `is_stateful`

The only thing left is the typedef is_stateful. But before you begin writing template specializations with appropriate member typedefs, let me stop you right there.

You can also use overload resolution for this. The return type can be changed on the different implementations and be stored in the typedef via decltype(). Overload resolution can be much easier controlled than template specializations, so I highly recommend it.

In the traits we have the following:

using is_stateful = decltype(traits_detail::is_stateful<Allocator>(traits_detail::full_concept{});

The allocator type must be given to the function otherwise its type cannot be deduced.

The implementation can be done like so:

template <class Allocator>
auto is_stateful(full_concept)
-> decltype(typename Allocator::is_stateful{});

It creates an object of the member typedef and uses its type as return type. There is no implementation required, since the function will never called.

The fallback is slightly more complicated, since an allocator is stateful, if it is not empty, so the result has to be reversed:

template <class Allocator>
auto is_stateful(min_concept)
-> std::integral_constant<bool, !std::is_empty<Allocator>::value>

But this is much simpler than the resulting class template specialization and easily extensible.

Conclusion

In this post, we have created a traits class that provides fallbacks instead of simply forwarding to certain member functions. This allows a minimal required concept with optional functions that can be used to override default behavior.

Note that this is only true for the default specializations. If you specialize it yourself, you need to implement this behavior again.

The implementation can be done by using different implementation functions taking a certain tag type from a hierachy with SFINAE disabling certain overloads if they do not have the required member function. Typedefs can be implemented in the same way, just use decltype() on the different return type.

If you are interested in the full implementation memory::allocator_traits, you can find it on github here.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.

Motivation

The Challenge

The Setup

Implementing max_node_size()

Implementing max_array_size()

Implementing allocate_node()

Implementing is_stateful

Conclusion

Implementing `max_node_size()`

Implementing `max_array_size()`

Implementing `allocate_node()`

Implementing `is_stateful`