20 Jan, 2014

True Story: Moving Past Bind

C++ provides std::bind for partial function application, which is the process of fixing a number of arguments to a function, producing another function of same or smaller arity. In the C++ lands, std::bind returns a function object which stores copies of the fixed arguments —known as bound arguments—, allowing the resulting bind expression to be called at points far from where it was created, multiple times if desired. This has important implications when the intention is to make that call just once...

The Problem

The function object returned from std::bind is not prepared to deal with the notion that sometimes it's going to be called just once —if at all—, and then immediately thrown away. In those scenarios, it would be better to relinquish ownership of the bound arguments to the wrapped function object, avoiding an unnecessary copy that would not even be possible when handling arguments of movable-only types.

These deferred calls appear in the standard at several places —std::call_once, std::thread, std::async—. Just like with std::bind, the target callable and arguments are decay copied, as the call will happen at a point in time where the lifetime of those objects could have already ended. Unlike std::bind, both wrapped callable and arguments will be moved —turned into rvalues— when the call is eventually made.

The standard library already provides the first half of the solution to the implementation of these deferred calls, or the more general one shot bind. The remaining half is moving the wrapped callable and arguments out of bind, which requires knowing which of the arguments are bound and which ones aren't.

std::bind

Since the solution will be reusing std::bind, it's important to know the rules under which it operates:

[20.9.9/1] The function template bind returns an object that binds a callable object passed as an argument to additional arguments.

[20.9.9.1/3] In the text that follows, the following names have the following meanings:

  • FD is the type decay<F>::type,

  • fd is an lvalue of type FD constructed from std::forward<F>(f),

  • Ti is the ith type in the template parameter back BoundArgs,

  • TiD is the type decay<Ti>::type,

  • ti is the ith argument in the function parameter pack bound_args,

  • tid is an lvalue of type TiD constructed from std::forward<Ti>(ti),

  • Uj is the jth deduced type of the UnBoundArgs&&... parameter of the forwarding call wrapper, and

  • uj is the jth argument associated with Uj.

template<class F, class... BoundArgs>
unspecified bind(F&& f, BoundArgs&&... bound_args);

[20.9.9.1/3] Returns: A forwarding call wrapper g with a weak result type (20.9.2). The effect of g(u1, u2, ..., uM) shall be INVOKE (fd, std::forward<V1>(v1), std::forward<V2>(v2), ..., std::forward<VN>(vN), result_of<FD cv & (V1, V2, ..., VN)>::type), where cv represents the cv-qualifiers of g and the values and types of the bound arguments v1, v2, ..., vN are determined as specified below. [...]

[20.9.9.1/10] The values of the bound arguments v1, v2, ..., vN and their corresponding types V1, V2, ..., VN depend on the types TiD derived from the call to bind and the cv-qualifiers cv of the call wrapper g as follows:

  • if TiD is reference_wrapper<T>, the argument is tid.get() and its type Vi is T&;

  • if the value of is_bind_expression<TiD>::value is true, the argument is tid(std::forward<Uj>(uj)...) and its type Vi is result_of<TiD cv & (Uj&&...)>::type&&;

  • if the value j of is_placeholder<TiD>::value is not zero, the argument is std::forward<Uj>(uj) and its type Vi is Uj&&;

  • otherwise, the value is tid and its type Vi is TiD cv &.

In short, the resulting function object from std::bind will pass lvalue references to the bound arguments, implicitly unwrapping std::reference_wrappers, evaluating nested bind expressions, and perfectly forwarding unbound arguments where placeholders were used.

The Solution

one_shot_bind

The forwarding call wrapper returned from std::bind is half of the solution. The other half consist of another forwarding call wrapper, one with knowledge of how the bind expression was created:

namespace detail {
  template <typename F, typename BoundArgs, typename FD = std::decay_t<F>>
  class one_shot_wrapper;

  template <typename F, typename ...BoundArgs, typename FD>
  class one_shot_wrapper<F, void(BoundArgs...), FD>
  {
  public:
    explicit one_shot_wrapper(FD const& f)
     : _f{f}
    {}
    explicit one_shot_wrapper(FD&& f)
     : _f{std::move(f)}
    {}

    template <typename ...Args>
    decltype(auto) operator()(Args&&... args)
    {
      return INVOKE(std::move(_f)
      , forward_from_bound<BoundArgs>::call(std::forward<Args>(args))...);
    }

  private:
    FD _f;
  };

The one_shot_wrapper is a forwarding call wrapper providing an operator() that forwards or moves each argument as appropriate. Such operator is non-const, so that attempts to call a const qualified instance of the wrapper returned from std::bind will result in a compilation error. The missing piece of the solution is the most important one: forward_from_bound, where the decisions are actually made.

The base case deals with ordinary bound arguments. Those are received by non-const lvalue reference and moved out:

namespace detail {
  template <
    typename Ti, typename TiD = std::decay_t<Ti>
  , typename Enable = void
  >
  struct forward_from_bound {
    static TiD&& call(TiD& tid) {
      return std::move(tid);
    }
  };
}

Then there's the placeholders, for which unbound arguments are received; and the bind expressions, for which the result of evaluating said expressions are received. Those are perfectly forwarded:

namespace detail {
  template <typename Ti, typename TiD>
  struct forward_from_bound<
    Ti, TiD
  , typename std::enable_if<
      std::is_placeholder<TiD>::value ||
      std::is_bind_expression<TiD>::value
    >::type
  > {
    template <typename Uj>
    static Uj&& call(Uj&& uj) {
      return std::forward<Uj>(uj);
    }
  };
}

Finally, the bound reference wrappers, which are received unwrapped and returned the same:

namespace detail {
  template <typename Ti, typename T>
  struct forward_from_bound<
    Ti, std::reference_wrapper<T>
  > {
    static T& call(T& tid) {
      return tid;
    }
  };
}

With those pieces ready, it is now possible to reuse std::bind and complete the solution:

template <typename F, typename ...BoundArgs>
auto one_shot_bind(F&& f, BoundArgs&&... bound_args) {
  return std::bind(
    detail::one_shot_wrapper<F, void(BoundArgs...)>{std::forward<F>(f)}
  , std::forward<BoundArgs>(bound_args)...);
}

A note on move semantics

Moving the bound arguments out of the call wrapper is fine, because the contract of one_shot_bind requires that the resulting function object be invoked at most once. It's easy to see how an additional flag could be added —in debug builds only— so that breaking that contract results in a runtime assertion.

However, there's another problematic scenario —one with std::bind itself— from which protecting the user is impossible in the general case. Consider the following snippet:

void foo(std::string s1, std::string s2) {
  // do something with s1 and s2 that
  // justifies taking them by value...
}

int main() {
  using namespace std::placeholders;
  auto bound = std::bind(&foo, _1, _1);
  bound(std::string{"Hello"});
}

Here foo takes both arguments by value, both of which are initialized from perfectly forwarding the std::string{"Hello"} temporary. Only one of them will contain the string "Hello", which one of them is implementation defined.

deferred_call

With the general solution in place, it's time to look at implementing the simpler use of deferred calls found in the standard. The differences with one_shot_bind are simple: all arguments are provided at the bind point, and none of them is special. Actually, the lack of implicit unwrapping of std::reference_wrappers is an inconsistency with the rest of the standard library —and an inconvenient one when used in contexts where implicit conversions does not happen— so this solution will differ from the standard to fill that need.

Not only placeholders and bind expressions from the standard library are handled specially by std::bind, but all objects whose type conforms to the corresponding traits —std::is_placeholder, std::is_bind_expression—. In order to avoid special treatment for those arguments, their types have to be hidden; this can be done using yet another wrapper:

namespace detail {
  template <typename T, typename TD = std::decay_t<T>>
  class protect_wrapper
  {
  public:
    explicit protect_wrapper(TD const& value)
     : _value{value}
    {}
    explicit protect_wrapper(TD&& value)
     : _value{std::move(value)}
    {}

    TD& get() {
      return _value;
    }

  private:
    TD _value;
  };

  // hide the type of placeholders and bind expressions
  template <
    typename T, typename TD = std::decay_t<T>
  , typename Enable =
      typename std::enable_if<
        std::is_placeholder<TD>::value ||
        std::is_bind_expression<TD>::value
      >::type
  >
  protect_wrapper<T> protect(T&& value)
  {
      return protect_wrapper<T>{std::forward(value)};
  }

  // leave everything else as is
  template <
    typename T, typename TD = std::decay_t<T>
  , typename Enable =
      typename std::enable_if<
        !std::is_placeholder<TD>::value &&
        !std::is_bind_expression<TD>::value
      >::type
  >
  T&& protect(T&& value)
  {
      return value;
  }
}

This wrapper has to be automatically unwrapped by one_shot_bind, and its value moved out:

namespace detail {
  template <typename Ti, typename T>
  struct forward_from_bound<
    Ti, protect_wrapper<T>
  > {
    static T&& call(protect_wrapper<T>& tid) {
      return std::move(tid.get());
    }
  };
}

The implementation of deferred_call looks just like the one of one_shot_bind, except that all special arguments are protected:

template <typename F, typename ...Args>
auto deferred_call(F&& f, Args&&... args) {
  return std::bind(
    detail::one_shot_wrapper<F, void(Args...)>{std::forward<F>(f)}
  , detail::protect(std::forward<Args>(args))...);
}

The Lambda Predicament

This seems like a lot of work for something repeatedly described in the standard library —and that's without considering that the implementation for INVOKE has to be provided as well—. Maybe a lambda expression, supposedly more powerful than a bind expression, is a better choice for the simple case of deferred_call. Here is a limited example of how such C++14 lambda would look:

template <typename F, typename A0>
auto deferred_call(F&& f, A0&& a0) {
  return [
    f = std::forward<F>(f)
  , arg0 = std::forward<A0>(a0)
  ]() mutable -> decltype(auto) {
    return INVOKE(std::move(f), std::move(a0));
  };
}

Not only is this verbose, particularly the decay copy of the captures, but it's also brittle. Without mutable —for which the empty parameter list is mandatory—, the generated operator() is const, in which case the captures would not be moved into the INVOKE expression. Without decltype(auto), the return type would drop the cvref-qualifications of the result type of the INVOKE expression. But there is a bigger problem —which the lack of variadics in the previous snippet should have hint at—: an init-capture is what allows to capture a decay copy instead of a plain copy, but those cannot be used with parameter packs:

[5.1.2/24] A simple-capture followed by an ellipsis is a pack expansion (14.5.3). An init-capture followed by an ellipsis is ill-formed.

A good workaround for such impediment is to decay copy the arguments into a std::tuple, and capture that instead. Conveniently, std::make_tuple will not only store decayed copies of its arguments, but it will also implicitly unwrap std::reference_wrappers. To expand the arguments when invoking the callable, apply could be used —another desired utility introduced yet not provided by the standard library—. The final implementation follows:

template <typename F, typename ...Args>
auto deferred_call(F&& f, Args&&... args) {
  return [
    f = std::forward<F>(f)
  , args = std::make_tuple(std::forward<Args>(args)...)
  ]() mutable -> decltype(auto) {
    return apply(std::move(f), std::move(args));
  };
}

A lambda implementation is thus possible in C++14 —assuming apply is given, just as INVOKE was assumed given before—, but hardly usable in the wild. Its complexity and fragility call for the solution to be put behind an abstraction layer, and its details soon forgotten...