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