1//===--- TrailingObjects.h - Variable-length classes ------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9/// 10/// \file 11/// This header defines support for implementing classes that have 12/// some trailing object (or arrays of objects) appended to them. The 13/// main purpose is to make it obvious where this idiom is being used, 14/// and to make the usage more idiomatic and more difficult to get 15/// wrong. 16/// 17/// The TrailingObject template abstracts away the reinterpret_cast, 18/// pointer arithmetic, and size calculations used for the allocation 19/// and access of appended arrays of objects, and takes care that they 20/// are all allocated at their required alignment. Additionally, it 21/// ensures that the base type is final -- deriving from a class that 22/// expects data appended immediately after it is typically not safe. 23/// 24/// Users are expected to derive from this template, and provide 25/// numTrailingObjects implementations for each trailing type except 26/// the last, e.g. like this sample: 27/// 28/// \code 29/// class VarLengthObj : private TrailingObjects<VarLengthObj, int, double> { 30/// friend TrailingObjects; 31/// 32/// unsigned NumInts, NumDoubles; 33/// size_t numTrailingObjects(OverloadToken<int>) const { return NumInts; } 34/// }; 35/// \endcode 36/// 37/// You can access the appended arrays via 'getTrailingObjects', and 38/// determine the size needed for allocation via 39/// 'additionalSizeToAlloc' and 'totalSizeToAlloc'. 40/// 41/// All the methods implemented by this class are are intended for use 42/// by the implementation of the class, not as part of its interface 43/// (thus, private inheritance is suggested). 44/// 45//===----------------------------------------------------------------------===// 46 47#ifndef LLVM_SUPPORT_TRAILINGOBJECTS_H 48#define LLVM_SUPPORT_TRAILINGOBJECTS_H 49 50#include "llvm/Support/AlignOf.h" 51#include "llvm/Support/Compiler.h" 52#include "llvm/Support/MathExtras.h" 53#include "llvm/Support/type_traits.h" 54#include <new> 55#include <type_traits> 56 57namespace llvm { 58 59namespace trailing_objects_internal { 60/// Helper template to calculate the max alignment requirement for a set of 61/// objects. 62template <typename First, typename... Rest> class AlignmentCalcHelper { 63private: 64 enum { 65 FirstAlignment = alignof(First), 66 RestAlignment = AlignmentCalcHelper<Rest...>::Alignment, 67 }; 68 69public: 70 enum { 71 Alignment = FirstAlignment > RestAlignment ? FirstAlignment : RestAlignment 72 }; 73}; 74 75template <typename First> class AlignmentCalcHelper<First> { 76public: 77 enum { Alignment = alignof(First) }; 78}; 79 80/// The base class for TrailingObjects* classes. 81class TrailingObjectsBase { 82protected: 83 /// OverloadToken's purpose is to allow specifying function overloads 84 /// for different types, without actually taking the types as 85 /// parameters. (Necessary because member function templates cannot 86 /// be specialized, so overloads must be used instead of 87 /// specialization.) 88 template <typename T> struct OverloadToken {}; 89}; 90 91/// This helper template works-around MSVC 2013's lack of useful 92/// alignas() support. The argument to LLVM_ALIGNAS(), in MSVC, is 93/// required to be a literal integer. But, you *can* use template 94/// specialization to select between a bunch of different LLVM_ALIGNAS 95/// expressions... 96template <int Align> 97class TrailingObjectsAligner : public TrailingObjectsBase {}; 98template <> 99class LLVM_ALIGNAS(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {}; 100template <> 101class LLVM_ALIGNAS(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {}; 102template <> 103class LLVM_ALIGNAS(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {}; 104template <> 105class LLVM_ALIGNAS(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {}; 106template <> 107class LLVM_ALIGNAS(16) TrailingObjectsAligner<16> : public TrailingObjectsBase { 108}; 109template <> 110class LLVM_ALIGNAS(32) TrailingObjectsAligner<32> : public TrailingObjectsBase { 111}; 112 113// Just a little helper for transforming a type pack into the same 114// number of a different type. e.g.: 115// ExtractSecondType<Foo..., int>::type 116template <typename Ty1, typename Ty2> struct ExtractSecondType { 117 typedef Ty2 type; 118}; 119 120// TrailingObjectsImpl is somewhat complicated, because it is a 121// recursively inheriting template, in order to handle the template 122// varargs. Each level of inheritance picks off a single trailing type 123// then recurses on the rest. The "Align", "BaseTy", and 124// "TopTrailingObj" arguments are passed through unchanged through the 125// recursion. "PrevTy" is, at each level, the type handled by the 126// level right above it. 127 128template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy, 129 typename... MoreTys> 130class TrailingObjectsImpl { 131 // The main template definition is never used -- the two 132 // specializations cover all possibilities. 133}; 134 135template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy, 136 typename NextTy, typename... MoreTys> 137class TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy, NextTy, 138 MoreTys...> 139 : public TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy, 140 MoreTys...> { 141 142 typedef TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy, MoreTys...> 143 ParentType; 144 145 struct RequiresRealignment { 146 static const bool value = alignof(PrevTy) < alignof(NextTy); 147 }; 148 149 static constexpr bool requiresRealignment() { 150 return RequiresRealignment::value; 151 } 152 153protected: 154 // Ensure the inherited getTrailingObjectsImpl is not hidden. 155 using ParentType::getTrailingObjectsImpl; 156 157 // These two functions are helper functions for 158 // TrailingObjects::getTrailingObjects. They recurse to the left -- 159 // the result for each type in the list of trailing types depends on 160 // the result of calling the function on the type to the 161 // left. However, the function for the type to the left is 162 // implemented by a *subclass* of this class, so we invoke it via 163 // the TopTrailingObj, which is, via the 164 // curiously-recurring-template-pattern, the most-derived type in 165 // this recursion, and thus, contains all the overloads. 166 static const NextTy * 167 getTrailingObjectsImpl(const BaseTy *Obj, 168 TrailingObjectsBase::OverloadToken<NextTy>) { 169 auto *Ptr = TopTrailingObj::getTrailingObjectsImpl( 170 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) + 171 TopTrailingObj::callNumTrailingObjects( 172 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()); 173 174 if (requiresRealignment()) 175 return reinterpret_cast<const NextTy *>( 176 llvm::alignAddr(Ptr, alignof(NextTy))); 177 else 178 return reinterpret_cast<const NextTy *>(Ptr); 179 } 180 181 static NextTy * 182 getTrailingObjectsImpl(BaseTy *Obj, 183 TrailingObjectsBase::OverloadToken<NextTy>) { 184 auto *Ptr = TopTrailingObj::getTrailingObjectsImpl( 185 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) + 186 TopTrailingObj::callNumTrailingObjects( 187 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()); 188 189 if (requiresRealignment()) 190 return reinterpret_cast<NextTy *>(llvm::alignAddr(Ptr, alignof(NextTy))); 191 else 192 return reinterpret_cast<NextTy *>(Ptr); 193 } 194 195 // Helper function for TrailingObjects::additionalSizeToAlloc: this 196 // function recurses to superclasses, each of which requires one 197 // fewer size_t argument, and adds its own size. 198 static constexpr size_t additionalSizeToAllocImpl( 199 size_t SizeSoFar, size_t Count1, 200 typename ExtractSecondType<MoreTys, size_t>::type... MoreCounts) { 201 return ParentType::additionalSizeToAllocImpl( 202 (requiresRealignment() ? llvm::alignTo<alignof(NextTy)>(SizeSoFar) 203 : SizeSoFar) + 204 sizeof(NextTy) * Count1, 205 MoreCounts...); 206 } 207}; 208 209// The base case of the TrailingObjectsImpl inheritance recursion, 210// when there's no more trailing types. 211template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy> 212class TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy> 213 : public TrailingObjectsAligner<Align> { 214protected: 215 // This is a dummy method, only here so the "using" doesn't fail -- 216 // it will never be called, because this function recurses backwards 217 // up the inheritance chain to subclasses. 218 static void getTrailingObjectsImpl(); 219 220 static constexpr size_t additionalSizeToAllocImpl(size_t SizeSoFar) { 221 return SizeSoFar; 222 } 223 224 template <bool CheckAlignment> static void verifyTrailingObjectsAlignment() {} 225}; 226 227} // end namespace trailing_objects_internal 228 229// Finally, the main type defined in this file, the one intended for users... 230 231/// See the file comment for details on the usage of the 232/// TrailingObjects type. 233template <typename BaseTy, typename... TrailingTys> 234class TrailingObjects : private trailing_objects_internal::TrailingObjectsImpl< 235 trailing_objects_internal::AlignmentCalcHelper< 236 TrailingTys...>::Alignment, 237 BaseTy, TrailingObjects<BaseTy, TrailingTys...>, 238 BaseTy, TrailingTys...> { 239 240 template <int A, typename B, typename T, typename P, typename... M> 241 friend class trailing_objects_internal::TrailingObjectsImpl; 242 243 template <typename... Tys> class Foo {}; 244 245 typedef trailing_objects_internal::TrailingObjectsImpl< 246 trailing_objects_internal::AlignmentCalcHelper<TrailingTys...>::Alignment, 247 BaseTy, TrailingObjects<BaseTy, TrailingTys...>, BaseTy, TrailingTys...> 248 ParentType; 249 using TrailingObjectsBase = trailing_objects_internal::TrailingObjectsBase; 250 251 using ParentType::getTrailingObjectsImpl; 252 253 // This function contains only a static_assert BaseTy is final. The 254 // static_assert must be in a function, and not at class-level 255 // because BaseTy isn't complete at class instantiation time, but 256 // will be by the time this function is instantiated. 257 static void verifyTrailingObjectsAssertions() { 258#ifdef LLVM_IS_FINAL 259 static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final."); 260#endif 261 } 262 263 // These two methods are the base of the recursion for this method. 264 static const BaseTy * 265 getTrailingObjectsImpl(const BaseTy *Obj, 266 TrailingObjectsBase::OverloadToken<BaseTy>) { 267 return Obj; 268 } 269 270 static BaseTy * 271 getTrailingObjectsImpl(BaseTy *Obj, 272 TrailingObjectsBase::OverloadToken<BaseTy>) { 273 return Obj; 274 } 275 276 // callNumTrailingObjects simply calls numTrailingObjects on the 277 // provided Obj -- except when the type being queried is BaseTy 278 // itself. There is always only one of the base object, so that case 279 // is handled here. (An additional benefit of indirecting through 280 // this function is that consumers only say "friend 281 // TrailingObjects", and thus, only this class itself can call the 282 // numTrailingObjects function.) 283 static size_t 284 callNumTrailingObjects(const BaseTy *Obj, 285 TrailingObjectsBase::OverloadToken<BaseTy>) { 286 return 1; 287 } 288 289 template <typename T> 290 static size_t callNumTrailingObjects(const BaseTy *Obj, 291 TrailingObjectsBase::OverloadToken<T>) { 292 return Obj->numTrailingObjects(TrailingObjectsBase::OverloadToken<T>()); 293 } 294 295public: 296 // Make this (privately inherited) member public. 297#ifndef _MSC_VER 298 using ParentType::OverloadToken; 299#else 300 // MSVC bug prevents the above from working, at least up through CL 301 // 19.10.24629. 302 template <typename T> 303 using OverloadToken = typename ParentType::template OverloadToken<T>; 304#endif 305 306 /// Returns a pointer to the trailing object array of the given type 307 /// (which must be one of those specified in the class template). The 308 /// array may have zero or more elements in it. 309 template <typename T> const T *getTrailingObjects() const { 310 verifyTrailingObjectsAssertions(); 311 // Forwards to an impl function with overloads, since member 312 // function templates can't be specialized. 313 return this->getTrailingObjectsImpl( 314 static_cast<const BaseTy *>(this), 315 TrailingObjectsBase::OverloadToken<T>()); 316 } 317 318 /// Returns a pointer to the trailing object array of the given type 319 /// (which must be one of those specified in the class template). The 320 /// array may have zero or more elements in it. 321 template <typename T> T *getTrailingObjects() { 322 verifyTrailingObjectsAssertions(); 323 // Forwards to an impl function with overloads, since member 324 // function templates can't be specialized. 325 return this->getTrailingObjectsImpl( 326 static_cast<BaseTy *>(this), TrailingObjectsBase::OverloadToken<T>()); 327 } 328 329 /// Returns the size of the trailing data, if an object were 330 /// allocated with the given counts (The counts are in the same order 331 /// as the template arguments). This does not include the size of the 332 /// base object. The template arguments must be the same as those 333 /// used in the class; they are supplied here redundantly only so 334 /// that it's clear what the counts are counting in callers. 335 template <typename... Tys> 336 static constexpr typename std::enable_if< 337 std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type 338 additionalSizeToAlloc(typename trailing_objects_internal::ExtractSecondType< 339 TrailingTys, size_t>::type... Counts) { 340 return ParentType::additionalSizeToAllocImpl(0, Counts...); 341 } 342 343 /// Returns the total size of an object if it were allocated with the 344 /// given trailing object counts. This is the same as 345 /// additionalSizeToAlloc, except it *does* include the size of the base 346 /// object. 347 template <typename... Tys> 348 static constexpr typename std::enable_if< 349 std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type 350 totalSizeToAlloc(typename trailing_objects_internal::ExtractSecondType< 351 TrailingTys, size_t>::type... Counts) { 352 return sizeof(BaseTy) + ParentType::additionalSizeToAllocImpl(0, Counts...); 353 } 354 355 /// A type where its ::with_counts template member has a ::type member 356 /// suitable for use as uninitialized storage for an object with the given 357 /// trailing object counts. The template arguments are similar to those 358 /// of additionalSizeToAlloc. 359 /// 360 /// Use with FixedSizeStorageOwner, e.g.: 361 /// 362 /// \code{.cpp} 363 /// 364 /// MyObj::FixedSizeStorage<void *>::with_counts<1u>::type myStackObjStorage; 365 /// MyObj::FixedSizeStorageOwner 366 /// myStackObjOwner(new ((void *)&myStackObjStorage) MyObj); 367 /// MyObj *const myStackObjPtr = myStackObjOwner.get(); 368 /// 369 /// \endcode 370 template <typename... Tys> struct FixedSizeStorage { 371 template <size_t... Counts> struct with_counts { 372 enum { Size = totalSizeToAlloc<Tys...>(Counts...) }; 373 typedef llvm::AlignedCharArray<alignof(BaseTy), Size> type; 374 }; 375 }; 376 377 /// A type that acts as the owner for an object placed into fixed storage. 378 class FixedSizeStorageOwner { 379 public: 380 FixedSizeStorageOwner(BaseTy *p) : p(p) {} 381 ~FixedSizeStorageOwner() { 382 assert(p && "FixedSizeStorageOwner owns null?"); 383 p->~BaseTy(); 384 } 385 386 BaseTy *get() { return p; } 387 const BaseTy *get() const { return p; } 388 389 private: 390 FixedSizeStorageOwner(const FixedSizeStorageOwner &) = delete; 391 FixedSizeStorageOwner(FixedSizeStorageOwner &&) = delete; 392 FixedSizeStorageOwner &operator=(const FixedSizeStorageOwner &) = delete; 393 FixedSizeStorageOwner &operator=(FixedSizeStorageOwner &&) = delete; 394 395 BaseTy *const p; 396 }; 397}; 398 399} // end namespace llvm 400 401#endif 402