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 1005 : 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 428 : static ReturnT CallImpl(void *CallableAddr,
218 : AdjustedParamT<ParamTs>... Params) {
219 428 : auto &Func = *reinterpret_cast<CalledAsT *>(CallableAddr);
220 428 : 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 1005 : UniqueFunctionBase(CallableT Callable, CalledAs<CalledAsT>) {
262 1005 : bool IsInlineStorage = true;
263 1005 : 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 1005 : new (CallableAddr) CallableT(std::move(Callable));
277 1005 : CallbackAndInlineFlag.setPointerAndInt(
278 : &CallbacksHolder<CallableT, CalledAsT>::Callbacks, IsInlineStorage);
279 1005 : }
280 :
281 1005 : ~UniqueFunctionBase() {
282 1005 : if (!CallbackAndInlineFlag.getPointer())
283 1005 : 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 1005 : }
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 1005 : unique_function(
377 : CallableT Callable,
378 : detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr,
379 : detail::EnableIfCallable<CallableT, R, P...> * = nullptr)
380 1005 : : Base(std::forward<CallableT>(Callable),
381 1005 : 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
|
