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 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 alignas()
95/// expressions...
96template <int Align>
97class TrailingObjectsAligner : public TrailingObjectsBase {};
98template <>
99class alignas(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {};
100template <>
101class alignas(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {};
102template <>
103class alignas(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {};
104template <>
105class alignas(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {};
106template <>
107class alignas(16) TrailingObjectsAligner<16> : public TrailingObjectsBase {
108};
109template <>
110class 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