11a6d157f84251df2e2b501cd7473476ed518f82
[lldb.git] / llvm / 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, 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
57 namespace llvm {
58
59 namespace trailing_objects_internal {
60 /// Helper template to calculate the max alignment requirement for a set of
61 /// objects.
62 template <typename First, typename... Rest> class AlignmentCalcHelper {
63 private:
64   enum {
65     FirstAlignment = AlignOf<First>::Alignment,
66     RestAlignment = AlignmentCalcHelper<Rest...>::Alignment,
67   };
68
69 public:
70   enum {
71     Alignment = FirstAlignment > RestAlignment ? FirstAlignment : RestAlignment
72   };
73 };
74
75 template <typename First> class AlignmentCalcHelper<First> {
76 public:
77   enum { Alignment = AlignOf<First>::Alignment };
78 };
79
80 /// The base class for TrailingObjects* classes.
81 class TrailingObjectsBase {
82 protected:
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...
96 template <int Align>
97 class TrailingObjectsAligner : public TrailingObjectsBase {};
98 template <>
99 class LLVM_ALIGNAS(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {};
100 template <>
101 class LLVM_ALIGNAS(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {};
102 template <>
103 class LLVM_ALIGNAS(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {};
104 template <>
105 class LLVM_ALIGNAS(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {};
106 template <>
107 class LLVM_ALIGNAS(16) TrailingObjectsAligner<16> : public TrailingObjectsBase {
108 };
109 template <>
110 class 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
116 template <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
128 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy,
129           typename... MoreTys>
130 struct TrailingObjectsImpl {
131   // The main template definition is never used -- the two
132   // specializations cover all possibilities.
133 };
134
135 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy,
136           typename NextTy, typename... MoreTys>
137 struct 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   // Ensure the methods we inherit are not hidden.
146   using ParentType::getTrailingObjectsImpl;
147   using ParentType::additionalSizeToAllocImpl;
148
149   static LLVM_CONSTEXPR bool requiresRealignment() {
150     return llvm::AlignOf<PrevTy>::Alignment < llvm::AlignOf<NextTy>::Alignment;
151   }
152
153   // These two functions are helper functions for
154   // TrailingObjects::getTrailingObjects. They recurse to the left --
155   // the result for each type in the list of trailing types depends on
156   // the result of calling the function on the type to the
157   // left. However, the function for the type to the left is
158   // implemented by a *subclass* of this class, so we invoke it via
159   // the TopTrailingObj, which is, via the
160   // curiously-recurring-template-pattern, the most-derived type in
161   // this recursion, and thus, contains all the overloads.
162   static const NextTy *
163   getTrailingObjectsImpl(const BaseTy *Obj,
164                          TrailingObjectsBase::OverloadToken<NextTy>) {
165     auto *Ptr = TopTrailingObj::getTrailingObjectsImpl(
166                     Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) +
167                 TopTrailingObj::callNumTrailingObjects(
168                     Obj, TrailingObjectsBase::OverloadToken<PrevTy>());
169
170     if (requiresRealignment())
171       return reinterpret_cast<const NextTy *>(
172           llvm::alignAddr(Ptr, llvm::alignOf<NextTy>()));
173     else
174       return reinterpret_cast<const NextTy *>(Ptr);
175   }
176
177   static NextTy *
178   getTrailingObjectsImpl(BaseTy *Obj,
179                          TrailingObjectsBase::OverloadToken<NextTy>) {
180     auto *Ptr = TopTrailingObj::getTrailingObjectsImpl(
181                     Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) +
182                 TopTrailingObj::callNumTrailingObjects(
183                     Obj, TrailingObjectsBase::OverloadToken<PrevTy>());
184
185     if (requiresRealignment())
186       return reinterpret_cast<NextTy *>(
187           llvm::alignAddr(Ptr, llvm::alignOf<NextTy>()));
188     else
189       return reinterpret_cast<NextTy *>(Ptr);
190   }
191
192   // Helper function for TrailingObjects::additionalSizeToAlloc: this
193   // function recurses to superclasses, each of which requires one
194   // fewer size_t argument, and adds its own size.
195   static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl(
196       size_t SizeSoFar, size_t Count1,
197       typename ExtractSecondType<MoreTys, size_t>::type... MoreCounts) {
198     return additionalSizeToAllocImpl(
199         (requiresRealignment()
200              ? llvm::alignTo(SizeSoFar, llvm::alignOf<NextTy>())
201              : SizeSoFar) +
202             sizeof(NextTy) * Count1,
203         MoreCounts...);
204   }
205 };
206
207 // The base case of the TrailingObjectsImpl inheritance recursion,
208 // when there's no more trailing types.
209 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy>
210 struct TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy>
211     : public TrailingObjectsAligner<Align> {
212   // This is a dummy method, only here so the "using" doesn't fail --
213   // it will never be called, because this function recurses backwards
214   // up the inheritance chain to subclasses.
215   static void getTrailingObjectsImpl();
216
217   static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl(size_t SizeSoFar) {
218     return SizeSoFar;
219   }
220
221   template <bool CheckAlignment> static void verifyTrailingObjectsAlignment() {}
222 };
223
224 } // end namespace trailing_objects_internal
225
226 // Finally, the main type defined in this file, the one intended for users...
227
228 /// See the file comment for details on the usage of the
229 /// TrailingObjects type.
230 template <typename BaseTy, typename... TrailingTys>
231 class TrailingObjects : private trailing_objects_internal::TrailingObjectsImpl<
232                             trailing_objects_internal::AlignmentCalcHelper<
233                                 TrailingTys...>::Alignment,
234                             BaseTy, TrailingObjects<BaseTy, TrailingTys...>,
235                             BaseTy, TrailingTys...> {
236
237   template <int A, typename B, typename T, typename P, typename... M>
238   friend struct trailing_objects_internal::TrailingObjectsImpl;
239
240   template <typename... Tys> class Foo {};
241
242   typedef trailing_objects_internal::TrailingObjectsImpl<
243       trailing_objects_internal::AlignmentCalcHelper<TrailingTys...>::Alignment,
244       BaseTy, TrailingObjects<BaseTy, TrailingTys...>, BaseTy, TrailingTys...>
245       ParentType;
246   using TrailingObjectsBase = trailing_objects_internal::TrailingObjectsBase;
247
248   using ParentType::getTrailingObjectsImpl;
249
250   // This function contains only a static_assert BaseTy is final. The
251   // static_assert must be in a function, and not at class-level
252   // because BaseTy isn't complete at class instantiation time, but
253   // will be by the time this function is instantiated.
254   static void verifyTrailingObjectsAssertions() {
255 #ifdef LLVM_IS_FINAL
256     static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final.");
257 #endif
258   }
259
260   // These two methods are the base of the recursion for this method.
261   static const BaseTy *
262   getTrailingObjectsImpl(const BaseTy *Obj,
263                          TrailingObjectsBase::OverloadToken<BaseTy>) {
264     return Obj;
265   }
266
267   static BaseTy *
268   getTrailingObjectsImpl(BaseTy *Obj,
269                          TrailingObjectsBase::OverloadToken<BaseTy>) {
270     return Obj;
271   }
272
273   // callNumTrailingObjects simply calls numTrailingObjects on the
274   // provided Obj -- except when the type being queried is BaseTy
275   // itself. There is always only one of the base object, so that case
276   // is handled here. (An additional benefit of indirecting through
277   // this function is that consumers only say "friend
278   // TrailingObjects", and thus, only this class itself can call the
279   // numTrailingObjects function.)
280   static size_t
281   callNumTrailingObjects(const BaseTy *Obj,
282                          TrailingObjectsBase::OverloadToken<BaseTy>) {
283     return 1;
284   }
285
286   template <typename T>
287   static size_t callNumTrailingObjects(const BaseTy *Obj,
288                                        TrailingObjectsBase::OverloadToken<T>) {
289     return Obj->numTrailingObjects(TrailingObjectsBase::OverloadToken<T>());
290   }
291
292 public:
293   // Make this (privately inherited) member public.
294   using ParentType::OverloadToken;
295
296   /// Returns a pointer to the trailing object array of the given type
297   /// (which must be one of those specified in the class template). The
298   /// array may have zero or more elements in it.
299   template <typename T> const T *getTrailingObjects() const {
300     verifyTrailingObjectsAssertions();
301     // Forwards to an impl function with overloads, since member
302     // function templates can't be specialized.
303     return this->getTrailingObjectsImpl(
304         static_cast<const BaseTy *>(this),
305         TrailingObjectsBase::OverloadToken<T>());
306   }
307
308   /// Returns a pointer to the trailing object array of the given type
309   /// (which must be one of those specified in the class template). The
310   /// array may have zero or more elements in it.
311   template <typename T> T *getTrailingObjects() {
312     verifyTrailingObjectsAssertions();
313     // Forwards to an impl function with overloads, since member
314     // function templates can't be specialized.
315     return this->getTrailingObjectsImpl(
316         static_cast<BaseTy *>(this), TrailingObjectsBase::OverloadToken<T>());
317   }
318
319   /// Returns the size of the trailing data, if an object were
320   /// allocated with the given counts (The counts are in the same order
321   /// as the template arguments). This does not include the size of the
322   /// base object.  The template arguments must be the same as those
323   /// used in the class; they are supplied here redundantly only so
324   /// that it's clear what the counts are counting in callers.
325   template <typename... Tys>
326   static LLVM_CONSTEXPR typename std::enable_if<
327       std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type
328       additionalSizeToAlloc(
329           typename trailing_objects_internal::ExtractSecondType<
330               TrailingTys, size_t>::type... Counts) {
331     return ParentType::additionalSizeToAllocImpl(0, Counts...);
332   }
333
334   /// Returns the total size of an object if it were allocated with the
335   /// given trailing object counts. This is the same as
336   /// additionalSizeToAlloc, except it *does* include the size of the base
337   /// object.
338   template <typename... Tys>
339   static LLVM_CONSTEXPR typename std::enable_if<
340       std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type
341       totalSizeToAlloc(typename trailing_objects_internal::ExtractSecondType<
342                        TrailingTys, size_t>::type... Counts) {
343     return sizeof(BaseTy) + ParentType::additionalSizeToAllocImpl(0, Counts...);
344   }
345
346   /// A type where its ::with_counts template member has a ::type member
347   /// suitable for use as uninitialized storage for an object with the given
348   /// trailing object counts. The template arguments are similar to those
349   /// of additionalSizeToAlloc.
350   ///
351   /// Use with FixedSizeStorageOwner, e.g.:
352   ///
353   /// \code{.cpp}
354   ///
355   /// MyObj::FixedSizeStorage<void *>::with_counts<1u>::type myStackObjStorage;
356   /// MyObj::FixedSizeStorageOwner
357   ///     myStackObjOwner(new ((void *)&myStackObjStorage) MyObj);
358   /// MyObj *const myStackObjPtr = myStackObjOwner.get();
359   ///
360   /// \endcode
361   template <typename... Tys> struct FixedSizeStorage {
362     template <size_t... Counts> struct with_counts {
363       typedef llvm::AlignedCharArray<
364           llvm::AlignOf<BaseTy>::Alignment, totalSizeToAlloc<Tys...>(Counts...)
365           > type;
366     };
367   };
368
369   /// A type that acts as the owner for an object placed into fixed storage.
370   class FixedSizeStorageOwner {
371   public:
372     FixedSizeStorageOwner(BaseTy *p) : p(p) {}
373     ~FixedSizeStorageOwner() {
374       assert(p && "FixedSizeStorageOwner owns null?");
375       p->~BaseTy();
376     }
377
378     BaseTy *get() { return p; }
379     const BaseTy *get() const { return p; }
380
381   private:
382     FixedSizeStorageOwner(const FixedSizeStorageOwner &) = delete;
383     FixedSizeStorageOwner(FixedSizeStorageOwner &&) = delete;
384     FixedSizeStorageOwner &operator=(const FixedSizeStorageOwner &) = delete;
385     FixedSizeStorageOwner &operator=(FixedSizeStorageOwner &&) = delete;
386
387     BaseTy *const p;
388   };
389 };
390
391 } // end namespace llvm
392
393 #endif