Analysis of libc++ STL Source Code – type_trait (Part 1)

In the previous section of the analysis of libc++ STL source code – type_trait, I provided a brief introduction to the type_traits of libc++’s STL library. In this section, we will explain and analyze the following five traits:

• add_cv_quals

• add_pointer

• add_reference

• aligned_storage

• aligned_union

Before analyzing this part of the source code, we will first introduce some techniques of template metaprogramming, mainly including:

• Variadic templates

• Compile-time recursion

• Template parameter packs

First, let’s introduce the concept related to template metaprogramming, variadic templates.

1. Template Metaprogramming – Variadic Templates

Variadic templates refer to templates where the parameters are variable. For example, the following template class is a variadic template.

template <typename ...Args>struct T {};

The class template T above is a variadic template, and Args is a parameter pack.

Regarding variadic templates, the following points should be noted:

• The template parameter pack can only be the last template parameter of the primary template.

• However, the template parameter pack can appear in any position of a specialized or partially specialized template.

For example, for the above template class T, its partially specialized version can take the following form:

template <typename ...Args, template <typename ...Args> class Ty>struct T<Ty<Args...>> {};

The variadic template parameter in the partially specialized version of the class template T appears in the first position.

An important use case for variadic templates is: storing type information. If you want to obtain a certain type stored in a variadic template, you need to implement compile-time recursion to retrieve the corresponding type.

Now let’s look at a scenario where we want to obtain the first type of a set of types. We can implement it as follows:

template <typename... _Types>struct type_list {};template <typename>struct type_list_head;template <typename _Head, typename... _Tail>struct type_list_head<type_list<_Head, _Tail...>> {  using type = _Head;};

Here we have implemented a variadic template type_list that only stores type information, and the specialized version of type_list_head is used to obtain the first type in the type_list class template.

With the above type_list_head class, we can implement a tool to find the first type whose sizeof operator returns a size greater than or equal to a given value.

template <typename _TypeList, size_t _Size, bool = _Size <= sizeof(typename type_list_head<_TypeList>::type)>struct find_first;template <typename _Head, typename... _Tail, size_t _Size>struct find_first<type_list<_Head, _Tail...>, _Size, true> {  using type = _Head;};template <typename _Head, typename... _Tail, size_t _Size>struct find_first<type_list<_Head, _Tail...>, _Size, false> {  using type = typename find_first<type_list<_Tail...>, _Size>::type;};

The purpose of the above find_first class template is to recursively find a type T that satisfies sizeof(T) >= _Size.

To understand how find_first works, we need to explain a relatively important concept in template metaprogramming: parameter pack expansion

Parameter pack expansion requires the use of the … operator. For example, the above

type_list<_Head, _Tail...>

uses parameter pack expansion. Assuming _Tail is

 _Head1, _Head2, _Head3

as a parameter pack, then after applying the parameter pack expansion operator, _Tail takes the following form:

type_list<_Head, _Head1, _Head2, _Head3>

To add, parameter pack expansion can also be applied in expressions.

In C++17, the fold expression introduced also uses the … operator, which will not be elaborated here. We will continue to introduce it when we encounter it in subsequent source code analyses. Now let’s dive into the actual STL source code analysis.

Let’s start with the most challenging part: aligned_storage.

2. aligned_storage

<span>std::aligned_storage provides a block of</span>raw memory space that meets specified size and alignment requirements, which can be used to store uninitialized objects of any type. If the parameters are invalid or specialized, the behavior is undefined. For a detailed explanation, please refer tohttps://en.cppreference.com/w/cpp/types/aligned_storage.html The implementation of this trait is in the file libcxx/include/__type_traits/aligned_storage.h. Now let’s analyze this part of the source code. Here, I will remove some unnecessary macros and present the modified code as follows:

template <class _Tp>struct __align_type {  static const size_t value = _LIBCPP_PREFERRED_ALIGNOF(_Tp);  typedef _Tp type;};struct __struct_double {  long double __lx;};struct __struct_double4 {  double __lx[4];};using __all_types =    __type_list<__align_type<unsigned char>,                __align_type<unsigned short>,                __align_type<unsigned int>,                __align_type<unsigned long>,                __align_type<unsigned long long>,                __align_type<double>,                __align_type<long double>,                __align_type<__struct_double>,                __align_type<__struct_double4>,                __align_type<int*> >;template <class _TL, size_t _Len>struct __find_max_align;template <class _Head, size_t _Len>struct __find_max_align<__type_list<_Head>, _Len> : public integral_constant<size_t, _Head::value> {};template <size_t _Len, size_t _A1, size_t _A2>struct __select_align {private:  static const size_t __min = _A2 < _A1 ? _A2 : _A1;  static const size_t __max = _A1 < _A2 ? _A2 : _A1;public:  static const size_t value = _Len < __max ? __min : __max;};template <class _Head, class... _Tail, size_t _Len>struct __find_max_align<__type_list<_Head, _Tail...>, _Len>    : public integral_constant<          size_t,          __select_align<_Len, _Head::value, __find_max_align<__type_list<_Tail...>, _Len>::value>::value> {};template <size_t _Len, size_t _Align = __find_max_align<__all_types, _Len>::value>struct _LIBCPP_DEPRECATED_IN_CXX23 _LIBCPP_NO_SPECIALIZATIONS aligned_storage {  union _ALIGNAS(_Align) type {    unsigned char __data[(_Len + _Align - 1) / _Align * _Align];  };};#if _LIBCPP_STD_VER >= 14template <size_t _Len, size_t _Align = __find_max_align<__all_types, _Len>::value>using aligned_storage_t _LIBCPP_DEPRECATED_IN_CXX23 = typename aligned_storage<_Len, _Align>::type;#endif

For the above source code, let’s first introduce several macros that appear in the source code:

_LIBCPP_DEPRECATED_IN_CXX23: indicates that this feature will be removed after C++23.

_LIBCPP_NO_SPECIALIZATIONS: this macro is defined as follows:

#  if __has_cpp_attribute(_Clang::__no_specializations__)#    define _LIBCPP_NO_SPECIALIZATIONS                                                                                 \
      [[_Clang::__no_specializations__("Users are not allowed to specialize this standard library entity")]]#  else#    define _LIBCPP_NO_SPECIALIZATIONS#  endif

<span>[[__no_specializations__]]</span> is a Clang extension attribute used to inform the compiler:

“Users are not allowed to specialize this standard library template.”

This feature can also be applied in our own template code.<span>_LIBCPP_NO_SPECIALIZATIONS</span> is used tomark standard library templates as non-specializable by users; if the compiler supports this attribute, it enables warnings/errors, otherwise, it is an empty macro.

_ALIGNAS(x): this macro is defined as # define _ALIGNAS(x) alignas(x)

alignas is a keyword introduced in modern C++ that specifies the alignment of a variable or type. alignas can be applied to both fundamental types and user-defined types. When alignas is applied to a class, struct, or union, it must be placed after the class, struct, or union keyword and before the type name to specify the alignment of that user-defined class. For a detailed explanation, please refer tohttps://book.douban.com/subject/35706615/ (

Embracing Modern C++ Safely) for further understanding.

_LIBCPP_PREFERRED_ALIGNOF: this macro is defined as

#  define _LIBCPP_PREFERRED_ALIGNOF(_Tp) __alignof(_Tp)

<span>_LIBCPP_PREFERRED_ALIGNOF(T)</span> returns the alignment requirement of type <span>T</span>, which is equivalent to the C++ built-in operator <span>alignof(T)</span>, but <span>__alignof</span> is the compiler built-in version (commonly found in GCC / Clang). For example:

_LIBCPP_PREFERRED_ALIGNOF(int)       // usually 4_LIBCPP_PREFERRED_ALIGNOF(double)    // usually 8_LIBCPP_PREFERRED_ALIGNOF(long long) // possibly 8

Now let’s analyze the implementation of aligned_storage in detail. The aligned_storage class template is implemented as follows:

template <size_t _Len, size_t _Align = __find_max_align<__all_types, _Len>::value>struct _LIBCPP_DEPRECATED_IN_CXX23 _LIBCPP_NO_SPECIALIZATIONS aligned_storage {  union _ALIGNAS(_Align) type {    unsigned char __data[(_Len + _Align - 1) / _Align * _Align];  };};

This class template contains two template parameters:

_Len: the requiredsize of storage space (in bytes)

_Align: alignment requirement, defaulting to the strictest alignment value among all types not exceeding <span>_Len</span>.

The class template internally defines a union, which is aligned to _Align, and the internal implementation of the union is an unsigned char array of size

(_Len + _Align - 1) / _Align * _Align

This expression performs a classic calculation – “rounding up to the alignment boundary”.

Assuming:

• <span>_Len</span> is the target length (for example, the number of bytes you need)

• <span>_Align</span> is the alignment unit (for example, 8-byte alignment)

The purpose of the expression is:

to calculate a value that is not less than <span>_Len</span> and is a <span>_Align</span> multiple.

In other words, it aligns the length to a multiple of <span>_Align</span>.

Next, let’s continue to see how the aligned_storage class template calculates _Align. This uses some basic concepts introduced at the beginning of this article: variadic templates, template recursion, and parameter pack expansion. The core implementation for calculating _Align is as follows:

size_t _Align = __find_max_align<__all_types, _Len>::value

This uses template metaprogramming techniques to map types to a certain value. This process is implemented by

__find_max_align

This class template is implemented as follows:

template <class _TL, size_t _Len>struct __find_max_align;template <class _Head, size_t _Len>struct __find_max_align<__type_list<_Head>, _Len> : public integral_constant<size_t, _Head::value> {};template <size_t _Len, size_t _A1, size_t _A2>struct __select_align {private:  static const size_t __min = _A2 < _A1 ? _A2 : _A1;  static const size_t __max = _A1 < _A2 ? _A2 : _A1;public:  static const size_t value = _Len < __max ? __min : __max;};template <class _Head, class... _Tail, size_t _Len>struct __find_max_align<__type_list<_Head, _Tail...>, _Len>    : public integral_constant<          size_t,          __select_align<_Len, _Head::value, __find_max_align<__type_list<_Tail...>, _Len>::value>::value> {};

The above defines the __find_max_align primary template with two template parameters and two specialization versions. Let’s first look at specialization version 1:

template <class _Head, size_t _Len>struct __find_max_align<__type_list<_Head>, _Len>   : public integral_constant<size_t, _Head::value> {};

__type_list is a container that retains type information, defined inlibcxx/include/__type_traits/type_list.h, implemented as:

template <class... _Types>struct __type_list {};

The base class of specialization version 1 is a class templateintegral_constant, defined inlibcxx/include/__type_traits/integral_constant.h, implemented as:

template <class _Tp, _Tp __v>struct _LIBCPP_NO_SPECIALIZATIONS integral_constant {  static inline _LIBCPP_CONSTEXPR const _Tp value = __v;  typedef _Tp value_type;  typedef integral_constant type;   _LIBCPP_CONSTEXPR operator value_type() const _NOEXCEPT { return value; }#if _LIBCPP_STD_VER >= 14   constexpr value_type operator()() const _NOEXCEPT { return value; }#endif};

<span>std::integral_constant<T, v> is a type that saves a constant value at compile time,</span>acting as both a “type” and a “value”, which is a cornerstone of C++ template metaprogramming. Returning to the class template __find_max_align specialization version 1, the work it accomplishes is: when there is only one element left in the type list (i.e., <span><span>__type_list<_Head></span></span>), the result of <span><span>__find_max_align</span></span> is the alignment value of that type.Next, let’s look at the second specialization version of __find_max_align, implemented as follows:

template <size_t _Len, size_t _A1, size_t _A2>struct __select_align {private:  static const size_t __min = _A2 < _A1 ? _A2 : _A1;  static const size_t __max = _A1 < _A2 ? _A2 : _A1;public:  static const size_t value = _Len < __max ? __min : __max;};template <class _Head, class... _Tail, size_t _Len>struct __find_max_align<__type_list<_Head, _Tail...>, _Len>    : public integral_constant<          size_t,          __select_align<_Len, _Head::value, __find_max_align<__type_list<_Tail...>, _Len>::value>::value> {};

This segment of code is the recursive implementation part of the __find_max_align template, which is the core logic for calculating the maximum alignment value under the specified size <span>_Len</span><span> among a set of types.</span><code><span>__select_align is used to choose the "appropriate one" between two alignment values </span><span>_A1</span> and <span>_A2</span>, depending on the target length <span>_Len</span>. If the required storage space <span>_Len</span> is less than the maximum alignment value, the smaller alignment is used; otherwise, the larger alignment is used. This is to avoid selecting a high alignment requirement for small objects (wasting space).<span>__find_max_align traverses the alignment values of a set of types, determining the most suitable alignment value under the specified length </span><code><span>_Len</span><span>, thus returning the maximum alignment requirement that can accommodate </span><strong><span>_Len</span></strong><span> bytes without excessive waste.</span><p>Finally, let’s take a look at the implementation of __all_types:</p><pre><code class="language-plaintext">template <class _Tp>struct __align_type { static const size_t value = _LIBCPP_PREFERRED_ALIGNOF(_Tp); typedef _Tp type;};struct __struct_double { long double __lx;};struct __struct_double4 { double __lx[4];};using __all_types = __type_list<__align_type<unsigned char>, __align_type<unsigned short>, __align_type<unsigned int>, __align_type<unsigned long>, __align_type<unsigned long long>, __align_type<double>, __align_type<long double>, __align_type<__struct_double>, __align_type<__struct_double4>, __align_type<int*> >;<span>_align_type is a</span>wrapper structure that saves the <span>alignment requirement</span> of a certain type <span>_Tp</span> and exposes two pieces of information:static const size_t value: the alignment value of that type, equivalent to <span>alignof(_Tp)</span><span>typedef _Tp type: the type itself, used for type passing in metaprogramming</span>

struct __struct_double {  long double __lx;};struct __struct_double4 {  double __lx[4];};

The existence of these two structures is to:

introduce some types with higher alignment requirements to cover the maximum alignment needs that may exist on different platforms.

For example:

• <span>__struct_double</span> may align to <span>alignof(long double)</span>;

• <span>__struct_double4</span> (an array of 4 doubles) typically has higher alignment requirements (such as 32 or 64 bytes, corresponding to SIMD boundaries).

This is to ensure that:

regardless of what the maximum alignment requirement of the target platform is, there is a suitable candidate type available.

In the next section, we will continue the analysis of the type_traits source code.