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/MemAlloc.h" 39 #include "llvm/Support/type_traits.h" 40 #include <cstring> 41 #include <memory> 42 #include <type_traits> 43 44 namespace llvm { 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. 56 template <typename FunctionT> class unique_function; 57 58 namespace detail { 59 60 template <typename T> 61 using EnableIfTrivial = 62 std::enable_if_t<llvm::is_trivially_move_constructible<T>::value && 63 std::is_trivially_destructible<T>::value>; 64 template <typename CallableT, typename ThisT> 65 using EnableUnlessSameType = 66 std::enable_if_t<!std::is_same<remove_cvref_t<CallableT>, ThisT>::value>; 67 template <typename CallableT, typename Ret, typename... Params> 68 using EnableIfCallable = std::enable_if_t<llvm::disjunction< 69 std::is_void<Ret>, 70 std::is_same<decltype(std::declval<CallableT>()(std::declval<Params>()...)), 71 Ret>, 72 std::is_same<const decltype(std::declval<CallableT>()( 73 std::declval<Params>()...)), 74 Ret>, 75 std::is_convertible<decltype(std::declval<CallableT>()( 76 std::declval<Params>()...)), 77 Ret>>::value>; 78 79 template <typename ReturnT, typename... ParamTs> class UniqueFunctionBase { 80 protected: 81 static constexpr size_t InlineStorageSize = sizeof(void *) * 3; 82 83 template <typename T, class = void> 84 struct IsSizeLessThanThresholdT : std::false_type {}; 85 86 template <typename T> 87 struct IsSizeLessThanThresholdT< 88 T, std::enable_if_t<sizeof(T) <= 2 * sizeof(void *)>> : std::true_type {}; 89 90 // Provide a type function to map parameters that won't observe extra copies 91 // or moves and which are small enough to likely pass in register to values 92 // and all other types to l-value reference types. We use this to compute the 93 // types used in our erased call utility to minimize copies and moves unless 94 // doing so would force things unnecessarily into memory. 95 // 96 // The heuristic used is related to common ABI register passing conventions. 97 // It doesn't have to be exact though, and in one way it is more strict 98 // because we want to still be able to observe either moves *or* copies. 99 template <typename T> struct AdjustedParamTBase { 100 static_assert(!std::is_reference<T>::value, 101 "references should be handled by template specialization"); 102 using type = typename std::conditional< 103 llvm::is_trivially_copy_constructible<T>::value && 104 llvm::is_trivially_move_constructible<T>::value && 105 IsSizeLessThanThresholdT<T>::value, 106 T, T &>::type; 107 }; 108 109 // This specialization ensures that 'AdjustedParam<V<T>&>' or 110 // 'AdjustedParam<V<T>&&>' does not trigger a compile-time error when 'T' is 111 // an incomplete type and V a templated type. 112 template <typename T> struct AdjustedParamTBase<T &> { using type = T &; }; 113 template <typename T> struct AdjustedParamTBase<T &&> { using type = T &; }; 114 115 template <typename T> 116 using AdjustedParamT = typename AdjustedParamTBase<T>::type; 117 118 // The type of the erased function pointer we use as a callback to dispatch to 119 // the stored callable when it is trivial to move and destroy. 120 using CallPtrT = ReturnT (*)(void *CallableAddr, 121 AdjustedParamT<ParamTs>... Params); 122 using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr); 123 using DestroyPtrT = void (*)(void *CallableAddr); 124 125 /// A struct to hold a single trivial callback with sufficient alignment for 126 /// our bitpacking. 127 struct alignas(8) TrivialCallback { 128 CallPtrT CallPtr; 129 }; 130 131 /// A struct we use to aggregate three callbacks when we need full set of 132 /// operations. 133 struct alignas(8) NonTrivialCallbacks { 134 CallPtrT CallPtr; 135 MovePtrT MovePtr; 136 DestroyPtrT DestroyPtr; 137 }; 138 139 // Create a pointer union between either a pointer to a static trivial call 140 // pointer in a struct or a pointer to a static struct of the call, move, and 141 // destroy pointers. 142 using CallbackPointerUnionT = 143 PointerUnion<TrivialCallback *, NonTrivialCallbacks *>; 144 145 // The main storage buffer. This will either have a pointer to out-of-line 146 // storage or an inline buffer storing the callable. 147 union StorageUnionT { 148 // For out-of-line storage we keep a pointer to the underlying storage and 149 // the size. This is enough to deallocate the memory. 150 struct OutOfLineStorageT { 151 void *StoragePtr; 152 size_t Size; 153 size_t Alignment; 154 } OutOfLineStorage; 155 static_assert( 156 sizeof(OutOfLineStorageT) <= InlineStorageSize, 157 "Should always use all of the out-of-line storage for inline storage!"); 158 159 // For in-line storage, we just provide an aligned character buffer. We 160 // provide three pointers worth of storage here. 161 // This is mutable as an inlined `const unique_function<void() const>` may 162 // still modify its own mutable members. 163 mutable 164 typename std::aligned_storage<InlineStorageSize, alignof(void *)>::type 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 CallbackAndInlineFlag.getPointer().template is<TrivialCallback *>(); 177 } 178 179 CallPtrT getTrivialCallback() const { 180 return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr; 181 } 182 183 NonTrivialCallbacks *getNonTrivialCallbacks() const { 184 return CallbackAndInlineFlag.getPointer() 185 .template get<NonTrivialCallbacks *>(); 186 } 187 188 CallPtrT getCallPtr() const { 189 return isTrivialCallback() ? getTrivialCallback() 190 : getNonTrivialCallbacks()->CallPtr; 191 } 192 193 // These three functions are only const in the narrow sense. They return 194 // mutable pointers to function state. 195 // This allows unique_function<T const>::operator() to be const, even if the 196 // underlying functor may be internally mutable. 197 // 198 // const callers must ensure they're only used in const-correct ways. 199 void *getCalleePtr() const { 200 return isInlineStorage() ? getInlineStorage() : getOutOfLineStorage(); 201 } 202 void *getInlineStorage() const { return &StorageUnion.InlineStorage; } 203 void *getOutOfLineStorage() const { 204 return StorageUnion.OutOfLineStorage.StoragePtr; 205 } 206 207 size_t getOutOfLineStorageSize() const { 208 return StorageUnion.OutOfLineStorage.Size; 209 } 210 size_t getOutOfLineStorageAlignment() const { 211 return StorageUnion.OutOfLineStorage.Alignment; 212 } 213 214 void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) { 215 StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment}; 216 } 217 218 template <typename CalledAsT> 219 static ReturnT CallImpl(void *CallableAddr, 220 AdjustedParamT<ParamTs>... Params) { 221 auto &Func = *reinterpret_cast<CalledAsT *>(CallableAddr); 222 return Func(std::forward<ParamTs>(Params)...); 223 } 224 225 template <typename CallableT> 226 static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept { 227 new (LHSCallableAddr) 228 CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr))); 229 } 230 231 template <typename CallableT> 232 static void DestroyImpl(void *CallableAddr) noexcept { 233 reinterpret_cast<CallableT *>(CallableAddr)->~CallableT(); 234 } 235 236 // The pointers to call/move/destroy functions are determined for each 237 // callable type (and called-as type, which determines the overload chosen). 238 // (definitions are out-of-line). 239 240 // By default, we need an object that contains all the different 241 // type erased behaviors needed. Create a static instance of the struct type 242 // here and each instance will contain a pointer to it. 243 // Wrap in a struct to avoid https://gcc.gnu.org/PR71954 244 template <typename CallableT, typename CalledAs, typename Enable = void> 245 struct CallbacksHolder { 246 static NonTrivialCallbacks Callbacks; 247 }; 248 // See if we can create a trivial callback. We need the callable to be 249 // trivially moved and trivially destroyed so that we don't have to store 250 // type erased callbacks for those operations. 251 template <typename CallableT, typename CalledAs> 252 struct CallbacksHolder<CallableT, CalledAs, EnableIfTrivial<CallableT>> { 253 static TrivialCallback Callbacks; 254 }; 255 256 // A simple tag type so the call-as type to be passed to the constructor. 257 template <typename T> struct CalledAs {}; 258 259 // Essentially the "main" unique_function constructor, but subclasses 260 // provide the qualified type to be used for the call. 261 // (We always store a T, even if the call will use a pointer to const T). 262 template <typename CallableT, typename CalledAsT> 263 UniqueFunctionBase(CallableT Callable, CalledAs<CalledAsT>) { 264 bool IsInlineStorage = true; 265 void *CallableAddr = getInlineStorage(); 266 if (sizeof(CallableT) > InlineStorageSize || 267 alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) { 268 IsInlineStorage = false; 269 // Allocate out-of-line storage. FIXME: Use an explicit alignment 270 // parameter in C++17 mode. 271 auto Size = sizeof(CallableT); 272 auto Alignment = alignof(CallableT); 273 CallableAddr = allocate_buffer(Size, Alignment); 274 setOutOfLineStorage(CallableAddr, Size, Alignment); 275 } 276 277 // Now move into the storage. 278 new (CallableAddr) CallableT(std::move(Callable)); 279 CallbackAndInlineFlag.setPointerAndInt( 280 &CallbacksHolder<CallableT, CalledAsT>::Callbacks, IsInlineStorage); 281 } 282 283 ~UniqueFunctionBase() { 284 if (!CallbackAndInlineFlag.getPointer()) 285 return; 286 287 // Cache this value so we don't re-check it after type-erased operations. 288 bool IsInlineStorage = isInlineStorage(); 289 290 if (!isTrivialCallback()) 291 getNonTrivialCallbacks()->DestroyPtr( 292 IsInlineStorage ? getInlineStorage() : getOutOfLineStorage()); 293 294 if (!IsInlineStorage) 295 deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(), 296 getOutOfLineStorageAlignment()); 297 } 298 299 UniqueFunctionBase(UniqueFunctionBase &&RHS) noexcept { 300 // Copy the callback and inline flag. 301 CallbackAndInlineFlag = RHS.CallbackAndInlineFlag; 302 303 // If the RHS is empty, just copying the above is sufficient. 304 if (!RHS) 305 return; 306 307 if (!isInlineStorage()) { 308 // The out-of-line case is easiest to move. 309 StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage; 310 } else if (isTrivialCallback()) { 311 // Move is trivial, just memcpy the bytes across. 312 memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize); 313 } else { 314 // Non-trivial move, so dispatch to a type-erased implementation. 315 getNonTrivialCallbacks()->MovePtr(getInlineStorage(), 316 RHS.getInlineStorage()); 317 } 318 319 // Clear the old callback and inline flag to get back to as-if-null. 320 RHS.CallbackAndInlineFlag = {}; 321 322 #ifndef NDEBUG 323 // In debug builds, we also scribble across the rest of the storage. 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 unique_function( 377 CallableT Callable, 378 detail::EnableUnlessSameType<CallableT, unique_function> * = nullptr, 379 detail::EnableIfCallable<CallableT, R, P...> * = nullptr) 380 : Base(std::forward<CallableT>(Callable), 381 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 417