Function.h

Go to the documentation of this file.

/*
 * Copyright 2016-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * @author Eric Niebler (eniebler@fb.com), Sven Over (over@fb.com)
 * Acknowledgements: Giuseppe Ottaviano (ott@fb.com)
 */

#pragma once

#include <functional>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

#include <folly/CppAttributes.h>
#include <folly/Portability.h>
#include <folly/Traits.h>
#include <folly/functional/Invoke.h>
#include <folly/lang/Exception.h>

namespace folly {

template <typename FunctionType>
class Function;

template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const> constCastFunction(
    Function<ReturnType(Args...)>&&) noexcept;

#if FOLLY_HAVE_NOEXCEPT_FUNCTION_TYPE
template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const noexcept> constCastFunction(
    Function<ReturnType(Args...) noexcept>&&) noexcept;
#endif

namespace detail {
namespace function {

enum class Op { MOVE, NUKE, HEAP };

union Data {
  Data() {}
  void* big;
  std::aligned_storage<6 * sizeof(void*)>::type tiny;
};

template <typename Fun, typename = Fun*>
using IsSmall = Conjunction<
    bool_constant<(sizeof(Fun) <= sizeof(Data::tiny))>,
    std::is_nothrow_move_constructible<Fun>>;
using SmallTag = std::true_type;
using HeapTag = std::false_type;

template <typename T>
struct NotFunction : std::true_type {};
template <typename T>
struct NotFunction<Function<T>> : std::false_type {};

template <typename T>
using EnableIfNotFunction =
    typename std::enable_if<NotFunction<T>::value>::type;

struct CoerceTag {};

template <typename T>
bool isNullPtrFn(T* p) {
  return p == nullptr;
}
template <typename T>
std::false_type isNullPtrFn(T&&) {
  return {};
}

template <typename F, typename... Args>
using CallableResult = decltype(std::declval<F>()(std::declval<Args>()...));

template <
    typename From,
    typename To,
    typename = typename std::enable_if<
        !std::is_reference<To>::value || std::is_reference<From>::value>::type>
using SafeResultOf = decltype(static_cast<To>(std::declval<From>()));

template <typename FunctionType>
struct FunctionTraits;

template <typename ReturnType, typename... Args>
struct FunctionTraits<ReturnType(Args...)> {
  using Call = ReturnType (*)(Data&, Args&&...);
  using IsConst = std::false_type;
  using ConstSignature = ReturnType(Args...) const;
  using NonConstSignature = ReturnType(Args...);
  using OtherSignature = ConstSignature;

  template <typename F>
  using ResultOf =
      SafeResultOf<CallableResult<_t<std::decay<F>>&, Args...>, ReturnType>;

  template <typename Fun>
  static ReturnType callSmall(Data& p, Args&&... args) {
    return static_cast<ReturnType>((*static_cast<Fun*>(
        static_cast<void*>(&p.tiny)))(static_cast<Args&&>(args)...));
  }

  template <typename Fun>
  static ReturnType callBig(Data& p, Args&&... args) {
    return static_cast<ReturnType>(
        (*static_cast<Fun*>(p.big))(static_cast<Args&&>(args)...));
  }

  static ReturnType uninitCall(Data&, Args&&...) {
    throw std::bad_function_call();
  }

  ReturnType operator()(Args... args) {
    auto& fn = *static_cast<Function<NonConstSignature>*>(this);
    return fn.call_(fn.data_, static_cast<Args&&>(args)...);
  }

  class SharedProxy {
    std::shared_ptr<Function<NonConstSignature>> sp_;

   public:
    explicit SharedProxy(Function<NonConstSignature>&& func)
        : sp_(std::make_shared<Function<NonConstSignature>>(std::move(func))) {}
    ReturnType operator()(Args&&... args) const {
      return (*sp_)(static_cast<Args&&>(args)...);
    }
  };
};

template <typename ReturnType, typename... Args>
struct FunctionTraits<ReturnType(Args...) const> {
  using Call = ReturnType (*)(Data&, Args&&...);
  using IsConst = std::true_type;
  using ConstSignature = ReturnType(Args...) const;
  using NonConstSignature = ReturnType(Args...);
  using OtherSignature = NonConstSignature;

  template <typename F>
  using ResultOf = SafeResultOf<
      CallableResult<const _t<std::decay<F>>&, Args...>,
      ReturnType>;

  template <typename Fun>
  static ReturnType callSmall(Data& p, Args&&... args) {
    return static_cast<ReturnType>((*static_cast<const Fun*>(
        static_cast<void*>(&p.tiny)))(static_cast<Args&&>(args)...));
  }

  template <typename Fun>
  static ReturnType callBig(Data& p, Args&&... args) {
    return static_cast<ReturnType>(
        (*static_cast<const Fun*>(p.big))(static_cast<Args&&>(args)...));
  }

  static ReturnType uninitCall(Data&, Args&&...) {
    throw std::bad_function_call();
  }

  ReturnType operator()(Args... args) const {
    auto& fn = *static_cast<const Function<ConstSignature>*>(this);
    return fn.call_(fn.data_, static_cast<Args&&>(args)...);
  }

  class SharedProxy {
    std::shared_ptr<Function<ConstSignature>> sp_;

   public:
    explicit SharedProxy(Function<ConstSignature>&& func)
        : sp_(std::make_shared<Function<ConstSignature>>(std::move(func))) {}
    ReturnType operator()(Args&&... args) const {
      return (*sp_)(static_cast<Args&&>(args)...);
    }
  };
};

#if FOLLY_HAVE_NOEXCEPT_FUNCTION_TYPE
template <typename ReturnType, typename... Args>
struct FunctionTraits<ReturnType(Args...) noexcept> {
  using Call = ReturnType (*)(Data&, Args&&...) noexcept;
  using IsConst = std::false_type;
  using ConstSignature = ReturnType(Args...) const noexcept;
  using NonConstSignature = ReturnType(Args...) noexcept;
  using OtherSignature = ConstSignature;

  template <typename F>
  using ResultOf =
      SafeResultOf<CallableResult<_t<std::decay<F>>&, Args...>, ReturnType>;

  template <typename Fun>
  static ReturnType callSmall(Data& p, Args&&... args) noexcept {
    return static_cast<ReturnType>((*static_cast<Fun*>(
        static_cast<void*>(&p.tiny)))(static_cast<Args&&>(args)...));
  }

  template <typename Fun>
  static ReturnType callBig(Data& p, Args&&... args) noexcept {
    return static_cast<ReturnType>(
        (*static_cast<Fun*>(p.big))(static_cast<Args&&>(args)...));
  }

  static ReturnType uninitCall(Data&, Args&&...) noexcept {
    terminate_with<std::bad_function_call>();
  }

  ReturnType operator()(Args... args) noexcept {
    auto& fn = *static_cast<Function<NonConstSignature>*>(this);
    return fn.call_(fn.data_, static_cast<Args&&>(args)...);
  }

  class SharedProxy {
    std::shared_ptr<Function<NonConstSignature>> sp_;

   public:
    explicit SharedProxy(Function<NonConstSignature>&& func)
        : sp_(std::make_shared<Function<NonConstSignature>>(std::move(func))) {}
    ReturnType operator()(Args&&... args) const {
      return (*sp_)(static_cast<Args&&>(args)...);
    }
  };
};

template <typename ReturnType, typename... Args>
struct FunctionTraits<ReturnType(Args...) const noexcept> {
  using Call = ReturnType (*)(Data&, Args&&...) noexcept;
  using IsConst = std::true_type;
  using ConstSignature = ReturnType(Args...) const noexcept;
  using NonConstSignature = ReturnType(Args...) noexcept;
  using OtherSignature = NonConstSignature;

  template <typename F>
  using ResultOf = SafeResultOf<
      CallableResult<const _t<std::decay<F>>&, Args...>,
      ReturnType>;

  template <typename Fun>
  static ReturnType callSmall(Data& p, Args&&... args) noexcept {
    return static_cast<ReturnType>((*static_cast<const Fun*>(
        static_cast<void*>(&p.tiny)))(static_cast<Args&&>(args)...));
  }

  template <typename Fun>
  static ReturnType callBig(Data& p, Args&&... args) noexcept {
    return static_cast<ReturnType>(
        (*static_cast<const Fun*>(p.big))(static_cast<Args&&>(args)...));
  }

  static ReturnType uninitCall(Data&, Args&&...) noexcept {
    throw std::bad_function_call();
  }

  ReturnType operator()(Args... args) const noexcept {
    auto& fn = *static_cast<const Function<ConstSignature>*>(this);
    return fn.call_(fn.data_, static_cast<Args&&>(args)...);
  }

  class SharedProxy {
    std::shared_ptr<Function<ConstSignature>> sp_;

   public:
    explicit SharedProxy(Function<ConstSignature>&& func)
        : sp_(std::make_shared<Function<ConstSignature>>(std::move(func))) {}
    ReturnType operator()(Args&&... args) const {
      return (*sp_)(static_cast<Args&&>(args)...);
    }
  };
};
#endif

template <typename Fun>
bool execSmall(Op o, Data* src, Data* dst) {
  switch (o) {
    case Op::MOVE:
      ::new (static_cast<void*>(&dst->tiny))
          Fun(std::move(*static_cast<Fun*>(static_cast<void*>(&src->tiny))));
      FOLLY_FALLTHROUGH;
    case Op::NUKE:
      static_cast<Fun*>(static_cast<void*>(&src->tiny))->~Fun();
      break;
    case Op::HEAP:
      break;
  }
  return false;
}

template <typename Fun>
bool execBig(Op o, Data* src, Data* dst) {
  switch (o) {
    case Op::MOVE:
      dst->big = src->big;
      src->big = nullptr;
      break;
    case Op::NUKE:
      delete static_cast<Fun*>(src->big);
      break;
    case Op::HEAP:
      break;
  }
  return true;
}

} // namespace function
} // namespace detail

template <typename FunctionType>
class Function final : private detail::function::FunctionTraits<FunctionType> {
  // These utility types are defined outside of the template to reduce
  // the number of instantiations, and then imported in the class
  // namespace for convenience.
  using Data = detail::function::Data;
  using Op = detail::function::Op;
  using SmallTag = detail::function::SmallTag;
  using HeapTag = detail::function::HeapTag;
  using CoerceTag = detail::function::CoerceTag;

  using Traits = detail::function::FunctionTraits<FunctionType>;
  using Call = typename Traits::Call;
  using Exec = bool (*)(Op, Data*, Data*);

  template <typename Fun>
  using IsSmall = detail::function::IsSmall<Fun>;

  // The `data_` member is mutable to allow `constCastFunction` to work without
  // invoking undefined behavior. Const-correctness is only violated when
  // `FunctionType` is a const function type (e.g., `int() const`) and `*this`
  // is the result of calling `constCastFunction`.
  mutable Data data_{};
  Call call_{&Traits::uninitCall};
  Exec exec_{nullptr};

  bool exec(Op o, Data* src, Data* dst) const {
    return exec_ && exec_(o, src, dst);
  }

  friend Traits;
  friend Function<typename Traits::ConstSignature> folly::constCastFunction<>(
      Function<typename Traits::NonConstSignature>&&) noexcept;
  friend class Function<typename Traits::OtherSignature>;

  template <typename Fun>
  Function(Fun&& fun, SmallTag) noexcept {
    using FunT = typename std::decay<Fun>::type;
    if (!detail::function::isNullPtrFn(fun)) {
      ::new (static_cast<void*>(&data_.tiny)) FunT(static_cast<Fun&&>(fun));
      call_ = &Traits::template callSmall<FunT>;
      exec_ = &detail::function::execSmall<FunT>;
    }
  }

  template <typename Fun>
  Function(Fun&& fun, HeapTag) {
    using FunT = typename std::decay<Fun>::type;
    data_.big = new FunT(static_cast<Fun&&>(fun));
    call_ = &Traits::template callBig<FunT>;
    exec_ = &detail::function::execBig<FunT>;
  }

  template <typename Signature>
  Function(Function<Signature>&& that, CoerceTag)
      : Function(static_cast<Function<Signature>&&>(that), HeapTag{}) {}

  Function(Function<typename Traits::OtherSignature>&& that, CoerceTag) noexcept
      : call_(that.call_), exec_(that.exec_) {
    that.call_ = &Traits::uninitCall;
    that.exec_ = nullptr;
    exec(Op::MOVE, &that.data_, &data_);
  }

 public:
  Function() = default;

  // not copyable
  Function(const Function&) = delete;

#if __OBJC__
  // Make sure Objective C blocks are copied
  template <class ReturnType, class... Args>
  /*implicit*/ Function(ReturnType (^objCBlock)(Args... args))
      : Function([blockCopy = (ReturnType(^)(Args...))[objCBlock copy]](
                     Args... args) { return blockCopy(args...); }){};
#endif

  Function(Function&& that) noexcept : call_(that.call_), exec_(that.exec_) {
    // that must be uninitialized before exec() call in the case of self move
    that.call_ = &Traits::uninitCall;
    that.exec_ = nullptr;
    exec(Op::MOVE, &that.data_, &data_);
  }

  /* implicit */ Function(std::nullptr_t) noexcept {}

  template <
      typename Fun,
      typename = detail::function::EnableIfNotFunction<Fun>,
      typename = typename Traits::template ResultOf<Fun>>
  /* implicit */ Function(Fun fun) noexcept(
      IsSmall<Fun>::value&& noexcept(Fun(std::declval<Fun>())))
      : Function(std::move(fun), IsSmall<Fun>{}) {}

  template <
      typename Signature,
      typename = typename Traits::template ResultOf<Function<Signature>>>
  Function(Function<Signature>&& that) noexcept(
      noexcept(Function(std::move(that), CoerceTag{})))
      : Function(std::move(that), CoerceTag{}) {}

  template <
      typename Member,
      typename Class,
      // Prevent this overload from being selected when `ptr` is not a
      // compatible member function pointer.
      typename = decltype(Function(std::mem_fn((Member Class::*)0)))>
  /* implicit */ Function(Member Class::*ptr) noexcept {
    if (ptr) {
      *this = std::mem_fn(ptr);
    }
  }

  ~Function() {
    exec(Op::NUKE, &data_, nullptr);
  }

  Function& operator=(const Function&) = delete;

#if __OBJC__
  // Make sure Objective C blocks are copied
  template <class ReturnType, class... Args>
  /* implicit */ Function& operator=(ReturnType (^objCBlock)(Args... args)) {
    (*this) = [blockCopy = (ReturnType(^)(Args...))[objCBlock copy]](
                  Args... args) { return blockCopy(args...); };
    return *this;
  }
#endif

  Function& operator=(Function&& that) noexcept {
    // Q: Why is it safe to destroy and reconstruct this object in place?
    // A: Two reasons: First, `Function` is a final class, so in doing this
    //    we aren't slicing off any derived parts. And second, the move
    //    operation is guaranteed not to throw so we always leave the object
    //    in a valid state.
    // In the case of self-move (this == &that), this leaves the object in
    // a default-constructed state. First the object is destroyed, then we
    // pass the destroyed object to the move constructor. The first thing the
    // move constructor does is default-construct the object. That object is
    // "moved" into itself, which is a no-op for a default-constructed Function.
    this->~Function();
    ::new (this) Function(std::move(that));
    return *this;
  }

  template <typename Fun, typename = decltype(Function(std::declval<Fun>()))>
  Function& operator=(Fun fun) noexcept(
      noexcept(/* implicit */ Function(std::declval<Fun>()))) {
    // Doing this in place is more efficient when we can do so safely.
    if (noexcept(/* implicit */ Function(std::declval<Fun>()))) {
      // Q: Why is is safe to destroy and reconstruct this object in place?
      // A: See the explanation in the move assignment operator.
      this->~Function();
      ::new (this) Function(std::move(fun));
    } else {
      // Construct a temporary and (nothrow) swap.
      Function(std::move(fun)).swap(*this);
    }
    return *this;
  }

  template <
      typename Signature,
      typename = typename Traits::template ResultOf<Function<Signature>>>
  Function& operator=(Function<Signature>&& that) noexcept(
      noexcept(Function(std::move(that)))) {
    return (*this = Function(std::move(that)));
  }

  Function& operator=(std::nullptr_t) noexcept {
    return (*this = Function());
  }

  template <typename Member, typename Class>
  auto operator=(Member Class::*ptr) noexcept
      // Prevent this overload from being selected when `ptr` is not a
      // compatible member function pointer.
      -> decltype(operator=(std::mem_fn(ptr))) {
    return ptr ? (*this = std::mem_fn(ptr)) : (*this = Function());
  }

  using Traits::operator();

  void swap(Function& that) noexcept {
    std::swap(*this, that);
  }

  explicit operator bool() const noexcept {
    return exec_ != nullptr;
  }

  bool hasAllocatedMemory() const noexcept {
    return exec(Op::HEAP, nullptr, nullptr);
  }

  using typename Traits::SharedProxy;

  SharedProxy asSharedProxy() && {
    return SharedProxy{std::move(*this)};
  }

  std::function<typename Traits::NonConstSignature> asStdFunction() && {
    return std::move(*this).asSharedProxy();
  }
};

template <typename FunctionType>
void swap(Function<FunctionType>& lhs, Function<FunctionType>& rhs) noexcept {
  lhs.swap(rhs);
}

template <typename FunctionType>
bool operator==(const Function<FunctionType>& fn, std::nullptr_t) {
  return !fn;
}

template <typename FunctionType>
bool operator==(std::nullptr_t, const Function<FunctionType>& fn) {
  return !fn;
}

template <typename FunctionType>
bool operator!=(const Function<FunctionType>& fn, std::nullptr_t) {
  return !(fn == nullptr);
}

template <typename FunctionType>
bool operator!=(std::nullptr_t, const Function<FunctionType>& fn) {
  return !(nullptr == fn);
}

template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const> constCastFunction(
    Function<ReturnType(Args...)>&& that) noexcept {
  return Function<ReturnType(Args...) const>{std::move(that),
                                             detail::function::CoerceTag{}};
}

template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const> constCastFunction(
    Function<ReturnType(Args...) const>&& that) noexcept {
  return std::move(that);
}

#if FOLLY_HAVE_NOEXCEPT_FUNCTION_TYPE
template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const noexcept> constCastFunction(
    Function<ReturnType(Args...) noexcept>&& that) noexcept {
  return Function<ReturnType(Args...) const noexcept>{
      std::move(that), detail::function::CoerceTag{}};
}

template <typename ReturnType, typename... Args>
Function<ReturnType(Args...) const noexcept> constCastFunction(
    Function<ReturnType(Args...) const noexcept>&& that) noexcept {
  return std::move(that);
}
#endif

template <typename FunctionType>
class FunctionRef;

template <typename ReturnType, typename... Args>
class FunctionRef<ReturnType(Args...)> final {
  using Call = ReturnType (*)(void*, Args&&...);

  static ReturnType uninitCall(void*, Args&&...) {
    throw std::bad_function_call();
  }

  template <typename Fun>
  static ReturnType call(void* object, Args&&... args) {
    using Pointer = _t<std::add_pointer<Fun>>;
    return static_cast<ReturnType>(invoke(
        static_cast<Fun&&>(*static_cast<Pointer>(object)),
        static_cast<Args&&>(args)...));
  }

  void* object_{nullptr};
  Call call_{&FunctionRef::uninitCall};

 public:
  FunctionRef() = default;

  template <
      typename Fun,
      typename std::enable_if<
          Conjunction<
              Negation<std::is_same<FunctionRef, _t<std::decay<Fun>>>>,
              is_invocable_r<ReturnType, Fun&&, Args&&...>>::value,
          int>::type = 0>
  constexpr /* implicit */ FunctionRef(Fun&& fun) noexcept
      // `Fun` may be a const type, in which case we have to do a const_cast
      // to store the address in a `void*`. This is safe because the `void*`
      // will be cast back to `Fun*` (which is a const pointer whenever `Fun`
      // is a const type) inside `FunctionRef::call`
      : object_(
            const_cast<void*>(static_cast<void const*>(std::addressof(fun)))),
        call_(&FunctionRef::call<Fun>) {}

  ReturnType operator()(Args... args) const {
    return call_(object_, static_cast<Args&&>(args)...);
  }

  constexpr explicit operator bool() const {
    return object_;
  }
};

} // namespace folly