This article investigates why the standard library needs a way to deduce a common type, how it is implemented and how it works.
To begin with, I'd like to thank my teammate Phillip. He helped me figure out some things in the C++ standard that I found ambiguous. He also helped me refine my code examples.
It all started when the PVS-Studio team set out to sift through and majorly enhance the C++ analyzer's core. Currently, one of the big tasks is to implement a new type system. Right now, our type system consists of strings encoded in a specific way. We want to replace this system with a hierarchical one. I won't go into too much detail about the new type system. Loosely put, we are trying to turn this:
into this:
If you want to know more about it, check out the talk my teammate Yuri gave at the itCppCon21 conference. There he discussed our old and new type systems in great detail - and showed funny pictures. By now, I think, he's assembled enough material for two or three new talks. So, we can all start looking forward to them :)
The new type system uses analogs of type_traits. These custom traits, same as their predecessors, help modify types and get the necessary information on types.
Just recently I wrote an std::common_type implementation for our type system. The original std::common_type trait is often used in metaprogramming to process an arbitrary number of types passed - and deduce a common type for them. We found our custom trait helpful when we needed to deduce a resulting type - for example, when we come across an arithmetic operation in a binary expression:
if (operationInfo->m_type == OperatorType::Arithmetic)
{
auto leftType = TypeTraits::ExtractMemberType
(result->GetLeftOperand().GetType());
auto rightType = TypeTraits::ExtractMemberType
(result->GetRightOperand().GetType());
auto resType = Types::Traits::CommonType(leftType, rightType);
....
}Before, this operation required much more code. Now the code looks elegant.
Suppose we want to write a naive implementation of a function template in order to calculate two vectors' dot product. These vectors can be instantiated with various types passed to them. The dot product type must be deduced automatically. In C++14 and later, one of the ways to implement such a function template is as follows:
#include <vector>
template <typename T, typename U>
auto dot_product(const std::vector<T> &a, const std::vector<U> &b)
{
// some bounds checks
??? result {};
auto a_it = a.begin();
auto b_it = b.begin();
while (a_it != a.end())
{
result += static_cast<???>(*a_it++) * static_cast<???>(*b_it++);
}
return result;
}The scenario assumes that the function receives vectors of the same size. Otherwise, calculating the dot product is impossible and will produce an array out-of-bounds error.
So, the function does exactly what we intended it to do. The compiler deduces for us the resulting type from the return statement. Only one problem remains - we somehow need to deduce the common type for the result variable.
However, before writing any code, let's study one very interesting language construct - the ternary operator. Maybe it can help us with this task.
Since the standard describes the ternary operator in great detail, covering the operator's every aspect here seems excessive. So, I'll focus on the most common cases that involve type deduction.
To help you understand the scenarios and results better, I'll use the following to help me present them:
Alright, let's get our hands dirty and look at some scenarios.
If the second and third operands are both of type void, then the result is also of type void. This is possible if both expressions contain, for example, throw, or calls to functions that return void, or explicit conversion to the void type. Below is some code that demonstrates this, with messages the compiler prints:
void foo();
void bar();
int foobar();
float barfoo();
template <typename ...>
struct tp; // type printer
void examples(bool flag)
{
tp<decltype(flag ? foo() : bar()), // void
decltype(flag ? (void) foobar() : (void) barfoo()), // void
decltype(flag ? throw 0 : throw 3.14)> _; // void
}If the second or third operand is a throw expression, then the resulting type is deduced from the other operand. In this case, the other operand must be of some type other than void. The code below demonstrates this scenario, with messages the compiler prints:
char arr[16];
template <typename ...>
struct tp; // type printer
void examples(bool flag)
{
tp<decltype(flag ? nullptr : throw "abs"), // nullptr_t
decltype(flag ? 3.14 : throw 3.14), // double
decltype(flag ? arr : throw 3.14)> _; // char (&)[16]
}If operand two and three are of different types and one of them is of a class type, the compiler chooses an overload that produces operands of the same types. For example, the compiler may choose a converting constructor or an implicit conversion operator. This is shown in the code below, with printed compiler messages:
template <typename ...>
struct tp; // type printer
struct IntWrapper
{
IntWrapper(int)
{
// ....
}
};
void examples(bool flag)
{
tp<decltype(flag ? IntWrapper {42} : 42)> _;
}If you take a look at the AST that Clang built for this code, you can notice the following:
....
-FunctionDecl <line:9:1, line:12:1> line:9:6 foo 'IntWrapper (bool)'
|-ParmVarDecl <col:10, col:15> col:15 used b 'bool'
`-CompoundStmt <line:10:1, line:12:1>
`-ReturnStmt <line:11:3, col:34>
`-ConditionalOperator <col:10, col:34> 'IntWrapper'
|-ImplicitCastExpr <col:10> 'bool' <LValueToRValue>
| `-DeclRefExpr <col:10> 'bool' lvalue ParmVar 0x558edcfc99d8 'b' 'bool'
|-CXXTemporaryObjectExpr <col:14, col:30> 'IntWrapper' 'void (int)' list
| `-IntegerLiteral <col:27> 'int' 42
`-ImplicitCastExpr <col:34> 'IntWrapper' <ConstructorConversion> // <=
`-CXXConstructExpr <col:34> 'IntWrapper' 'void (int)'
`-IntegerLiteral <col:34> 'int' 42 // <=Here Clang implicitly calls a converting constructor for the third operand, and consequently, both operands become of the same type - IntWrapper.
This scenario involves the second and third operands with standard conversions applied: lvalue-to-rvalue, array-to-pointer, or function-to-pointer. After the conversions are executed, several situations are possible.
If the second and third operands are of the same type, the resulting type will be the same. The codebelow demonstrates this, with messages the compiler prints:
template <typename ...>
struct tp; // type printer
struct MyClass
{
// ....
};
void examples(bool flag)
{
tp<decltype(flag ? MyClass {} : MyClass {})> _;
}The second and third operands can also have an arithmetic type or an enumeration type. For arithmetic and enumeration types, the usual arithmetic conversions form the common type. This common type is the resulting type. The code below demonstrates this, with printed compiler messages:
template <typename ...>
struct tp; // type printer
void examples(bool flag)
{
char ch = 1;
short sh = 2;
double d = 3;
float f = 4;
unsigned long long ull = 5;
long double ld = 6;
tp<decltype(flag ? ch : sh),
decltype(flag ? f : d),
decltype(flag ? ull : ld) > _;
}Note that one or both operands can be of type pointer or of type pointer-to-member. In this case a composite pointer type is formed and it becomes the resulting type. The following rules are used to form it: pointer conversions/pointer-to-member conversions, function pointer conversions and qualification conversions. This is what it looks like, with printed compiler messages:
template <typename ...>
struct tp; // type printer
struct MyBaseClass
{
// ....
};
struct MyClass : MyBaseClass
{
// ....
};
void examples(bool flag)
{
auto a = new MyClass();
auto b = new MyBaseClass();
tp<decltype(flag ? a : b)> _;
}Also, both operands can be of type std::nullptr_t. Or one operand can be of type std::nullptr_t, and the other one is nullptr. Then the resulting type is std::nullptr_t. This is what the code looks like, with printed compiler messages:
#include <cstddef>
template <typename ...>
struct tp; // type printer
void examples(bool flag)
{
tp<decltype(flag ? std::nullptr_t {} : nullptr )> _;
}Now we can see that deducing a common type is very easy - and in most cases the ternary operator can help. Well, enough theory. Let's use the principles described above and write some code that deduces a common type!
P.S. In order to write a custom std::common_type trait implementation for our new type system (TypeTraits::CommonType), we needed to use all common type deduction rules described above, and some that we haven't mentioned.
Let's get back to our function that calculates a dot product of vectors. Starting with C++11, we can use the decltype specifier that takes an expression and returns this expression's type. We've already used this specifier earlier - when we worked with type_printer. From the previous paragraph we know, that if decltype receives a ternary operator call with objects of two types, the compiler deduces the common type.
Let's try it:
#include <vector>
template <typename T, typename U>
auto dot_product(const std::vector<T> &a, const std::vector<U> &b)
{
// ....
decltype(true ? std::declval<T>() : std::declval<U>()) result {};
// ....
}Let's take a closer look at what this code does:
std::declval<T> is a function template with no implementation. This template returns an rvalue-link to type T. When T=void, the expression returns the void type. This template is often used in compile-time context (decltype, sizeof, requires, ....) and allows working with an object of the passed type and avoid the constructor call. This is especially useful if the T type does not have a default public constructor or if this constructor has been removed.
Note that as a type, you may get references. In this case std::decay comes in handy. It removes CV-qualifiers and references. It adds pointers for functions (function-to-pointer conversion) and converts arrays to pointers (array-to-pointer conversion):
#include <vector>
template <typename T, typename U>
auto dot_product(const std::vector<T> &a, const std::vector<U> &b)
{
// ....
std::decay_t<
decltype( true ? std::declval<typename std::decay<T>::type>()
: std::declval<typename std::decay<U>::type>()
)
> result {};
// ....
}Agree - most people wouldn't want to write this in their code. Let's try to refactor the code a little. To do this, we'll need to write a couple of helper class templates for convenience. First, let's try to write a class that deduces a common type for two types passed:
template <class T, class U>
struct common_type
{
using type = std::decay_t<
decltype( true ? std::declval< std::decay_t<T> >()
: std::declval< std::decay_t<U> >() ) >;
};Now we can use this common_type in our code:
#include <vector>
template <typename T, typename U>
auto dot_product(const std::vector<T> &a, const std::vector<U> &b)
{
// ....
common_type<T, U>::type result {};
// ....
}Excellent, we got rid of all this scary bunch of code and made the code easy to read. Now it's time to teach common_type to work with any number of types passed - from zero to n. Let's slightly change our basic class template and its specializations:
#include <type_traits>
template <typename ...>
struct common_type; // (1)
template <typename ...Ts>
using common_type_t = typename common_type<Ts...>::type;
template <>
struct common_type<> // (2)
{
};
template <class T>
struct common_type<T> // (3)
{
using type = std::decay_t<T>;
};
template <class T, class U>
struct common_type<T, U> // (4)
{
using type = std::decay_t<
decltype( true ? std::declval< std::decay_t<T> >()
: std::declval< std::decay_t<U> >() ) >;
};
template <class T, class U, class... V>
struct common_type<T, U, V...> // (5)
{
using type = typename common_type
<typename common_type<T,U>::type, V...>::type;
};It's worth mentioning that common_type is implemented in the standard library in a similar way. Now let's examine the code above and see what happens there:
As I said above, the complete information about the ternary operator's type inference is available in the standard. I used the latest up-to-date working draft. You can find this information in chapter 7.6.16. The drafts themselves are available, for example, here. You can also use documentation from cppreference.
In this article I've reviewed how std::common_type works. For a better understanding, we read the standard and wrote the trait's implementation - we even discussed the ternary operator's logic. I hope you find this article useful. Thank you for reading!