diff options
author | Lloyd Pique <lpique@google.com> | 2022-11-09 13:56:40 -0800 |
---|---|---|
committer | Lloyd Pique <lpique@google.com> | 2023-12-13 01:14:11 +0000 |
commit | ace9af9bc7fc604df5c201c080bbad6ad5ec5529 (patch) | |
tree | e3298820ead3960999e6e15646665cf64c9489c2 /include | |
parent | 0c73574b6dd34c87390f2ae1e577cdaf21f820b3 (diff) | |
download | native-ace9af9bc7fc604df5c201c080bbad6ad5ec5529.tar.gz |
FTL: Introduce ftl::Function<F,N> et al.
ftl::Function<F, N> is a container for function object, and can mostly
be used in place of std::function<F>.
Unlike std::function<F>, a ftl::Function<F, N>:
* Uses a static amount of memory (controlled by N), and never any
dynamic allocation.
* Satisfies the std::is_trivially_copyable<> trait.
* Satisfies the std::is_trivially_destructible<> trait.
However to satisfy those constraints, the contained function object must
also satisfy those constraints, meaning certain types (like
std::unique_ptr's) cannot be part of the contained function object type.
The size of a ftl::Function<F, N> is guaranteed to be:
sizeof(std::intptr_t) * (N + 2)
If not specified, N defaults to zero, which is big enough to store a lambda
that captures a single pointer (such as "this" for forwarding to a
member function.
By comparison, sizeof(std::function) == sizeof(std::intptr_t) * 4, at
least with on x86-64 with clang 15.
Compile time checks are performed that the constraints are all satisfied,
and that the value of N is large enough to contain the desired function
object type.
ftl::make_function is a helper function to construct a ftl::Function,
and will deduce the template type arguments. In addition to constructing
a ftl::Function for a function object, ftl::make_function has overloads
for creating a ftl::Function which will invoke a member function or a free
(non-member) function.
ftl::no_op is a helper value to construct a ftl::Function<F, N> that
does nothing, except default construct a return value, if one is needed.
A unit test is also included to demonstrate and verify the
implementation, including asserting that function objects which don't
meet the requirements cannot be used. The test also asserts some
non-obvious corner cases for handling argument and return value
conversions to match how std::function behaves.
Bug: 279581095
Test: atest ftl_test
Change-Id: I268facb106a248d0766e931595291036bc606fb7
Diffstat (limited to 'include')
-rw-r--r-- | include/ftl/details/function.h | 135 | ||||
-rw-r--r-- | include/ftl/function.h | 297 |
2 files changed, 432 insertions, 0 deletions
diff --git a/include/ftl/details/function.h b/include/ftl/details/function.h new file mode 100644 index 0000000000..35c5a8b302 --- /dev/null +++ b/include/ftl/details/function.h @@ -0,0 +1,135 @@ +/* + * Copyright 2022 The Android Open Source Project + * + * 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. + */ + +#pragma once + +#include <array> +#include <cstddef> +#include <cstdint> +#include <cstring> +#include <type_traits> + +namespace android::ftl::details { + +// The maximum allowed value for the template argument `N` in +// `ftl::Function<F, N>`. +constexpr size_t kFunctionMaximumN = 14; + +// Converts a member function pointer type `Ret(Class::*)(Args...)` to an equivalent non-member +// function type `Ret(Args...)`. + +template <typename> +struct remove_member_function_pointer; + +template <typename Class, typename Ret, typename... Args> +struct remove_member_function_pointer<Ret (Class::*)(Args...)> { + using type = Ret(Args...); +}; + +template <typename Class, typename Ret, typename... Args> +struct remove_member_function_pointer<Ret (Class::*)(Args...) const> { + using type = Ret(Args...); +}; + +template <auto MemberFunction> +using remove_member_function_pointer_t = + typename remove_member_function_pointer<decltype(MemberFunction)>::type; + +// Helper functions for binding to the supported targets. + +template <typename Ret, typename... Args> +auto bind_opaque_no_op() -> Ret (*)(void*, Args...) { + return [](void*, Args...) -> Ret { + if constexpr (!std::is_void_v<Ret>) { + return Ret{}; + } + }; +} + +template <typename F, typename Ret, typename... Args> +auto bind_opaque_function_object(const F&) -> Ret (*)(void*, Args...) { + return [](void* opaque, Args... args) -> Ret { + return std::invoke(*static_cast<F*>(opaque), std::forward<Args>(args)...); + }; +} + +template <auto MemberFunction, typename Class, typename Ret, typename... Args> +auto bind_member_function(Class* instance, Ret (*)(Args...) = nullptr) { + return [instance](Args... args) -> Ret { + return std::invoke(MemberFunction, instance, std::forward<Args>(args)...); + }; +} + +template <auto FreeFunction, typename Ret, typename... Args> +auto bind_free_function(Ret (*)(Args...) = nullptr) { + return [](Args... args) -> Ret { return std::invoke(FreeFunction, std::forward<Args>(args)...); }; +} + +// Traits class for the opaque storage used by Function. + +template <std::size_t N> +struct function_opaque_storage { + // The actual type used for the opaque storage. An `N` of zero specifies the minimum useful size, + // which allows a lambda with zero or one capture args. + using type = std::array<std::intptr_t, N + 1>; + + template <typename S> + static constexpr bool require_trivially_copyable = std::is_trivially_copyable_v<S>; + + template <typename S> + static constexpr bool require_trivially_destructible = std::is_trivially_destructible_v<S>; + + template <typename S> + static constexpr bool require_will_fit_in_opaque_storage = sizeof(S) <= sizeof(type); + + template <typename S> + static constexpr bool require_alignment_compatible = + std::alignment_of_v<S> <= std::alignment_of_v<type>; + + // Copies `src` into the opaque storage, and returns that storage. + template <typename S> + static type opaque_copy(const S& src) { + // TODO: Replace with C++20 concepts/constraints which can give more details. + static_assert(require_trivially_copyable<S>, + "ftl::Function can only store lambdas that capture trivially copyable data."); + static_assert( + require_trivially_destructible<S>, + "ftl::Function can only store lambdas that capture trivially destructible data."); + static_assert(require_will_fit_in_opaque_storage<S>, + "ftl::Function has limited storage for lambda captured state. Maybe you need to " + "increase N?"); + static_assert(require_alignment_compatible<S>); + + type opaque; + std::memcpy(opaque.data(), &src, sizeof(S)); + return opaque; + } +}; + +// Traits class to help determine the template parameters to use for a ftl::Function, given a +// function object. + +template <typename F, typename = decltype(&F::operator())> +struct function_traits { + // The function type `F` with which to instantiate the `Function<F, N>` template. + using type = remove_member_function_pointer_t<&F::operator()>; + + // The (minimum) size `N` with which to instantiate the `Function<F, N>` template. + static constexpr std::size_t size = + (std::max(sizeof(std::intptr_t), sizeof(F)) - 1) / sizeof(std::intptr_t); +}; + +} // namespace android::ftl::details diff --git a/include/ftl/function.h b/include/ftl/function.h new file mode 100644 index 0000000000..3538ca4eae --- /dev/null +++ b/include/ftl/function.h @@ -0,0 +1,297 @@ +/* + * Copyright 2022 The Android Open Source Project + * + * 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. + */ + +#pragma once + +#include <cstddef> +#include <functional> +#include <type_traits> +#include <utility> + +#include <ftl/details/function.h> + +namespace android::ftl { + +// ftl::Function<F, N> is a container for function object, and can mostly be used in place of +// std::function<F>. +// +// Unlike std::function<F>, a ftl::Function<F, N>: +// +// * Uses a static amount of memory (controlled by N), and never any dynamic allocation. +// * Satisfies the std::is_trivially_copyable<> trait. +// * Satisfies the std::is_trivially_destructible<> trait. +// +// However those same limits are also required from the contained function object in turn. +// +// The size of a ftl::Function<F, N> is guaranteed to be: +// +// sizeof(std::intptr_t) * (N + 2) +// +// A ftl::Function<F, N> can always be implicitly converted to a larger size ftl::Function<F, M>. +// Trying to convert the other way leads to a compilation error. +// +// A default-constructed ftl::Function is in an empty state. The operator bool() overload returns +// false in this state. It is undefined behavior to attempt to invoke the function in this state. +// +// The ftl::Function<F, N> can also be constructed or assigned from ftl::no_op. This sets up the +// ftl::Function to be non-empty, with a function that when called does nothing except +// default-constructs a return value. +// +// The ftl::make_function() helpers construct a ftl::Function<F, N>, including deducing the +// values of F and N from the arguments it is given. +// +// The static ftl::Function<F, N>::make() helpers construct a ftl::Function<F, N> without that +// deduction, and also allow for implicit argument conversion if the target being called needs them. +// +// The construction helpers allow any of the following types of functions to be stored: +// +// * Any SMALL function object (as defined by the C++ Standard), such as a lambda with a small +// capture, or other "functor". The requirements are: +// +// 1) The function object must be trivial to destroy (in fact, the destructor will never +// actually be called once copied to the internal storage). +// 2) The function object must be trivial to copy (the raw bytes will be copied as the +// ftl::Function<F, N> is copied/moved). +// 3) The size of the function object cannot be larger than sizeof(std::intptr_t) * (N + 1), +// and it cannot require stricter alignment than alignof(std::intptr_t). +// +// With the default of N=0, a lambda can only capture a single pointer-sized argument. This is +// enough to capture `this`, which is why N=0 is the default. +// +// * A member function, with the address passed as the template value argument to the construction +// helper function, along with the instance pointer needed to invoke it passed as an ordinary +// argument. +// +// ftl::make_function<&Class::member_function>(this); +// +// Note that the indicated member function will be invoked non-virtually. If you need it to be +// invoked virtually, you should invoke it yourself with a small lambda like so: +// +// ftl::function([this] { virtual_member_function(); }); +// +// * An ordinary function ("free function"), with the address of the function passed as a template +// value argument. +// +// ftl::make_function<&std::atoi>(); +// +// As with the member function helper, as the function is known at compile time, it will be called +// directly. +// +// Example usage: +// +// class MyClass { +// public: +// void on_event() const {} +// int on_string(int*, std::string_view) { return 1; } +// +// auto get_function() { +// return ftl::function([this] { on_event(); }); +// } +// } cls; +// +// // A function container with no arguments, and returning no value. +// ftl::Function<void()> f; +// +// // Construct a ftl::Function containing a small lambda. +// f = cls.get_function(); +// +// // Construct a ftl::Function that calls `cls.on_event()`. +// f = ftl::function<&MyClass::on_event>(&cls); +// +// // Create a do-nothing function. +// f = ftl::no_op; +// +// // Invoke the contained function. +// f(); +// +// // Also invokes it. +// std::invoke(f); +// +// // Create a typedef to give a more meaningful name and bound the size. +// using MyFunction = ftl::Function<int(std::string_view), 2>; +// int* ptr = nullptr; +// auto f1 = MyFunction::make_function( +// [cls = &cls, ptr](std::string_view sv) { +// return cls->on_string(ptr, sv); +// }); +// int r = f1("abc"sv); +// +// // Returns a default-constructed int (0). +// f1 = ftl::no_op; +// r = f1("abc"sv); +// assert(r == 0); + +template <typename F, std::size_t N = 0> +class Function; + +// Used to construct a Function that does nothing. +struct NoOpTag {}; + +constexpr NoOpTag no_op; + +// Detects that a type is a `ftl::Function<F, N>` regardless of what `F` and `N` are. +template <typename> +struct is_function : public std::false_type {}; + +template <typename F, std::size_t N> +struct is_function<Function<F, N>> : public std::true_type {}; + +template <typename T> +constexpr bool is_function_v = is_function<T>::value; + +template <typename Ret, typename... Args, std::size_t N> +class Function<Ret(Args...), N> final { + // Enforce a valid size, with an arbitrary maximum allowed size for the container of + // sizeof(std::intptr_t) * 16, though that maximum can be relaxed. + static_assert(N <= details::kFunctionMaximumN); + + using OpaqueStorageTraits = details::function_opaque_storage<N>; + + public: + // Defining result_type allows ftl::Function to be substituted for std::function. + using result_type = Ret; + + // Constructs an empty ftl::Function. + Function() = default; + + // Constructing or assigning from nullptr_t also creates an empty ftl::Function. + Function(std::nullptr_t) {} + Function& operator=(std::nullptr_t) { return *this = Function(nullptr); } + + // Constructing from NoOpTag sets up a a special no-op function which is valid to call, and which + // returns a default constructed return value. + Function(NoOpTag) : function_(details::bind_opaque_no_op<Ret, Args...>()) {} + Function& operator=(NoOpTag) { return *this = Function(no_op); } + + // Constructing/assigning from a function object stores a copy of that function object, however: + // * It must be trivially copyable, as the implementation makes a copy with memcpy(). + // * It must be trivially destructible, as the implementation doesn't destroy the copy! + // * It must fit in the limited internal storage, which enforces size/alignment restrictions. + + template <typename F, typename = std::enable_if_t<std::is_invocable_r_v<Ret, F, Args...>>> + Function(const F& f) + : opaque_(OpaqueStorageTraits::opaque_copy(f)), + function_(details::bind_opaque_function_object<F, Ret, Args...>(f)) {} + + template <typename F, typename = std::enable_if_t<std::is_invocable_r_v<Ret, F, Args...>>> + Function& operator=(const F& f) noexcept { + return *this = Function{OpaqueStorageTraits::opaque_copy(f), + details::bind_opaque_function_object<F, Ret, Args...>(f)}; + } + + // Constructing/assigning from a smaller ftl::Function is allowed, but not anything else. + + template <std::size_t M> + Function(const Function<Ret(Args...), M>& other) + : opaque_{OpaqueStorageTraits::opaque_copy(other.opaque_)}, function_(other.function_) {} + + template <std::size_t M> + auto& operator=(const Function<Ret(Args...), M>& other) { + return *this = Function{OpaqueStorageTraits::opaque_copy(other.opaque_), other.function_}; + } + + // Returns true if a function is set. + explicit operator bool() const { return function_ != nullptr; } + + // Checks if the other function has the same contents as this one. + bool operator==(const Function& other) const { + return other.opaque_ == opaque_ && other.function_ == function_; + } + bool operator!=(const Function& other) const { return !operator==(other); } + + // Alternative way of testing for a function being set. + bool operator==(std::nullptr_t) const { return function_ == nullptr; } + bool operator!=(std::nullptr_t) const { return function_ != nullptr; } + + // Invokes the function. + Ret operator()(Args... args) const { + return std::invoke(function_, opaque_.data(), std::forward<Args>(args)...); + } + + // Creation helper for function objects, such as lambdas. + template <typename F> + static auto make(const F& f) -> decltype(Function{f}) { + return Function{f}; + } + + // Creation helper for a class pointer and a compile-time chosen member function to call. + template <auto MemberFunction, typename Class> + static auto make(Class* instance) -> decltype(Function{ + details::bind_member_function<MemberFunction>(instance, + static_cast<Ret (*)(Args...)>(nullptr))}) { + return Function{details::bind_member_function<MemberFunction>( + instance, static_cast<Ret (*)(Args...)>(nullptr))}; + } + + // Creation helper for a compile-time chosen free function to call. + template <auto FreeFunction> + static auto make() -> decltype(Function{ + details::bind_free_function<FreeFunction>(static_cast<Ret (*)(Args...)>(nullptr))}) { + return Function{ + details::bind_free_function<FreeFunction>(static_cast<Ret (*)(Args...)>(nullptr))}; + } + + private: + // Needed so a Function<F, M> can be converted to a Function<F, N>. + template <typename, std::size_t> + friend class Function; + + // The function pointer type of function stored in `function_`. The first argument is always + // `&opaque_`. + using StoredFunction = Ret(void*, Args...); + + // The type of the opaque storage, used to hold an appropriate function object. + // The type stored here is ONLY known to the StoredFunction. + // We always use at least one std::intptr_t worth of storage, and always a multiple of that size. + using OpaqueStorage = typename OpaqueStorageTraits::type; + + // Internal constructor for creating from a raw opaque blob + function pointer. + Function(const OpaqueStorage& opaque, StoredFunction* function) + : opaque_(opaque), function_(function) {} + + // Note: `mutable` so that `operator() const` can use it. + mutable OpaqueStorage opaque_{}; + StoredFunction* function_{nullptr}; +}; + +// Makes a ftl::Function given a function object `F`. +template <typename F, typename T = details::function_traits<F>> +Function(const F&) -> Function<typename T::type, T::size>; + +template <typename F> +auto make_function(const F& f) -> decltype(Function{f}) { + return Function{f}; +} + +// Makes a ftl::Function given a `MemberFunction` and a instance pointer to the associated `Class`. +template <auto MemberFunction, typename Class> +auto make_function(Class* instance) + -> decltype(Function{details::bind_member_function<MemberFunction>( + instance, + static_cast<details::remove_member_function_pointer_t<MemberFunction>*>(nullptr))}) { + return Function{details::bind_member_function<MemberFunction>( + instance, static_cast<details::remove_member_function_pointer_t<MemberFunction>*>(nullptr))}; +} + +// Makes a ftl::Function given an ordinary free function. +template <auto FreeFunction> +auto make_function() -> decltype(Function{ + details::bind_free_function<FreeFunction>(static_cast<decltype(FreeFunction)>(nullptr))}) { + return Function{ + details::bind_free_function<FreeFunction>(static_cast<decltype(FreeFunction)>(nullptr))}; +} + +} // namespace android::ftl |