Which <Type_Traits> Cannot Be Implemented Without Compiler Hooks

Which type_traits cannot be implemented without compiler hooks?

I have written up a complete answer here — it's a work in progress, so I'm giving the authoritative hyperlink even though I'm cutting-and-pasting the text into this answer.

Also see libc++'s documentation on Type traits intrinsic design.

is_union

is_union queries an attribute of the class that isn't exposed through any other means;
in C++, anything you can do with a class or struct, you can also do with a union. This
includes inheriting and taking member pointers.

is_aggregate, is_literal_type, is_pod, is_standard_layout, has_virtual_destructor

These traits query attributes of the class that aren't exposed through any other means.
Essentially, a struct or class is a "black box"; the C++ language gives us no way to
crack it open and examine its data members to find out if they're all POD types, or if
any of them are private, or if the class has any constexpr constructors (the key
requirement for is_literal_type).

is_abstract

is_abstract is an interesting case. The defining characteristic of an abstract
class type is that you cannot get a value of that type; so for example it is
ill-formed to define a function whose parameter or return type is abstract, and
it is ill-formed to create an array type whose element type is abstract.
(Oddly, if T is abstract, then SFINAE will apply to T[] but not to T(). That
is, it is acceptable to create the type of a function with an abstract return type;
it is ill-formed to define an entity of such a function type.)

So we can get very close to a correct implementation of is_abstract using
this SFINAE approach:

template<class T, class> struct is_abstract_impl : true_type {};
template<class T> struct is_abstract_impl<T, void_t<T[]>> : false_type {};

template<class T> struct is_abstract : is_abstract_impl<remove_cv_t<T>, void> {};

However, there is a flaw! If T is itself a template class, such as vector<T>
or basic_ostream<char>, then merely forming the type T[] is acceptable; in
an unevaluated context this will not cause the compiler to go instantiate the
body of T, and therefore the compiler will not detect the ill-formedness of
the array type T[]. So the SFINAE will not happen in that case, and we'll
give the wrong answer for is_abstract<basic_ostream<char>>.

This quirk of template instantiation in unevaluated contexts is the sole reason
that modern compilers provide __is_abstract(T).

is_final

is_final queries an attribute of the class that isn't exposed through any other means.
Specifically, the base-specifier-list of a derived class is not a SFINAE context; we can't
exploit enable_if_t to ask "can I create a class derived from T?" because if we
cannot create such a class, it'll be a hard error.

is_empty

is_empty is an interesting case. We can't just ask whether sizeof (T) == 0 because
in C++ no type is ever allowed to have size 0; even an empty class has sizeof (T) == 1.
"Emptiness" is important enough to merit a type trait, though, because of the Empty Base
Optimization: all sufficiently modern compilers will lay out the two classes

struct Derived : public T { int x; };

struct Underived { int x; };

identically; that is, they will not lay out any space in Derived for the empty
T subobject. This suggests a way we could test for "emptiness" in C++03, at least
on all sufficiently modern compilers: just define the two classes above and ask
whether sizeof (Derived) == sizeof (Underived). Unfortunately, as of C++11, this
trick no longer works, because T might be final, and the "final-ness" of a class
type is not exposed by any other means! So compiler vendors who implement final
must also expose something like __is_empty(T) for the benefit of the standard library.

is_enum

is_enum is another interesting case. Technically, we could implement this type trait
by the observation that if our type T is not a fundamental type, an array type,
a pointer type, a reference type, a member pointer, a class or union, or a function
type, then by process of elimination it must be an enum type. However, this deductive
reasoning breaks down if the compiler happens to support any other types not falling
into the above categories. For this reason, modern compilers expose __is_enum(T).

A common example of a supported type not falling into any of the above categories
would be __int128_t. libc++ actually detects the presence of __int128_t and includes
it in the category of "integral types" (which makes it a "fundamental type" in the above
categorization), but our simple implementation does not.

Another example would be vector int, on compilers supporting Altivec vector extensions;
this type is more obviously "not integral" but also "not anything else either", and most
certainly not an enum type!

is_trivially_constructible, is_trivially_assignable

The triviality of construction, assignment, and destruction are all attributes of the
class that aren't exposed through any other means. Notice that with this foundation
we don't need any additional magic to query the triviality of default construction,
copy construction, move assignment, and so on. Instead,
is_trivially_copy_constructible<T> is implemented in terms of
is_trivially_constructible<T, const T&>, and so on.

is_trivially_destructible

For historical reasons, the name of this compiler builtin is not __is_trivially_destructible(T)
but rather __has_trivial_destructor(T). Furthermore, it turns out that the builtin
evaluates to true even for a class type with a deleted destructor! So we first need
to check that the type is destructible; and then, if it is, we can ask the magic builtin
whether that destructor is indeed trivial.

underlying_type

The underlying type of an enum isn't exposed through any other means. You can get close
by taking sizeof(T) and comparing it to the sizes of all known types, and by asking
for the signedness of the underlying type via T(-1) < T(0); but that approach still
cannot distinguish between underlying types int and long on platforms where those
types have the same width (nor between long and long long on platforms where those
types have the same width).

Why is there no language support in C++ for all C++ standard library type traits?

There are many aspects of the C++ standard library which cannot be implemented without support from the compiler. For example, type_info. A "freestanding C++ library" implementation can't provide such a type, since it is the result of a keyword-based expression: typeid. The only people who could provide such a thing are compiler writers, since the compiler is the one who has to generate those objects.

The same is true of many other elements of the standard library. exception_ptr, current_exception(s), initializer_list, etc. There's a whole chapter of this stuff in the C++ standard.

Not all components of the standard library can be implemented without compiler support. Type traits are simply one more thing which a freestanding C++ library cannot implement. Not in ISO standard C++.

As for why they didn't provide the tools needed to implement them? Because that would have taken more time. Note that reflection isn't even a fully-formed TS yet, while type-traits have been standard for 5 years now.

It is difficult to specify general tools like reflection. To know exactly what behavior you need and how it should be provided. It's much easier to look at common usage patterns (as exemplified by Boost) and just use them. Type-traits are the low-hanging fruit of reflection.

How does the compiler define the classes in type_traits?

Back in the olden days, when people were first fooling around with type traits, they wrote some really nasty template code in attempts to write portable code to detect certain properties. My take on this was that you had to put a drip-pan under your computer to catch the molten metal as the compiler overheated trying to compile this stuff. Steve Adamczyk, of Edison Design Group (provider of industrial-strength compiler frontends), had a more constructive take on the problem: instead of writing all this template code that takes enormous amounts of compiler time and often breaks them, ask me to provide a helper function.

When type traits were first formally introduced (in TR1, 2006), there were several traits that nobody knew how to implement portably. Since TR1 was supposed to be exclusively library additions, these couldn't count on compiler help, so their specifications allowed them to get an answer that was occasionally wrong, but they could be implemented in portable code.

Nowadays, those allowances have been removed; the library has to get the right answer. The compiler help for doing this isn't special knowledge of particular templates; it's a function call that tells you whether a particular class has a particular property. The compiler can recognize the name of the function, and provide an appropriate answer. This provides a lower-level toolkit that the traits templates can use, individually or in combination, to decide whether the class has the trait in question.

Which standard c++ classes cannot be reimplemented in c++?

std::type_info is a simple class, although populating it requires typeinfo: a compiler construct.

Likewise, exceptions are normal objects, but throwing exceptions requires compiler magic (where are the exceptions allocated?).

The question, to me, is "how close can we get to std::initializer_lists without compiler magic?"

Looking at wikipedia, std::initializer_list<typename T> can be initialized by something that looks a lot like an array literal. Let's try giving our std::initializer_list<typename T> a conversion constructor that takes an array (i.e., a constructor that takes a single argument of T[]):

namespace std {
     template<typename T> class initializer_list {
         T internal_array[];
         public:
         initializer_list(T other_array[]) : internal_array(other_array) { };

         // ... other methods needed to actually access internal_array
     }
}

Likewise, a class that uses a std::initializer_list does so by declaring a constructor that takes a single std::initializer_list argument -- a.k.a. a conversion constructor:

struct my_class {
    ...
    my_class(std::initializer_list<int>) ...
}

So the line:

 my_class m = {1, 2, 3};

Causes the compiler to think: "I need to call a constructor for my_class; my_class has a constructor that takes a std::initializer_list<int>; I have an int[] literal; I can convert an int[] to a std::initializer_list<int>; and I can pass that to the my_class constructor" (please read to the end of the answer before telling me that C++ doesn't allow two implicit user-defined conversions to be chained).

So how close is this? First, I'm missing a few features/restrictions of initializer lists. One thing I don't enforce is that initializer lists can only be constructed with array literals, while my initializer_list would also accept an already-created array:

int arry[] = {1, 2, 3};
my_class = arry;

Additionally, I didn't bother messing with rvalue references.

Finally, this class only works as the new standard says it should if the compiler implicitly chains two user-defined conversions together. This is specifically prohibited under normal cases, so the example still needs compiler magic. But I would argue that (1) the class itself is a normal class, and (2) the magic involved (enforcing the "array literal" initialization syntax and allowing two user-defined conversions to be implicitly chained) is less than it seems at first glance.

How does the std::is_union implementation work?

Not all of the std library can be implemented in C++.

You skipped the tests for various intrinsics.

There is no way to implment is_union without intrinsics, essentially.

The std library is not a library that ships with C++, it is part of the language. #include <vector> permits certain code to work; no vector header need exist, just the state of the C++ program has to change after the directive.

In practice (by design) it is written and implemented in C++ as a relatively conventional library with the help from intrinsics, and written with reserved tokens to avoid preprocessor conflicts (the __ and _Ty variable names, for example).

C++ Type Traits

Some type traits, like std::is_class just use compiler intrinsics (aka built-ins). You cannot write these yourself without special support from the compiler.

Type traits are mostly useful in generic context—you may want to specialize things based on the properties of types, or impose restrictions on template arguments. For example, an implementation of std::copy may use std::memcpy internally instead of an explicit loop when the iterators are pointers to PODs. This can be achieved with SFINAE.

Where is static_assert implemented?

static_assert is a new language-level feature in C++11, rather than a library included in a header file. A compliant C++ implementation is free to implement static_assert however it likes. It could be built into the compiler (I suspect most compilers do this), or it could be a part of a library (though this would be challenging, since static_assert doesn't require a header file). I think the best way to find out which it is for your particular compiler would be to check the documentation and, if necessary, to look over the source.

Is there magic in the STL?

in other words, has anything been done to the compiler to allow for a 'special case' the STL needed to work?

No.

It was all implemented as 'pure' C++ code, using the magic of templates.

There has been some work done to compilers to improve the STL (I'm thinking about various optimisations) but otherwise, no, you could write the entire STL if you really wanted. Some people did - STLPort is an implementation that didn't have the backing of any compiler manufacturer.

---

Related Topics