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