1//===- FunctionExtras.h - Function type erasure utilities -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8/// \file
9/// This file provides a collection of function (or more generally, callable)
10/// type erasure utilities supplementing those provided by the standard library
11/// in `<function>`.
12///
13/// It provides `unique_function`, which works like `std::function` but supports
14/// move-only callable objects and const-qualification.
15///
16/// Future plans:
17/// - Add a `function` that provides ref-qualified support, which doesn't work
18/// with `std::function`.
19/// - Provide support for specifying multiple signatures to type erase callable
20/// objects with an overload set, such as those produced by generic lambdas.
21/// - Expand to include a copyable utility that directly replaces std::function
22/// but brings the above improvements.
23///
24/// Note that LLVM's utilities are greatly simplified by not supporting
25/// allocators.
26///
27/// If the standard library ever begins to provide comparable facilities we can
28/// consider switching to those.
29///
30//===----------------------------------------------------------------------===//
31
32#ifndef LLVM_ADT_FUNCTIONEXTRAS_H
33#define LLVM_ADT_FUNCTIONEXTRAS_H
34
35#include "llvm/ADT/PointerIntPair.h"
36#include "llvm/ADT/PointerUnion.h"
37#include "llvm/ADT/STLForwardCompat.h"
38#include "llvm/Support/MemAlloc.h"
39#include "llvm/Support/type_traits.h"
40#include <cstring>
41#include <type_traits>
42
43namespace llvm {
44
45/// unique_function is a type-erasing functor similar to std::function.
46///
47/// It can hold move-only function objects, like lambdas capturing unique_ptrs.
48/// Accordingly, it is movable but not copyable.
49///
50/// It supports const-qualification:
51/// - unique_function<int() const> has a const operator().
52/// It can only hold functions which themselves have a const operator().
53/// - unique_function<int()> has a non-const operator().
54/// It can hold functions with a non-const operator(), like mutable lambdas.
55template <typename FunctionT> class unique_function;
56
57namespace detail {
58
59template <typename CallableT, typename ThisT>
60using EnableUnlessSameType =
61 std::enable_if_t<!std::is_same<remove_cvref_t<CallableT>, ThisT>::value>;
62template <typename CallableT, typename Ret, typename... Params>
63using EnableIfCallable = std::enable_if_t<std::disjunction<
64 std::is_void<Ret>,
65 std::is_same<decltype(std::declval<CallableT>()(std::declval<Params>()...)),
66 Ret>,
67 std::is_same<const decltype(std::declval<CallableT>()(
68 std::declval<Params>()...)),
69 Ret>,
70 std::is_convertible<decltype(std::declval<CallableT>()(
71 std::declval<Params>()...)),
72 Ret>>::value>;
73
74template <typename ReturnT, typename... ParamTs> class UniqueFunctionBase {
75protected:
76 static constexpr size_t InlineStorageSize = sizeof(void *) * 3;
77 static constexpr size_t InlineStorageAlign = alignof(void *);
78
79 // Provide a type function to map parameters that won't observe extra copies
80 // or moves and which are small enough to likely pass in register to values
81 // and all other types to l-value reference types. We use this to compute the
82 // types used in our erased call utility to minimize copies and moves unless
83 // doing so would force things unnecessarily into memory.
84 //
85 // The heuristic used is related to common ABI register passing conventions.
86 // It doesn't have to be exact though, and in one way it is more strict
87 // because we want to still be able to observe either moves *or* copies.
88 template <typename T> struct AdjustedParamTBase {
89 static_assert(!std::is_reference<T>::value,
90 "references should be handled by template specialization");
91 static constexpr bool IsSizeLessThanThreshold =
92 sizeof(T) <= 2 * sizeof(void *);
93 using type =
94 std::conditional_t<std::is_trivially_copy_constructible<T>::value &&
95 std::is_trivially_move_constructible<T>::value &&
96 IsSizeLessThanThreshold,
97 T, T &>;
98 };
99
100 // This specialization ensures that 'AdjustedParam<V<T>&>' or
101 // 'AdjustedParam<V<T>&&>' does not trigger a compile-time error when 'T' is
102 // an incomplete type and V a templated type.
103 template <typename T> struct AdjustedParamTBase<T &> { using type = T &; };
104 template <typename T> struct AdjustedParamTBase<T &&> { using type = T &; };
105
106 template <typename T>
107 using AdjustedParamT = typename AdjustedParamTBase<T>::type;
108
109 // The type of the erased function pointer we use as a callback to dispatch to
110 // the stored callable when it is trivial to move and destroy.
111 using CallPtrT = ReturnT (*)(const UniqueFunctionBase *Self,
112 AdjustedParamT<ParamTs>... Params);
113 using DestroyMovePtrT = void (*)(UniqueFunctionBase *LHS,
114 UniqueFunctionBase *RHS);
115
116 // The main storage buffer. This will either have a pointer to out-of-line
117 // storage or an inline buffer storing the callable.
118 union StorageT {
119 // For out-of-line storage we keep a pointer to the underlying storage.
120 void *OutOfLine;
121 static_assert(
122 sizeof(OutOfLine) <= InlineStorageSize,
123 "Should always use all of the out-of-line storage for inline storage!");
124
125 // For in-line storage, we just provide an aligned character buffer. We
126 // provide three pointers worth of storage here.
127 // This is mutable as an inlined `const unique_function<void() const>` may
128 // still modify its own mutable members.
129 alignas(InlineStorageAlign) mutable std::byte Inline[InlineStorageSize];
130 } Storage;
131
132 CallPtrT CallPtr = nullptr;
133 DestroyMovePtrT DestroyMovePtr = nullptr;
134
135 // A simple tag type so the call-as type to be passed to the constructor.
136 template <typename T> struct CalledAs {};
137
138 // Essentially the "main" unique_function constructor, but subclasses
139 // provide the qualified type to be used for the call.
140 // (We always store a T, even if the call will use a pointer to const T).
141 template <typename CallableT, typename CalledAsT>
142 UniqueFunctionBase(CallableT Callable, CalledAs<CalledAsT>) {
143 // static as workaround an MSVC bug which treats constexpr uses as odr-uses.
144 static constexpr bool UsesInlineStorage =
145 sizeof(CallableT) <= InlineStorageSize &&
146 alignof(CallableT) <= InlineStorageAlign;
147 void *CallableAddr = &Storage.Inline;
148 if constexpr (!UsesInlineStorage) {
149 CallableAddr = allocate_buffer(Size: sizeof(CallableT), Alignment: alignof(CallableT));
150 Storage.OutOfLine = CallableAddr;
151 }
152
153 // Now move into the storage.
154 new (CallableAddr) CallableT(std::move(Callable));
155
156 CallPtr = [](const UniqueFunctionBase *Self,
157 AdjustedParamT<ParamTs>... Params) -> ReturnT {
158 void *CallableAddr =
159 UsesInlineStorage ? &Self->Storage.Inline : Self->Storage.OutOfLine;
160 auto &Func = *reinterpret_cast<CalledAsT *>(CallableAddr);
161 return Func(std::forward<ParamTs>(Params)...);
162 };
163
164 // For trivial inline storage, we don't need to do anything on move/destroy.
165 if constexpr (!std::is_trivially_move_constructible_v<CallableT> ||
166 !std::is_trivially_destructible_v<CallableT> ||
167 !UsesInlineStorage) {
168 // If LHS is set, move LHS callable to RHS, then destroy RHS callable.
169 DestroyMovePtr = [](UniqueFunctionBase *LHS, UniqueFunctionBase *RHS) {
170 if constexpr (!UsesInlineStorage) {
171 if (LHS) {
172 // Out-of-line move: just move the pointer.
173 LHS->Storage.OutOfLine = RHS->Storage.OutOfLine;
174 } else {
175 // Out-of-line destroy.
176 void *RHSCallableAddr = RHS->Storage.OutOfLine;
177 reinterpret_cast<CallableT *>(RHSCallableAddr)->~CallableT();
178 deallocate_buffer(Ptr: RHSCallableAddr, Size: sizeof(CallableT),
179 Alignment: alignof(CallableT));
180 }
181 } else {
182 auto *RHSCallable =
183 reinterpret_cast<CallableT *>(&RHS->Storage.Inline);
184 if (LHS) {
185 // Inline move: move-construct first...
186 auto *LHSCallable =
187 reinterpret_cast<CallableT *>(&LHS->Storage.Inline);
188 new (LHSCallable) CallableT(std::move(*RHSCallable));
189 }
190 // ... destroy RHS in any case.
191 RHSCallable->~CallableT();
192 }
193 };
194 }
195 }
196
197 ~UniqueFunctionBase() {
198 if (DestroyMovePtr)
199 DestroyMovePtr(nullptr, this);
200 }
201
202 UniqueFunctionBase(UniqueFunctionBase &&RHS) noexcept {
203 CallPtr = RHS.CallPtr;
204 DestroyMovePtr = RHS.DestroyMovePtr;
205 if (DestroyMovePtr)
206 DestroyMovePtr(this, &RHS);
207 else // Trivial callable stored inline => memcpy.
208 memcpy(&Storage.Inline, &RHS.Storage.Inline, InlineStorageSize);
209
210 RHS.CallPtr = nullptr;
211 RHS.DestroyMovePtr = nullptr; // Moved everything out of RHS.
212#ifndef NDEBUG
213 // In debug builds, we also scribble across the rest of the storage.
214 memset(RHS.Storage.Inline, 0xAD, InlineStorageSize);
215#endif
216 }
217
218 UniqueFunctionBase &operator=(UniqueFunctionBase &&RHS) noexcept {
219 if (this == &RHS)
220 return *this;
221
222 // Because we don't try to provide any exception safety guarantees we can
223 // implement move assignment very simply by first destroying the current
224 // object and then move-constructing over top of it.
225 this->~UniqueFunctionBase();
226 new (this) UniqueFunctionBase(std::move(RHS));
227 return *this;
228 }
229
230 UniqueFunctionBase() = default;
231
232public:
233 explicit operator bool() const { return (bool)CallPtr; }
234};
235
236} // namespace detail
237
238template <typename R, typename... P>
239class unique_function<R(P...)> : public detail::UniqueFunctionBase<R, P...> {
240 using Base = detail::UniqueFunctionBase<R, P...>;
241
242public:
243 unique_function() = default;
244 unique_function(std::nullptr_t) {}
245 unique_function(unique_function &&) = default;
246 unique_function(const unique_function &) = delete;
247 unique_function &operator=(unique_function &&) = default;
248 unique_function &operator=(const unique_function &) = delete;
249
250 template <typename CallableT>
251 unique_function(
252 CallableT Callable,
253 detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
254 detail::EnableIfCallable<CallableT, R, P...> * = nullptr)
255 : Base(std::forward<CallableT>(Callable),
256 typename Base::template CalledAs<CallableT>{}) {}
257
258 R operator()(P... Params) { return this->CallPtr(this, Params...); }
259};
260
261template <typename R, typename... P>
262class unique_function<R(P...) const>
263 : public detail::UniqueFunctionBase<R, P...> {
264 using Base = detail::UniqueFunctionBase<R, P...>;
265
266public:
267 unique_function() = default;
268 unique_function(std::nullptr_t) {}
269 unique_function(unique_function &&) = default;
270 unique_function(const unique_function &) = delete;
271 unique_function &operator=(unique_function &&) = default;
272 unique_function &operator=(const unique_function &) = delete;
273
274 template <typename CallableT>
275 unique_function(
276 CallableT Callable,
277 detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
278 detail::EnableIfCallable<const CallableT, R, P...> * = nullptr)
279 : Base(std::forward<CallableT>(Callable),
280 typename Base::template CalledAs<const CallableT>{}) {}
281
282 R operator()(P... Params) const { return this->CallPtr(this, Params...); }
283};
284
285} // end namespace llvm
286
287#endif // LLVM_ADT_FUNCTIONEXTRAS_H
288