include/llvm/Support/TrailingObjects.h

   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, as well as asserts that
  20 /// the alignment of the classes involved are appropriate for the
  21 /// usage. Additionally, it ensures that the base type is final --
  22 /// deriving from a class that expects data appended immediately after
  23 /// it is typically not safe.
  24 ///
  25 /// Users are expected to derive from this template, and provide
  26 /// numTrailingObjects implementations for each trailing type,
  27 /// e.g. like this sample:
  28 ///
  29 /// \code
  30 /// class VarLengthObj : private TrailingObjects<VarLengthObj, int, double> {
  31 ///   friend TrailingObjects;
  32 ///
  33 ///   unsigned NumInts, NumDoubles;
  34 ///   size_t numTrailingObjects(OverloadToken<int>) const { return NumInts; }
  35 ///   size_t numTrailingObjects(OverloadToken<double>) const {
  36 ///     return NumDoubles;
  37 ///   }
  38 ///  };
  39 /// \endcode
  40 ///
  41 /// You can access the appended arrays via 'getTrailingObjects', and
  42 /// determine the size needed for allocation via
  43 /// 'additionalSizeToAlloc' and 'totalSizeToAlloc'.
  44 ///
  45 /// All the methods implemented by this class are are intended for use
  46 /// by the implementation of the class, not as part of its interface
  47 /// (thus, private inheritance is suggested).
  48 ///
  49 //===----------------------------------------------------------------------===//
  50
  51 #ifndef LLVM_SUPPORT_TRAILINGOBJECTS_H
  52 #define LLVM_SUPPORT_TRAILINGOBJECTS_H
  53
  54 #include <new>
  55 #include <type_traits>
  56 #include "llvm/Support/AlignOf.h"
  57 #include "llvm/Support/Compiler.h"
  58 #include "llvm/Support/type_traits.h"
  59
  60 namespace llvm {
  61
  62 namespace trailing_objects_internal {
  63 /// Helper template to calculate the max alignment requirement for a set of
  64 /// objects.
  65 template <typename First, typename... Rest> class AlignmentCalcHelper {
  66 private:
  67   enum {
  68     FirstAlignment = AlignOf<First>::Alignment,
  69     RestAlignment = AlignmentCalcHelper<Rest...>::Alignment,
  70   };
  71
  72 public:
  73   enum {
  74     Alignment = FirstAlignment > RestAlignment ? FirstAlignment : RestAlignment
  75   };
  76 };
  77
  78 template <typename First> class AlignmentCalcHelper<First> {
  79 public:
  80   enum { Alignment = AlignOf<First>::Alignment };
  81 };
  82
  83 /// The base class for TrailingObjects* classes.
  84 class TrailingObjectsBase {
  85 protected:
  86   /// OverloadToken's purpose is to allow specifying function overloads
  87   /// for different types, without actually taking the types as
  88   /// parameters. (Necessary because member function templates cannot
  89   /// be specialized, so overloads must be used instead of
  90   /// specialization.)
  91   template <typename T> struct OverloadToken {};
  92 };
  93
  94 /// This helper template works-around MSVC 2013's lack of useful
  95 /// alignas() support. The argument to LLVM_ALIGNAS(), in MSVC, is
  96 /// required to be a literal integer. But, you *can* use template
  97 /// specialization to select between a bunch of different LLVM_ALIGNAS
  98 /// expressions...
  99 template <int Align>
 100 class TrailingObjectsAligner : public TrailingObjectsBase {};
 101 template <>
 102 class LLVM_ALIGNAS(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {};
 103 template <>
 104 class LLVM_ALIGNAS(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {};
 105 template <>
 106 class LLVM_ALIGNAS(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {};
 107 template <>
 108 class LLVM_ALIGNAS(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {};
 109 template <>
 110 class LLVM_ALIGNAS(16) TrailingObjectsAligner<16> : public TrailingObjectsBase {
 111 };
 112 template <>
 113 class LLVM_ALIGNAS(32) TrailingObjectsAligner<32> : public TrailingObjectsBase {
 114 };
 115
 116 // Just a little helper for transforming a type pack into the same
 117 // number of a different type. e.g.:
 118 //   ExtractSecondType<Foo..., int>::type
 119 template <typename Ty1, typename Ty2> struct ExtractSecondType {
 120   typedef Ty2 type;
 121 };
 122
 123 // TrailingObjectsImpl is somewhat complicated, because it is a
 124 // recursively inheriting template, in order to handle the template
 125 // varargs. Each level of inheritance picks off a single trailing type
 126 // then recurses on the rest. The "Align", "BaseTy", and
 127 // "TopTrailingObj" arguments are passed through unchanged through the
 128 // recursion. "PrevTy" is, at each level, the type handled by the
 129 // level right above it.
 130
 131 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy,
 132           typename... MoreTys>
 133 struct TrailingObjectsImpl {
 134   // The main template definition is never used -- the two
 135   // specializations cover all possibilities.
 136 };
 137
 138 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy,
 139           typename NextTy, typename... MoreTys>
 140 struct TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy, NextTy,
 141                            MoreTys...>
 142     : public TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy,
 143                                  MoreTys...> {
 144
 145   typedef TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy, MoreTys...>
 146       ParentType;
 147
 148   // Ensure the methods we inherit are not hidden.
 149   using ParentType::getTrailingObjectsImpl;
 150   using ParentType::additionalSizeToAllocImpl;
 151
 152   static void verifyTrailingObjectsAssertions() {
 153     static_assert(llvm::AlignOf<PrevTy>::Alignment >=
 154                       llvm::AlignOf<NextTy>::Alignment,
 155                   "A trailing object requires more alignment than the previous "
 156                   "trailing object provides");
 157
 158     ParentType::verifyTrailingObjectsAssertions();
 159   }
 160
 161   // These two functions are helper functions for
 162   // TrailingObjects::getTrailingObjects. They recurse to the left --
 163   // the result for each type in the list of trailing types depends on
 164   // the result of calling the function on the type to the
 165   // left. However, the function for the type to the left is
 166   // implemented by a *subclass* of this class, so we invoke it via
 167   // the TopTrailingObj, which is, via the
 168   // curiously-recurring-template-pattern, the most-derived type in
 169   // this recursion, and thus, contains all the overloads.
 170   static const NextTy *
 171   getTrailingObjectsImpl(const BaseTy *Obj,
 172                          TrailingObjectsBase::OverloadToken<NextTy>) {
 173     return reinterpret_cast<const NextTy *>(
 174         TopTrailingObj::getTrailingObjectsImpl(
 175             Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) +
 176         TopTrailingObj::callNumTrailingObjects(
 177             Obj, TrailingObjectsBase::OverloadToken<PrevTy>()));
 178   }
 179
 180   static NextTy *
 181   getTrailingObjectsImpl(BaseTy *Obj,
 182                          TrailingObjectsBase::OverloadToken<NextTy>) {
 183     return reinterpret_cast<NextTy *>(
 184         TopTrailingObj::getTrailingObjectsImpl(
 185             Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) +
 186         TopTrailingObj::callNumTrailingObjects(
 187             Obj, TrailingObjectsBase::OverloadToken<PrevTy>()));
 188   }
 189
 190   // Helper function for TrailingObjects::additionalSizeToAlloc: this
 191   // function recurses to superclasses, each of which requires one
 192   // fewer size_t argument, and adds its own size.
 193   static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl(
 194       size_t Count1,
 195       typename ExtractSecondType<MoreTys, size_t>::type... MoreCounts) {
 196     return sizeof(NextTy) * Count1 + additionalSizeToAllocImpl(MoreCounts...);
 197   }
 198 };
 199
 200 // The base case of the TrailingObjectsImpl inheritance recursion,
 201 // when there's no more trailing types.
 202 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy>
 203 struct TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy>
 204     : public TrailingObjectsAligner<Align> {
 205   // This is a dummy method, only here so the "using" doesn't fail --
 206   // it will never be called, because this function recurses backwards
 207   // up the inheritance chain to subclasses.
 208   static void getTrailingObjectsImpl();
 209
 210   static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl() { return 0; }
 211
 212   static void verifyTrailingObjectsAssertions() {}
 213 };
 214
 215 } // end namespace trailing_objects_internal
 216
 217 // Finally, the main type defined in this file, the one intended for users...
 218
 219 /// See the file comment for details on the usage of the
 220 /// TrailingObjects type.
 221 template <typename BaseTy, typename... TrailingTys>
 222 class TrailingObjects : private trailing_objects_internal::TrailingObjectsImpl<
 223                             trailing_objects_internal::AlignmentCalcHelper<
 224                                 TrailingTys...>::Alignment,
 225                             BaseTy, TrailingObjects<BaseTy, TrailingTys...>,
 226                             BaseTy, TrailingTys...> {
 227
 228   template <int A, typename B, typename T, typename P, typename... M>
 229   friend struct trailing_objects_internal::TrailingObjectsImpl;
 230
 231   template <typename... Tys> class Foo {};
 232
 233   typedef trailing_objects_internal::TrailingObjectsImpl<
 234       trailing_objects_internal::AlignmentCalcHelper<TrailingTys...>::Alignment,
 235       BaseTy, TrailingObjects<BaseTy, TrailingTys...>, BaseTy, TrailingTys...>
 236       ParentType;
 237   using TrailingObjectsBase = trailing_objects_internal::TrailingObjectsBase;
 238
 239   using ParentType::getTrailingObjectsImpl;
 240
 241   // Contains static_assert statements for the alignment of the
 242   // types. Must not be at class-level, because BaseTy isn't complete
 243   // at class instantiation time, but will be by the time this
 244   // function is instantiated. Recurses through the superclasses.
 245   static void verifyTrailingObjectsAssertions() {
 246 #ifdef LLVM_IS_FINAL
 247     static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final.");
 248 #endif
 249     ParentType::verifyTrailingObjectsAssertions();
 250   }
 251
 252   // These two methods are the base of the recursion for this method.
 253   static const BaseTy *
 254   getTrailingObjectsImpl(const BaseTy *Obj,
 255                          TrailingObjectsBase::OverloadToken<BaseTy>) {
 256     return Obj;
 257   }
 258
 259   static BaseTy *
 260   getTrailingObjectsImpl(BaseTy *Obj,
 261                          TrailingObjectsBase::OverloadToken<BaseTy>) {
 262     return Obj;
 263   }
 264
 265   // callNumTrailingObjects simply calls numTrailingObjects on the
 266   // provided Obj -- except when the type being queried is BaseTy
 267   // itself. There is always only one of the base object, so that case
 268   // is handled here. (An additional benefit of indirecting through
 269   // this function is that consumers only say "friend
 270   // TrailingObjects", and thus, only this class itself can call the
 271   // numTrailingObjects function.)
 272   static size_t
 273   callNumTrailingObjects(const BaseTy *Obj,
 274                          TrailingObjectsBase::OverloadToken<BaseTy>) {
 275     return 1;
 276   }
 277
 278   template <typename T>
 279   static size_t callNumTrailingObjects(const BaseTy *Obj,
 280                                        TrailingObjectsBase::OverloadToken<T>) {
 281     return Obj->numTrailingObjects(TrailingObjectsBase::OverloadToken<T>());
 282   }
 283
 284 public:
 285   // make this (privately inherited) class public.
 286   using ParentType::OverloadToken;
 287
 288   /// Returns a pointer to the trailing object array of the given type
 289   /// (which must be one of those specified in the class template). The
 290   /// array may have zero or more elements in it.
 291   template <typename T> const T *getTrailingObjects() const {
 292     verifyTrailingObjectsAssertions();
 293     // Forwards to an impl function with overloads, since member
 294     // function templates can't be specialized.
 295     return this->getTrailingObjectsImpl(
 296         static_cast<const BaseTy *>(this),
 297         TrailingObjectsBase::OverloadToken<T>());
 298   }
 299
 300   /// Returns a pointer to the trailing object array of the given type
 301   /// (which must be one of those specified in the class template). The
 302   /// array may have zero or more elements in it.
 303   template <typename T> T *getTrailingObjects() {
 304     verifyTrailingObjectsAssertions();
 305     // Forwards to an impl function with overloads, since member
 306     // function templates can't be specialized.
 307     return this->getTrailingObjectsImpl(
 308         static_cast<BaseTy *>(this), TrailingObjectsBase::OverloadToken<T>());
 309   }
 310
 311   /// Returns the size of the trailing data, if an object were
 312   /// allocated with the given counts (The counts are in the same order
 313   /// as the template arguments). This does not include the size of the
 314   /// base object.  The template arguments must be the same as those
 315   /// used in the class; they are supplied here redundantly only so
 316   /// that it's clear what the counts are counting in callers.
 317   template <typename... Tys>
 318   static LLVM_CONSTEXPR typename std::enable_if<
 319       std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type
 320       additionalSizeToAlloc(
 321           typename trailing_objects_internal::ExtractSecondType<
 322               TrailingTys, size_t>::type... Counts) {
 323     return ParentType::additionalSizeToAllocImpl(Counts...);
 324   }
 325
 326   /// Returns the total size of an object if it were allocated with the
 327   /// given trailing object counts. This is the same as
 328   /// additionalSizeToAlloc, except it *does* include the size of the base
 329   /// object.
 330   template <typename... Tys>
 331   static LLVM_CONSTEXPR typename std::enable_if<
 332       std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type
 333       totalSizeToAlloc(typename trailing_objects_internal::ExtractSecondType<
 334                        TrailingTys, size_t>::type... Counts) {
 335     return sizeof(BaseTy) + ParentType::additionalSizeToAllocImpl(Counts...);
 336   }
 337 };
 338
 339 } // end namespace llvm
 340
 341 #endif