25 Oct, 2013

True Story: Call Me Maybe

The call_me_maybe function takes a target as its only argument. If the target object can be called with some specific arguments, it will call it. But not immediately —it doesn't want to look desperate—; instead, it will store it somewhere until the time is right. What follows is how such a crazy function is implemented...

The Problem

We are targeting objects that can be called with a deferred_call_tag as first argument and a std::string as second argument. A deferred_call_tag is just an empty struct devised for target types to explicitly state their intent to be treated specially —this is no novel concept, see for instance std::nothrow_t—. When those special objects are seen, they will be stored in a container and eventually invoked at a later time.

It should be immediately obvious that some form of overloading will be needed, given that the behavior of the function needs to be specialized based on whether or not the target object can be called with our arguments. This in turn exposes the main requirement, that of being able to determine if an object is callable with certain arguments. The rest is boilerplate, and looks more or less like this:

std::vector<std::function<void(std::string)>> callables;

// a tag for callables of our interest to identify themselves
struct deferred_call_tag {};

// if target is callable with specified arguments
template <typename Target>
auto call_me_maybe(Target&& target)
 -> typename std::enable_if<
      is_callable<Target(deferred_call_tag, std::string)>::value
    >::type
{
  callables.push_back(
    std::bind(target, deferred_call_tag{}, std::placeholders::_1)
  );
}
// otherwise do nothing
template <typename Target>
auto call_me_maybe(Target&& target)
 -> typename std::enable_if<
      !is_callable<Target(deferred_call_tag, std::string)>::value
    >::type
{}

void call_them_now()
{
  for (auto& callable : callables)
    callable("Hello!");
  callables.clear();
}

Note that since we are using std::bind, the actual call signature would be Target cv&(deferred_call_tag cv&, std::string) where cv is the const-volatile qualification of the bound object used to invoke the target. This is a controlled and simplified scenario —albeit with a complex real implementation that looks for partial matches and errors out instead of discarding them as not callable—, generic code has to make sure to use the correct cv-ref qualifications on the call expression given to is_callable.

All that remains is implementing is_callable with the intended semantics. But first, some definitions...

Callable Objects

A function object is an object that can be called as if it were a function.

[20.10/1] A function object type is an object type (3.9) that can be the type of the postfix-expression in a function call (5.2.2, 13.3.1.1). [...]

It should be noted that function references are not function object types, as references are not object types. The standard further reads on a note:

Such a type is a function pointer or a class type which has a member operator() or a class type which has a conversion to a pointer to function.

Function objects together with member pointers conform the callable objects, which as the name implies are objects that can be called —either with regular function call syntax or the ugly looking member pointer access ones for passing the implicit this argument—.

[20.10.1/3] A callable type is a function object type (20.10) or a pointer to member.

[20.10.1/4] A callable object is an object of a callable type.

A related concept is that of a call wrapper, which is a function object that forwards the call operation to the callable object it wraps.

[20.10.1/5] A call wrapper type is a type that holds a callable object and supports a call operation that forwards to that object.

[20.10.1/6] A call wrapper is an object of a call wrapper type.

[20.10.1/7] A target object is the callable object held by a call wrapper.

The standard provided call wrappers are std::function, std::bind, std::mem_fn and std::reference_wrapper.

Invoke

The syntax required to invoke a callable object depends on the callable type, with five different options to choose from. The pseudomacro INVOKE is defined as a conceptual aid to abstract these differences away —while the standard does not actually implement it, doing so is not only easy but also useful—.

[20.10.2/1] Define INVOKE(f, t1, t2, ..., tN) as follows:

  • (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T and t1 is an object of type T or a reference to an object of type T or a reference to an object of a type derived from T;
  • ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a class T and t1 is not one of the types described in the previous item;
  • t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is an object of type T or a reference to an object of type T or a reference to an object of a type derived from T;
  • (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1 is not one of the types described in the previous item;
  • f(t1, t2, ..., tN) in all other cases.

[20.10.2/2] Define INVOKE(f, t1, t2, ..., tN, R) as INVOKE(f, t1, t2, ..., tN) implicitly converted to R.

It should be noted that the (*t1).*f expression is used instead of the simpler t1->*f. This not only allows invoking a member pointer via a smart pointer, it also prevents invocation via an overloaded operator->* —scarce as those are in the wild—.

While not immediately obvious, a reference_wrapper can also be used to invoke a member pointer given that it is itself a call wrapper, resulting in the application of INVOKE to the referenced object.

The Solution

It should be clear by now that the implementation of is_callable<F(Args...)> will consist of determining whether the expression INVOKE(std::declval<F>(), std::declval<Arg>()...) is well formed or not.

C++14

C++14 provides a packaged solution almost ready to go in the form of std::result_of. This trait definition has been improved to became SFINAE-friendly, which means there will be no error when the INVOKE expression is ill formed; instead, the member typedef type will simply not be there.

[20.10.7.6]

Template: template <class Fn, class... ArgTypes> struct result_of<Fn(ArgTypes...)>;

Condition: Fn and all types in the parameter pack ArgTypes shall be complete types, (possibly cv-qualified) void, or arrays of unknown bound.

Comments: If the expression INVOKE(declval<Fn>(), declval<ArgTypes>()...) is well formed when treated as an unevaluated operand (Clause 5), the member typedef type shall name the type decltype(INVOKE(declval<Fn>(), declval<ArgTypes>()...)); otherwise, there shall be no member type. Access checking is performed as if in a context unrelated to Fn and ArgTypes. Only the validity of the immediate context of the expression is considered. [ Note: The compilation of the expression can result in side effects such as the instantiation of class template specializations and function template specializations, the generation of implicitly-defined functions, and so on. Such side effects are not in the “immediate context” and can result in the program being ill-formed. —end note ].

All that is needed is to exploit this newly gained guarantee in a SFINAE context. The way this is done is by defining a base template with a template parameter defaulted to void, and a specialization that evaluates an expression and always results in void for that parameter; only when such expression is well formed the specialization will be picked, as the argument matches the default parameter —this technique is not so different than using std::enable_if to pick template specializations—. Thus, the SFINAE can be turned into a bool metavalue:

namespace detail {
  template <typename T>
  using always_void = void;

  template <typename Expr, typename Enable = void>
  struct is_callable_impl
    : std::false_type
  {};

  template <typename F, typename ...Args>
  struct is_callable_impl<F(Args...), always_void<std::result_of_t<F(Args...)>>>
    : std::true_type
  {};
}

template <typename Expr>
struct is_callable
  : detail::is_callable_impl<Expr>
{};

This is due to N3436 by Eric Niebler, David Walker, and Joel de Guzman. Before it came into C++14 it was missed so bad that Boost has turned its own result_of implementation into a SFINAE-friendly one —even on C++03— since 1.52.0.

C++11

This definition of std::result_of states as a requirement that the INVOKE expression be well formed, so it cannot be leveraged to implement the solution—as we already knew—. Instead, all of the alternative expressions in INVOKE have to be tested in order to determine if any of them is well formed:

namespace detail {
  template <typename T>
  using always_void = void;

  template <typename Expr, std::size_t Step = 0, typename Enable = void>
  struct is_callable_impl
    : is_callable_impl<Expr, Step + 1>
  {};

  // (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T 
  // and t1 is an object of type T or a reference to an object of type T or a 
  // reference to an object of a type derived from T;
  template <typename F, typename T, typename ...Args>
  struct is_callable_impl<F(T, Args...), 0,
    always_void<decltype(
      (std::declval<T>().*std::declval<F>())(std::declval<Args>()...)
    )>
  > : std::true_type
  {};

  // ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a class T 
  // and t1 is not one of the types described in the previous item;
  template <typename F, typename T, typename ...Args>
  struct is_callable_impl<F(T, Args...), 1,
    always_void<decltype(
      ((*std::declval<T>()).*std::declval<F>())(std::declval<Args>()...)
    )>
  > : std::true_type
  {};

  // t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is an 
  // object of type T or a reference to an object of type T or a reference to an 
  // object of a type derived from T;
  template <typename F, typename T>
  struct is_callable_impl<F(T), 2,
    always_void<decltype(
      std::declval<T>().*std::declval<F>()
    )>
  > : std::true_type
  {};

  // (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1 is 
  // not one of the types described in the previous item;
  template <typename F, typename T>
  struct is_callable_impl<F(T), 3,
    always_void<decltype(
      (*std::declval<T>()).*std::declval<F>()
    )>
  > : std::true_type
  {};

  // f(t1, t2, ..., tN) in all other cases.
  template <typename F, typename ...Args>
  struct is_callable_impl<F(Args...), 4,
    always_void<decltype(
      std::declval<F>()(std::declval<Args>()...)
    )>
  > : std::true_type
  {};

  template <typename Expr>
  struct is_callable_impl<Expr, 5>
    : std::false_type
  {};
}

template <typename Expr>
struct is_callable
  : detail::is_callable_impl<Expr>
{};

Not as nice as before, but still manageable...

C++03

Without decltype, the only unevaluated context to abuse is sizeof; and without generalized SFINAE —also known as SFINAE for expressions—, all expressions need to always be well formed.

This technique is based on the one described here by Eric Niebler.
For clarity and brevity, this code uses C++11/14 features that have known approximations in C++03.

The potentially callable type needs to be wrapped so that the call expression is always well formed. This is done by providing a conversion to a function pointer that accepts all kinds of arguments —which makes the type a function object type as per [20.10/1]— to act as a fallback:

namespace detail
{
  struct fallback_argument
  {
    template <typename T>
    fallback_argument(T const&); // convertible from anything
  };

  struct fallback_call
  {
    fallback_call const& operator,(int) const; // explained later
  };

  template <typename ...Args>
  struct call_wrapper_fallback
  {
    typedef fallback_call const& (*function_pointer)(
       // as many fallback_arguments as elements in Args...
      std::conditional_t<false, Args, fallback_argument>...
    );
    operator function_pointer() const volatile;
  };
}

The wrapper then merges the potentially valid call with the fallback call:

namespace detail
{
  template <typename FD, typename ...Args>
  struct call_wrapper;

  // (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T 
  // and t1 is an object of type T or a reference to an object of type T or a 
  // reference to an object of a type derived from T;
  //
  // ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a class T 
  // and t1 is not one of the types described in the previous item;
  template <typename R, typename C, typename ...P, typename ...Args>
  struct call_wrapper<R (C::*)(P...), Args...>
    : call_wrapper_fallback<Args...>
  {
    R operator()(C&, P...) const volatile;
    R operator()(C*, P...) const volatile;

    template <typename SmartPtr>
    std::enable_if_t<boost::has_dereference<SmartPtr, C&>::value, R>
    operator()(SmartPtr, P...) const volatile;
    // boost::has_dereference uses the same principles than is_callable
  };

  template <typename R, typename C, typename ...P, typename ...Args>
  struct call_wrapper<R (C::*)(P...) const, Args...>
    : call_wrapper_fallback<Args...>
  {
    R operator()(C const&, P...) const volatile;
    R operator()(C const*, P...) const volatile;

    template <typename SmartPtr>
    std::enable_if_t<boost::has_dereference<SmartPtr, C const&>::value, R>
    operator()(SmartPtr, P...) const volatile;
  };

  // t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is an 
  // object of type T or a reference to an object of type T or a reference to an 
  // object of a type derived from T;
  //
  // (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1 is 
  // not one of the types described in the previous item;
  template <typename R, typename C, typename ...Args>
  struct call_wrapper<R C::*, Args...>
    : call_wrapper_fallback<Args...>
  {
    // return types would be cv-refs, but it is irrelevant for just checking the call
    R operator()(C const&) const volatile;
    R operator()(C const*) const volatile;

    template <typename SmartPtr>
    std::enable_if_t<boost::has_dereference<SmartPtr, C const&>::value, R>
    operator()(SmartPtr) const volatile;
  };

  // f(t1, t2, ..., tN) in all other cases.
  template <typename R, typename ...P, typename ...Args>
  struct call_wrapper<R(*)(P...), Args...>
    : call_wrapper_fallback<Args...>
  {
    R operator()(P...) const volatile;
  };

  template <typename FD, typename ...Args>
  struct call_wrapper<FD, Args...>
    : std::conditional_t<std::is_class<FD>::value, FD, empty>
    , call_wrapper_fallback<Args...>
  {
     // if FD is a class, extend it to inherit its operator()s and 
     // conversions to function pointers if any
     //
     // otherwise, extend empty which is just struct empty {};
  };
}

With the wrapper in place, the solution is implemented by making an unevaluated call to an instance of it with the same cv-ref qualifications than the target type —using qualify_as_t, of trivial implementation—. This call will yield fallback_call when the original expression would be ill formed, and any other type when it would be well formed. The result type of the call can then be detected using an overloaded check function.

But there is a caveat, the result type of a well formed call could just as well be void, which cannot be used as an argument to the check function. There are only a handful of constructions that accept a void-resulting expression as argument, and from those the only one that can be tampered with is the comma operator. That is why fallback_call overloads operator, to return itself, so that (expr, 0) can be used to turn anything but fallback_calls into an int—this works provided that user defined types don't overload operator, to return void, but who does that?—.

Finally, the check function overloads return known types of different sizes, allowing sizeof to determine which overload was picked —this is sometimes referred to as the sizeof trick, obsolete since decltype—:

namespace detail
{
  template <typename Expr, typename FD>
  struct is_callable_impl;

  template <typename F, typename ...Args, typename FD>
  struct is_callable_impl<F(Args...), FD>
  {
      typedef qualify_as_t<call_wrapper<FD, Args...>, F> call_wrapper_t;
      typedef char (&no_type)[1];
      typedef char (&yes_type)[2];

      template <typename T>
      static yes_type check(T const &);
      static no_type check(fallback_call const &);

      static bool const value =
          sizeof(check(
              (std::declval<call_wrapper_t>()(std::declval<Args>()...), 0)
          )) == sizeof(yes_type);
      typedef std::integral_constant<bool, value> type;
  };
}

template <typename Expr>
struct is_callable;

template <typename F, typename ...Args>
struct is_callable<F(Args...)>
  : detail::is_callable_impl<F(Args...), std::decay_t<F>>::type
{};

This implementation is a good approximation, but it does have some drawbacks —besides complexity—. The obvious one is that it has to use preprocessor repetition to emulate variadic templates, thus only working up to a predefined number of arguments. The more subtle ones have to do with corner cases that would cause ambiguities or other hard errors, like testing a function object that is convertible to a function pointer accepting all kinds of arguments; those situations should be rare enough to not compromise the trait's usability.

At least one thing is clear... C++ knows how to stay on top of the wave!