Branch data Line data Source code
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 : :
45 : : namespace 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.
57 : : template <typename FunctionT> class unique_function;
58 : :
59 : : namespace detail {
60 : :
61 : : template <typename T>
62 : : using EnableIfTrivial =
63 : : std::enable_if_t<std::is_trivially_move_constructible<T>::value &&
64 : : std::is_trivially_destructible<T>::value>;
65 : : template <typename CallableT, typename ThisT>
66 : : using EnableUnlessSameType =
67 : : std::enable_if_t<!std::is_same<remove_cvref_t<CallableT>, ThisT>::value>;
68 : : template <typename CallableT, typename Ret, typename... Params>
69 : : using 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 : :
80 : : template <typename ReturnT, typename... ParamTs> class UniqueFunctionBase {
81 : : protected:
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 : : alignas(void *) mutable std::byte InlineStorage[InlineStorageSize];
165 : : } StorageUnion;
166 : :
167 : : // A compressed pointer to either our dispatching callback or our table of
168 : : // dispatching callbacks and the flag for whether the callable itself is
169 : : // stored inline or not.
170 : : PointerIntPair<CallbackPointerUnionT, 1, bool> CallbackAndInlineFlag;
171 : :
172 : 0 : bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
173 : :
174 : 0 : bool isTrivialCallback() const {
175 [ # # # # ]: 0 : return isa<TrivialCallback *>(CallbackAndInlineFlag.getPointer());
176 : : }
177 : :
178 : : CallPtrT getTrivialCallback() const {
179 : : return cast<TrivialCallback *>(CallbackAndInlineFlag.getPointer())->CallPtr;
180 : : }
181 : :
182 : 0 : NonTrivialCallbacks *getNonTrivialCallbacks() const {
183 [ # # # # ]: 0 : return cast<NonTrivialCallbacks *>(CallbackAndInlineFlag.getPointer());
184 : : }
185 : :
186 : : CallPtrT getCallPtr() const {
187 : : return isTrivialCallback() ? getTrivialCallback()
188 : : : getNonTrivialCallbacks()->CallPtr;
189 : : }
190 : :
191 : : // These three functions are only const in the narrow sense. They return
192 : : // mutable pointers to function state.
193 : : // This allows unique_function<T const>::operator() to be const, even if the
194 : : // underlying functor may be internally mutable.
195 : : //
196 : : // const callers must ensure they're only used in const-correct ways.
197 : : void *getCalleePtr() const {
198 : : return isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
199 : : }
200 : 0 : void *getInlineStorage() const { return &StorageUnion.InlineStorage; }
201 : 0 : void *getOutOfLineStorage() const {
202 : 0 : return StorageUnion.OutOfLineStorage.StoragePtr;
203 : : }
204 : :
205 : 0 : size_t getOutOfLineStorageSize() const {
206 : 0 : return StorageUnion.OutOfLineStorage.Size;
207 : : }
208 : 0 : size_t getOutOfLineStorageAlignment() const {
209 : 0 : return StorageUnion.OutOfLineStorage.Alignment;
210 : : }
211 : :
212 : : void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
213 : : StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
214 : : }
215 : :
216 : : template <typename CalledAsT>
217 : 0 : static ReturnT CallImpl(void *CallableAddr,
218 : : AdjustedParamT<ParamTs>... Params) {
219 : 0 : auto &Func = *reinterpret_cast<CalledAsT *>(CallableAddr);
220 : 0 : return Func(std::forward<ParamTs>(Params)...);
221 : : }
222 : :
223 : : template <typename CallableT>
224 : : static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
225 : : new (LHSCallableAddr)
226 : : CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
227 : : }
228 : :
229 : : template <typename CallableT>
230 : : static void DestroyImpl(void *CallableAddr) noexcept {
231 : : reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
232 : : }
233 : :
234 : : // The pointers to call/move/destroy functions are determined for each
235 : : // callable type (and called-as type, which determines the overload chosen).
236 : : // (definitions are out-of-line).
237 : :
238 : : // By default, we need an object that contains all the different
239 : : // type erased behaviors needed. Create a static instance of the struct type
240 : : // here and each instance will contain a pointer to it.
241 : : // Wrap in a struct to avoid https://gcc.gnu.org/PR71954
242 : : template <typename CallableT, typename CalledAs, typename Enable = void>
243 : : struct CallbacksHolder {
244 : : static NonTrivialCallbacks Callbacks;
245 : : };
246 : : // See if we can create a trivial callback. We need the callable to be
247 : : // trivially moved and trivially destroyed so that we don't have to store
248 : : // type erased callbacks for those operations.
249 : : template <typename CallableT, typename CalledAs>
250 : : struct CallbacksHolder<CallableT, CalledAs, EnableIfTrivial<CallableT>> {
251 : : static TrivialCallback Callbacks;
252 : : };
253 : :
254 : : // A simple tag type so the call-as type to be passed to the constructor.
255 : : template <typename T> struct CalledAs {};
256 : :
257 : : // Essentially the "main" unique_function constructor, but subclasses
258 : : // provide the qualified type to be used for the call.
259 : : // (We always store a T, even if the call will use a pointer to const T).
260 : : template <typename CallableT, typename CalledAsT>
261 : 0 : UniqueFunctionBase(CallableT Callable, CalledAs<CalledAsT>) {
262 : 0 : bool IsInlineStorage = true;
263 : 0 : void *CallableAddr = getInlineStorage();
264 : : if (sizeof(CallableT) > InlineStorageSize ||
265 : : alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
266 : : IsInlineStorage = false;
267 : : // Allocate out-of-line storage. FIXME: Use an explicit alignment
268 : : // parameter in C++17 mode.
269 : : auto Size = sizeof(CallableT);
270 : : auto Alignment = alignof(CallableT);
271 : : CallableAddr = allocate_buffer(Size, Alignment);
272 : : setOutOfLineStorage(CallableAddr, Size, Alignment);
273 : : }
274 : :
275 : : // Now move into the storage.
276 [ # # ]: 0 : new (CallableAddr) CallableT(std::move(Callable));
277 [ # # # # ]: 0 : CallbackAndInlineFlag.setPointerAndInt(
278 : : &CallbacksHolder<CallableT, CalledAsT>::Callbacks, IsInlineStorage);
279 : 0 : }
280 : :
281 : 0 : ~UniqueFunctionBase() {
282 [ # # ]: 0 : if (!CallbackAndInlineFlag.getPointer())
283 : 0 : return;
284 : :
285 : : // Cache this value so we don't re-check it after type-erased operations.
286 : 0 : bool IsInlineStorage = isInlineStorage();
287 : :
288 [ # # ]: 0 : if (!isTrivialCallback())
289 [ # # ]: 0 : getNonTrivialCallbacks()->DestroyPtr(
290 : 0 : IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
291 : :
292 [ # # ]: 0 : if (!IsInlineStorage)
293 : 0 : deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
294 : : getOutOfLineStorageAlignment());
295 : 0 : }
296 : :
297 : : UniqueFunctionBase(UniqueFunctionBase &&RHS) noexcept {
298 : : // Copy the callback and inline flag.
299 : : CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
300 : :
301 : : // If the RHS is empty, just copying the above is sufficient.
302 : : if (!RHS)
303 : : return;
304 : :
305 : : if (!isInlineStorage()) {
306 : : // The out-of-line case is easiest to move.
307 : : StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
308 : : } else if (isTrivialCallback()) {
309 : : // Move is trivial, just memcpy the bytes across.
310 : : memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
311 : : } else {
312 : : // Non-trivial move, so dispatch to a type-erased implementation.
313 : : getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
314 : : RHS.getInlineStorage());
315 : : }
316 : :
317 : : // Clear the old callback and inline flag to get back to as-if-null.
318 : : RHS.CallbackAndInlineFlag = {};
319 : :
320 : : #if !defined(NDEBUG) && !LLVM_ADDRESS_SANITIZER_BUILD
321 : : // In debug builds without ASan, we also scribble across the rest of the
322 : : // storage. Scribbling under AddressSanitizer (ASan) is disabled to prevent
323 : : // overwriting poisoned objects (e.g., annotated short strings).
324 : : memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
325 : : #endif
326 : : }
327 : :
328 : : UniqueFunctionBase &operator=(UniqueFunctionBase &&RHS) noexcept {
329 : : if (this == &RHS)
330 : : return *this;
331 : :
332 : : // Because we don't try to provide any exception safety guarantees we can
333 : : // implement move assignment very simply by first destroying the current
334 : : // object and then move-constructing over top of it.
335 : : this->~UniqueFunctionBase();
336 : : new (this) UniqueFunctionBase(std::move(RHS));
337 : : return *this;
338 : : }
339 : :
340 : : UniqueFunctionBase() = default;
341 : :
342 : : public:
343 : : explicit operator bool() const {
344 : : return (bool)CallbackAndInlineFlag.getPointer();
345 : : }
346 : : };
347 : :
348 : : template <typename R, typename... P>
349 : : template <typename CallableT, typename CalledAsT, typename Enable>
350 : : typename UniqueFunctionBase<R, P...>::NonTrivialCallbacks UniqueFunctionBase<
351 : : R, P...>::CallbacksHolder<CallableT, CalledAsT, Enable>::Callbacks = {
352 : : &CallImpl<CalledAsT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
353 : :
354 : : template <typename R, typename... P>
355 : : template <typename CallableT, typename CalledAsT>
356 : : typename UniqueFunctionBase<R, P...>::TrivialCallback
357 : : UniqueFunctionBase<R, P...>::CallbacksHolder<
358 : : CallableT, CalledAsT, EnableIfTrivial<CallableT>>::Callbacks{
359 : : &CallImpl<CalledAsT>};
360 : :
361 : : } // namespace detail
362 : :
363 : : template <typename R, typename... P>
364 : : class unique_function<R(P...)> : public detail::UniqueFunctionBase<R, P...> {
365 : : using Base = detail::UniqueFunctionBase<R, P...>;
366 : :
367 : : public:
368 : : unique_function() = default;
369 : : unique_function(std::nullptr_t) {}
370 : : unique_function(unique_function &&) = default;
371 : : unique_function(const unique_function &) = delete;
372 : : unique_function &operator=(unique_function &&) = default;
373 : : unique_function &operator=(const unique_function &) = delete;
374 : :
375 : : template <typename CallableT>
376 : 0 : unique_function(
377 : : CallableT Callable,
378 : : detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
379 : : detail::EnableIfCallable<CallableT, R, P...> * = nullptr)
380 : 0 : : Base(std::forward<CallableT>(Callable),
381 : 0 : typename Base::template CalledAs<CallableT>{}) {}
382 : :
383 : : R operator()(P... Params) {
384 : : return this->getCallPtr()(this->getCalleePtr(), Params...);
385 : : }
386 : : };
387 : :
388 : : template <typename R, typename... P>
389 : : class unique_function<R(P...) const>
390 : : : public detail::UniqueFunctionBase<R, P...> {
391 : : using Base = detail::UniqueFunctionBase<R, P...>;
392 : :
393 : : public:
394 : : unique_function() = default;
395 : : unique_function(std::nullptr_t) {}
396 : : unique_function(unique_function &&) = default;
397 : : unique_function(const unique_function &) = delete;
398 : : unique_function &operator=(unique_function &&) = default;
399 : : unique_function &operator=(const unique_function &) = delete;
400 : :
401 : : template <typename CallableT>
402 : : unique_function(
403 : : CallableT Callable,
404 : : detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
405 : : detail::EnableIfCallable<const CallableT, R, P...> * = nullptr)
406 : : : Base(std::forward<CallableT>(Callable),
407 : : typename Base::template CalledAs<const CallableT>{}) {}
408 : :
409 : : R operator()(P... Params) const {
410 : : return this->getCallPtr()(this->getCalleePtr(), Params...);
411 : : }
412 : : };
413 : :
414 : : } // end namespace llvm
415 : :
416 : : #endif // LLVM_ADT_FUNCTIONEXTRAS_H
|
