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/Compiler.h"
39#include "llvm/Support/MemAlloc.h"
40#include "llvm/Support/type_traits.h"
41#include <cstring>
42#include <memory>
43#include <type_traits>
44
45namespace llvm {
46
47/// unique_function is a type-erasing functor similar to std::function.
48///
49/// It can hold move-only function objects, like lambdas capturing unique_ptrs.
50/// Accordingly, it is movable but not copyable.
51///
52/// It supports const-qualification:
53/// - unique_function<int() const> has a const operator().
54/// It can only hold functions which themselves have a const operator().
55/// - unique_function<int()> has a non-const operator().
56/// It can hold functions with a non-const operator(), like mutable lambdas.
57template <typename FunctionT> class unique_function;
58
59namespace detail {
60
61template <typename T>
62using EnableIfTrivial =
63 std::enable_if_t<std::is_trivially_move_constructible<T>::value &&
64 std::is_trivially_destructible<T>::value>;
65template <typename CallableT, typename ThisT>
66using EnableUnlessSameType =
67 std::enable_if_t<!std::is_same<remove_cvref_t<CallableT>, ThisT>::value>;
68template <typename CallableT, typename Ret, typename... Params>
69using EnableIfCallable = std::enable_if_t<std::disjunction<
70 std::is_void<Ret>,
71 std::is_same<decltype(std::declval<CallableT>()(std::declval<Params>()...)),
72 Ret>,
73 std::is_same<const decltype(std::declval<CallableT>()(
74 std::declval<Params>()...)),
75 Ret>,
76 std::is_convertible<decltype(std::declval<CallableT>()(
77 std::declval<Params>()...)),
78 Ret>>::value>;
79
80template <typename ReturnT, typename... ParamTs> class UniqueFunctionBase {
81protected:
82 static constexpr size_t InlineStorageSize = sizeof(void *) * 3;
83
84 template <typename T, class = void>
85 struct IsSizeLessThanThresholdT : std::false_type {};
86
87 template <typename T>
88 struct IsSizeLessThanThresholdT<
89 T, std::enable_if_t<sizeof(T) <= 2 * sizeof(void *)>> : std::true_type {};
90
91 // Provide a type function to map parameters that won't observe extra copies
92 // or moves and which are small enough to likely pass in register to values
93 // and all other types to l-value reference types. We use this to compute the
94 // types used in our erased call utility to minimize copies and moves unless
95 // doing so would force things unnecessarily into memory.
96 //
97 // The heuristic used is related to common ABI register passing conventions.
98 // It doesn't have to be exact though, and in one way it is more strict
99 // because we want to still be able to observe either moves *or* copies.
100 template <typename T> struct AdjustedParamTBase {
101 static_assert(!std::is_reference<T>::value,
102 "references should be handled by template specialization");
103 using type =
104 std::conditional_t<std::is_trivially_copy_constructible<T>::value &&
105 std::is_trivially_move_constructible<T>::value &&
106 IsSizeLessThanThresholdT<T>::value,
107 T, T &>;
108 };
109
110 // This specialization ensures that 'AdjustedParam<V<T>&>' or
111 // 'AdjustedParam<V<T>&&>' does not trigger a compile-time error when 'T' is
112 // an incomplete type and V a templated type.
113 template <typename T> struct AdjustedParamTBase<T &> { using type = T &; };
114 template <typename T> struct AdjustedParamTBase<T &&> { using type = T &; };
115
116 template <typename T>
117 using AdjustedParamT = typename AdjustedParamTBase<T>::type;
118
119 // The type of the erased function pointer we use as a callback to dispatch to
120 // the stored callable when it is trivial to move and destroy.
121 using CallPtrT = ReturnT (*)(void *CallableAddr,
122 AdjustedParamT<ParamTs>... Params);
123 using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr);
124 using DestroyPtrT = void (*)(void *CallableAddr);
125
126 /// A struct to hold a single trivial callback with sufficient alignment for
127 /// our bitpacking.
128 struct alignas(8) TrivialCallback {
129 CallPtrT CallPtr;
130 };
131
132 /// A struct we use to aggregate three callbacks when we need full set of
133 /// operations.
134 struct alignas(8) NonTrivialCallbacks {
135 CallPtrT CallPtr;
136 MovePtrT MovePtr;
137 DestroyPtrT DestroyPtr;
138 };
139
140 // Create a pointer union between either a pointer to a static trivial call
141 // pointer in a struct or a pointer to a static struct of the call, move, and
142 // destroy pointers.
143 using CallbackPointerUnionT =
144 PointerUnion<TrivialCallback *, NonTrivialCallbacks *>;
145
146 // The main storage buffer. This will either have a pointer to out-of-line
147 // storage or an inline buffer storing the callable.
148 union StorageUnionT {
149 // For out-of-line storage we keep a pointer to the underlying storage and
150 // the size. This is enough to deallocate the memory.
151 struct OutOfLineStorageT {
152 void *StoragePtr;
153 size_t Size;
154 size_t Alignment;
155 } OutOfLineStorage;
156 static_assert(
157 sizeof(OutOfLineStorageT) <= InlineStorageSize,
158 "Should always use all of the out-of-line storage for inline storage!");
159
160 // For in-line storage, we just provide an aligned character buffer. We
161 // provide three pointers worth of storage here.
162 // This is mutable as an inlined `const unique_function<void() const>` may
163 // still modify its own mutable members.
164 mutable std::aligned_storage_t<InlineStorageSize, alignof(void *)>
165 InlineStorage;
166 } StorageUnion;
167
168 // A compressed pointer to either our dispatching callback or our table of
169 // dispatching callbacks and the flag for whether the callable itself is
170 // stored inline or not.
171 PointerIntPair<CallbackPointerUnionT, 1, bool> CallbackAndInlineFlag;
172
173 bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
174
175 bool isTrivialCallback() const {
176 return isa<TrivialCallback *>(CallbackAndInlineFlag.getPointer());
177 }
178
179 CallPtrT getTrivialCallback() const {
180 return cast<TrivialCallback *>(CallbackAndInlineFlag.getPointer())->CallPtr;
181 }
182
183 NonTrivialCallbacks *getNonTrivialCallbacks() const {
184 return cast<NonTrivialCallbacks *>(CallbackAndInlineFlag.getPointer());
185 }
186
187 CallPtrT getCallPtr() const {
188 return isTrivialCallback() ? getTrivialCallback()
189 : getNonTrivialCallbacks()->CallPtr;
190 }
191
192 // These three functions are only const in the narrow sense. They return
193 // mutable pointers to function state.
194 // This allows unique_function<T const>::operator() to be const, even if the
195 // underlying functor may be internally mutable.
196 //
197 // const callers must ensure they're only used in const-correct ways.
198 void *getCalleePtr() const {
199 return isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
200 }
201 void *getInlineStorage() const { return &StorageUnion.InlineStorage; }
202 void *getOutOfLineStorage() const {
203 return StorageUnion.OutOfLineStorage.StoragePtr;
204 }
205
206 size_t getOutOfLineStorageSize() const {
207 return StorageUnion.OutOfLineStorage.Size;
208 }
209 size_t getOutOfLineStorageAlignment() const {
210 return StorageUnion.OutOfLineStorage.Alignment;
211 }
212
213 void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
214 StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
215 }
216
217 template <typename CalledAsT>
218 static ReturnT CallImpl(void *CallableAddr,
219 AdjustedParamT<ParamTs>... Params) {
220 auto &Func = *reinterpret_cast<CalledAsT *>(CallableAddr);
221 return Func(std::forward<ParamTs>(Params)...);
222 }
223
224 template <typename CallableT>
225 static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
226 new (LHSCallableAddr)
227 CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
228 }
229
230 template <typename CallableT>
231 static void DestroyImpl(void *CallableAddr) noexcept {
232 reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
233 }
234
235 // The pointers to call/move/destroy functions are determined for each
236 // callable type (and called-as type, which determines the overload chosen).
237 // (definitions are out-of-line).
238
239 // By default, we need an object that contains all the different
240 // type erased behaviors needed. Create a static instance of the struct type
241 // here and each instance will contain a pointer to it.
242 // Wrap in a struct to avoid https://gcc.gnu.org/PR71954
243 template <typename CallableT, typename CalledAs, typename Enable = void>
244 struct CallbacksHolder {
245 static NonTrivialCallbacks Callbacks;
246 };
247 // See if we can create a trivial callback. We need the callable to be
248 // trivially moved and trivially destroyed so that we don't have to store
249 // type erased callbacks for those operations.
250 template <typename CallableT, typename CalledAs>
251 struct CallbacksHolder<CallableT, CalledAs, EnableIfTrivial<CallableT>> {
252 static TrivialCallback Callbacks;
253 };
254
255 // A simple tag type so the call-as type to be passed to the constructor.
256 template <typename T> struct CalledAs {};
257
258 // Essentially the "main" unique_function constructor, but subclasses
259 // provide the qualified type to be used for the call.
260 // (We always store a T, even if the call will use a pointer to const T).
261 template <typename CallableT, typename CalledAsT>
262 UniqueFunctionBase(CallableT Callable, CalledAs<CalledAsT>) {
263 bool IsInlineStorage = true;
264 void *CallableAddr = getInlineStorage();
265 if (sizeof(CallableT) > InlineStorageSize ||
266 alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
267 IsInlineStorage = false;
268 // Allocate out-of-line storage. FIXME: Use an explicit alignment
269 // parameter in C++17 mode.
270 auto Size = sizeof(CallableT);
271 auto Alignment = alignof(CallableT);
272 CallableAddr = allocate_buffer(Size, Alignment);
273 setOutOfLineStorage(Ptr: CallableAddr, Size, Alignment);
274 }
275
276 // Now move into the storage.
277 new (CallableAddr) CallableT(std::move(Callable));
278 CallbackAndInlineFlag.setPointerAndInt(
279 &CallbacksHolder<CallableT, CalledAsT>::Callbacks, IsInlineStorage);
280 }
281
282 ~UniqueFunctionBase() {
283 if (!CallbackAndInlineFlag.getPointer())
284 return;
285
286 // Cache this value so we don't re-check it after type-erased operations.
287 bool IsInlineStorage = isInlineStorage();
288
289 if (!isTrivialCallback())
290 getNonTrivialCallbacks()->DestroyPtr(
291 IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
292
293 if (!IsInlineStorage)
294 deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
295 getOutOfLineStorageAlignment());
296 }
297
298 UniqueFunctionBase(UniqueFunctionBase &&RHS) noexcept {
299 // Copy the callback and inline flag.
300 CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
301
302 // If the RHS is empty, just copying the above is sufficient.
303 if (!RHS)
304 return;
305
306 if (!isInlineStorage()) {
307 // The out-of-line case is easiest to move.
308 StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
309 } else if (isTrivialCallback()) {
310 // Move is trivial, just memcpy the bytes across.
311 memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
312 } else {
313 // Non-trivial move, so dispatch to a type-erased implementation.
314 getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
315 RHS.getInlineStorage());
316 }
317
318 // Clear the old callback and inline flag to get back to as-if-null.
319 RHS.CallbackAndInlineFlag = {};
320
321#if !defined(NDEBUG) && !LLVM_ADDRESS_SANITIZER_BUILD
322 // In debug builds without ASan, we also scribble across the rest of the
323 // storage. Scribbling under AddressSanitizer (ASan) is disabled to prevent
324 // overwriting poisoned objects (e.g., annotated short strings).
325 memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
326#endif
327 }
328
329 UniqueFunctionBase &operator=(UniqueFunctionBase &&RHS) noexcept {
330 if (this == &RHS)
331 return *this;
332
333 // Because we don't try to provide any exception safety guarantees we can
334 // implement move assignment very simply by first destroying the current
335 // object and then move-constructing over top of it.
336 this->~UniqueFunctionBase();
337 new (this) UniqueFunctionBase(std::move(RHS));
338 return *this;
339 }
340
341 UniqueFunctionBase() = default;
342
343public:
344 explicit operator bool() const {
345 return (bool)CallbackAndInlineFlag.getPointer();
346 }
347};
348
349template <typename R, typename... P>
350template <typename CallableT, typename CalledAsT, typename Enable>
351typename UniqueFunctionBase<R, P...>::NonTrivialCallbacks UniqueFunctionBase<
352 R, P...>::CallbacksHolder<CallableT, CalledAsT, Enable>::Callbacks = {
353 &CallImpl<CalledAsT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
354
355template <typename R, typename... P>
356template <typename CallableT, typename CalledAsT>
357typename UniqueFunctionBase<R, P...>::TrivialCallback
358 UniqueFunctionBase<R, P...>::CallbacksHolder<
359 CallableT, CalledAsT, EnableIfTrivial<CallableT>>::Callbacks{
360 &CallImpl<CalledAsT>};
361
362} // namespace detail
363
364template <typename R, typename... P>
365class unique_function<R(P...)> : public detail::UniqueFunctionBase<R, P...> {
366 using Base = detail::UniqueFunctionBase<R, P...>;
367
368public:
369 unique_function() = default;
370 unique_function(std::nullptr_t) {}
371 unique_function(unique_function &&) = default;
372 unique_function(const unique_function &) = delete;
373 unique_function &operator=(unique_function &&) = default;
374 unique_function &operator=(const unique_function &) = delete;
375
376 template <typename CallableT>
377 unique_function(
378 CallableT Callable,
379 detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
380 detail::EnableIfCallable<CallableT, R, P...> * = nullptr)
381 : Base(std::forward<CallableT>(Callable),
382 typename Base::template CalledAs<CallableT>{}) {}
383
384 R operator()(P... Params) {
385 return this->getCallPtr()(this->getCalleePtr(), Params...);
386 }
387};
388
389template <typename R, typename... P>
390class unique_function<R(P...) const>
391 : public detail::UniqueFunctionBase<R, P...> {
392 using Base = detail::UniqueFunctionBase<R, P...>;
393
394public:
395 unique_function() = default;
396 unique_function(std::nullptr_t) {}
397 unique_function(unique_function &&) = default;
398 unique_function(const unique_function &) = delete;
399 unique_function &operator=(unique_function &&) = default;
400 unique_function &operator=(const unique_function &) = delete;
401
402 template <typename CallableT>
403 unique_function(
404 CallableT Callable,
405 detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
406 detail::EnableIfCallable<const CallableT, R, P...> * = nullptr)
407 : Base(std::forward<CallableT>(Callable),
408 typename Base::template CalledAs<const CallableT>{}) {}
409
410 R operator()(P... Params) const {
411 return this->getCallPtr()(this->getCalleePtr(), Params...);
412 }
413};
414
415} // end namespace llvm
416
417#endif // LLVM_ADT_FUNCTIONEXTRAS_H
418

source code of llvm/include/llvm/ADT/FunctionExtras.h