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 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(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 343 public: 344 explicit operator bool() const { 345 return (bool)CallbackAndInlineFlag.getPointer(); 346 } 347 }; 348 349 template <typename R, typename... P> 350 template <typename CallableT, typename CalledAsT, typename Enable> 351 typename UniqueFunctionBase<R, P...>::NonTrivialCallbacks UniqueFunctionBase< 352 R, P...>::CallbacksHolder<CallableT, CalledAsT, Enable>::Callbacks = { 353 &CallImpl<CalledAsT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>}; 354 355 template <typename R, typename... P> 356 template <typename CallableT, typename CalledAsT> 357 typename UniqueFunctionBase<R, P...>::TrivialCallback 358 UniqueFunctionBase<R, P...>::CallbacksHolder< 359 CallableT, CalledAsT, EnableIfTrivial<CallableT>>::Callbacks{ 360 &CallImpl<CalledAsT>}; 361 362 } // namespace detail 363 364 template <typename R, typename... P> 365 class unique_function<R(P...)> : public detail::UniqueFunctionBase<R, P...> { 366 using Base = detail::UniqueFunctionBase<R, P...>; 367 368 public: 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 389 template <typename R, typename... P> 390 class unique_function<R(P...) const> 391 : public detail::UniqueFunctionBase<R, P...> { 392 using Base = detail::UniqueFunctionBase<R, P...>; 393 394 public: 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